--- title: Invalidation source: 'https://academia.sh/en/courses/asynchronous-processing/invalidation' course: 'Caching, Queues and Asynchronous Processing' language: en updated: '2026-08-23T07:00:23+00:00' license: 'CC BY-SA 4.0' --- # Invalidation Measuring time-based, event-based, and version-based invalidation on the same workload: the trade-off a lifetime sets up between origin reads and stale reads, the delay of an event consumer fed by an outbox, and the orphaned-entry cost of putting the version in the key. 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. ```sh # 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. ```js // 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**. ```js // 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.