Problem RestatementProblem
Design search over status posts on a social network like Facebook. A user types keywords, like pizza or pizza AND (napoli OR brooklyn), and gets matching posts, newest (or most relevant) first, with stable pagination. Posts are created, edited and deleted all the time, and new posts should be searchable within seconds. The corpus has billions of posts. Meta asked this several times, including boolean expressions with precedence and parentheses.
RequirementsRequirements
1.1 Functional
- Keyword search, and boolean queries with AND, OR, NOT and parentheses.
- Sort by recency (or relevance), paginate stably.
- Reflect creates, edits and deletes quickly.
- Only return posts the searcher is allowed to see.
1.2 Non-Functional
- Latency under ~200 ms.
- Freshness: seconds.
- Scale: billions of posts, thousands of queries/sec.
1.3 Scale Estimates
- 5B posts, 500M new posts/day ≈ 6K writes/sec.
- 20K search queries/sec.
- The index is roughly the size of the text itself: tens of TB, sharded across many machines.
1.4 API Design
GET /v1/search/posts?q=pizza AND (napoli OR brooklyn)&cursor=&limit=20
The Inverted Index
- Tokenize each post: lowercase, remove punctuation, split into words, optionally stem ("running" → "run") and drop very common words.
- Build an inverted index: for each term, a posting list of post IDs that contain it, sorted by post ID. If post IDs increase over time (e.g., Snowflake-style IDs), this order is also newest-last, which makes "newest first" easy.
- Queries:
A AND B→ intersect two sorted lists (walk both with two pointers, O(n + m); or skip ahead when one list is much shorter).A OR B→ merge (union).A AND NOT B→ difference.- Parentheses and precedence: parse the query into a tree (NOT binds tightest, then AND, then OR), and evaluate bottom-up. Start with the rarest terms to keep intermediate lists small.
High-Level ArchitectureArchitecture
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
PW["Post writes"] --> K[("Kafka - post events")]
K --> IX["Indexers - tokenize"]
IX --> S1[("Index shard 1 - posts by ID range or hash")]
IX --> S2[("Index shard 2")]
IX --> S3[("Index shard N")]
U["Searcher"] --> Q["Query service - parse, fan out, merge"]
Q --> S1
Q --> S2
Q --> S3
Q --> PV["Privacy filter"]
PV --> UDeep Dive — Sharding the index: by document or by term?Deep dive
Billions of posts will not fit in one index, so the index has to be split. There are two ways to cut it, and they fail very differently.
Keep one index
One machine holds the full inverted index. Every query is answered locally, boolean logic is trivial, and there is nothing to merge.
The posting list for a common word like pizza alone runs to hundreds of millions of entries; the whole index is orders of magnitude past one machine's memory and disk. Indexing throughput is capped at one machine's write rate while the whole platform produces posts, and the machine is a single point of failure for all of search. This rung exists only to make the next choice concrete.
Shard by term
Give each shard a set of terms and the complete posting list for each. A query for pizza touches exactly one shard — attractive, because most queries are short and would only wake a handful of machines.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["pizza AND brooklyn"] --> S1["Shard holding 'pizza' - 400M postings"]
Q --> S2["Shard holding 'brooklyn' - 90M postings"]
S1 -->|"ship the posting list"| X["Intersect across the network"]
S2 -->|"ship the posting list"| X
X --> HOT["'pizza' shard also serves every query containing pizza"]Two problems, and both get worse with scale. An AND across terms has to intersect posting lists that live on different machines, so the big lists move across the network per query. And term frequency follows a power law: whichever shard owns the common words serves a large share of all traffic while other shards idle. Writing a single post also touches as many shards as it has distinct terms.
Shard by document, with time tiers
Each shard indexes a subset of posts — by hash of post id, or by time range — and holds every term for those posts.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["pizza AND (napoli OR brooklyn)"] --> B["Query service - scatter"]
B --> H["Hot tier - last few days, in memory"]
B --> W["Warm shards - on disk"]
B --> C["Cold shards - archive"]
H --> M["Merge top-K - each shard evaluates the full query locally"]
W --> M
C --> M
M --> R["Results - stop early when recent results suffice"]Every shard can evaluate the whole boolean expression by itself, so nothing but a small top-K list crosses the network. A new post is written to exactly one shard. Load spreads evenly because documents are distributed by hash, not by the popularity of the words in them.
The cost is that every query fans out to every shard, which makes the tail latency of the slowest shard the latency of the query. Time tiers are what make that affordable: keep the last few days in fast in-memory shards and older posts on disk, and since most searches want recent posts, the query can often stop once the hot tier has produced enough results and never wait on the cold ones.
Key FlowsFlows
5.1 Indexing a new post
- The post is saved. An event goes to Kafka.
- An indexer tokenizes it and appends the post ID to each term's in-memory posting list in the right shard. It's searchable within seconds.
- The in-memory segments are periodically flushed into immutable on-disk segments (as Lucene does) and merged in the background.
5.2 Edits and deletes
- Delete: add the post ID to a deleted set (a bitmap) checked at query time. Segment merges drop them for good.
- Edit: delete + re-index the new version.
5.3 Query
- Parse into a boolean tree and validate it (limit query complexity).
- Fan out to shards (or only the recent tier first). Each returns its top K by recency or score, plus a cursor.
- Merge, remove posts the user can't see (privacy: friends-only, blocked users), and return a page with a cursor such as
(last_post_id), so the next page continues exactly there.
Ranking and Privacy
- Recency sort is natural with time-ordered IDs. Relevance adds BM25 text scoring (how often and how rare the term is), engagement and social closeness.
- Privacy: index the post's visibility (public, friends, custom) and author. At query time, filter using the searcher's friend list (cached). For public-only search, keep a separate, simpler index of public posts.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Index | Inverted index, sorted posting lists | Fast AND/OR | Scan posts: impossible at scale |
| Sharding | By document, with time tiers | Local boolean evaluation, cheap writes | By term: hot terms, cross-shard joins |
| Freshness | In-memory segments + background merge | Seconds to searchable | Batch rebuild: hours of delay |
| Deletes | Deleted bitmap + merges | Instant hiding | Rewrite index: slow |
Wrap-UpWrap-up
Tokenize posts into an inverted index with sorted posting lists, and evaluate boolean queries by parsing them into a tree and intersecting, merging and subtracting lists, rarest terms first. Shard by document with hot recent tiers, fan out and merge top results with cursor pagination, index new posts in real time via Kafka into in-memory segments, hide deletes with a bitmap, and apply privacy filters before returning results.