Design Facebook

Clarify the ask

The interview question is to design Facebook.

The core is people, friendships and posts. A user finds friends, posts to them, and reads what friends posted.

Messaging stays out of this design. Message delivery, if needed, reuses the chat design.

Likes and comments are part of a post's life. They are small attachments to posts, not separate systems here.

Estimate the scale

The service has 2,000,000,000 users.

The average user has 300 friends. That average is a stated design figure for this problem.

2,000,000,000 users × 300 friends each = 600,000,000,000 counted friendships.

Each friendship joins two people, so that count names every friendship twice.

600,000,000,000 ÷ 2 = 300,000,000,000 friendship edges counted once.

1,000,000,000 posts a day ÷ 86,400 seconds = 11,574 posts per second.

Feed reads dwarf post writes. Reading the graph and the feed is the heavy direction.

What the design must get right

A new friendship must show for both people quickly. A friendship one side cannot see feels like a bug, not a delay.

Posts carry an audience, the set of people allowed to see them. The design must never show a post outside its audience.

The audience check belongs in every read path. Feed, search and profile pages all enforce the same rule.

The service is global from the start. Friends and readers sit on different continents as a normal case, not an exception.

The high-level shape

A social graph is a network drawn as points for people and lines for their friendships.

One store holds the friendship graph itself. It answers who is connected to whom, and little else.

Posts live in their own store, keyed by author. The feed is built from posts and the graph together.

Search walks both words and connections.

Friendship is the core object here. Every other part of the design reads the graph or writes to it.

Where the design breaks

The graph is far too large for one machine. It must be sharded, and a friendship can span shards.

A famous account gathers connections far beyond the average. Its corner of the graph becomes a hot spot.

Regions disagree during failures. Two sides of the world can hold different views of the same friendship for a while.

The graph comes first in the design. Search and regions build on it.

Data model: the social graph

The social graph is this problem's central data.

A node is a point in the graph that stands for one person. An edge is a line between two nodes that stands for one friendship.

Friendship here is mutual. One edge serves both people, because each can see the other as a friend.

Following a public page is different. That link runs one way, and the graph stores it as a different kind of edge.

Questions the graph answers

Who are this person's friends? The graph answers by reading one adjacency list.

Are these two people friends? The graph answers by checking one list for the other.

What friends do they share? The graph answers by overlapping two adjacency lists.

Who might this person know? The graph answers by walking to friends of friends.

Adjacency storage

Adjacency means the list of neighbours joined directly to one node. The store keeps one adjacency list per user, holding friend identifiers.

The graph is sharded by user identifier. One user's whole list lives on one shard, so a friend list reads from one place.

Each friendship appears in two lists, one for each person. That duplication is deliberate, and the storage arithmetic shows its size.

300,000,000,000 edges × 2 lists = 600,000,000,000 list entries.

In this design one list entry takes 16 bytes, enough for an identifier and a little bookkeeping.

600,000,000,000 entries × 16 bytes = 9,600 GB of adjacency data.

Reading the graph

A friend list read is one shard lookup. The profile page and the feed builder both start from that read.

A friendship check asks whether one identifier sits in the other's list. The audience check on posts leans on this question constantly.

Mutual friends are the overlap of two lists. Comparing two lists of a few hundred entries is cheap enough to do on request.

Hot lists are cached. A famous account's list is read constantly and changes rarely, which is exactly what a cache rewards.

Writing the graph

Accepting a friend request writes two lists on two shards. Both writes belong to one change, even though they land apart.

If the second write fails, the friendship is one-sided for a while. The design treats a one-sided edge as not yet a friendship.

A background repair pass compares paired lists. It completes or removes half-written edges, so the two sides converge.

Removing a friendship deletes from both lists. A stale entry left behind would wrongly pass audience checks, so removal uses the same repair pass.

Where the graph breaks

A public page holds millions of follower edges. One list that large cannot live or be read as a single unit.

Oversized lists are split into pieces across shards. Readers fetch the pieces they need, and counts are kept separately.

A lost shard loses the lists it held. Replicas of each shard are what the reads fall back to.

The graph stays a simple structure under all of this. Points, lines and lists are enough, if the lists are placed and repaired with care.

Deep dive: graph search

Graph search is search that walks the social graph instead of matching only words. A question about friends and their interests becomes a walk from node to node.

Graph search is the search this problem is known for.

The graph holds more than people. Places, pages and interests are nodes too, joined by edges such as lives in or likes.

A typed question is parsed into a start node, a walk and a filter. The answer is the set of nodes the walk reaches and the filter keeps.

Questions as walks

Friends who live in one city is a short walk. Start at the viewer, step to friends, and keep those with an edge to that city.

Friends of friends who like cycling takes two steps out. The second step starts from every friend, not from one person.

Photos of friends works the same way with different edges. Posts and photos hang off their authors by ownership edges.

One walking engine serves all of these. The question changes the edges and filters, not the machinery.

What a walk costs

One user has 300 friends, on the design's average figure.

Each of those friends has 300 friends of their own.

300 friends × 300 friends each = 90,000 friends of friends, before repeats are removed.

A third step would multiply that set again by hundreds. Walks therefore stop at two steps in almost every question.

Filters apply at every step, not only at the end. Keeping only friends in one city shrinks the set before the next step begins.

Indexes beside the graph

Not every question is a walk. Names and post words are matched by an index, the mapping from a word to the items containing it.

The post index grows with posting volume. In this design one index entry takes 100 bytes.

1,000,000,000 posts a day × 100 bytes = 100 GB of new index entries a day.

Attribute lists are precomputed for common filters. The set of users joined to a popular city or interest is built ahead, not during a question.

A good plan starts from the smaller side. A rare interest narrows the walk faster than a common city does.

Freshness and privacy

Every result passes the audience check at answer time. A post its author hid from the searcher never appears, however the walk found it.

Deleted posts can linger in an index briefly. Opening a result re-checks the post store, and a deleted post answers as gone.

New friendships change walk results at once. The walk reads live adjacency lists, so a new friend is reachable immediately.

Privacy outranks freshness here. A slightly stale answer is acceptable, and a leaked one is not.

Where graph search breaks

Dense corners of the graph explode a walk's cost. A question touching a huge page can reach millions of nodes in one step.

Expensive walks carry a time budget. When the budget ends, the search returns the partial answer it has, marked by ranking below complete ones.

Graceful degradation keeps the common questions fast. Rare, huge questions degrade first, and everyday searches of friends stay whole.

Deep dive: multi-region

Multi-region design runs one service across data centers on several continents at once. Facebook's readers and writers are everywhere, so no single region can serve the whole world well.

A round trip inside one data center takes about 0.5 milliseconds. A round trip across an ocean takes about 150 milliseconds.

That gap shapes the whole regional design. Local answers are nearly free, and global agreement is always bought with waiting.

A home region per user

Each user's data is mastered in a home region, the region nearest that user. Writes for that user are led by the home region.

Copies of the data live in other regions for reading. A traveller reads a local copy instead of crossing an ocean for every screen.

Replication lag is the delay before a copy receives the latest change. Distant readers can see data that is seconds behind the home region.

A friendship joins two home regions whenever the friends live apart. The edge is copied to both, one copy under each person's home.

Consistency choices

PACELC frames the choice. During a partition the design picks availability or consistency, and in normal times it picks latency or consistency.

Posts are eventually consistent across regions. A post reaches distant friends after replication, usually within seconds.

Like counts merge counts kept per region. Two regions can disagree briefly, and the merged total settles as copies arrive.

Sign-in data stays strongly consistent in its home region. A password change must not race with an old copy elsewhere.

Friendship edges are copied to both friends' home regions.

Like counts are eventually consistent, merged from regions.

Conflicts between regions

The same profile can be edited in two regions during a partition. Both edits are real, and they disagree when the regions reconnect.

Last-write-wins settles simple fields by time. It is crude, and for a display name it is good enough.

Friendship changes deserve more care than a timestamp. The repair pass reconciles edge pairs after regions reconnect.

Vector clocks can order edits where time alone is not trusted. This design uses them sparingly, on shared objects only.

When a region fails

A failed region's readers move to the nearest surviving region. Their answers come from copies, with longer replication lag until the region returns.

Writes for users homed in the failed region pause or reroute. Rerouting elects a temporary home, and fencing stops the old home writing on its return.

Surviving regions absorb the shifted traffic. Headroom for a neighbour's load is part of the design, not a surprise.

The service degrades before it falls. Distant reads and slower freshness are the graceful price of a lost region.

Evaluation

The Facebook trade-offs weigh graph consistency against global speed. The graph is too large and too spread out for every answer to be instant and exact.

Scale and distance force every choice here.

The graph holds 300,000,000,000 friendship edges counted once. No single machine, and no single region, holds the whole truth cheaply.

Friendship reads are exact, from live adjacency lists. The price paid is two writes for every change.

Friend suggestions are approximate walks, refreshed often. The price paid is suggestions that can lag new friendships.

Cross-region posts are eventually consistent copies. The price paid is distant friends seeing posts seconds late.

Audience checks are checked on every read. The price paid is time spent checking every result.

Exact where it counts

Friendship itself stays exact. Feed building, audience checks and search all trust the edge, so the edge cannot be approximate.

Exactness costs two list writes per change and a repair pass forever. The design pays it because everything else stands on the graph.

Suggestions can be approximate safely. A suggestion list refreshed from recent walks may miss yesterday's friendship and still be useful.

Counts sit between the two. A like count a moment behind is normal, and nobody can act on the difference.

Duplication against read speed

Every friendship is stored twice, once in each person's list. Cross-region friendships are then copied again into two home regions.

Each copy makes some reader's answer local and fast. Each copy is also one more write to keep honest.

The alternative is fetching across shards and oceans at read time. Reads outnumber writes here by far, so the design duplicates.

Privacy over convenience

Audience checks run on every read path, including search results built from precomputed sets. The check costs time on every single answer.

Skipping checks for speed would leak private posts eventually. One leak costs more trust than years of small delays.

This is the one trade-off the design refuses to make. Convenience yields to privacy in every conflict between them.

Feed cost against graph truth

Fan-out on write would copy every post into hundreds of feeds. At this posting rate the copies multiply fast.

Fan-out on read avoids the copies and pays at reading time instead. The hybrid remains the sane middle here.

Either way, the feed is a view built over the graph. When feed and graph disagree, the graph is the truth and the feed is rebuilt.

The wrap-up

The design in one line. A sharded graph of people and friendships, stored at both ends of every edge, copied across regions, and checked on every read.

Search walks that graph with strict step limits and early filters. Regions accept brief disagreement everywhere except where trust is at stake.

The graph is the product's memory of who knows whom. Keeping that memory exact, private and fast enough is the whole design.

The Facebook estimate at a glance