Invalidation

The previous lesson’s last measurement left behind a stale entry: even though the write rule was followed, the old value stayed in the cache, and it stayed there for fifty reads. Without a mechanism to evict that entry, the problem does not resolve itself.

Evicting an entry from the cache is called invalidation, and it has three distinct triggers. An entry can drop on its own after a set period, an event can evict it, or the key itself can change and make the entry unreachable. This lesson runs all three against the same workload and measures the number of stale reads each one produces.

Measurement Setup

The schema is the one from the previous lesson; the outbox table introduced in the Business Logic Placement topic is added on top of it. The write operation both updates the shelf count and drops an event record into this table within the same transaction.

# setup.sh — the previous lesson's schema, plus the outbox table from M16/K04
rm -f library.db
sqlite3 library.db <<'SQL'
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL,
                    branch_id INTEGER NOT NULL, on_shelf INTEGER NOT NULL);
CREATE TABLE outbox (message_id INTEGER PRIMARY KEY, body TEXT NOT NULL,
                           status TEXT NOT NULL DEFAULT 'pending');
INSERT INTO book SELECT n, 'Book ' || n, 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 again 1200 operations. The clock is not real time but the workload step: every operation advances the clock by one. This way, the lifetime comparison produces the same numbers independent of the machine; the unit of time is the step, not milliseconds.

Three Approaches

The three strategies answer the same three questions differently: what is the key, how long does the entry live, and what happens when a write occurs.

// invalidation.mjs — time-based, event-based, and version-based invalidation on the same workload
import { DatabaseSync } from "node:sqlite";
import { copyFileSync, rmSync } from "node:fs";

function workload(count) {                            // 85% reads, 15% writes, 12 popular books
  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 };
  return {
    s, db,
    read: (id) => { s.reads += 1; return db.prepare("SELECT on_shelf FROM book WHERE book_id = ?").get(id).on_shelf; },
    truth: (id) => db.prepare("SELECT on_shelf FROM book WHERE book_id = ?").get(id).on_shelf,
    write(id, delta) {                               // write and event in the same transaction (outbox)
      db.exec("BEGIN");
      const next = Math.max(0, this.truth(id) + delta);
      db.prepare("UPDATE book SET on_shelf = ? WHERE book_id = ?").run(next, id);
      db.prepare("INSERT INTO outbox (body) VALUES (?)").run(JSON.stringify({ bookId: id }));
      db.exec("COMMIT");
    },
    close: () => db.close(),
  };
}

function run(label, setup) {
  const origin = openOrigin("invalidation.db");
  const box = new Map();                          // key -> { value, validUntil }
  const m = { hit: 0, miss: 0, stale: 0 };
  let step = 0;                                    // clock: not real time, the workload step
  const strategy = setup(origin, box, () => step);
  for (const [kind, id, delta] of workload(1200)) {
    step += 1;
    if (kind === "read") {
      const key = strategy.key(id);
      const entry = box.get(key);
      let value;
      if (entry && entry.validUntil > step) { m.hit += 1; value = entry.value; }
      else { m.miss += 1; value = origin.read(id); box.set(key, { value, validUntil: strategy.lifetime(step) }); }
      if (value !== origin.truth(id)) m.stale += 1;
    } else {
      origin.write(id, delta);
      strategy.written(id);
    }
    strategy.tick?.();
  }
  origin.close();
  rmSync("invalidation.db", { force: true });
  return `${label.padEnd(22)}${[origin.s.reads, m.hit, m.miss, m.stale].map((n) => String(n).padStart(10)).join("")}`;
}

// 1) Time-based: a write never touches the cache, the entry drops once its lifetime runs out.
const timeBased = (lifetime) => () => ({
  key: (id) => `book:${id}`,
  lifetime: (step) => step + lifetime,
  written: () => {},
});

// 2) Event-based: a write produces an event in the outbox, the consumer deletes the key.
const eventBased = (delay) => (origin, box) => {
  let count = 0;
  return {
    key: (id) => `book:${id}`,
    lifetime: () => Infinity,
    written: () => {},
    tick() {                                      // the consumer runs once every `delay` steps
      if ((count += 1) % delay !== 0) return;
      const messages = origin.db.prepare(
        "SELECT message_id, body FROM outbox WHERE status = 'pending'").all();
      for (const msg of messages) {
        box.delete(`book:${JSON.parse(msg.body).bookId}`);
        origin.db.prepare("UPDATE outbox SET status = 'processed' WHERE message_id = ?").run(msg.message_id);
      }
    },
  };
};

// 3) Version-based: the key carries a version; a write raises the version, the old key becomes unreachable.
const versionBased = () => {
  const version = new Map();
  return {
    key: (id) => `book:v${version.get(id) ?? 1}:${id}`,
    lifetime: () => Infinity,
    written: (id) => version.set(id, (version.get(id) ?? 1) + 1),
  };
};

console.log(["invalidation", "org.reads", "hits", "misses", "stale"]
  .map((h, i) => (i === 0 ? h.padEnd(22) : h.padStart(10))).join(""));
console.log(run("time (lifetime=10)", timeBased(10)));
console.log(run("time (lifetime=50)", timeBased(50)));
console.log(run("time (lifetime=200)", timeBased(200)));
console.log(run("event (delay=5)", eventBased(5)));
console.log(run("event (delay=25)", eventBased(25)));
console.log(run("version", versionBased));

invalidation           org.reads      hits    misses     stale
time (lifetime=10)           626       399       626        18
time (lifetime=50)           232       793       232       147
time (lifetime=200)           72       953        72       445
event (delay=5)              155       870       155        14
event (delay=25)             153       872       153        97
version                      156       869       156         0

What the Numbers Say

The time-based rows trace a single curve. As the lifetime rises from ten to two hundred, origin reads fall from 626 to 72, and stale reads rise from 18 to 445. These two numbers are the two ends of the same dial: the lifetime is the exchange rate between the load placed on the origin and the staleness accepted in return. As it approaches zero, the cache becomes pointless; as it grows, the cache builds its own reality.

The event-based rows step off this curve. With a five-step consumer delay, origin reads are 155 and stale reads are 14. For the same level of staleness, the time-based approach demanded four times as many origin reads. The difference comes from tying invalidation to a cause: the entry drops not because time passed, but because the data changed. A key that never changes stays in the cache forever.

The weakness of the event-based approach shows up in the second row. When the consumer delay rose from five to twenty-five, stale reads climbed from 14 to 97. The staleness window is now the time between an event being produced and being processed. This is a delivery problem: the event was produced and recorded, but no one has read it yet.

In the version-based row, stale reads are zero. Because the write changes the key, the old entry is never even looked up; the new key is never found in the cache, so the first read goes to the origin. Origin reads, at 156, are nearly the same as the event-based approach, but staleness has been eliminated entirely.

When the Version Enters the Key

Version-based invalidation has two consequences: no delete ever happens, and old entries keep sitting in the cache. The block below shows both. It also shows that a version can be placed on an entire namespace instead of a single record; this form is called a generation.

// version-key.mjs — once the version enters the key, old entries become unreachable, but are not deleted
const box = new Map();
const version = new Map();                        // version per book
let branchVersion = 1;                            // a shared version at the branch level (generation)

const bookKey = (id) => `book:v${version.get(id) ?? 1}:${id}`;
const listKey = (branchId, page) => `branch:${branchId}:g${branchVersion}:list:${page}`;

box.set(bookKey(7), { on_shelf: 3 });
box.set(listKey(2, 1), ["Book 5", "Book 8"]);
box.set(listKey(2, 2), ["Book 11"]);
console.log("starting keys:", [...box.keys()].join("  "));

version.set(7, 2);                                // book 7 was updated
branchVersion += 1;                               // branch lists are invalidated in bulk
console.log("key looked up for book 7         :", bookKey(7),
  "-> in cache:", box.has(bookKey(7)));
console.log("key looked up for branch 2 page 1:", listKey(2, 1),
  "-> in cache:", box.has(listKey(2, 1)));

box.set(bookKey(7), { on_shelf: 2 });
const live = new Set([bookKey(7), listKey(2, 1), listKey(2, 2)]);
const orphaned = [...box.keys()].filter((a) => !live.has(a));
console.log(`entries=${box.size}  orphaned entries=${orphaned.length}  ->`, orphaned.join("  "));

starting keys: book:v1:7  branch:2:g1:list:1  branch:2:g1:list:2
key looked up for book 7         : book:v2:7 -> in cache: false
key looked up for branch 2 page 1: branch:2:g2:list:1 -> in cache: false
entries=4  orphaned entries=3  -> book:v1:7  branch:2:g1:list:1  branch:2:g1:list:2

The value of a generation counter is this: no matter how many list pages a branch has, incrementing a single number invalidates all of them. The keys never need to be found and deleted one by one — in a shared cache, searching by key pattern is expensive, and often dangerous.

The cost is in the last line. Three of the four entries are now dead entries that no read will ever look up again. These entries take up space and can only be cleared by a lifetime or an eviction policy. Version-based invalidation is therefore always set up together with an upper time bound.

The second condition is that the version counter must be shared. In the example above, the counter lives in process memory; when two application instances run, one raising the version does not get seen by the other, which keeps reading the old key. The counter itself must be kept in a shared store, so every read pays for one extra access.

Where Each Approach Fits

The three approaches do not exclude one another; they are layered on top of each other.

Time-based invalidation is always present, because it is the only guarantee left when the others fail. When an event is lost, or an application instance misses a version increase, the lifetime is the only thing bounding staleness. In client and edge caches, it is the only option: there is no way to reach those copies and delete them.

Event-based invalidation reacts when the data changes and decouples staleness from the lifetime. Its correctness depends on the event actually being delivered. The consumer delay in the measurement was its most optimistic case: the event had been recorded and was only read late. A lost event leaves a stale entry behind forever.

Version-based invalidation moves eviction into the read path: instead of deleting the wrong entry, it looks up the correct entry under a different name. It is the most resistant approach to race conditions, because it does not depend on the ordering of a delete. Its cost is the space that dead entries accumulate.

Summary

• The lifetime is the exchange rate between origin load and accepted staleness: as the lifetime rose from 10 to 200, origin reads fell from 626 to 72, and stale reads rose from 18 to 445.
• Event-based invalidation steps off this curve: with a five-step consumer delay, 155 origin reads and 14 stale reads — a quarter of the origin load for the same level of staleness.
• The staleness window of the event-based approach is the time between an event being produced and being processed; when the delay rose from five to twenty-five, stale reads climbed from 14 to 97.
• Once the version enters the key, stale reads drop to zero and no delete ever happens; with a generation counter, a single increment invalidates an entire namespace.
• The cost of the version-based approach is orphaned entries; it is therefore always set up with an upper time bound, and the counter must be shared.

Next Step

In this lesson, the key changed three times: first book:7, then a form carrying the version, then a list key carrying a branch’s generation counter. Each time, one more piece of information went into the key, and each time, this was done by hand. When a key structure is built by hand, two mistakes become unavoidable: two different queries landing on the same key, and one tenant’s data being served to another tenant. The next lesson treats the key as a design object; it writes a generator built on namespace, tenant separation, and canonical ordering of criteria, and demonstrates both mistakes by running them.