--- title: 'Cache Placement' source: 'https://academia.sh/en/courses/scaling-the-data/cache-placement' course: 'Scaling the Data Layer' language: en updated: '2026-08-23T07:01:32+00:00' license: 'CC BY-SA 4.0' --- # Cache Placement Treating which layer a copy sits in as a design decision: separating the client, edge, web, application, and database layers by scope and capacity, measuring the per-layer hit ratio and miss penalty of a four-layer chain, turning the introductory course's 0.90 cache hit assumption into a result of the design, and showing that a single correctly sized cache delivers the same ratio with fewer touches. 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. ```js // 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 ```js // 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. ```js // 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.