11 — Design A News Feed System

This chapter covers the delivery half of a social feed at two-billion-user scale.

It works through four things:

• pricing the two ways a feed can be built, and which is cheaper and why;
• why the answer at this scale is a mix of both rather than either one;
• why one celebrity’s post is structurally undeliverable by the cheaper of the two, not merely slow;
• the pagination bug that makes a hundred million feed pages a day show the same post twice.

Every number below is arithmetic you can rerun, and the assumptions behind those numbers are stated before they are used.

The input and output. The input is two things: a stream of posts — one author writes one item — and a follow graph, the record of who subscribes to whom.

The output is, for one viewer, one page. A page is a list of roughly 20 posts in some order, plus a token that lets the client ask for the next 20. That is the whole contract. A request looks like GET /v1/feed?limit=20&cursor=... and the response is {items[], next_cursor}.

This chapter owns delivery. It does not own ranking. The scoring function that decides what order those 20 posts appear in — the multi-task heads, calibration, integrity demotion, exploration, the recency decay — is derived in ml 10 — Personalized News Feed. Every number here that touches ranking is cited from there rather than re-derived.

What is left is the harder half of the interview, and the half candidates skip: how a post gets from one author’s write into two billion viewers’ lists, and how a client reads page 3 of a list that is being mutated underneath it.

Three other chapters go deeper on machinery this one uses: chapter 02 for estimation templates, chapter 05 for how data is spread across machines, and chapter 06 for the store the per-viewer list lives in. You do not need any of them to follow this chapter; each idea is restated here at the point of use.

1. Framing: what decision, and what breaks

There is exactly one architectural decision in a feed and everything else is a consequence of it: when is a follower’s timeline materialized — at write time, or at read time? To materialize a list is to actually compute and store it, as opposed to leaving it as a query you run later.

The two options have names, and they are used constantly, so fix them now.

• Fan-out on write (also called push): the moment an author posts, the system writes a pointer to that post into a stored list belonging to each of the author’s followers. That per-viewer stored list is the inbox. Reading a feed is then just reading your own inbox — one lookup.
• Fan-out on read (also called pull): nothing is written to anyone on publish. The post goes only into the author’s own list — the outbox, or author timeline. When a viewer loads their feed, the system fetches the outbox of every account they follow and merges the results.

Fan-out is the word for one event turning into many operations; on write it fans out to followers, on read it fans in from followees. Push moves the work to publish time and pays per follower; pull moves the work to read time and pays per followee.

Get the choice wrong in one direction and a single celebrity post stalls the cluster. Get it wrong in the other and every feed load fans out to two hundred backend calls and inherits the worst delay of all of them.

What breaks, in the order it will break:

Three terms in that table need glosses before you go further.

p99 is the 99th percentile. Sort the day’s requests by how long each took; p99 is the time the slowest one percent exceeded. It is the number users actually notice, and it is the number a mean hides. p95 later in the chapter is the same idea at the 95th percentile — the time the slowest five percent exceeded.

A power-law distribution is one where a few items are enormously larger than the rest, so the mean tells you almost nothing about any individual sample. Follower counts are the textbook example: a median in the hundreds and a maximum in the hundreds of millions.

h is a cache’s hit rate — the fraction of reads the cache answers by itself. So 1 - h is the fraction that fall through to the database behind it.

State this decision at the start. The question is whether to materialize on write or on read. The answer is a hybrid split on the follower distribution, so price both to show why.

2. Requirements

What the feed must do, the targets it must hit, and the assumptions underneath them — separating the ones that would change the architecture from the ones that would only change the machine count.

Functional

• Publish a post (text, optional media, optional link).
• Fetch a viewer’s feed, ranked, paginated, infinite-scroll.
• Follow / unfollow, block, mute.
• No post appears twice in one session; a post the viewer has already seen is deprioritized.

Non-functional — these decide the design

Four terms from that table.

The critical path is the chain of work a user is actually sitting there waiting on. Anything off the critical path can be slow without anyone noticing, which is why the “on the critical path?” column shows up repeatedly later.

Eventual consistency means different copies of the data may disagree for a while, and will converge. Read-your-writes is the narrower promise that whoever just wrote something can immediately see it. That narrower promise matters here for a specific reason: an author who posts and does not see their own post concludes the app is broken.

A read replica is a copy of the database kept for serving reads. It lags the original by some milliseconds, which is exactly the mechanism by which read-your-writes gets violated.

The durability row is the one that makes the rest of the design tractable. The inbox is a cache of a query, not a system of record. If a machine loses it, you rebuild it from the post store and the follow graph.

That means the inbox needs none of quorum writes, vector clocks, or Merkle repair — three mechanisms for keeping replicas honest, derived in chapter 06. Losing an inbox entry costs one missing post in one feed, and the repair is a background rebuild, so paying for those guarantees would buy nothing.

The assumptions this design rests on

Every number below flows from six stated assumptions. State them before you spend them, because the interviewer’s favourite move is to change one and see whether the design follows or collapses.

Two words in that table need defining before the argument that follows.

A load-bearing assumption is one where being wrong changes the shape of the system rather than its size. Get a load-bearing assumption wrong and you rewrite the design; get a non-load-bearing one wrong and you buy different quantities of the same machines.

Zipf-skewed describes how post popularity is distributed: a small number of posts get most of the views, and the n-th most popular post gets roughly 1/n of the views the most popular one gets. It is the assumption the cache sizing in Deep dive 5 cache tiers and the hit rate economics rests on, and it is derived there.

The fan-out decision — the single architectural choice this chapter exists to make — is driven entirely by two of these six assumptions. It is worth being blunt about which two.

Load-bearing assumption 1: the read:write ratio

The read:write ratio decides which of push and pull is cheaper, and it decides it by itself. The break even is posting rate not follower count derives the break-even and it comes out as p < r: push wins exactly when an author posts less often (p times a day) than their followers read (r times a day).

At the assumed 0.2 posts and 5 reads per user per day, push wins by 5 / 0.2 = 25x.

Now invert the assumption. Imagine a network where people read once a day and post ten times — which is what a group-messaging or live-commentary product actually looks like. Then p = 10 and r = 1, pull wins by a factor of ten, the inbox disappears from the design entirely, and the whole of Deep dive 3 the inbox store is deleted.

This is not a tuning parameter. It determines the architecture.

Load-bearing assumption 2: the power-law follower tail

The power-law follower distribution is what forces the answer to be a hybrid rather than either pure design.

Suppose it were false — suppose every account had exactly the mean 400 followers. Then pure push would be correct and this chapter would be four pages long: 200 billion small writes a day, no burst, no threshold, no hot set.

The celebrity problem in Deep dive 2 the celebrity burst exists solely because a single sample from the tail is 250,000x the mean of 400. That is log10(250,000) = 5.4 orders of magnitude, and 5.7 orders against the median of 200 (3a the population). The hybrid in Where the threshold sits and what moving it costs exists solely to remove those samples from the push path.

Change the shape of the follower distribution and the hybrid stops being necessary; change the mean and you only buy more machines.

The other two that are load-bearing, briefly

The latency budget is load-bearing because 500 ms at p95 is what forbids the 200-way fan-in, independent of cost (The two totals side by side). Even if pull were free, it would still be too slow.

The failure-tolerance asymmetry is load-bearing because it is the licence to treat the inbox as disposable. That licence is what lets the inbox skip replication guarantees, stay cheap to shard, and be rebuilt from the post store after any loss.

The two that are not, and the direction they push

The peak multiplier and the per-entry byte count are the two you can be wrong about cheaply.

Doubling the peak factor buys machines and nothing else changes.

Doubling the entry from 24 B to 48 B doubles a storage figure that was never the binding constraint. It is worth walking that one out, because the obvious phrasing has it backwards. IOPS — input/output operations per second, the count of discrete disk reads or writes a device can perform — is the other candidate constraint on the inbox store.

today, 24 B entry      capacity needs 36 shards   write IOPS needs 3   ->  capacity binds by 36 / 3 = 12x
doubled, 48 B entry    capacity needs 72 shards   write IOPS needs 3   ->  capacity binds by 72 / 3 = 24x

Doubling the bytes doubles the capacity requirement and leaves the operation count exactly where it was, so the gap widens to 24x. A bigger entry moves the conclusion further from flipping, not closer.

To make IOPS bind instead, you would have to shrink the entry twelvefold, to 2 B — and there is nothing left to remove from a 24 B pointer. Both directions are safe, which is what “not load-bearing” means.

Getting a non-load-bearing assumption wrong costs money. Getting a load-bearing one wrong costs a rewrite.

3. Back of the envelope

The assumptions become the four totals the rest of the chapter spends: the population, the cost of push, the cost of pull, and the bytes on the wire — plus the one discipline that keeps those totals honest.

3a. The population

These are the traffic figures every later number is derived from, adopted wholesale from Scale and cost so the two chapters cannot disagree. DAU is daily active users, the count of distinct people who open the product on a given day.

DAU                          2,000,000,000
sessions/day                 8,000,000,000        (4 per DAU)
impressions/day              200,000,000,000      (25 per session)
posts created/day            500,000,000
median follows               200
mean followers per post      400

An impression is one post displayed to one viewer.

The last two lines are easy to confuse, and they point in opposite directions. Follows (200) counts how many accounts a viewer subscribes to — that is the pull cost, paid by the reader. Followers per post (400) counts how many people receive a given author’s post — that is the push cost, paid by the writer. They are different numbers about different people, and the rest of the chapter multiplies each by a different thing.

Now one figure this chapter adds that ml 10 does not need, because pagination is this chapter’s problem: how many separate page fetches those sessions generate.

page size                    20 posts
pages per session            25 / 20                  =  1.25
timeline reads/day           8,000,000,000 x 1.25     =  10,000,000,000
per second                   10,000,000,000 / 86,400  =  115,741
peak at 2.5x                 115,741 x 2.5            =  289,353
reads per user per day       10,000,000,000 / 2,000,000,000  =  5

A note on the second line: a session shows 25 posts and a page holds 20, so an average session asks for 1.25 pages — one full page plus a quarter of a second one. The 0.25 is the scroll, and it matters again in The offset bug derived where it becomes the count of pages that can be corrupted.

Each user reads their feed five times a day and posts a fifth of a time. The whole push-versus-pull argument is a comparison of those two numbers.

3b. Write amplification vs read amplification

Price both designs in operations per day, under a labelling discipline the rest of the chapter enforces. Amplification is the multiplier between one user-visible action and the number of internal operations it causes.

The block below prices push first, then pull, then divides one by the other. The tag in square brackets on each block is load-bearing and is explained immediately after.

PUSH   write amplification  =  posts x mean followers        [OFFERED LOAD]
       500,000,000 x 400                     =  200,000,000,000  inbox writes/day
       200,000,000,000 / 86,400              =  2,314,815  writes/s avg
       2,314,815 x 2.5                       =  5,787,038  writes/s peak

PULL   read amplification   =  timeline reads x follows      [OFFERED LOAD]
       10,000,000,000 x 200                  =  2,000,000,000,000  fetches/day
       2,000,000,000,000 / 86,400            =  23,148,148  fetches/s avg

ratio  2,000,000,000,000 / 200,000,000,000   =  10

Pull costs ten times as many operations as push, and unlike push every one of them is on the critical path. (The two pure designs priced prices pull at 1.6e12 from sessions alone; the extra 4e11 here is the scroll page, which only exists once you have committed to pagination. Same number, one more term.)

Offered load is not service capacity

Both totals above are demand. Neither is a fleet. Two different quantities get written in the same units — operations per second — and confusing them is the most common arithmetic error in this problem, so the bracket on each block is not decoration:

• Offered load is how much work arrives. It is what the world asks the system to do.
• Service capacity is how much work the machines you bought can perform.

State whether a rate is offered load or service capacity at the moment you derive it, and never divide one by the other without saying which is which.

Here is why that matters concretely. 5,787,038 writes/s is what the workload asks for at peak, so it is the wrong denominator for any question of the form “how long does this take.”

Suppose you provision a fleet at exactly 5,787,038 writes/s of capacity. At peak the fleet is 100% busy serving the ordinary workload, so the spare left over for anything extra is 5,787,038 - 5,787,038 = 0 writes/s. An extra burst of any size divided by zero spare is unbounded — the burst never drains at all.

Every “seconds to deliver” figure in this chapter therefore names a capacity first (Deep dive 2 the celebrity burst), and the gap between capacity and load is the only thing that does any work.

3c. Storage and bandwidth

Sizing the stored inboxes and the bytes leaving the building shows that bandwidth, not storage, is the number worth remembering.

The block has two independent parts. The first sizes the disks that hold every user’s inbox. The second sizes the network — how many bytes per second leave the building to serve feed pages — at two different traffic levels, and the difference between those two levels is the point of the section.

inbox    3 B recently-active users x 500 entries x 24 B  =  36 TB     [ml 10 8.2]
         x 3 replicas                                     =  108 TB

egress   20 posts x 1.5 KB hydrated                       =  30 KB per page

  at average  115,741 /s x 30,000 B  =  3,472,230,000 B/s  x 8  =  27.8 Gbps  [OFFERED LOAD, avg]
  at peak     289,353 /s x 30,000 B  =  8,680,590,000 B/s  x 8  =  69.4 Gbps  [OFFERED LOAD, peak]

Two terms there. Egress is data flowing out of the data centre to users, which is the direction cloud providers charge for. A post is hydrated when the system replaces a bare post identifier with the actual content — author name, text, media URLs, counts — which is what turns an 8-byte pointer into a 1.5 KB object.

The x 8 in the egress lines converts bytes per second into bits per second, because network capacity is quoted in bits and everything else here is in bytes.

Storage is sized at the average, network at the peak

The two egress rows are not interchangeable. This is the same discipline 3b write amplification vs read amplification insists on for load versus capacity, applied along a second axis: say which traffic level a rate is quoted at.

Storage accumulates, so it is sized at the average. 108 TB is a month’s bill, and a busy hour does not make the disks any bigger.

Network cards do not accumulate. A card either carries this second’s traffic or drops it; nothing gets made up later. So anything with a queue in front of it is sized at the peak.

The binding number for the fleet is therefore 69.4 Gbps, not 27.8. A server network card sustains about 1 Gbps standing, so:

69.4 Gbps / 1 Gbps per machine  =  70 machines' worth of network card

Seventy machines spent on nothing but serialized feed pages, before a single byte of media. Treat that as a floor rather than a fleet size — it assumes every card runs at 100% of its rating, which nobody provisions for.

The 27.8 Gbps average is the right figure for the egress invoice and the wrong one for the machine count. Quote it as the constraint and you understate the fleet by the peak factor, 2.5x.

Two things reduce it. Compressing the text payload with gzip takes a page from roughly 30 KB to roughly 10 KB, which is 9.3 Gbps average and 23.1 Gbps at peak. And media never touches this path at all — media is a URL in the payload, and the client fetches the bytes from a content delivery network, a fleet of caches sited near users (chapter 01).

4. API sketch

The request and response shapes carry three choices that are what a reviewer grades.

Five endpoints. The left column is the HTTP method and path, the right column after the arrow is what comes back. audience on the first line is the post’s visibility setting — public, followers-only, a named list.

POST   /v1/posts                     {text, media_ids[], audience}  -> {post_id, created_at}
GET    /v1/feed?limit=20&cursor=...  -> {items[], next_cursor}
POST   /v1/follow                    {target_id}
DELETE /v1/follow/{target_id}
GET    /v1/users/{id}/posts?cursor=  -> author timeline (the pull source)

The last line is the outbox from Framing what decision and what breaks: one author’s own posts in order, which is the thing a pull-based read would fetch two hundred of and merge.

Three things a reviewer looks for:

• cursor, never offset or page. An offset names a count of rows from the top of the list; a cursor names a position in it. The difference is derived in Deep dive 4 pagination that survives inserts and it is the single most common giveaway that a candidate has not built one of these.
• limit is capped server-side at 50 regardless of what the client asks, because the read path’s bandwidth is linear in it (3c storage and bandwidth) and an uncapped limit lets one caller multiply their cost to you for free — an amplification attack, which is what the rate limiter of chapter 04 exists to bound.
• next_cursor is opaque and signed. Opaque means the client is expected to send it back unmodified and not to parse it; signed means it carries a cryptographic tag so the server can detect tampering. It encodes a server-side snapshot id, and if clients could synthesize it they could pin themselves to arbitrary positions in other people’s snapshots.

5. Data model

Four stores, one deliberately tiny and one deliberately duplicated. For each, the first line is the key and what it maps to; the second line is how it is partitioned and what promises it makes. The two to look at hardest are inbox and graph.

posts        post_id (PK, k-sortable, ch 07)  author_id  created_at  body_ref  media[]  audience
             sharded by post_id · authoritative · never deleted, only tombstoned

inbox        user_id -> [ (post_id, author_id, created_at, flags) x <= 500 ]
             sharded by user_id · derived · capped · 72 h TTL

graph        follower_id -> [followee_id]   AND   followee_id -> [follower_id]
             both directions materialized; the reverse index IS the fanout job's input

counters     post_id -> (likes, comments, reshares)     separate store, different write pattern

Five terms from that block.

PK is the primary key, the column that uniquely identifies a row.

k-sortable means identifiers issued later sort after identifiers issued earlier, because the high bits of the id are a timestamp. Sorting by id is then very nearly sorting by time, which is what lets the cursor in The cursor and why a ranked feed needs a snapshot use the id as a tiebreak. The scheme that produces these ids is derived in chapter 07.

Sharded by post_id means rows are spread across many machines by hashing that column, so any one lookup touches exactly one machine. A shard is one of those machines and the slice of data it owns.

A post is never deleted, only tombstoned. A tombstone is a marker row meaning “this was deleted”. You keep it because in a replicated store an absent row and a deleted row look identical, so without the marker a lagging replica would push the data back.

TTL is time-to-live: an expiry after which an entry is discarded automatically, with no delete request needed.

Now the inbox entry, field by field. Add the right column and you get the 24 B that 3c storage and bandwidth already spent.

post_id       8 B      (64-bit k-sortable id, ch 07)
author_id     8 B
created_at    4 B      (unix seconds; 32 bits lasts to 2106)
flags         4 B      (source: in-network / group / out-of-network, seen bit, type)
                     ----
                       24 B

Note what is absent: the post body. An inbox entry is a pointer, not a copy.

Two consequences follow. First, size: 500 x 24 B = 12,000 B per inbox instead of 500 x 1,500 B = 750,000 B — 12 KB instead of 750 KB, a 62x difference. Second, and more important, edits: the post body lives in exactly one place, so editing or deleting a post once makes it change or disappear from every inbox that points at it — up to a hundred million of them for a head account — without touching any of them.

Why the follow graph is stored twice

The follow graph is stored in both directions on purpose. That is a denormalization — deliberately keeping the same fact in two shapes so that two different queries are each a single lookup, at the cost of writing it twice and having to keep the copies agreeing.

Two different jobs need two different directions. Fanout starts from an author and needs followee -> followers: who do I write to? The pull path starts from a viewer and needs follower -> followees: whose posts do I read?

Neither can be derived from the other cheaply at this scale. Inverting the edge list on demand means scanning every edge in the graph, and there are 2e9 users x 200 follows = 4e11 of them.

The cost of the duplication is a two-phase write on every follow: two rows in two indexes. The failure mode is a one-sided edge — A follows B according to one index and not the other — which a periodic reconciliation job fixes by scanning for disagreements.

6. High-level architecture

The whole system fits on one page, every box named so the deep dives can refer to it.

The diagram has two halves that meet nowhere except at the stores. The top half is the write path: what happens when someone presses send. The bottom half is the read path: what happens when someone opens the app. The two diamonds are the only branches in the system, and each one is the subject of a later deep dive.

flowchart TD
    subgraph W["Write path"]
        A(["Author posts"]) --> PS["Post service<br/>validate · assign id · persist"]
        PS ==>|"WRITE"| POSTS[("Post store<br/>sharded by post_id")]
        PS --> Q["Fanout queue<br/>partitioned by author_id"]
        Q --> FW["Fanout workers"]
        FW --> DEC{"author followers<br/>above threshold?"}
        DEC ==>|"no · 99.99% of authors · WRITE"| INBOX[("Inbox store<br/>LSM · 500 cap · 72 h TTL")]
        DEC ==>|"yes · head accounts · WRITE"| HOT["Head hot-set broadcast<br/>80 MB · in process"]
    end

    subgraph R["Read path"]
        C(["Feed request + cursor"]) --> ED["Edge / API gateway<br/>auth · rate limit"]
        ED --> SNAP{"cursor names<br/>a live snapshot?"}
        SNAP -.->|"yes · READ"| SS[("Snapshot store<br/>27.8 M sessions · 22 GB<br/>both figures derived in §10.2")]
        SNAP -->|no| BUILD["Build candidate set"]
        BUILD -.->|"READ"| INBOX
        BUILD -.->|"READ"| HOT
        BUILD --> RANK["Ranking service<br/>see ml 10"]
        RANK ==>|"WRITE"| SS
        SS --> HYD["Hydrate 20 posts<br/>content cache -> post store"]
        HYD -.->|"READ"| PC[("Post content cache<br/>225 GB · h = 0.89<br/>§11")]
        PC -.->|"READ on miss"| POSTS
        HYD --> OUT(["Page + next_cursor"])
    end

    style DEC fill:#bc6c25,color:#fff
    style HOT fill:#bc6c25,color:#fff
    style SNAP fill:#2d6a4f,color:#fff
    style RANK fill:#1d3557,color:#fff

The write path, box by box

An author presses send. The post service does three things: validate the post, assign it an id, persist it.

Persisting means writing the row to the post store. That store is sharded by post_id and is the only authoritative copy of a post anywhere in the system. Everything else downstream is derived and rebuildable.

The post service then drops a job onto the fanout queue. The queue is partitioned by author_id, which means all of one author’s fanout work lands in one ordered stream. Three properties that make it worse than the arithmetic explains why partitioning by author and not by follower is the choice that keeps one celebrity from blocking everyone.

Fanout workers consume that queue and ask the one question the hybrid turns on: is this author’s follower count above the threshold?

• Below threshold — 99.99% of authors. The worker appends a 24-byte pointer to each follower’s inbox store, the log-structured merge tree with the 500-entry cap and 72-hour expiry from Data model.
• Above threshold — head accounts. The worker does not push at all. The post joins the head hot-set broadcast: 80 MB of recent posts by the biggest accounts, replicated into the memory of every read host (Why the real threshold is follower count anyway).

The read path, box by box

A feed request + cursor arrives at the edge / API gateway — the front door that terminates the connection, authenticates the user, and applies the rate limit.

The gateway asks whether the cursor names a live snapshot. A snapshot is a frozen, already-ranked list built earlier in this session (The cursor and why a ranked feed needs a snapshot).

If yes, the page is served straight out of the snapshot store — 22 GB covering 27.8 M concurrent sessions. That is the cheap path, and it is the one most requests take.

If no, the system has to build a candidate set: read this viewer’s inbox, add anything relevant from the hot set, and hand the merged candidates to the ranking service. Ranking is the entire subject of ml 10, and from here it is one network call.

The ranked list is frozen into the snapshot store. Then the top 20 are hydrated — turned from pointers into full objects — against the post content cache (225 GB, hit rate h = 0.89, Deep dive 5 cache tiers and the hit rate economics), falling through to the post store on a miss. What leaves the building is a page + next_cursor.

How to read the arrows

Arrows in this diagram are not all the same kind of thing, so they are not all drawn the same way:

• a thick solid arrow is a write;
• a dotted arrow is a read.

That distinction matters most at the three stores the diagram touches twice. The post store is written by the post service and read by the content cache on a miss. The inbox store is written by fanout and read by the candidate builder. The snapshot store is written by the ranker and read by the gateway on a cursor hit.

Draw those identically and a derived index reads as just another pipeline stage — the direction of authority disappears from the picture.

Two nodes also carry numbers this section has not earned yet. The snapshot store’s 27.8 M sessions · 22 GB is derived in The cursor and why a ranked feed needs a snapshot, several hundred lines below; the content cache’s 225 GB · h = 0.89 in Deep dive 5 cache tiers and the hit rate economics.

How to read the colours

The palette here is chapter-local and deliberately not chapter 01’s. In that chapter, blue marks the authoritative copy of the data, green marks anything that takes load off the request path, orange marks a rung forced by something other than throughput, and red marks the step you cannot undo.

Here the same colours index this chapter’s deep dives rather than classify components:

• orange (two boxes) — the celebrity fix (Where the threshold sits and what moving it costs, Deep dive 2 the celebrity burst);
• green — the pagination fix (Deep dive 4 pagination that survives inserts);
• blue — the one thing this chapter does not own, ranking (ml 10).

One consequence of that scheme is worth naming rather than leaving as an accident. The post store is the only authoritative copy in the system, and it is left plain — as is the inbox. That is the point. §2 already established that the inbox is a derived index, and the post store is the one component nothing in this chapter makes difficult.

7. Deep dive 1: push, pull, and why the answer is neither

Pricing push and pull against each other produces a break-even that lands somewhere surprising — and the threshold you actually implement turns out to be a different quantity from the one the break-even names.

7.1 The two totals, side by side

Start by putting the two designs’ costs next to each other, because the comparison people remember is the wrong half of the argument.

The op-count ratio is 10x, and it is the less important half of the argument. The decisive half is latency.

Why a wide fan-in makes a rare delay into a common one

A straggler is one unusually slow call among many parallel ones.

Here is the mechanism, in three steps.

1. A pull-based feed read must wait on 200 independent backend fetches before it can answer anything.
2. A request that waits on 200 things is only as fast as the slowest of them. Its latency is the max over the fetches, not the mean.
3. So a delay that is rare per fetch becomes near-certain per request — you get 200 chances to draw a slow one.

Put numbers on it. Say each fetch has a p99 of 20 ms, meaning each individual fetch has a 1% chance of landing in that slow tail. Then each fetch has a 99% chance of being fast, and all 200 have to be fast for the request to be fast:

P(one fetch is fast)        =  0.99
P(no fetch is a straggler)  =  0.99 ^ 200  =  0.134
P(at least one straggler)   =  1 - 0.134   =  0.866

Eighty-seven percent of feed loads would contain a p99 event. A tail that is rare per call is the common case per request once you fan in wide enough. That one line kills pure pull on its own, independent of cost.

Pure push dies at the other end of the distribution, and for a different reason — not a mean that is too high but a tail with no upper bound. That is Deep dive 2 the celebrity burst.

7.2 The break-even is posting rate, not follower count

Almost nobody does this derivation, and it produces an answer that contradicts the rule of thumb everyone quotes.

Take one author with F followers who posts p times a day. Each follower reads their feed r times a day (3a the population fixed r = 5).

Count the operations each design costs for this one author. Under push, every post writes one row per follower, so the day’s cost is posts times followers. Under pull, every read by a follower fetches this author’s timeline once, so the day’s cost is reads times followers.

push cost/day  =  F x p        one inbox write per follower per post
pull cost/day  =  F x r        one timeline fetch per follower per read

push is cheaper  <=>  F x p  <  F x r
                 <=>      p  <  r          divide both sides by F

F cancels. The break-even does not depend on follower count at all. It depends only on whether the author posts more often than their followers read.

Substituting r = 5 reads/day gives the break-even for four kinds of account. The ratio in the right column is just the larger rate over the smaller one:

median author       0.2 posts/day   ->  push is 5 / 0.2       =  25x cheaper
active author       3 posts/day     ->  push is 5 / 3         =  1.7x cheaper
head account        5 posts/day     ->  pull is 5 / 5         =  1.0x, a tie
news wire           40 posts/day    ->  pull is 40 / 5        =  8x cheaper

So on raw operation count, the rule “push for small accounts, pull for big accounts” is not what the arithmetic says. It says: push for infrequent posters, pull for prolific ones. A 200-follower account posting forty times a day is a worse push candidate than a 10 M-follower account posting twice a week.

This is not a trick — The hybrid and the threshold derived arrives at the same place from the other side when it notes the threshold is really on followers x posts_per_day. What the cancellation shows is why: the follower term is common to both sides, so it can never appear in a cost comparison.

7.3 Why the real threshold is follower count anyway

The break-even above counts operations as if all operations cost the same. They do not, and the difference is entirely about whether the work can be shared.

A push write is private. F followers means F distinct rows on F different machines. None of that work is reusable by anyone else — each row exists for exactly one reader.

A pull fetch is public. All F followers read the same author timeline. The first reader populates a cache entry and every other reader is a cache hit. So the F x r figure counts logical reads against a working set of exactly one object.

That makes the real question: where does that one object live? Price the three options against the standing latency table from chapter 02.

A remote procedure call, or RPC, is a request to another machine over the network. It costs on the order of 500 microseconds even when nothing goes wrong. A read from the calling process’s own memory costs about 100 nanoseconds — 5,000 times less.

The third column multiplies the per-fetch cost by the 200-way fan-in.

The RPC is 5,000x the memory reference, so pull is only cheap when the pulled set is resident in the feed host’s own address space — and that is a RAM budget, which is a count of accounts, which is a follower threshold. That is the whole reason the threshold is expressed in followers: not because followers drive cost, but because followers are how you rank accounts for admission to a fixed-size RAM budget.

The hybrid and the threshold derived sizes that budget and I take its result as given rather than re-deriving it: ~50,000 accounts above 1 M followers at 50,000 x 50 x 32 B = 80 MB of in-process hot set.

7.4 Where the threshold sits, and what moving it costs

ml 10 leaves one question open — what happens if you move the threshold — and the answer is that the chosen value is pinned by a cliff rather than picked off a smooth curve.

Step 1: a model of the follower tail

To sweep the threshold you first need something you do not yet have: a way to say how many accounts sit above any given follower count. ml 10 gives you two points. You need a curve through them.

Use a Pareto tail, the standard model for power-law data. It says the count of accounts with more than F followers falls off as F raised to a negative power:

N(>F)  =  50,000 x (F / 1e6) ^ -a

Read that as: start from a known point — 50,000 accounts above one million followers — and every time you multiply the follower cut F, the count divides by that same factor raised to a. The exponent a controls how fast the tail thins. Larger a means a thinner tail, i.e. fewer giant accounts.

You have one unknown, a, and two facts from ml 10 to fit it against:

anchor A   N(>1e6) = 50,000                            [ml 10 8.2]
anchor B   top 5,000 accounts average 4 M followers    [ml 10 8.1]

Anchor A is already built into the model — it is the 50,000 constant. So a has to be chosen to reproduce anchor B.

Step 2: fit the exponent to anchor B

Anchor B talks about “the top 5,000 accounts”. Turn that into a follower cut. Call F5 the follower count above which exactly 5,000 accounts sit, and solve:

N(>F5)  =  5,000
50,000 x (F5/1e6)^-a  =  5,000        substitute the model
        (F5/1e6)^-a   =  0.1          divide both sides by 50,000
        (F5/1e6)^a    =  10           invert both sides
         F5/1e6       =  10^(1/a)     take the a-th root
         F5           =  1e6 x 10^(1/a)

Now you need the average followers of those top 5,000, because that is what anchor B actually states. A standard Pareto result gives the mean of everything above a cut:

mean above a cut of x   =   x  x  a / (a - 1)          (valid for a > 1)

Try a = 2.5 and substitute:

F5    =  1,000,000 x 10^(1/2.5)  =  1,000,000 x 10^0.4  =  2,511,886  followers
mean  =  2,511,886 x 2.5 / 1.5                          =  4,186,477  followers

Anchor B says 4,000,000. The fit gives 4,186,477, which is (4,186,477 - 4,000,000) / 4,000,000 = 4.7% high.

A single exponent reproduces both of ml 10’s stated anchors to within 5%. That makes a = 2.5 good enough to extrapolate one decade in either direction — and no further, because the extreme tail of a real follower graph is fatter than any single exponent can capture.

Step 3: cross-check the fit against a number it was not fitted to

A fit that reproduces the point you fitted it to proves nothing. Check it against a third quantity: the total number of follower-edges held by accounts above 1 M followers. ml 10 gives you enough to compute that two ways.

ml 10's buckets   5,000 x 4,000,000 + 45,000 x 1,100,000  =  69,500,000,000
Pareto integral   50,000 accounts x (1e6 x a/(a-1))       =  83,333,333,333
                  50,000 x 1,000,000 x 2.5 / 1.5

The second line is just “how many accounts are above 1 M” times “their Pareto mean”, using the same mean formula as step 2 with x = 1e6.

83.3e9 / 69.5e9 = 1.20, so the two are twenty percent apart — and the Pareto number is the higher one, which is the direction a fit that ignores the real graph’s top-end truncation should be wrong in. Good enough to sweep with.

Step 4: sweep the threshold

Now vary the threshold T and read off how much RAM the hot set costs. Each admitted account contributes 50 recent posts x 32 B = 1,600 B (Why the real threshold is follower count anyway).

The table is the answer; the block underneath is the arithmetic for each row, so you can check any line of it.

The (0.1), (0.3), (3) below are T / 1e6 — the threshold expressed in millions, which is what the model’s (F / 1e6) term wants.

100 k   (0.1)^-2.5 = 316.23     50,000 x 316.23    =  15,811,500  accounts
        15,811,500 x 1,600                         =  25,298,400,000  B  =  25.3 GB
300 k   (0.3)^-2.5 = 20.286     50,000 x 20.286    =  1,014,300  accounts
        1,014,300 x 1,600                          =  1,622,880,000  B   =  1.62 GB
3 M     (3)^-2.5   = 0.06415    50,000 x 0.06415   =  3,208  accounts
        3,208 x 1,600                              =  5,132,800  B       =  5.1 MB

Paging, in the 300 k row, is what an operating system does when a machine is short of memory: it evicts some of a process’s memory pages to disk and re-reads them on demand. The re-read is a page fault, and it stalls the thread for a disk access.

That costs roughly 100 microseconds, against the 100 nanoseconds Why the real threshold is follower count anyway priced for a resident read — a 1,000x loss on the single property that made the in-process hot set worth having in the first place. So “marginal” in that row means: the design becomes a bet on what else happens to be resident on the feed host, rather than something that holds by construction.

Step 5: what the sweep tells you

RAM scales as T^-2.5. Halving the threshold multiplies the memory by 2^2.5 = 5.7x.

That exponent is why 1 M is not an arbitrary round number. One decade lower, at 100 k, the hot set is 25 GB and no longer fits in a process — which destroys the exact property (Why the real threshold is follower count anyway) that made pull cheap. The threshold is pinned by a cliff, not chosen off a gradient.

And what the hybrid buys, taken from The hybrid and the threshold derived rather than re-derived here: 55% of all inbox writes removed and 100% of the catastrophic bursts, for 80 MB per host. Post-hybrid the push path carries 2.0e11 x 0.45 = 9.0e10 writes/day.

A caveat: “1 M followers” is not a universal number

The threshold depends on the criterion you pick, and this chapter picks RAM. Other chapters pick differently and land somewhere else, which is fine as long as you say which criterion you used.

The shape of nine minutes works a threshold of 50,000 followers from a delivery target instead: deliver a celebrity post within 60 seconds, using whatever capacity the fanout fleet has left over. Its fleet supplies 5,800 writes/s and carries 4,640 writes/s of peak load, so:

spare at peak   5,800 - 4,640           =  1,160  writes/s
ceiling         1,160 x 60 s            =  69,600  followers
ch 03 then sets the threshold at 50,000, below the ceiling, for headroom

(That chapter section is where every figure in this paragraph is derived. Ch 03 Step 4 only quotes the 50,000 and the 1,160-out-of-5,800 spare, so cite the derivation, not the wrap.)

Note the form of that expression. It is threshold = (capacity - load) x SLO_seconds, never load x SLO_seconds. An SLO is a service level objective — the target a team commits to.

Multiply the 2,320 writes/s average offered load by 60 instead and you get 139,200, which is double the real ceiling. That version silently assumes the fleet is idle and available to spend entirely on one post, which it is not.

The criterion sets the threshold, and there are three criteria in common use:

1. Delivery target against stated spare capacity — how ch 03 does it, appropriate for small fleets.
2. RAM budget — how this chapter does it, appropriate once the hot set has to be in process.
3. Queue depth — how production does it, where the threshold moves with current backlog.

Say which one you are using. A candidate who quotes a follower number without naming its criterion — or who names a delivery target without naming the capacity it runs against — has memorized an answer rather than derived one.

8. Deep dive 2: the celebrity burst

Pure push does not merely get expensive at the top of the follower distribution — it becomes structurally unable to meet the target, and the arithmetic misleads you if you use the wrong denominator.

The mean is 400 followers per post. The mean is not the problem. The problem is that a single sample from the tail dwarfs it.

Name the statistic when you quote the ratio, because the two on offer here differ by a factor of two. A 100 M-follower account is:

against the mean of 400      1e8 / 400  =  250,000x    log10(250,000)  =  5.4 orders of magnitude
against the median of 200    1e8 / 200  =  500,000x    log10(500,000)  =  5.7 orders of magnitude

Neither of those is “six orders of magnitude”, which is the number people reach for. The argument below runs on the mean, because the mean is what the write budget is a share of.

The write budget for one post

Define the write budget for one post as the day’s total inbox-write load divided by the day’s posts. By 3b write amplification vs read amplification that comes out to exactly the mean fanout, which is a useful sanity check that the two definitions agree.

This is a fair share of demand, not an allowance of capacity — the distinction 3b write amplification vs read amplification sets up, and it is about to matter.

budget per post   200,000,000,000 / 500,000,000   =  400  writes     [share of OFFERED LOAD]

Now price one post from a 100 M-follower account against that budget:

writes for one post                100,000,000
as multiples of the budget         100000000 / 400              =  250,000
as a share of the ENTIRE day       100000000 / 200000000000     =  0.0005   =  0.05 %

One post consumes a quarter of a million posts’ worth of write budget, and 0.05% of everything the platform will write today — for one person pressing send once.

8.1 How long it takes to deliver, and why that needs a capacity

Converting that burst into seconds is as much about method as about the answer: you cannot divide a burst by an offered load and get a duration.

“How many seconds does that burst take” is unanswerable from 3b write amplification vs read amplification alone, because everything in §3b is demand and a duration needs a rate the machines can actually supply.

So state the fleet. And state it as a provisioning decision — something you chose — rather than as a derived fact. Headroom is capacity bought above expected peak, and headroom is what any burst actually eats.

The block below does four things in order: names the peak load, picks a fleet 25% above it, subtracts to get the spare at two different load levels, then divides the burst by each spare.

peak offered load       (§3b)                       =  5,787,038  writes/s   [LOAD]
provision at peak + 25% headroom
  5,787,038 x 1.25        =  7,233,797.5  ->  7,233,798  writes/s   [CAPACITY]

spare at peak           7,233,798 - 5,787,038       =  1,446,760  writes/s
spare at average load   7,233,798 - 2,314,815       =  4,918,983  writes/s

delivery of one 1e8-write post, out of the spare:
  at peak               100,000,000 / 1,446,760     =  69.1  s
  at average load       100,000,000 / 4,918,983     =  20.3  s

Delivering that one post takes 69 seconds if it lands at peak and 20 seconds if it lands at the daily average. The target is 5 seconds, so it misses by 69.1 / 5 = 14x in the bad case and 20.3 / 5 = 4x in the good one.

Notice that the 69 s is a consequence of the 25% headroom you chose, not a property of the post. Change the provisioning and the number moves:

• Provision at exactly peak demand. Spare is zero, and the post never drains at all. Not “slow” — never.
• Provision to hit the 5 s target at peak. That needs 1e8 / 5 = 20,000,000 writes/s of spare, so a fleet at 5,787,038 + 20,000,000 = 25,787,038 writes/s. That is 25,787,038 / 5,787,038 = 4.5x peak demand, bought for one account.

That is the actual shape of the problem, and it is invisible if you divide by the demand figure.

The shortcut that flatters the answer

The tempting shortcut is 1e8 / 5,787,038 = 17.3 s. It is wrong, and wrong in the flattering direction.

5,787,038 is the load the fleet is already carrying at peak. Dividing by it describes a fleet doing no other work at all, which is not the fleet being designed. The honest range is 20.3–69.1 s at 25% headroom, and unbounded at zero headroom.

The conclusion the number exists to support — push cannot serve the head of the distribution — only gets stronger under the correct denominator, which is worth noticing: getting the method right did not rescue the design.

(The two pure designs priced quotes 33 s for the same post against a 3 M writes/s cluster. That denominator is a capacity, and it assumes the cluster is otherwise idle — same post, same 1e8 writes, a different and explicitly stated denominator.)

8.2 Three properties that make it worse than the arithmetic

The arithmetic above assumes bursts arrive politely and independently. They do not, for three reasons.

1. Bursts are correlated. Head accounts post in response to the same news, so tail events arrive together rather than spread out at random. The arithmetic above priced one 1e8 burst; in practice you get several at once.

2. The queue is first-in-first-out within each partition. That is exactly why the fanout queue is partitioned by author_id and not by follower. Partition by author and a celebrity’s enormous job only delays that celebrity’s own later posts. Get it backwards — partition by follower — and one celebrity’s job sits at the head of every partition it touches, blocking every ordinary post behind it.

3. Retries multiply the work. Suppose the job fails partway through, at 60 M of the 100 M writes, and retries from the start: that is 60,000,000 + 100,000,000 = 160,000,000 writes for one post. The fix is to checkpoint by follower-shard — record progress in units the job can resume from — rather than treating the whole post as one indivisible unit.

The hybrid removes the burst entirely rather than smoothing it, and that is the right kind of fix. Head accounts are never pushed at all, so the 1e8-write event does not exist anywhere in the system to be scheduled, throttled, or retried.

What to say: “Fanout-on-write is not slow for celebrities, it is structurally unable to serve a power-law follower distribution — the cost of one operation is unbounded above. You do not tune that, you remove those accounts from the path.”

9. Deep dive 3: the inbox store

The store that holds the materialized per-viewer lists raises three questions: what the write path costs, why the list is capped, and how many machines it takes — where the usual textbook answer is now wrong on current hardware.

9.1 What the write path actually costs

Start with the post-hybrid write volume, taking the 55% reduction from Where the threshold sits and what moving it costs as given.

push writes/day       90,000,000,000                          [OFFERED LOAD]
per second            90000000000 / 86400        =  1,041,667
bytes/s appended      1041667 x 24              =  25,000,008

Twenty-five megabytes a second of logical appends across the whole fleet. A single laptop could move that.

That number is small, and it is a trap. The fleet does not “move 25 MB/s”. It performs 1.04 million discrete random writes per second against 3 billion distinct keys, and the byte count is irrelevant next to the operation count.

A random write is one that lands at an unpredictable place on the device, as opposed to a sequential write that continues where the last one stopped. The same bytes cost a storage device far more when scattered, which is why the operation count and not the byte count is the figure to carry forward.

9.2 Why the list is capped at 500

Three independent arguments justify the cap, and the one everybody reaches for first is the weakest of them.

Argument 1: storage (the weak one)

This is the argument everyone gives. 500 entries x 24 B x 3 B active users = 36 TB, and without a cap the number is unbounded, because follow count is unbounded.

True, but 36 TB is not a hard number to buy. Keep going.

Argument 2: bandwidth (the one that binds)

The read path ships the whole inbox slice across the network to the ranking service. So every entry in the cap is bytes on a wire, on every single read, forever.

First a unit. A NIC is a network interface card. One gigabit per second is 1e9 / 8 = 125,000,000 bytes per second, which is the divisor in the block below — dividing a byte rate by 125,000,000 gives you the number of 1 Gbps cards it would saturate.

The block prices the capped design first, then the same traffic with the cap removed, each at both average and peak.

capped     500 x 24 B                      =  12,000 B per read
  at average  115,741 /s x 12,000  =  1,388,892,000 B/s  / 125,000,000  =   11.1  NICs   [avg]
  at peak     289,353 /s x 12,000  =  3,472,236,000 B/s  / 125,000,000  =   27.8  NICs   [peak]

uncapped, high-connectivity user at 3,000 entries        [ml 10 2.1]
           3,000 x 24 B                    =  72,000 B per read
  at average  115,741 /s x 72,000  =  8,333,352,000 B/s  / 125,000,000  =   66.7  NICs   [avg]
  at peak     289,353 /s x 72,000  = 20,833,416,000 B/s  / 125,000,000  =  166.7  NICs   [peak]

Peak is the row that sizes the fleet, for the reason 3c storage and bandwidth gives: a card carries a second’s traffic or it drops it.

Subtract the two peak rows: 166.7 - 27.8 = 138.9. Removing the cap costs 139 machines of pure network capacity at peak — 66.7 - 11.1 = 55.6, so 56 at the daily average — to move candidates that the ranker is going to discard anyway.

The magnitude of that depends on the peak factor you assumed. The ratio does not, and the ratio is the real argument: 3,000 / 500 = 6x the bytes on the wire, at every hour of the day, regardless of peak factor.

Bandwidth is linear in the cap, and nothing else in the system is. That makes the cap the cheapest dial you have.

Argument 3: amortization

Trimming the list back to 500 on every single append would double the write operation count — one append plus one trim, every time.

Trim lazily instead. Only trim when the list length exceeds cap + 100, which means one trim buys you the next 100 appends:

trims per append     1 / 100      =  0.01     ->  1% write overhead
worst-case length    500 + 100    =  600      ->  20% bandwidth overshoot, bounded

The overshoot is bounded at 600 entries, so the bandwidth argument above degrades by at most 600 / 500 = 1.2, and the write overhead drops from 100% to 1%. That is the trade.

The cap and the TTL are two different bounds

The 72 h TTL and the 500-entry cap both limit the inbox, and for most users the TTL binds first. A median user’s inbox receives 309 posts per 72 h (The inventory is small and that inverts the retrieval problem) — well under 500, so those entries expire before they are ever trimmed.

The cap exists for the high-connectivity tail, where 3,000 posts arrive in the same 72-hour window and the TTL never gets a chance to bind.

Whether truncating that tail costs recall is a ranking question, and it belongs to ml 10. The delivery-side statement is narrower and sufficient:

impressions per user per day   200,000,000,000 / 2,000,000,000  =  100
500 candidates / 100 per day                                    =  5 days of consumption

A user consumes 100 impressions a day, so 500 candidates is five days of maximum consumption. The 501st candidate is being retained for a session that will never reach it.

9.3 Shard count: capacity binds, and the IOPS argument no longer does

Derive the machine count two ways and the textbook derivation turns out to be a decade out of date.

IOPS means input/output operations per second — the count of discrete reads or writes a storage device can perform, as distinct from the bytes it can move.

There are two candidate constraints on how many machines the inbox needs: bytes to store, and operations to perform. Compute both and take the larger.

capacity      36 TB / 1 TB per box                      =  36    shards
write IOPS    1,041,667 /s / 500,000 IOPS per device    =   2.1  ->  3  shards

Capacity binds, by 36 / 3 = 12x. That is a change from how this problem is usually taught.

The textbook version divides the same 1,041,667 writes/s by 10,000 IOPS, gets 1,041,667 / 10,000 = 105 shards, and concludes you must buy 105 / 36 = 2.9x the disks you need for the bytes, purely to buy operations.

That conclusion depended on the 10,000 figure, and the 10,000 figure is a queue-depth-1 latency — the rate you get issuing one request at a time and waiting for each to finish — mistaken for a device ceiling. A modern NVMe solid-state drive (a flash device attached directly to the PCI Express bus rather than through an older disk protocol) sustains 500,000 to 1,000,000 random IOPS when many requests are outstanding at once. The two rows that will burn you flags that row for exactly this reason.

So do not reach for the IOPS argument here. On current hardware it does not reach.

The real argument for an LSM tree

The case for a log-structured merge tree at this scale is write amplification and space, not random-write throughput. Know which argument you are making, because only one of them survives the previous subsection.

An LSM tree is a storage engine that buffers writes in memory and flushes them to disk as sorted files, which background jobs then merge. The point is that every disk write it issues is sequential, even though the incoming writes were random.

Write amplification is the ratio of bytes actually written to disk over bytes the application asked to write. For an LSM it is roughly 10x, because the merging rewrites data several times over.

Ten times sounds bad until you price the alternative on this workload. A B-tree updates a row where that row already lives, and disks are written a page at a time, so appending one 24-byte inbox entry rewrites the whole page holding it. Its amplification is therefore set by page size over 24 B, which is far worse than 10x — and unlike the LSM’s 10x, none of it comes out sequential.

So the LSM converts 25 MB/s of random writes into 250 MB/s of sequential ones, and sequential is the thing devices are fast at (Lsm trees vs b trees):

sequential write need    25 MB/s x 10 write amplification  =  250  MB/s fleet-wide
per shard at 36 shards   250 / 36                          =  6.9  MB/s
device sequential                                          =  1,000  MB/s

Under 1% of one device’s sequential bandwidth. Capacity binds again and the shard count is 36, times 3 replicas, so 108 boxes. The read side is fine either way: 115,741 / 36 = 3,215 reads/s/shard against a device that does hundreds of thousands, and most of them are served from the memory tier below.

A memory tier in front of it

One more tier is worth deriving, because it removes most of those disk reads entirely.

The observation: in a typical session a viewer only ever reads the first two pages of their inbox. Two pages is 2 x 20 = 40 entries. So size a RAM tier holding just those:

40 entries x 24 B x 2,000,000,000 DAU   =  1,920,000,000,000  B  =  1.92 TB
at 256 GB/box                            1,920 GB / 256 GB       =  7.5  ->  8 boxes

Eight boxes of RAM hold the first two pages of every daily active user’s inbox.

The working set — the part of the data actually touched in normal operation — of a 108-box disk tier is 1.92 TB, because the tail of each list is only touched by deep scrollers.

Partition both tiers by user_id on a hash ring: a scheme that places both keys and machines on a circle of hash values, so a key belongs to the first machine clockwise from it. Adding a machine then moves only the keys between two adjacent points on the circle — 1/(N+1) of them — rather than the roughly 94% that a naive “hash modulo machine count” rehashes (chapter 05).

10. Deep dive 4: pagination that survives inserts

The most common way to paginate is broken for a feed — derivably so, with a probability attached — and the fix a ranked feed actually needs has two parts.

10.1 The offset bug, derived

Start with what OFFSET actually means, and why a feed violates the assumption it needs.

LIMIT 20 OFFSET 20 says: skip 20 rows from the head of the list, then give me the next 20. That is a count of rows from the top, and it is only stable if the top of the list is stable.

A feed’s top is not stable. It is being prepended to constantly.

Walk one concrete case. The client fetches page 1 and gets rows 0..19. The reader spends 30 seconds on it. During those 30 seconds, k new posts arrive at the head, pushing everything down by k. The client then asks for OFFSET 20, which returns rows 20..39 of the new list — and rows 20..39 of the new list are rows 20-k .. 39-k of the list page 1 came from.

So if k = 3, page 2 begins at old row 17, and old rows 17, 18, 19 were already on page 1.

k > 0  (inserts)   ->  the last k items of page 1 are served again   -> k duplicates
k < 0  (deletes)   ->  |k| items between the pages are never served  -> |k| skipped

Putting a probability on it

The bug only bites when k > 0, so the question is: what is the chance that at least one post arrives during the reader’s dwell?

Arrivals into one user’s inbox come from many independent authors, which makes them well modelled as a Poisson process — events arriving independently at some average rate lambda. The Poisson process has one property this needs: the chance of no event at all in a window of length t is exp(-lambda t).

So P(page is corrupted) = 1 - exp(-lambda t). All that remains is lambda and t.

lambda comes from the The inventory is small and that inverts the retrieval problem inventory model, converted from posts-per-72-hours to posts-per-second. The / 3 / 86,400 is “divide by 3 days, then by seconds per day”:

median user   309 posts / 72 h                 309 / 3 / 86,400   =  0.00119  /s
p95 user      1,380 posts / 72 h               1380 / 3 / 86,400  =  0.00532  /s
dwell between page requests                                       =  30  s

Dwell is how long the reader spends on a page before asking for the next one, and it is what sets t.

For page 2, t is one dwell: 30 s. For page 5 it is cumulative — the clock runs from when the list was first read, so t = 5 x 30 = 150 s. That cumulative growth is the whole reason the bug gets worse the further you scroll. Substituting both rates at both windows:

median, page 2    lambda t  =  0.00119 x 30   =  0.0357   ->  1 - e^-0.0357  =  3.5 %
p95,    page 2    lambda t  =  0.00532 x 30   =  0.1596   ->  1 - e^-0.1596  =  14.8 %
p95,    page 5    lambda t  =  0.00532 x 150  =  0.798    ->  1 - e^-0.798   =  55.0 %

By page 5, more than half of a well-connected user’s page loads contain a duplicate.

The corruption probability grows with cumulative dwell, so the deeper someone scrolls the worse it gets. That is precisely backwards from what the product wants, since deep scrollers are the engaged users.

The population number

Blend those per-user rates to roughly 5% and multiply by how many pages are exposed to the bug. Page 1 is never corrupted — there is nothing before it — so only the scroll pages count, and 3a the population already counted those: 1.25 pages per session means 0.25 scroll pages per session.

scroll requests/day    8,000,000,000 sessions x 0.25   =  2,000,000,000
corrupted pages/day    2,000,000,000 x 0.05            =    100,000,000

A hundred million visibly wrong pages a day, from a clause that looks correct in a code review.

10.2 The cursor, and why a ranked feed needs a snapshot

The fix has two halves: one that works for a time-ordered list, and a second that a ranked list also needs.

Half one: the keyset cursor

For a chronological list — one sorted newest-first by time — the fix is a keyset cursor. Instead of naming a count of rows to skip, name a position in the sort order and ask for everything after it.

The query below is the whole idea. The line to look at is the WHERE clause with the comment on it: that is the cursor, and it is a comparison against values rather than a row count.

SELECT ... FROM inbox
 WHERE user_id = ?
   AND (created_at, post_id) < (?, ?)      -- the cursor
 ORDER BY created_at DESC, post_id DESC
 LIMIT 20

Why that fixes it: a new post has a created_at above the cursor value, so the < comparison excludes it. Inserts at the head are simply invisible to a cursor pointing lower down. Deletes below the cursor shift nothing, because nothing is being counted.

The keyset cursor also indexes better. Build a composite index on (user_id, created_at, post_id) — one index over three columns in that order — and it serves both the filter and the sort from a single scan of one contiguous range (Composite covering and hash indexes). Compare OFFSET 20000, which must read and throw away 20,000 rows before it can return the first one.

Half two: why ranked feeds need more

For a ranked feed the keyset cursor is not enough, and this is the part interviewers actually probe.

The problem is the sort key. For a chronological feed the sort key is created_at, which never changes once a post is written. For a ranked feed the sort key is a model score, and a score is not stable. It moves with:

• the model version, which is redeployed;
• elapsed time, through the recency decay (Recency derived rather than assumed);
• the viewer’s own state — which page 1 just changed, by generating impressions.

So a post can legitimately move from rank 25 to rank 15 between two requests. A cursor of the form (score, id) < cursor compares against a score that has since changed, and the post crosses the boundary a second time and is served twice. Same bug, different cause.

The fix: freeze the ranked list once per session and paginate the frozen copy. That frozen list is the snapshot, and the cursor becomes an index into it — a plain integer position.

Freezing costs memory, so price it. Concurrent sessions come from Little’s law in its simplest form: sessions per day times how long each lasts, divided by seconds in a day.

concurrent sessions   8,000,000,000 x 300 s / 86,400   =  27,777,778
snapshot payload      100 post ids x 8 B               =  800  B
snapshot store        27,777,778 x 800                 =  22,222,222,400  B  =  22.2 GB

Twenty-two gigabytes of Redis — an in-memory key-value store — buys correct pagination for the entire platform. That is less than one 256 GB box (Shard count capacity binds and the iops argument no longer does) against a bug that otherwise shows up on a hundred million pages a day.

Give each snapshot a TTL of the session length, 300 s, extended each time it is used. An expired cursor means “rebuild from the top”, which is also exactly the right behavior for a client that was backgrounded for an hour.

Two product details that make freezing acceptable

New posts arriving mid-session do not get injected mid-list. They go behind a “12 new posts” pill, which loads a fresh snapshot when tapped. The frozen list is not a limitation you apologize for in the interview; it is the behavior users already expect from every feed they use.

A seen-set keeps the freeze honest across sessions. Snapshots expire, so without one, the next session can re-show what the last one showed.

Remembering exactly which posts a user has been shown is expensive, so use a Bloom filter: a compact bit array that answers “have I seen this?” with either “definitely not” or “probably yes”. It never misses a true member, but it occasionally produces a false positive — claiming to have seen something it has not.

The memory cost per element for a target false-positive rate f is -ln(f) / ln(2)^2 bits. At f = 0.01:

bits per element   -ln(0.01) / ln(2)^2                 =  9.6  bits
bloom total        2e9 users x 2,000 recent ids x 9.6 bits / 8   =  4.8 TB
exact set          2e9 users x 2,000 recent ids x 8 B           =  32  TB

What the 1% buys and costs: 4.8 TB instead of 32 TB, at the price of wrongly suppressing 1% of eligible posts. Against a 500-candidate pool, losing 5 candidates is invisible. That is the right trade.

The two behaviors, in code

page is the correct implementation, indexing into a frozen list. offset_bug reproduces the failure and returns exactly the items that get served twice, so the assertions below can name them.

page has to enforce the two properties Api sketch claims for it, not merely describe them. §4 says the cursor is opaque and signed and that limit is capped server-side at 50, and a cursor that arrives as -5 or a limit that arrives as -1 is precisely the case those two sentences exist to cover. Left unenforced, page(snapshot, -5) slices from the end of the list, returns an empty page, and hands back a forward cursor of 15 that the client will happily send again; page(snapshot, 0, -1) returns 99 of the 100 items in one page. Both are the amplification the server-side cap is for, and both are checked below.

from typing import Optional

MAX_LIMIT = 50          # §4: the cap lives on the server, not in the request


def page(snapshot: list[int], cursor: Optional[int], limit: int = 20):
    """Cursor is a position in a frozen list, so inserts elsewhere cannot shift it.

    `cursor is None`, never `if not cursor`: 0 is a real position.
    """
    if not isinstance(limit, int) or limit < 1:
        raise ValueError("limit must be a positive integer")
    limit = min(limit, MAX_LIMIT)                    # capped HERE, not in the schema
    if cursor is not None and (not isinstance(cursor, int)
                               or not 0 <= cursor <= len(snapshot)):
        raise ValueError("cursor is not a position in this snapshot")
    start = 0 if cursor is None else cursor
    end = min(start + limit, len(snapshot))
    return snapshot[start:end], (end if end < len(snapshot) else None)


def offset_bug(before: list[int], inserted: int, offset: int, limit: int = 20):
    """Reproduce the duplicate: k inserts at the head repeat the last k of page 1."""
    after = list(range(-inserted, 0)) + before
    page1 = before[:limit]
    page2 = after[offset:offset + limit]
    return sorted(set(page1) & set(page2))          # non-empty exactly when inserted > 0


assert offset_bug(list(range(100)), inserted=3, offset=20) == [17, 18, 19]
assert offset_bug(list(range(100)), inserted=0, offset=20) == []

# The correct implementation is the one the prose recommends, so assert on it.
snap = list(range(100))
assert page(snap, None) == (list(range(20)), 20)
assert page(snap, 0) == (list(range(20)), 20)        # 0 is a position, not "unset"
assert page(snap, 80) == (list(range(80, 100)), None)
assert page(snap, 100) == ([], None)

# A hostile cursor. Unguarded this returns ([], 15): an empty page and a
# forward cursor the client will send back.
for bad in (-5, 101, "20", 1.5):
    try:
        page(snap, bad)
        raise AssertionError(f"cursor {bad!r} was accepted")
    except ValueError:
        pass

# A hostile limit. Unguarded, -1 returns 99 items in one page and 10,000
# returns the whole snapshot, which is the amplification §4's cap exists to stop.
for bad in (0, -1):
    try:
        page(snap, 0, bad)
        raise AssertionError(f"limit {bad!r} was accepted")
    except ValueError:
        pass
items, _ = page(snap, 0, 10_000)
assert len(items) == MAX_LIMIT

One line in there is worth pointing at, because the sibling chapter gets the same shape wrong. cursor is None, not if not cursor. Here the two happen to agree — position 0 and “no cursor” both start at the top — so falsiness would be harmless by luck rather than by design. In The dedup mechanism both ends the identical construct is applied to a sequence number, where 0 is a real value that is not equivalent to “nothing yet”, and a truthiness test there silently disables gap detection for the life of the conversation. Test integers against None, not against zero, and the habit costs nothing on the day it is not needed.

11. Deep dive 5: cache tiers and the hit-rate economics

Four caches need sizing, and the sizing yields the one result worth carrying out of the chapter: buying more cache pays off faster than linearly, up to an exact point at which that argument stops being honest.

Four tiers, each justified by a different constraint. Read the table as a chain: a miss at one tier falls through to whatever the last column names. L0 and L1 have already been derived earlier in the chapter; L2 is the one this section works out.

11.1 Sizing L2 from the popularity curve

L2 is the tier worth deriving, because its sizing rests entirely on an assumed popularity distribution and the answer is counter-intuitive.

Post popularity is close to Zipf with exponent s = 1: a heavily skewed distribution in which the n-th most popular item gets about 1/n of the traffic the most popular one gets. Word frequencies, city sizes and post views all behave this way empirically.

For s = 1 there is a standard result. The share of accesses covered by caching the top k items out of N is:

h  =  ln(k) / ln(N)

That is the same result chapter 08 writes as log10(m)/8 for its 1e8-link corpus — the base of the logarithm cancels, so it does not matter which one you use.

Two inputs. Live inventory is N = 1.5 B posts (The index turns over 33 per day and that kills nightly rebuilds), and a hydrated post object is 1.5 KB. Now try caching 1% of the corpus and then 10%:

ln(1.5e9)                                          =  21.129

top 1%    k = 1.5e7    ln(1.5e7) / ln(1.5e9)   =  16.524 / 21.129  =  0.782  hit rate
                       15,000,000 x 1,500      =  22,500,000,000  B  =  22.5 GB

top 10%   k = 1.5e8    ln(1.5e8) / ln(1.5e9)   =  18.826 / 21.129  =  0.891  hit rate
                       150,000,000 x 1,500     =  225,000,000,000 B  =  225 GB

Ten times the memory moved the hit rate from 78.2% to 89.1% — only 11 points. That looks like poor value. It is not, and the next subsection is why.

11.2 Why the returns do not diminish

Apply the 1/(1-h) result from chapter 02. If the cache answers a fraction h of reads, the store behind it sees 1 - h of them, so the reduction in load on that store is 1 / (1 - h):

h = 0.782    1 / (1 - 0.782)  =  1 / 0.218  =    4.59x   reduction in post-store reads
h = 0.891    1 / (1 - 0.891)  =  1 / 0.109  =    9.17x
h = 0.990    1 / (1 - 0.990)  =  1 / 0.010  =  100x

Ten times the RAM (22.5 GB -> 225 GB) doubles the leverage. Eight times again gets you 100x.

Here is why the returns do not diminish, in two steps. Substitute the Zipf hit rate into 1 - h:

1 - h  =  1 - ln(k)/ln(N)  =  (ln(N) - ln(k)) / ln(N)  =  ln(N/k) / ln(N)

so     1/(1-h)  =  ln(N) / ln(N/k)

That expression blows up as k approaches N, because ln(N/k) goes to zero. Said in words: the hit rate climbs only with the logarithm of the memory you buy, but the load falls as the reciprocal of what is left over — and the reciprocal wins the race.

11.3 Where the argument stops being honest

Push it to h = 0.99 and see what you actually have to buy. Solve ln(k) / ln(N) = 0.99 for k:

ln(k)   =  0.99 x 21.129       =  20.918
k       =  e^20.918            =  1,215,000,000  posts   (81% of live inventory)
bytes   =  1,215,000,000 x 1,500  =  1,822,500,000,000  B  =  1.82 TB

At 99% the “cache” holds 81% of the corpus, which is not a cache. It is a second copy of the store with no durability and a hard invalidation problem — every edit and delete now has to be chased into it.

That is where the economics actually stop: not at a cost curve, but at the point where the thing stops being a cache at all. 225 GB and h = 0.89 is the defensible answer.

Note what the whole argument rests on. The Zipf skew is an assumption, not a law.

Test it by assuming the opposite. Under uniform popularity, caching 10% of 1.5 B equally-read posts gives exactly h = 0.10, and a leverage of 1 / 0.9 = 1.11x. No amount of memory would ever produce the 9.17x, because there is no head of the distribution to catch.

The cache tier is an assumption cashed in. That is why the first thing to measure in production is the actual popularity curve.

11.4 The same leverage, running backwards

Every leverage figure above is also a failure mode, and it is worth seeing the arithmetic from that side.

Load on the post store is (1 - h) of the read rate. So losing the cache tier does not raise that load gradually — it multiplies it by 1/(1-h) the instant the tier goes away. Losing L2 takes the post store from 10.9% of the 115,741 reads/s to 100% of them:

warm   115,741 x 0.109   =   12,616  reads/s to the post store
cold   115,741 x 1.000   =  115,741  reads/s
step   115,741 / 12,616  =  9.17x    instantly, not gradually

A cache is warm when it holds the entries its traffic will ask for, and cold when it is empty — after a restart, a deploy, or a flush. Cache warming is populating it before it takes live traffic, by replaying recent keys into it rather than letting real users pay for every miss.

Restart an L2 node cold and the post store takes a 9x step function, not a ramp. Three fixes, in order of how much they buy:

• Consistent hashing, so losing one node moves 1/N of the keys rather than all of them (chapter 05). This turns a fleet-wide step into a fractional one.
• Request coalescing, also called single-flight: when n requests miss on the same key at the same moment, send one read to the origin and make the other n-1 wait for its answer. Without it, a cold key attracts n identical reads.
• Staggered restarts, so the whole tier never goes cold at once.

12. Bottlenecks and scaling

Every limit the design runs into appears below with the number at which it binds and the two moves that relieve it, in sequence: apply “First fix”, and when that is exhausted, apply “Then”.

Two terms from that table. A whale, in the “Feed read fan-in” row, is a viewer who follows an unusually large number of accounts, so their read fan-in is far above the median — the mirror image of a celebrity, who has an unusual number of followers. A field mask, in the “Egress bytes” row, is a request parameter naming which fields the client actually wants, so the server can omit the rest.

The last row is worth saying out loud: engagement counters are a different system with a different write pattern, and they do not belong in the post row. A hot post takes thousands of increments per second against one key. That is a contended-counter problem — many writers racing to update the same value, derived in Where the counter lives and the race that makes incr expire wrong — and it is not a feed problem.

13. Failure modes

Each failure below comes with how wide the damage spreads, the signal that catches it, and the mechanism that contains it.

Blast radius is how far one component’s failure reaches — sometimes a fraction of users, sometimes which part of the product stops working. Detection is the metric you would put an alert on, and it carries as much weight as the fix: a failure nobody can see is a failure nobody contains.

Four terms from that table.

To autoscale on lag, in the first row, is to add fanout workers automatically when the queue’s backlog grows, rather than waiting for a human to notice. To shed load, in the same row, is to deliberately stop serving some requests the usual way so the rest keep working — here, moving the affected users off their stale inboxes and onto a pull-on-read path until fanout catches up.

QPS in the third row is queries per second, the request rate the origin sees. Reverse-chronological in the last row means newest first, with no model involved at all.

The row worth volunteering before you are asked

That last row is the answer to “what happens when the machine-learning tier fails”, and reverse-chronological is a complete answer. The feed’s dependency on ranking is a quality dependency, not an availability one, and a design where the ranker is on the critical availability path has confused the two.

The same shape shows up in three other rows, and it is what makes the table worth walking in an interview. Every mitigation above gives up a property rather than the service. A lost snapshot store resets in-flight scrolls to the top, and the feed still loads. A stale hot set falls back to a pull RPC, which is slower and still correct. A dead inbox shard falls back to the post store and the follow graph, which is slower and still complete. Name the property you are trading away, and the failure stops sounding like an outage.

14. Alternatives rejected

Each design that was seriously on the table appears with the specific number that disqualified it — the form an interviewer wants, because it proves the choice was made rather than defaulted into.

A B-tree, in the last row, is the sorted tree index a traditional database uses. It updates a row where that row already sits, so a 24-byte inbox append dirties and rewrites a whole page. That is the write-amplification argument. It is a different claim from the operation-count one Shard count capacity binds and the iops argument no longer does retires, and only one of the two still holds on current hardware.

15. Interviewer pushback

The same material one last time, as spoken answers — the voice you would actually use under questioning.

Every answer below follows one shape: name the mechanism, give the number, then say what the number is measured against — a capacity, an offered load, a ratio. The third part is the one candidates drop, and dropping it is what turns 69 seconds into 17.

“Why not just push everything and add machines?”

Because the cost of one operation is unbounded above, not because the average is too high. The average is 400 writes per post and that is fine. The problem is that a single post can be 1e8 writes, which is 250,000 times that. Machines buy capacity, and what a burst spends is capacity minus the load already on the fleet: at 25% headroom over peak that spare is 1.45 M writes/s and the post takes 69 s against a 5 s target, and to make it 5 s I would have to provision 4.5x peak demand for one account. Adding machines moves the headroom term while leaving the burst exactly as violent. The hybrid removes the unbounded case rather than provisioning for it.

“Your break-even says posting rate, but you threshold on followers. Isn’t that inconsistent?”

They answer different questions. The op-count break-even is p < r and the follower term cancels, so on raw counts a prolific small account is a worse push candidate than a quiet large one. But the two ops are not the same price: a pull is only cheap when the pulled set is in process, which is a fixed RAM budget, and follower count is how you rank accounts for admission to it. Followers are the admission criterion, not the cost driver. In production I would sort on followers x posts_per_day and take the top-K until the 80 MB budget fills, which is what The hybrid and the threshold derived recommends too.

“Where does the 500-entry cap come from?”

Bandwidth, primarily, and I would quote it at peak because a network card has no way to average. The read path ships the slice to the ranker, so bytes on the wire are linear in the cap: 500 entries is 12 KB per read and 28 machines of network card at the 289 k reads/s peak — 11 at the 116 k daily average — while 3,000 entries is 72 KB and 167 machines at peak. The ratio is 6x either way, which is the part that does not depend on my peak factor. Storage is the secondary argument at 36 TB. And the cap costs nothing on the consumption side, because a user takes 100 impressions a day and 500 candidates is five days of that.

“A user complains they see the same post twice. Walk me through it.”

Almost certainly OFFSET. The list is prepended to between page requests, so page 2 re-serves the last k items of page 1 where k is the number of inserts during the dwell. For a p95 user at 0.0053 arrivals/s and a 30 s dwell that is 15% of page-2 loads and 55% by page 5. The fix is a cursor. For a chronological list, keyset on (created_at, post_id). For a ranked list, keyset is not enough because scores move, so I freeze the ranked list per session — 22 GB of Redis at 27.8 M concurrent sessions — and the cursor is a position in the frozen list.

“What if the ranking service is down?”

Serve reverse-chronological from the same inbox. The feed degrades in quality, not availability. If my design cannot do that, I have made a quality dependency into an availability dependency, which is the more serious bug.

“How fresh does a post have to be in a follower’s inbox?”

Five seconds at p99 for the follower, and immediately for the author, which is a different requirement. The author’s own post is read-your-writes: write it into their own inbox synchronously on the request path before returning, and let the other 399 go through the queue. One synchronous write out of 400 buys the only consistency guarantee anyone will actually notice.

“Two billion users. Is 36 shards really enough?”

For bytes, yes. But shard count here is set by failure domain and rebuild time: one shard down is 1/36 of users degraded, and rebuilding 1 TB from the post store at 1 GB/s sequential is 1,000 s. I would take 128 shards for a 0.8% blast radius and accept the wasted capacity.

Cheat sheet

Every result in the chapter, one line each, in the order you would reach for them at a whiteboard.

Next: 12 — Design A Chat System — where the same push/pull question returns with a real-time deadline attached, and the connection itself becomes the state you have to shard.

Related: ml 10 — Personalized News Feed owns everything this chapter delegates about ranking; chapter 05 partitions the inbox; chapter 06 is the store underneath it; chapter 02 is where 1/(1-h) comes from.