--- title: 'News Feed' source: 'https://academia.sh/en/courses/case-studies/news-feed' course: 'Case Studies' language: en updated: '2026-08-23T07:01:24+00:00' license: 'CC BY-SA 4.0' --- # 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.