Design a news feed

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

We start with 2 million daily users. Each reads about 19 timeline pages a day: 5 visits of 3 to 4 pages.

Reads per day: 2 million x 19 = 38 million. Per second on average: 38,000,000 / 86,400 = 440.

Traffic is not flat over a day. We take a peak factor of 2.2: the busiest time of day carries 2.2 times the average.

So timeline reads at peak are 440 x 2.2 = 968 per second.

Each user writes about 1 post a day. That is 2,000,000 / 86,400 = 23 posts per second, and 23 x 2.2 = 51 at peak.

968 + 51 = 1,019, so we plan for 1,000 requests per second: 950 reads and 50 posts.

A user reads 19 pages for each post written, so reads outnumber posts 19 to 1. Reads are 95% of the load.

The interviewer will ask for ten times the load. So we size storage and memory for 20 million daily users.

Posts: 20 million a day. Per year, 20 million x 365 = 7.3 billion.

A post holds three 8-byte fields, about 140 bytes of text, and a 40-byte media key on 30% of posts.

That is 24 + 140 + 40 x 0.3 = 176 bytes of data. Our database is Aurora PostgreSQL.

Row overhead adds 28 bytes, two indexes 50, and free space 15%: (176 + 28 + 50) x 1.15 = 292, so 300 bytes.

Posts per year: 7.3 billion x 300 bytes = 2.2 TB. Aurora storage grows to 256 TiB on current versions, so storage limits nothing here.

Follow graph: we assume 40 million accounts, each following about 150. That is 40 million x 150 = 6 billion follow rows.

We index each row both ways, so it takes about 120 bytes. 6 billion x 120 bytes = 720 GB, and it grows with accounts, not time.

Users add photos later on this page. We size them now: 30% of posts carry one photo, so 20 million x 0.3 = 6 million a day.

We store three sizes of each photo: a 50 KB thumbnail, an 80 KB medium and a 160 KB full-screen copy. That is 290 KB.

Per year: 6 million x 290 KB x 365 = 635 TB, about 640 TB.

An original upload is about 3 MB. Kept, originals add 6 million x 3 MB = 18 TB a day, or 6.6 PB a year.

That is 10 times the resized copies. So we keep the full-screen copy, and originals expire after 2 to 3 days.

Timeline memory: the design for ten times the load keeps a list of post IDs in memory for each user.

We keep lists only for users active in the last 7 days. We assume 80% of weekly users visit on a given day.

So weekly users are 20 million / 0.8 = 20 million x 1.25 = 25 million lists.

Each list keeps the newest 500 post IDs. An ID is a 64-bit number, and in memory it takes 10 bytes with its encoding.

A list is 500 x 10 bytes = 5,000 bytes, plus about 1 KB for its key and overhead. So each list is about 6 KB.

All lists: 25 million x 6 KB = 150 GB, or 140 GiB. We size for 150 GiB, which leaves 7% for growth.

One cache.r7g.xlarge node has 26.32 GiB, and 19.7 GiB is usable after the default 25% reserve.

150 / 19.7 = 7.6, so we split the lists over 8 nodes.

Per instance: a database instance has 8 virtual processors. The first design reads a timeline with one query that merges the newest posts of about 150 accounts.

That query costs 5 ms of one processor, so one processor serves 1,000 / 5 = 200 per second.

One instance serves 8 x 200 = 1,600 of those queries per second.

A short lookup or insert costs about 1 ms. At that speed, one instance serves 8 x 1,000 = 8,000 per second.

Per task: each copy of an API service is a task with one virtual processor.

A Feed API task works on 10 requests at once. Each takes 20 ms, mostly waiting on the database.

So one task serves 10 x 1,000 / 20 = 500 requests per second.

We keep each task near 70% busy, which leaves room for a burst. So we count 350 per task.

1,000 / 350 = 2.9 tasks, but we keep at least 4. So 4 tasks run, at 1,000 / 2,000 = 50% busy.

Later designs split the API. A Post API task also serves 500. A Timeline API request takes 8 ms, so a task serves 10 x 1,000 / 8 = 1,250.

A fan-out worker task runs 4 threads, and a job takes 6 ms. One thread serves 1,000 / 6 = 167 jobs per second.

So one worker task serves 667 jobs per second, and two tasks, or 8 threads, serve 1,333.

Check in: Close the page and derive 1,000 requests per second from 2 million daily users. Say each line out loud.

Start with the simplest design that works

If we draw the final design first, we cannot say what each box fixes. The interviewer asks why a box is there, and we have no answer.

We start with one service and one database. The Feed API takes every request.

The database has a writer and one read replica, a copy of the data that serves reads.

A post is one insert. A timeline read is one merge query: it finds the newest posts of about 150 accounts and keeps the top 20.

We call this design pull, because we build the timeline when the user reads it. Interviewers also call it fan-out on read.

We price the merge query at 5 ms of database time. Each database instance has 8 vCPUs, or virtual processors.

At 5 ms per query, one vCPU serves 200 queries per second. So the 8 vCPUs of the replica serve 1,600 merge queries per second.

Stage 1 runs this design in SysPad at 1,000 requests per second. Each card is a part of the system. Each arrow carries requests.

Read the four result tiles of Stage 1. "First to saturate" reads "Nothing at this load". A part saturates when it gets more requests than it can serve.

The note under that tile names the busiest part: the Posts and follows DB, at 59%. Its replica gets 950 merge queries per second, and serves 1,600.

The Feed API card shows 50%. The Feed API uses auto-scaling: it adds copies, called tasks, as load grows. So the database is the part to watch.

The latency tile shows 27ms on the slowest path. The cost tile shows $3,987/mo.

Of that, $1,724 pays for the answers sent to the apps: 1,000 a second, about 8 KB each. Data sent out to the internet is called egress.

AWS bills egress per GB, after 100 free GB a month.

Press 2,000. The database saturates, so pull runs out between these two loads.

The trade-off:

Every read runs the merge query again. The work grows with reads times accounts followed, and reads are 95% of all requests.

Stage 1: Pull at read time, 1,000 requests per second

• Load: 1,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $3,987/mo

Check in: Say out loud why this design is enough at 1,000 requests per second. Use one number from the tiles.

Ten times the traffic

The interviewer asks: Traffic grows ten times, to 10,000 requests per second. What breaks first?

Press 1,000 on Stage 2, then press 10,000. The design is the same. Only the load changes.

At 10,000, "First to saturate" names the Posts and follows DB. Its card turns red and shows a warning triangle.

Reads now ask for 9,500 merge queries per second. The read replica serves 1,600.

The latency tile now shows "≥" before the number. Past saturation, SysPad can give only a lower limit for latency.

The database card shows 100%. Reads ask for 7,900 more merge queries per second than the replica can serve.

The Feed API is not the problem. Auto-scaling adds tasks, and it stays below its limit.

So the fix must take read work off the database. More API tasks send the same queries to the same database.

The brute-force fix is more read replicas. About seven replicas carry 9,500 merge queries per second.

The trade-off:

Each replica costs the same as the last one, and the work per read does not shrink.

Aurora allows at most 15 read replicas. So pull on one database stops near 25,000 requests per second.

Stage 2: The same design at 10,000 requests per second

• Load: 10,000 req/sec
• First to saturate: Posts and follows DB
• Estimated cost: $18k/mo

• Latency past saturation is a lower bound, not an estimate. Posts and follows DB is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Posts and follows DB: Readers 594% used: 9,500 reads/s against 1,600 across 1 reader (the writer takes no reads while readers exist).

Check in: Name the part that saturates and the number that proves it. Then say what a fix must change.

The cache that does not help

The common reflex is to add a cache. Here we put a result cache in front of the merge query.

It keeps each user's timeline page for 30 seconds. A hit needs the same user to ask for the same page again in that time.

Users load about 19 pages a day, and most are different pages. So we give this cache a generous 20% hit rate: the share of reads it answers itself.

At 10,000, the database in Stage 3 still saturates.

With one replica for reads, the cache must answer at least 83% of reads. A cache keyed by user and page does not get near that.

The latency tile does not go down either. It shows the slowest path. Here that is a post insert, which goes straight to the database.

A hit stops at the cache and skips the 5 ms merge query. But most reads miss, so most reads pay for both.

The trade-off:

The cache adds a box and a monthly bill, and the database still saturates. A cache helps only when many reads ask for the same key.

Stage 3: A result cache in front of the merge query

• Load: 10,000 req/sec
• First to saturate: Posts and follows DB
• Estimated cost: $19k/mo

• Latency past saturation is a lower bound, not an estimate. Posts and follows DB is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Timeline result cache: Effective hit rate 20%: most reads miss through to the origin.
• Posts and follows DB: Readers 476% used: 7,614 reads/s against 1,600 across 1 reader (the writer takes no reads while readers exist).

Check in: Think of data that many users read at the same time. Would a cache in front of it help? Say why.

Move the work from read time to write time

Pull runs the merge query on every read. Reads outnumber posts 19 to 1, so we do the work on the busy side.

We switch to push: when a user writes a post, we add the post ID to the timeline list of each follower. Interviewers also call it fan-out on write.

Step through the figure to see where the work goes in each design.

We split the Feed API in two. The Timeline API serves reads, and the Post API takes posts. Each one scales on its own.

The Post API saves the post, puts one job on a queue, and returns. A queue holds jobs until a worker takes them.

Fan-out workers take each job and add the post ID to about 300 lists. That is 150,000 small writes per second.

A read now takes two steps. It gets the user's list from Home timelines, then gets 20 posts from the Post cache.

The Post cache works because many readers ask for the same posts. Without it, reads would send 190,000 lookups per second to the database.

We keep lists only for users active in the last 7 days. We assume that is 1.25 times the 20 million daily users we now have: 25 million lists.

Memory sets the size of Home timelines. 25 million lists of 500 IDs need about 150 GiB. So we split them over 8 shards, nodes that each hold one part.

Other users get their list rebuilt from the database on their next visit.

Press 10,000. "First to saturate" reads "Nothing at this load". The cost tile shows $23k/mo.

The latency tile shows the slowest path. Here that is the path of a post, not of a timeline read.

Press 19,000. The database saturates again. Most of its load is misses from the Post cache.

At 35,000, the database is still the only part that saturates.

The trade-off:

Push costs 150,000 writes per second, 150 GiB of memory, and a short delay before followers see a post.

The money is close. Push costs $22,979 a month. Pull with seven read replicas costs about $24,190.

Both send the same answers to the apps, so both pay the same $13,774 of egress.

Push wins on headroom. Even with 15 replicas, pull stops near 25,000 requests per second. Push goes to the database mostly for cache misses.

Push versus pull: where the work goes

1. B writes a post. One row appears in Posts. A post is written once.
2. Pull. A opens the app. We look up the lists of B, C and D, and merge them into one feed of 20.
3. Pull at scale. 9,500 reads per second each need 150 lookups. The database fills past full. Pull does the work every time someone reads.
4. Push. We go back to B's post. A worker copies it into the feeds of A, E and F. That is 1 insert per follower, once.
5. A opens the app again. We read one list, A's own feed. Push does the work once, when someone writes.
6. Pull is 9,500 heavy queries per second. Push is 150,000 tiny inserts and 9,500 tiny reads per second. More operations, each one cheap. That is the trade.

Stage 4: Push: timelines built when a post is written

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $23k/mo

Check in: Push does more operations than pull. Say why the database still gets less work.

The average says it fits

The interviewer asks: A celebrity with a million followers joins. What changes?

We call an account with 100,000 followers or more a big account. We assume 1,000 of them, with 1 million followers each.

Together they make about 0.15 posts per second at peak. That is 0.03% of all posts, but it causes half of all timeline writes.

With push, the average post now goes to 606 lists instead of 300. Stage 5 uses that average.

At 10,000, nothing saturates, and the cost does not change. By the simulation, a celebrity fits.

SysPad puts one average number on each arrow. It cannot show one post that is much bigger than the rest.

So we do the time math by hand. One big post is one job with 1 million writes. On one worker thread, it takes about 12 seconds.

We aim to deliver each post within 5 seconds. So the big account's own followers wait more than twice our target.

Normal posts do not wait. A normal post takes 6 ms, so one thread serves about 167 per second.

The other 7 threads serve about 1,167 normal posts per second, and only 500 arrive.

Normal posts wait only if we split the big job into chunks, or if many big accounts post at once.

Step through the figure to see who waits.

The trade-off:

At peak, big accounts use 23% of the worker fleet: 0.153 big posts per second x 12 seconds = 1.84 of our 8 threads.

They cause half the writes but use less than half the time. A normal post pays a fixed 3 ms for only 300 writes.

Many of the big-account writes go to lists that nobody reads that day.

The celebrity: a burst against a queue

1. The fan-out queue holds normal posts, 300 inserts each. Two worker tasks, with 4 threads each, take them evenly. Delivery takes under 1 second.
2. A big account posts. Its job is 3,333 times larger and holds one thread for 12 seconds. One big post delays its own followers. It blocks other posts only when it is split into chunks, or when many big accounts post at once.
3. Hybrid. We go back. The big post goes once into a small separate store. Nothing enters the queue. Delivery stays under 1 second.
4. A reads a timeline. We merge A's own feed with 25 big-account lists. That adds 25 reads to every timeline load.
5. Push for big accounts is 153k inserts per second, in bursts. Pull is 237.5k reads per second, smooth. Hybrid costs more operations. It buys smooth load and instant delivery.

Stage 5: Push for every account, big accounts included

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $23k/mo

Check in: Why does an average hide this problem? Say it in one sentence.

Stop pushing for big accounts

A 12-second job breaks our 5-second target. We can split it into chunks, but then all 8 worker threads spend 1.5 seconds on one post.

During that time, about 750 normal posts wait. Chunks move the wait from the big account's followers onto everyone.

So we stop pushing big accounts. A worker adds a big post once, to the author's own list in a small store called Big-account posts.

On a read, the Timeline API also reads the lists of the big accounts that the user follows. It merges them into the user's list by time.

Each user follows about 25 big accounts. So each timeline read adds 25 small lookups.

We set the limit at 100,000 followers. A job of that size takes about 1.2 seconds, inside our target.

Press 10,000. Nothing saturates. The cost tile shows $23k/mo, the same rounded figure as push.

Big-account posts runs on 3 nodes: a primary, which takes the writes, and 2 replicas, which copy it. All 3 serve reads.

One node, a cache.r7g.large, serves 160,000 lookups a second. At 10,000, reads ask for 9,500 x 25 = 237,500, so one node alone would saturate.

Hybrid costs $449.53 a month more. The Big-account posts store is $378.43 of that, and the Timeline API runs 2 more tasks, for $71.10.

The trade-off:

Hybrid does more operations, not fewer. Push for big accounts was 153,000 writes per second. Pull for them is 237,500 reads per second.

We still choose hybrid. It removes the 12-second jobs, it keeps the load smooth, and a big post appears at once.

The simulation shows the extra reads. It cannot show the burst we removed, so that part stays hand math.

Stage 6: Hybrid: push for most accounts, pull for big ones

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $23k/mo

Check in: The interviewer says hybrid saves work. Correct them with one number.

Where each design runs out

The interviewer asks: How far does each design go before something breaks?

Each design so far ran at one load. That does not tell us how much room it has before the next twist.

In each design, the first wall is the read replica of the database.

Pull sends 95% of all requests to the replica as merge queries. So pull runs out near 1,700 requests per second.

That is 1.7 times the load of Stage 1. Its 2,000 button shows the wall.

In push, the replica does only short lookups of about 1 ms. At that speed, the same 8 vCPUs serve 8,000 per second.

Push sends the replica only cache misses, timeline rebuilds and follower lookups. So push runs out near 18,200, about 10 times further than pull.

Hybrid does not move this first wall. It sends the database the same reads as push.

Press 19,000 on Stage 6. Only the database saturates, as in push.

The Big-account posts card is red, at 94%, but it is not saturated. A card turns red at 90%, and a part saturates only past 100%.

Reads on that store go to its primary and 2 replicas. Each node serves 160,000 lookups a second, so the 3 serve 480,000.

95% of requests are reads, and each read adds 25 lookups: 0.95 x 25 = 23.75 a request. At 19,000, that is 451,250 a second, 94% of 480,000.

Press 25,000. Big-account posts saturates too. It is the second wall: 480,000 / 23.75 = 20,211, so near 20,200 requests per second.

The trade-off:

A new replica moves the first wall in both designs. Per replica, push carries about 10 times the load of pull. That is why push wins at this scale.

Hybrid buys smooth delivery, not more room.

Stage 6: Hybrid: push for most accounts, pull for big ones

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $23k/mo

Check in: The interviewer asks how far the design goes. Give the load, and the part that saturates first.

A spike hits the front door

The interviewer asks: A live event starts. Posts jump five times for ten minutes.

Posts jump from 500 to 2,500 per second. Reads stay at 9,500 per second, so the load is 12,000.

Auto-scaling adds tasks, but a new task takes minutes to start. A spike arrives in seconds.

So this stage and the next run with auto-scaling off. Each service keeps the tasks it had before the spike.

At 12,000, "First to saturate" names the Post API.

Its 2 tasks serve 1,000 posts per second. The other 1,500 posts per second fail at the front door.

The queue and the workers do not saturate. That is only because the Post API passes on just the posts it serves.

So the failure is at the front door, not in the fan-out. That is where we add capacity.

Stage 7: First minute of a spike, with 2 Post API tasks

• Load: 12,000 req/sec
• First to saturate: Post API
• Estimated cost: $26k/mo

• Latency past saturation is a lower bound, not an estimate. Post API is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Post API: Fargate 1vCPU-2GB ×2 at 100% of a fixed 2-task ceiling.

Check in: Which is worse for a user: a post that fails, or a timeline that is late? Say why.

Headroom at the door, lag behind the queue

Every post must succeed during the spike. Followers can see the post a few minutes late.

We keep 8 Post API tasks at all times. They serve 4,000 posts per second, which covers the spike.

At 12,000, "First to saturate" now names the Fan-out workers. That is the plan.

The workers sit behind the queue. A slow worker makes timelines late, but it does not slow down a post.

Read the warnings under the canvas. The queue warning says the backlog grows by about 1,200 jobs per second.

The simulation shows only the first minute of the spike. Step through the figure for what happens next.

Ten minutes at that rate puts about 700,000 jobs in the queue. With no new workers, the queue is empty again 14 minutes after the spike.

If auto-scaling adds workers in about 3 minutes, the worst lag is under 3 minutes.

The trade-off:

Eight tasks cost about $213 a month more, and most of the time they are idle. That buys zero failed posts.

The spike now costs timeline lag instead. We measure lag as the age of the oldest job, and we add workers before a known event.

The queue during a spike: a bathtub

1. The fan-out queue is a tank. Posts flow in at 500 per second. Workers drain 1,333 per second, so the level stays at zero.
2. A live event starts. Posts jump to 2,500 per second. Two front-door tasks cannot take them. Without headroom, posts fail here.
3. We give the front door 8 tasks. Now every post gets in, and the tank fills at 1,167 per second. At 5 minutes it holds 350,000.
4. At 10 minutes the tank holds 700,000 posts. Then the event ends, and the tap returns to 500 per second.
5. With a fixed drain, the level falls at 833 per second. The tank is empty at 24 minutes. No post failed. Timelines were up to 700,000 / 1,333 = 525 seconds late, about 9 minutes.
6. Now add auto-scaling at 3 minutes. The drain widens to 13,333 per second. The level peaks near 210,000 and empties in seconds. Scale-out speed decides the lag.

Stage 8: First minute of a spike, with 8 Post API tasks

• Load: 12,000 req/sec
• First to saturate: Fan-out workers
• Estimated cost: $27k/mo

• Fan-out queue: Fan-out workers drains 1.3k/s of the 2.5k/s offered, so the backlog here grows by 1.2k/s - about 4.2M messages after an hour.
• Fan-out workers: Fargate 1vCPU-2GB ×2 at 100% of a fixed 2-task ceiling.

Check in: Say where this system may fall behind, and where it may not.

Keep photo bytes off the API

The interviewer asks: Users can now add a photo to a post.

About 30% of posts now carry one photo of about 3 MB. That is 150 uploads, or 450 MB, per second.

If those bytes go through the load balancer and the API, the API spends its time moving files.

The Post API returns a presigned URL: a link that allows one upload, for a short time. The app uses it to upload the photo straight to S3, the object store.

When the upload ends, S3 starts the Image resizer function. It writes three sizes of the photo to the Media bucket.

The app loads thumbnails through a CDN, a network of caches near the users. Each timeline page shows about 6, so the CDN gets 57,000 requests per second.

Each image URL contains a hash of the file. A file never changes, so the CDN never has to remove an old copy.

At 10,000, nothing saturates. The latency tile now shows the photo upload, because it is the slowest path.

The cost tile shows $383k/mo, far more than any stage before. Media delivery is most of it.

The trade-off:

Image delivery becomes the main cost of the system. Media is 94% of the tile, $359,707 of $383,348: the CDN, both buckets and the resizer.

Like every cost tile on this page, it bills the peak as if it ran all month.

An average month, at the peak divided by 2.2, is about $200,096. Media is 92% of that.

CDN requests cost nearly as much as CDN data: $147,734 a month against $181,537.

A thumbnail is only 50 KB, so its request fee weighs about as much as its bytes. Smaller thumbnails cut the data charge, not the request charge.

Served straight from S3, the same thumbnails would cost about $415,000 a month. Through the CDN, with S3 reads for its misses, they cost about $332,000.

The CDN price per GB keeps falling with volume, to $0.02, while data straight out of S3 stops falling at $0.05. So the CDN is cheaper, and faster.

The CDN is also one more cache to keep correct. Hashed URLs make that simple, because no file ever changes.

Stage 9: Photos through S3 and a CDN

• Load: 10,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $383k/mo

• Media bucket: Standard storage holds 640 TB.

Check in: Say why the API never touches a photo. Then say what that choice costs us.

The questions with no load story

The interviewer asks: Walk me through the API and the data model. How do you make post IDs?

None of these parts breaks under load, so no stage is about them. An interviewer asks about every one, so we answer each in a line or two.

Post: POST /v1/posts with the text and an optional media ID. It returns 201 Created with the post ID and its time.

It returns 400 for empty text or text over 280 characters. It returns 422 if the photo is not uploaded yet, and 429 for posting too fast.

Each post carries an idempotency key: one ID the app makes for each post, sent again on every retry.

The Post API keeps each key with its post ID for 24 hours. A retry gets the first post back, not a second one.

That costs 20 million posts a day x 100 bytes = 2 GB. Without it, a timeout and a retry make two posts and 600 list writes.

Media: POST /v1/media returns 201 with a media ID and a presigned upload URL, valid for 15 minutes.

Timeline: GET /v1/timeline with a limit of 20 and a cursor, a marker for where the last page ended. It returns 200 with the posts and the next cursor.

The cursor holds the last post ID the client saw. The next page is the posts older than that ID.

An offset would fail here. At 500 new posts a second, every page moves down between two loads, and the user sees posts twice.

A user away for more than 7 days has no list. The call still returns 200, and it is slower while we rebuild the list.

Delete: DELETE /v1/posts/{id} returns 204, or 403 if the caller is not the author. Follow and unfollow are PUT and DELETE on /v1/follows/{user_id}.

A PUT gives the same result when it repeats, so follow needs no idempotency key.

Data: the posts table is keyed by post ID. It holds the author, the time, the text, the media key and a deleted time.

An index on author and post ID, newest first, finds the newest posts of one author. Pull, rebuilds and big accounts all ask that.

The follows table is keyed by follower, then followee, for "who do I follow". A second index by followee answers "who follows this user" for fan-out.

A normal post reads its 300 followers in one 1 ms scan.

A timeline list holds post IDs, newest first. Each insert adds the ID at the front, then trims the list to 500.

Why 500: a user reads about 19 pages, or 380 posts, a day. A list gains 20 million posts x 300 followers / 25 million lists = 240 IDs a day.

So 500 IDs hold about 2 days, more than a day of reading. Older pages fall back to the merge query.

Big-account posts keeps the newest 100 IDs of each big account: 1,000 x 100 x 10 bytes = about 1 MB.

IDs: we use Snowflake-style IDs, 64-bit numbers that sort by time. Twitter introduced the design in 2010.

Each ID has 41 bits of milliseconds, 10 bits of generator number and 12 bits of sequence.

The time part lasts 69 years. Each of 1,024 generators can make 4,096 IDs per millisecond.

Sorting by ID is sorting by time. So lists, the big-account merge and cursors need no time lookup.

Each Post API task makes its own IDs, with no shared counter. In the URL shortener, one shared counter was a hot item.

An 8-byte ID also keeps lists small. A UUID stored as text takes about 38 bytes, so lists would need 24 shards, not 8.

Clocks drift by a few milliseconds, so IDs are only roughly in time order. A feed does not mind.

The trade-off:

Each choice has a price. The cursor needs time-sorted IDs, the idempotency key costs 2 GB of memory, and the 500-ID cap sends old pages to the database.

Check in: Say why the timeline uses a cursor and not an offset. Use the post rate in your answer.

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, what a user sees, and how stale the data can get.

A Home timelines shard is lost, with no replica to take over. It holds 25 million / 8 = 3.1 million lists, and it serves 9,500 / 8 = 1,190 reads per second.

At first, all of those reads miss. Each rebuild is a 5 ms merge query: 1,190 x 5 ms = 5.9 vCPUs.

The read replica already does 4,405 lookups a second for push, at 1 ms each. That is 4.4 of its 8 vCPUs.

4.4 + 5.9 = 10.3 of 8, about 130%, so the replica saturates.

After its first page, a user has a list again. Misses fall to one per visit: 1,190 / 3.8 pages = 310 per second.

The replica drops to 75%, so the storm lasts about one visit, a minute or two.

So each shard gets a replica node, which takes over in seconds. If both are lost, we rebuild on read and cap rebuilds near 700 per second.

Above the cap, the timeline returns 200 with fewer posts, never an error. A second database replica, at $973 a month, absorbs the whole storm.

The queue can deliver a fan-out job twice. A shard failover of about 10 seconds fails 500 x 10 = 5,000 jobs partway.

Each returns after 30 seconds and writes again to the 7 healthy shards: 262 duplicates a job, 1.3 million in all.

So an insert first checks the newest 50 IDs, and adds the ID only if it is absent. The Timeline API also drops duplicates.

Shard replication is asynchronous, so a failover can lose a few inserts. We replay the last 30 seconds of posts to that shard: 500 x 30 = 15,000.

The duplicate check makes the replay safe.

The Post API saves the post, then queues the job. A crash between the two leaves a post that nobody sees.

A transactional outbox fixes it: the post and an outbox row commit together. A relay then queues each job from the outbox.

A job that always fails would return every 30 seconds for 4 days, until the queue drops it.

After 5 tries, which is 2.5 minutes, the queue moves it to a dead-letter queue: a side queue for failed jobs.

We alarm when the dead-letter queue holds any job. After the fix, we send its jobs back.

A deleted post stays in up to 300 lists for about 2 days. We mark it deleted, and the Timeline API drops it when it fetches the 20 posts.

An unfollow runs a small job that rewrites the list without that author. A block works the same way, plus a filter at read time, so it acts at once.

Consistency: at steady state a post waits briefly in the queue, and its job takes 6 ms. Followers see it well inside a second, against our 5-second target.

In the spike with no new workers, the worst lag is 700,000 / 1,333 = 525 seconds, about 9 minutes.

With workers added at 3 minutes, the worst lag is under 3 minutes. A big post has no lag, because we merge it at read time.

We alarm on the age of the oldest job in the queue.

An author must see their own post at once. So the Post API puts the new ID on the author's list before it returns 201.

The Post API also writes the post into the Post cache. Without it, a follower's first read goes to a database replica, which can be up to 100 ms behind.

The post would then look deleted.

Ranking: keep the same 500 candidates, plus big-account posts, and add a scorer. 9,500 reads x 500 = 4.75 million scores a second, a stage of its own.

Multi-region: each user has a home region, and reads stay local. Aurora Global Database copies posts across regions, typically in under a second.

Each region fans out from its own queue into its own timeline cache.

Notifications: a second consumer of each post, on its own queue. A big post is 1 million sends, 100 seconds at an assumed 10,000 a second.

So notifications never share the fan-out queue.

Minutes 0 to 5: requirements. Post, follow, a home timeline newest first, 20 a page, and photos. Ranking is out. Ask the scale.

Minutes 5 to 10: the numbers. 20 million users, 9,500 reads and 500 posts a second, and 300 followers a post.

Then 150 GiB of lists, 2.2 TB of posts and 640 TB of photos a year.

Minutes 10 to 15: the API with the cursor and the idempotency key. The data model with Snowflake IDs and the 500-ID cap.

Minutes 15 to 20: pull on the board. One database, a 5 ms merge query, 1,600 a second per replica. It runs out near 1,700.

Minutes 20 to 27: push. The queue, the workers, the timeline cache sized by memory, and the Post cache. The wall moves to near 18,200.

Minutes 27 to 33: a celebrity. The 12-second job, hybrid at 100,000 followers, and 237,500 more reads a second.

Minutes 33 to 38: a spike, with headroom at the door and lag behind the queue. Then photos: a presigned upload and a CDN.

Minutes 38 to 45: failure modes, staleness and read-your-own-post. Then ranking and multi-region as next steps.

The trade-off:

Each answer to a failure has a price. A second database replica costs $973 a month. The rebuild cap shows some users a short timeline, and we say so first.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.