Cache Strategies

The previous lesson placed the cache by hand inside the read path: look it up, fetch it from the origin if it is missing, store it. This pattern has a name, and it is not the only option. A cache can sit beside the read path, or it can be a layer that every read passes through. On the write path there is a separate question: when the origin is updated, what happens to the cached copy — is it updated at the same time, is it deleted, or does the write go to the cache first?

This lesson runs three strategies against the same workload: cache-aside, write-through, and write-behind. What gets measured is the number of reads and writes reaching the origin, and the number of records where the origin actually falls behind.

Measurement Setup

The measurement runs on the shelf-copy count: issuing a loan lowers this number, and a return raises it. It is the most frequently written field in the library data, which makes it well suited to distinguishing between write strategies. A column holding this count is added to the book table from the previous lesson.

# setup.sh — the lesson's database: a shelf-copy count column is added to the book table
rm -f library.db
sqlite3 library.db <<'SQL'
CREATE TABLE branch (branch_id INTEGER PRIMARY KEY, name TEXT NOT NULL, city TEXT NOT NULL);
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author TEXT NOT NULL,
                    branch_id INTEGER REFERENCES branch(branch_id), on_shelf INTEGER NOT NULL);
INSERT INTO branch VALUES (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul');
INSERT INTO book SELECT n, 'Book ' || n, 'Author ' || (n % 10 + 1), n % 3 + 1, 3
  FROM (WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 60) SELECT n FROM s);
SQL
sqlite3 library.db "SELECT 'book=' || count(*) || ' total_on_shelf=' || sum(on_shelf) FROM book;"

book=60 total_on_shelf=180

The workload is 1200 operations: 85% reads, 15% writes, concentrated on twelve popular books. Each strategy runs against its own copy of the database, so the comparison starts from the same initial state.

Three Strategies

All three setups expose the same interface: read and write. The difference between them lies only in the bodies of these two functions.

// strategies.mjs — same workload across three strategies: origin access and inconsistency are measured
import { DatabaseSync } from "node:sqlite";
import { copyFileSync, rmSync } from "node:fs";

// Same workload: 85% reads, 15% writes; requests concentrate on the first 12 books.
function workload(count) {
  let seed = 20250729;
  const random = () => ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648);
  return Array.from({ length: count }, () => {
    const isWrite = random() < 0.15;
    return [isWrite ? "write" : "read", Math.floor(random() * 12) + 1, isWrite ? (random() < 0.5 ? -1 : 1) : 0];
  });
}

function openOrigin(file) {
  rmSync(file, { force: true });
  copyFileSync("library.db", file);
  const db = new DatabaseSync(file);
  const s = { reads: 0, writes: 0 };
  return {
    s,
    read: (id) => { s.reads += 1; return db.prepare("SELECT on_shelf FROM book WHERE book_id = ?").get(id).on_shelf; },
    write: (id, d) => { s.writes += 1; db.prepare("UPDATE book SET on_shelf = ? WHERE book_id = ?").run(d, id); },
    check: (id) => db.prepare("SELECT on_shelf FROM book WHERE book_id = ?").get(id).on_shelf,
    close: () => db.close(),
  };
}

function run(name, setup) {
  const origin = openOrigin(`${name}.db`);
  const cache = new Map();
  const truth = new Map();                       // the workload's logical ground truth
  const m = { hit: 0, miss: 0, stale: 0 };
  const { read, write, finish } = setup(origin, cache, m);
  for (const [kind, id, delta] of workload(1200)) {
    if (kind === "read") {
      const d = read(id);
      if (!truth.has(id)) truth.set(id, origin.check(id));
      if (d !== truth.get(id)) m.stale += 1;
    } else {
      if (!truth.has(id)) truth.set(id, origin.check(id));
      const next = Math.max(0, truth.get(id) + delta);
      truth.set(id, next);
      write(id, next);
    }
  }
  const pending = finish ? finish() : 0;
  const diverged = [...truth.keys()].filter((id) => origin.check(id) !== truth.get(id)).length;
  origin.close();
  rmSync(`${name}.db`, { force: true });
  return { name, ...origin.s, ...m, pending, diverged };
}

const cacheAside = (o, c, m) => ({
  read(id) {
    if (c.has(id)) { m.hit += 1; return c.get(id); }
    m.miss += 1; const d = o.read(id); c.set(id, d); return d;
  },
  write(id, d) { o.write(id, d); c.delete(id); },     // entry is deleted after the write
});

const writeThrough = (o, c, m) => ({
  read(id) {
    if (c.has(id)) { m.hit += 1; return c.get(id); }
    m.miss += 1; const d = o.read(id); c.set(id, d); return d;
  },
  write(id, d) { o.write(id, d); c.set(id, d); },     // origin and cache are updated together
});

const writeBehind = (o, c, m) => {
  const pending = new Map();
  let count = 0;
  return {
    read(id) {
      if (c.has(id)) { m.hit += 1; return c.get(id); }
      m.miss += 1; const d = o.read(id); c.set(id, d); return d;
    },
    write(id, d) {                                  // write goes to the cache first, the origin later
      c.set(id, d); pending.set(id, d);
      if ((count += 1) % 20 === 0) { for (const [i, v] of pending) o.write(i, v); pending.clear(); }
    },
    finish: () => pending.size,                   // writes that would be lost if the process stopped here
  };
};

const headers = ["strategy", "org.reads", "org.writes", "hits", "misses", "stale", "pending", "diverged"];
console.log(headers.map((h, i) => (i === 0 ? h.padEnd(16) : h.padStart(11))).join(""));
for (const [name, setup] of [["cache-aside", cacheAside], ["write-through", writeThrough], ["write-behind", writeBehind]]) {
  const r = run(name.replace(/ /g, "-"), setup);
  console.log(name.padEnd(16) + [r.reads, r.writes, r.hit, r.miss, r.stale, r.pending, r.diverged]
    .map((n) => String(n).padStart(11)).join(""));
}

strategy          org.reads org.writes       hits     misses      stale    pending   diverged
cache-aside             156        175        869        156          0          0          0
write-through             7        175       1018          7          0          0          0
write-behind              7         74       1018          7          0         10          5

What the Numbers Say

Cache-aside made 156 origin reads. There are twelve distinct keys; the remaining 144 misses came from the entry being deleted after every write. Every deleted entry gets reloaded on the next read. This is the strategy’s cost: as write frequency rises, so does the miss count.

Write-through made 7 origin reads — just one for each key seen for the first time. Because a write updates the cached entry with the new value instead of deleting it, the entry never dropped out. The hit count rose from 869 to 1018. In exchange, the cache starts carrying values that may never be read again: a rarely read book’s shelf count enters the cache on every write and takes up space.

Write-behind lowered the origin write count from 175 to 74. Writes went to the cache first, were flushed to the origin in a batch every twenty writes, and consecutive writes to the same book merged into a single update. It is the only strategy that cuts the write load on the origin to less than half.

The last two columns show the price of this gain. When the workload ended, 10 writes were still pending in the cache, and 5 records at the origin had diverged from their true value. Had the process stopped at that moment, those writes would have been lost — the cache rests on memory, the origin on disk. Write-behind pays with durability to lower the write load. In the library example, one copy of the shelf count can be lost; the same strategy cannot be used for the loan record itself.

It is worth noting that the stale column is zero on every row. None of the three strategies gave the reader a wrong value, because all of them reflected the write in the cache. The inconsistency did not occur at the reader; it occurred between the origin and the cache, and it showed up in the diverged column.

Cache-Aside’s Race

In the run above, operations executed one after another. On a real server, two requests advance at the same time, and a known gap in cache-aside surfaces: a miss load can collide with a write. The block below builds this ordering step by step.

// cache-aside-race.mjs — cache-aside's classic race: a miss load collides with a write
import { DatabaseSync } from "node:sqlite";
import { copyFileSync, rmSync } from "node:fs";

rmSync("race.db", { force: true });
copyFileSync("library.db", "race.db");
const db = new DatabaseSync("race.db");
const originRead = (id) => db.prepare("SELECT on_shelf FROM book WHERE book_id = ?").get(id).on_shelf;
const originWrite = (id, d) => db.prepare("UPDATE book SET on_shelf = ? WHERE book_id = ?").run(d, id);
const cache = new Map();
const log = (step, text) => console.log(`${String(step).padStart(2)}. ${text.padEnd(54)} ` +
  `cache=${cache.has(7) ? cache.get(7) : "-"} origin=${originRead(7)}`);

// Request A: it is reading, took a miss, and read the origin; it has not stored it in the cache yet.
const aRead = originRead(7);
log(1, "A: miss, read from the origin (value in hand)");

// Request B completes in between: one copy was checked out.
originWrite(7, aRead - 1);
cache.delete(7);
log(2, "B: updated the origin, deleted the cache entry");

// Request A now stores the stale value it is holding in the cache.
cache.set(7, aRead);
log(3, "A: stored the stale value it was holding in the cache");

let stale = 0;
for (let i = 0; i < 50; i++) {
  const d = cache.has(7) ? cache.get(7) : originRead(7);
  if (d !== originRead(7)) stale += 1;
}
log(4, `stale among the next 50 reads: ${stale}`);
db.close();
rmSync("race.db", { force: true });

 1. A: miss, read from the origin (value in hand)          cache=- origin=3
 2. B: updated the origin, deleted the cache entry         cache=- origin=2
 3. A: stored the stale value it was holding in the cache  cache=3 origin=2
 4. stale among the next 50 reads: 50                      cache=3 origin=2

The write rule was followed to the letter — the origin was updated, the entry was deleted — and the cache still ended up stale. The flaw is in the ordering: a delete cannot delete an entry that has not been stored yet. Staleness does not correct itself; the wrong value is served until the entry is written again or its lifetime expires.

This is proof that cache-aside is never sufficient on its own. It is paired with at least a time limit; when the ordering must be resolved definitively, a version stamp is added to the entry, or loading the same key is collapsed into a single call. All three are the subject of later lessons.

Selection Criteria

The three strategies are not interchangeable options; each fits a different read–write ratio.

For read-heavy, rarely changing data, cache-aside is enough; the code only needs to know the read path, and the application keeps running if the cache goes down. Where the same key is both read and written often, write-through avoids misses, in exchange for filling the cache with values that are never read. Where the write rate exceeds what the origin can bear and the loss of individual writes is tolerable, write-behind lowers the load; where the loss is not tolerable, this strategy is ruled out.

There is also a fourth option, in which the write never touches the cache at all: write-around. The origin is updated; the cache entry is neither deleted nor written, so it stays stale until it expires. It is used for data written once and not read again for a long time, to avoid polluting the cache, but it means the staleness window is accepted outright.

Summary

• Cache-aside deletes the entry on a write; across the 1200-operation workload it produced 156 origin reads, 144 of which were reloads of deleted entries.
• Write-through updates the entry instead of deleting it, which brought origin reads down to 7 and raised the hit count to 1018; in exchange, it also keeps values in the cache that are never read.
• Write-behind lowered origin writes from 175 to 74, because consecutive writes to the same key merged in the batch flush; its cost is 10 pending writes that would be lost if the process stopped.
• In all three strategies, the reader never saw a stale value; the inconsistency occurred between the origin and the cache. Write-behind cannot be used for data that requires durability.
• When a miss load collides with a write in cache-aside, the delete has no effect, and the stale entry does not correct itself; the strategy is not sufficient on its own.

Next Step

The last measurement left a question open: when does a stale entry in the cache go away? Every strategy in this lesson assumed it caught the moment of the write. That assumption falls apart when the write comes from another process, when the data is changed directly in the database, or when an ordering flaw like the one above occurs. How long an entry should live, which event should evict it, and how a stale entry becomes unreachable when the key itself changes are a separate set of decisions. The next lesson compares time-based, event-based, and version-based invalidation on the same workload and measures the number of stale reads each one produces.