--- title: 'Case Studies' source: 'https://academia.sh/en/courses/case-studies' language: en updated: '2026-08-23T07:01:23+00:00' license: 'CC BY-SA 4.0' lessons: 14 outcomes: - 'Solves well-known system design problems end to end' - "Writes each case's constraints and trade-offs explicitly" - 'Builds a rationale for the choice by comparing alternative designs' --- # Case Studies Defending, on a single problem, the decisions six courses built separately: turning each case's constraints into numbers, setting up its own assumption table and running a back-of-the-envelope estimate, assembling the design by name from patterns established in earlier courses, eliminating at least one alternative with a number, writing down the rationale for the pattern deliberately left unused, and stating plainly how the design behaves under failure and what it gives up. ## Read-Heavy Systems Four designs where reads outnumber writes by a wide margin: a URL shortening service built on key generation, redirection, and caching; comparing fan-out on write with fan-out on read for the same stream; a search suggestion built on prefix structures and update lag; and a content distribution design that separates static from dynamic content. ### URL Shortening Service Source: https://academia.sh/en/courses/case-studies/link-shortening-service The first read-heavy case: turning the constraints into functional and non-functional requirements as numbers, deriving a back-of-the-envelope estimate from nine assumptions, choosing the short-key length from the occupancy rate, the collision rate, and the guessing cost, eliminating counter-based generation with a measured difference, and writing down the design's behavior under a partition failure and the freshness it gives up. Six courses built a design language piece by piece. This course's job is not to teach new mechanics; it is to use the established patterns **together, on a single problem** and defend each choice with a reason. Every case walks the same six steps: constraints turn into numbers, assumptions collect in their own table, a back-of-the-envelope estimate follows from that table, the design assembles from patterns by name, at least one alternative is eliminated with a number, and the design's behavior under failure and what it gives up are written down. The first case is the **URL shortening service**: given a long link, it generates a short key, and requesting that key redirects to the original target. The design looks at a single decision — **how the short key is generated** — and this lesson measures that decision. #### Constraints **Functional requirements.** F1: a short key is generated and returned for a long link. F2: requesting the short key redirects to the target. F3: a link has an expiration time; an expired link does not redirect. F4: the owner deletes the link. F5: a short key is never assigned to two different targets. **Scope reduction.** Click counting, requests for a custom key, malware scanning of the target link, and account management are outside this design; each brings its own write path and does not move the decisions below. **Non-functional requirements.** The threshold's source is written, not its class; the format follows the Introduction to System Design course's Functional and Non-Functional Requirements lesson. | Code | Threshold | Threshold's source | |---|---|---| | G1 | the median redirect response does not exceed 50 ms | the redirect is an extra round trip inserted between the click and the destination page | | G2 | the shortening call does not exceed 300 ms | the result is awaited on screen | | G3 | the redirect path's service availability is 99.95 percent | the shortened link is embedded in written text and cannot be taken back | | G4 | the hit probability of a random key guess is below 1/1000 | the link is not secret, but it should not be listable either | #### Assumptions This table is this lesson's alone; later cases build their own and do not inherit numbers from it. | Code | Assumption | Value | Rationale | |---|---|---|---| | BK1 | shortenings created per day | 500,000 | shortening depends on a sharing action, it is infrequent | | BK2 | daily redirects per shortening | 100 | a link is opened many times on the day it is shared | | BK3 | peak factor | 3 | the ratio of the peak-hour rate to the daily average | | BK4 | link record | 500 bytes | target link, owner, creation and expiration time | | BK5 | retention period | 1825 days | an unrenewed link drops after five years | | BK6 | the key share receiving 0.80 of requests | 0.01 | access concentrates in a small number of new links | | BK7 | alphabet size | 62 | digits and both letter cases; no separators, can be typed by hand | | BK8 | cache record | 300 bytes | key and target link | | BK9 | redirect response | 300 bytes | bodiless response and its headers | #### Back-of-the-Envelope Estimate ```js // shortening/estimate.mjs — the back-of-the-envelope estimate from BK1-BK9 and the key-length scan const BK = { dailyShortenings: 500_000, // BK1 redirectsPerShortening: 100, // BK2 peakFactor: 3, // BK3 recordBytes: 500, // BK4 retentionDays: 1825, // BK5 hotShare: 0.01, // BK6: the key share receiving 0.80 of requests hotRequestShare: 0.80, // BK6 alphabet: 62, // BK7 cacheRecordBytes: 300, // BK8 responseBytes: 300, // BK9 }; const DAY = 86_400, MONTH_MIN = 43_800, TARGET = 0.9995; // TARGET: G3 threshold, not an assumption function compute(v) { const readPeak = ((v.dailyShortenings * v.redirectsPerShortening) / DAY) * v.peakFactor; const total = v.dailyShortenings * v.retentionDays; return { total, readPeak, writePeak: (v.dailyShortenings / DAY) * v.peakFactor, storeReads: readPeak * (1 - v.hotRequestShare), egressMbit: (readPeak * v.responseBytes * 8) / 1e6, storeGB: (total * v.recordBytes) / 1e9, cacheGB: (total * v.hotShare * v.cacheRecordBytes) / 1e9, }; } const f = (x, n = 2) => x.toFixed(n); const r = compute(BK); console.log(`total links in the retention window = ${r.total.toLocaleString("en-US")}`); console.log(`peak redirects/s = ${f(r.readPeak)} peak shortenings/s = ${f(r.writePeak)} ratio = ${f(r.readPeak / r.writePeak)}`); console.log(`redirects/s behind the cache = ${f(r.storeReads)} egress = ${f(r.egressMbit)} Mbit/s`); console.log(`store = ${f(r.storeGB)} GB cache = ${f(r.cacheGB)} GB G3 downtime budget = ${f((1 - TARGET) * MONTH_MIN, 1)} min/month`); console.log(`\n${"length".padEnd(9)}${"key space".padStart(19)}${"occupancy".padStart(11)}` + `${"extra tries/record".padStart(20)}${"extra hits/s at peak".padStart(24)}${"guesses per hit".padStart(22)}`); const extraTries = {}; for (const L of [5, 6, 7, 8]) { const space = BK.alphabet ** L, d = r.total / space; // Retry expectation: with k keys already assigned, one attempt's miss probability is k/space. let extra = 0; for (let k = 0; k < r.total; k += r.total / 1e5) extra += (1 / (1 - k / space) - 1) / 1e5; extraTries[L] = extra; console.log(`${String(L).padEnd(9)}${space.toLocaleString("en-US").padStart(19)}${f(d, 6).padStart(11)}` + `${f(extra, 6).padStart(20)}${f(extra * r.writePeak, 4).padStart(24)}${f(1 / d, 1).padStart(22)}`); } const SHARD = 8, dropped = r.readPeak / SHARD * (1 - BK.hotRequestShare); console.log(`\nsingle shard failure (${SHARD} shards): dropped redirects ${f(dropped)}/s = ` + `${f(dropped / r.readPeak, 4)} of requests, rejected shortenings ${f(r.writePeak / SHARD)}/s`); console.log(`G3 budget against a single shard failure = ${f((1 - TARGET) * MONTH_MIN / (dropped / r.readPeak), 1)} min/month`); const doubled = compute({ ...BK, dailyShortenings: BK.dailyShortenings * 2 }); console.log(`\nBK1 sensitivity: daily shortenings 500,000 -> 1,000,000 makes store ${f(r.storeGB)} -> ${f(doubled.storeGB)} GB, ` + `occupancy at 7 characters ${f(r.total / BK.alphabet ** 7, 6)} -> ${f(doubled.total / BK.alphabet ** 7, 6)}, ` + `guesses per hit ${f(BK.alphabet ** 7 / r.total, 1)} -> ${f(BK.alphabet ** 7 / doubled.total, 1)}`); ``` ``` total links in the retention window = 912,500,000 peak redirects/s = 1736.11 peak shortenings/s = 17.36 ratio = 100.00 redirects/s behind the cache = 347.22 egress = 4.17 Mbit/s store = 456.25 GB cache = 2.74 GB G3 downtime budget = 21.9 min/month length key space occupancy extra tries/record extra hits/s at peak guesses per hit 5 916,132,832 0.996035 4.550910 79.0089 1.0 6 56,800,235,584 0.016065 0.008120 0.1410 62.2 7 3,521,614,606,208 0.000259 0.000130 0.0022 3859.3 8 218,340,105,584,896 0.000004 0.000002 0.0000 239276.8 single shard failure (8 shards): dropped redirects 43.40/s = 0.0250 of requests, rejected shortenings 2.17/s G3 budget against a single shard failure = 876.0 min/month BK1 sensitivity: daily shortenings 500,000 -> 1,000,000 makes store 456.25 -> 912.50 GB, occupancy at 7 characters 0.000259 -> 0.000518, guesses per hit 3859.3 -> 1929.7 ``` These numbers are in the **estimate** class, and four of them determine the design. The peak ratio is exactly 100: 1736.11 redirects per second against 17.36 shortenings. The retention window holds 912,500,000 links and 456.25 GB — more than a single node can carry. Behind the cache, 347.22 requests/s remain, and the entire hot set is 2.74 GB — it fits in memory. The most decisive is the key-length table: five characters is **full** for this volume (occupancy 0.996035), six characters does not satisfy G4 (62.2 guesses per hit, threshold 1000), seven characters satisfies both (3859.3 guesses, 0.000130 extra tries per record). Even if BK1 doubles, seven characters still leaves 1929.7 guesses per hit, and the threshold holds. #### The Collision Rate of Key Generation The `extra tries/record` column in the table is an expectation. This section measures whether random generation behaves this way, whether the collision rate depends **only on the occupancy rate**, and where the difference from a counter arises. ```js // shortening/key.mjs — collision rate of key generation: how random generation depends on // occupancy, and a comparison with counter-based generation. The key space is modeled as an // array of slots, the generator is hand-written, the seed is fixed; the numbers are not // machine-dependent. IT IS A MODEL. const SEED = 20260730; const generator = (t) => { let s = t % 2147483647; return () => (s = (s * 48271) % 2147483647) / 2147483647; }; function fillRandomly(m, n, rand) { // on a collision, a new key is drawn const full = new Uint8Array(m); let tries = 0; for (let i = 0; i < n; i += 1) { let y; do { y = Math.floor(rand() * m); tries += 1; } while (full[y]); full[y] = 1; } return { full, extra: tries - n }; } function expectedExtra(m, n) { // with k slots full, one attempt's miss probability is k/m let t = 0; for (let k = 0; k < n; k += 1) t += 1 / (1 - k / m) - 1; return t; } const M = 2_000_000, OCCUPANCY = [0.016065, 0.1, 0.5, 0.9, 0.996035]; const f = (x, n = 6) => x.toFixed(n); const c = (x) => x.toLocaleString("en-US"); console.log(`model: a ${c(M)}-slot key space, seed ${SEED}, hand-written generator`); console.log(`\n${"occupancy".padEnd(10)}${"added".padStart(10)}${"extra tries".padStart(14)}` + `${"measured/record".padStart(17)}${"expected/record".padStart(17)}${"measured/expected".padStart(19)}`); for (const d of OCCUPANCY) { const n = Math.round(d * M); const { extra } = fillRandomly(M, n, generator(SEED)); const exp = expectedExtra(M, n); console.log(`${f(d).padEnd(10)}${c(n).padStart(10)}${c(extra).padStart(14)}` + `${f(extra / n).padStart(17)}${f(exp / n).padStart(17)}${f(extra / exp, 4).padStart(19)}`); } // Scale check: the collision rate depends on occupancy, not the size of the space. console.log(""); for (const m of [250_000, 2_000_000, 8_000_000]) { const n = m / 2; const { extra } = fillRandomly(m, n, generator(SEED)); console.log(`scale check: space ${c(m).padStart(9)}, occupancy 0.500000 -> extra tries/record ${f(extra / n)}`); } // Two generation modes at the same occupancy: the counter never collides, but its keys are adjacent. const GUESSES = 20_000, BLOCK = 1000, d6 = 0.016065, n6 = Math.round(d6 * M); const random = fillRandomly(M, n6, generator(SEED)); const counterFull = new Uint8Array(M); for (let i = 0; i < n6; i += 1) counterFull[i] = 1; // the counter distributes upward from 0 const guesser = generator(SEED + 1); let randomHits = 0, counterHits = 0; for (let g = 0; g < GUESSES; g += 1) { if (random.full[Math.floor(guesser() * M)]) randomHits += 1; // a random guess against random keys if (counterFull[g]) counterHits += 1; // a sequential guess against counter keys } const row = (name, extra, coord, hits) => console.log(`${name.padEnd(18)}${c(extra).padStart(14)}` + `${coord.padStart(21)}${c(hits).padStart(12)}${(GUESSES / hits).toFixed(1).padStart(22)}`); console.log(`\noccupancy ${f(d6)}, ${c(n6)} keys assigned, ${c(GUESSES)} guesses`); console.log(`${"generation mode".padEnd(18)}${"extra tries".padStart(14)}${"coordination calls".padStart(21)}` + `${"hits".padStart(12)}${"guesses per hit".padStart(22)}`); row("random", random.extra, "0", randomHits); row(`counter (block ${BLOCK})`, 0, (n6 / BLOCK).toFixed(1), counterHits); ``` ``` model: a 2,000,000-slot key space, seed 20260730, hand-written generator occupancy added extra tries measured/record expected/record measured/expected 0.016065 32,130 256 0.007968 0.008119 0.9813 0.100000 200,000 10,771 0.053855 0.053605 1.0047 0.500000 1,000,000 385,317 0.385317 0.386294 0.9975 0.900000 1,800,000 2,802,181 1.556767 1.558425 0.9989 0.996035 1,992,070 9,053,122 4.544580 4.552201 0.9983 scale check: space 250,000, occupancy 0.500000 -> extra tries/record 0.386128 scale check: space 2,000,000, occupancy 0.500000 -> extra tries/record 0.385317 scale check: space 8,000,000, occupancy 0.500000 -> extra tries/record 0.384476 occupancy 0.016065, 32,130 keys assigned, 20,000 guesses generation mode extra tries coordination calls hits guesses per hit random 256 0 344 58.1 counter (block 1000) 0 32.1 20,000 1.0 ``` The measurement gives three things. The ratio of measured to expected sits between 0.98 and 1.01 at every occupancy; the closed form represents random generation faithfully, and the 0.000130 in the table is reliable. The scale check shows the collision rate depends on occupancy, not on the size of the space: when the space grows thirty-two-fold, the ratio moves from 0.386128 to 0.384476, landing on the same third digit — which is why a two-million-slot model can speak for a 3.5-trillion space. Third, the ratio is not linear in occupancy: at 0.10 there are 0.05 extra tries per record, while at 0.996035 there are 4.54. The last table places the two generation modes side by side. The counter never collides; its cost has two line items. The first is coordination: the counter is handed out from one place, and in blocks of a thousand keys it makes 32.1 calls for 32,130 keys — 0.017 calls per second at peak, negligible. The second is predictability, and it is not negligible: a client guessing sequentially hits on 20,000 of 20,000 tries, against 344 of 20,000 for random. #### Design No component is re-explained; each one is tied back to the lesson that established it, and this case's **parameter** for it is written down. - **Edge caching** (Traffic Layer, Content Delivery Networks). The parameter is the redirect response's lifetime at the edge: **300 seconds**. This is the **staleness window** from the Scaling the Data Layer course's Consistency and Stale Data lesson, meaning F3 and F4 take effect at the edge with a delay. - **The redirect service is stateless** (Application Layer, Stateless Services); since the state carried per request is zero, **session stickiness** (Traffic Layer, Session Stickiness) is off. - **Key–value store** (Scaling the Data Layer, Store Types), **sharded** (Data Distribution, Sharding) into eight shards. The shard key is **the short key itself**: both redirect and delete already know it, both access patterns touch a single node, and no scatter–gather occurs. - **Cache-aside** (Scaling the Data Layer, Cache-Aside). The parameter comes from BK6: the 2.74 GB hot set serves 0.80 of requests, leaving 347.22 requests/s behind it. - **API gateway and rate limiting** (Traffic Layer, API Gateway), on the shortening path only. The parameter is **20 shortenings per minute per account**: peak writes run at 17.36/s, and no single client should be able to fill it. - **Eventual consistency** (Introduction to System Design, Consistency Models). Propagating a new key to the replicas takes time; the parameter is that the first redirect immediately after shortening goes to the primary replica, so the creator can open their own link. **Two deliberately unused patterns.** Command and query responsibility separation (Scaling the Data Layer, Command and Query Separation) is not used: the read model is the same as the write model, there is no projection to derive. A **message queue** (Application Layer, Message Queues) is not used on the shortening path: the caller waits for the key inside the response. #### Eliminated Alternative: Counter-Based Generation The alternative design does not draw the key at random; it generates it by converting an incrementing counter to base 62. Collision is zero by definition, F5 is guaranteed arithmetically, and the store's existence check never runs. The number that eliminates it is in G4. Because counter keys are contiguous, a client guessing sequentially hits on every try (20,000/20,000 in the measurement, 1.0 guesses per hit); random generation at seven characters needs 3859.3 guesses per hit. The difference is **3859-fold**, and the threshold is 1000; the counter cannot satisfy this at any key length, because the problem is not the size of the space but contiguity. What it wins was measured, and small — at seven characters, the extra store touches random generation adds at peak is 0.0022/s, less than one ten-thousandth of the 17.36 writes. The alternative wins if a different constraint changes: had the key length been fixed at five characters, occupancy would be 0.996035, and random generation would produce 4.55 extra tries per record and 79.01 extra store touches per second at peak — four and a half times the write load. In that case the counter would be the only working mode, and G4 could not be satisfied by any mode at all. #### Failure Behavior and What Is Given Up **If a store shard drops** (Resilience and Reliability, Failure Modes), that shard's keys are served only from the cache: 0.0250 of redirects, 43.40 requests/s, are dropped, and 2.17 shortenings/s are rejected. G3's monthly 21.9-minute downtime budget, measured against this partial failure, corresponds to **876.0 minutes** of a single-shard outage. **If the store drops entirely**, redirects continue from the cache through **graceful degradation** (Resilience and Reliability, Graceful Degradation), and 0.80 of requests are answered; the shortening path is closed, because returning an unwritten key would break F5. **What is given up is freshness.** A deleted or expired link keeps working for the 300-second window at the edge. The design bought this window deliberately: in exchange, most redirects never reach the origin at all. #### Summary - The constraints reduced to five functional requirements and four thresholds; four out-of-scope items were written down, and each threshold carries a source, not a class. - The estimate from nine assumptions gave a peak ratio of 100 (1736.11 redirects/s, 17.36 shortenings/s), and set the retention window at 456.25 GB and the hot set at 2.74 GB. - Key length was set by two thresholds at once: five characters is full (0.996035), six characters does not satisfy G4 (62.2 guesses), seven characters satisfies both (0.000130 extra tries, 3859.3 guesses). - The collision rate depends on occupancy, not the size of the space: at 0.50 occupancy, three different spaces gave 0.386128 / 0.385317 / 0.384476, and measured/expected fell between 0.98 and 1.01 on every row. - Counter-based generation zeroes out collisions but leaves 1.0 guesses per hit under sequential guessing; what it wins is 0.0022 store touches per second at peak, so it was eliminated. - A single-shard failure drops 0.0250 of requests; G3's 21.9-minute budget corresponds to 876.0 minutes of a shard outage; what is given up is the edge's 300-second staleness window. #### Next Step In this case, reads outnumbered writes a hundred to one, and the read's response was **a single record**: give the key, get back the target. The caching decision therefore stayed simple, and no merging happened on the redirect path. In the next case, the read ratio stays similar but the response changes: instead of a single record, an ordered list compiled from many sources is requested. The question then stops being "where do I cache the record" and becomes: **when** is the list compiled — fanned out to everyone's box the moment it is written, or gathered at read time? The two options' work volume differs sharply for the same stream, and the difference is set not per user but by the tail of the follower distribution. ### News Feed Source: https://academia.sh/en/courses/case-studies/news-feed Building the same stream with two distribution models: measuring the work volume of fan-out on write against fan-out on read, the tail of the follower distribution misleading an estimate done with the average, deriving the hybrid model's threshold as a number from the distribution capacity and the visibility window, and computing the moment the window is exceeded when the distribution consumer slows down. In the previous case, the read's response was a single record: give the key, get back the target. In this case the read ratio stays similar but the response changes — the **news feed** is an ordered list compiled from many sources. The question therefore stops being "where do I cache the record" and becomes: **when** is the list compiled? There are two options — **fan-out on write**, which writes the post into every follower's box the moment it is published; **fan-out on read**, which merges the followed accounts' posts the moment the feed is requested. This lesson measures both options' work volume and gives the hybrid model's threshold as a number. #### Constraints **Functional requirements.** F1: a user publishes a post. F2: a user requests the posts of the accounts they follow, ordered by time. F3: a user follows and unfollows. F4: a deleted post does not appear in the feed. **Scope reduction.** Ranking by relevance score, media files, notifications, and search are outside this design; a ranking model changes the feed's **content**, not the distribution decision. | Code | Threshold | Threshold's source | |---|---|---| | G1 | the feed's first page (20 posts) returns in 200 ms | the first view expected when the feed opens | | G2 | a published post appears in a follower's feed within 60 seconds | for the feed to count as live | | G3 | the feed box store does not exceed 20 GB | for the box to stay in memory | #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | VH1 | daily active users | 1,000,000 | users who open the feed at least once a day | | VH2 | daily posts per user | 0.2 | most users read, few write | | VH3 | daily feed requests per user | 8 | the feed is refreshed several times a day | | VH4 | peak factor | 3 | the ratio of the peak-hour rate to the daily average | | VH5 | follower distribution | base 33, exponent 1.16 | followers concentrate in a small number of accounts; the exponent is the tail's thickness | | VH6 | entries kept in the box | 400 | twenty pages of history are enough, the rest comes from the post store | | VH7 | box entry | 32 bytes | post ID and timestamp | VH5 is not a number but a **distribution**; its average follows from the model and was not chosen as an assumption. An account's follower count cannot exceed the user count, and the model applies this cap. #### Back-of-the-Envelope Estimate and the Two Models' Work Volume ```js // feed/estimate.mjs — the estimate from VH1-VH7 and the work volume of the two distribution // models. The follower distribution is generated with a hand-written generator (fixed seed), // the cap is the user count. IT IS A MODEL. const VH = { users: 1_000_000, postsPerUser: 0.2, feedRequests: 8, peakFactor: 3, base: 33, exponent: 1.16, boxEntries: 400, entryBytes: 32 }; const DAY = 86_400; const postPeak = (VH.users * VH.postsPerUser / DAY) * VH.peakFactor; const feedPeak = (VH.users * VH.feedRequests / DAY) * VH.peakFactor; let s = 20260730 % 2147483647; const rand = () => (s = (s * 48271) % 2147483647) / 2147483647; const followers = new Float64Array(VH.users); let atCap = 0; for (let i = 0; i < VH.users; i += 1) { const v = Math.round(VH.base * Math.pow(rand(), -1 / VH.exponent)); if (v > VH.users - 1) atCap += 1; followers[i] = Math.min(VH.users - 1, v); } const totalFollows = followers.reduce((a, b) => a + b, 0), average = totalFollows / VH.users; const sorted = Float64Array.from(followers).sort(); const pct = (p) => sorted[Math.floor(p * VH.users)]; const topShare = sorted.slice(VH.users - VH.users / 1000).reduce((a, b) => a + b, 0) / totalFollows; const b = (x, n = 2) => x.toFixed(n); console.log(`peak posts/s = ${b(postPeak)} peak feed requests/s = ${b(feedPeak)} read/write ratio = ${b(feedPeak / postPeak)}`); console.log(`box store = ${b(VH.users * VH.boxEntries * VH.entryBytes / 1e9)} GB (${VH.boxEntries} entries per user)`); console.log(`\nfollower distribution: average ${b(average)} p50 ${pct(0.5)} p90 ${pct(0.9)} p99 ${pct(0.99)} ` + `p99.9 ${pct(0.999)} largest ${sorted[VH.users - 1]} accounts at cap ${atCap}`); console.log(`the top one-thousandth slice holds ${b(topShare, 4)} of follows`); const writeWork = postPeak * average, readWork = feedPeak * average; console.log(`\n${"model".padEnd(20)}${"work per write".padStart(16)}${"work per read".padStart(16)}${"work/s at peak".padStart(15)}`); console.log(`${"fan-out on write".padEnd(20)}${b(average).padStart(16)}${"1.00".padStart(16)}${b(writeWork + feedPeak).padStart(15)}`); console.log(`${"fan-out on read".padEnd(20)}${"1.00".padStart(16)}${b(average).padStart(16)}${b(readWork + postPeak).padStart(15)}`); console.log(`ratio = ${b((readWork + postPeak) / (writeWork + feedPeak))}`); const doubled = ((VH.users * VH.feedRequests * 2 / DAY) * VH.peakFactor) * average; console.log(`\nVH3 sensitivity: daily feed requests 8 -> 16 makes fan-out on read ${b(readWork)} -> ${b(doubled)} work/s, ` + `fan-out on write stays at ${b(writeWork)} work/s`); ``` ``` peak posts/s = 6.94 peak feed requests/s = 277.78 read/write ratio = 40.00 box store = 12.80 GB (400 entries per user) follower distribution: average 203.63 p50 60 p90 241 p99 1763 p99.9 12474 largest 999999 accounts at cap 7 the top one-thousandth slice holds 0.2753 of follows model work per write work per read work/s at peak fan-out on write 203.63 1.00 1691.87 fan-out on read 1.00 203.63 56570.71 ratio = 33.44 VH3 sensitivity: daily feed requests 8 -> 16 makes fan-out on read 56563.76 -> 113127.53 work/s, fan-out on write stays at 1414.09 work/s ``` Three numbers carry the decision. The first is the ratio: the same stream wants 1691.87 work/s at peak with fan-out on write, and 56,570.71 work/s with fan-out on read — **33.44-fold**. The difference is the read/write ratio itself; work gets multiplied by whichever side's rate it is replicated on, and the read side runs forty times as often. The second is the box store: 12.80 GB, below G3's 20 GB threshold. The third is sensitivity: when feed requests double, fan-out on read climbs to 113,127.53 while fan-out on write stays at 1414.09. Fan-out on write is **independent of read volume**; this is its defining property. The distribution row carries a warning. The average is 203.63, but the median is 60, the 99.9th percentile is 12,474, and the largest account is at the cap. The top one-thousandth slice holds 0.2753 of follows. The estimate done with the average gives the steady rate correctly, but it says nothing about what a single post demands. #### The Hybrid Model's Threshold ```js // feed/hybrid.mjs — the hybrid model's threshold: accounts above the threshold are gathered // at read time. Same distribution generator and same seed; follow probability is assumed // proportional to popularity. IT IS A MODEL. const VH = { users: 1_000_000, postsPerUser: 0.2, feedRequests: 8, peakFactor: 3, base: 33, exponent: 1.16 }; const DAY = 86_400, WINDOW = 60; // WINDOW: G2 threshold const postPeak = (VH.users * VH.postsPerUser / DAY) * VH.peakFactor; const feedPeak = (VH.users * VH.feedRequests / DAY) * VH.peakFactor; let s = 20260730 % 2147483647; const rand = () => (s = (s * 48271) % 2147483647) / 2147483647; const followers = new Float64Array(VH.users); for (let i = 0; i < VH.users; i += 1) followers[i] = Math.min(VH.users - 1, Math.round(VH.base * Math.pow(rand(), -1 / VH.exponent))); const sorted = Float64Array.from(followers).sort(); const average = sorted.reduce((a, b) => a + b, 0) / VH.users; // Connections below the threshold are fanned out on write, those above are gathered on read. function work(threshold) { let below = 0, above = 0, largestBelow = 0, aboveAccounts = 0; for (const f of sorted) { if (f <= threshold) { below += f; largestBelow = f; } else { above += f; aboveAccounts += 1; } } return { write: postPeak * (below / VH.users), read: feedPeak * (above / VH.users), largestBelow, aboveAccounts }; } const b = (x, n = 2) => x.toFixed(n); const fullWrite = work(VH.users), CAPACITY = 3 * fullWrite.write; // capacity is set to three times the steady rate const THRESHOLD = Math.round(WINDOW * (CAPACITY - fullWrite.write)); // the share left for one post is the window's share console.log(`steady write rate = ${b(fullWrite.write)} box writes/s, capacity ${b(CAPACITY)}/s, ` + `left for a single post ${b(CAPACITY - fullWrite.write)}/s -> threshold in a ${WINDOW} s window = ${THRESHOLD.toLocaleString("en-US")} followers`); console.log(`\n${"threshold".padStart(11)}${"accounts above".padStart(16)}${"write work/s".padStart(15)}${"read work/s".padStart(14)}` + `${"total work/s".padStart(14)}${"largest burst/s".padStart(18)}`); for (const e of [1000, 10_000, 84_846, THRESHOLD, VH.users]) { const r = work(e); console.log(`${e.toLocaleString("en-US").padStart(11)}${String(r.aboveAccounts).padStart(16)}${b(r.write).padStart(15)}` + `${b(r.read).padStart(14)}${b(r.write + r.read).padStart(14)}${b(r.largestBelow / WINDOW).padStart(18)}`); } const chosen = work(THRESHOLD); console.log(`\nat the chosen threshold: ${chosen.aboveAccounts} accounts above are gathered at read time, ` + `${b(chosen.read / feedPeak, 3)} extra resources per feed request, total work ${b(chosen.write + chosen.read)}/s`); console.log(`in the thresholdless design the largest single post wants ${b(sorted[VH.users - 1] / WINDOW)} box writes/s = ` + `${b(sorted[VH.users - 1] / WINDOW / fullWrite.write)} times the steady rate`); // If the distribution consumer slows down: backlog / capacity, the moment it exceeds the G2 window. console.log(`\n${"consumer capacity".padEnd(21)}${"backlog/s".padStart(11)}${"G2 exceeded at".padStart(16)}`); for (const k of [1200, 1000, 700]) { const backlog = chosen.write - k; console.log(`${`${k} box writes/s`.padEnd(21)}${b(backlog).padStart(11)}${`${b(WINDOW * k / backlog)} s`.padStart(16)}`); } console.log(`average followers ${b(average)}; the connection share above the threshold ${b(chosen.read / feedPeak / average, 4)}`); ``` ``` steady write rate = 1414.09 box writes/s, capacity 4242.28/s, left for a single post 2828.19/s -> threshold in a 60 s window = 169,691 followers threshold accounts above write work/s read work/s total work/s largest burst/s 1,000 19203 700.05 28561.87 29261.92 16.67 10,000 1308 1000.84 16530.11 17530.95 166.52 84,846 115 1193.70 8815.60 10009.30 1393.05 169,691 52 1247.71 6655.38 7903.09 2820.88 1,000,000 0 1414.09 0.00 1414.09 16666.65 at the chosen threshold: 52 accounts above are gathered at read time, 23.959 extra resources per feed request, total work 7903.09/s in the thresholdless design the largest single post wants 16666.65 box writes/s = 11.79 times the steady rate consumer capacity backlog/s G2 exceeded at 1200 box writes/s 47.71 1509.13 s 1000 box writes/s 247.71 242.22 s 700 box writes/s 547.71 76.68 s average followers 203.63; the connection share above the threshold 0.1177 ``` The table's last row seems to settle the argument at first glance: unthresholded fan-out on write minimizes total work at 1414.09/s, and every threshold makes this number grow. Pulling the threshold down to 1000 raises total work to 29,261.92, close to twenty times as much. The reason does not change — every connection moved above the threshold gets recounted on the side that runs forty times as often. What sets the threshold is not total work but the **last column**. In the thresholdless design, the largest account's single post wants 16,666.65 box writes per second within the 60-second G2 window: **11.79 times** the steady rate. This demand is invisible to an estimate done with the average, because the average is 203.63 and says nothing about the size of a single record. The threshold is **computed** from here. If the distribution capacity is set to three times the steady rate (4242.28/s), 2828.19 writes/s are left for a single post; over a 60-second window this comes to **169,691 followers**. That is the threshold, and it has two inputs: the window and the capacity. At the chosen threshold, 52 accounts move to the read side, 23.959 extra resources are read per feed request, and total work becomes 7903.09/s — 5.59 times the thresholdless design. This is the price paid to keep a single post from consuming the entire distribution capacity. The 52 accounts above the threshold hold only 0.1177 of connections. This is why the hybrid model works: the fifty-two accounts at the tail of the queue carry only this share of connections, yet produce the entire burst. #### Design - **Materialized view** (Scaling the Data Layer, Materialized Views). The feed box is a projection; the parameter is **400 entries** per box and **32 bytes** per entry, 12.80 GB in total. - **Command and query responsibility separation** (Scaling the Data Layer, Command and Query Separation). The write path looks at the post store, the read path at the box; the parameter is that the box holds the post's ID, not its text. - **Message queue and competing consumers** (Application Layer, Message Queues; Competing Consumers). Distribution jobs land on a queue; the parameter is capacity: three times the steady 1414.09/s, 4242.28 box writes/s. - **Sharding** (Data Distribution, Sharding). The box store is sharded by user ID; the parameter is that a feed request touches **a single node** — scatter–gather occurs only for the 52 accounts above the threshold. - **Backpressure** (Resilience and Reliability, Backpressure). When the queue backs up, a signal goes to the publish path; the parameter is G2's 60-second window. **Two deliberately unused patterns.** Edge caching (Traffic Layer, Content Delivery Networks) is not used: the feed is personal, no two users get the same response, and a shared cache produces no hits. Sequential convoy (Application Layer, Sequential Convoy) is not used: the order of distribution jobs does not matter, because the feed is sorted by timestamp inside the box. #### Eliminated Alternative: Pure Fan-Out on Read The alternative design never builds a box; the latest posts of followed accounts are merged the moment the feed is requested. Two things it wins were measured: the box store drops from 12.80 GB to zero, and the G2 window disappears — a post is visible the moment it is published, because visibility does not require moving it. Unfollowing also takes effect instantly. The number that eliminates it is in the work volume: 56,570.71 work/s at peak, 33.44 times fan-out on write. What is more, this number depends on read volume; when VH3 doubles it climbs to 113,127.53 while fan-out on write stays at 1414.09. The alternative wins if a different constraint changes: if the read/write ratio moved from 40 toward 1, the two models' work would equalize and there would be no reason left to keep a box. This means the decision is set not by followers per post, but by **the ratio of feed requests to posts**. #### Failure Behavior and What Is Given Up **If the distribution consumer slows down** (Resilience and Reliability, Failure Modes), the queue backs up and visibility latency grows. The table gives the moment it is exceeded: if capacity drops to 1200 box writes/s, the backlog is 47.71/s and G2's 60-second window is exceeded in **1509.13 seconds**; at 1000 it is 242.22 seconds, at 700 it is 76.68 seconds. A partial slowdown does not stop the feed, it **delays** it; the symptom of this failure is therefore not an error but a shift in freshness. **If a shard of the box store drops**, the feed for users in that shard returns empty. Graceful degradation (Resilience and Reliability, Graceful Degradation) here means switching to fan-out on read: the path already built for the 52 accounts above the threshold opens temporarily, for the users in the dropped shard, to everyone they follow — expensive, but better than an empty feed. **What is given up is write amplification.** Each post is written to an average of 203.63 boxes, and this work happens even if no read ever arrives. The design multiplied writes by close to two hundred to cheapen reads; the entire decision rests on the read/write ratio being 40. #### Summary - The same stream wants 1691.87 work/s at peak with fan-out on write and 56,570.71 work/s with fan-out on read: 33.44-fold. The difference is the read/write ratio itself. - Fan-out on write is independent of read volume: when feed requests double, fan-out on read climbs to 113,127.53 while fan-out on write stays at 1414.09. - The follower distribution's average is 203.63, but its median is 60 and its p99.9 is 12,474; the top one-thousandth slice holds 0.2753 of follows. - Total work does not set the threshold — the thresholdless design is cheapest at 1414.09/s. What sets the threshold is the 16,666.65 writes/s the largest account's single post wants within the 60-second window, 11.79 times the steady rate. - The threshold is computed from the window and the capacity: at three times the steady rate, the threshold is 169,691 followers, 52 accounts move to the read side, and total work becomes 7903.09/s. - When consumer capacity drops to 1200/1000/700, the G2 window is exceeded in 1509.13 / 242.22 / 76.68 seconds; what is given up is 203.63 box writes per post. #### Next Step In this case, the cost of reading was compiling, and compiling was cheapened by shifting it to write time. One property made the shift possible: **for whom** the response would be prepared was known at write time, because the follower list is known the moment it is written. In the next case this property disappears. A user starts typing text and requests a suggestion list on every keystroke; what the query will be is not known in advance, and the number of possible queries is not finite the way a list of users is. If the response cannot be prepared at write time, it has to be prepared at read time — and this time the read threshold is not 200 milliseconds, but small enough to fit between keystrokes. The question turns to which data structure can hold that threshold, and how much freshness must be given up. ### Search Suggestion Source: https://academia.sh/en/courses/case-studies/search-suggestion A read case where the response cannot be prepared at write time: comparing the prefix tree's memory and search cost against a flat list, choosing the tree's depth as a number from the memory budget, measuring the change update lag produces in the first ten suggestions, and a frozen structure degrading through staleness. In the previous case, the response could be prepared at write time, because **for whom** it would be prepared was known the moment it was written. Here that property is gone: a user requests a **search suggestion** on every keystroke, and what they will type is not known in advance. If the response cannot be prepared at write time, it has to be prepared at read time, and this time the read threshold is small enough to fit between keystrokes. This lesson measures which structure can hold that threshold, and what update lag does to the results. #### Constraints **Functional requirements.** F1: at most 10 suggestions are returned for a given prefix. F2: suggestions are ordered by query frequency. F3: new queries enter the suggestion pool. F4: a blocked query is never suggested. **Scope reduction.** Spelling correction, personalization, semantic matching, and multilingual support are outside this design. A suggestion is given only for a prefix up to **10 characters** long; beyond that, the client filters the list it already has. This reduction pays off in the design's most expensive line item. | Code | Threshold | Threshold's source | |---|---|---| | G1 | the median suggestion response does not exceed 20 ms | the gap between two keystrokes | | G2 | the suggestion structure does not exceed 8 GB | for the structure to stay in a single node's memory without splitting | | G3 | a new query's lag before entering the suggestion list does not exceed 600 seconds | for a rising query to be caught the same day | #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | VA1 | daily searches | 20,000,000 | number of completed searches | | VA2 | suggestion requests per search | 12 | every typed character produces one request | | VA3 | peak factor | 3 | the ratio of the peak-hour rate to the daily average | | VA4 | distinct query count | 30,000,000 | long tail, most queries are asked only a few times | | VA5 | new queries added per day | 300,000 | one percent of the pool renews every day | | VA6 | query frequency distribution | Zipf, exponent 1 | rank-r query's frequency is proportional to 1/r | | VA7 | suggestion list length | 10 | F1's list | #### Back-of-the-Envelope Estimate ```js // suggestion/estimate.mjs — the back-of-the-envelope estimate from VA1-VA7 and turning the // thresholds into numbers const VA = { dailySearches: 20e6, suggestionsPerSearch: 12, peakFactor: 3, distinctQueries: 30e6, dailyNewQueries: 300_000, listLength: 10 }; const DAY = 86_400, MEMORY = 8e9, WINDOW = 600; // MEMORY: G2 threshold, WINDOW: G3 threshold const b = (x, n = 2) => x.toFixed(n); const suggestionPeak = (VA.dailySearches * VA.suggestionsPerSearch / DAY) * VA.peakFactor; const searchPeak = (VA.dailySearches / DAY) * VA.peakFactor; console.log(`peak suggestion requests/s = ${b(suggestionPeak)} peak searches/s = ${b(searchPeak)} ratio = ${b(suggestionPeak / searchPeak)}`); console.log(`G2's byte budget per query = ${b(MEMORY / VA.distinctQueries)} bytes (${MEMORY / 1e9} GB / ${(VA.distinctQueries / 1e6)} million queries)`); console.log(`new queries accumulated in the G3 window = ${b(VA.dailyNewQueries / DAY * WINDOW)} (${VA.dailyNewQueries.toLocaleString("en-US")} per day)`); console.log(`the rebuild job runs ${b(DAY / WINDOW)} times a day; each run scans ${(VA.distinctQueries / 1e6)} million queries`); const doubled = (VA.dailySearches * VA.suggestionsPerSearch * 2 / DAY) * VA.peakFactor; console.log(`VA2 sensitivity: suggestion requests per search 12 -> 24 makes peak ${b(doubled)} requests/s; the memory budget does not change, because the structure does not depend on request count`); ``` ``` peak suggestion requests/s = 8333.33 peak searches/s = 694.44 ratio = 12.00 G2's byte budget per query = 266.67 bytes (8 GB / 30 million queries) new queries accumulated in the G3 window = 2083.33 (300,000 per day) the rebuild job runs 144.00 times a day; each run scans 30 million queries VA2 sensitivity: suggestion requests per search 12 -> 24 makes peak 16666.67 requests/s; the memory budget does not change, because the structure does not depend on request count ``` Three numbers determine the design. Peak suggestion requests run at 8333.33 per second — twelve times search, because every character produces a request. G2's 8 GB threshold turns into a budget of **266.67 bytes** per query, and this turns the data structure choice into a budget question. G3's window ties the rebuild job to 144 runs a day, with 2083.33 new queries accumulating on each run. #### Measuring the Structures The **prefix tree** (trie) is the structure established in the Data Structures course's Tries lesson. Its mechanics are not re-explained here; what this case measures are its two parameters — **depth** and **the ready list kept per node**. ```js // suggestion/structures.mjs — the memory and search cost of a prefix tree versus a flat list, // and update lag's effect on the freshness of results. The query set is generated with a // hand-written generator. IT IS A MODEL. const SEED = 20260730, QUERIES = 50_000, WORDS = 4000, SAMPLE = 2000, K = 10, VA4 = 30e6; const NODE_BYTES = 48, RECORD_OVERHEAD = 8; // accounting: node 48 bytes, 8 bytes overhead per record let s = SEED % 2147483647; const rand = () => (s = (s * 48271) % 2147483647) / 2147483647; const pick = (a) => a[Math.floor(rand() * a.length)]; const SYLLABLES = ["ka", "le", "mi", "tu", "ro", "sa", "ne", "bi", "dol", "gar", "ver", "tan", "yi", "us", "ce"]; const vocabulary = []; for (let i = 0; i < WORDS; i += 1) { let k = ""; for (let h = 0, n = 2 + Math.floor(rand() * 2); h < n; h += 1) k += pick(SYLLABLES); vocabulary.push(k); } const queries = [], seen = new Set(); while (queries.length < QUERIES) { const n = 1 + Math.floor(rand() * 3); let q = pick(vocabulary); for (let i = 1; i < n; i += 1) q += " " + pick(vocabulary); if (seen.has(q) === false) { seen.add(q); queries.push(q); } } const frequency = new Float64Array(QUERIES); // Zipf: rank r -> 1e6/r for (let i = 0; i < QUERIES; i += 1) frequency[i] = 1e6 / (i + 1); const root = new Map(), atDepth = new Int32Array(64); for (const q of queries) { // prefix tree: each node is a Map let d = root, k = 0; for (const c of q) { k += 1; let child = d.get(c); if (child === undefined) { child = new Map(); d.set(c, child); atDepth[Math.min(k, 63)] += 1; } d = child; } } const b = (x, n = 2) => x.toFixed(n); const characters = queries.reduce((a, q) => a + q.length, 0); console.log(`model: ${QUERIES.toLocaleString("en-US")} distinct queries, average length ${b(characters / QUERIES)} characters`); console.log(`\n${"structure".padEnd(30)}${"nodes".padStart(11)}${"bytes per query".padStart(19)}${"GB at VA4 queries".padStart(20)}`); console.log(`${"flat list".padEnd(30)}${"-".padStart(11)}${b((characters + QUERIES * RECORD_OVERHEAD) / QUERIES).padStart(19)}` + `${b((characters + QUERIES * RECORD_OVERHEAD) / QUERIES * VA4 / 1e9).padStart(20)}`); let accumulated = 1; for (let d = 1; d <= 63; d += 1) { accumulated += atDepth[d]; if ([6, 8, 10].includes(d) === false && d !== 63) continue; const bytes = accumulated * (NODE_BYTES + K * 4); // node + the node's ready list console.log(`${`prefix tree, depth ${d === 63 ? "full" : d}`.padEnd(30)}${accumulated.toLocaleString("en-US").padStart(11)}` + `${b(bytes / QUERIES).padStart(19)}${b(bytes / QUERIES * VA4 / 1e9).padStart(20)}`); } // Request frequency is Zipf-weighted: since frequency is 1/r, rank is drawn from a QUERIES^u distribution. const weightedPick = () => Math.min(QUERIES - 1, Math.floor(Math.pow(QUERIES, rand())) - 1); const sorted = queries.map((q, i) => [q, i]).sort((a, c) => (a[0] < c[0] ? -1 : a[0] > c[0] ? 1 : 0)); const binaryLog = Math.ceil(Math.log2(QUERIES)); const treeUnits = [], listUnits = [], range = []; for (let i = 0; i < SAMPLE; i += 1) { const q = queries[weightedPick()], prefix = q.slice(0, 1 + Math.floor(rand() * Math.min(10, q.length))); let lo = 0, hi = sorted.length; // binary search for the start of the range while (lo < hi) { const o = (lo + hi) >> 1; if (sorted[o][0] < prefix) lo = o + 1; else hi = o; } let n = 0; while (lo + n < sorted.length && sorted[lo + n][0].startsWith(prefix)) n += 1; treeUnits.push(prefix.length + 1); // descent + reading the node's ready list listUnits.push(binaryLog + n); range.push([lo, n]); } const percentile = (a, p) => [...a].sort((x, y) => x - y)[Math.floor(p * a.length)]; const mean = (a) => a.reduce((x, y) => x + y, 0) / a.length; console.log(`\n${"search".padEnd(32)}${"average units".padStart(16)}${"p99".padStart(8)}`); for (const [name, a] of [["prefix tree (ready list is read)", treeUnits], ["flat sorted list (binary + scan)", listUnits]]) console.log(`${name.padEnd(32)}${b(mean(a)).padStart(16)}${String(percentile(a, 0.99)).padStart(8)}`); // Update lag: a share of queries rises over time; the suggestion list built from an old // snapshot is compared against the correct list at that moment. const RISING = 0.02, HALF_LIFE = 3600; const rising = new Uint8Array(QUERIES); for (let i = 0; i < QUERIES; i += 1) rising[i] = rand() < RISING ? 1 : 0; const topK = (lo, n, f) => { const p = []; for (let i = 0; i < n; i += 1) { const j = sorted[lo + i][1]; p.push([f(j), j]); } p.sort((x, y) => y[0] - x[0]); return p.slice(0, K).map((x) => x[1]); }; console.log(`\n${"lag".padStart(9)}${"rise factor".padStart(15)}${"overlap in top 10".padStart(19)}${"prefixes with a changed top".padStart(30)}`); for (const lag of [600, 3600, 21_600, 86_400]) { const factor = 1 + lag / HALF_LIFE; let overlap = 0, topChanged = 0; for (const [lo, n] of range) { const old = topK(lo, n, (j) => frequency[j]); const fresh = topK(lo, n, (j) => frequency[j] * (rising[j] ? factor : 1)); const set = new Set(fresh); overlap += old.filter((x) => set.has(x)).length / Math.max(1, Math.min(K, n)); if (old[0] !== fresh[0]) topChanged += 1; } console.log(`${`${lag} s`.padStart(9)}${b(factor).padStart(15)}${b(overlap / range.length, 4).padStart(19)}` + `${b(topChanged / range.length, 4).padStart(30)}`); } const PEAK = 8333.33; // from the estimate block: peak suggestion requests/s console.log(`\nunits/s at peak: prefix tree ${b(mean(treeUnits) * PEAK)}, flat sorted list ${b(mean(listUnits) * PEAK)} ` + `(ratio ${b(mean(listUnits) / mean(treeUnits))})`); ``` ``` model: 50,000 distinct queries, average length 15.42 characters structure nodes bytes per query GB at VA4 queries flat list - 23.42 0.70 prefix tree, depth 6 4,588 8.07 0.24 prefix tree, depth 8 24,762 43.58 1.31 prefix tree, depth 10 86,967 153.06 4.59 prefix tree, depth full 357,080 628.46 18.85 search average units p99 prefix tree (ready list is read) 6.10 11 flat sorted list (binary + scan) 1047.32 6593 lag rise factor overlap in top 10 prefixes with a changed top 600 s 1.17 0.9979 0.0000 3600 s 2.00 0.9898 0.0015 21600 s 7.00 0.9546 0.0795 86400 s 25.00 0.8382 0.1640 units/s at peak: prefix tree 50833.31, flat sorted list 8727688.18 (ratio 171.69) ``` The first table turns depth into a budget decision. At full depth, the prefix tree wants 628.46 bytes per query, **18.85 GB** at VA4 scale — more than double G2's 8 GB threshold. Cut to a depth of 10, it drops to 153.06 bytes per query, **4.59 GB**, and falls under the threshold. This is where the scope reduction pays off: not suggesting for a prefix longer than ten characters is not a convenience, it is the **constraint** that lets the tree fit the budget. Cost does not grow linearly with depth — the move from 6 to 8 multiplies bytes fivefold, from 8 to 10 three and a half fold. The second table gives the search cost. The unit is a visited node or a compared record, not a duration. The prefix tree spends an average of 6.10 units and 11 units at p99: cost depends on prefix length, not query count, so the worst case is bounded too. In the flat sorted list, binary search finds the start of the range, but every matching record still has to be scanned: 1047.32 units on average, 6593 at p99. At peak load the difference is 50,833.31 against 8,727,688.18 units/s, that is **171.69-fold**. The third table gives the price of update lag. Within G3's 600-second window, the top ten suggestions' overlap is 0.9979, and no prefix's top suggestion changes. When the window grows to an hour, overlap is 0.9898; at six hours, 0.9546, and the top changes for 0.0795 of prefixes; for a structure rebuilt once a day, overlap drops to 0.8382 and the top suggestion is wrong for **0.1640** of prefixes. Freshness does not decay linearly: the first ten minutes are nearly free, the first day is expensive. #### Design - **Prefix tree, depth 10** (Data Structures, Tries). The parameter is depth; it stays under G2 at 4.59 GB. - **Materialized view** (Scaling the Data Layer, Materialized Views). Each node holds that prefix's first 10 suggestions ready; the parameter is **10 records × 4 bytes** per node, and this is what brings the search cost down from a subtree walk to 6.10 units. - **Replication** (Data Distribution, Replication). Every suggestion node holds a full copy of the structure in memory; the parameter is 4.59 GB per copy. - **Push-based distribution** (Traffic Layer, Push and Pull Based Distribution). The structure is built in bulk and pushed to the nodes; the parameter is the 600-second period, that is, 144 runs a day. - **Task queue and background job** (Application Layer, Task Queues and Background Jobs). The parameter is the 30 million queries scanned per rebuild run. - **Edge caching** (Traffic Layer, Content Delivery Networks). Since the suggestion response is not personal, it can be cached at the edge; the parameter is that its lifetime is **600 seconds**, the same as G3. In the previous case, this exact reason kept this pattern from being usable. **Two deliberately unused patterns.** Sharding (Data Distribution, Sharding) is not used: since the structure fits a single node at 4.59 GB, sharding would turn every request into scatter–gather and break p99. Cache-aside (Scaling the Data Layer, Cache-Aside) is not used: the whole structure is already in memory, there is no store behind it to warm up. #### Eliminated Alternative: A Flat Sorted List The alternative design does not build a tree; it keeps queries in a sorted array, finds the prefix by binary search, and scans the matching range. What it wins was measured, and it is large: 23.42 bytes per query, **0.70 GB** at VA4 scale, less than a sixth of what the prefix tree uses; and since no depth limit is needed, long prefixes are served too. The number that eliminates it is in search cost: an average of 1047.32 units against 6.10, and 8,727,688.18 against 50,833.31 units/s at peak load. The real problem is not the average but the tail — 6593 units at p99, because short prefixes match thousands of records, all of which must be sorted by frequency. G1 is the threshold for fitting between keystrokes, and a structure that breaks p99 cannot carry that threshold. The alternative wins if a different constraint changes: had suggestions been given only for long prefixes, the matching range would shrink and the two structures would converge; what decides it is how many records the shortest prefix matches. #### Failure Behavior and What Is Given Up **If the rebuild job stops**, the structure freezes and requests keep being answered — the symptom of this failure is not an error but a shift in freshness. The third table counts this shift: if the job stops for an hour, the top ten's overlap is 0.9898; for six hours, 0.9546, and the top suggestion is wrong for 0.0795 of prefixes; for a day, 0.8382 and 0.1640. Graceful degradation (Resilience and Reliability, Graceful Degradation) arrives on its own here, because the read path does not depend on the build path. **If a suggestion node drops**, no request is lost: because every node keeps a full copy, the load spreads to the others, and only the capacity share shrinks. This is the second payoff of preferring replication over sharding. **What is given up is depth and freshness.** A prefix longer than ten characters finds no ready list and is left to the client's filtering; a new query is not suggested for up to 600 seconds. Both were bought deliberately: in exchange, the structure fit a single node's memory, and search cost dropped to prefix length. #### Summary - Peak suggestion requests reach 8333.33/s, twelve times search; G2's 8 GB threshold turns into a budget of 266.67 bytes per query. - At full depth, the prefix tree wants 628.46 bytes per query and 18.85 GB — outside the budget. Cut to depth 10, it becomes 153.06 bytes and 4.59 GB; this is where the scope reduction pays off. - Keeping the first 10 suggestions ready per node brings search down to an average of 6.10 units and 11 units at p99. - A flat sorted list uses less than a sixth of the memory (0.70 GB) but spends 1047.32 units on average, 6593 at p99; the difference at peak load is 171.69-fold, and the elimination comes from the tail. - Update lag does not decay linearly: at 600 seconds, overlap is 0.9979 and the top change rate is 0.0000; at a day, overlap is 0.8382 and the top suggestion is wrong for 0.1640 of prefixes. - What is given up is the ready list for a prefix longer than ten characters and a 600-second freshness window. #### Next Step In all three cases, the response was **a record**: a target link, a list of posts, a list of suggestions. The bytes carried were small, and the expensive line item was compute or memory; the network was never a constraint. In the next case this changes: the same system carries both personal responses of a few hundred bytes and large, unchanging files resent on every request. When the two travel the same path, one breaks the other's queue. The question is where the two kinds of traffic get split, and what the split does to the request count and the bytes that reach the origin. ### Content Distribution Design Source: https://academia.sh/en/courses/case-studies/content-distribution-design Separating static and dynamic traffic: measuring the split's effect on the request count and bytes reaching the origin with an edge cache model, deriving the hit rate the threshold requires from the estimate, separating the request hit rate from the byte hit rate, and the versioned name zeroing out the staleness window. In all three cases, the response was a record, the bytes carried were small, and the expensive line item was compute or memory. In this case the same system carries two different kinds of traffic: **personal responses** of a few hundred bytes, and large, unchanging **static assets** resent on every request. When the two travel the same path, one's property breaks the other — a personal response cannot be cached, and the entire path is treated as uncacheable because of it. This lesson measures what the split does to the request count and bytes reaching the origin. #### Constraints **Functional requirements.** F1: the application shell and its assets (scripts, styles, images) reach the client. F2: a request for personal data is answered. F3: when a new version is published, the client does not use the old one. F4: a published version can be rolled back. **Scope reduction.** Resizing and encoding images, offline operation, and whether the shell is built on the server or the client are outside this design; all three change the number of **bytes** carried, not where traffic gets split. | Code | Threshold | Threshold's source | |---|---|---| | G1 | the median personal response does not exceed 150 ms | how long data is expected on screen | | G2 | no more than 2000 requests per second reach the origin | the origin's provisioned capacity | | G3 | a new version is active on every client within 300 seconds | for a bad version to be rolled back | | G4 | the cache per edge node does not exceed 8 GB | the node's local storage share | #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | VI1 | daily sessions | 4,000,000 | number of users who open the application | | VI2 | static asset requests per session | 25 | scripts, styles, and images combined | | VI3 | personal requests per session | 8 | data calls that fill the screen | | VI4 | peak factor | 3 | the ratio of the peak-hour rate to the daily average | | VI5 | static asset size | base 20 KB, exponent 2, cap 4 MB | a few large bundles, many small assets; average is 40 KB | | VI6 | personal response | 6 KB | fields that fill the screen | | VI7 | distinct static assets | 500,000 | versioned names and images included | | VI8 | static request distribution | Zipf, exponent 0.9 | a small number of assets in every session, most requested rarely | #### Back-of-the-Envelope Estimate ```js // distribution/estimate.mjs — the estimate from VI1-VI8 and deriving the hit rate G2 requires const VI = { sessions: 4e6, staticRequests: 25, dynamicRequests: 8, peakFactor: 3, assetBytes: 40_960, responseBytes: 6144 }; const DAY = 86_400, ORIGIN = 2000; // ORIGIN: G2 threshold, requests/s const b = (x, n = 2) => x.toFixed(n); const mbit = (x) => (x * 8) / 1e6; const staticPeak = (VI.sessions * VI.staticRequests / DAY) * VI.peakFactor; const dynamicPeak = (VI.sessions * VI.dynamicRequests / DAY) * VI.peakFactor; const staticBytes = staticPeak * VI.assetBytes, dynamicBytes = dynamicPeak * VI.responseBytes; console.log(`peak static requests/s = ${b(staticPeak)} peak dynamic requests/s = ${b(dynamicPeak)} total = ${b(staticPeak + dynamicPeak)}`); console.log(`request ratio static/dynamic = ${b(staticPeak / dynamicPeak)} byte ratio = ${b(staticBytes / dynamicBytes)}`); console.log(`peak egress: static ${b(mbit(staticBytes))} Mbit/s, dynamic ${b(mbit(dynamicBytes))} Mbit/s`); console.log(`G2 threshold ${ORIGIN} requests/s; the undivided design exceeds it by ${b(staticPeak + dynamicPeak - ORIGIN)} requests/s`); console.log(`static request hit rate needed to hold G2 = ${b(1 - (ORIGIN - dynamicPeak) / staticPeak, 4)}`); console.log(`the dynamic floor alone sends ${b(dynamicPeak)} requests/s to the origin = ${b(dynamicPeak / (staticPeak + dynamicPeak), 4)} of the total`); const doubled = (VI.sessions * VI.staticRequests * 2 / DAY) * VI.peakFactor; console.log(`VI2 sensitivity: static requests per session 25 -> 50 makes peak static ${b(doubled)} requests/s and required hit rate ${b(1 - (ORIGIN - dynamicPeak) / doubled, 4)}`); ``` ``` peak static requests/s = 3472.22 peak dynamic requests/s = 1111.11 total = 4583.33 request ratio static/dynamic = 3.13 byte ratio = 20.83 peak egress: static 1137.78 Mbit/s, dynamic 54.61 Mbit/s G2 threshold 2000 requests/s; the undivided design exceeds it by 2583.33 requests/s static request hit rate needed to hold G2 = 0.7440 the dynamic floor alone sends 1111.11 requests/s to the origin = 0.2424 of the total VI2 sensitivity: static requests per session 25 -> 50 makes peak static 6944.44 requests/s and required hit rate 0.8720 ``` Four numbers determine the design. The first is that the two ratios are **different from each other**: static traffic is 3.13 times dynamic in requests, 20.83 times in bytes. Speaking of a single "traffic" number is therefore misleading — the answer differs depending on which resource is under pressure. The second is that the undivided design exceeds G2 by 2583.33 requests/s. The third is that the threshold turns into a hit rate: keeping the origin under 2000 requests/s requires a static hit rate of at least **0.7440**. The fourth is the floor itself: the dynamic stream alone sends 1111.11 requests/s to the origin, and this **does not come down** no matter the hit rate; 0.2424 of total requests is reduced by no cache. #### Measuring the Split ```js // distribution/separation.mjs — the effect of the static/dynamic split on requests and bytes // reaching the origin. The edge cache is a Map that keeps the most recently used entry // (insertion order = use order). Asset sizes and the request stream are generated with a // hand-written generator, the seed is fixed. IT IS A MODEL. const SEED = 20260730, ASSETS = 500_000, REQUESTS = 1_800_000, WARMUP = 600_000; const BASE = 20_480, EXPONENT = 2.0, CAP = 4 << 20, ZIPF = 0.9; // VI5 and VI8 const STATIC_PEAK = 3472.22, DYNAMIC_PEAK = 1111.11, DYNAMIC_BYTES = 6144; // from the estimate block let s = SEED % 2147483647; const rand = () => (s = (s * 48271) % 2147483647) / 2147483647; const size = new Int32Array(ASSETS); for (let i = 0; i < ASSETS; i += 1) size[i] = Math.min(CAP, Math.round(BASE * Math.pow(rand(), -1 / EXPONENT))); const totalBytes = size.reduce((a, b) => a + b, 0); // Zipf(0.9) inverse sampling: rank = (1 + u (N^(1-z) - 1))^(1/(1-z)) const scalePow = Math.pow(ASSETS, 1 - ZIPF); const draw = () => Math.min(ASSETS - 1, Math.floor(Math.pow(1 + rand() * (scalePow - 1), 1 / (1 - ZIPF))) - 1); const requests = new Int32Array(REQUESTS); for (let i = 0; i < REQUESTS; i += 1) requests[i] = draw(); function run(capacity) { const cache = new Map(); let cursor = cache.keys(); let filled = 0, hits = 0, hitBytes = 0, measured = 0, measuredBytes = 0; for (let i = 0; i < REQUESTS; i += 1) { const v = requests[i], bt = size[v], counted = i >= WARMUP; if (counted) { measured += 1; measuredBytes += bt; } if (cache.has(v)) { cache.delete(v); cache.set(v, bt); if (counted) { hits += 1; hitBytes += bt; } continue; } if (bt > capacity) continue; // an asset that does not fit is not cached while (filled + bt > capacity) { // the least recently used entry is evicted let n = cursor.next(); if (n.done) { cursor = cache.keys(); n = cursor.next(); } const evictedBytes = cache.get(n.value); if (evictedBytes !== undefined) { cache.delete(n.value); filled -= evictedBytes; } } cache.set(v, bt); filled += bt; } return { requestHitRate: hits / measured, byteHitRate: hitBytes / measuredBytes, retained: cache.size }; } const b = (x, n = 2) => x.toFixed(n); const mbit = (bytesS) => (bytesS * 8) / 1e6; console.log(`model: ${ASSETS.toLocaleString("en-US")} assets, total ${b(totalBytes / 1e9)} GB, average ` + `${b(totalBytes / ASSETS / 1024)} KB, ${REQUESTS.toLocaleString("en-US")} requests (first ${WARMUP.toLocaleString("en-US")} warmup)`); const undividedRequests = STATIC_PEAK + DYNAMIC_PEAK; const undividedBytes = STATIC_PEAK * (totalBytes / ASSETS) + DYNAMIC_PEAK * DYNAMIC_BYTES; console.log(`\nno split (the personal document makes the entire path uncacheable):`); console.log(` reaching the origin: ${b(undividedRequests)} requests/s and ${b(mbit(undividedBytes))} Mbit/s`); console.log(`\n${"edge cache".padStart(12)}${"assets retained".padStart(17)}${"request hit rate".padStart(18)}` + `${"byte hit rate".padStart(15)}${"origin requests/s".padStart(19)}${"origin Mbit/s".padStart(15)}${"request factor".padStart(16)}${"byte factor".padStart(13)}`); for (const gb of [0.5, 2, 8, 20.5]) { const r = run(gb * 1e9); const originRequests = STATIC_PEAK * (1 - r.requestHitRate) + DYNAMIC_PEAK; const originBytes = STATIC_PEAK * (1 - r.byteHitRate) * (totalBytes / ASSETS) + DYNAMIC_PEAK * DYNAMIC_BYTES; console.log(`${`${gb} GB`.padStart(12)}${r.retained.toLocaleString("en-US").padStart(17)}${b(r.requestHitRate, 4).padStart(18)}` + `${b(r.byteHitRate, 4).padStart(15)}${b(originRequests).padStart(19)}${b(mbit(originBytes)).padStart(15)}${b(undividedRequests / originRequests).padStart(16)}${b(undividedBytes / originBytes).padStart(13)}`); } ``` ``` model: 500,000 assets, total 20.44 GB, average 39.93 KB, 1,800,000 requests (first 600,000 warmup) no split (the personal document makes the entire path uncacheable): reaching the origin: 4583.33 requests/s and 1190.40 Mbit/s edge cache assets retained request hit rate byte hit rate origin requests/s origin Mbit/s request factor byte factor 0.5 GB 12,118 0.4562 0.4390 2999.18 691.80 1.53 1.72 2 GB 49,111 0.6188 0.6059 2434.84 502.20 1.88 2.37 8 GB 196,218 0.8272 0.8209 1711.28 258.06 2.68 4.61 20.5 GB 324,829 0.8773 0.8727 1537.00 199.14 2.98 5.98 ``` The model finds the assets' average to be 39.93 KB; because the estimate block uses VI5's theoretical average (40 KB), the two blocks' byte counts diverge in the second digit. The measured value is the true average of the cap-truncated distribution. **The split holds G2 only with enough cache.** At the 8 GB G4 allows, the request hit rate is 0.8272, above the required 0.7440; 1711.28 requests/s reach the origin and the threshold holds. At 2 GB, the hit rate drops to 0.6188, the origin rises to 2434.84 requests/s, and **G2 breaks**. Cache size is not a convenience in this design; it is the parameter that holds the threshold. **The split does not reduce requests and bytes at the same rate.** At 8 GB, requests drop 2.68-fold, bytes 4.61-fold. The reason was already in the estimate: the dynamic stream holds 0.2424 of requests but less than one-twentieth of bytes. As the cache removes the static side, what remains is a floor that is **heavy in requests, light in bytes**. A design cannot be defended with the sentence "we cut the origin by seventy percent"; which number was cut must be stated. **Request hit rate and byte hit rate are separate numbers.** In every row, the byte hit rate is lower than the request hit rate (0.8209 against 0.8272): large assets get evicted from the cache sooner, because dozens of small assets fit in their place. The difference is small but its sign is constant, and it grows as the cache shrinks (0.4390 against 0.4562 at 0.5 GB). #### Design - **Content delivery network and edge caching** (Traffic Layer, Content Delivery Networks). The parameter is **8 GB** per node, and the measured request hit rate of 0.8272 is above G2's required 0.7440. - **Static content hosting** (Traffic Layer, Static Content Hosting). The parameter is the **versioned name**: an asset whose content changes gets a new name too, so it can be given an unbounded lifetime. - **API gateway** (Traffic Layer, API Gateway). The dynamic path goes through here; the parameter is the 1111.11 requests/s floor reaching the origin. - **Backend for frontend** (Traffic Layer, Backends for Frontends). The parameter is **8** personal requests per session; if this number drops, the floor drops too, because the floor is reduced not by caching but by **merging**. - **Push-based distribution** (Traffic Layer, Push and Pull Based Distribution). A new version's assets are pushed to the edge before publishing; the parameter is G3's **300-second** window. - **Graceful degradation** (Resilience and Reliability, Graceful Degradation). When the origin drops, the edge keeps serving the assets it holds; the parameter is the share of requests that stay up. **Two deliberately unused patterns.** Refresh-ahead (Scaling the Data Layer, Refresh-Ahead) is not used: an asset under a versioned name never goes stale, there is nothing to refresh. Session stickiness (Traffic Layer, Session Stickiness) is not used: the static path holds no state, and stickiness would lower the hit rate by preventing the edge cache from being shared. #### Eliminated Alternative: One Path, Short-Lived Cache The alternative design does not separate the two kinds of traffic; it sends everything through one path and gives static assets a short cache lifetime. What it wins is real: a single distribution line, a single publish step, no version mixing — the document and its assets refresh together. A publish staying atomic is not a small gain. The number that eliminates it is at the origin. Because the personal document cannot be cached, caching on the single path can be given only to assets, and their lifetime has to stay short since their names never change; this pulls the hit rate close to the table's 0.5 GB row. In the undivided design, the origin takes 4583.33 requests/s and 1190.40 Mbit/s — it exceeds G2 by 2583.33 requests/s, and no cache size rescues this, because the problem is not size but **cacheability**. The alternative wins if a different constraint changes: had the origin's capacity been 5000 requests/s, G2 would hold on its own, and bandwidth would be the split's only remaining justification. #### Failure Behavior and What Is Given Up **If the origin drops**, the static path stays up: the edge keeps meeting 0.8272 of requests with the assets it holds, and thanks to the versioned name, what it serves is not stale but the correct version. What drops is the entire dynamic floor — 0.2424 of requests. The application opens but its data does not arrive; this is graceful degradation's shape in this case. **If an edge node drops**, other nodes take the load, but their caches are cold for those assets. The table's first row gives the lower bound of a cold cache: at a 0.4562 hit rate the origin takes 2999.18 requests/s and **G2 breaks**. The cost of takeover here is not capacity but **warmup time**. **What is given up is the atomicity of publishing.** Because the two paths advance at two speeds, a client can see a new document with an old asset, or the reverse, within G3's 300-second window. The versioned name zeroed out the staleness window on the static side, but in exchange it opened a new window: **the staleness of each side relative to the other**. #### Summary - Static traffic is 3.13 times dynamic in requests, 20.83 times in bytes; defending a design with a single traffic number hides which resource is under pressure. - G2's 2000 requests/s threshold turns into a hit rate: static hit rate must be at least 0.7440. At the 8 GB G4 allows, the measured hit rate is 0.8272; at 2 GB it is 0.6188 and the threshold breaks. - The split cuts requests 2.68-fold and bytes 4.61-fold; the difference comes from the dynamic floor holding 0.2424 of requests but a very small share of bytes. - The byte hit rate is always lower than the request hit rate (0.8209 against 0.8272 at 8 GB), and the gap grows as the cache shrinks, because large assets are evicted first. - The versioned name zeroes out the staleness window on the static side; refresh-ahead is therefore unnecessary. - What is given up is the atomicity of publishing: within the 300-second window, a new document can be paired with an old asset. #### Next Step The four cases belonged to the same family. In URL shortening, reads outnumbered writes a hundred to one; in the news feed, forty to one; in search suggestion, twelve to one; in content distribution, even the dynamic requests stayed small next to cached static traffic. This ratio was the backbone of all four designs: work was shifted from the read side to the write side (fanning out to the box, keeping a ready suggestion list, the prefix tree), because writing was infrequent and the shifted work was cheap. All four shared a second point too: **staleness was an affordable price.** A redirect 300 seconds old at the edge, a post invisible for 60 seconds, a query not suggested for 600 seconds, one side drifting relative to the other — none of it counted as unacceptable, because a read being a little old is a correctable error. In a system dominated by writing, neither decision holds. If writing is not infrequent, shifting work to the read side is a multiplier, not a gain; and if a record being wrong is unacceptable, staleness stops being an affordable price and becomes a direct failure. The next topic opens with these reversed constraints: systems where writing outpaces reading, where order and delivery must be guaranteed, and where processing a record twice produces real damage. ## Write- and Consistency-Heavy Systems Five cases where writing and correctness drive the design: a chat system with connection management, delivery guarantees, and ordering problems; a notification system with multi-channel distribution and retries; a rate limiter with distributed counters and window algorithms; a ticketing and inventory system with contention management under limited resources; and a payment flow built on idempotency, reconciliation, and an audit trail. ### Chat System Source: https://academia.sh/en/courses/case-studies/chat-system The first case where writing dominates: connection and delivery scale drawn from nine assumptions, the effect of the delivery guarantee choice on lost and duplicated message counts measured in a one-second peak window, ordering violations counted with inversions, the sequential convoy's cost in wait rounds, and the polling model eliminated by needing 140.63 times push's delivery rate. The Read-Heavy Systems topic produced four cases, and in all four reading outdid writing by a wide margin. That balance makes one thing cheap: a response being a few seconds stale was an affordable cost, because the same record was read thousands of times and its freshness depended on a single write. The staleness window was a design tool there. This topic takes the reverse balance. In chat, a record is written once and read a small number of times; the record itself is a message a user sent. Its being lost, appearing a second time, or appearing in the wrong order is not acceptable. The same patterns are still on hand, but their parameters sit elsewhere. #### Constraints and Scope The functional requirements are five items: one-to-one message sending, group messages with at most 50 members, presence (online or last seen), delivery and read receipts, and holding messages for an offline recipient. What is not designed is stated explicitly: voice and video calling, file attachments, in-message search, end-to-end encryption, and history export are outside this case. The non-functional requirements are written with a threshold and the threshold's source: lost messages are zero (source: the message being assumed to exist once "sent" is shown to the sender), the same message being shown a second time is zero (source: the recipient's seen list being equal to the sent list), an ordering violation within a chat is zero (source: messages being replies to one another), and the median delivery delay to a connected recipient does not exceed 200 milliseconds (source: the concurrency the sender expects from the peer's typing indicator). #### Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | SO1 | daily active users | 5,000,000 | account that opens the app at least once a day | | SO2 | messages sent per user per day | 40 | short exchanges spread across a few chats | | SO3 | message body | 220 bytes | text, sender, chat ID, timestamp | | SO4 | peak factor | 4 | ratio of evening hours to the daily average | | SO5 | concurrently connected user share | 0.25 | connection held while the app is open | | SO6 | recipients per message | 2.4 | average of the one-to-one and group mix | | SO7 | offline recipient share | 0.35 | share of recipients not connected at delivery time | | SO8 | retention period | 365 days | history opens a year back | | SO9 | connections per node | 50,000 | open connections a single node carries | ```js // chat/scale.mjs — the back-of-envelope calculation drawn from the SO assumption table export const SO = { dailyUsers: 5_000_000, // SO1 messagesPerUser: 40, // SO2 messageBytes: 220, // SO3 peakFactor: 4, // SO4 connectedShare: 0.25, // SO5 avgRecipients: 2.4, // SO6 offlineShare: 0.35, // SO7 retentionDays: 365, // SO8 connectionsPerNode: 50_000, // SO9 }; const DAY = 86_400; export function calculate(v) { const dailyMessages = v.dailyUsers * v.messagesPerUser; const avgSend = dailyMessages / DAY; const peakSend = avgSend * v.peakFactor; const peakDelivery = peakSend * v.avgRecipients; const connected = v.dailyUsers * v.connectedShare; return { "daily messages": dailyMessages, "average sends/s": avgSend, "peak sends/s": peakSend, "peak deliveries/s": peakDelivery, "peak mailbox writes/s": peakDelivery * v.offlineShare, "concurrent connected users": connected, "connection nodes": connected / v.connectionsPerNode, "peak egress Mbit/s": (peakDelivery * v.messageBytes * 8) / 1e6, "daily data growth GB": (dailyMessages * v.messageBytes) / 1e9, "stored data TB": (dailyMessages * v.messageBytes * v.retentionDays) / 1e12, }; } const r = calculate(SO); const format = (x) => (Number.isInteger(x) ? String(x) : x.toFixed(2)); for (const [name, d] of Object.entries(r)) console.log(`${name.padEnd(28)}${format(d).padStart(13)}`); const RESULT = ["peak deliveries/s", "connection nodes", "daily data growth GB"]; console.log(`\n${"assumption doubled".padEnd(25)}${RESULT.map((s) => s.split(" ")[0].padStart(11)).join("")}`); for (const name of ["messagesPerUser", "connectedShare", "avgRecipients"]) { const y = calculate({ ...SO, [name]: SO[name] * 2 }); console.log(`${name.padEnd(25)}${RESULT.map((s) => `x${(y[s] / r[s]).toFixed(2)}`.padStart(11)).join("")}`); } ``` ``` daily messages 200000000 average sends/s 2314.81 peak sends/s 9259.26 peak deliveries/s 22222.22 peak mailbox writes/s 7777.78 concurrent connected users 1250000 connection nodes 25 peak egress Mbit/s 39.11 daily data growth GB 44 stored data TB 16.06 assumption doubled peak connection daily messagesPerUser x2.00 x1.00 x2.00 connectedShare x1.00 x2.00 x1.00 avgRecipients x2.00 x1.00 x1.00 ``` These numbers belong to the **calculation** class. Four of them shape the design. First, peak sends are 9259.26 while peak deliveries are 22,222.22: every write produces 2.4 deliveries on average, and the load the system sees is not the write rate but the **delivery** rate. Second, 1,250,000 concurrent connections mean 25 connection nodes; that is 25 units of state held somewhere. Third, peak mailbox writes are 7777.78 records per second: more than a third of deliveries go to a recipient who is not connected and get written to a persistent mailbox. Fourth, bandwidth is small: 39.11 Mbit/s of egress, 44 GB of daily growth. In this case the bottleneck is not bytes but **record count** and **connection count**. The sensitivity table separates two sources: when the connected share doubles, only the node count doubles; when the recipient count doubles, only the delivery rate doubles. #### Design **Connection node.** The long-lived connection turns the stickiness covered in the Traffic Layer course's Session Stickiness lesson from a choice into a requirement: a connection is bound to a node and stays on that node. The parameter is the stickiness key: the device ID, not the user ID, because a second device for the same user is a separate connection. The mapping from device to node is done with the consistent hashing from the same course's Balancing Algorithms lesson; on a 25-node ring, adding one node moves a connection share of 1/26. **Routing directory.** The sender's node must know which node the recipient is connected to. This is the state store from the Application Layer and Service Interaction course's Stateless Services lesson; the record it holds is user ID, node name, and last heartbeat timestamp — the same record as presence. **Delivery path.** Every delivery passes through a message broker. Order within a chat is kept with the lane from the same course's Sequential Convoy lesson, and **the lane key is the chat ID**, not the sender ID: the ordering constraint exists within the chat, not across all of a sender's chats. **Uniqueness.** The client generates the message ID, and a resend carries the same ID. The scope of the uniqueness key from the Resilience and Reliability course's Idempotent Operations lesson is the `(sender, client message ID)` pair here; the chat ID is not part of the scope, because there is no case of the same message going to two chats. **Offline mailbox.** Messages for a recipient who is not connected are written to a persistent mailbox; the partition key from the Scaling the Data Layer course's Partitioning Strategies lesson is the recipient ID. **Deliberately unused pattern.** Edge caching (Traffic Layer, Entry Points) has no place in this design: every message goes to a single set of recipients exactly once, and no shared hit ever forms. #### Delivery Guarantee and Order Are Measured The measurement is an in-process model: there is no real socket, network, or broker; the channel is a probability and a round is an abstract step. Three more assumptions are added. **SO10 — channel loss probability 0.02**, justified by short cellular-connection drops; **SO11 — acknowledgment loss probability 0.01**, justified by the acknowledgment's return path being shorter; **SO12 — resend backoff 3 rounds**. The model takes a one-second peak window: 22,222 deliveries, 40 chat lanes. ```js // chat/delivery.mjs — in-process model of the delivery guarantee and ordering breakdown. // There is no real network, socket, or queue: the channel is a probability, the round is an abstract step. export function generator(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } const DELIVERIES = 22222, CHATS = 40; // calculation: peak deliveries/s x 1-second window const LOSS = 0.02, ACK_LOSS = 0.01; // SO10, SO11 const BACKOFF = 3; // SO12: resend backoff rounds export function run({ attempts, keyed, convoy, seed }) { const rnd = generator(seed); const laneLastArrival = new Array(CHATS).fill(0); const laneStream = Array.from({ length: CHATS }, () => []); const s = { channelAttempts: 0, lost: 0, duplicated: 0, waitRounds: 0 }; for (let i = 0; i < DELIVERIES; i += 1) { const chat = i % CHATS; const seq = Math.floor(i / CHATS); // the message's position in the lane and its send round let round = convoy ? Math.max(seq, laneLastArrival[chat]) : seq; s.waitRounds += round - seq; // waiting on the earlier message in the lane let reached = 0, arrival = null; for (let d = 0; d < attempts; d += 1) { s.channelAttempts += 1; if (rnd() < LOSS) { round += BACKOFF; continue; } // delivery dropped on the channel reached += 1; if (arrival === null) arrival = round; if (rnd() < ACK_LOSS) { round += BACKOFF; continue; } // ack dropped, sender resends break; } if (reached === 0) s.lost += 1; else { if (keyed === false) s.duplicated += reached - 1; laneStream[chat].push({ seq, arrival }); laneLastArrival[chat] = arrival; } } s.inversions = laneStream.reduce((t, stream) => { const arrivals = stream.map((o, i) => ({ ...o, i })).sort((a, b) => a.arrival - b.arrival || a.i - b.i); let n = 0; for (let a = 0; a < arrivals.length; a += 1) for (let b = a + 1; b < arrivals.length; b += 1) if (arrivals[a].seq > arrivals[b].seq) n += 1; return t + n; }, 0); return s; } const SCHEMES = [ ["at-most-once / free", { attempts: 1, keyed: false, convoy: false }], ["at-least-once / free", { attempts: 5, keyed: false, convoy: false }], ["at-least-once + key", { attempts: 5, keyed: true, convoy: false }], ["same + sequential convoy", { attempts: 5, keyed: true, convoy: true }], ]; console.log(`model: ${DELIVERIES} deliveries, ${CHATS} chat lanes, loss ${LOSS}, ack loss ${ACK_LOSS}, seed 20260730`); console.log(`\n${"scheme".padEnd(26)}${"channel attempts".padStart(17)}${"lost".padStart(10)}` + `${"duplicated".padStart(11)}${"inversions".padStart(11)}${"wait rounds".padStart(14)}`); const R = {}; for (const [name, choice] of SCHEMES) { const r = (R[name] = run({ ...choice, seed: 20260730 })); console.log(`${name.padEnd(26)}${String(r.channelAttempts).padStart(17)}${String(r.lost).padStart(10)}` + `${String(r.duplicated).padStart(11)}${String(r.inversions).padStart(11)}${String(r.waitRounds).padStart(14)}`); } const mostOnce = R["at-most-once / free"], atLeastOnce = R["at-least-once / free"]; const convoy = R["same + sequential convoy"]; console.log(`\nexpected loss = ${DELIVERIES} x ${LOSS} = ${(DELIVERIES * LOSS).toFixed(2)}; measured ${mostOnce.lost}`); console.log(`cost of resending: channel attempts x${(atLeastOnce.channelAttempts / mostOnce.channelAttempts).toFixed(4)}, ` + `duplicate display rate ${((100 * atLeastOnce.duplicated) / DELIVERIES).toFixed(2)}%`); console.log(`cost of the convoy: ${(convoy.waitRounds / DELIVERIES).toFixed(3)} wait rounds per message; ` + `inversions ${atLeastOnce.inversions} -> ${convoy.inversions}`); ``` ``` model: 22222 deliveries, 40 chat lanes, loss 0.02, ack loss 0.01, seed 20260730 scheme channel attempts lost duplicated inversions wait rounds at-most-once / free 22222 408 0 0 0 at-least-once / free 22870 0 229 827 0 at-least-once + key 22870 0 0 827 0 same + sequential convoy 22870 0 0 0 1414 expected loss = 22222 x 0.02 = 444.44; measured 408 cost of resending: channel attempts x1.0292, duplicate display rate 1.03% cost of the convoy: 0.064 wait rounds per message; inversions 827 -> 0 ``` These numbers belong to the **measurement** class; they reproduce with seed 20260730. The first row shows what at-most-once delivery gets: in the one-second peak window, 408 messages are lost, and in exchange no duplication and no ordering violation arise. Expected loss was 444.44; the measured 408 is this run's count. Lost messages do not disrupt the order of the rest, because nothing is resent. At-most-once delivery being clean with respect to order is not a coincidence — it is the loss itself. The second row hands over the bill for at-least-once delivery. Loss drops to zero; the cost is channel attempts rising to 1.0292 times, 229 messages reaching the recipient a second time (1.03% of deliveries), and 827 inversions. The duplication comes from the acknowledgment being lost: the message has arrived, the sender does not know it. The third row isolates the uniqueness key's contribution: the 229 duplicate displays drop to zero, inversions stay at 827. The key ledger resolves duplication, **not order**; the two are separate problems and call for separate patterns. The fourth row is the sequential convoy's contribution: the 827 inversions drop to zero, in exchange for 0.064 wait rounds paid per message, 1414 rounds total in the window. The wait arises from loss — when one delivery drops, the messages behind it wait in the lane. In a round without loss, the convoy's cost is zero. #### Eliminated Alternative: Polling A design that holds no connection can be built: messages are written to the mailbox, and the client asks at a fixed interval. This design removes the 25 connection nodes, the routing directory, and session stickiness all at once. The reason for its elimination is a ratio. ```js // chat/alternative.mjs — numeric comparison of the push model against the polling model const CONNECTED = 1_250_000, PEAK_DELIVERY = 22222.22; // scale.mjs calculation: connected users, peak deliveries/s const THRESHOLD_MS = 200; // delivery delay threshold (source: the write-response expectation) console.log(`${"poll interval".padStart(16)}${"poll requests/s".padStart(17)}${"ratio to push".padStart(14)}` + `${"non-empty polls".padStart(16)}${"avg delay ms".padStart(17)}`); for (const interval of [(2 * THRESHOLD_MS) / 1000, 1, 3, 10, 30]) { const requests = CONNECTED / interval; const nonEmpty = Math.min(1, (PEAK_DELIVERY * interval) / CONNECTED); console.log(`${`${interval} s`.padStart(16)}${requests.toFixed(0).padStart(17)}` + `${`x${(requests / PEAK_DELIVERY).toFixed(2)}`.padStart(14)}${`${(100 * nonEmpty).toFixed(2)}%`.padStart(16)}` + `${((interval * 1000) / 2).toFixed(0).padStart(17)}`); } const breakeven = CONNECTED / PEAK_DELIVERY; console.log(`\nbreakeven interval = connected / peak delivery = ${breakeven.toFixed(2)} s`); console.log(`average delivery delay at this interval = ${((breakeven * 1000) / 2 / 1000).toFixed(2)} s`); console.log(`interval needed for a ${THRESHOLD_MS} ms threshold = ${((2 * THRESHOLD_MS) / 1000).toFixed(1)} s, ` + `that is, x${(CONNECTED / ((2 * THRESHOLD_MS) / 1000) / PEAK_DELIVERY).toFixed(2)} of push's requests`); ``` ``` poll interval poll requests/s ratio to push non-empty polls avg delay ms 0.4 s 3125000 x140.63 0.71% 200 1 s 1250000 x56.25 1.78% 500 3 s 416667 x18.75 5.33% 1500 10 s 125000 x5.63 17.78% 5000 30 s 41667 x1.88 53.33% 15000 breakeven interval = connected / peak delivery = 56.25 s average delivery delay at this interval = 28.13 s interval needed for a 200 ms threshold = 0.4 s, that is, x140.63 of push's requests ``` The elimination number is the last line: a 200-millisecond average delay threshold demands a 0.4-second interval, which is 3,125,000 requests per second — 140.63 times the delivery rate in the push model. What is more, 99.29% of these requests return empty. Polling is a rate paid for work that is not carried. What the alternative wins is written too. The breakeven interval is 56.25 seconds: if the delay threshold rises above this, polling produces fewer requests, and the 25 connection nodes and the routing directory drop out of the design. The elimination is a delivery-delay-threshold decision; if the threshold were one minute, the choice would reverse. #### Failure Behavior and What Is Sacrificed When a connection node goes down, 50,000 connections drop at once and all of them try to reconnect. This is the scenario from the Performance Anti-Patterns and Monitoring course's Retry Storm lesson; its counterpart is the jitter and retry budget from the Resilience and Reliability course's Retries and Storm Risk lesson. The parameter is a ceiling: the 50,000 connections spread across the remaining 24 nodes mean 2083 extra connections per node, that is, 4.17% utilization. When the broker goes down, the design follows the path from the Graceful Degradation lesson: the connection stays up, presence and read receipts stop, and message sending falls through to the offline mailbox. What is sacrificed, in one sentence: a single lane per chat accepts giving up chat-level parallelism for the sake of in-chat order, and a 1414-round wait during rounds with loss. #### Summary - When writing dominates, the measure is record count: peak sends are 9259.26 while peak deliveries are 22,222.22, and bandwidth stays small at 39.11 Mbit/s. - 1,250,000 concurrent connections mean 25 nodes; when the connected share doubles, the delivery rate does not change, only the node count doubles. - At-most-once delivery lost 408 messages in the one-second peak window and never disrupted order; at-least-once delivery zeroed out loss but produced 229 duplicate displays and 827 inversions. - The uniqueness key zeroed out duplication and left inversions at 827; the sequential convoy zeroed out inversions and took 0.064 wait rounds per message. - Polling demands 140.63 times push's requests at the 200-millisecond threshold, and 99.29% of them return empty; the breakeven interval is 56.25 seconds. - Edge caching was deliberately not used: every message goes to a single set of recipients and never produces a shared hit. #### Next Step In this case delivery moved along a single path: the recipient was either connected or the message was written to their mailbox, and failure was met with a resend. The next case asks the same question where more than one path exists. The same notification can go out over different channels, the channels' failure rates differ from one another, and one channel's failure is grounds for trying another. The number to ask then is this: how much does trying the channels in sequence versus at the same time move the total delivery rate and the resend load. ### Notification System Source: https://academia.sh/en/courses/case-studies/notification-system The case where the same message can go out over more than one path: separating channel-specific transient and permanent failure rates, three attempts on a single channel leaving the delivery rate 3.01 points below the threshold, measuring single-channel against parallel and cascading channel order in delivery rate, outbound calls, duplicate deliveries, and delay, and parallel fan-out eliminated by its call amplification. In the previous case, delivery moved along a single path, and the only response to failure was retrying that same path. In this case there is more than one path. The same notification can go out by app push, SMS, or email; the channels' failure rates differ from one another, and one channel's failure is grounds for trying another. This changes the resend question. Where an attempt gets spent is now the question of "the same place, or somewhere else," and the answer moves two numbers at once: the total delivery rate and the number of outbound calls. #### Constraints and Scope The functional requirements: accepting the notification request, choosing a channel by the recipient's preference, formatting per channel, recording delivery status, and preventing the same event from going to the recipient a second time. What is not designed: writing the notification text and the templating language, translation, the permissions screen, choosing recipient sets, and the internal workings of the channel providers themselves. The non-functional requirements are written with a threshold and its source: the total delivery rate does not fall below 0.99 (source: the notification being the sole messenger for a transaction), the average delivery delay for an urgent notification does not exceed 5 seconds (source: the recipient expecting the news at the moment they perform the action), and the number of deliveries reaching the recipient for one event is one (source: receiving the same news over two channels counting as an error for the recipient). #### Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | BI1 | daily active recipients | 5,000,000 | account able to receive notifications | | BI2 | notifications per recipient per day | 6 | transaction news and reminders | | BI3 | peak factor | 5 | notifications piling into a few hours of the day | | BI4 | channel share | 0.55 / 0.25 / 0.20 | preference split across push, SMS, email | | BI5 | transient failure per channel | 0.05 / 0.02 / 0.01 | momentary unreachability, a resend fixes it | | BI6 | permanent failure per channel | 0.06 / 0.02 / 0.01 | invalid address, revoked permission, a resend does not fix it | | BI7 | notification record | 300 bytes | event ID, recipient, channel, status, timestamp | | BI8 | attempt budget | 3 | most outbound calls made per notification | | BI9 | wait between attempts | 30 seconds | time left for a transient failure to pass | The BI5–BI6 distinction is this case's decisive assumption. A transient failure clears when retried on the same channel; a permanent failure does not clear, and every attempt spent on the same channel is wasted. ```js // notification/scale.mjs — the back-of-envelope calculation drawn from the BI assumption table export const BI = { dailyRecipients: 5_000_000, // BI1 notificationsPerRecipient: 6, // BI2 peakFactor: 5, // BI3 share: { push: 0.55, sms: 0.25, email: 0.20 }, // BI4 transient: { push: 0.05, sms: 0.02, email: 0.01 }, // BI5 permanent: { push: 0.06, sms: 0.02, email: 0.01 }, // BI6 recordBytes: 300, // BI7 budget: 3, // BI8 wait: 30, // BI9 }; const DAY = 86_400; const daily = BI.dailyRecipients * BI.notificationsPerRecipient; const peak = (daily / DAY) * BI.peakFactor; console.log(`daily notifications ${daily}`); console.log(`peak notifications/s ${peak.toFixed(2)}`); console.log(`daily data growth GB ${((daily * BI.recordBytes) / 1e9).toFixed(2)}`); console.log(`\n${"channel".padEnd(11)}${"share".padStart(6)}${"peak calls/s".padStart(14)}${"transient".padStart(11)}` + `${"permanent".padStart(11)}${"remaining after 3 attempts".padStart(28)}`); let blendedRemaining = 0; for (const ch of Object.keys(BI.share)) { const remaining = BI.permanent[ch] + BI.transient[ch] ** BI.budget; blendedRemaining += BI.share[ch] * remaining; console.log(`${ch.padEnd(11)}${BI.share[ch].toFixed(2).padStart(6)}${(peak * BI.share[ch]).toFixed(2).padStart(14)}` + `${BI.transient[ch].toFixed(2).padStart(11)}${BI.permanent[ch].toFixed(2).padStart(11)}${remaining.toFixed(6).padStart(28)}`); } console.log(`\nsingle channel, ${BI.budget} attempts -> blended remaining error ${blendedRemaining.toFixed(6)}, ` + `delivery rate ${(1 - blendedRemaining).toFixed(4)}`); console.log(`threshold 0.9900 -> single channel ${1 - blendedRemaining >= 0.99 ? "passes" : "fails"}; ` + `gap ${((0.99 - (1 - blendedRemaining)) * 100).toFixed(2)} points`); console.log(`unreached notifications: peak ${(peak * blendedRemaining).toFixed(2)}/s, ` + `daily ${Math.round(daily * blendedRemaining)}`); console.log(`cascading worst-case delivery = (${BI.budget} - 1) x ${BI.wait} s = ${(BI.budget - 1) * BI.wait} s`); ``` ``` daily notifications 30000000 peak notifications/s 1736.11 daily data growth GB 9.00 channel share peak calls/s transient permanent remaining after 3 attempts push 0.55 954.86 0.05 0.06 0.060125 sms 0.25 434.03 0.02 0.02 0.020008 email 0.20 347.22 0.01 0.01 0.010001 single channel, 3 attempts -> blended remaining error 0.040071, delivery rate 0.9599 threshold 0.9900 -> single channel fails; gap 3.01 points unreached notifications: peak 69.57/s, daily 1202129 cascading worst-case delivery = (3 - 1) x 30 s = 60 s ``` These numbers belong to the **calculation** class. Three of them shape the design. First, peak load does not split evenly across channels: the push channel takes 954.86 calls per second while email takes 347.22, so the most crowded channel is also the channel with the highest permanent failure rate. Second, three attempts on the same channel all but erase the transient failure (0.05 to the third power for push, that is, 0.000125) but do not touch the permanent one; the remaining error comes almost entirely from BI6. Third, the single-channel design's delivery rate comes out to 0.9599 and stays 3.01 points below the 0.99 threshold: 1,202,129 notifications a day never arrive at all. The threshold forces a channel-order decision. #### Design **Intake and queue.** The notification request is accepted asynchronously; the Application Layer and Service Interaction course's Message Queues and Competing Consumers lessons give the structure here. The parameter is priority classes: two classes from the same course's Priority Queue lesson are used, urgent notification and reminder, because only one of the thresholds carries a delay. **Bulkhead per channel.** The resource pool from the Resilience and Reliability course's Bulkhead Pattern lesson is split per channel, and pool shares are given by the peak call rate: 954.86, 434.03, and 347.22 calls/s. The reason for the split is that one channel slowing down must not make the other channels' calls wait. **Circuit breaker per channel.** The threshold in the same course's Circuit Breaker lesson is here a choice of what to count: the circuit breaker counts only transient failures. A permanent failure is specific to the recipient and carries no information about the channel's health; if permanent failures counted toward it, the push channel's circuit would trip constantly because of a 6% floor. **Placement of the attempt budget.** The attempt budget in the Retries and Storm Risk lesson is 3, and this case's decision is where the budget gets spent: on the same channel, or on the next one in line. The measurement section turns this decision into a number. **Uniqueness.** The scope of the uniqueness key from the Resilience and Reliability course's Idempotent Operations lesson is the `(event ID, recipient)` pair here; the channel is not part of the scope, because the same event going out over two channels is exactly what is meant to be prevented. **Deliberately unused pattern.** The sequential convoy (Application Layer and Service Interaction, Queues and Workflows) has no place in this design: there is no ordering constraint between two notifications, each is the messenger for an independent event, and imposing a lane would cut parallelism for no reason. #### Channel Order Is Measured The measurement is an in-process model: there is no real channel, external service, or network; each attempt is a probability, and a round is an abstract step, one round being 30 seconds by BI9. The model takes a one-minute peak window: 104,167 notifications. Three arrangements spend the same 3-call budget in different places — **single channel** spends all three on the preferred channel, **parallel** spends all three on three channels at once, **cascading** spends one on the preferred channel and the rest on the others in sequence. ```js // notification/distribution.mjs — in-process model of channel order. There is no real channel, // external service, or network: each attempt is a probability, a round is an abstract step (BI9: 30 s wait per round). const CHANNEL = ["push", "sms", "email"]; const SHARE = { push: 0.55, sms: 0.25, email: 0.20 }; // BI4 const TRANSIENT = { push: 0.05, sms: 0.02, email: 0.01 }; // BI5 const PERMANENT = { push: 0.06, sms: 0.02, email: 0.01 }; // BI6 const BUDGET = 3, WAIT = 30; // BI8, BI9 const NOTIFICATIONS = 104_167; // calculation: peak 1736.11 notifications/s x 60 s window function generator(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } export function run({ arrangement, seed, multiplier = 1, down = null }) { const rnd = generator(seed); const s = { delivered: 0, outboundCalls: 0, duplicated: 0, roundTotal: 0 }; for (let i = 0; i < NOTIFICATIONS; i += 1) { let u = rnd(), preferred = CHANNEL[CHANNEL.length - 1]; for (const k of CHANNEL) { if (u < SHARE[k]) { preferred = k; break; } u -= SHARE[k]; } const isPermanent = {}; for (const k of CHANNEL) isPermanent[k] = k === down || rnd() < Math.min(1, PERMANENT[k] * multiplier); const sequence = arrangement === "single channel" ? [preferred, preferred, preferred] : [preferred, ...CHANNEL.filter((k) => k !== preferred)]; let reached = 0, firstRound = null; for (let t = 0; t < BUDGET; t += 1) { const k = sequence[t]; s.outboundCalls += 1; const succeeded = isPermanent[k] === false && rnd() >= Math.min(1, TRANSIENT[k] * multiplier); if (succeeded) { reached += 1; if (firstRound === null) firstRound = arrangement === "parallel" ? 0 : t; if (arrangement !== "parallel") break; } } if (reached > 0) { s.delivered += 1; s.roundTotal += firstRound; s.duplicated += reached - 1; } } s.rate = s.delivered / NOTIFICATIONS; return s; } const ARRANGEMENT = ["single channel", "parallel", "cascading"]; console.log(`model: ${NOTIFICATIONS} notifications, ${CHANNEL.length} channels, attempt budget ${BUDGET}, seed 20260730`); console.log(`\n${"arrangement".padEnd(16)}${"delivery rate".padStart(15)}${"outbound calls".padStart(16)}` + `${"calls/notification".padStart(20)}${"duplicated".padStart(12)}${"avg delivery s".padStart(16)}`); const R = {}; for (const a of ARRANGEMENT) { const r = (R[a] = run({ arrangement: a, seed: 20260730 })); console.log(`${a.padEnd(16)}${r.rate.toFixed(4).padStart(15)}${String(r.outboundCalls).padStart(16)}` + `${(r.outboundCalls / NOTIFICATIONS).toFixed(3).padStart(20)}${String(r.duplicated).padStart(12)}` + `${((r.roundTotal / r.delivered) * WAIT).toFixed(2).padStart(16)}`); } console.log(`\n${"failure multiplier".padEnd(20)}${ARRANGEMENT.map((a) => `${a} rate`.padStart(21)).join("")}`); for (const c of [1, 2, 3]) { const row = ARRANGEMENT.map((a) => run({ arrangement: a, seed: 20260730, multiplier: c }).rate.toFixed(4).padStart(21)); console.log(`${`x${c}`.padEnd(20)}${row.join("")}`); } console.log(`\n${"push channel down entirely".padEnd(28)}${ARRANGEMENT.map((a) => a.padStart(17)).join("")}`); const downed = ARRANGEMENT.map((a) => run({ arrangement: a, seed: 20260730, down: "push" })); console.log(`${"delivery rate".padEnd(28)}${downed.map((r) => r.rate.toFixed(4).padStart(17)).join("")}`); console.log(`${"outbound calls".padEnd(28)}${downed.map((r) => String(r.outboundCalls).padStart(17)).join("")}`); const single = R["single channel"], par = R["parallel"], cas = R["cascading"]; console.log(`\ncascading - single channel delivery rate difference = ${((cas.rate - single.rate) * 100).toFixed(2)} points`); console.log(`cost of parallel: outbound calls x${(par.outboundCalls / cas.outboundCalls).toFixed(2)}, ` + `${par.duplicated} duplicated deliveries, ${(par.duplicated / NOTIFICATIONS).toFixed(2)} extra per notification`); console.log(`gain of parallel: avg delivery ${((par.roundTotal / par.delivered) * WAIT).toFixed(2)} s, ` + `cascading ${((cas.roundTotal / cas.delivered) * WAIT).toFixed(2)} s`); ``` ``` model: 104167 notifications, 3 channels, attempt budget 3, seed 20260730 arrangement delivery rate outbound calls calls/notification duplicated avg delivery s single channel 0.9590 116305 1.117 0 1.08 parallel 0.9999 312501 3.000 190861 0.00 cascading 0.9999 112357 1.079 0 2.35 failure multiplier single channel rate parallel rate cascading rate x1 0.9590 0.9999 0.9999 x2 0.9199 0.9993 0.9994 x3 0.8790 0.9979 0.9979 push channel down entirely single channel parallel cascading delivery rate 0.4443 0.9993 0.9991 outbound calls 220661 312501 166806 cascading - single channel delivery rate difference = 4.09 points cost of parallel: outbound calls x2.78, 190861 duplicated deliveries, 1.83 extra per notification gain of parallel: avg delivery 0.00 s, cascading 2.35 s ``` These numbers belong to the **measurement** class; they reproduce with seed 20260730. The first table prices out the placement of the budget. Single channel gives a 0.9590 delivery rate, the same order of magnitude as the 0.9599 found by calculation; cascading climbs to 0.9999 with the same three-call budget, a difference of 4.09 points. What stands out is the second column: the cascading arrangement does this with **fewer** outbound calls, 1.079 calls per notification, below single channel's 1.117 calls. A notification that hits a permanent failure wastes all three calls in the single-channel arrangement; in the cascading arrangement, the second call finishes the job. Where a resend goes matters more than how many there are. The second table gives the sensitivity of the failure rates. When every channel's failure rate triples, single channel drops to 0.8790, cascading stays at 0.9979. Channel diversity's gain grows as the failure rate grows: the difference climbs from 4.09 points to 11.89 points. #### Eliminated Alternative: Parallel Fan-Out The parallel arrangement gives the same result as cascading in delivery rate (0.9999) and beats it on delay: average delivery is 0.00 seconds, versus 2.35 seconds for cascading. Even so, it is eliminated by two numbers. First, the outbound call count is 2.78 times cascading's, and it is fixed at 3.000 calls per notification; it does not fall even when channel failure falls, because the parallel arrangement sends all three without waiting for a result. Second, and decisive, it produces 190,861 duplicated deliveries: 1.83 extra deliveries per notification. This directly violates the non-functional requirement — the recipient gets the same news over an average of nearly three channels at once. What the alternative wins is written too: the parallel arrangement zeroes out the 60-second worst-case delivery window. If the delay threshold were 1 second instead of 5 and the "single delivery" requirement were lifted, the choice would reverse; a middle path where two channels are tried at once would also be defensible at this threshold. #### Failure Behavior and What Is Sacrificed The failure scenario is one channel stopping entirely: the push channel fails for every recipient. The third table gives the result. The single-channel arrangement drops to 0.4443 — more than half the notifications never arrive — and its outbound calls rise to 220,661, that is, 1.90 times normal, because attempts that go to waste use up the whole budget. The cascading arrangement stays at 0.9991, and its outbound calls rise to 166,806. This is where the circuit breaker per channel earns its keep: once the push channel's circuit trips, the sequence starts directly from the second channel, and the 54,449 wasted calls the failure would have added (166,806 minus 112,357) never happen. What is sacrificed is in one sentence: the cascading order buys its delivery rate with delay — a recipient whose first channel hits a permanent failure gets the notification 30 seconds late, and 60 seconds late if the second one fails too. #### Summary - Channel failure cannot be designed for without splitting it in two: transient failure is erased in three attempts (0.05 to the third power), permanent failure never shrinks on the same channel, and it makes up nearly all of the remaining error. - The single-channel arrangement gives a delivery rate of 0.9599 calculated, 0.9590 measured; that is 3.01 points below the 0.99 threshold, and 1,202,129 notifications a day do not arrive. - Cascading order gives 0.9999 with the same three-call budget, and does it with fewer outbound calls: 1.079 calls per notification, against single channel's 1.117 calls. - When failure rates triple, single channel drops to 0.8790, cascading stays at 0.9979; diversity's gain climbs from 4.09 points to 11.89 points. - Parallel fan-out gives the same delivery rate but produces 2.78 times the outbound calls and 1.83 extra deliveries per notification; it is eliminated for violating the single-delivery requirement. - When the push channel fails entirely, single channel drops to 0.4443, cascading stays at 0.9991; the cost is the notification arriving 30 or 60 seconds late. #### Next Step In both of these cases the system's job was to satisfy a request, and failure was a bad outcome. The next case designs the reverse: a component whose job is to **reject** the request. The rejection decision is made by looking at a shared counter, and the counter is distributed; two questions follow from this. In what form the counter's window is defined determines how far above the limit it is possible to climb, and how much drift concurrently reading and writing nodes produce in the counter. Both are countable. ### Rate Limiter Source: https://academia.sh/en/courses/case-studies/rate-limiter Designing the component whose job is to reject the request: the overshoot allowed by fixed window, sliding window counter, and token bucket measured across three request patterns, the doubling crossing at the window boundary counted, the overshoot and false-rejection count the distributed counter produces under centralized, split-quota, and delayed-synchronization arrangements, and the synchronization interval determining the threshold. In the previous two cases, the system's job was to satisfy a request; failure was a bad outcome. This case designs the reverse: a component whose job is to **reject** the request. The location of the rate-limiting decision was addressed in the Traffic Layer course and the Caching, Queues and Asynchronous Processing course; its algorithm was not. What is designed here is the rate limiter component itself. The rejection decision is made by looking at a shared counter, and the counter is distributed. Two questions follow from this: in what form the counter's window is defined lets the count climb above the declared limit, and how much drift concurrently reading and writing nodes produce in the counter. #### Constraints and Scope The functional requirements: counting requests per client, rejecting a request that exceeds the limit, reporting the remaining allowance and wait time in the response, and reading the limit from a rule set. What is not designed: authentication, billing for the quota, abuse detection, and the rule-management interface. The non-functional requirements are written with a threshold and its source: the number of requests a client lets through in any 60-second interval does not exceed 1.1 times the declared limit (source: the limit being a promise made to the client), a client that stays under the limit is never rejected (source: the other side of the same promise), and a request is not rejected when the counter store goes down (source: the limiter itself not being a source of outages). #### Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | HS1 | tracked clients | 200,000 | number of distinct keys the limit applies to | | HS2 | peak requests at the edge | 40,000/s | total request rate passing through the limiter | | HS3 | declared limit per client | 600 requests / 60 s | the right written into the contract | | HS4 | limiter node count | 8 | horizontal scale at the edge | | HS5 | counter synchronization interval | 0.2 seconds | how often nodes refresh the shared view | | HS6 | counter record | 48 bytes | key, count, window timestamp | | HS7 | sliding window slice | 12 (5 seconds each) | granularity the 60 seconds is split into | | HS8 | token bucket capacity | 60 tokens | allowance left for a burst | ```js // rate-limit/scale.mjs — the back-of-envelope calculation drawn from the HS assumption table const HS = { clients: 200_000, peakRequests: 40_000, limit: 600, windowS: 60, nodes: 8, syncS: 0.2, recordBytes: 48, slices: 12 }; // HS1..HS8 const perNode = HS.peakRequests / HS.nodes; console.log(`peak requests/s per node ${perNode}`); console.log(`touches/s if using a centralized counter ${HS.peakRequests}`); console.log(`client limit's per-second equivalent ${HS.limit / HS.windowS}`); console.log(`\n${"counter arrangement".padEnd(25)}${"records per client".padStart(21)}${"total MB".padStart(11)}`); for (const [name, n] of [["fixed window", 1], ["token bucket", 1], ["sliding window counter", HS.slices]]) console.log(`${name.padEnd(25)}${String(n).padStart(21)}` + `${((HS.clients * n * HS.recordBytes) / 1e6).toFixed(2).padStart(11)}`); const blindCeiling = (HS.limit / HS.windowS) * HS.syncS * HS.nodes; console.log(`\nsync ceiling: requests a node misses in ${HS.syncS} s = ` + `${perNode * HS.syncS} (all clients)`); console.log(`blind ceiling for a single client = (limit/s) x sync x nodes = ${blindCeiling} requests`); console.log(`threshold: 1.1 times the limit = ${HS.limit * 1.1}; with the blind ceiling ${HS.limit + blindCeiling} -> ` + `${HS.limit + blindCeiling <= HS.limit * 1.1 ? "passes" : "fails"}`); ``` ``` peak requests/s per node 5000 touches/s if using a centralized counter 40000 client limit's per-second equivalent 10 counter arrangement records per client total MB fixed window 1 9.60 token bucket 1 9.60 sliding window counter 12 115.20 sync ceiling: requests a node misses in 0.2 s = 1000 (all clients) blind ceiling for a single client = (limit/s) x sync x nodes = 16 requests threshold: 1.1 times the limit = 660; with the blind ceiling 616 -> passes ``` These numbers belong to the **calculation** class. Three of them shape the design. First, if a centralized counter is used, the peak edge needs 40,000 touches per second; this makes the limiter itself the busiest write source in the system. Second, the sliding window counter demands 115.20 MB, exactly 12 times the fixed window's 9.60 MB; the granularity is written directly to memory. Third, the blind ceiling is 16 requests: within a 0.2-second synchronization interval, eight nodes can let through at most 16 requests for one client without knowing about each other, which comes to 616 and stays below the 660 threshold. The synchronization interval was chosen by this calculation. #### The Window's Shape Determines the Overshoot The measurement is an in-process model: there is no real clock, network, or store; time is the model's clock and the request list is deterministic. Three patterns are tried: a **uniform** flow at twice the limit's rate, a flow **piled up** on either side of the window boundary, and a flow arriving **right at the limit** but spaced out. What is measured is the highest number accepted requests reach in any 60-second sliding interval. ```js // rate-limit/window.mjs — in-process model of the three window algorithms. There is no real // clock, network, or store: time is the model's clock (ms) and the request list is deterministic. const LIMIT = 600, WINDOW = 60_000, SLICE = 5_000, DURATION = 180_000; // HS3, HS7 const BUCKET = 60, REFILL = LIMIT / (WINDOW / 1000); // HS8 const patterns = { "uniform 2x": () => Array.from({ length: (DURATION / 1000) * 20 }, (_, i) => i * 50), "piled at boundary": () => { const times = []; for (const boundary of [WINDOW, 2 * WINDOW]) for (const [start, n] of [[boundary - SLICE, LIMIT], [boundary, LIMIT]]) for (let i = 0; i < n; i += 1) times.push(start + Math.floor((i * SLICE) / n)); return times.sort((a, b) => a - b); }, "spaced at the limit": () => { const times = []; for (let k = 0; k < DURATION / WINDOW; k += 1) for (let i = 0; i < LIMIT; i += 1) times.push(k * WINDOW + Math.floor((i * SLICE) / LIMIT)); return times; }, }; const ALGORITHM = { "fixed window": () => { let p = -1, n = 0; return (t) => { const k = Math.floor(t / WINDOW); if (k !== p) { p = k; n = 0; } return n < LIMIT && (n += 1, true); }; }, "sliding window counter": () => { const counts = new Map(); return (t) => { const slice = Math.floor(t / SLICE), firstValid = slice - WINDOW / SLICE + 1; for (const k of counts.keys()) if (k < firstValid) counts.delete(k); let total = 0; for (const v of counts.values()) total += v; if (total >= LIMIT) return false; counts.set(slice, (counts.get(slice) ?? 0) + 1); return true; }; }, "token bucket": () => { let tokens = BUCKET, last = 0; return (t) => { tokens = Math.min(BUCKET, tokens + ((t - last) / 1000) * REFILL); last = t; return tokens >= 1 && (tokens -= 1, true); }; }, }; const busiestWindow = (accepted) => { let peak = 0; for (let i = 0, j = 0; i < accepted.length; i += 1) { while (accepted[i] - accepted[j] >= WINDOW) j += 1; peak = Math.max(peak, i - j + 1); } return peak; }; console.log(`model: ${DURATION / 1000} s, limit ${LIMIT}/${WINDOW / 1000} s, bucket ${BUCKET} tokens, refill ${REFILL}/s`); for (const [patternName, generate] of Object.entries(patterns)) { const requests = generate(); console.log(`\npattern "${patternName}": ${requests.length} requests`); console.log(`${"algorithm".padEnd(25)}${"accepted".padStart(11)}${"rejected".padStart(11)}` + `${"busiest 60 s".padStart(15)}${"overshoot".padStart(11)}${"overshoot ratio".padStart(18)}`); for (const [algoName, make] of Object.entries(ALGORITHM)) { const allow = make(), accepted = requests.filter((t) => allow(t)); const peak = busiestWindow(accepted); console.log(`${algoName.padEnd(25)}${String(accepted.length).padStart(11)}${String(requests.length - accepted.length).padStart(11)}` + `${String(peak).padStart(15)}${String(peak - LIMIT).padStart(11)}${`x${(peak / LIMIT).toFixed(3)}`.padStart(18)}`); } } ``` ``` model: 180 s, limit 600/60 s, bucket 60 tokens, refill 10/s pattern "uniform 2x": 3600 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 1800 600 0 x1.000 sliding window counter 1800 1800 600 0 x1.000 token bucket 1859 1741 659 59 x1.098 pattern "piled at boundary": 2400 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 600 1200 600 x2.000 sliding window counter 1200 1200 600 0 x1.000 token bucket 318 2082 159 -441 x0.265 pattern "spaced at the limit": 1800 requests algorithm accepted rejected busiest 60 s overshoot overshoot ratio fixed window 1800 0 600 0 x1.000 sliding window counter 1800 0 600 0 x1.000 token bucket 327 1473 109 -491 x0.182 ``` These numbers belong to the **measurement** class and are deterministic; there is no randomness. The first pattern keeps all three algorithms within the limit, with a single exception: the token bucket at 659, that is, 1.098 times. This 59-request excess is one short of the 60-token bucket capacity that HS8 chooses. Compared against the 1.1x threshold, a capacity of 60 turns out to be the ceiling; raised to 66, the threshold would be crossed. The second pattern turns the fixed window's known flaw into a number: requests piled on either side of the window boundary fall into two separate counters, and 1200 requests get through in a sliding 60-second interval — exactly double. In a system whose limit is declared as 600, a client can let 1200 requests through. The sliding window counter stays at 600 on the same pattern. The third pattern shows the token bucket's cost. The client sits right at the limit, sending 600 requests per window and never exceeding any limit; the sliding window counter lets all of them through, and the token bucket rejects 1473 of the 1800 requests. The bucket does not bank idle time; a client that runs intermittently cannot use its full allowance. The second non-functional requirement is violated by this row, and so the algorithm chosen is the **sliding window counter**. #### The Distributed Counter's Drift The chosen algorithm works correctly on a single node. When eight nodes count the same client, the question changes. Three arrangements are compared: the **centralized** arrangement, where every request touches a shared counter; **split quota**, where the limit is divided by the node count; and **delayed synchronization**, where nodes count locally and synchronize at an interval. ```js // rate-limit/distributed.mjs — in-process model of the distributed counter. There is no real // node, network, or store: node assignment uses a seeded generator, synchronization uses the model clock. const LIMIT = 600, WINDOW = 60, NODES = 8; // HS3, HS4 function generator(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } export function run({ arrangement, rate, interval = 0.2, seed }) { const rnd = generator(seed); const n = rate * WINDOW; const local = new Array(NODES).fill(0); let global = 0, lastGlobal = 0, lastSync = 0, accepted = 0, rejected = 0, touches = 0; for (let i = 0; i < n; i += 1) { const t = (i / rate), node = Math.floor(rnd() * NODES); if (arrangement === "delayed synchronization" && t - lastSync >= interval) { lastGlobal = global; lastSync = t; for (let j = 0; j < NODES; j += 1) local[j] = 0; } let allow; if (arrangement === "centralized") { touches += 1; allow = global < LIMIT; } else if (arrangement === "split quota") allow = local[node] < LIMIT / NODES; else allow = lastGlobal + local[node] < LIMIT; if (allow) { accepted += 1; global += 1; local[node] += 1; } else rejected += 1; } if (arrangement === "delayed synchronization") touches = NODES * Math.floor(WINDOW / interval); return { requests: n, accepted, rejected, touches, overshoot: Math.max(0, accepted - LIMIT) }; } const ARRANGEMENT = ["centralized", "split quota", "delayed synchronization"]; for (const rate of [10, 90]) { console.log(`\nclient rate ${rate}/s -> ${rate * WINDOW} requests, limit ${LIMIT}, ${NODES} nodes, seed 20260730`); console.log(`${"arrangement".padEnd(26)}${"accepted".padStart(11)}${"rejected".padStart(11)}${"overshoot".padStart(12)}` + `${"false rejects".padStart(16)}${"counter touches".padStart(18)}`); for (const a of ARRANGEMENT) { const r = run({ arrangement: a, rate, seed: 20260730 }); const falseRejects = rate * WINDOW <= LIMIT ? r.rejected : 0; console.log(`${a.padEnd(26)}${String(r.accepted).padStart(11)}${String(r.rejected).padStart(11)}` + `${String(r.overshoot).padStart(12)}${String(falseRejects).padStart(16)}${String(r.touches).padStart(18)}`); } } console.log(`\ndelayed synchronization, client rate 90/s (burst)`); console.log(`${"sync interval".padEnd(18)}${"accepted".padStart(11)}${"overshoot".padStart(12)}` + `${"overshoot ratio".padStart(18)}${"touches/s".padStart(12)}${"threshold 660".padStart(16)}`); for (const a of [0.2, 1, 2, 5]) { const r = run({ arrangement: "delayed synchronization", rate: 90, interval: a, seed: 20260730 }); console.log(`${`${a} s`.padEnd(18)}${String(r.accepted).padStart(11)}${String(r.overshoot).padStart(12)}` + `${`x${(r.accepted / LIMIT).toFixed(3)}`.padStart(18)}${(r.touches / WINDOW).toFixed(1).padStart(12)}` + `${(r.accepted <= LIMIT * 1.1 ? "passes" : "fails").padStart(16)}`); } ``` ``` client rate 10/s -> 600 requests, limit 600, 8 nodes, seed 20260730 arrangement accepted rejected overshoot false rejects counter touches centralized 600 0 0 0 600 split quota 575 25 0 25 0 delayed synchronization 600 0 0 0 2400 client rate 90/s -> 5400 requests, limit 600, 8 nodes, seed 20260730 arrangement accepted rejected overshoot false rejects counter touches centralized 600 4800 0 0 5400 split quota 600 4800 0 0 0 delayed synchronization 609 4791 9 0 2400 delayed synchronization, client rate 90/s (burst) sync interval accepted overshoot overshoot ratio touches/s threshold 660 0.2 s 609 9 x1.015 40.0 passes 1 s 630 30 x1.050 8.0 passes 2 s 720 120 x1.200 4.0 fails 5 s 900 300 x1.500 1.6 fails ``` The first table eliminates split quota. The client sits right at its limit, sending 600 requests and never exceeding it; even so, 25 of its requests are rejected — 4.17%. The reason is distribution imbalance: requests do not split evenly across the eight nodes, and a node that fills its share rejects while unused quota sits idle on other nodes. Splitting the quota does not split the limit — it splits the **right**. The second table prices out the centralized counter. Its overshoot is zero, that much is true; its cost is 40,000 counter touches per second at the peak edge, and even in this single-client model, its 5400 touches are more than double delayed synchronization's 2400. Delayed synchronization accepts 609, with an overshoot of 9. The third table chooses the parameter. As the synchronization interval grows, the overshoot grows: 1.015x at 0.2 seconds, 1.050x at 1 second, 1.200x at 2 seconds. Since the threshold is 1.1x, 1 second passes and 2 seconds does not. Counter touches shrink in the opposite direction: from 40 per second to 4. HS5's choice of 0.2 seconds is the intersection of these two curves, and if the threshold were tightened to 1.05x, the interval would be forced to stay at 0.2 seconds. #### Design, Failure Behavior, and What Is Sacrificed The decision point is the gateway: the portability rule from the Traffic Layer course's Gateway Offloading lesson applies here, because the client ID is a metadata field and the decision does not read the domain's input. The counter is held in the key–value store from the Scaling the Data Layer course's Store Types lesson; the key is the `(client, slice)` pair, the record is 48 bytes, and the time-to-live is 60 seconds. The component itself is the **throttling** from the Resilience and Reliability course's Throttling and Load Shedding lesson: it cuts off above a known rate and does not look at instantaneous capacity. **Deliberately unused pattern.** Queue-based load leveling (Application Layer and Service Interaction) is not used: queuing the excess request and processing it later turns the limit into a delay, whereas the component's contract is to reject. The failure scenario is the counter store going down. Per the third threshold, the limiter stays open: nodes decide using the last known shared view and only their own local counter. This approaches split quota's behavior, and during the outage, overshoot per client can climb as high as eightfold. What is sacrificed is in one sentence: this design does not zero out overshoot — it buys keeping it at 1.015x with 40 counter touches instead of 40,000. #### Summary - Fixed window let 1200 requests through in a sliding 60-second interval on a request pattern piled at the window boundary: exactly double the declared limit. - Token bucket let 659 through on the uniform flow (1.098x, exactly the bucket's capacity), but rejected 1473 of the 1800 requests from a client running intermittently right at the limit. - Sliding window counter stayed at 600 on all three patterns and rejected no valid request; its cost is 12 times the memory, 115.20 MB instead of 9.60 MB. - Split quota rejected 25 requests (4.17%) from a client sitting right at its limit because of distribution imbalance; splitting the quota splits the right. - The centralized counter's overshoot is zero, but it demands 40,000 touches per second at the peak edge; delayed synchronization gives a 1.015x overshoot at a 0.2-second interval with 40 touches per second. - The synchronization interval determines the threshold: 1.050x at 1 second (passes), 1.200x at 2 seconds (fails). #### Next Step In this case, the counter was guarding a threshold, and what was lost when the threshold was crossed was a request; the client resends. The next case asks the same counting problem where what is counted is **not recoverable**. There is a limited number of seats or stock items; a counter that counts two too many does not produce a rejected request — it produces an item sold that does not exist. The number to measure then is the oversell produced under contention, and a second number stands beside it: the valid request the same guard rejects. ### Ticketing and Inventory System Source: https://academia.sh/en/courses/case-studies/ticketing-and-inventory-system The case where the counted thing cannot be recovered: the allotment exhausting in 0.179 seconds at peak rate, the unprotected read–decide–write flow overselling the allotment by 5.59x under 16 concurrent workers, optimistic and pessimistic locking measured in oversold items versus rejected valid requests, and the reservation window's effect on wasted item-seconds. In the previous case, a counter guarded a threshold, and what was lost when the threshold was exceeded was a request — the client retries. This case poses the same counting problem where the counted thing is **unrecoverable**. There is a limited number of seats, and when the counter overcounts by two, the cost is not a rejected request but an item sold that does not exist. Two differences follow from this. First, the unit of overshoot changes: in the rate limiter, 1.1x was acceptable; here, not even a single unit has an equivalent. Second, holding a resource and selling it are separate operations, and there is a window between them. #### Constraints and Scope Functional requirements: reporting the remaining allotment, opening a reservation, converting a reservation into a sale, releasing an expired reservation, and processing a cancellation. Out of scope: payment execution (the subject of the next case), rendering the seat map, pricing, and resale. The non-functional requirements are written with a threshold and its source: **oversold items are zero** (source: the obligation that every sold item has a match), **valid requests rejected while stock remains are zero** (source: a buyer must not leave empty-handed before the allotment runs out), and the reservation decision does not exceed 100 milliseconds (source: the page must not go unresponsive at the moment of launch). #### Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | BS1 | allotment | 5,000 items | the limited resource opened for a single sale | | BS2 | requests at launch | 200,000 / 10 seconds | demand piling up at the moment of launch | | BS3 | items per request | 1.4 | the average of single- and double-item purchases | | BS4 | reservation window | 120 seconds | time left for the payment step | | BS5 | completion rate by window | 0.45 / 0.65 / 0.72 | share of payments completed within a 30-, 120-, and 300-second window | | BS6 | concurrent write worker | 16 | number of jobs touching the allotment row at once | | BS7 | stock record | 64 bytes | item ID, status, reservation timestamp | | BS8 | retry budget under optimistic conflict | 3 | upper bound on retries | ```js // ticketing/measure.mjs — rough sizing derived from the BS assumption table const BS = { allotment: 5_000, launchRequests: 200_000, launchSeconds: 10, items: 1.4, window: 120, completion: { 30: 0.45, 120: 0.65, 300: 0.72 }, workers: 16, recordBytes: 64 }; const peak = BS.launchRequests / BS.launchSeconds; const demand = BS.launchRequests * BS.items; const drain = BS.allotment / (peak * BS.items); console.log(`peak requests/s ${peak}`); console.log(`total demand at launch ${demand} items`); console.log(`demand / allotment ${(demand / BS.allotment).toFixed(1)}x`); console.log(`allotment drain time ${drain.toFixed(3)} s (at peak rate)`); console.log(`requests arriving by drain ${Math.round(peak * drain)}`); console.log(`stock table ${((BS.allotment * BS.recordBytes) / 1e3).toFixed(1)} KB`); console.log(`reservation count ${(BS.allotment / BS.items).toFixed(0)} (allotment / items)`); console.log(`\n${"window".padStart(9)}${"completion rate".padStart(17)}${"sold in round one".padStart(20)}` + `${"items returned".padStart(17)}${"wasted item-seconds".padStart(22)}`); for (const [w, c] of Object.entries(BS.completion)) { const back = BS.allotment * (1 - c); console.log(`${`${w} s`.padStart(9)}${c.toFixed(2).padStart(17)}${(BS.allotment * c).toFixed(0).padStart(20)}` + `${back.toFixed(0).padStart(17)}${(back * Number(w)).toFixed(0).padStart(22)}`); } const c120 = BS.completion[BS.window], c30 = BS.completion[30]; console.log(`\nwindow 30 s -> 120 s: sold in round one ${(BS.allotment * c30).toFixed(0)} -> ` + `${(BS.allotment * c120).toFixed(0)} (+${((c120 - c30) * BS.allotment).toFixed(0)} items)`); console.log(`the same change moves wasted item-seconds ${(BS.allotment * (1 - c30) * 30).toFixed(0)} -> ` + `${(BS.allotment * (1 - c120) * BS.window).toFixed(0)} (` + `${((BS.allotment * (1 - c120) * BS.window) / (BS.allotment * (1 - c30) * 30)).toFixed(2)}x)`); ``` ``` peak requests/s 20000 total demand at launch 280000 items demand / allotment 56.0x allotment drain time 0.179 s (at peak rate) requests arriving by drain 3571 stock table 320.0 KB reservation count 3571 (allotment / items) window completion rate sold in round one items returned wasted item-seconds 30 s 0.45 2250 2750 82500 120 s 0.65 3250 1750 210000 300 s 0.72 3600 1400 420000 window 30 s -> 120 s: sold in round one 2250 -> 3250 (+1000 items) the same change moves wasted item-seconds 82500 -> 210000 (2.55x) ``` These numbers are of the **computed** class. Three of them determine the design. First, demand is 56x the allotment, and the allotment drains at peak rate in **0.179 seconds**; the problem the design solves is not capacity but counting correctly within a 0.179-second interval. Second, only 3,571 requests arrive within that interval; the job for the remaining 196,429 requests is to be rejected, and that job must happen without ever touching the allotment row. Third, the reservation window carries a cost in both directions: raising it from 30 seconds to 120 seconds increases the items sold in round one by 1,000 but raises wasted item-seconds by 2.55x. #### Oversell Is Measured The measurement is an in-process model: there is no real thread, database, or lock; 16 workers are advanced step by step by a seeded scheduler, and contention arises from other workers stepping in between one worker's read and its write. Three regimes are compared: the **unprotected** read–decide–write flow, **optimistic** locking that checks a version column, and **pessimistic** locking that makes the decision under a lock. The mechanics were built in the Data Access Layer and Business Logic course's Optimistic and Pessimistic Locking lesson; what is measured here is the number of oversold items in this case. ```js // ticketing/contention.mjs — an in-process model of contention over a limited resource. There // is no real thread, database, or lock: 16 workers are advanced step by step by a scheduler. const ALLOTMENT = 5_000, REQUESTS = 20_000, RETRY_BUDGET = 3; // BS1, BS8 function rng(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } export function run({ regime, seed, WORKERS = 16 }) { // BS6: concurrent write workers const rnd = rng(seed); const shared = { stock: ALLOTMENT, version: 0, locked: false }; const queue = Array.from({ length: REQUESTS }, () => (rnd() < 0.6 ? 1 : 2)); // BS3: average 1.4 const workers = Array.from({ length: WORKERS }, () => ({ phase: "idle" })); const s = { sold: 0, rejected: 0, validRejected: 0, conflict: 0, wait: 0, step: 0 }; let cursor = 0; while (cursor < REQUESTS || workers.some((w) => w.phase !== "idle")) { const w = workers[Math.floor(rnd() * WORKERS)]; s.step += 1; if (w.phase === "idle") { if (cursor >= REQUESTS) continue; w.qty = queue[cursor]; cursor += 1; w.attempt = 0; w.phase = "read"; } if (w.phase === "read") { if (regime === "pessimistic") { if (shared.locked) { s.wait += 1; continue; } shared.locked = true; } w.readStock = shared.stock; w.readVersion = shared.version; w.phase = "write"; continue; } if (w.readStock < w.qty) { // the stock read is not enough s.rejected += 1; if (shared.stock >= w.qty) s.validRejected += 1; if (regime === "pessimistic") shared.locked = false; w.phase = "idle"; continue; } if (regime === "optimistic" && shared.version !== w.readVersion) { // version changed s.conflict += 1; w.attempt += 1; if (w.attempt >= RETRY_BUDGET) { s.rejected += 1; if (shared.stock >= w.qty) s.validRejected += 1; w.phase = "idle"; } else w.phase = "read"; continue; } shared.stock = w.readStock - w.qty; shared.version += 1; s.sold += w.qty; if (regime === "pessimistic") shared.locked = false; w.phase = "idle"; } s.oversold = Math.max(0, s.sold - ALLOTMENT); s.stockRemaining = shared.stock; return s; } console.log(`model: allotment ${ALLOTMENT}, 16 workers, ${REQUESTS} requests, retry budget ${RETRY_BUDGET}, seed 20260730`); console.log(`\n${"regime".padEnd(12)}${"sold".padStart(9)}${"oversold".padStart(13)}` + `${"stock left".padStart(12)}${"conflict".padStart(9)}${"rejected (valid)".padStart(18)}` + `${"wait steps".padStart(15)}${"total steps".padStart(13)}`); const R = {}; for (const d of ["unprotected", "optimistic", "pessimistic"]) { const r = (R[d] = run({ regime: d, seed: 20260730 })); console.log(`${d.padEnd(12)}${String(r.sold).padStart(9)}${String(r.oversold).padStart(13)}` + `${String(r.stockRemaining).padStart(12)}${String(r.conflict).padStart(9)}` + `${`${r.rejected} (${r.validRejected})`.padStart(18)}${String(r.wait).padStart(15)}${String(r.step).padStart(13)}`); } const k = R.unprotected, i = R.optimistic, p = R.pessimistic; console.log(`\nunprotected regime sold ${(k.sold / ALLOTMENT).toFixed(3)}x the allotment; ` + `oversold / allotment = ${((100 * k.oversold) / ALLOTMENT).toFixed(2)}%`); console.log(`optimistic: oversold ${i.oversold}, ${i.conflict} conflicts, ` + `${i.validRejected} valid requests rejected once the retry budget ran out`); console.log(`pessimistic: oversold ${p.oversold}, valid rejections ${p.validRejected}, ` + `step count ${(p.step / i.step).toFixed(2)}x the optimistic count`); console.log(`\n${"concurrent workers".padStart(19)}${"optimistic conflict".padStart(21)}${"valid rejected".padStart(16)}` + `${"pessimistic wait".padStart(18)}`); for (const n of [2, 4, 16]) { const a = run({ regime: "optimistic", seed: 20260730, WORKERS: n }); const b = run({ regime: "pessimistic", seed: 20260730, WORKERS: n }); console.log(`${String(n).padStart(19)}${String(a.conflict).padStart(21)}${String(a.validRejected).padStart(16)}` + `${String(b.wait).padStart(18)}`); } ``` ``` model: allotment 5000, 16 workers, 20000 requests, retry budget 3, seed 20260730 regime sold oversold stock left conflict rejected (valid) wait steps total steps unprotected 27963 22963 1798 0 0 (0) 0 40047 optimistic 5000 0 0 10038 16397 (2409) 0 55267 pessimistic 5000 0 0 0 16427 (0) 304276 344446 unprotected regime sold 5.593x the allotment; oversold / allotment = 459.26% optimistic: oversold 0, 10038 conflicts, 2409 valid requests rejected once the retry budget ran out pessimistic: oversold 0, valid rejections 0, step count 6.23x the optimistic count concurrent workers optimistic conflict valid rejected pessimistic wait 2 1519 130 20043 4 3577 520 60109 16 10038 2409 304276 ``` This is of the **measured** class; it reproduces with seed 20260730. The first row is the measurement of the unprotected regime, and it carries two numbers. 5.593x the allotment was sold, and oversold items came to 22,963. The second number is more instructive: **stock remaining shows 1,798.** The counter is not merely wrong, it is wrong in the wrong direction — the system still reports room to sell. No request was rejected, because no worker ever saw the stock as insufficient; lost writes pushed the counter back up. The second and third rows show that both protections zero out overselling. The difference is in the other columns. Optimistic locking produces 10,038 conflicts and rejects **2,409 valid requests** once the retry budget runs out: a buyer who leaves empty-handed while stock remains. This is a violation of the second non-functional requirement. Pessimistic locking produces no valid rejections, at the cost of 304,276 wait steps and 6.23x the optimistic regime's total step count. The fourth table shows that both costs depend on the same variable: the number of concurrent workers. At 2 workers, optimistic locking's valid rejections drop to 130, and pessimistic locking's wait steps drop to 20,043. Contention is not a constant, it is a design parameter. #### Design and the Eliminated Alternative The allotment row is protected with a **pessimistic lock**; the reason for the choice is 2,409 against 0 valid rejections. The lock's hold time is given as a lease, and the lease mechanics from the Application Layer and Service Interaction course's Leader Election lesson are applied here to lock ownership; a stuck lock drops once the lease expires. The reservation window is 120 seconds, and the supervisor that releases an expired reservation is the supervisor from the same course's Scheduler–Agent–Supervisor lesson. To keep the 20,000 requests/s at launch from reaching the allotment row, two layers stand in front: the previous case's rate limiter and the queue from the same course's Queue-Based Load Leveling lesson. In the previous case, the queue was **deliberately not used**, because the contract there was to reject; here the contract is to enqueue, and the same pattern changes place for that reason. The idempotency key's scope is the triple `(buyer, allotment, client request ID)`; a buyer's retry does not open a second reservation. **Pattern deliberately not used.** Splitting the allotment counter into shards (Scaling the Data Layer, Sharding) is not used: this is the same thing as the split quota measured in the previous case, and it produces rejections while items remain in another shard — there, it rejected 4.17 percent of a client running right at the limit. The eliminated alternative is optimistic locking, and the number that eliminates it is 2,409 valid rejections. What it wins is written down too: 6.23x fewer steps, that is, a write path that holds no lock. What it would take to change the verdict is also clear: with 2 concurrent workers instead of 16, valid rejections would drop to 130, or 2.6 percent of the allotment, and raising the retry budget from 3 to 6 could lower that further. #### Failure Behavior and What Is Sacrificed If the worker holding the lock fails, the allotment row stays locked for the lease duration and no sale can happen during that time; if the lease is longer than the 0.179-second drain window, the entire launch stalls. On the queue side, the Resilience and Reliability course's Graceful Degradation lesson governs: once the allotment is exhausted, requests are rejected without ever touching the allotment row, and that is the normal path for the 196,429 requests. What is sacrificed fits in one sentence: this design sacrifices throughput to zero out overselling — 304,276 wait steps and 6.23x the processing are the price paid so that not even a single item is sold in excess. #### Summary - Demand is 56x the allotment and it drains at peak rate in 0.179 seconds; only 3,571 requests arrive within that interval, and the job for the remaining 196,429 requests is to be rejected. - The unprotected regime sold 5.593x the allotment, oversold by 22,963; and worse, the counter ends up showing 1,798 units of stock remaining — wrong in the wrong direction. - Optimistic locking zeroed out overselling but produced 10,038 conflicts and rejected 2,409 valid requests once the retry budget ran out. - Pessimistic locking zeroed out both overselling and valid rejections; the price is 304,276 wait steps and 6.23x the optimistic regime's total steps. - Both costs depend on the number of concurrent workers: at 2 workers instead of 16, valid rejections drop from 2,409 to 130, and wait steps drop from 304,276 to 20,043. - Raising the reservation window from 30 seconds to 120 seconds increases items sold in round one by 1,000 but raises wasted item-seconds by 2.55x. #### Next Step The reservation made a promise, but the step that keeps it was left out of this case: the payment itself. That step is a transaction with two sides, and neither side can see the other's records. The next case takes up that split. The number to ask is how far the two records diverge from each other: the number of unmatched records, where the gap comes from, and how long it takes a late-arriving confirmation to close it. ### Payment Flow Source: https://academia.sh/en/courses/case-studies/payment-flow The case where the two sides' records diverge: splitting the number of unmatched records in a reconciliation cycle by source, polling bringing the gap down from 59.74 per mille to 9.76 per mille, late-arriving confirmations making up most of the remaining gap, the cycle interval lowering the gap rate while lengthening the closure time, and the audit trail's seven-year volume. In the previous case, the reservation made a promise, and the step that keeps it was left out of scope: the payment itself. That step has two sides; each side keeps its own record, neither can see the other's ledger, and message exchange is the only link between them. Idempotence and the idempotency key were built in the Resilience and Reliability course's Idempotent Operations lesson and are not repeated here; a resent request never opens a second transaction. This lesson asks something else: how far the two ledgers **diverge** when messages are lost or late, how that gap is counted, and when it closes. #### Constraints and Scope Functional requirements: initiating a payment, processing the status notification from the other party, querying the status, initiating a refund, and writing every status transition to the audit trail. Out of scope: the authentication flow, fraud scoring, closing the accounting ledger, and the refund rules themselves. The non-functional requirements are written with a threshold and its source: a transaction's status on both sides matches within **30 minutes** at the latest (source: how long a gap may close on its own before manual review), the unmatched-record rate per reconciliation cycle does not exceed **10 per mille** (source: how many records one cycle can review by hand), and every status transition appears in the audit trail and the record never changes afterward (source: a transaction's history must be reconstructible). #### Assumptions and Scale | Code | Assumption | Value | Rationale | |---|---|---|---| | OD1 | daily payment transactions | 1,200,000 | the sum of completed and rejected attempts | | OD2 | peak multiplier | 4 | the ratio of evening-hour volume to the daily average | | OD3 | notification delay | 0.92 / 0.06 / 0.02 | shares of notifications arriving within five seconds, within five minutes, and later | | OD4 | notification loss | 0.03 | the other party's notification never arriving at all | | OD5 | poll interval | 60 seconds | how often a pending transaction is queried | | OD6 | reconciliation cycle | 900 seconds | how often the two ledgers are compared | | OD7 | audit trail | 5 transitions × 260 bytes | number of status transitions per transaction and record length | | OD8 | retention period | 2,555 days | disputes can be reopened as far back as seven years | | OD9 | settlement on the other side | 0.90 / 0.08 / 0.02 | shares of transactions settling in 3, 3–60, and 60–900 seconds; the other party's own approval steps produce a queue | | OD10 | synchronous-verification budget | 20 seconds | the upper bound on how long a request can be kept open while waiting for a reply | ```js // payment/measure.mjs — rough sizing derived from the OD assumption table const OD = { dailyTransactions: 1_200_000, peakMultiplier: 4, notificationLoss: 0.03, poll: 60, cycle: 900, auditRecordBytes: 260, transitionCount: 5, retentionDays: 2555 }; // OD1..OD8 const DAY = 86_400; const peak = (OD.dailyTransactions / DAY) * OD.peakMultiplier; const auditDaily = OD.dailyTransactions * OD.transitionCount * OD.auditRecordBytes; console.log(`peak transactions/s ${peak.toFixed(2)}`); console.log(`records compared per cycle ${Math.round(peak * OD.cycle)}`); console.log(`notifications lost per day ${OD.dailyTransactions * OD.notificationLoss}`); console.log(`records/s the poll will find ${(peak * OD.notificationLoss).toFixed(2)}`); console.log(`audit trail, daily GB ${(auditDaily / 1e9).toFixed(2)}`); console.log(`audit trail, ${OD.retentionDays} days, TB ${((auditDaily * OD.retentionDays) / 1e12).toFixed(2)}`); console.log(`audit rows / transaction ratio ${OD.transitionCount} (one row per transition)`); console.log(`\n${"reconciliation cycle".padStart(21)}${"records at peak batch".padStart(23)}` + `${"cycles per day".padStart(17)}`); for (const c of [300, OD.cycle, 3600]) console.log(`${`${c / 60} min`.padStart(21)}${Math.round(peak * c).toString().padStart(23)}` + `${(DAY / c).toFixed(0).padStart(17)}`); console.log(`\ndaily records compared is independent of the cycle: ${OD.dailyTransactions} ` + `(each record once); the cycle only changes the batch size and the time to find the difference`); ``` ``` peak transactions/s 55.56 records compared per cycle 50000 notifications lost per day 36000 records/s the poll will find 1.67 audit trail, daily GB 1.56 audit trail, 2555 days, TB 3.99 audit rows / transaction ratio 5 (one row per transition) reconciliation cycle records at peak batch cycles per day 5 min 16667 288 15 min 50000 96 60 min 200000 24 daily records compared is independent of the cycle: 1200000 (each record once); the cycle only changes the batch size and the time to find the difference ``` These numbers are of the **computed** class; OD9 and OD10 feed only the eliminated alternative's model. Three of them shape the design. First, the peak rate is 55.56 transactions per second — none of this case's decisions turn on volume. Second, 36,000 notifications never arrive each day, and finding them costs 1.67 queries per second, a small load, but without it those records diverge. Third, the audit trail is the real volume item: 1.56 GB daily, 3.99 TB over seven years, five rows per transaction. #### Measuring the Gap The measurement is an in-process model: there is no real counterparty, network, or store; delay and loss are parameters, and time is the model's own clock. The model generates one cycle's transactions and, for each, computes when it settles on the other side and when the local side learns of it, then compares the two states at cycle end. The gap splits into three sources: lost notifications, late notifications, and transactions not yet settled on the other side — the last is not a gap, both sides say the same thing. ```js // payment/reconciliation.mjs — an in-process model of the gap between the two sides' records. // There is no real counterparty, network, or store: delay and loss are parameters, and time is // the model's own clock (seconds). const PEAK = 55.56, POLL = 60, LOSS = 0.03; // computed; OD5, OD4 const SETTLE_TIME = 3; // time for the transaction to finish on the other side (s) function rng(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } // OD3: notification delay in three tiers — 92% fast, 6% delayed, 2% late const delay = (r) => (r < 0.92 ? 5 * (r / 0.92) : r < 0.98 ? 5 + 295 * ((r - 0.92) / 0.06) : 300 + 1500 * ((r - 0.98) / 0.02)); export function run({ cycle, polling, seed }) { const rnd = rng(seed); const n = Math.round(PEAK * cycle); const s = { transactions: n, lateArrived: 0, lost: 0, unsettled: 0 }; for (let i = 0; i < n; i += 1) { const start = (i / PEAK), finish = start + SETTLE_TIME; const isLost = rnd() < LOSS, d = delay(rnd()); const notifiedAt = isLost ? Infinity : finish + d; const pollAt = polling ? Math.ceil(finish / POLL) * POLL : Infinity; const knownAt = Math.min(notifiedAt, pollAt); if (finish >= cycle) { s.unsettled += 1; continue; } // not finished on the other side either if (knownAt < cycle) continue; // both sides know if (isLost) s.lost += 1; else s.lateArrived += 1; } s.unmatched = s.lateArrived + s.lost; s.perMille = (1000 * s.unmatched) / s.transactions; return s; } const printRow = (label, r) => console.log(`${label.padEnd(26)}${String(r.transactions).padStart(9)}${String(r.unmatched).padStart(12)}` + `${String(r.lateArrived).padStart(14)}${String(r.lost).padStart(10)}` + `${String(r.unsettled).padStart(15)}${r.perMille.toFixed(2).padStart(11)}`); console.log(`model: peak ${PEAK} transactions/s, notification loss ${LOSS}, poll ${POLL} s, seed 20260730`); console.log(`\n${"regime (900 s cycle)".padEnd(26)}${"txns".padStart(9)}${"unmatched".padStart(12)}` + `${"late arrived".padStart(14)}${"lost".padStart(10)}${"unsettled".padStart(15)}${"per mille".padStart(11)}`); printRow("notification only", run({ cycle: 900, polling: false, seed: 20260730 })); printRow("notification + poll", run({ cycle: 900, polling: true, seed: 20260730 })); console.log(`\n${"reconciliation cycle".padStart(21)}${"txns".padStart(9)}${"unmatched".padStart(12)}` + `${"per mille".padStart(11)}${"10 per mille limit".padStart(21)}${"closure min".padStart(13)}${"30 min limit".padStart(14)}`); for (const c of [300, 900, 3600]) { const r = run({ cycle: c, polling: true, seed: 20260730 }); console.log(`${`${c / 60} min`.padStart(21)}${String(r.transactions).padStart(9)}${String(r.unmatched).padStart(12)}` + `${r.perMille.toFixed(2).padStart(11)}${(r.perMille <= 10 ? "passes" : "fails").padStart(21)}` + `${String((2 * c) / 60).padStart(13)}${((2 * c) / 60 <= 30 ? "passes" : "fails").padStart(14)}`); } const a = run({ cycle: 900, polling: false, seed: 20260730 }); const b = run({ cycle: 900, polling: true, seed: 20260730 }); const c60 = run({ cycle: 3600, polling: true, seed: 20260730 }); console.log(`\nthe gap that polling closes: ${a.unmatched} -> ${b.unmatched} records ` + `(per mille ${a.perMille.toFixed(2)} -> ${b.perMille.toFixed(2)})`); console.log(`${b.lateArrived}/${b.unmatched} of the remaining gap is late-arriving confirmations`); console.log(`cycle 15 min -> 60 min: unmatched count ${b.unmatched} -> ${c60.unmatched} (nearly the same), ` + `per mille ${b.perMille.toFixed(2)} -> ${c60.perMille.toFixed(2)}`); ``` ``` model: peak 55.56 transactions/s, notification loss 0.03, poll 60 s, seed 20260730 regime (900 s cycle) txns unmatched late arrived lost unsettled per mille notification only 50004 2987 1437 1550 166 59.74 notification + poll 50004 488 369 119 166 9.76 reconciliation cycle txns unmatched per mille 10 per mille limit closure min 30 min limit 5 min 16668 488 29.28 fails 10 passes 15 min 50004 488 9.76 passes 30 passes 60 min 200016 482 2.41 passes 120 fails the gap that polling closes: 2987 -> 488 records (per mille 59.74 -> 9.76) 369/488 of the remaining gap is late-arriving confirmations cycle 15 min -> 60 min: unmatched count 488 -> 482 (nearly the same), per mille 9.76 -> 2.41 ``` These numbers are of the **measured** class; they reproduce with seed 20260730. The first table separates out polling's contribution. In the notification-only regime, 2,987 records per cycle do not match, 59.74 per mille; since the threshold is 10 per mille, this regime fails on its own. Adding polling drops the gap to 488, 9.76 per mille: lost notifications fall from 1,550 to 119, since the query finds them within 60 seconds at the latest. Of the remaining 488 records, 369 are **late-arriving confirmations**, and polling cannot close this gap: the other side has finished the work but has not yet sent the notification, so the poll also gets a "pending" reply. This is not a defect but a genuine interval between the two sides' clocks; reconciliation's job is to **count** it and wait for closure. The second table selects the cycle interval; the most instructive row is the count itself: unmatched records are 488 at 5 minutes, 488 at 15, and 482 at 60 — practically unchanged. The gap is a boundary event, determined not by the cycle's length but by the number of transactions **at its edge**; lengthening the cycle does not resolve it, only dilutes the rate from 29.28 per mille to 2.41 per mille. Closure time runs two cycle lengths: 10, 30, and 120 minutes. The two thresholds press from opposite directions, and only 15 minutes clears both. #### Design **Status notification and polling.** The other party's notification is the structure from the Application Layer and Service Interaction course's Asynchronous Request–Reply lesson; polling, meanwhile, is a pattern **eliminated** in this topic's first case, there for producing 140.63x the requests as a primary delivery path. Here it only queries what is pending, so its peak load is 1.67 queries per second — the same pattern, a different role, a different parameter. **Audit trail.** The append-only log from the Scaling the Data Layer course's Event-Sourced Design lesson is the audit trail here; its parameters are the retention period and the transition count: 5 rows per transaction, 260 bytes, 3.99 TB over seven years. The trail is never overwritten, only appended to; a transaction's current status is a projection derived from it. **What happens once a gap is found.** An unmatched record triggers the step from the Resilience and Reliability course's Compensating Transactions lesson: if the local side says "succeeded" while the other party says "declined," the local effect is rolled back. Compensation is triggered **only by reconciliation**; no request path initiates it on its own. **Pattern deliberately not used.** Payment status is not cached (Scaling the Data Layer, Cache Architecture): a stale status would be shown to the user as final — here, staleness is not a window, it is a defect. #### Eliminated Alternative: Synchronous Verification A design that removes the reconciliation cycle altogether can be argued for: every payment is queried synchronously, the request waits for the reply, and the two ledgers that could diverge never arise. This regime is sensitive not to load but to **settlement time on the other side**: as that time grows, transactions fall into the model's third source above, the bucket that does not count as a gap; in the synchronous regime they turn directly into unanswered requests. The alternative's model therefore gives settlement its own distribution (OD9) and the request a wait budget (OD10); a synchronous reply counts as lossless, so the measurement favors the alternative. ```js // payment/synchronous-verification.mjs — an in-process model of the eliminated alternative. // There is no real counterparty: the settlement time is a parameter, and time is the model's // own clock (seconds). const PEAK = 55.56, CYCLE = 900, N = Math.round(PEAK * CYCLE); // computed; OD6 function rng(seed) { // 32-bit linear congruential generator let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } const settle = (r) => // OD9: 90% 3 s, 8% 3-60 s, 2% 60-900 s (r < 0.9 ? 3 : r < 0.98 ? 3 + 57 * ((r - 0.9) / 0.08) : 60 + 840 * ((r - 0.98) / 0.02)); function run(budget) { // every payment keeps the request open until a reply arrives const rnd = rng(20260730); let unresolved = 0, held = 0; for (let i = 0; i < N; i += 1) { const s = settle(rnd()); held += Math.min(s, budget); if (s > budget) unresolved += 1; // closed unanswered, and no cycle to close it either } return { unresolved, perMille: (1000 * unresolved) / N, avg: held / N }; } console.log(`model: peak ${PEAK} transactions/s, cycle ${CYCLE} s, ${N} transactions, seed 20260730`); for (const b of [20, 60, 540]) { const r = run(b); console.log(`budget ${b} s: unresolved ${r.unresolved} (per mille ${r.perMille.toFixed(2)}, limit ` + `${r.perMille <= 10 ? "passes" : "fails"}), average hold ${r.avg.toFixed(2)} s, ` + `open requests at peak ${(PEAK * r.avg).toFixed(1)}`); } ``` ``` model: peak 55.56 transactions/s, cycle 900 s, 50004 transactions, seed 20260730 budget 20 s: unresolved 3789 (per mille 75.77, limit fails), average hold 4.48 s, open requests at peak 249.1 budget 60 s: unresolved 995 (per mille 19.90, limit fails), average hold 6.38 s, open requests at peak 354.4 budget 540 s: unresolved 421 (per mille 8.42, limit passes), average hold 13.06 s, open requests at peak 725.7 ``` These numbers are of the **measured** class; they reproduce with seed 20260730. The number that eliminates the alternative is **75.77 per mille**: at a 20-second budget, 3,789 transactions per cycle close unanswered — 7.6x the threshold — with no cycle to close them; closure time is undefined, not 30 minutes. Widening the budget is not cheap: at 60 seconds the rate still sits at 19.90 per mille, clearing the threshold only at 540 seconds — nine minutes of client wait — with 725.7 requests open at peak. What it wins is written down too: a transaction answered within budget has its two ledgers match **at the moment of reply**, average closure 4.48 seconds, with reconciliation and compensation work never arising. The verdict would flip if the other party settled 99 percent of transactions within budget: the unresolved rate would drop to 10 per mille, the alternative would pass the threshold, and the reconciliation cycle would become unnecessary. #### Failure Behavior and What Is Sacrificed If the other party's notification path stops entirely, polling becomes the only channel and every transaction is learned of within 60 seconds at most; at peak that is 55.56 queries per second, 33x normal, and the throttling from the Resilience and Reliability course's Throttling and Load Shedding lesson cuts that rate. If a reconciliation cycle is missed, the gap is not lost — it shows up in the next cycle with twice the records; reconciliation withstands interruption because it reconstructs its state from the trail. What is sacrificed fits in one sentence: this design sacrifices instantaneous consistency — the two ledgers never say the same thing at the same moment, only a guarantee that they will within 30 minutes. #### Summary - Volume decides nothing here: a peak of 55.56 transactions/s is carried by any structure; the real volume item is the audit trail — 1.56 GB per day, 3.99 TB over seven years. - In the notification-only regime, 2,987 records per cycle do not match (59.74 per mille); polling brings that to 488 (9.76 per mille) and drops lost notifications from 1,550 to 119. - 369 of the remaining 488 are late-arriving confirmations; polling cannot close this, since the other party has not reported the outcome yet either. - Unmatched records are nearly independent of cycle length (488, 488, 482); lengthening the cycle does not resolve the gap, only dilutes the rate from 29.28 to 2.41 per mille. - The two thresholds squeeze the cycle to a single value: the 10-per-mille limit eliminates 5 minutes, the 30-minute closure limit eliminates 60 minutes, and 15 minutes remains. - The cycle-free synchronous-verification alternative is eliminated at 75.77 per mille unresolved records; it clears the threshold only with a 540-second wait budget and 725.7 open requests at peak. #### Next Step Five cases belonged to the same family: writes dominated, and a wrong record was unacceptable. Decisions came from delivery guarantees, channel order, window shape, lock type, and the reconciliation cycle. All five share a feature easy to miss: the data was **small**. A message was 220 bytes, a notification record 300 bytes, a counter 48 bytes, a stock row 64 bytes, a trail record 260 bytes; no design decision came from the byte count itself, all came from the meaning per record. Where a record is meaningless on its own, where its value only emerges in bulk, and where a single object does not fit in one server's memory, this ordering reverses — the subject of the next topic. ## Data-Intensive Systems Five cases where the volume of data drives the design: an object storage service with multipart upload and a durability calculation, a video streaming service with a transcoding pipeline and adaptive streaming, a metrics aggregation system with a time-series write path and rollups, a location-based service with spatial indexing and proximity queries, and a batch-and-stream processing pipeline that uses both processing models together. ### Object Storage Service Source: https://academia.sh/en/courses/case-studies/object-storage-service The first case where volume drives the design: choosing part size against the probability of interruption, measuring the extra bytes sent in an in-process model and verifying it with a closed form, comparing replica count against erasure coding on storage factor and annual loss, and eliminating coding for small objects on request count. The previous topic defended five cases from the write side, and all of them shared one thing in common: the data was **small** and meaningful on its own, per record. The design was driven not by volume but by the record's correctness, order, and delivery guarantee. This topic removes that assumption. Here a single record holds megabytes, and the storage line item overshadows the others. The first case is an **object storage** service: a client writes a binary body under a key, then reads it back by the same key. Two decisions need measuring — the extra bytes a **multipart upload** sends, and how many copies of the data are kept. This lesson's **durability** is about the data not being lost; the Resilience and Reliability course's **resilience** was about the service staying up — a store can stay up and still lose data. #### Constraints Functional requirement: writing, reading, deleting, and prefix-listing objects by key; sending large objects part by part, merging at the end, resuming an unfinished upload. Non-functional requirement, in numbers: the extra bytes sent per object — resends plus per-part overhead — do not exceed **2** percent of the object size; objects lost per year stay under **500**; stored bytes do not exceed **1.5** times the raw data; a small object read is served by a **single** request. Scope reduction: access control and signature verification (the Backend Development curriculum's Authentication and Authorization course), versioning, lifecycle, cross-region replication, and content search are not designed. #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | ND1 | daily uploaded objects | 1,200,000 | the daily total across clients | | ND2 | small object share | 0.92 | small attachments dominate by count | | ND3 | small object average size | 180 KB | documents and small images | | ND4 | large object average size | 90 MB | recordings and backup files | | ND5 | reads per object over its lifetime | 4 | an object is read a handful of times | | ND6 | peak multiplier | 3 | peak hour's ratio to the daily average | | ND7 | bytes sent between interruptions | 250 MB | clients are on mobile networks | | ND8 | per-part overhead | 8 KB | header, signature, part-ledger entry | | ND9 | annual node loss probability | 0.01 | from hardware and operations | | ND10 | retention period | 365 days | the contract runs on an annual cycle | | ND11 | object metadata record | 400 bytes | key, size, checksum, placement | | ND12 | slowest uploading client | 1 Mbit/s | the lower bound for the valet key's lifetime | #### Scale ```js // object-scale.mjs — the scale computation from the ND table; all of it is arithmetic const ND = { objects: 1_200_000, smallShare: 0.92, smallBytes: 180e3, largeBytes: 90e6, reads: 4, peak: 3, interruptionBytes: 250e6, partOverhead: 8192, retentionDays: 365, metadataBytes: 400, partSize: 2e6, slowClientMbit: 1 }; const DAY = 86_400; const avgBytes = ND.smallShare * ND.smallBytes + (1 - ND.smallShare) * ND.largeBytes; const dailyBytes = ND.objects * avgBytes, objectsPerSec = ND.objects / DAY; const partsPerSec = objectsPerSec * ((1 - ND.smallShare) * Math.ceil(ND.largeBytes / ND.partSize) + ND.smallShare); const r = { "large objects' byte share": ((1 - ND.smallShare) * ND.largeBytes) / avgBytes, "daily uploaded TB": dailyBytes / 1e12, "raw stored PB": (dailyBytes * ND.retentionDays) / 1e15, "peak upload objects/s": objectsPerSec * ND.peak, "peak part requests/s": partsPerSec * ND.peak, "part-split request multiplier": partsPerSec / objectsPerSec, "peak upload Mbit/s": (dailyBytes / DAY) * ND.peak * 8 / 1e6, "peak read Mbit/s": (dailyBytes / DAY) * ND.reads * ND.peak * 8 / 1e6, "metadata stored GB": (ND.objects * ND.retentionDays * ND.metadataBytes) / 1e9, "object/metadata volume ratio": avgBytes / ND.metadataBytes, }; for (const [name, d] of Object.entries(r)) console.log(name.padEnd(30) + (Number.isInteger(d) ? String(d) : d.toFixed(2)).padStart(10)); const best = (k) => Math.sqrt(2 * ND.partOverhead * ND.interruptionBytes * k); // lowest extra bytes console.log(`\nbest part size = sqrt(2 * overhead * interruption interval) = ${(best(1) / 1e6).toFixed(2)} MB` + `; ND7 x2 -> ${(best(2) / 1e6).toFixed(2)} MB, ND7 x0.5 -> ${(best(0.5) / 1e6).toFixed(2)} MB`); console.log(`at the slowest client a 2 MB part takes ${(ND.partSize * 8) / (ND.slowClientMbit * 1e6)} s -> ` + `valet key lifetime 60 s (x${(60 / ((ND.partSize * 8) / (ND.slowClientMbit * 1e6))).toFixed(2)} margin)`); ``` ``` large objects' byte share 0.98 daily uploaded TB 8.84 raw stored PB 3.23 peak upload objects/s 41.67 peak part requests/s 188.33 part-split request multiplier 4.52 peak upload Mbit/s 2455.20 peak read Mbit/s 9820.80 metadata stored GB 175.20 object/metadata volume ratio 18414.00 best part size = sqrt(2 * overhead * interruption interval) = 2.02 MB; ND7 x2 -> 2.86 MB, ND7 x0.5 -> 1.43 MB at the slowest client a 2 MB part takes 16 s -> valet key lifetime 60 s (x3.75 margin) ``` These numbers are in the **calculation** class, and four of them drive the design. Eight percent of objects carry 98 percent of the bytes, so the two size classes are designed separately. Metadata volume is 1/18,414th of object volume: 175.20 GB against 3.23 PB. Splitting into parts multiplies the request count by 4.52: 41.67 object uploads become 188.33 part requests at peak. Peak read throughput is 9820.80 Mbit/s — the dominant line item is not requests, it is bandwidth and storage. #### Part Size When an interruption cuts a stream, the bytes sent up to that point are wasted. As parts shrink, wasted bytes drop, but the overhead (ND8) is paid on every part. The sum of the two curves is measured. ```js // part-size.mjs — in-process model: multipart upload of a 90 MB object. No network, no file; // interruptions are generated at exponential intervals over bytes sent. The seed is visible, the generator is hand-written. const OBJECT = 90e6, INTERRUPTION = 250e6, OVERHEAD = 8192, RUNS = 5000, SEED = 20260730, L = 1 / INTERRUPTION; let state = SEED; // linear congruential generator const rand = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; const interval = () => -Math.log(1 - rand()) / L; // bytes sent before an interruption function upload(size) { let sent = 0; for (let remaining = OBJECT; remaining > 0; remaining -= size) { const p = Math.min(size, remaining); for (;;) { sent += OVERHEAD; // every attempt is a request round const g = interval(); if (g >= p) { sent += p; break; } sent += g; // interrupted: this part is resent from the start } } return sent; } function expected(size) { // closed form over the same partitioning let t = 0; for (let remaining = OBJECT; remaining > 0; remaining -= size) { const p = Math.min(size, remaining); t += (Math.exp(L * p) - 1) / L + OVERHEAD * Math.exp(L * p); } return t; } console.log(`model: ${RUNS} uploads, object ${OBJECT / 1e6} MB, interruption interval ${INTERRUPTION / 1e6} MB, ` + `per-part overhead ${OVERHEAD} bytes, seed ${SEED}\n\n` + "part".padStart(14) + "part count".padStart(14) + "sent MB".padStart(15) + "measured ratio".padStart(16) + "expected ratio".padStart(16)); for (const b of [256e3, 1e6, 2e6, 4e6, 16e6, OBJECT]) { let t = 0; for (let i = 0; i < RUNS; i += 1) t += upload(b); const avg = t / RUNS; console.log((b === OBJECT ? "single stream" : `${(b / 1e6).toFixed(2)} MB`).padStart(14) + String(Math.ceil(OBJECT / b)).padStart(14) + (avg / 1e6).toFixed(2).padStart(15) + (avg / OBJECT).toFixed(4).padStart(16) + (expected(b) / OBJECT).toFixed(4).padStart(16)); } ``` ``` model: 5000 uploads, object 90 MB, interruption interval 250 MB, per-part overhead 8192 bytes, seed 20260730 part part count sent MB measured ratio expected ratio 0.26 MB 352 92.94 1.0326 1.0326 1.00 MB 90 90.91 1.0101 1.0102 2.00 MB 45 90.68 1.0075 1.0081 4.00 MB 23 90.90 1.0100 1.0101 16.00 MB 6 93.11 1.0346 1.0319 single stream 1 108.14 1.2015 1.2038 ``` The measured ratio is a valid **measurement** for this run; the expected ratio is a run-independent **calculation**; the two agree on three of four digits. The 2 percent constraint cuts off both ends of the curve: at 256 KB the extra bytes run 3.26 percent, and the cause is not resending but the overhead of 352 parts; at 16 MB it is 3.46 percent, and the cause is resending. Only the range from 1 MB to 4 MB meets the constraint, and the best point sits at 2 MB, the same place the closed form gives. In a single stream, an average of 108.14 MB goes out for a 90 MB object; this ratio worsens as the object grows, because the expected bytes grow exponentially with object size. **Sensitivity.** If ND7 doubles, the best part size shifts to 2.86 MB; if it halves, to 1.43 MB; a fourfold change in ND7 shifts the part size by a factor of two. The decision is weakly tied to ND7 — 2 MB is defensible across a wide range. #### Design The upload path relies on the **Valet Key Pattern** (the Resilience and Reliability course's Distributed Correctness topic). The service does not carry bytes; it returns a time-limited key that authorizes the client to write a single part. The key's scope is an upload ID paired with a part number, and its lifetime is 60 seconds — at the slowest client a 2 MB part takes 16 seconds, leaving a margin of 3.75x. This choice keeps 2455.20 Mbit/s of upload traffic outside the service nodes. A part write is **idempotent** (same topic, Idempotent Operations); the uniqueness key is the same binary data, so a client can send without being certain which part actually landed. The metadata store is a **key-value store** (the Scaling the Data Layer course's Data Distribution topic, Store Types) and is **sharded** by the hash of the object key (same topic, Sharding). Hashing is chosen over range partitioning: keys collected under a shared prefix would overheat a single shard under range partitioning. The **Scheduler–Agent–Supervisor** pattern collects the parts of unfinished uploads (the Application Layer and Service Interaction course's Queues and Workflows topic); its window is 7 days. **Deliberately unused pattern: caching.** Cache-aside from the Scaling the Data Layer course's Cache Architecture topic has no place here: an object is read only 4 times over its lifetime (ND5), and the cost of a layer holding a fraction of the daily 8.84 TB is not worth four reads. The second is **session stickiness** (the Traffic Layer course's Load Balancing topic): part writes are stateless. #### Eliminated Alternative: Three Copies of Every Object The simplest design keeps three copies of every object. The alternative is **erasure coding**: the object is split into k data parts, m parity parts are computed, and any k of the k+m parts return the object. ```js // durability.mjs — the storage, loss, and request cost of replica count versus erasure coding. // Losses are assumed independent (ND9); this is a model assumption, not a measurement. let P = 0.01; // ND9 const N = 1_200_000 * 365, SMALL = 180e3, OVERHEAD = 8192; // ND1xND10, ND3, ND8 const PEAK = (1_200_000 * 4 / 86_400) * 3 * 0.92; // object-scale.mjs: small object reads/s const binom = (n, i) => { let t = 1; for (let j = 0; j < i; j += 1) t = (t * (n - j)) / (j + 1); return t; }; const loss = (k, m) => { if (m === 0) return P ** k; // all k copies are lost let t = 0; // m+1 or more of the k+m parts are lost for (let i = m + 1; i <= k + m; i += 1) t += binom(k + m, i) * P ** i * (1 - P) ** (k + m - i); return t; }; console.log(`ND9 = ${P}, stored objects ${N.toLocaleString("en-US")}\n\n` + "setup".padEnd(16) + "storage factor".padStart(16) + "lost objects/year".padStart(19) + "read requests".padStart(15) + "overhead at 180 KB".padStart(20)); for (const [name, k, m] of [["3 copies", 3, 0], ["erasure (6,3)", 6, 3], ["erasure (10,4)", 10, 4], ["erasure (12,4)", 12, 4]]) console.log(name.padEnd(16) + (m === 0 ? k : (k + m) / k).toFixed(2).padStart(16) + (loss(k, m) * N).toFixed(2).padStart(19) + String(m === 0 ? 1 : k).padStart(15) + `${((((m === 0 ? k : k + m) * OVERHEAD) / SMALL) * 100).toFixed(1)}%`.padStart(20)); const RAW = 3.23, LARGE_SHARE = 0.9775; // object-scale.mjs const mix = LARGE_SHARE * 1.4 + (1 - LARGE_SHARE) * 3; // large erasure (10,4), small 3 copies // GB-month: under linear growth the year average is half the year-end figure, x12 months -> x6 console.log(`\nyear-end storage: all erasure (10,4) ${(RAW * 1.4).toFixed(2)} PB, mixed ` + `(factor ${mix.toFixed(3)}) ${(RAW * mix).toFixed(2)} PB, all 3 copies ${(RAW * 3).toFixed(2)} PB`); console.log(`the mix's excess is ${(RAW * (mix - 1.4) * 6e6).toFixed(0)} GB-month; for small objects, peak ` + `part requests/s is ${PEAK.toFixed(2)} for 3 copies, ${(PEAK * 10).toFixed(2)} for erasure (10,4)\n`); for (const p of [0.005, 0.01, 0.02, 0.04]) { P = p; console.log(`ND9=${p} -> 3 copies ${loss(3, 0).toExponential(2)}, erasure (10,4) ` + `${loss(10, 4).toExponential(2)}, ratio ${(loss(3, 0) / loss(10, 4)).toFixed(2)}`); } ``` ``` ND9 = 0.01, stored objects 438,000,000 setup storage factor lost objects/year read requests overhead at 180 KB 3 copies 3.00 438.00 1 13.7% erasure (6,3) 1.50 530.17 6 41.0% erasure (10,4) 1.40 81.33 10 63.7% erasure (12,4) 1.33 174.51 12 72.8% year-end storage: all erasure (10,4) 4.52 PB, mixed (factor 1.436) 4.64 PB, all 3 copies 9.69 PB the mix's excess is 697680 GB-month; for small objects, peak part requests/s is 153.33 for 3 copies, 1533.33 for erasure (10,4) ND9=0.005 -> 3 copies 1.25e-7, erasure (10,4) 6.03e-9, ratio 20.74 ND9=0.01 -> 3 copies 1.00e-6, erasure (10,4) 1.86e-7, ratio 5.39 ND9=0.02 -> 3 copies 8.00e-6, erasure (10,4) 5.51e-6, ratio 1.45 ND9=0.04 -> 3 copies 6.40e-5, erasure (10,4) 1.51e-4, ratio 0.42 ``` Three copies lose on two numbers at once. The storage constraint is 1.50x while three copies' factor is 3.00; erasure (10,4) stays under it at 1.40 and also wins on durability: 81.33 objects lost per year instead of 438. Erasure (6,3) breaks the "under 500" constraint with an annual loss of 530.17; erasure (12,4) is the cheapest on storage, but its loss is more than double (10,4)'s. The alternative wins where the object is small. Erasure (10,4) splits a 180 KB object into fourteen 18 KB parts: overhead climbs to 63.7 percent of the object, and a read needs ten requests — 1533.33 part requests at peak instead of 153.33, which breaks the "served by a single request" constraint. The choice is therefore mixed: three copies for small objects, erasure (10,4) for large ones, at a factor of 1.436. **Which constraint change flips the alternative:** if ND9 drops to five per thousand, coding's advantage grows to 20.74x; at 2 percent it falls to 1.45x, at 4 percent to 0.42x — once node loss becomes frequent enough, three copies pulls ahead, because it requires losing all of the copies rather than three of fourteen parts. Independent loss is a model assumption; if losses are correlated, both columns are optimistic. #### Failure Behavior and What Is Sacrificed When a shard of the metadata store goes down, no new upload can start in that hash range and no merge can complete; but part writes already in flight continue, because they go straight to the store through the valet key. This is **graceful degradation** (the Resilience and Reliability course's Fault Isolation topic): the upload does not stop, it only cannot finish, and the client can complete it within the 7-day window. On the loss of one storage node, an erasure (10,4) object is read from 13 of its 14 parts; because repair reads k = 10 parts, its traffic runs to the size of the object. Since the peak part-request rate is 188.33/s, the upload path gets **throttling** (same topic) set with a threshold above that rate. **What is sacrificed:** for small objects, the storage factor was left at 3. If everything were coded, year-end storage would be 4.52 PB; the mixed choice is 4.64 PB — 697,680 GB-month of extra storage a year, the price of keeping small-object reads at 153.33 part requests instead of 1533.33. #### Summary - Eight percent of objects carry 98 percent of the bytes; the two size classes are designed separately, and multipart upload multiplies the request count by 4.52 — 188.33 part requests at peak. - Part size is chosen from the bottom of a trough: the extra-byte ratio runs 1.0326 at 256 KB, 1.0075 at 2 MB, 1.0346 at 16 MB, 1.2015 in a single stream, and the best point sits exactly where sqrt(2 × overhead × interruption interval) puts it. - Three copies lose on two numbers at once: a storage factor of 3.00 against 1.40, an annual loss of 438 against 81.33 objects; but for small objects, coding pushes reads from 153.33 to 1533.33 requests, so three copies wins there. - The choice is tied to ND9: if the loss probability rises to 4 percent, the ratio becomes 0.42 and three copies pulls ahead. #### Next Step In this case the object was a meaningless byte sequence: stored as written, served as read, its content never inspected. The next case removes that assumption: the uploaded file gets multiple representations, and which one is served is decided by the requester's conditions at that moment. The question becomes: in how many forms is the same content kept, how is the processor cost of producing them weighed against the bytes they store, and when does an extra form become waste. ### Video Streaming Service Source: https://academia.sh/en/courses/case-studies/video-streaming-service The case where multiple representations of the same content are kept: budgeting the transcoding pipeline in processor-seconds, measuring the bitrate ladder's hit rate against the viewer bandwidth distribution, the shrinking bandwidth utilization gained per rung, and three separate constraints eliminating three separate ladders. In the previous case, the object was a meaningless byte sequence to the service: stored as written, served as read. This case removes that assumption. The uploaded file is not stored just once; multiple representations are produced from its content, and which representation is served is decided by the requester's bandwidth at that moment. The new line item is the **transcoding pipeline**, and the new trade-off is how many rungs **adaptive streaming**'s **bitrate ladder** carries. The decision to measure is this: each rung costs both stored bytes and processor-seconds, but in return delivers a stream that better fits the viewer's bandwidth. The rung count is chosen where these two curves cross, and the crossing point depends on the distribution of viewer bandwidth. #### Constraints Functional requirement: producing multiple quality rungs from the uploaded source copy, splitting each rung into fixed-duration segments, handing the client the segment list, and letting the client switch between rungs. Non-functional requirement, in numbers: the share of viewers who cannot play because their bandwidth does not carry even the lowest rung stays under **10** percent; stored bytes do not exceed **2.5** times the source copy; processors continuously allocated to encoding do not exceed **1500**; an hour of video does not take more than **10** minutes to go from upload to watchable. Scope reduction: content protection, live streaming, recommendations, subtitle generation, and ad placement are not designed. #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | VY1 | daily uploaded video hours | 4,000 | the daily total across uploaders | | VY2 | source copy's bit rate | 20,000 kbit/s | unencoded upload | | VY3 | daily watched hours | 900,000 | watching runs far heavier than uploading | | VY4 | peak multiplier | 3 | peak hour's ratio to the daily average | | VY5 | retention period | 365 days | the catalog is kept for a year | | VY6 | encoding cost | 0.4 + 0.25 × Mbit/s | processor-seconds per video-second | | VY7 | viewer bandwidth distribution | 0.25/1.5 + 0.50/6 + 0.25/20 | a three-class mixture, exponential, Mbit/s | | VY8 | bandwidth's usable share | 0.8 | protocol overhead and fluctuation margin | | VY9 | segment duration | 4 s | rung switching happens at this granularity | | VY10 | edge cache hit rate | 0.95 | segments are immutable and kept for a long time | VY6 and VY7 are this design's two load-bearing assumptions: one sets the production cost, the other the hit rate. Both are reasoned, not measured. #### Scale ```js // video-scale.mjs — the scale computation from the VY table; all of it is arithmetic const VY = { uploadedHours: 4000, sourceKbit: 20_000, watchedHours: 900_000, retentionDays: 365, fixedCpu: 0.4, cpuPerKbit: 0.25, segmentSec: 4 }; const RUNGS = [400, 1200, 3000, 6000, 12_000]; // chosen bitrate ladder rungs, kbit/s const total = RUNGS.reduce((a, b) => a + b, 0); const cpu = RUNGS.reduce((a, k) => a + VY.fixedCpu + VY.cpuPerKbit * (k / 1000), 0); const videoSec = VY.uploadedHours * 3600; for (const [name, d] of [ ["watched / uploaded hours", VY.watchedHours / VY.uploadedHours], ["rung total kbit/s", total], ["encoding processor-sec / video-sec", cpu], ["daily stored TB", (videoSec * (VY.sourceKbit + total) * 1000) / 8 / 1e12], ["year-end stored PB", (videoSec * (VY.sourceKbit + total) * 1000 * VY.retentionDays) / 8 / 1e15], ["daily segments produced", (videoSec / VY.segmentSec) * RUNGS.length], ]) console.log(name.padEnd(36) + d.toFixed(2).padStart(14)); console.log(`\nan hour of video requires ${(3600 * cpu).toFixed(0)} processor-sec:`); for (const n of [30, 60, 120]) console.log(` ${n} workers -> upload-to-watchable ${((3600 * cpu) / n / 60).toFixed(2)} min`); ``` ``` watched / uploaded hours 225.00 rung total kbit/s 22600.00 encoding processor-sec / video-sec 7.65 daily stored TB 76.68 year-end stored PB 27.99 daily segments produced 18000000.00 an hour of video requires 27540 processor-sec: 30 workers -> upload-to-watchable 15.30 min 60 workers -> upload-to-watchable 7.65 min 120 workers -> upload-to-watchable 3.83 min ``` These numbers are in the **calculation** class. Three of them drive the design. Every uploaded hour is watched for 225 hours: an encoding cost paid once is read two hundred twenty-five times, which on its face makes preparing the content at upload time, not at watch time, the sound choice. 18,000,000 segments are produced per day — that is the object count the distribution layer sees, not the video count. And the last line meets a constraint directly: the 10-minute latency constraint requires at least 46 workers; at 30 workers the figure runs to 15.30 minutes and breaks the constraint, at 60 workers it stays at 7.65 minutes. #### Rung Selection The rung count is defensible only once the viewer bandwidth distribution is given. The model below sets up no network and runs no encoder: it draws bandwidth from VY7's three-class mixture, picks the highest rung that fits each viewer's usable bandwidth, and compares four ladders over the same set of viewers. ```js // rung-selection.mjs — in-process model: how accurate rung selection is against the viewer // bandwidth distribution. No network, no encoder; the distribution is a three-class mixture and is written as a model. const VIEWERS = 200_000, SEED = 20260731, SHARE = 0.8; // VY8: the usable share of bandwidth const CLASS = [[0.25, 1500], [0.50, 6000], [0.25, 20_000]]; // VY7: share, average kbit/s const SOURCE = 20_000, FIXED = 0.4, CPU_PER_KBIT = 0.25; // VY2, VY6 const WATCHED_HOURS = 900_000, PEAK = 3, HIT = 0.95; // VY3, VY4, VY10 const UPLOADED_SEC = 4000 * 3600; // VY1: video-seconds encoded per day let state = SEED; const rand = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; function bandwidth() { // pick a class, draw from its exponential let u = rand(), i = 0; while (i < CLASS.length - 1 && u > CLASS[i][0]) { u -= CLASS[i][0]; i += 1; } return -Math.log(1 - rand()) * CLASS[i][1]; } const bandwidths = Array.from({ length: VIEWERS }, bandwidth); const LADDER = { "1 rung": [3000], "3 rungs": [800, 3000, 9000], "5 rungs": [400, 1200, 3000, 6000, 12_000], "8 rungs": [300, 600, 1000, 1800, 3000, 5000, 8000, 12_000] }; function measure(m) { let notPlayable = 0, selectedTotal = 0, utilizationTotal = 0; for (const b of bandwidths) { const available = b * SHARE; const s = m.filter((k) => k <= available).pop(); if (s === undefined) { notPlayable += 1; continue; } selectedTotal += s; utilizationTotal += s / available; } const playable = VIEWERS - notPlayable; const totalKbit = m.reduce((a, b) => a + b, 0); return { notPlayable: notPlayable / VIEWERS, avgSelected: selectedTotal / playable, utilization: utilizationTotal / playable, storage: (SOURCE + totalKbit) / SOURCE, cpu: m.reduce((a, k) => a + FIXED + CPU_PER_KBIT * (k / 1000), 0) }; } console.log(`model: ${VIEWERS} viewers, seed ${SEED}, class shares ` + `${CLASS.map(([p, o]) => `${p}/${o}`).join(" ")} kbit/s (exponential)\n`); console.log("ladder".padEnd(11) + "not playable".padStart(13) + "avg selected".padStart(13) + "bandwidth utilization".padStart(23) + "storage factor".padStart(16) + "sustained processors".padStart(22) + "peak edge Gbit/s".padStart(18) + "origin Gbit/s".padStart(15)); const R = {}; for (const [name, m] of Object.entries(LADDER)) { const r = measure(m); R[name] = r; const edge = (WATCHED_HOURS * 3600 * r.avgSelected * 1000 / 86_400) * PEAK / 1e9; console.log(name.padEnd(11) + `${(r.notPlayable * 100).toFixed(2)}%`.padStart(13) + r.avgSelected.toFixed(0).padStart(13) + `${(r.utilization * 100).toFixed(1)}%`.padStart(23) + r.storage.toFixed(2).padStart(16) + ((UPLOADED_SEC * r.cpu) / 86_400).toFixed(0).padStart(22) + edge.toFixed(2).padStart(18) + (edge * (1 - HIT)).toFixed(2).padStart(15)); } const k = Object.keys(LADDER); console.log("\nbandwidth utilization gained per rung:"); for (let i = 1; i < k.length; i += 1) { const d = LADDER[k[i]].length - LADDER[k[i - 1]].length; console.log(` ${k[i - 1]} -> ${k[i]}: ${(((R[k[i]].utilization - R[k[i - 1]].utilization) * 100) / d).toFixed(2)} points/rung`); } const disabled = measure([400, 1200, 3000, 6000]); // if the top rung is disabled console.log(`top rung disabled: avg selected ${disabled.avgSelected.toFixed(0)} kbit/s, edge output ` + `x${(disabled.avgSelected / R["5 rungs"].avgSelected).toFixed(2)}, not playable unchanged at ${(disabled.notPlayable * 100).toFixed(2)}%`); const customCpu = WATCHED_HOURS * 3600 * (FIXED + CPU_PER_KBIT * 6); // one stream per viewer const ladderCpu = UPLOADED_SEC * R["5 rungs"].cpu; console.log(`per-viewer custom encoding: ${customCpu.toExponential(2)} processor-sec/day, ${(customCpu / ladderCpu).toFixed(1)}x ` + `the 5-rung ladder's (${(ladderCpu).toExponential(2)})`); ``` ``` model: 200000 viewers, seed 20260731, class shares 0.25/1500 0.5/6000 0.25/20000 kbit/s (exponential) ladder not playable avg selected bandwidth utilization storage factor sustained processors peak edge Gbit/s origin Gbit/s 1 rung 45.75% 3000 43.2% 1.15 192 337.50 16.88 3 rungs 13.77% 3846 56.5% 1.64 733 432.71 21.64 5 rungs 8.91% 4442 64.9% 2.13 1275 499.72 24.99 8 rungs 6.08% 4607 73.8% 2.58 1854 518.24 25.91 bandwidth utilization gained per rung: 1 rung -> 3 rungs: 6.66 points/rung 3 rungs -> 5 rungs: 4.22 points/rung 5 rungs -> 8 rungs: 2.96 points/rung top rung disabled: avg selected 3242 kbit/s, edge output x0.73, not playable unchanged at 8.91% per-viewer custom encoding: 6.16e+9 processor-sec/day, 55.9x the 5-rung ladder's (1.10e+8) ``` The ratios in the table are **measurements**, the cost columns are in the **calculation** class; the measured ratios depend on this run's seed, while the differences that separate the constraints are magnitudes independent of the seed. Bandwidth utilization gained per rung drops from 6.66 to 4.22 to 2.96 points: **each new rung gains less than the one before it, but its cost does not drop to match.** #### Design The measurement points to the five-rung ladder; the design is built on it. The transcoding pipeline sits on a **message queue** and **competing consumers** (the Application Layer and Service Interaction course's Queues and Workflows topic). The parameter is worker count: 60 workers make an hour of video watchable in 7.65 minutes. The same topic's **priority queue** puts new uploads ahead of the re-encoding jobs that backfill the catalog; this keeps the latency constraint binding only on new uploads. The job message does not carry bytes, it carries the source object's key — the **Claim Check Pattern** (the Resilience and Reliability course's Distributed Correctness topic). An encoding job is **idempotent** (same topic); the uniqueness key is the pair of video ID and rung, so a job re-run after being left half-finished does not produce a second output. The distribution side is built on a **content delivery network** and **edge cache** (the Traffic Layer course's Entry Points topic). The parameter is the hit rate: VY10's 95 percent brings the peak edge traffic of 499.72 Gbit/s down to 24.99 Gbit/s at the origin. Because segments never change once produced, there is no question of a staleness window; the same topic's **push-based distribution** moves a newly uploaded piece of content's first segments to the edge before it is ever watched, and the rest arrives by pull. The segment list and the segments are static files (same topic, Static Content Hosting), so there is no application code on the read path. **Deliberately unused pattern: circuit breaker.** The circuit breaker from the Resilience and Reliability course's Fault Isolation topic has no place in the encoding layer, because workers make no synchronous call; they pull from the queue and re-surface a failed job — there is no call path to cut. The second is **Command and Query Separation** (the Scaling the Data Layer course's Read–Write Separation topic): the read path is not a query, it is fetching a file whose name is already known, and deriving a separate read model has no payoff. #### Eliminated Alternatives Three alternatives are eliminated by three separate numbers, and each is caught by a different constraint. **One rung** is the cheapest: a storage factor of 1.15, 192 sustained processors. But 45.75 percent of viewers cannot carry that single rung and cannot play at all — four and a half times the 10 percent constraint. Three rungs also stays above the constraint, at 13.77 percent. **Eight rungs** is best on the hit side: bandwidth utilization of 73.8 percent, 6.08 percent not playable. It breaks two constraints at once: a storage factor of 2.58 (limit 2.5) and 1854 sustained processors (limit 1500). The 8.9 points of utilization it gains cost 21 percent more on storage and 45 percent more on processors. **Per-viewer custom encoding** — producing each stream on the fly, fitted exactly to the viewer's bandwidth — solves the hit-rate problem completely, because utilization reaches 100 percent and no extra rung is stored. It requires 6.16 billion processor-seconds a day, 55.9 times the five-rung ladder's 110 million processor-seconds. The reason is the first line of the scale calculation: encoding is paid not once per upload but once per watch, and watching runs at 225 times uploading. What remains is **five rungs**: 8.91 percent not playable, a storage factor of 2.13, 1275 sustained processors — all three constraints are met. **Which constraint change flips the alternative:** if the storage limit rises to 2.6, eight rungs gets in and raises bandwidth utilization by 8.9 points; if the viewer bandwidth distribution narrows (the three classes move closer together), fewer rungs suffice and three rungs starts meeting the constraint. #### Failure Behavior and What Is Sacrificed When the encoding layer goes down entirely, the catalog keeps playing; only new uploads fail to become watchable and back up in the queue. This is **graceful degradation** (the Fault Isolation topic), and its cost is suspending the latency constraint. When the origin goes down, the edge cache keeps serving 95 percent of requests, because segments are immutable and there is no risk of a stale copy. On the output side, when the peak load limit is forced, the top rung is disabled: the average selected bit rate drops from 4442 to 3242 kbit/s, edge output falls to 0.73x, and the not-playable share of viewers holds unchanged at 8.91 percent — degradation lowers quality, it does not leave anyone out. **What is sacrificed:** bandwidth utilization was left at 64.9 percent. A third of the viewer's usable bandwidth sits idle, and that is the price of keeping storage under 2.5x and encoding under 1500 processors. #### Summary - Every uploaded hour is watched for 225 hours; this ratio is why the encoding cost is paid at upload time rather than watch time, and it is also what makes per-viewer custom encoding 55.9 times more expensive. - The hit rate of the bitrate ladder can only be measured together with the viewer bandwidth distribution: at five rungs, bandwidth utilization is 64.9 percent, and 8.91 percent of viewers cannot play. - Utilization gained per rung drops from 6.66 to 4.22 to 2.96 points while the cost per rung does not drop; that is why the ladder has an end. - Three alternatives are eliminated by three separate constraints: one rung by its not-playable share (45.75 percent), eight rungs by its storage (2.58) and processor (1854) limits, per-viewer custom encoding by processor-seconds. - The edge cache brings output down from 499.72 Gbit/s to 24.99 Gbit/s, and because segments are immutable, the question of a staleness window never even opens. #### Next Step In this case too, data was stored as written: a piece was produced, put somewhere, and later read back unchanged. Every byte produced was worth storing. The next case removes that assumption. There, records are produced by the hundreds of thousands per second, none of them meaningful on its own, and storing all of them is impossible. The question becomes: how long is a given record kept raw, when is it aggregated, and how far does an answer read from aggregated data diverge from one read from raw data. ### Metrics Aggregation System Source: https://academia.sh/en/courses/case-studies/metrics-aggregation-system The case where no single record is meaningful on its own: budgeting the time-series write path by sample rate, the effect of storage tiers on total bytes, and measuring in a real engine which questions downsampling leaves untouched and which it answers with one hundred percent error. In the previous two cases, every byte produced was worth storing: an object was kept exactly as written, a video segment was read many times after it was produced. This case removes that assumption. Here records are produced hundreds of thousands of times per second, no single one is meaningful on its own, and storing all of them indefinitely is neither possible nor necessary. The system is a **metrics aggregation** system: nodes send numeric samples at regular intervals, the samples are written as a **time series**, and questions are always asked over a time range. The decision to be measured is the joint effect of **downsampling** and **rollup**: stored bytes and scanned rows fall, but the answer read from rolled-up data is not equal to the answer read from raw data. This gap depends on the question type, and the design chooses that gap deliberately. Which metrics are worth collecting is not this case's subject; that question was settled in the Performance Anti-Patterns and Monitoring course's Instrumentation Design lesson. Here the metric set is a given, and the design's job is to carry it. #### Constraints Functional requirement: accepting samples, reading by series and time range, answering average / max / percentile / threshold-breach questions over a series, and dropping data whose retention period has expired. Non-functional requirement, with numbers: the write path accepts a peak of **480,000** samples/s without loss; total stored bytes do not exceed **40** TB; a six-hour dashboard query scans fewer than **400** rows per series; over the last **7** days, percentile and threshold-breach questions are answered **without error**. Scope narrowing: alerting rules, the dashboard interface, monitoring categories, and distributed trace collection are not designed here — these are the subject of the Performance Anti-Patterns and Monitoring course. #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | OT1 | monitored node | 20,000 | sum of running processes | | OT2 | series per node | 120 | a few metrics per process, resource, and endpoint | | OT3 | sampling interval | 10 s | the agent's send frequency | | OT4 | raw sample record | 26 bytes | series ID, time, and value | | OT5 | rollup record | 34 bytes | bucket, count, total, and max | | OT6 | peak multiplier | 2 | the metric stream is regular, its peak is shallow | | OT7 | raw retention | 7 days | incident review looks back one week | | OT8 | one-minute rollup retention | 90 days | quarter-over-quarter comparison | | OT9 | five-minute rollup retention | 730 days | capacity trend goes back two years | | OT10 | dashboard window | 6 hours | one shift's window | OT6 is this case's distinguishing assumption: the peak multiplier was 3 in earlier cases, here it is 2. The metric stream depends on the agent's scheduler, not on user behavior, so its peak is shallow. #### Scale ```js // metrics/scale.mjs — scale calculation derived from the OT table and the total across storage tiers const OT = { node: 20_000, seriesPerNode: 120, intervalS: 10, rawBytes: 26, rollupBytes: 34, peak: 2, queryWindowH: 6, rawDays: 7, minuteDays: 90, fiveMinuteDays: 730 }; const series = OT.node * OT.seriesPerNode; const samplesS = series / OT.intervalS; const rawDaily = samplesS * 86_400 * OT.rawBytes; const rollupDaily = (grainS) => (series * (86_400 / grainS)) * OT.rollupBytes; for (const [name, d] of [ ["series count", series], ["average samples/s", samplesS], ["peak samples/s", samplesS * OT.peak], ["raw daily GB", rawDaily / 1e9], ["1 min rollup daily GB", rollupDaily(60) / 1e9], ["5 min rollup daily GB", rollupDaily(300) / 1e9], ]) console.log(name.padEnd(24) + d.toFixed(2).padStart(12)); const tiers = [["raw", rawDaily, OT.rawDays], ["1 min rollup", rollupDaily(60), OT.minuteDays], ["5 min rollup", rollupDaily(300), OT.fiveMinuteDays]]; let total = 0; console.log(`\n${"tier".padEnd(15)}${"days".padStart(6)}${"stored TB".padStart(14)}`); for (const [name, days, retention] of tiers) { total += (days * retention) / 1e12; console.log(name.padEnd(15) + String(retention).padStart(6) + ((days * retention) / 1e12).toFixed(2).padStart(14)); } const allRaw = (rawDaily * OT.fiveMinuteDays) / 1e12; console.log(`total ${total.toFixed(2)} TB; if everything were kept raw for ${OT.fiveMinuteDays} days it would be ` + `${allRaw.toFixed(2)} TB (x${(allRaw / total).toFixed(2)})`); console.log(`${OT.queryWindowH}-hour query, rows read per series: raw ` + `${(OT.queryWindowH * 3600) / OT.intervalS}, 1 min ${OT.queryWindowH * 60}, ` + `5 min ${(OT.queryWindowH * 3600) / 300}`); ``` ``` series count 2400000.00 average samples/s 240000.00 peak samples/s 480000.00 raw daily GB 539.14 1 min rollup daily GB 117.50 5 min rollup daily GB 23.50 tier days stored TB raw 7 3.77 1 min rollup 90 10.58 5 min rollup 730 17.16 total 31.50 TB; if everything were kept raw for 730 days it would be 393.57 TB (x12.49) 6-hour query, rows read per series: raw 2160, 1 min 360, 5 min 72 ``` These numbers are in the **calculation** class. Three of them determine the design. The write path sees 240,000 samples/s on average, 480,000 at peak; this is two orders of magnitude higher than the earlier cases where one request corresponded to one record, and it makes the per-sample cost of every step in the write path decisive. The storage tier total is 31.50 TB, under the 40 TB limit; if the same data were kept raw it would be 393.57 TB, that is, 12.49 times as much, and the limit would be violated. The six-hour query reads 360 rows from the one-minute rollup, 2160 from the raw tier; only the rollup tiers meet the 400-row limit. #### The Cost of Downsampling The table above shows only the gain. The cost is in the answer itself, and it is measured in a real engine. The model below does not stand up a cluster; it generates six hours of a single series inside `node:sqlite`, rolls it up into two grains, and asks the same four questions of all three formats at once. ```js // metrics/downsampling.mjs — a single series' raw and rolled-up forms in a real engine via // node:sqlite. The generator is hand-written, the seed is visible; what is measured is stored // bytes, scanned rows, and the gap the same four questions get between the two forms. The model // is written as what it is. import { DatabaseSync } from "node:sqlite"; const DURATION = 21_600, SEED = 20260801, THRESHOLD = 200; // 6 hours, one sample per second let state = SEED; const rand = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; const generate = (t) => { // daily wave + noise + occasional spike const base = 100 + 40 * Math.sin((2 * Math.PI * t) / 86_400) + (rand() - 0.5) * 30; return base + (rand() < 0.002 ? 300 : 0); }; const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE raw(t INTEGER PRIMARY KEY, value REAL); CREATE TABLE rollup60(bucket INTEGER PRIMARY KEY, count INTEGER, total REAL, maxValue REAL); CREATE TABLE rollup300(bucket INTEGER PRIMARY KEY, count INTEGER, total REAL, maxValue REAL);`); db.exec("BEGIN"); const insert = db.prepare("INSERT INTO raw VALUES(?,?)"); for (let t = 0; t < DURATION; t += 1) insert.run(t, generate(t)); db.exec("COMMIT"); for (const g of [60, 300]) db.exec(`INSERT INTO rollup${g} SELECT t / ${g}, count(*), sum(value), max(value) FROM raw GROUP BY t / ${g}`); const percentile = (a, p) => { const s = [...a].sort((x, y) => x - y); return s[Math.floor(s.length * p)]; }; const rawValues = db.prepare("SELECT value FROM raw").all().map((r) => r.value); const bytes = (t) => db.prepare("SELECT sum(pgsize) AS b FROM dbstat WHERE name = ?").get(t).b; const rows = (t) => db.prepare(`SELECT count(*) AS n FROM ${t}`).get().n; const RAW = { avg: rawValues.reduce((a, b) => a + b) / DURATION, max: Math.max(...rawValues), p95: percentile(rawValues, 0.95), over: rawValues.filter((d) => d > THRESHOLD).length }; console.log(`model: ${DURATION} samples (one per second), seed ${SEED}, threshold ${THRESHOLD}\n`); console.log("format".padEnd(14) + "rows".padStart(7) + "bytes".padStart(9) + "bytes/row".padStart(12) + "average".padStart(10) + "max".padStart(10) + "p95".padStart(9) + "over-threshold s".padStart(18)); const line = (name, n, b, avg, max, p, over) => console.log(name.padEnd(14) + String(n).padStart(7) + String(b).padStart(9) + (b / n).toFixed(1).padStart(12) + avg.toFixed(2).padStart(10) + max.toFixed(2).padStart(10) + p.toFixed(2).padStart(9) + String(over).padStart(18)); line("raw", rows("raw"), bytes("raw"), RAW.avg, RAW.max, RAW.p95, RAW.over); const ROLLUP = {}; for (const g of [60, 300]) { const k = db.prepare(`SELECT count, total, maxValue FROM rollup${g}`).all(); const bucketAvg = k.map((r) => r.total / r.count); const o = { avg: k.reduce((a, r) => a + r.total, 0) / DURATION, max: Math.max(...k.map((r) => r.maxValue)), p95: percentile(bucketAvg, 0.95), over: bucketAvg.filter((d) => d > THRESHOLD).length * g }; ROLLUP[g] = o; line(`${g} s rollup`, rows(`rollup${g}`), bytes(`rollup${g}`), o.avg, o.max, o.p95, o.over); } console.log(`\ndeviation from the raw answer (percent):`); for (const g of [60, 300]) { const s = (a, b) => (((a - b) / b) * 100).toFixed(2); console.log(` ${g} s rollup -> average ${s(ROLLUP[g].avg, RAW.avg)}, max ` + `${s(ROLLUP[g].max, RAW.max)}, p95 ${s(ROLLUP[g].p95, RAW.p95)}, ` + `over-threshold time ${s(ROLLUP[g].over, RAW.over)}`); } for (const g of [60, 300]) { // the same question with the max column const n = db.prepare(`SELECT count(*) AS n FROM rollup${g} WHERE maxValue > ?`).get(THRESHOLD).n; console.log(` ${g} s rollup, over-threshold time with max: ${n * g} s (raw ${RAW.over} s, ` + `x${((n * g) / RAW.over).toFixed(1)})`); } console.log(`scanned-row ratio: 60 s rollup 1/${DURATION / rows("rollup60")}, ` + `300 s rollup 1/${DURATION / rows("rollup300")}; byte ratio 1/` + `${(bytes("raw") / bytes("rollup60")).toFixed(1)} and 1/${(bytes("raw") / bytes("rollup300")).toFixed(1)}`); ``` ``` model: 21600 samples (one per second), seed 20260801, threshold 200 format rows bytes bytes/row average max p95 over-threshold s raw 21600 356352 16.5 125.84 450.17 148.84 41 60 s rollup 360 16384 45.5 125.84 450.17 140.74 0 300 s rollup 72 4096 56.9 125.84 450.17 139.88 0 deviation from the raw answer (percent): 60 s rollup -> average 0.00, max 0.00, p95 -5.44, over-threshold time -100.00 300 s rollup -> average 0.00, max 0.00, p95 -6.02, over-threshold time -100.00 60 s rollup, over-threshold time with max: 2400 s (raw 41 s, x58.5) 300 s rollup, over-threshold time with max: 9600 s (raw 41 s, x234.1) scanned-row ratio: 60 s rollup 1/60, 300 s rollup 1/300; byte ratio 1/21.8 and 1/87.0 ``` These numbers are in the **measurement** class; the values depend on this run's seed, the sign and magnitude of the deviations do not. Because the bytes column depends on the page grain, bytes per row look large in a table with few rows; for comparison, the total byte ratio is what matters. The four questions show three separate behaviors. **Average and max are not distorted at all:** the deviation is 0.00 percent at both grains, because the rollup row carries the total, the count, and the max — the average and the max can be reconstructed exactly from these three. **The percentile is distorted, but only a little:** p95 comes out 5.44 percent low at the one-minute grain, 6.02 percent low at the five-minute grain, because the bucket average flattens the distribution inside the bucket. **The threshold breach disappears completely:** viewed through the bucket average, the 41-second breach looks like 0 seconds, that is, 100 percent error. Asking the same question with the max column does not work either, it misses in the opposite direction: 2400 seconds at the one-minute grain, 9600 seconds at the five-minute grain — 58.5 and 234.1 times the raw answer, because a breach in any second of a bucket counts the whole bucket as breaching. **A rollup row answers the questions its carried columns can answer; for the others it leaves an uncertainty between a lower bound and an upper bound.** #### Design The write path is built on a **message broker** and **competing consumers** (the Application Layer and Service Interaction course's Queues and Workflows topic); **queue-based load leveling** from the same topic flattens the peak 480,000 samples/s into a steady rate the writers see. On the agent side, **backpressure** (the Resilience and Reliability course's Fault Isolation topic) is measured by buffer utilization, and when the buffer fills, the oldest sample is dropped. The store is a **wide-column store** (the Scaling the Data Layer course's Data Distribution topic, Store Types): the row key is the series ID, the columns are time-ordered. The **sharding** key is the series ID, not the node name — sharding by node name would let one node's 120 series fall into a single shard and create a hot shard. **Partitioning** is by time (the same topic, Partitioning Strategies), and the retention policy is enforced by dropping partitions: a raw partition older than 7 days is deleted in a single operation, not row by row. Rollup is two **materialized views** (the same topic): the refresh is incremental and writes only the bucket that just closed. The parameters are the grains — 60 seconds and 300 seconds — and their rationale is OT8 and OT9's retention periods. The tier read for capacity estimation is the five-minute one; the method for going from a time series to a resource estimate was established in the Performance Anti-Patterns and Monitoring course's Capacity Planning lesson and is not repeated here, only its input comes from this tier. **Deliberately unused pattern: the idempotency key ledger.** The ledger from the Resilience and Reliability course's Idempotent Operations lesson has no place here, because a sample is already addressed by the (series, time) pair, and a duplicate write overwrites the same cell with the same value; a separate ledger would add a record of the same order of magnitude next to every 26-byte sample record, and it would be paid 240,000 times per second. The second is **federation** (the Data Distribution topic): there is no separate functional domain to split off, all the data is uniform and has a single access pattern. #### Eliminated Alternatives **Keeping everything raw** answers percentile and threshold questions without error at any date. It requires 393.57 TB, ten times the 40 TB limit; the six-hour query also scans 2160 rows per series and violates the 400-row limit too. It is eliminated by two limits at once. **Keeping everything as a five-minute rollup** is the cheapest: 17.16 TB total and 72 rows per query. It answers the threshold-breach question with either 100 percent error (0 seconds) or a 234.1-fold inflation (9600 seconds), and deviates by 6.02 points on the percentile. It is eliminated by the "without error over the last 7 days" limit. The chosen three-tier layout stays at 31.50 TB, scans 360 rows per query, and answers the sensitive questions without error because raw data sits there for the last seven days. **Which limit changes and the alternative wins:** if threshold-breach and percentile questions are never asked, the raw tier loses its reason to exist, the 3.77 TB line item drops, and the write path can write straight to the rollup; conversely, if incident review looks back further than a week, raw retention is extended and the total quickly pushes against 40 TB. #### Failure Behavior and What Is Given Up When the message broker goes down, agents accumulate in their buffers; dropping the oldest sample when the buffer fills is **graceful degradation** (the Fault Isolation topic), because the series stays continuous but its grain temporarily coarsens — the average and max question keeps being answered, the threshold-breach question cannot be. The reverse happens too: if the rollup job falls behind, the dashboard reads from the raw tier and rows scanned per series rise from 360 to 2160, a sixfold increase. When a shard node goes down, only the reads for the series on that shard are affected; since questions are asked per series, the blast radius is one shard. **What is given up:** percentile and threshold-breach questions on data older than seven days do not get a reliable answer. How many seconds a fluctuation from a month ago lasted cannot be asked in this design; the answer that can be obtained is either 0 or 58.5 times the true value. #### Summary - The metric stream makes per-sample cost decisive: 2,400,000 series, 240,000 samples/s on average, 480,000 at peak; the peak multiplier is 2, not the 3 of earlier cases, because the stream depends on the agent's scheduler. - The storage tier total is 31.50 TB; if the same data were kept raw it would be 393.57 TB, that is, 12.49 times as much. - Rollup reduces scanned rows by 60- and 300-fold, and stored bytes by 21.8- and 87.0-fold. - Deviation depends on the question type: 0.00 percent for average and max, 5.44 and 6.02 percent for p95, 100 percent for threshold-breach duration — the same question inflates 58.5- and 234.1-fold when asked with the max column. - This is why the raw tier is not a performance line item but an **answerability** line item: seven days of raw data costs 3.77 TB, and in exchange it defines the window in which sensitive questions can be answered. #### Next Step In this case, finding a record was easy: given a series ID and a time range, the rows to read sat in one place, in order. The next case removes that convenience. There, records sit on a two-dimensional plane and the question comes in the form "the ones near this point"; proximity has no sortable key, because every way of sorting two dimensions along a single axis pushes some neighbors far apart. The question becomes: how many candidate records must be examined to answer such a query, and how does that count depend on the chosen cell size. ### Location-Based Service Source: https://academia.sh/en/courses/case-studies/location-based-service The case of a query with no sortable key: comparing the proximity query against a flat scan, measuring on real data the candidate count a geohash scans, choosing cell size from the trade-off between candidate count and index lookups, and counting the results missed when a neighboring cell is not queried. In the previous case, finding a record was easy: given a series ID and a time range, the rows to read sat in one place, in order. This case removes that convenience. Records sit on a two-dimensional plane, and the question comes in the form "the ones near this point." Proximity has no sortable key: every way of sorting two dimensions along a single axis pushes some neighbors far apart, because two points that are adjacent on one axis can be far apart on the plane, and two points that are neighbors on the plane can be far apart on the axis. The solution is to divide the plane into cells and write a **geohash** into every record: records in the same cell carry the same key, and a **proximity query** scans the cells first, then the candidates inside each cell. The decision to be measured is cell size, and it carries a two-way trade-off: as the cell grows, the scanned candidate count rises; as the cell shrinks, the number of cells that must be queried rises. #### Constraints Functional requirement: registering a place, updating a moving object's location, returning the places within a given radius of a given point, and sorting the result by distance. Non-functional requirement, with numbers: the proximity query returns **all** records within the radius, the miss rate is **zero**; candidates scanned per query do not exceed **1000**; the design carries a peak of **1666.67** queries/s and **24,000** location updates/s. Scope narrowing: route finding, estimated time of arrival, map rendering, place ranking, and geographic projection transforms are not designed; because the region is small in this case, a planar approximation is used, and this is a model simplification. #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | KT1 | registered place | 40,000,000 | total points in the service area | | KT2 | daily active user | 6,000,000 | those making proximity queries | | KT3 | queries per user per day | 8 | search and map navigation | | KT4 | peak multiplier | 3 | ratio of peak hour to daily average | | KT5 | place record | 320 bytes | name, location, category, hours | | KT6 | moving object | 120,000 | carriers whose location changes continuously | | KT7 | location update interval | 15 s | the carrier's report frequency | | KT8 | density in a residential area | 20 places/km² | the model region's average | | KT9 | cost of one cell search | 20 candidates | ratio of an index lookup to a row scan | | KT10 | proximity radius | 1 km | walking-distance query | KT9 is this case's decision-driving assumption: choosing cell size depends on how many row scans one index lookup is worth, and this ratio varies by storage engine. #### Scale ```js // location/scale.mjs — scale calculation derived from the KT table; all of it is arithmetic const KT = { place: 40_000_000, user: 6_000_000, query: 8, peak: 3, placeBytes: 320, moving: 120_000, updateS: 15, density: 20, radiusKm: 1, candidateBudget: 1000 }; const DAY = 86_400; const queryS = (KT.user * KT.query) / DAY; const updateS = KT.moving / KT.updateS; for (const [name, d] of [ ["peak proximity queries/s", queryS * KT.peak], ["peak location updates/s", updateS * KT.peak], ["update / query ratio", updateS / queryS], ["place data GB", (KT.place * KT.placeBytes) / 1e9], ["radius area km2", Math.PI * KT.radiusKm ** 2], ["expected places in area", Math.PI * KT.radiusKm ** 2 * KT.density], ]) console.log(name.padEnd(26) + d.toFixed(2).padStart(14)); const flat = queryS * KT.peak * KT.place; console.log(`\nflat scan: ${KT.place.toLocaleString("en-US")} records per query -> at peak ` + `${flat.toExponential(2)} records/s`); console.log(`with a candidate budget of ${KT.candidateBudget}, peak is ${(queryS * KT.peak * KT.candidateBudget) .toLocaleString("en-US", { maximumFractionDigits: 0 })} records/s (1/${KT.place / KT.candidateBudget} of a flat scan)`); ``` ``` peak proximity queries/s 1666.67 peak location updates/s 24000.00 update / query ratio 14.40 place data GB 12.80 radius area km2 3.14 expected places in area 62.83 flat scan: 40,000,000 records per query -> at peak 6.67e+10 records/s with a candidate budget of 1000, peak is 1,666,667 records/s (1/40000 of a flat scan) ``` These numbers are in the **calculation** class, and three of them determine the design. First, data volume is small in this case: 40,000,000 place records take up 12.80 GB, nothing next to the terabytes of the previous three cases. The weight here is not in data volume but in the **number of records touched per query**. A flat scan means reading 66.7 billion records per second at peak; if the candidate count is held at 1000, the same load drops to 1,666,667 records/s, that is, to one forty-thousandth. Second, writes dominate reads: location updates are 14.40 times the queries, at a peak of 24,000/s. Third, a query's real answer is 62.83 records on average; the candidate budget is sixteen times that number, meaning the design accepts a degree of waste from the outset. #### Candidate Count Cell size can only be defended against a real distribution, because points do not spread uniformly. The model below places 200,000 clustered points on a 100 × 100 km plane, writes the geohash into an index for five cell sizes, and asks the same 200 queries of all of them. ```js // location/spatial.mjs — candidate count scanned by a spatial key on real data via node:sqlite. // The region is modeled as a 100x100 km plane (a planar approximation for a small region); the // points are clustered, the generator is hand-written, and the seed is visible. The model is // written as what it is. import { DatabaseSync } from "node:sqlite"; const N = 200_000, EDGE = 100, R = 1, QUERIES = 200, SEED = 20260802, CLUSTERS = 20, SEARCH = 20; const CELL = [0.5, 1, 2, 4, 8]; // cell edge length, km let state = SEED; const rand = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; const center = Array.from({ length: CLUSTERS }, () => [rand() * EDGE, rand() * EDGE]); function point() { // 60% around a cluster, 40% uniform if (rand() < 0.4) return [rand() * EDGE, rand() * EDGE]; const [mx, my] = center[Math.floor(rand() * CLUSTERS)]; const a = rand() * 2 * Math.PI, d = -Math.log(1 - rand()) * 3; return [Math.min(EDGE, Math.max(0, mx + d * Math.cos(a))), Math.min(EDGE, Math.max(0, my + d * Math.sin(a)))]; } const code = (x, y, c) => Math.floor(y / c) * 10_000 + Math.floor(x / c); const db = new DatabaseSync(":memory:"); db.exec(`CREATE TABLE place(id INTEGER PRIMARY KEY, x REAL, y REAL, ${CELL.map((_, i) => `h${i} INTEGER`).join(", ")}); ${CELL.map((_, i) => `CREATE INDEX place_h${i} ON place(h${i});`).join("\n")}`); db.exec("BEGIN"); const insert = db.prepare(`INSERT INTO place VALUES(?,?,?,${CELL.map(() => "?").join(",")})`); const points = []; for (let i = 0; i < N; i += 1) { const [x, y] = point(); points.push([x, y]); insert.run(i, x, y, ...CELL.map((c) => code(x, y, c))); } db.exec("COMMIT"); const queries = Array.from({ length: QUERIES }, point); const near = (q, x, y) => (x - q[0]) ** 2 + (y - q[1]) ** 2 <= R * R; let flatMatched = 0; // flat scan: the measure of correctness for (const q of queries) flatMatched += points.filter(([x, y]) => near(q, x, y)).length; console.log(`model: ${N} places, ${EDGE}x${EDGE} km, ${CLUSTERS} clusters, radius ${R} km, ` + `${QUERIES} queries, seed ${SEED}`); console.log(`flat scan: ${N} candidates per query, ${(flatMatched / QUERIES).toFixed(2)} matches\n`); console.log("cell km".padEnd(10) + "queried".padStart(12) + "candidates".padStart(12) + "hit rate".padStart(10) + "equivalent work".padStart(17) + "own cell".padStart(15) + "missed".padStart(11)); const WORK = {}; for (const c of CELL) { const i = CELL.indexOf(c), k = Math.ceil(R / c); let candidates = 0, matched = 0, cells = 0, own = 0; for (const q of queries) { const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c), list = []; for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) list.push((cy + dy) * 10_000 + cx + dx); cells += list.length; const s = db.prepare(`SELECT x, y FROM place WHERE h${i} IN (${list.map(() => "?").join(",")})`).all(...list); candidates += s.length; for (const r of s) if (near(q, r.x, r.y)) { matched += 1; if (Math.floor(r.y / c) === cy && Math.floor(r.x / c) === cx) own += 1; } } WORK[c] = [candidates / QUERIES, cells / QUERIES]; console.log(`${c}`.padEnd(10) + (cells / QUERIES).toFixed(0).padStart(12) + (candidates / QUERIES).toFixed(0).padStart(12) + `${((matched / candidates) * 100).toFixed(1)}%`.padStart(10) + (candidates / QUERIES + (cells / QUERIES) * SEARCH).toFixed(0).padStart(17) + (own / QUERIES).toFixed(2).padStart(15) + `${(((matched - own) / matched) * 100).toFixed(1)}%`.padStart(11)); } console.log(`\nmatch count is the same as the flat scan at every cell size (${(flatMatched / QUERIES).toFixed(2)}): ` + `neighboring cells are queried, so nothing is missed`); console.log(`equivalent work = candidates + queried cells x ${SEARCH} (KT9: the cost of one cell search)`); const [a1, h1] = WORK[0.5], [a2, h2] = WORK[1]; console.log(`point where 0.5 km and 1 km break even: one cell search = ${((a2 - a1) / (h1 - h2)).toFixed(2)} ` + `candidate scans; below this 0.5 km wins, above it 1 km wins`); ``` ``` model: 200000 places, 100x100 km, 20 clusters, radius 1 km, 200 queries, seed 20260802 flat scan: 200000 candidates per query, 443.95 matches cell km queried candidates hit rate equivalent work own cell missed 0.5 25 700 63.4% 1200 105.33 76.3% 1 9 864 51.4% 1044 181.41 59.1% 2 9 2123 20.9% 2303 322.27 27.4% 4 9 5251 8.5% 5431 381.24 14.1% 8 9 13611 3.3% 13791 415.85 6.3% match count is the same as the flat scan at every cell size (443.95): neighboring cells are queried, so nothing is missed equivalent work = candidates + queried cells x 20 (KT9: the cost of one cell search) point where 0.5 km and 1 km break even: one cell search = 10.25 candidate scans; below this 0.5 km wins, above it 1 km wins ``` These numbers are in the **measurement** class; the values depend on this run's seed and clustering parameters, the trend across columns does not. Because the model is clustered, 443.95 matches come out per query — seven times the 62.83 from the scale calculation, since queries are drawn from the same distribution as the points and cluster in dense regions. Three things follow. First, **the index does not break correctness:** match count equals the flat scan at every cell size, 443.95 — the geohash is a pre-filter, not an approximation; exact distance is computed separately for every candidate. Second, **the hit rate collapses with cell size:** 63.4 percent of scanned candidates are real matches at 0.5 km, only 3.3 percent at 8 km. The eight-kilometer cell scans 13,611 candidates; the 1000-candidate limit eliminates 2 km and above outright. Third, the shape of the trade-off: as the cell shrinks, candidates fall but queried cells rise — 25 cells and 700 candidates at 0.5 km, 9 cells and 864 candidates at 1 km. At KT9's ratio, equivalent work is 1200 versus 1044, and **1 km wins**. The break-even point can be written down too: the two sizes tie exactly when one cell search is worth 10.25 candidate scans — cheaper than that, 0.5 km wins; more expensive, 1 km does. The decision is a property of the storage engine, not of geography. #### Design The geohash is written into the record by **denormalization** (the Scaling the Data Layer course's Data Distribution topic) and an **index** is placed on it (the Databases curriculum's Relational Database Administration course, Index Types); together the two form the **spatial index**. The mechanics were established there — the only thing chosen here is the key's grain, 1 km. A category filter puts the key in a **composite index** instead (the same course, Composite and Partial Indexes): order (cell, category), since the cell is given by equality every query. The **sharding** key is not the geohash itself but its hash (the Data Distribution topic, Sharding). Sharding by the geohash directly would put every cell of a dense region on the same shard, turning the model's clustering straight into a hot shard; hash sharding spreads a query's 9 cells across different shards as nine parallel lookups — a latency cost paid because the peak 1666.67 queries must not pile up on one shard. A moving object's location lives in a separate **key–value store** (the same topic, Store Types): the key is the object ID, the value is the last location and cell. The 24,000 updates/s never touch the place table, since place records almost never change and sharing an index between the two workloads would tie its maintenance to the update rate. A place query's cell result is cached with **cache-aside** (the Cache Architecture topic); the staleness window is safe because places do not change, and moving objects never enter the cache. **Deliberately unused pattern: the materialized view.** Precomputing each cell's candidate list with its neighbors would reduce a query to one read, but every record would then appear in nine cells; the moving objects' 8000 updates/s become 72,000 writes, tripling the peak write rate for a gain of one index lookup. The second is the **claim check pattern** (the Resilience and Reliability course's Distributed Correctness topic): even in the worst case, the response body — 1000 filtered candidates at 320 bytes each — stays under a hundred kilobytes, so storing it and returning a claim check would only add a round trip. #### Eliminated Alternatives **Flat scan** satisfies the miss-rate limit perfectly with no index maintenance, but reads 40,000,000 records per query and rises to 66.7 billion records/s at peak — forty thousand times the candidate budget. A **coarse cell**, 8 km say, minimizes lookups (9 cells) but scans 13,611 candidates, thirteen times the 1000 limit; even 2 km, at 2123 candidates, is twice over. **Single-cell query** is the third alternative: one lookup instead of nine. The table's last two columns eliminate it: scanning only the query point's own cell at 1 km would find just 181.41 of the 443.95 matches, a **59.1 percent miss rate**. The rate falls as the cell grows (6.3 percent at 8 km) but never reaches zero, because the closer a query point sits to the cell's edge, the further the circle extends outside it. Single-cell query does not satisfy the miss-rate limit at any cell size; scanning the neighboring cells is not an optimization, it is a requirement. **Which limit changes and the alternative wins:** if the miss-rate limit were relaxed to "90 percent of results is enough," single-cell query at the 8 km cell would pass at 93.7 percent, and nine lookups would drop to one. #### Failure Behavior and What Is Given Up When a shard node goes down, some of a query's nine cells go unanswered. Two options exist, and the design picks the second: treat the incomplete answer as an error, or answer with the available cells and mark the result partial. The second is **graceful degradation** (the Resilience and Reliability course's Fault Isolation topic): its cost is measured — a missing cell violates the zero miss-rate limit, but a one-in-nine incomplete scan is far smaller than single-cell query's 59.1 percent miss rate. When the cache goes down, load lands directly on the index and the peak 1666.67 queries reach the store in full; this is why the candidate budget is set against peak rate, not response size. **What is given up:** 864 candidates are scanned per query, while the real answer is 443.95 records — a 51.4 percent hit rate, and the design accepts a scan that is roughly half wasted on every query. What this waste buys is a miss rate that stays at zero and a cell size that can be pinned to a single number. #### Summary - In this case volume is small (12.80 GB) but the query is expensive: a flat scan reads 66.7 billion records/s at peak, and a candidate budget of 1000 drops the same load to one forty-thousandth. - The geohash does not break correctness: match count equals a flat scan at every cell size (443.95), since the cell is a pre-filter and exact distance is computed separately for every candidate. - Candidate count grows fast with cell size: 700 at 0.5 km, 864 at 1 km, 13,611 at 8 km; the hit rate falls from 63.4 percent to 3.3 percent, and the 1000-candidate limit eliminates 2 km and above. - A small cell reduces candidates but increases cell count: 0.5 km is 25 cells and 700 candidates, 1 km is 9 cells and 864 candidates; equivalent work is 1200 versus 1044, and the two sizes break even when one cell search is worth 10.25 candidate scans. - Querying neighboring cells is not an optimization but a necessity: scanning only its own cell gives a 59.1 percent miss rate at 1 km, 6.3 percent at 8 km, and it does not reach zero at any size. #### Next Step The four cases in this topic stood on two sides of the same divide. The object storage service and the video service did the work **at write time**: the segment was placed, the bitrate ladder was produced, and reading only picked up what was ready. The metrics system and the location service did part of the work **at query time**: rollup was precomputed, yet the percentile question was answered at read time; the geohash was written in advance, yet the proximity query was rescanned every time. No case took on the two being needed **together in the same system**: if the same data had to be both fully processed in retrospect and answered within seconds of arriving, reconciling the two processing forms' results would be a separate design problem. The next lesson takes on that problem. ### Batch and Stream Processing Pipeline Source: https://academia.sh/en/courses/case-studies/batch-and-stream-processing-pipeline The closing case where two processing models are used together in the same system: how the watermark cuts off late-arriving data, how the stream path's first published result diverges from the batch path's recomputation, the divergence's closing curve, and the overhead cost of running both paths at once. Each of the previous four cases did its work either **at write time** or **at query time**; none needed both together in the same system. This case takes on that problem. The system counts an event stream in one-minute windows, and two paths are built: **stream processing** publishes a result within seconds, and **batch processing** recomputes the same window hours later from the log. The two produce different results from the same input, because the stream path must close a window and cannot see anything after that moment. The decision to close is made by the **watermark**: a bound expressed in event time that says how far the stream has advanced along its time axis, and a window closes once this bound passes it. Despite the similar name, it is distinct from the Application Layer and Service Interaction course's **version stamp** and the Resilience and Reliability course's **deployment stamp**: one marks a record's version, the other a deployment unit's identity, this one marks progress in time. A record that arrives after the watermark has passed is **late-arriving data**, and it does not enter the published count. #### Constraints **Functional requirement:** accept an event, count it in 60-second windows by event time, publish the result, and correct it with late-arriving data. **Non-functional requirement, as a number:** the first result is published at most 60 seconds after the window closes; its divergence does not exceed 30 per mille; the divergence drops below 0.5 per mille within 12 hours; the two paths' combined overhead does not exceed 3 times the raw input. **Scope reduction:** cross-stream joins, session windows, exactly-once processing guarantees, and a query language are not designed. #### Assumptions | Code | Assumption | Value | Rationale | |---|---|---|---| | TA1 | daily events | 900,000,000 | total produced by the edges | | TA2 | event record | 180 bytes | ID, event time, type, field | | TA3 | window size | 60 s | the finest grain of reporting | | TA4 | delay distribution | 0.94 uniform 0-5 s; 0.055 exponential 90 s; 0.005 exponential 4 hours | most edges are fast, very few are offline | | TA5 | peak factor | 3 | ratio of the peak hour to the daily average | | TA6 | batch run interval | 6 hours | four runs a day | | TA7 | log retention period | 30 days | history the recompute can reach | TA4 is the load-bearing assumption: the entire difference between the two paths comes from the delay distribution's tail. Without a tail, the two paths give the same result and there is no need for a second path. #### Scale ```js // pipeline-scale.mjs — the scale calculation derived from the TA table and the cost of running both paths at once const TA = { dailyEvents: 900_000_000, eventBytes: 180, windowSec: 60, peakFactor: 3, batchIntervalHours: 6, retentionDays: 30 }; const DAY = 86_400; const eventsPerSec = TA.dailyEvents / DAY; for (const [name, d] of [ ["avg events/s", eventsPerSec], ["peak events/s", eventsPerSec * TA.peakFactor], ["daily log GB", (TA.dailyEvents * TA.eventBytes) / 1e9], ["log TB (retention)", (TA.dailyEvents * TA.eventBytes * TA.retentionDays) / 1e12], ]) console.log(name.padEnd(22) + d.toFixed(2).padStart(14)); console.log(`\nbatch runs every ${TA.batchIntervalHours} hours; the scan window determines the workload:`); console.log("scan hours".padEnd(13) + "daily runs".padStart(14) + "batch multiple".padStart(15) + "combined total".padStart(15)); for (const W of [6, 12, 24]) { const runs = 24 / TA.batchIntervalHours; const mult = (runs * W) / 24; console.log(String(W).padEnd(13) + String(runs).padStart(14) + mult.toFixed(2).padStart(15) + (1 + mult).toFixed(2).padStart(15)); } ``` ``` avg events/s 10416.67 peak events/s 31250.00 daily log GB 162.00 log TB (retention) 4.86 batch runs every 6 hours; the scan window determines the workload: scan hours daily runs batch multiple combined total 6 4 1.00 2.00 12 4 2.00 3.00 24 4 4.00 5.00 ``` These numbers are in the **calculation** class. The lower table binds the last constraint: because the batch run executes every six hours, the same event is read more times as the scan window grows — once for a six-hour window, twice for twelve hours, four times for twenty-four hours. The stream path's single pass brings the combined total to 2.00 / 3.00 / 5.00 times, and the 3-times constraint eliminates the twenty-four-hour scan outright. #### The Difference Between the Two Paths The watermark delay determines both publish latency and divergence, and the two move in opposite directions. The model below builds no cluster; it draws delay from TA4's mixture and compares what the stream path counts against the batch path's exact count. ```js // two-paths.mjs — in-process model: the difference in the result the stream path and the // batch path produce over the same event set. No network, no cluster; the delay distribution is // TA4's three-part mixture, the generator is hand-written, and the seed is visible. IT IS A MODEL. const WINDOW = 60, WINDOWS = 120, EVENTS = 2000, SEED = 20260803; const MIX = [[0.94, "uniform", 5], [0.055, "exponential", 90], [0.005, "exponential", 14_400]]; // TA4 let state = SEED; const random = () => { state = (state * 1103515245 + 12345) % 2147483648; return state / 2147483648; }; function delay() { let u = random(), i = 0; while (i < MIX.length - 1 && u > MIX[i][0]) { u -= MIX[i][0]; i += 1; } const [, kind, p] = MIX[i]; return kind === "uniform" ? random() * p : -Math.log(1 - random()) * p; } const S = (x) => MIX.reduce((a, [w, kind, p]) => // independent of the run: tail probability a + w * (kind === "uniform" ? Math.max(0, 1 - x / p) : Math.exp(-x / p)), 0); const expectedLate = (L) => { // via a uniform position within the window let t = 0; for (let i = 0; i < 6000; i += 1) t += S(WINDOW + L - (i + 0.5) * (WINDOW / 6000)); return t / 6000; }; const total = WINDOWS * EVENTS; // arrival instant measured from the window's start const arrivals = Array.from({ length: total }, () => random() * WINDOW + delay()); console.log(`model: ${WINDOWS} windows x ${EVENTS} events = ${total}, window ${WINDOW} s, seed ${SEED}`); console.log(`delay mixture: ${MIX.map(([w, t, p]) => `${w}/${t}/${p}s`).join(" ")}\n`); console.log("watermark delay".padEnd(16) + "publish delay".padStart(16) + "late per mille".padStart(16) + "expected per mille".padStart(20)); for (const L of [0, 15, 60, 120, 300]) { const late = arrivals.filter((o) => o > WINDOW + L).length; console.log(`${L} s`.padEnd(16) + `${WINDOW + L} s`.padStart(16) + ((late / total) * 1000).toFixed(2).padStart(16) + (expectedLate(L) * 1000).toFixed(2).padStart(20)); } console.log(`\nthe divergence's closing (against the result published with a 60 s watermark delay):`); console.log("after window closes".padEnd(21) + "still missing".padStart(17) + "divergence per mille".padStart(22)); for (const [name, T] of [["1 hour later", 3600], ["6 hours later", 21_600], ["12 hours later", 43_200], ["24 hours later", 86_400]]) { const remaining = arrivals.filter((o) => o > WINDOW + T).length; console.log(name.padEnd(21) + String(remaining).padStart(17) + ((remaining / total) * 1000).toFixed(3).padStart(22)); } ``` ``` model: 120 windows x 2000 events = 240000, window 60 s, seed 20260803 delay mixture: 0.94/uniform/5s 0.055/exponential/90s 0.005/exponential/14400s watermark delay publish delay late per mille expected per mille 0 s 60 s 82.46 84.30 15 s 75 s 37.42 38.96 60 s 120 s 24.67 25.58 120 s 180 s 13.32 15.53 300 s 360 s 5.37 6.32 the divergence's closing (against the result published with a 60 s watermark delay): after window closes still missing divergence per mille 1 hour later 711 2.962 6 hours later 251 1.046 12 hours later 69 0.287 24 hours later 0 0.000 ``` The measured per-mille figure is a **measurement** tied to this run; the expected per-mille figure is a **calculation** independent of the run, derived from the mixture's tail probability. On all five rows, the two sit at the same order of magnitude. The upper table binds both constraints at once. At a watermark delay of 0, the divergence is 82.46 per mille; at 15 seconds, 37.42 — both break the 30-per-mille constraint; at 60 seconds, 24.67 per mille satisfies it. On the other hand, publish delay is window size plus the watermark, and the "at most 60 seconds later" constraint bounds the watermark to 60 seconds. The two constraints intersect at a single value: **watermark delay of 60 seconds.** The first row also corrects a misconception. At a watermark of zero, most of what is missed is not late-arriving data — it is an event that lands in the window's final seconds and arrives at normal speed; even some events with a delay under five seconds cross the boundary. At 15 seconds, this share disappears entirely, and the drop from 82.46 to 37.42 per mille comes from there. What is left of the divergence really does come from the tail. The lower table gives the closing curve: 2.962 per mille an hour later, 1.046 six hours later, 0.287 twelve hours later. The "drops below 0.5 per mille within 12 hours" constraint is not satisfied by a six-hour scan, but it is by a twelve-hour one. The workload constraint had already eliminated twenty-four hours; the closing constraint eliminates six hours. What remains is a **twelve-hour scan window**, and the total work comes out to exactly 3.00 times the raw input. #### Design The single source of truth is the event log, and both paths are its **projection** (the Scaling the Data Layer course's Read–Write Separation topic, Event-Sourced Design). The write model is the log, the read model is the window counts; separating the two is the same topic's **Command and Query Separation**. The table the batch path produces is a **materialized view** (the Data Distribution topic), and its refresh is not incremental — it is a recomputation of the twelve-hour window. Overwriting the published value must be **idempotent** (the Resilience and Reliability course's Distributed Correctness topic); the uniqueness key is the pair of window and path, so the result does not change even if the same run executes twice. The intake side sits on a **message broker** and **competing consumers** (the Application Layer and Service Interaction course's Queues and Workflows topic); the peak of 31,250 events/s is this layer's input, and when a consumer falls behind, **backpressure** (the Fault Isolation topic) propagates all the way to the edge. What the reader sees is **eventually consistent** (the Introduction to System Design course's Fundamental Properties topic), and the staleness window here is a measured number: 0.287 per mille. **Deliberately unused pattern: edge caching.** The edge caching from the Traffic Layer course's Entry Points topic is not placed in front of the published counts, because the same window's value keeps being corrected for twelve hours; opening a second staleness window at the edge would make the design's one measurable guarantee — the closing time — unmeasurable. The second is the **compensating transaction** (the Distributed Correctness topic): what the batch path does is not a rollback but an overwrite, because the log does not change. #### Eliminated Alternatives **Stream only** is the cheapest: one times the work, publish in 120 seconds. But the 24.67-per-mille divergence never closes; there is no second pass to correct it. **Batch only** is flawless on accuracy and its workload is one times. A window's result is published, in the worst case, six hours later: 360 times the publish constraint. **Widening the watermark** brings the divergence down to 5.37 per mille at 300 seconds and satisfies the 30-per-mille constraint with a single path; publish delay rises to 360 seconds, six times over the first constraint. **Which constraint changes and the alternative wins:** if the publish constraint is relaxed to 6 minutes, a single stream path suffices, and the second path's 2.00-times extra overhead drops. #### Failure Behavior and What Is Given Up When the stream path stops entirely, the system keeps responding: the batch path produces the correct result once every six hours, publish delay rises from 120 seconds to six hours, and the divergence drops to zero. This is an unusual form of **graceful degradation** (the Fault Isolation topic) — the dimension that degrades is not accuracy but freshness. The reverse happens when the batch path stops: publish stays at 120 seconds, but the 24.67-per-mille divergence freezes. Neither failure loses data, because both paths derive from the log, which is kept for thirty days. **What is given up:** the same event is processed twice. Total work is 3.00 times the raw input, and the same count is kept in two separate code paths; that the two agree is guaranteed not by sharing code but by a measurement. The first number given to the reader is also never final. #### Summary - The watermark is the decision to close a window; because its delay moves publish latency and divergence in opposite directions, it is squeezed between two constraints. - At a watermark of 0 / 15 / 60 / 120 / 300 seconds, the divergence is 82.46 / 37.42 / 24.67 / 13.32 / 5.37 per mille; the 30-per-mille constraint and the 60-second publish constraint intersect at a single value, 60 seconds. - At a watermark of zero, most of what is missed is not late-arriving data but a normal event that lands in the window's final seconds; at 15 seconds, this share disappears entirely. - The scan window is squeezed from both sides: twenty-four hours violates the workload constraint at 5.00 times, six hours violates the closing constraint at 1.046 per mille; twelve hours satisfies both at the margin. #### Course Wrap-Up Fourteen cases carried out the same six steps, and each was defended with a number. | Case | The number that decides the design | Patterns chosen | Eliminated alternative | What is given up | |---|---|---|---|---| | URL Shortening | read/write 100; 3859.3 guesses at seven characters | edge caching, cache-aside, sharding | counter-based generation: 1.0 guesses per hit | 300 s staleness window | | News Feed | fan-out on write 1691.87 / fan-out on read 56,570.71 work/s (33.44x) | threshold-based hybrid fan-out, message queue, backpressure | pure fan-out on read: 33.44x work | 203.63 box writes per post | | Search Suggestion | 266.67 bytes per query; 4.59 GB at depth 10 | prefix tree, task queue, push-based distribution | a flat sorted list: 6593 units at p99 | 10-character limit, 600 s freshness | | Content Distribution | request ratio 3.13, byte ratio 20.83; required hit rate 0.7440 | content delivery network, edge caching, versioned name | short-lived single cache: 0.6188 at 2 GB | atomicity of publishing | | Chat System | peak delivery 22,222.22/s; 1,250,000 connections, 25 nodes | uniqueness key, sequential convoy, offline mailbox | polling: 140.63x requests | chat-level parallelism | | Notification System | single-channel delivery 0.9590, 3.01 points below the threshold | cascading order, circuit breaker, bulkhead pattern | parallel fan-out: 2.78x calls | 30-60 s delivery delay | | Rate Limiter | fixed window 1200 (2.000x), sliding window counter 600 | sliding window counter, 0.2 s delayed synchronization | centralized counter: 40,000 touches/s | overshoot staying at 1.015x | | Ticketing and Inventory | demand 56x the allotment; drains in 0.179 s | pessimistic locking, allotment row | optimistic locking: 2409 valid rejections | 304,276 wait steps | | Payment Flow | notification-only 59.74 per mille; with polling 9.76 per mille | idempotency, 15-min reconciliation cycle, audit trail | synchronous verification: 75.77 per mille | 9.76 per mille and 30-min closure | | Object Storage | 1.0075 at a 2 MB part; erasure (10,4) factor 1.40 | valet key, idempotency, sharding, supervisor | three copies: 3.00x, 438 lost per year | 697,680 GB-month of extra storage | | Video Streaming | watched/uploaded 225; 8.91 percent not playable | priority queue, claim check, edge caching | eight rungs: 2.58x, 1854 processors | bandwidth utilization 64.9 percent | | Metrics Aggregation | 240,000 samples/s; 31.50 TB against 393.57 TB | wide-column store, time partitioning, materialized view | five-minute rollup only: 100 percent error at the threshold | percentile questions older than 7 days | | Location-Based | 864 candidates at a 1 km cell, 51.4 percent hit rate | spatial index, composite index, hash sharding | 8 km cell: 13,611 candidates | a scan roughly half wasted | | Batch and Stream | 24.67 per mille at a 60 s watermark; 0.287 per mille at 12 hours | watermark, event log and projection, idempotency | stream only: the divergence never closes | 3.00x work, two code paths | The table's rule is this curriculum's rule: **a design decision can be defended only together with a number and an alternative.** A decision given without writing down the number's class — assumption, calculation, measurement — cannot be argued, because the other side does not know what to ask for a reason: an assumption is defended with its rationale and sensitivity, a calculation with arithmetic that has been run, a measurement with its apparatus and seed. Seven courses built this rule piece by piece. Introduction to System Design turned qualities into numbers and set up the back-of-the-envelope estimate; the Traffic Layer took on how a request enters the system, the Application Layer and Service Interaction how work is split across services, and Scaling the Data Layer how data is distributed. Resilience and Reliability took on how failure is contained, and Performance Anti-Patterns and Monitoring showed how these are made visible. Case Studies combined all of them, one problem at a time, and asked for the same thing every time: turn the constraint into a number, write down the assumption, run the calculation, choose the pattern by name, take on one alternative, say what is given up. What comes after this is the reader's own design problem. The constraints there will not resemble these fourteen cases'; the only thing that will resemble them is the method. The first question is always the same: which number decides this choice, what class is that number, and which alternative was eliminated.