Case study: News feed

"Design the home feed of a social app" is a very common question. The interviewer asks: "A user opens the app. How do you show the newest posts from the 200 accounts they follow, in under 300 ms, when some accounts have millions of followers?"

A weak answer picks one way to build the list and forgets photos, caches and ranking. A strong answer counts reads and writes first. It builds the list in a hybrid way, keeps ranking in one step that can be switched off, and sends photos through a content delivery network (CDN). It also says what fails and what the user sees.

At SDE-1 level you should follow one post and one feed open. At SDE-2 level you should add the numbers and the caches. At SDE-3 level you should also keep pages steady when the order changes, and handle a hot post and failures.

Think about a school with many classes. Each class has its own notice board. When a teacher writes a notice, a helper pins a copy on the board of every class that should read it. Reading is quick, and the helper does the work. When the head of a huge group writes a notice, pinning it to every board takes all day. So students walk to one main board for those. Before they read, a class monitor picks the 20 notices that matter most, not only the newest 20. Photos stay in the store room, and the notice shows the room number.

The feed design is the same. A home feed is the list of posts from the accounts a user follows, 20 posts for each page.

What lesson 76 decided

Each user has a feed list: the newest 500 post IDs, 8 bytes each, kept in memory. When someone posts, a worker adds the ID to the list of every follower. This is push. A star is an account above a follower threshold, here 1,000,000. A star post needs millions of writes, so stars are not pushed. When a feed opens, the app merges the newest posts of the stars the user follows. This is pull. Followers who have not opened the app for 30 days are skipped. When one comes back, the app builds that list once with a pull.

What the app must do

• A user can post text and one optional photo, and can follow and unfollow.
• A user opens a home feed (newest first, or in a ranked order), 20 posts a page, and can scroll to older posts.
• A post from an ordinary account reaches its followers within a few seconds. The author sees the post at once.
• The feed opens in under 300 ms for 99% of requests (p99, lesson 4). A slightly old feed is fine, an empty feed is not.

The parts

• App servers keep no state (lesson 26) and sit behind a load balancer (lesson 28).
• The post store has one row for each post: ID, author, text, photo key, time. The ID sorts by time (lesson 23). The store is split by a hash of the post ID (lesson 43).
• The author index lists the newest post IDs of each author. It is split by author ID.
• The follow store keeps two views on purpose: "who follows X" for pushing, and "whom does U follow" for reading. Both are split by user ID.
• The feed lists are in memory, one sorted set (lesson 37) for each user, split by user ID. A second server keeps a copy of each list (lesson 39).
• The fan-out queue and its workers spread new posts (lessons 58 and 76).
• The post cache keeps post text by ID (cache-aside, lesson 32).
• The ranker is a service that puts posts in order.
• Object storage and a CDN serve photos (lessons 24 and 36).

The path of one post

1. If there is a photo, the phone uploads it straight to object storage with a pre-signed URL (a link that allows one upload, lesson 24). The post keeps only the storage key.
2. The phone sends "create post" with an idempotency key (lesson 61). The key is a unique value, so a repeat does not post twice.
3. The post service makes a time-sortable ID and saves the post. In the same transaction it saves an event row in an outbox table (a table that holds events until they are sent, lesson 64). It adds the ID to the author index and to the author's own feed list. Then it answers "posted".
4. A relay (a small program that sends the outbox rows) puts the event on the fan-out queue.
5. A worker reads the author's followers in batches. If the author is a star, it stops. Otherwise it skips followers who have been away for 30 days, and adds the ID to the list of each other follower. Adding an ID twice changes nothing, so a repeat is safe.

The path of one feed open

1. The app server receives the request. The first page has no cursor. A cursor (lesson 10) is a token that marks where the last page ended.
2. It reads the user's feed list. It also reads the newest posts of each star the user follows, from its own memory (lesson 45).
3. It merges the IDs and drops posts that are deleted or blocked. It keeps the newest 300. These are the candidates.
4. It asks the ranker to put the candidates in order.
5. It saves the first 100 ordered IDs for 10 minutes. The cursor points into this saved list.
6. It reads the 20 post bodies for page 1 from the post cache in one call. A miss reads the post store and fills the cache.
7. It answers with the text and the CDN link of each photo.

Page 2 reads positions 21 to 40 of the saved list, and then repeats step 6.

A follow adds the newest 20 posts of that author to the user's list, once. An unfollow starts a small job that removes that author's IDs. A block or a private account is checked when the feed opens, because the rule can change after the list was built.

The ranking hook

A ranking hook is one fixed place in the feed open where an ordering step can be plugged in or switched off. It gets the user and the 300 candidates, and it returns them in a new order. A score is a number for each candidate. Here is a simple score: (likes + 2 x comments + 1) / (hours old + 2).

• Post B is 10 minutes (0.17 hours) old with no likes: (0 + 0 + 1) / (0.17 + 2) = 0.46.
• Post A is 1 hour old with 30 likes and 5 comments: (30 + 10 + 1) / (1 + 2) = 13.7.
• Post C is 5 hours old with 400 likes and 40 comments: (400 + 80 + 1) / (5 + 2) = 68.7.

Time order is B, A, C. Score order is C, A, B. A team can replace the formula with a trained model, and the hook stays the same.

Four rules for the hook:

1. Rank only the candidates, not all posts.
2. Set a timeout of 50 ms (an assumption). If the ranker is slow or down, show time order. The user still gets a feed (lesson 54).
3. Compute scores when the feed opens, not when the post is written, because likes and age keep changing.
4. Keep pages stable. If you rank again for page 2, the scores have moved, so posts repeat or disappear. The saved list in step 5 fixes this.

Photos and caches

A photo is far bigger than a post. App servers never carry photo bytes. A worker makes a display copy for phone screens and a thumbnail (a tiny copy for small previews). The name of each file holds a hash of its bytes. So a file never changes, and the CDN can keep it for a long time (lesson 36).

The caches:

• The post cache holds text, author and photo key. It keeps an entry for 10 minutes (the time to live, TTL). An edit or a delete removes the entry at once (lesson 34).
• Like counts change all the time. Keep them apart from the post, so a like does not rewrite it. The counter of a star post is split into buckets (lesson 45).
• Star lists hold the newest 20 posts of each star. Each app server keeps them in memory for 2 seconds, so it asks the shared cache for each star at most once in that time.

Assumptions (made up to teach with, except the scale, which follows a Tradeoff practice problem; see Sources):

• Design choices, all assumptions: 500 IDs in a list, 300 candidates, 100 saved IDs for 10 minutes, a 10-minute post cache, a 2-second star cache, a 30-day skip.
• 200 million (20 crore) daily users. Each opens the feed 10 times a day and follows 200 accounts: 190 ordinary accounts and 10 stars.
• There are 200 million ordinary accounts with 190 followers each on average. There are 1,000 stars with 2 million followers each. Check: 200,000,000 x 10 = 1,000 x 2,000,000 = 2 billion links to stars.
• Ordinary accounts post 40 million times a day in total. A star posts 5 times a day.
• Peak is 3 times the average (lesson 14). A day has 86,400 seconds.
• A list server does 35,000 operations per second (lesson 76) and holds 64 GB of list data. A cache server does 70,000 reads per second at our 70% plan. An app server has 8 cores, which is 5,600 ms of work per second at 70%. One feed open costs 8 ms of app work.
• 20% of posts have a photo. A post row is 1 KB. A photo is 2 MB, plus a 100 KB display copy and a 30 KB thumbnail.

Step 1: traffic. Feed opens: 200,000,000 x 10 = 2 billion a day = 23,148 per second, and 69,444 at the peak. Posts: 40,000,000 / 86,400 = 463 per second.

Step 2: push work. Ordinary posts: 40,000,000 x 190 = 7.6 billion list writes a day = 87,963 per second, and 263,889 at the peak. If we also pushed the stars: 1,000 x 5 x 2,000,000 = 10 billion more. That is more than all ordinary writes. One star post alone is 2,000,000 / 35,000 = 57 seconds of one list server. So stars are pulled.

Step 3: list memory. One list is 500 x 8 = 4,000 bytes. All lists: 200,000,000 x 4,000 = 800 GB. This is the raw size; a real store adds overhead, so plan for more. This answers the predict box. With two copies: 1,600 GB / 64 GB = 25 servers. Operations at the peak: writes 263,889 x 2 copies = 527,778, plus 69,444 reads = 597,222. That is 597,222 / 35,000 = 17.1 servers. Memory decides, so we need 25.

Step 4: post reads. Each open reads 20 posts: 69,444 x 20 = 1,388,880 reads per second at the peak. Cache servers: 1,388,880 / 70,000 = 19.8, so 20. Assumption: the hit rate is 95%. The post store then gets 5% = 69,444 reads per second. Assumption: a store server does 10,000 reads per second. That is 6.9, so 7 servers.

Step 5: app servers and star lists. 69,444 x 8 ms = 555,552 ms per second. Then 555,552 / 5,600 = 99.2, so 100 app servers. Star list reads: 69,444 x 10 = 694,440 per second. Each app server asks for each star at most once every 2 seconds: 100 x 1,000 / 2 = 50,000 per second. That is 694,440 / 50,000 = 13.9 times fewer. The cost: a star post can appear 2 seconds late.

Step 6: ranking. Assumption: scoring one post costs 2 microseconds of CPU. One open scores 300 candidates: 300 x 2 = 600 microseconds = 0.6 ms. At the peak: 69,444 x 0.6 = 41,666 ms per second = 41.7 cores. A ranker server gives 5,600 ms, so 41,666 / 5,600 = 7.4, which is 8 servers. A saved list is 100 x 8 = 800 bytes. Lists alive = opens per second x 600 seconds = 69,444 x 600 = 41.7 million at the peak. That is 41.7 million x 800 bytes = 33.3 GB.

Step 7: photos. Photos a day: 20% x 40,000,000 = 8 million. Each takes 2,000 + 100 + 30 = 2,130 KB. So 8,000,000 x 2.13 MB = 17.04 TB a day (1 MB = 1,000 KB). Post rows are 40,000,000 x 1 KB = 40 GB a day, so photos are 17,040 / 40 = 426 times more. Each open shows 20 x 20% = 4 photos of 100 KB, which is 400 KB. A day: 2 billion x 400 KB = 800 TB = 9.26 GB per second = 74 gigabits per second. At the peak: 222 gigabits per second. If the CDN hit rate is 95% (assumption), the origin (our own storage) serves 5% = 11.1 gigabits per second.

Step 8: a part fails.

• The ranker has a bug and takes 2 seconds. The 50 ms timeout limits the extra wait to 50 ms, and the user sees time order. Without it, every open waits 2 seconds.
• A list server dies. Its follower copy takes over (lesson 41). If both copies are lost, the list is rebuilt when its user opens the app, with one pull of 200 lookups (lesson 76).

• The hybrid timeline solves slow reads and star bursts. It costs a merge on every open, a star cache and a threshold to watch. I would move the threshold when spare list capacity changes.
• The ranking hook solves relevance with little risk. It costs 8 ranker servers and 33.3 GB of saved lists. I would switch to time order if the cost is too high or users want the newest first.
• A CDN solves photo traffic: of 222 gigabits per second at the peak, only 11.1 reach our storage. It costs CDN fees and two extra copies of each photo.
• The post cache solves 1,388,880 reads per second. It costs old text if a delete leaves the entry. I would remove the entry on every edit and delete.

"A ranked feed needs a different design from a time feed." The candidates are built the same way. Ranking is one step after them, behind a timeout.

"Compute the score when the post is written and keep the lists sorted by it." A score changes with likes and age. Post C scored 68.7 only after 5 hours. At write time it scored 0.5. A stored score would be wrong within minutes.

"Store the photo in the post row and send it from the app servers." Photos are 426 times the size of post rows. App servers would carry up to 222 gigabits per second.

1. Why does a feed list hold only post IDs? Where do the text and the photo of a post come from?
2. An app has 50 million daily users, and each opens the feed 8 times a day. A page shows 20 posts. Peak is 3 times the average. A cache server does 70,000 reads per second. How many cache servers do the post reads need?
3. The ranker becomes very slow. What does the user see, and what protects the feed?