Cache Placement

The previous topic designed where and in what form the data sits: the store type matched the access pattern, the data was replicated, sharded, and the read path shortened with denormalization. The path really did shorten, but one thing did not change: every read still goes to a store. The next question is meeting the read in front of the store — which layer should the copy sit in.

This lesson turns that question into a placement decision. The Caching, Queues and Asynchronous Processing course built and measured cache layers, strategies, and invalidation, none of it retold here — what changes is scale itself. In the Introduction to System Design course’s back-of-the-envelope computation, the cache was not a strategy but a single number: V9, the fraction of tracking queries served from cache, was taken as 0.90 and brought reads behind cache/s down to 41.67 and requests reaching the store/s down to 138.89. That number was an assumption; this lesson’s job is to turn it into a result — which placement produces 0.90, and what producing it costs.

What Defines a Layer

Three things define a cache layer.

Scope is how many requests the same copy can serve: the client cache serves one user, the edge cache every user in a region, the shared web-layer response cache every request, and the in-process application cache only requests landing on its own instance. As scope grows, warming one copy pays off for more requests.

Capacity is how many entries the layer can hold. When capacity falls under the working set, the layer evicts its own entries and leaks the overflow onward.

Revocability is whether a placed copy can be removed, and it runs opposite to scope: an application entry is deleted instantly by code, an edge entry needs a separate operation, and a client copy has no removal path at all — it stays until the lifetime given at placement runs out. This measure does not appear in the numbers here, but it decides the outcome in the last section.

There is a fifth layer, different from the rest: the database cache sits inside the source itself, lowering a query’s cost rather than the number of queries, and no line of the computation depends on it. This was established and measured in the Caching, Queues and Asynchronous Processing course, not repeated here — why the model below has four layers.

The Chain Model

The model is in-process: layers are objects, counters are explicit, and capacity and access pattern are parameters. No real cache product or cloud environment is set up; what is measured is a count, not time, so it does not change from run to run.

The access pattern is the course’s tracking query: a single-key read by tracking number. A shipment’s queries arrive together — the user opens the page, refreshes it, and checks back after a while. This bursting is this lesson’s assumption, not added to K01’s table.

B1 (this lesson’s assumption): a shipment’s queries arrive in bursts of length 10, and 1000 shipments are queried at once. Rationale: the Traffic Layer course’s Content Delivery Networks lesson used the same burst length and measured an edge hit rate of 0.8998; the addition here is a concurrent shipment count that defines a working set and makes capacity meaningful. Sensitivity: at burst 5 the unique key count doubles and every layer’s hit ratio falls; at working set 2000, fixed-capacity layers leak more overflow onward.

// cache/layer.mjs — the in-process model of the layer chain. Layers are objects,
// counters are explicit. Capacity, burst length, and working set are the model's parameters.
export function cache(capacity) {
  const box = new Map();
  const o = {
    eviction: 0,
    get(a) { const d = box.get(a); if (d !== undefined) { box.delete(a); box.set(a, d); } return d; },
    put(a, d) {
      box.delete(a); box.set(a, d);
      if (box.size > capacity) { box.delete(box.keys().next().value); o.eviction += 1; }
    },
  };
  return o;
}

// Access pattern: a single-key read by tracking number. A shipment's queries arrive in
// bursts of length `burst`; `workingSet` shipments are queried at once. An `ownerShare`
// share of the queries come from the user who started the shipment, the rest from another.
export function stream({ requests, workingSet, burst, users, ownerShare = 0.7 }) {
  let seed = 20260730;
  const rand = () => ((seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648);
  const spawn = (id) => ({ id, remaining: burst, owner: Math.floor(rand() * users) + 1 });
  let next = 1;
  const active = Array.from({ length: workingSet }, () => spawn(next++));
  const output = [];
  for (let i = 0; i < requests; i++) {
    const j = Math.floor(rand() * active.length);
    const item = active[j];
    const requester = rand() < ownerShare ? item.owner : Math.floor(rand() * users) + 1;
    output.push([requester, `track:${item.id}`]);
    if ((item.remaining -= 1) === 0) active[j] = spawn(next++);
  }
  return output;
}

// Chain: each request polls the layers in order. A miss counts one poll per layer, one
// access at the store, and one write touch back to each layer on the way back.
export function chain(requests, layers) {
  const boxes = layers.map(() => new Map());
  const counter = layers.map(() => ({ hit: 0, eviction: 0 }));
  const s = { store: 0, touch: 0, miss: 0 };
  const getBox = (i, user, key) => {
    const scope = layers[i].scope;
    const id = scope === "user" ? user
      : scope === "instance" ? (key.length + Number(key.slice(6))) % layers[i].instance : 0;
    let c = boxes[i].get(id);
    if (c === undefined) { c = cache(layers[i].capacity); boxes[i].set(id, c); }
    return c;
  };
  for (const [user, key] of requests) {
    let found = -1;
    for (let i = 0; i < layers.length; i++) {
      s.touch += 1;
      if (getBox(i, user, key).get(key) !== undefined) { found = i; break; }
    }
    if (found === -1) { s.store += 1; s.miss += 1; s.touch += 1; }
    else counter[found].hit += 1;
    const last = found === -1 ? layers.length - 1 : found - 1;
    for (let i = 0; i <= last; i++) { s.touch += 1; getBox(i, user, key).put(key, key); }
  }
  for (let i = 0; i < layers.length; i++)
    for (const c of boxes[i].values()) counter[i].eviction += c.eviction;
  return { counter, ...s };
}

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

The window is 480 seconds; at K01’s peak read rate of 416.67 req/s, that window holds 200,000 tracking queries. A touch is the model’s single unit of cost: one layer poll, one store access, or one write-back. Touches are not weighted — a store access and a memory poll count the same. The placement decision itself assigns the weight; the count only says how much work was done.

Measurement

// cache/placement.mjs — measuring the four-layer chain and returning to the K01 computation
import { stream, chain, K01 } from "./layer.mjs";

const REQUESTS = 200_000, BURST = 10, WORKING = 1000, USERS = 40_000;
const requests = stream({ requests: REQUESTS, workingSet: WORKING, burst: BURST, users: USERS });
const LAYERS = [
  { name: "client", scope: "user", capacity: 4 },
  { name: "edge", scope: "shared", capacity: 250 },
  { name: "web", scope: "shared", capacity: 600 },
  { name: "app", scope: "instance", capacity: 400, instance: 4 },
];

const unique = new Set(requests.map(([, a]) => a)).size;
const r = chain(requests, LAYERS);
console.log(`requests ${REQUESTS} (480 s window), unique tracking numbers ${unique}, burst ${BURST}, concurrent shipments ${WORKING}`);
console.log();
console.log("layer      scope        capacity      hit    hit ratio eviction");
console.log("---------- ----------- --------- -------- ------------ --------");
for (let i = 0; i < LAYERS.length; i++) {
  const k = LAYERS[i], c = r.counter[i];
  const cap = k.scope === "instance" ? `${k.capacity}x${k.instance}` : String(k.capacity);
  console.log(`${k.name.padEnd(10)} ${k.scope.padEnd(11)} ${cap.padStart(9)} ` +
    `${String(c.hit).padStart(8)} ${(c.hit / REQUESTS).toFixed(4).padStart(12)} ${String(c.eviction).padStart(8)}`);
}
console.log(`${"store".padEnd(10)} ${"-".padEnd(11)} ${"-".padStart(9)} ${String(r.store).padStart(8)} ` +
  `${(r.store / REQUESTS).toFixed(4).padStart(12)} ${"-".padStart(8)}`);

const h = 1 - r.store / REQUESTS;
const behind = K01.peakRead * (1 - h);
console.log();
console.log(`combined hit ratio    = ${h.toFixed(4)}  (V9 assumption 0.90)`);
console.log(`touches per miss      = ${2 * LAYERS.length + 1} (${LAYERS.length} polls + 1 store + ${LAYERS.length} write-backs)`);
console.log(`touch / request       = ${(r.touch / REQUESTS).toFixed(3)}`);
console.log();
console.log(`back to K01 (peak read ${K01.peakRead.toFixed(2)}, peak write ${K01.peakWrite.toFixed(2)} req/s)`);
console.log(`reads never leaving the client = ${(K01.peakRead * r.counter[0].hit / REQUESTS).toFixed(2)}`);
console.log(`reads reaching the app         = ${(K01.peakRead * (r.counter[3].hit + r.store) / REQUESTS).toFixed(2)}`);
console.log(`reads behind cache/s           = ${behind.toFixed(2)}  (V9 gives 41.67)`);
console.log(`requests reaching the store/s  = ${(behind + K01.peakWrite).toFixed(2)}  (V9 gives 138.89)`);
console.log(`write/read at the store        = ${(K01.peakWrite / behind).toFixed(2)}  (V9 gives 2.33)`);

requests 200000 (480 s window), unique tracking numbers 20454, burst 10, concurrent shipments 1000

layer      scope        capacity      hit    hit ratio eviction
---------- ----------- --------- -------- ------------ --------
client     user                4   140045       0.7002    34810
edge       shared            250    16520       0.0826    43185
web        shared            600    14390       0.0720    28445
app        instance        400x4     8394       0.0420    19051
store      -                   -    20651       0.1033        -

combined hit ratio    = 0.8967  (V9 assumption 0.90)
touches per miss      = 9 (4 polls + 1 store + 4 write-backs)
touch / request       = 2.531

back to K01 (peak read 416.67, peak write 97.22 req/s)
reads never leaving the client = 291.76
reads reaching the app         = 60.51
reads behind cache/s           = 43.02  (V9 gives 41.67)
requests reaching the store/s  = 140.25  (V9 gives 138.89)
write/read at the store        = 2.26  (V9 gives 2.33)

All these numbers belong to the computed class: counted over a deterministic stream, with no time measured, so they do not change from run to run.

The first result is about V9. The four layers’ combined hit ratio came out to 0.8967, slightly under the assumed 0.90. The difference looks small but shows up in the computation: reads behind cache/s 43.02 instead of 41.67, requests reaching the store/s 140.25 instead of 138.89, write/read at the store 2.26 instead of 2.33. The assumption is now defensible, because the placement producing it has been written down, and these lines get recalculated whenever capacity or the working set changes.

The second result is about the distribution of the hit ratio. 0.7002 of requests stopped at the client layer, in a cache of only four entries, since most queries inside a burst come from the same user — so 291.76 reads per second never reach the network. The remaining three layers stopped 0.1966 combined, and reads reaching the app fell from 416.67 to 60.51 req/s. The Content Delivery Networks lesson in the Traffic Layer course measured the same line at 41.76; its application cache could hold every key in the window, while these layers’ capacity sits under the working set, as the eviction column shows.

The third result is about where the cost sits. A miss makes nine touches — four polls, one store access, four write-backs on the way back — averaging 2.531 touches/request. As the chain lengthens the hit ratio rises, but every miss walks a longer path.

The Limit of Adding a Layer

A layer’s value is the ratio of requests stopped to touches added. The run below builds the chain from scratch to isolate each layer’s own share, and shows what it takes to match the same hit ratio with a single cache.

// cache/layer-count.mjs — what is gained and paid as layers are added to the chain
import { stream, chain, K01 } from "./layer.mjs";

const REQUESTS = 200_000;
const requests = stream({ requests: REQUESTS, workingSet: 1000, burst: 10, users: 40_000 });
const FULL = [
  { name: "client", scope: "user", capacity: 4 },
  { name: "edge", scope: "shared", capacity: 250 },
  { name: "web", scope: "shared", capacity: 600 },
  { name: "app", scope: "instance", capacity: 400, instance: 4 },
];

console.log("chain                        hit ratio store/s  touch/request     stopped    added touches    touches/stopped");
console.log("---------------------------- --------- ------- -------------- ----------- ---------------- ------------------");
let prev = { touch: REQUESTS, store: REQUESTS };   // cacheless: one store access per request
for (let n = 0; n <= FULL.length; n++) {
  const r = n === 0 ? { store: REQUESTS, touch: REQUESTS } : chain(requests, FULL.slice(0, n));
  const h = 1 - r.store / REQUESTS;
  const storeRate = K01.peakRead * (1 - h) + K01.peakWrite;
  const stopped = prev.store - r.store;
  const added = r.touch - prev.touch;
  const label = n === 0 ? "(cacheless)" : "+" + FULL[n - 1].name;
  console.log(`${label.padEnd(28)} ${h.toFixed(4).padStart(9)} ${storeRate.toFixed(2).padStart(7)} ` +
    `${(r.touch / REQUESTS).toFixed(3).padStart(14)} ${(n === 0 ? "-" : String(stopped)).padStart(11)} ` +
    `${(n === 0 ? "-" : String(added)).padStart(16)} ${(n === 0 ? "-" : (added / stopped).toFixed(2)).padStart(18)}`);
  prev = r;
}

const full = chain(requests, FULL);
const h = 1 - full.store / REQUESTS;
console.log();
console.log(`four-layer combined hit ratio = ${h.toFixed(4)}`);
console.log(`capacity needed for the same hit ratio with a single layer:`);
for (const cap of [250, 600, 1000, 1200, 2000]) {
  const t = chain(requests, [{ name: "single", scope: "shared", capacity: cap }]);
  const th = 1 - t.store / REQUESTS;
  console.log(`  capacity ${String(cap).padStart(4)} -> hit ratio ${th.toFixed(4)}  store/s ${(K01.peakRead * (1 - th) + K01.peakWrite).toFixed(2).padStart(6)}  touch/request ${(t.touch / REQUESTS).toFixed(3)}`);
}

chain                        hit ratio store/s  touch/request     stopped    added touches    touches/stopped
---------------------------- --------- ------- -------------- ----------- ---------------- ------------------
(cacheless)                     0.0000  513.89          1.000           -                -                  -
+client                         0.7002  222.13          1.600      140045           119910               0.86
+edge                           0.7828  187.71          2.034       16520            86870               5.26
+web                            0.8548  157.73          2.324       14390            58090               4.04
+app                            0.8967  140.25          2.531        8394            41302               4.92

four-layer combined hit ratio = 0.8967
capacity needed for the same hit ratio with a single layer:
  capacity  250 -> hit ratio 0.2321  store/s 417.20  touch/request 2.536
  capacity  600 -> hit ratio 0.5236  store/s 295.71  touch/request 1.953
  capacity 1000 -> hit ratio 0.7915  store/s 184.11  touch/request 1.417
  capacity 1200 -> hit ratio 0.8646  store/s 153.63  touch/request 1.271
  capacity 2000 -> hit ratio 0.8975  store/s 139.95  touch/request 1.205

The first table gives diminishing returns in numbers. In the cacheless design, requests reaching the store run at 513.89 req/s — the whole of K01’s peak load at the edge. The first layer brings that to 222.13, adding only 0.86 touches per request stopped, since a stopped request already cancels a store access. The next three layers’ ratios are 5.26, 4.04, and 4.92: each charges close to five extra touches per request saved. The fourth layer stops 8394 requests, adds 41,302 touches, and lowers the store load by only 17.49 req/s.

The second table is more uncomfortable. A single shared cache with capacity 2000 gives a 0.8975 hit ratio — above the four-layer chain’s 0.8967 — with 1.205 touches per request instead of 2.531. The chain’s justification is not the combined hit ratio: a single, right-sized layer delivers the same ratio more cheaply.

The chain’s justification is where the hit ratio gets served. In a single shared cache, every hit costs a network round trip and all pass through one component; in the four-layer placement, 291.76 reads per second never reach the network. In exchange, those reads are served at the layer with the lowest revocability: once placed, the client copy cannot be removed. The placement decision sits between these two sentences, and both are consistent with the same hit ratio.

Summary

• Scope, capacity, and revocability define a cache layer; the database cache sits outside this ranking — it lowers a query’s cost, not its count.
• The four-layer chain’s combined hit ratio measured 0.8967, turning K01’s V9 = 0.90 assumption into a design result: reads behind cache/s 43.02 instead of 41.67, requests reaching the store/s 140.25 instead of 138.89, write/read at the store 2.26 instead of 2.33.
• 0.7002 of the hit ratio stopped at the four-entry client cache; 291.76 reads per second never reached the network, and reads reaching the app fell from 416.67 to 60.51 req/s.
• As the chain lengthens, every miss walks a longer path: at four layers a miss makes nine touches, averaging 2.531 touches/request, with each layer’s extra touches per request stopped running 0.86, 5.26, 4.04, and 4.92.
• A single shared cache with capacity 2000 delivers a 0.8975 hit ratio with 1.205 touches; the chain’s justification is not the hit ratio but which layer serves it.

Next Step

In this lesson every layer worked the same way: check, ask the next one down if missing, put it back on the way up — a single loop in the code, and it has a name, and it is not the only option. A layer’s hit ratio depends not only on capacity but on when an entry drops out, and what drops an entry is usually a write. K01’s computation described a system that is write-heavy where the store sees it: a write/read ratio of 2.33. The next lesson names this application-controlled placement and turns the hit ratio from a fixed number into a function of write frequency, one that says where 0.90 holds and where it does not.