Cache-Aside

The previous lesson measured four layers as a chain, all behaving the same way: check, ask the next one down if missing, put it back on the way up. That behavior is called cache-aside, and a layer’s hit ratio does not depend on capacity alone — a second force, a write, drops entries too. The back-of-the-envelope computation described a system write-heavy where the store sees it: write/read at the store 2.33. This lesson turns the hit ratio from a fixed number into a function of write frequency.

Cache-aside’s mechanics were built and measured in the Caching, Queues and Asynchronous Processing course and are not retold here. The questions here differ: which layer this strategy belongs to, and what it gives at K01’s write rate.

What Application-Controlled Means

Cache-aside’s defining trait is that the cache sits beside the read path: fetching responsibility lies with the application, not the cache. The same read path has two implementations — application code checking by hand, or the read passing through the cache layer — and both go by this name. The difference is not in the mechanics but in where the responsibility sits, which is the only thing the last section measures.

This strategy is the only option everywhere the cache cannot be wired to the write path. In the shipment tracking service, state events come not from the application’s read path but from the carrier, processed through the queue designed in the Application Layer and Service Interaction course and written to the store from there. The read-path cache only learns of the write through an invalidation message — which is why deleting the entry, not updating it, is all it can do. Wiring a write to the cache is the next lesson’s subject.

The layer choice follows from this too. In the previous lesson’s measurement, the application layer’s shared cache stopped only a small share of the hit ratio, but had the highest revocability: a delete message applies there instantly. Cache-aside is therefore placed at the application layer; edge and client layers cannot run the same strategy, since they have no delete, only a lifetime.

The Effect of Writes on the Hit Ratio

The model is in-process and single-layer: since the previous lesson’s measurement showed that a single shared cache with capacity 2000 covers the working set, capacity is removed as a binding constraint here, leaving write ratio as the only variable.

B1 (this lesson’s assumption): state events land on the shipments being queried at that moment. Rationale: a shipment produces events and gets queried for the same reason — it is in transit now. This is the direction where invalidation is strongest; sensitivity: if half the events land on shipments not being queried, the deletion count and its extra reads fall by half. Not added to K01’s table.

// cache/aside.mjs — the in-process model of cache-aside. Cache, store, and event stream are
// each their own module; counters are explicit. Write/read ratio, capacity, and failure share are parameters.
export function openBox(capacity) {
  const m = new Map();
  const o = {
    eviction: 0,
    has: (a) => m.has(a),
    get(a) { const d = m.get(a); if (d !== undefined) { m.delete(a); m.set(a, d); } return d; },
    put(a, d) { m.delete(a); m.set(a, d); if (m.size > capacity) { m.delete(m.keys().next().value); o.eviction += 1; } },
    remove: (a) => m.delete(a),
  };
  return o;
}

// Stream: reads and writes land on the same active shipment set (B1). `ratio` is the write/read ratio.
export function stream({ reads, ratio, workingSet, burst }) {
  let seed = 20260730;
  const rand = () => ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648);
  let next = 1;
  const active = Array.from({ length: workingSet }, () => ({ id: next++, remaining: burst }));
  const output = [];
  let debt = 0;
  for (let i = 0; i < reads; i++) {
    const j = Math.floor(rand() * active.length);
    const item = active[j];
    output.push(["read", `track:${item.id}`]);
    if ((item.remaining -= 1) === 0) active[j] = { id: next++, remaining: burst };
    for (debt += ratio; debt >= 1; debt -= 1)
      output.push(["write", `track:${active[Math.floor(rand() * active.length)].id}`]);
  }
  return output;
}

// Cache-aside: on read, check-fetch-put; on write, write to the store and delete the entry.
// invalidate=false: a write does not delete the entry. failure: the share of cache ops that fail.
// canBypass=false: the read passes through the cache; the application cannot go to the store itself.
export function run(ops, { capacity, invalidate = true, failure = 0, canBypass = true }) {
  const c = openBox(capacity);
  let seed = 991;
  const failed = () => failure > 0 && ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648) < failure;
  const s = { hit: 0, miss: 0, storeRead: 0, storeWrite: 0, deletion: 0, stale: 0, touch: 0, unserved: 0 };
  const truth = new Map();
  let version = 0;
  for (const [type, key] of ops) {
    if (!truth.has(key)) truth.set(key, 0);
    if (type === "read") {
      s.touch += 1;
      if (failed()) {
        if (!canBypass) { s.unserved += 1; continue; }
        s.miss += 1; s.storeRead += 1; s.touch += 1;
        continue;
      }
      if (c.has(key)) {
        s.hit += 1;
        if (c.get(key) !== truth.get(key)) s.stale += 1;
        continue;
      }
      s.miss += 1; s.storeRead += 1; s.touch += 2;
      c.put(key, truth.get(key));
    } else {
      truth.set(key, (version += 1));
      s.storeWrite += 1; s.touch += 1;
      if (!invalidate) continue;
      s.touch += 1;
      if (failed()) continue;                       // the delete is lost: the entry stays stale
      if (c.remove(key)) s.deletion += 1;
    }
  }
  return { ...s, eviction: c.eviction };
}

// M19/K01 back-of-the-envelope inputs (V1-V4, V8).
export const K01 = {
  peakRead: (2_000_000 * 6 / 86_400) * 3,
  peakWrite: (400_000 * 7 / 86_400) * 3,
};

// cache/ratio.mjs — measuring the hit ratio as a function of the write/read ratio
import { stream, run, K01 } from "./aside.mjs";

const READS = 200_000, CAPACITY = 2000, WORKING = 1000, BURST = 10;
const K01_RATIO = K01.peakWrite / K01.peakRead;

console.log(`reads ${READS}, capacity ${CAPACITY}, concurrent shipments ${WORKING}, burst ${BURST}`);
console.log(`K01 write/read ratio = ${K01_RATIO.toFixed(4)} (peak write ${K01.peakWrite.toFixed(2)} / peak read ${K01.peakRead.toFixed(2)})`);
console.log();
console.log(" write/read   write      hit  store read     behind cache/s reaching store/s write/read at store");
console.log("----------- ------- -------- ----------- ------------------ ---------------- -------------------");
for (const ratio of [0, 0.05, 0.1167, K01_RATIO, 0.4667, 1]) {
  const ops = stream({ reads: READS, ratio, workingSet: WORKING, burst: BURST });
  const r = run(ops, { capacity: CAPACITY });
  const h = r.hit / READS;
  const behind = K01.peakRead * (1 - h);
  const label = Math.abs(ratio - K01_RATIO) < 1e-9 ? `${ratio.toFixed(4)}*` : ratio.toFixed(4);
  console.log(`${label.padStart(11)} ${String(r.storeWrite).padStart(7)} ${h.toFixed(4).padStart(8)} ` +
    `${String(r.storeRead).padStart(11)} ${behind.toFixed(2).padStart(18)} ` +
    `${(behind + K01.peakWrite).toFixed(2).padStart(16)} ${(K01.peakWrite / behind).toFixed(2).padStart(19)}`);
}
console.log("* the ratio implied by K01's peak rates");

console.log();
const ops = stream({ reads: READS, ratio: K01_RATIO, workingSet: WORKING, burst: BURST });
const withInv = run(ops, { capacity: CAPACITY });
const without = run(ops, { capacity: CAPACITY, invalidate: false });
console.log(`K01 ratio, with invalidation   : hit ${(withInv.hit / READS).toFixed(4)}  store read ${withInv.storeRead}  deletions ${withInv.deletion}  stale reads ${withInv.stale}`);
console.log(`K01 ratio, without invalidation: hit ${(without.hit / READS).toFixed(4)}  store read ${without.storeRead}  deletions ${without.deletion}  stale reads ${without.stale}`);
console.log(`extra store read per deletion  = ${((withInv.storeRead - without.storeRead) / withInv.deletion).toFixed(2)}`);
console.log(`extra work per write           = ${((withInv.touch - without.touch) / withInv.storeWrite).toFixed(2)} touches + ${((withInv.storeRead - without.storeRead) / withInv.storeWrite).toFixed(2)} store reads`);

reads 200000, capacity 2000, concurrent shipments 1000, burst 10
K01 write/read ratio = 0.2333 (peak write 97.22 / peak read 416.67)

 write/read   write      hit  store read     behind cache/s reaching store/s write/read at store
----------- ------- -------- ----------- ------------------ ---------------- -------------------
     0.0000       0   0.8976       20483              42.67           139.90                2.28
     0.0500   10000   0.8551       28976              60.37           157.59                1.61
     0.1167   23340   0.8039       39212              81.69           178.91                1.19
    0.2333*   46666   0.7287       54257             113.04           210.26                0.86
     0.4667   93340   0.6134       77312             161.07           258.29                0.60
     1.0000  200000   0.4523      109549             228.23           325.45                0.43
* the ratio implied by K01's peak rates

K01 ratio, with invalidation   : hit 0.7287  store read 54257  deletions 33957  stale reads 0
K01 ratio, without invalidation: hit 0.8977  store read 20451  deletions 0  stale reads 105794
extra store read per deletion  = 1.00
extra work per write           = 2.45 touches + 0.72 store reads

All the numbers belong to the computed class; they were counted over a deterministic stream, and no time was measured.

The first row repeats the previous lesson’s result with no writes: hit ratio 0.8976, requests reaching the store/s 139.90 — K01’s assumption holds here, but not at K01’s own write rate. At a write/read ratio of 0.2333, the hit ratio drops to 0.7287, reads behind cache/s climbs from 41.67 to 113.04, and requests reaching the store/s from 138.89 to 210.26. V9 = 0.90 implicitly assumed “nothing ever gets written to the cache”; at its own write rate the system falls nineteen percent short.

The write/read at the store column is even more interesting. K01 computed this ratio at 2.33 and called the read-heavy system write-heavy where the store sees it. At cache-aside’s real hit ratio it falls to 0.86: invalidation inflates the store’s read load enough to turn it read-heavy again. The write count never changed; what changed is the reads each write causes.

The last three rows count that causation. At K01’s ratio, 33,957 entries were deleted and store reads rose from 20,451 to 54,257: 1.00 extra store read per deletion — a deleted entry is almost always read again, since the reason it was deleted is exactly that the shipment is active. A write’s cost to the cache is thus not “one deletion” but “one deletion plus 0.72 store reads.”

Switching invalidation off returns the hit ratio to 0.8977, and the bill shows up in a different column: 105,794 stale reads, more than half of all reads. Cache-aside’s trade-off sits between these two columns, and the middle ground between them — the acceptable staleness window — is the subject of this topic’s last lesson.

Whether the Application Can Go to the Store on Its Own

The difference between the two implementation forms becomes measurable when the cache layer fails. The model makes a share of cache operations fail; the application-controlled form counts this as a miss and goes to the store, while the pass-through form cannot serve the request.

// cache/failure.mjs — how the two forms behave when the cache layer partly fails
import { stream, run, K01 } from "./aside.mjs";

const READS = 200_000, CAPACITY = 2000;
const RATIO = K01.peakWrite / K01.peakRead;
const ops = stream({ reads: READS, ratio: RATIO, workingSet: 1000, burst: 10 });

console.log("failure form                        served     hit  store read reaching store/s stale reads");
console.log("------- ----------------------- ---------- ------- ----------- ---------------- -----------");
for (const failure of [0, 0.1, 0.5, 1]) {
  for (const [label, canBypass] of [["application-controlled", true], ["pass-through", false]]) {
    const r = run(ops, { capacity: CAPACITY, failure, canBypass });
    const served = READS - r.unserved;
    const h = r.hit / READS;
    const storeRate = K01.peakRead * (r.storeRead / READS) + K01.peakWrite;
    console.log(`${failure.toFixed(2).padStart(7)} ${label.padEnd(23)} ${(served / READS).toFixed(4).padStart(10)} ` +
      `${h.toFixed(4).padStart(7)} ${String(r.storeRead).padStart(11)} ${storeRate.toFixed(2).padStart(16)} ${String(r.stale).padStart(11)}`);
  }
}

failure form                        served     hit  store read reaching store/s stale reads
------- ----------------------- ---------- ------- ----------- ---------------- -----------
   0.00 application-controlled      1.0000  0.7287       54257           210.26           0
   0.00 pass-through                1.0000  0.7287       54257           210.26           0
   0.10 application-controlled      1.0000  0.6468       70650           244.41        7473
   0.10 pass-through                0.8974  0.6468       50126           201.65        7473
   0.50 application-controlled      1.0000  0.3209      135818           380.18       18780
   0.50 pass-through                0.4876  0.3209       33334           166.67       18780
   1.00 application-controlled      1.0000  0.0000      200000           513.89           0
   1.00 pass-through                0.0000  0.0000           0            97.22           0

In the healthy state both forms produce the same row; the difference appears only under failure. When the cache fails completely, the application-controlled form keeps serving every request, and requests reaching the store climb to 513.89 req/s — the whole of K01’s peak load at the edge, a design requirement: choosing cache-aside requires the store to carry this load briefly. In the pass-through form, served requests drop to zero, and the service’s availability becomes tied to the cache layer staying up.

The requests-reaching-the-store column misleads here, and is deliberately placed side by side: at a 50 percent failure rate, the pass-through form’s store sees less load than in the healthy state — 166.67 req/s. While the store load looks low, half of all requests go unanswered — one metric improving cannot be read on its own.

The third column carries an unexpected result: at a 10 percent failure rate there are 7473 stale reads, where the healthy run had none. What gets lost is not reads but deletions; a failed delete leaves a stale entry without showing up as an error in any counter, so cache-aside’s correctness depends on the operation that fails in the quietest way.

Summary

• Cache-aside is the read-path cache where fetching responsibility lies with the application, not the cache; it is the only option when a write cannot be wired to the cache, and deleting the entry is all it can do.
• The hit ratio is a function of the write/read ratio: 0.8976 with no writes, 0.7287 at K01’s ratio of 0.2333. The V9 = 0.90 assumption implicitly assumed a system with no writes.
• Back to K01: reads behind cache/s climbs from 41.67 to 113.04, requests reaching the store/s from 138.89 to 210.26; write/read at the store falls from 2.33 to 0.86, meaning the store turns read-heavy again.
• Each deletion causes 1.00 extra store read; a write’s cost to the cache is 2.45 touches and 0.72 store reads. Turning invalidation off returns the hit ratio to 0.8977, but produces 105,794 stale reads.
• When the cache fails completely, the application-controlled form serves every request and the store takes on 513.89 req/s; in the pass-through form, served requests drop to zero. Under partial failure, lost deletions leave 7473 stale reads.

Next Step

This lesson’s entire cost grew from one constraint: the cache was not where the write happened, so it could only delete the old value, never put in the new one, and every deletion caused a store read. That constraint does not always hold. When the path writing shipment state to the store passes through the application’s own code, nothing stops it from also writing the new value to the cache — the write goes to both places, and no deletion happens. The same link can go one step further, sending the write to the cache first and the store later in a batch, this time changing a number not on the read side but in the numerator of write/read at the store. The next lesson measures these two arrangements: how many places the write path stretches to, how much extra work each write costs, and how many events remain in memory when the process stops.