Skip to content

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
Practice this question

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

AskWhy it mattersA 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.

The requirements menu

RequirementScopeWhy

Create and like posts

Core

The write side that feeds search. It matters because each post fans out to many keyword lists and each like wants to move its post in an ordering.

Search posts by keyword

Core

The product. One keyword in, a page of matching posts out, and it has to work when tens of millions of matching posts share the keyword.

Sort results by recency or by like count

Core

Two orderings, and the second one changes constantly. Most of the design difficulty comes from keeping the like order cheap to maintain and cheap to read.

Page through results with a cursor

Optional

Take it: the API already returns a cursor. Make it carry the last result's sort value and post id rather than a numeric offset, so paging resumes after the last result as posts arrive, though like-score order can still shift between pages. It also lets you return a short first page and keep the latency target.

Delete or edit posts and have search reflect it

Optional

Leave it unless asked. Deletion means touching each keyword list the post was added to, or filtering deleted ids at read time. Say which you'd do and move on.

Treat hashtags as keywords

Optional

Cheap to take: the tokenizer emits the tag as one more keyword. Worth a sentence because it shows you've thought about what the tokenizer emits.

Search by several keywords combined with AND

Optional

Leave it for this round. Intersecting lists favors keeping each post's keywords together on one shard, which is the opposite split from the one single-keyword search wants. Name the tension if you have time.

Show a fresh like count next to each result

Optional

Take it if you use approximate scores in the index: reading fresh counts for the page you return fixes the displayed numbers and the order of that page at once.

Fuzzy matching and synonyms

Out of scope

Depending on how it's done, each can multiply the lists a search reads or the keywords written per post. Say the tokenizer is where you'd add stemming later, and stop.

Personalised results

Out of scope

Results that differ per viewer remove the shared cache in front of search, so confirm this is out before you draw that cache. It comes back as the closing question.

Privacy rules on who sees a post

Out of scope

A real system filters results by audience, which is also per viewer. Out for this round; mention that one common place for it is after the index lookup, as a filter on the candidates, though it can also be built into the query or the index.

Relevance ranking beyond recency and likes

Out of scope

A relevance score is a third ordering and a whole ranking pipeline. The two fixed orderings are what make precomputed lists work.

Images and media

Out of scope

Search indexes text; media lives in blob storage and is fetched by the post service when results are rendered.

Non-functional requirements

RequirementWhat 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

QuantityWorkingResultWhat 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

EntityWhat 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

EndpointNotes

GET /search?keyword={k}&sort={recency|likes}&cursor={c} → { results, next_cursor }

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.

POST /posts { content } → { post_id }

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.

POST /posts/{id}/likes

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

readappendClientAPI gatewayWrite servicesSearch serviceRecency index

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.

eventsappendmilestonesreadcandidatesoverflowoverflowmissClientAPI gatewayWrite servicesSearch serviceKafka logIngestionRecency indexLikes indexCold blob index
The whole design

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?

A concept that helps here: Inverted indexesA concept that helps here: Sorted sets and leaderboardsA concept that helps here: Blob storage and presigned uploads

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?

A concept that helps here: Approximate countingA concept that helps here: Stream processing and windowsA concept that helps here: Sorted sets and leaderboards

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?

A concept that helps here: Sharding and partition keysA concept that helps here: Hot keys and hot partitionsA concept that helps here: Queues and logs

Concepts this guide uses

Sources

  1. Wikipedia: Inverted index
  2. Redis documentation: ZADD
  3. Redis documentation: ZREVRANGE
  4. Redis documentation: LTRIM
  5. Redis documentation: ZREMRANGEBYRANK
  6. Redis documentation: Scale with Redis Cluster
  7. Redis documentation: Redis cluster specification
  8. Confluent: What is Kafka retention?
  9. CubeAPM: What is Kafka consumer lag and why does it matter?
  10. University of Waterloo thesis abstract: Inverted Index Partitioning Strategies for a Distributed Search Engine
  11. intervu.dev: Social Post Search System Design: FAANG Interview Guide
Sign in to report a mistake