In this article
Before you start
This page belongs to the distributed systems interview guide and assumes you can do a quick size estimate; the back-of-the-envelope estimation page teaches it.
Why interviewers ask this
The question tests whether a candidate can turn one vague product sentence into numbers, a data model and a defensible trade-off. Candidates report variants such as a Twitter-like service, an Instagram feed, a friends activity feed and a Facebook-like platform that shows friend counts, and a first-, second- or third-level connection badge.
A weak answer draws boxes labeled "feed service" and "database" and stops. A strong answer separates the two problems: the graph (who follows whom, read constantly) and the feed (what each person sees, built from posts). It states the read-to-write ratio, picks when to build feeds, and says what happens for an account with a huge audience. A Staff-level answer also names what is allowed to be stale, because the product tolerates a short delay in a feed but not a lost post.
News feed and social graph from first principles
- A social graph is a data model of people and other objects, called nodes, joined by typed, directed links, called edges, such as follows, friends, likes and comments, that lets a service ask who is connected to whom.
- News feed
- A news feed is a per-user, time-ordered list of recent posts from the accounts that user follows, assembled by the service so a person can open one screen instead of visiting every profile.
In plain words
Think of a newspaper stand. You can pre-assemble a bundle for every reader each time a story is printed. Or you can wait for the reader and gather stories from each publisher they like. Bundling ahead makes pickup quick but needs much copying. Gathering on arrival saves copying but makes each pickup slow. The analogy breaks in one place: a stand has a fixed number of readers, while a feed service has accounts whose follower counts differ by millions.
In one precise sentence, the design stores edges once and posts once. Then it either precomputes each feed (fan-out on write) or computes it at read time (fan-out on read).
Step 1: Model the graph and the posts
Store two things separately. The graph is a set of typed objects and typed, directed edges. Bronson et al. (2013) describe Facebook's version this way and note that an association is often paired with an inverse edge, so a friend link exists in both directions. A follow link is one directed edge; a friend link is two.
A post is one row: an id, an author, a time and a body. Index follow edges both ways, because feed building needs "who follows author X" (followers) and the follow list of a reader needs "whom does user Y follow". Input: a follow action or a new post. Output: one or two edge rows, or one post row. Nothing about feeds exists yet; you have only the raw facts a feed is built from.
Step 2: Build the feed by fan-out on write, fan-out on read or both
Fan-out on write copies the id of each new post into the cached feed list of every follower, so reading a feed is one lookup. Fan-out on read stores nothing per follower: at read time the service fetches the follow list, pulls each followed account's recent posts and merges them by time. Write is cheap and read is expensive in the second design, and the reverse in the first.
The deciding number is the follower count. For ordinary accounts, pushing is fine because a feed is read far more often than a post is written. For an account with tens of millions of followers, one post becomes tens of millions of writes, so the common answer is a hybrid: push for ordinary accounts, and pull the few very large accounts' recent posts at read time. Krikorian's Timelines at Scale talk is described as covering the architecture Twitter used for thousands of events a second. Where to draw the line is a tunable threshold, not a fixed constant.
Text description of the diagram
- Fan-out on write does its work when a post is written.
- Fan-out on read does its work when the feed is opened.
- A hybrid pulls the recent posts of very large accounts at read time.
Step 3: Serve the feed from a cached list and a cursor
The read path fetches the reader's cached feed list, a short list of post ids, looks up the post bodies, and returns one page. Keep only a bounded number of ids per user, because few people scroll far. If the feed list is missing (a new user, an evicted cache entry), rebuild it with the fan-out-on-read method and store the result.
Page with a cursor, not an offset. A cursor is the id or timestamp of the last item the client saw, so "next page" means "posts older than this". An offset page shifts whenever a new post arrives at the top, so a reader would see duplicates. Bronson et al. (2013) describe the same idea for the graph: lists are kept by time and a read asks for the most recent slice. For ranking, the simplest answer is time order; a ranked feed adds a scoring step before returning the page. The application programming interface (API) design page covers cursor pagination.
Step 4: Scale the graph with shards, a cache and one leader per shard
The graph is read-heavy. In Facebook's trace, 99.8% of requests were reads and 0.2% were writes, a ratio of about 499 to 1 (computed from those two figures).1 So the design optimizes reads: shard the data by a key so no server holds it all, and put caches in front of the database.
The same paper reports that Facebook's web servers originally read MySQL directly with memcache as a lookaside cache, and that the graph store replaced this for the data types that fit its model. Each shard has one leader and every write for that shard goes through it, so writes are consistent. Followers (cache servers) receive updates asynchronously, which is called eventual consistency: replicas agree after a short delay. The paper measured replica lag under 1 second 85% of the time and under 10 seconds 99.8% of the time. The cache layer itself is described in Scaling Memcache at Facebook.
Step-by-step description
- Posts and follow edges are stored separately.
- Workers copy each post id to followers.
- A read is one cached list.
- Shards and caches serve the read-heavy graph.
- Posts and follow edges are stored once.
- Fan-out workers copy each post id into the feed cache of every follower.
- The feed cache serves each read from one list.
- The graph is sharded and cached in front of the database.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
The inputs are assumptions, not measurements: 100 million daily active users, 2 posts per user per day, 200 followers and 200 followed accounts per user on average, 10 feed opens per user per day, 800 post ids kept per feed at 8 bytes each (all illustrative).1
Fan-out on write turns 200 million posts a day into 40 billion feed-list writes a day, about 462,963 a second, which is 40 writes for every feed read. Fan-out on read turns 1 billion feed opens into 200 billion follow-list lookups a day, about 2,314,815 a second. Feed reads are about 11.6 thousand a second (11,574.1 on average). The feed lists take 6,400 bytes per user, 640 gigabytes in total, or 1,920 gigabytes with three replicas.1
| Quantity (illustrative inputs) | Value |
|---|---|
| Posts per day | 200,000,000 |
| Feed reads per day | 1,000,000,000 |
| Feed reads per second, average | 11,574.1 |
| Fan-out on write: feed-list writes per day | 40,000,000,000 |
| Fan-out on write: writes per second | 462,963 |
| Fan-out on read: lookups per day | 200,000,000,000 |
| Fan-out on read: lookups per second | 2,314,815 |
| One feed list (800 ids, 8 bytes each) | 6,400 bytes |
| All feed lists, one copy | 640 gigabytes |
| One post from a 50-million-follower account at 20,000 writes a second | 2,500 seconds (41.7 minutes) |
The last row is why the hybrid exists: one such post equals 250,000 posts from an ordinary 200-follower account.1 The sizing method is the one in back-of-the-envelope estimation.
Text description of the diagram
- Feed reads are about 11.6 thousand a second.
- Fan-out on write needs about 463 thousand feed-list writes a second.
- Fan-out on read needs about 2,315 thousand follow-list lookups a second.
Trade-offs and edge cases
No fan-out strategy wins every row, so the workload decides. Push gives fast reads and wastes writes on followers who never log in; pull wastes read work on every open; a hybrid needs a threshold and two code paths, and a feed must merge pushed and pulled posts correctly.
Edge cases to name:
- Celebrity posts. Delivery takes minutes (41.7 in the example above), so pull large accounts at read time instead.
- Counts. Do not count edges by scanning. Facebook's graph store has a separate count query, and 1% of the counts it returned were 512K or more, so counts are stored and cached.1 A friends-count-for-millions-of-posts question is answered with stored counters.
- Deletes and unfollows. A deleted post must disappear from copied feed lists; store ids and check the post store when rendering.
- Staleness. Feeds can lag; read-after-write can break after a failover, so show a user their own new post locally.
- Graph databases. A social graph does not require one: Facebook served its graph from sharded MySQL with caches and a fixed set of queries, although its interface is graph-shaped (Bronson et al., 2013).
For the chat variant, which needs a live push channel, see designing a chat system.
How to answer it in an interview
How would you design a news feed and a social graph?
I model the social graph as users and directed follow edges, sharded by user id with a cache in front, because reads dominate. A post goes to a post store, and fan-out workers push its id into each follower's cached feed list, so reading a feed is one lookup. For accounts with huge follower counts I skip the push and merge their recent posts in when the feed is read. Feeds are eventually consistent, and I page with a cursor, not an offset.
The spoken structure: say the two problems (graph and feed), give the read-to-write numbers, choose push, pull or hybrid with the reason, then name consistency and pagination.
Common mistakes
- "I'll use fan-out on write for everyone." (wrong) One post from a very large account becomes tens of millions of writes. (right) "Push for ordinary accounts, pull for very large ones, with a threshold I can tune."
- "The feed needs strong consistency." (wrong) A short delay is acceptable and buys availability. (right) "Writes go through one leader per shard; followers catch up asynchronously."
- "I'll count friends by counting edges at read time." (wrong) That scans a list that can be huge. (right) "I keep a counter per user and cache it."
- "Page 2 is offset 20." (wrong) New posts shift offsets and cause duplicates. (right) "The cursor is the last post's time and id."
- "Start by choosing a database." (wrong) The choice depends on numbers. (right) "First I estimate reads, writes and storage."
Follow-up questions
How would your system function if it had to scale to hundreds of millions or potentially a billion users?
Shard the graph and the feed lists by user id, keep reads in caches with one leader per shard for writes, and add shards as storage grows; Facebook's published system handled a billion reads and millions of writes a second. Re-run the estimate at the new scale and move the push-or-pull threshold.
How would you show whether a profile is a first-, second- or third-level connection?
Compare friend lists from both ends. First level is one edge lookup; second level is an overlap of the two lists. For third level, fetch one list and the other person's two-hop set, up to 40,000 ids (illustrative);1 any overlap means three hops or fewer. Cache the result per pair.
How do you fetch the friends count for millions of posts?
Store a counter per account and update it when edges change, then batch-read counters for the authors on the page. Never count edges at read time.
Do you need a graph database for a social graph?
Not necessarily. Sharded relational storage with a cache and a small set of fixed queries ran Facebook's graph; a graph database is a choice, not a requirement.
How do you paginate a news feed?
Use a cursor, the time and id of the last item seen, and return posts older than it. See also representational state transfer (REST) API interview questions.
Does a news feed need strong consistency?
No. Eventual consistency is the usual choice for reads; make sure the author sees their own post at once by adding it locally.
- A social graph is typed nodes and directed edges; reads outnumber writes about 499 to 1 in Facebook's published trace.
- Fan-out on write precomputes feeds; fan-out on read builds them when opened; a hybrid pulls very large accounts.
- The follower count decides the strategy, so estimate the numbers before drawing boxes.
- Serve feeds from a cached id list with cursor pagination; accept eventual consistency.
- Count stored, not scanned.
Sources
- TAO: Facebook's Distributed Data Store for the Social Graph — USENIX ATC 2013 (Bronson et al.), 26 Jun 2013
- Timelines at Scale (Raffi Krikorian, QCon San Francisco 2012) — InfoQ, 3 Apr 2013
- Scaling Memcache at Facebook — USENIX NSDI 2013 (Nishtala et al.), 2 Apr 2013
