How to design a news feed

In this lesson, we’ll solve the delivery problem behind a feed: getting one author’s post into two billion followers’ feeds, and letting a client read page 3 of a list that is being changed underneath it. At this scale, delivery is the hard part. By the end you’ll be able to derive the one architectural decision every feed turns on, place the push/pull split from a follower distribution, and defend a cursor that survives inserts in an interview.

We will not cover ranking. The scoring function that decides what order the posts appear in lives in the feed-ranking chapter; numbers here that touch ranking are taken from there.

The contract. The input is a stream of posts (one author writes one item) plus a follow graph (who subscribes to whom). The output, for one viewer, is one page: about 20 posts in some order, plus a token to fetch the next 20. A request is GET /v1/feed?limit=20&cursor=..., and the response is {items[], next_cursor}.

A few terms used throughout:

• p99 / p95: percentiles of request latency. Sort the day’s requests by how long each took; p99 is the time the slowest 1% exceeded, p95 the slowest 5%. This is what users notice, and it is what a mean hides.
• Power-law distribution: a few items are enormously larger than the rest, so the mean says almost nothing about any one sample. Follower counts are the textbook case: a median in the hundreds, a maximum in the hundreds of millions.
• Critical path: the chain of work a user is actually waiting on. Anything off it can be slow without anyone noticing.

The one decision, and what breaks

There is exactly one architectural choice in a feed, and everything else follows from it: is a follower’s timeline computed at write time or at read time? To materialize a list is to actually compute and store it, not leave it as a query you run later.

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

flowchart TD
    subgraph P["Push · fan-out on write"]
        A1(["Author posts"]) --> W1["Write a pointer into<br/>every follower's inbox"]
        W1 --> I1[("Follower inbox")]
        R1(["Viewer reads"]) -.->|"one lookup"| I1
    end
    subgraph L["Pull · fan-out on read"]
        A2(["Author posts"]) --> O2[("Author outbox only")]
        R2(["Viewer reads"]) -.->|"fetch + merge<br/>every followee's outbox"| O2
    end

Push moves the work to publish time and pays once per follower. Pull moves the work to read time and pays once per followee. Get the choice wrong one way and a single celebrity post stalls the cluster; wrong the other way and every feed load fans out to hundreds of backend calls and inherits the slowest of them.

What breaks, in the order it breaks:

Here h is the cache hit rate: the fraction of reads the cache answers itself, so 1 - h is the fraction that fall through to the store behind it.

The answer is a hybrid: push for most authors, pull for the few with enormous follower counts. The rest of this lesson derives why, and where the split sits.

Requirements

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; an already-seen post is deprioritized.

Non-functional (these decide the design)

Two of these carry more weight than the rest:

• The durability asymmetry makes the whole 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. So the inbox needs none of the machinery that keeps replicas honest (quorum writes, vector clocks, Merkle repair, all covered in the key-value store chapter). Losing an entry costs one missing post in one feed, and the repair is a background rebuild.

• Eventual consistency means copies may disagree for a while and then converge. Read-your-writes is the narrower promise that whoever just wrote something can immediately see it. Only the author needs it, and only for their own post.

The assumptions

Every number below flows from a handful of stated assumptions. Two of them are load-bearing: being wrong about them changes the shape of the system, not just the machine count.

1. The read:write ratio decides push vs pull by itself. Each user reads their feed about 5 times a day and posts about 0.2 times a day. The break-even (derived below) is p < r: push wins when an author posts less often than followers read. At 0.2 posts vs 5 reads, push wins by 25x. Invert it, a product where people post 10 times a day and read once (live commentary, group chat), and pull wins, the inbox disappears, and the design is different. This is not a tuning knob; it sets the architecture.

2. The power-law follower tail forces the hybrid. If every account had exactly the mean 400 followers, pure push would be correct and this lesson would be short. The celebrity problem exists only because one sample from the tail (100 M followers) is 250,000x the mean. The hybrid exists solely to keep those samples off the push path.

Two assumptions you can be wrong about cheaply: the peak multiplier (2.5x average) and the per-entry byte count (24 B). Doubling either just buys more machines. In fact doubling the entry to 48 B widens the gap between the capacity constraint and the operations constraint on the inbox store, so it moves the design further from any flip, not closer. Getting a non-load-bearing assumption wrong costs money; getting a load-bearing one wrong costs a rewrite.

Back of the envelope

The traffic figures every later number derives from, adopted wholesale from the feed-ranking chapter so the two cannot disagree. DAU is daily active users; an impression is one post shown to one viewer.

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               (how many a viewer subscribes to -> PULL cost)
mean followers per post  400               (how many receive a post      -> PUSH cost)

Follows (200) and followers per post (400) are different numbers about different people, and the rest of the lesson multiplies each by a different thing.

Pages come from pagination, which is this lesson’s problem: a session shows 25 posts and a page holds 20, so a session asks for 1.25 pages. That gives 8e9 x 1.25 = 1e10 timeline reads/day, or 115,741 reads/s average, 289,353 at 2.5x peak, and 5 reads per user per day.

Push cost vs pull cost

PUSH   posts x mean followers   =  5e8 x 400   =  2.0e11 inbox writes/day   =  2.31 M/s avg, 5.79 M/s peak
PULL   reads x follows          =  1e10 x 200  =  2.0e12 fetches/day        =  23.1 M/s avg
                                             ratio = 10x

Pull costs 10x the operations of push, and unlike push every one is on the critical path. But the op count is the less important half of the argument (see below); latency is the decisive half.

Offered load is not service capacity. Both totals above are demand (what the world asks the system to do), not what a fleet can supply. They are written in the same units (ops/s), and confusing them is the most common error in this problem. If you provision a fleet at exactly the 5.79 M/s peak, it is 100% busy at peak and has zero spare for any burst, so a burst never drains. Every “seconds to deliver” figure later names a capacity first, and the gap between capacity and load is the only thing that does work.

Storage and bandwidth

inbox    3e9 active users x 500 entries x 24 B  =  36 TB   (x3 replicas = 108 TB)
egress   20 posts x 1.5 KB hydrated             =  30 KB per page
         avg  115,741/s x 30 KB  =  27.8 Gbps
         peak 289,353/s x 30 KB  =  69.4 Gbps

A post is hydrated when a bare post id is replaced by the actual content (author, text, media URLs, counts), the step that turns an 8-byte pointer into a 1.5 KB object. Egress is data leaving the data centre, the direction cloud providers charge for.

Storage is sized at the average; anything with a queue in front of it is sized at the peak. Disks accumulate, so 108 TB is a month’s bill regardless of a busy hour. A network card carries this second’s traffic or drops it, so the binding number for the fleet is 69.4 Gbps at peak, not 27.8. At ~1 Gbps sustained per card that is 70 machines’ worth of network just to serialize feed pages, before any media.

Two things cut it. Gzip takes a page from ~30 KB to ~10 KB (23.1 Gbps at peak). And media never touches this path: it is a URL in the payload, and the client fetches the bytes from a content delivery network (a fleet of caches near users), covered in the scaling-up chapter.

API sketch

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)

Three choices carry weight:

• 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 the whole of the pagination deep dive below, and it is the surest sign a candidate has not built one of these.
• limit is capped server-side (say 50) regardless of what the client asks. Read-path bandwidth is linear in it, so an uncapped limit lets one caller multiply their cost to you for free, the amplification attack that the rate-limiter chapter bounds.
• next_cursor is opaque and signed. Opaque means the client sends it back unmodified; signed means it carries a cryptographic tag so tampering is detectable. It encodes a server-side snapshot id, and if clients could forge it they could pin themselves to arbitrary positions in other people’s snapshots.

Data model

Four stores, one deliberately tiny and one deliberately duplicated.

posts        post_id (PK, k-sortable)  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

k-sortable ids sort by time because their high bits are a timestamp, which lets a cursor use the id as a tiebreak (see the ID-generator chapter). A post is never deleted, only tombstoned: a marker meaning “this was deleted”, kept because in a replicated store an absent row and a deleted row look identical, so without the marker a lagging replica would resurrect the data. TTL is an expiry after which an entry is dropped automatically.

The inbox entry is 24 B and holds no post body:

post_id 8 B  +  author_id 8 B  +  created_at 4 B  +  flags 4 B  =  24 B

An inbox entry is a pointer, not a copy. Two consequences: size (500 x 24 B = 12 KB per inbox instead of 750 KB with bodies), and edits (the body lives in one place, so editing or deleting a post once changes it in every inbox that points at it, up to 100 M of them for a head account, without touching any of them).

The graph is stored twice, a denormalization: the same fact kept in two shapes so two queries are each one lookup. 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 is cheap to derive from the other, because inverting the edge list means scanning all 2e9 x 200 = 4e11 edges. The cost is a two-phase write per follow; the failure mode is a one-sided edge (A follows B in one index but not the other), fixed by a periodic reconciliation job.

Architecture

The system has two halves that meet only at the stores. The write path is what happens when someone presses send; the read path is what happens when someone opens the app. The two diamonds are the only branches, and each is a deep dive below. Thick arrows are writes, dotted arrows are reads: the distinction matters at the three stores the diagram touches twice, so a derived index does not read as just another pipeline stage.

flowchart TD
    subgraph W["Write path"]
        A(["Author posts"]) --> PS["Post service<br/>validate · assign id · persist"]
        PS ==>|"WRITE"| POSTS[("Post store<br/>authoritative")]
        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"| HOT["Head hot-set broadcast<br/>80 MB · in process on every read host"]
    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/>frozen ranked lists · 22 GB")]
        SNAP -->|no| BUILD["Build candidate set"]
        BUILD -.->|"READ"| INBOX
        BUILD -.->|"READ"| HOT
        BUILD --> RANK["Ranking service<br/>(feed-ranking chapter)"]
        RANK ==>|"WRITE"| SS
        SS --> HYD["Hydrate 20 posts"]
        HYD -.->|"READ"| PC[("Post content cache<br/>225 GB · h = 0.89")]
        PC -.->|"READ on miss"| POSTS
        HYD --> OUT(["Page + next_cursor"])
    end

Write path. The post service validates, assigns an id, and persists the row to the post store: the only authoritative copy anywhere. It then drops a job on the fanout queue, partitioned by author_id so all of one author’s work lands in one ordered stream (partitioning by follower instead would let one celebrity block everyone). Fanout workers ask the hybrid’s one question: is this author above the follower threshold? Below it (99.99% of authors), the worker appends a 24-byte pointer to each follower’s inbox. Above it (head accounts), it pushes nothing; 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.

Read path. A request hits the edge / API gateway, which terminates the connection, authenticates, and rate-limits. If the cursor names a live snapshot (a frozen, already-ranked list built earlier this session), the page is served straight from the snapshot store: the cheap path most requests take. Otherwise the system builds a candidate set (this viewer’s inbox plus anything relevant from the hot set), hands it to the ranking service, freezes the result into the snapshot store, then hydrates the top 20 against the post content cache, falling through to the post store on a miss.

The post store and the inbox are the two components nothing here makes difficult: the post store is authoritative and rebuildable-from-nothing, the inbox is a derived index rebuildable from it.

Deep dive 1: push, pull, and why the answer is a hybrid

Putting the two designs side by side:

The 10x op-count ratio is the less important half. The decisive half is latency.

A wide fan-in turns a rare delay into a common one. A pull read waits on 200 independent fetches, so its latency is the max over them, not the mean. A straggler, one unusually slow call among many parallel ones, that is rare per fetch becomes near-certain per request, because you get 200 chances to draw one. If each fetch has a p99 of 20 ms (1% chance of landing slow), then all 200 being fast has probability 0.99^200 = 0.134, so 87% of feed loads would contain a p99 event. That kills pure pull on its own, independent of cost. Pure push dies at the other end of the distribution, an unbounded tail, which is the next deep dive.

The break-even is posting rate, not follower count

Take one author with F followers who posts p times a day, whose followers each read r times a day. Push writes one row per follower per post; pull fetches this author’s timeline once per follower per read:

push cost/day  =  F x p
pull cost/day  =  F x r
push is cheaper  <=>  p < r     (F cancels)

Here F cancels. The break-even does not depend on follower count at all: only on whether the author posts more often than their followers read. At r = 5:

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

So the popular 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 40 times a day is a worse push candidate than a 10 M-follower account posting twice a week.

Why the real threshold is follower count anyway

The break-even counts all operations as equal. They are not, and the difference is whether the work is shareable. A push write is private: F followers means F distinct rows, each read by exactly one person, none reusable. A pull fetch is public: all F followers read the same author timeline, so the first reader populates a cache and the rest are hits: the F x r figure counts logical reads against a working set of one object.

The real question is where that one object lives. A remote procedure call (a request to another machine) costs ~500 µs even when nothing goes wrong; a read from the calling process’s own memory costs ~100 ns, 5,000x less.

Pull is only cheap when the pulled set lives in the feed host’s own memory, and that is a RAM budget, which is a count of accounts, which is a follower threshold. Followers are the admission criterion to a fixed RAM budget, not the cost driver. The feed-ranking chapter sizes that budget: ~50,000 accounts above 1 M followers, at 50,000 x 50 posts x 32 B = 80 MB of in-process hot set.

Where the threshold sits

The chosen threshold is pinned by a cliff, not picked off a smooth curve. Modelling the follower tail as a Pareto distribution (the standard power-law model) fitted to the feed-ranking chapter’s two anchors (50,000 accounts above 1 M followers, and the top 5,000 averaging 4 M followers) gives an exponent of about 2.5, which reproduces both anchors to within 5%. That is good enough to extrapolate one decade in either direction, no further, because the extreme tail of a real graph is fatter than any single exponent captures.

Sweeping the threshold T, where each admitted account costs 50 posts x 32 B = 1,600 B:

RAM scales as T^-2.5, so halving the threshold multiplies memory by 2^2.5 = 5.7x. One decade below 1 M, the hot set is 25 GB and no longer fits in a process, which destroys the exact property that made pull cheap. That is why 1 M is not an arbitrary round number.

Paging in the 300 k row is what an OS does when short of memory: it evicts memory pages to disk and re-reads them on demand. The re-read (a page fault) stalls the thread for a disk access, ~100 µs against the 100 ns of a resident read, a 1,000x loss on the single property the in-process hot set exists to provide. “Marginal” means the design becomes a bet on what else is resident, not something that holds by construction.

What the hybrid buys, from the feed-ranking chapter: 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.

The “1 M followers” figure is not universal. The threshold depends on the criterion you pick, and RAM is only one. A delivery target (deliver a celebrity post within 60 s using the fanout fleet’s spare capacity) lands near 50,000 instead, via threshold = (capacity - load) x SLO_seconds, never load x SLO_seconds, which assumes an idle fleet and doubles the answer. An SLO is a service level objective, the target a team commits to. The three criteria in common use are a delivery target against stated spare capacity, a RAM budget (this lesson), and queue depth (production, where the threshold moves with backlog). What matters is naming which one you used.

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.

The mean of 400 followers is not the problem; a single sample from the tail dwarfs it. A 100 M-follower account is 1e8 / 400 = 250,000x the mean (log10 = 5.4 orders of magnitude), or 500,000x the median of 200. The argument runs on the mean, because the write budget is a share of the mean.

The write budget for one post is the day’s total inbox-write load divided by the day’s posts, which comes out to exactly the mean fanout of 400 writes, a fair share of demand, not an allowance of capacity. One post from a 100 M-follower account is 250,000 budgets, and 1e8 / 2e11 = 0.05% of everything the platform writes that day, for one person pressing send once.

Working out how long it takes to deliver shows why the answer needs a capacity, not a load. You cannot divide a burst by an offered load and get a duration; a duration needs a rate the machines can actually supply. State the fleet as a decision: provision at peak + 25% headroom (capacity bought above expected peak), so 5.79 M/s x 1.25 = 7.23 M/s capacity. The burst eats the spare:

spare at peak     7.23 M/s - 5.79 M/s  =  1.45 M/s  ->  1e8 / 1.45e6  =  69 s
spare at avg      7.23 M/s - 2.31 M/s  =  4.92 M/s  ->  1e8 / 4.92e6  =  20 s

Against a 5 s target, one post misses by 14x at peak and 4x at average load. And the 69 s is a property of the headroom you chose, not the post. Provision at exactly peak demand and the spare is zero: the post never drains at all, not “slow”, never. Provision to hit 5 s at peak and you need 20 M/s of spare, a fleet at 4.5x peak demand, bought for one account.

The tempting shortcut 1e8 / 5.79e6 = 17.3 s is wrong in the flattering direction: 5.79 M/s is the load the fleet is already carrying, so dividing by it describes a fleet doing no other work. The honest range is 20–69 s at 25% headroom, unbounded at zero. Getting the method right does not rescue the design, which is the point.

Three things make it worse than the arithmetic:

1. Bursts are correlated. Head accounts post about the same news, so tail events arrive together.
2. The queue is FIFO within a partition. Partitioning by author_id means a celebrity’s huge job only delays that celebrity’s own later posts. Partition by follower instead and one celebrity’s job blocks every ordinary post behind it.
3. Retries multiply the work. A job that fails at 60 M of 100 M writes and restarts does 160 M writes. Fix it by checkpointing per follower-shard so the job can resume.

The hybrid removes the burst instead of smoothing it: head accounts are never pushed, so the 1e8-write event does not exist anywhere to be scheduled, throttled, or retried. Fanout-on-write is not slow for celebrities: it is structurally unable to serve a power-law follower distribution, because the cost of one operation is unbounded above. You do not tune that; you remove those accounts from the path.

Deep dive 3: the inbox store

The write path is small in bytes and large in operations. Post-hybrid volume is 9e10 / 86,400 = 1.04 M writes/s, which at 24 B each is only 25 MB/s of appends: a laptop could move that. But it is 1.04 million discrete random writes per second against 3 billion distinct keys, and the operation count, not the byte count, is what sizes the store. A random write lands at an unpredictable place on the device (versus a sequential write that continues where the last stopped), and the same bytes cost far more when scattered.

Why the list is capped at 500

Three arguments, and the one everyone reaches for first is the weakest.

• Storage (weak): 500 x 24 B x 3e9 users = 36 TB, unbounded without a cap. True, but 36 TB is easy to buy.
• Bandwidth (binding): the read path ships the whole inbox slice to the ranker, so every capped entry is bytes on a wire on every read. At 500 entries a read is 12 KB and needs ~28 network cards at the 289 k/s peak; at 3,000 entries it is 72 KB and needs ~167 cards. Removing the cap costs ~139 machines of pure network at peak, to move candidates the ranker discards anyway. The magnitude depends on the peak factor, but the ratio, 3,000/500 = 6x the bytes, every hour, does not. Bandwidth is linear in the cap, and nothing else in the system is, which makes the cap the cheapest dial you have.
• Amortization: trimming on every append would double the operation count. Trim lazily only when length exceeds cap + 100, so one trim buys the next 100 appends: 1% write overhead, at most a 20% bandwidth overshoot bounded at 600 entries.

The cap and the TTL are different bounds. For a median user the 72 h TTL binds first: they receive ~309 posts per 72 h, well under 500, so entries expire before they are trimmed. The cap exists for the high-connectivity tail, where ~3,000 posts arrive in the window and the TTL never gets the chance. On the consumption side the cap costs nothing: a user takes ~100 impressions a day, so 500 candidates is five days of maximum consumption: the 501st is retained for a session that will never reach it.

Shard count: capacity binds, not IOPS

IOPS is input/output operations per second: the count of reads or writes a device can do, distinct from the bytes it can move. Two candidate constraints:

capacity     36 TB / 1 TB per box                   =  36  shards
write IOPS   1.04 M/s / 500,000 IOPS per NVMe box   =  ~3  shards

Capacity binds, by 12x, a change from how this is usually taught. The textbook divides 1.04 M/s by 10,000 IOPS and gets 105 shards, concluding you must buy 2.9x the disks purely for operations. But 10,000 is a queue-depth-1 latency (the rate you get issuing one request at a time) mistaken for a device ceiling. A modern NVMe SSD (flash attached directly to the PCIe bus) sustains 500,000–1,000,000 random IOPS with many requests outstanding. On current hardware the IOPS argument no longer reaches.

The real case for an LSM tree is write amplification and space, not throughput. An LSM tree buffers writes in memory and flushes them to disk as sorted files that background jobs merge, so every disk write it issues is sequential even though the incoming writes were random. Write amplification (bytes written to disk over bytes the application asked to write) is ~10x for an LSM (the merging rewrites data), which sounds bad until you price the alternative: a B-tree updates a row where it already lives, and since disks write a page at a time, appending one 24 B entry rewrites the whole page, far worse than 10x, and none of it sequential. So the LSM turns 25 MB/s of random writes into 250 MB/s of sequential ones, under 1% of one device’s sequential bandwidth. Capacity binds again: 36 shards x 3 replicas = 108 boxes.

A memory tier sits in front of it. In a typical session a viewer reads only the first two pages: 2 x 20 = 40 entries. Sizing a RAM tier for just those: 40 x 24 B x 2e9 DAU = 1.92 TB, or 8 boxes at 256 GB each. Eight boxes hold the first two pages of every daily active user’s inbox, which is the working set: the part actually touched in normal operation, since only deep scrollers reach the tail. Partition both tiers by user_id on a hash ring so adding a machine moves only 1/(N+1) of the keys instead of rehashing nearly everything (see the consistent-hashing chapter).

Deep dive 4: pagination that survives inserts

The OFFSET bug

LIMIT 20 OFFSET 20 says: skip 20 rows from the head, then give me the next 20. That is a count of rows from the top, and it is only stable if the top is stable. A feed’s top is not: it is being prepended to constantly.

Walk it through. The client fetches page 1 (rows 0–19) and reads it for 30 s. During that time k new posts arrive at the head, pushing everything down by k. The client asks for OFFSET 20, which returns rows 20–39 of the new list, which are rows 20-k..39-k of the list page 1 came from. If k = 3, page 2 begins at old row 17, and 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

How often does it bite? Arrivals into one inbox come from many independent authors, so they are well modelled as a Poisson process (events arriving independently at average rate lambda), for which the chance of no event in a window t is exp(-lambda t). So P(page corrupted) = 1 - exp(-lambda t). With arrival rates of 0.00119/s (median user) and 0.00532/s (p95 user) and a 30 s dwell:

median, page 2  ->  3.5%
p95,    page 2  ->  14.8%
p95,    page 5  ->  55%     (t is cumulative: 5 x 30 s = 150 s)

The window is cumulative (the clock runs from when the list was first read), so by page 5, more than half of a well-connected user’s page loads contain a duplicate. That is exactly backwards from what the product wants, since deep scrollers are the engaged users. Across the platform, 2e9 scroll requests/day at a blended ~5% rate is 100 million visibly wrong pages a day, from a clause that looks correct in review.

The fix: keyset cursor, plus a snapshot for ranked feeds

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

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

A new post has a created_at above the cursor, so the < comparison excludes it: inserts at the head are invisible to a cursor pointing lower down, and deletes below shift nothing because nothing is counted. A composite index on (user_id, created_at, post_id) serves both the filter and the sort from one contiguous scan, versus OFFSET 20000 reading and discarding 20,000 rows first.

A ranked feed needs more. The keyset cursor works because the sort key (created_at) never changes. A ranked feed sorts on a model score, which is not stable: it moves with the model version, with elapsed time through recency decay, and with the viewer’s own state (page 1 just generated impressions). So a post can move from rank 25 to rank 15 between requests, cross the cursor boundary a second time, and be served twice. Same bug, different cause.

The fix is to freeze the ranked list once per session and paginate the frozen copy. That frozen list is the snapshot, and the cursor becomes a plain integer position into it. Concurrent sessions come from Little’s law (sessions/day x duration / seconds/day = 8e9 x 300 / 86,400 = 27.8 M), and a snapshot of 100 post ids is 800 B, so the store is 27.8 M x 800 B = 22 GB of Redis (an in-memory key-value store). Twenty-two gigabytes buys correct pagination for the whole platform: less than one 256 GB box against a bug that otherwise shows on 100 M pages a day. Give each snapshot a TTL of the session length (300 s), extended on use; an expired cursor means “rebuild from the top”, which is also the right behavior for a client backgrounded for an hour.

Two product details make freezing acceptable. New posts arriving mid-session go behind a “12 new posts” pill that loads a fresh snapshot when tapped instead of being injected mid-list, the behavior users already expect. And a seen-set keeps the freeze honest across sessions, so the next session does not re-show the last one’s posts. Tracking exact seen-ids is expensive, so use a Bloom filter (a compact bit array that answers “seen this?” with “definitely not” or “probably yes”). At a 1% false-positive rate it costs -ln(0.01)/ln(2)^2 = 9.6 bits per element, so 2e9 users x 2,000 recent ids fits in 4.8 TB instead of the 32 TB an exact set needs. The 1% wrongly suppresses ~5 of a 500-candidate pool, which is invisible.

The pagination code

The cursor position must be validated, because the two API-sketch promises (the cursor is opaque and signed, limit is capped server-side) are exactly what a hostile -5 cursor or -1 limit tests. Unguarded, page(snapshot, -5) slices from the end and hands back a forward cursor the client will resend, and page(snapshot, 0, -1) returns 99 items in one page. Both are the amplification the cap exists to stop.

from typing import Optional

MAX_LIMIT = 50          # 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) == []

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)

for bad in (-5, 101, "20", 1.5):                     # hostile cursors
    try:
        page(snap, bad)
        raise AssertionError(f"cursor {bad!r} was accepted")
    except ValueError:
        pass

for bad in (0, -1):                                  # hostile limits
    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 matters: cursor is None, not if not cursor. Here position 0 and “no cursor” both start at the top, so a truthiness test would be harmless by luck. But applied to a sequence number where 0 is a real value distinct from “nothing yet”, the same construct silently breaks. Test integers against None, not against zero.

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

Four tiers, each justified by a different constraint, form a chain in which a miss at one tier falls through to the next.

L2 is sized from the popularity curve. Post popularity is close to Zipf with exponent 1: the n-th most popular item gets about 1/n of the traffic of the most popular. For that case there is a standard result: the share of accesses covered by caching the top k of N items is h = ln(k)/ln(N). With N = 1.5e9 live posts and 1.5 KB per hydrated object:

top 1%   k = 1.5e7  ->  h = 0.782,  22.5 GB
top 10%  k = 1.5e8  ->  h = 0.891,  225 GB

Ten times the memory moved the hit rate only 11 points, which looks like poor value. It is not.

The returns do not actually diminish. Load on the store behind a cache is (1-h) of reads, so the reduction is 1/(1-h):

h = 0.782  ->  4.6x
h = 0.891  ->  9.2x
h = 0.990  ->  100x

Ten times the RAM (22.5 -> 225 GB) doubled the leverage; eight times again gets 100x. Substituting the Zipf hit rate gives 1/(1-h) = ln(N)/ln(N/k), which blows up as k approaches N. 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 argument stops somewhere. Push to h = 0.99 and solving ln(k)/ln(N) = 0.99 gives k = 1.2e9: 81% of the corpus, 1.82 TB. At that point the “cache” is a second copy of the store with no durability and a hard invalidation problem, so it is no longer a cache. 225 GB at h = 0.89 is the defensible answer.

The whole argument rests on the Zipf skew, which is an assumption, not a law. Under uniform popularity, caching 10% gives exactly h = 0.10 and a leverage of 1.11x, and no amount of memory produces the 9.2x because there is no head of the distribution to catch. That is why the first thing to measure in production is the actual popularity curve.

The same leverage runs backwards as a failure mode. Losing the L2 tier does not raise store load gradually: it multiplies it by 1/(1-h) the instant the tier goes. Losing L2 takes the post store from 10.9% of 115,741 reads/s (12,616/s) to 100% (115,741/s), a 9.2x step function, not a ramp. A cache is warm when it holds what its traffic will ask for and cold when empty (after a restart or flush); cache warming populates it before it takes live traffic. Three fixes, most-buys-first: consistent hashing so losing one node moves 1/N of keys not all of them; request coalescing (single-flight), where n simultaneous misses on one key send one read to the origin and the other n-1 wait; and staggered restarts so the tier never goes cold at once.

Bottlenecks and scaling

Each limit, the number it binds at, and the two moves that relieve it in order.

A whale is a viewer who follows an unusual number of accounts (the mirror of a celebrity, who has an unusual number of followers). A field mask names which fields the client actually wants so the server can omit the rest. The last row matters: engagement counters are a different system, a hot post takes thousands of increments/s against one key, a contended-counter problem (see the rate-limiter chapter), not a feed problem.

Failure modes

Each failure, how wide the damage spreads (blast radius), the metric to alert on, and the mechanism that contains it.

To autoscale on lag is to add workers automatically when the backlog grows. To shed load is to deliberately stop serving some requests the usual way so the rest keep working. QPS is queries per second. Reverse-chronological means newest first, with no model involved.

Every mitigation here gives up a property, not 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 slower-but-correct pull RPC; a dead inbox shard falls back to the post store and follow graph, slower but complete; a dead ranker falls back to reverse-chronological. The feed’s dependency on ranking is a quality dependency, not an availability one: a design where the ranker sits on the critical availability path has confused the two.

Alternatives rejected

Conclusion

• There is one architectural decision, materialize at write or at read, and the answer is a hybrid split on the follower distribution. Two assumptions drive it: the read:write ratio (5 reads vs 0.2 posts per user per day picks push over pull) and the power-law follower tail (forces the hybrid). The 2.5x peak factor and the 24 B entry are not load-bearing.
• Push dies on an unbounded tail, pull dies on latency. One 1e8-follower post is 250,000x the per-post write budget; a 200-way pull fan-in makes an 87%-likely straggler. The hybrid removes both cases instead of provisioning for them.
• The break-even is p < r (follower count cancels), but the implemented threshold is on followers, because pull is cheap only when the pulled set is in-process RAM (100 ns vs 500 µs RPC), and RAM budget ranks accounts by followers.
• The inbox is a derived, disposable pointer index: 24 B per entry, capped at 500 for bandwidth, on an LSM store where capacity binds at 36 shards (not IOPS, on modern NVMe).
• Correct pagination needs a cursor, and a ranked feed needs a per-session snapshot because scores move: 22 GB of Redis against a bug that otherwise shows on 100 M pages a day.
• Caching pays off faster than linearly up to the point where the cache holds most of the corpus and stops being a cache; 225 GB at h = 0.89 gives 9.2x leverage.
• Every failure degrades a property, not the service: most importantly, a dead ranker falls back to reverse-chronological.

One line to remember: a feed turns on a single question, materialize at write or at read, and the answer is always a hybrid, because push dies on an unbounded tail and pull dies on latency, so you split on the follower distribution and keep the extremes off the wrong path.

Next: Design a chat system, where the same push/pull question returns with a real-time deadline and the connection itself becomes state you have to shard.

Further reading

• Raffi Krikorian, Timelines at Scale (QCon 2012): Twitter’s hybrid fanout and the celebrity problem in production.
• Bronson et al., TAO: Facebook’s Distributed Data Store for the Social Graph (USENIX ATC 2013): the follow-graph store this lesson abstracts.
• O’Neil et al., The Log-Structured Merge-Tree (LSM-Tree) (Acta Informatica, 1996): the write-amplification argument behind the inbox store.
• Burton Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors (CACM, 1970): the seen-set filter.
• The feed-ranking chapter owns everything this lesson delegates about ranking; the consistent-hashing chapter partitions the inbox; the key-value store chapter is the store underneath it.