How to design Facebook post search
The first sections are free. The deep dives, level expectations and quiz are part of Pro.
On this page
- The problem
- Clarifying questions
- The requirements menu
- Non-functional requirements
- Estimates
- Core entities
- The API
- The high-level design
- What breaks first
- The deep dives
- Entity fields
- The inverted index and sorting
- Likes and write volume
- Splitting the index and keeping it fresh
- Variants
- What each level is expected to show
- The 30-second answer
- Quiz
The problem
Post search takes one keyword and returns the posts that contain it, newest first or most liked first, across a social network's whole history of posts, and the interviewer rules out an off-the-shelf search engine. The answer turns on an inverted index that lives in memory, with each keyword's matches kept in both orderings ahead of time so a search reads the top of a list instead of sorting, and on seeing that the write side dominates: 10,000 new posts per second, each touching between 10 and 1,000 keyword lists, plus 100,000 likes per second that each want to move their post up the most-liked ordering.
Clarifying questions
| Ask | Why it matters | A typical answer |
|---|---|---|
Is a search one keyword, or phrases and several keywords combined? | One keyword means a search reads one list, which lets you split the index by keyword. Several keywords mean intersecting lists, which pushes toward splitting by post and merging across shards. | One keyword, matched exactly. Fuzzy matching and synonyms are out of scope. |
Does everyone who searches the same keyword see the same results? | Shared results can be cached in front of the search service and at the edge. Results that depend on the viewer, for privacy or friendship, make that cache worthless, so it's worth asking before drawing it. | Yes for this round: results are not personalized and privacy rules are out of scope. Our prepared closing question brings back favoring friends' posts, so keep the door open. |
How soon after someone posts must the post show up in search? | It decides whether indexing may run asynchronously behind a log and how much lag that log may build up before it's a problem. | Within 1 minute. Posting itself should not wait for indexing. |
Which orderings do we support, and how exact must the most-liked order be? | Each ordering is a second structure per keyword, and exactness decides whether each like must reach the index or whether an approximate score with fresh counts on display is acceptable. | Newest first and most liked first, nothing more. Our advice: propose an approximate like order corrected with fresh counts for the page you return, and ask whether that's acceptable. |
How far back do searches reach, and may old or unpopular posts be slower to find? | Ten years of posts don't fit the fast tier, so you need permission for a slower path to old and rarely searched content. | 10 years of posts must be findable, and a slower answer for old or unpopular posts is fine. |
What are the volumes: users, posts, likes and searches? | The ratio of writes to searches decides where the design effort goes. Here the surprise is that likes outnumber posts and both outnumber searches. | A billion users, 10,000 new posts per second, 100,000 likes per second, about 10,000 searches a second bursting 10 times or more, answered in under 500 ms. |
Non-functional requirements
| Requirement | What it forces |
|---|---|
Median query answers in under 500 ms | No scan over posts and no sorting of a large match set at query time. In this design each keyword's matches are kept already sorted in both orders, and a search reads the top of one list, fetches the page's posts and returns. |
A new post is searchable within 1 minute | Indexing can run asynchronously behind a durable log, but the lag of that log has to be watched and the worker pool sized so a burst of posts drains within the minute. Any shared result cache in front of search gets a short lifetime for the same reason. |
Every post can be found, old or unpopular ones too, even if slower | Dropping old posts from the index is not allowed, so the memory tier can't be the whole index. Each keyword's in-memory list is capped and the rest spills to cheaper storage that a search falls back to. |
High request volume and high availability | Stateless search servers behind a gateway, an index split across many nodes with replicas, and a log between the writers (post service, like service) and the index so a slow or dead indexing worker delays posts rather than losing them or slowing the post service. |
Estimates
| Quantity | Working | Result | What it sizes |
|---|---|---|---|
Index writes a second caused by new posts | 10,000 posts per second × 10 to 1,000 keywords per post = 100,000 to 10,000,000 appends a second; two structures per keyword doubles it: up to 2,000 writes per post and 200,000 to 20,000,000 writes a second | Between 200,000 and 20 million index writes a second from new posts, before likes | The write load on the index, which is what the index must be sized for, not the 10,000 searches a second. |
Writes against searches | 200,000 to 20,000,000 post index writes a second, plus likes written through to a sorted set per keyword: 100,000 likes × 10 to 1,000 keywords = 1,000,000 to 100,000,000 score updates a second; against 10,000 searches a second that is (1,200,000 to 120,000,000) ÷ 10,000 ≈ 120 to 12,000 | Likes written through would add 1 million to 100 million score updates a second; writes outnumber searches by about 120 to 12,000 times | Why this is a write-heavy system despite being a search product, and why the ingestion path gets the design effort. |
Entries in a full index of 10 years of posts | 3.6 trillion posts × 10 to 1,000 keywords = 36 trillion to 3.6 quadrillion entries; at 8 bytes per post id (a 64-bit id), 36 × 10^12 × 8 B ≈ 288 TB and 3.6 × 10^15 × 8 B ≈ 28.8 PB per ordering; two orderings double it | Roughly 288 TB at the low end and about 29 PB at the high end for one ordering, before any overhead per entry | Why the whole index can't live in memory once years of posts accumulate, and why each keyword's hot list is capped with the rest in blob storage. |
Bytes moved to sort one popular keyword at query time | 10 million matching ids × 8 bytes per id = 80 MB read and sorted for one search; if all 10,000 searches a second looked like that, 10,000 × 80 MB = 800 GB a second | About 80 MB per search for one keyword matching 10 million posts | Why sorting matches at query time fails the 500 ms target for popular keywords, and why both orderings are kept ahead of time. The 10 million is an illustration of the tens of millions in the scenario, not a measured figure. |
Index writes while a like count climbs to 1,000 | Writing each like: 1,000 writes. Writing at powers of ten: at 1, 10, 100 and 1,000 likes, four writes. Writing at powers of two: 1, 2, 4, 8, 16, 32, 64, 128, 256 and 512, ten writes | Four or ten milestone writes per keyword instead of 1,000; with 10 to 1,000 keywords per post, that is 40 to 10,000 sorted-set writes (4 × 10 to 10 × 1,000) instead of 10,000 to 1,000,000 (1,000 × 10 to 1,000 × 1,000) | How much the likes index write rate drops when scores are updated at milestones, which is what makes 100,000 likes per second affordable. |
Searches a second at a burst | 10,000 searches a second × 10 = 100,000 searches a second | About 100,000 searches a second during a burst | What the search servers and the hot index shards face when a name trends, and the point where one keyword's shard becomes the limit. |
Backlog after ten minutes of stalled indexing | 10 minutes = 600 seconds; 10,000 posts per second × 600 s = 6 million posts; 100,000 likes per second × 600 s = 60 million like events | About 6 million posts and 60 million likes waiting in the log | What the log must hold during an outage and how much extra worker capacity is needed to drain it: at double the normal rate the backlog clears in another ten minutes. |
Memory for one capped keyword list | A cap of 10,000 entries × 8 bytes per id = 80 KB per ordering per keyword, before Redis overhead per element | About 80 KB per keyword per ordering at a cap of 10,000 | Why capping lists makes the hot tier's size depend on the number of keywords rather than the number of posts. |
Core entities
| Entity | What it holds |
|---|---|
Post | One row per post: who wrote it, the text the tokenizer reads, and when it was created. |
Like | A user's like, kept mainly as a count per post. |
Keyword index | One entry per keyword: its matching post ids in creation order and in like order, capped, with the overflow in blob storage. |
User | Who posts, likes and searches. Accounts are out of scope, so this stays a stub. |
The API
| Endpoint | Notes |
|---|---|
| One keyword, one ordering, one page. The cursor carries the last returned result's sort value (its creation time or its approximate like score) together with its post id, so the next page resumes after that point as new posts arrive (a post whose like score moves across the cursor can repeat or be skipped), and it crosses into the cold object once the hot head is exhausted. Results are the same for everyone, so this response can be cached with a short lifetime. |
| Writes the post and publishes an event to the log, then returns. Tokenizing and indexing happen behind the log, within the one-minute target. The caller is the authenticated user, so no user id in the body. |
| Increments the post's count in the like service and publishes a like event. Make it idempotent per user and post so a retried request doesn't count twice. |
The high-level design
Step 1 of 4
Posts, likes and a keyword index
Start with the two sides of the product. Clients reach an API gateway. The write services (the post service and the like service) own posts and like counts in their own stores. For search, add an inverted index: a map from each keyword to the ids of the posts containing it, which is the structure that makes full-text lookup fast at the cost of extra work when a document is added. In this first cut the post service appends the id of the post being created to each keyword's list as part of creating it, and the search service reads a keyword's list, fetches the posts from the post service and returns a page. Sorting by likes means pulling the whole list and sorting it, which is the first thing to fix.
What breaks first
The deep dives
The inverted index and sorting. Someone searches a popular name. Tens of millions of matching posts exist, and the searcher wants the most liked first, in under 500 ms. What does the index hold per keyword, and how does one search get its page without sorting the whole match set?
Likes and write volume. Likes arrive at 100,000 a second, ten times the rate of new posts, and each one wants to move its post in the most-liked ordering under each of the post's keywords. How does the index keep up, and what does the ordering lose?
Splitting the index and keeping it fresh. The index holds trillions of entries, new posts must be searchable within a minute, and one name suddenly trends. How do you split the index across machines, and what keeps new posts flowing into it during a burst or an outage?
Concepts this guide uses
Sources
- Wikipedia: Inverted index
- Redis documentation: ZADD
- Redis documentation: ZREVRANGE
- Redis documentation: LTRIM
- Redis documentation: ZREMRANGEBYRANK
- Redis documentation: Scale with Redis Cluster
- Redis documentation: Redis cluster specification
- Confluent: What is Kafka retention?
- CubeAPM: What is Kafka consumer lag and why does it matter?
- University of Waterloo thesis abstract: Inverted Index Partitioning Strategies for a Distributed Search Engine
- intervu.dev: Social Post Search System Design: FAANG Interview Guide