Design post search (Facebook)

This is an infrastructure problem wearing a product costume. The prompt is Facebook post search, keyword queries over every post ever written, sortable by recency or by like count, with Elasticsearch, Postgres full-text, and every other prebuilt index deliberately off the table. That restriction is the point. The problem tests whether you can lay out data, build an index from primitives, and scale both sides of it, so this write-up builds exactly that, an inverted index by hand.

The instinct on any search problem is to treat reads as the enemy. The estimates say otherwise. A billion users create 10 thousand posts and 100 thousand likes per second against 10 thousand searches per second, and tokenization multiplies each post into roughly a hundred index writes, so the write side outweighs the read side by two orders of magnitude. The second pressure is storage, since ten years of posts is 3.6 trillion documents and 3.6 petabytes of content, set against a 500 millisecond median latency target and a one-minute window for a new post to become searchable.

The design that survives both pressures precomputes everything the read path would otherwise compute, and buffers everything the write path cannot absorb in real time.

Scope and requirements

The product surface is small. Users create posts, users like posts, and users search posts by keyword, with results sortable by recency or by like count. Everything else that makes real search hard is pushed below the line, fuzzy matching, personalization, privacy filters, media, sophisticated relevance scoring, and result pages that update live. Dropping personalization is the single most consequential cut, because it means two people running the same query get the same bytes back, and that one property is what makes the read path cacheable later. It is a cut worth stating explicitly up front, because so much of the design leans on it.

The non-functional requirements carry the design. Median queries return in under 500 milliseconds. New posts become searchable within one minute of creation. Every post stays discoverable forever, with an explicit allowance that old or unpopular posts may take longer to return. The system stays highly available and absorbs a request volume we will estimate next. That allowance for slow old posts is not filler, it is the clause that later licenses a hot and cold storage split, and the one-minute freshness window is the clause that licenses both a write buffer and a result cache.

One more constraint frames everything. With Elasticsearch and prebuilt full-text indexes off the table, the index in this article is assembled from primitive parts, and the parts are Redis structures because they are the simplest honest stand-in for a sharded in-memory key-value store we control. Banning the prebuilt technology is a useful exercise precisely because it separates knowing what an index is from knowing what an index is called.

Sizing the problem

Start with a billion users. The average user creates one post and ten likes per day, and a day rounds up to 100 thousand seconds for clean arithmetic. That gives 10 thousand posts created per second and 100 thousand likes per second, and the imbalance is the first finding, like events outnumber post creations ten to one. Tokenization then multiplies the post side, because indexing a post means one index write per keyword it contains, and a hundred-word post produces on the order of a hundred postings writes. The creation path alone lands near a million index writes per second before a single like is counted.

Reads are almost quiet by comparison. One search per user per day is 10 thousand searches per second, with bursts plausibly reaching ten times that during live events. Put the two sides next to each other and the shape of the system is settled. This is a write-heavy system that happens to have a search box on the front, and a design that spends its whole effort on read scaling has optimized the wrong half.

Storage is the second finding. Ten years of a billion posts a day is 3.6 trillion posts, and at a generous kilobyte of metadata each the corpus is 3.6 petabytes. The index does not need to be anywhere near that, because it stores eight-byte postIds rather than content. Assume around 500 million distinct keywords once bigrams are counted. Each keyword's two orderings are capped at ten thousand entries, but keyword popularity is so skewed that the average keyword holds closer to a thousand ids, and the arithmetic comes out near eight terabytes across both orderings, call it order ten terabytes once structure overhead is included. An index hundreds of times smaller than its corpus is what makes an in-memory design legal at all, and the caps that produce that ratio are a core design decision made now, not an optimization bolted on later.

The API

The system speaks through three operations, two on the write side and one on the read side. In production the write side would not be fresh HTTP endpoints at all, the search system would consume post-created and like-created events off the social product's existing event bus, but modeling them as endpoints keeps the contract explicit and the migration to a stream is mechanical. The read side is one query endpoint behind the API gateway, which owns authentication and rate limiting, and pagination is cursor-based because offset paging over an index this size re-materializes everything it skips.

The search response returns hydrated posts rather than bare ids, which matters for the caching story later, and the requesting user's identity comes from the gateway session rather than anything in the query string. Nothing about the request identifies the user beyond authorization, which is the absence of personalization made visible in the contract.

POST /posts                    (internal, emitted by the Post Service)
  { "postId": 8812993041, "authorId": 45121, "content": "..." }

POST /likes                    (internal, emitted by the Like Service)
  { "userId": 99213, "postId": 8812993041 }

GET  /search?q=taylor+swift&sort=recency&cursor=...
  -> { "results": [ { post }, ... ], "nextCursor": "..." }
     sort is recency | likes

An inverted index, built by hand

Query-time scanning is dead before it starts. A search that greps 3.6 petabytes needs half an hour even with a thousand machines each streaming disk at two gigabytes per second, and a SQL LIKE '%taylor%' against a posts table is the same scan wearing different syntax. The structure that eliminates the scan is the inverted index, a map from each keyword to the list of documents containing it, so the work of finding matches happens once at write time and a query becomes a lookup.

The requirement to sort by recency or like count adds the second twist. Sorting at query time would mean fetching like counts for every candidate in a posting list that could hold millions of ids, on every request. Instead each keyword keeps two precomputed orderings. A creation list holds postIds newest first, which a plain Redis list gives for free since a left-push is chronological order. A popularity structure holds postIds scored by like count, which is exactly a Redis sorted set, an ordered collection with logarithmic inserts and range reads by rank. A query reads one key on one shard and pages through it in order, and the price is that every write must now maintain both structures.

The entities behind this are deliberately thin, a User who writes, a Post with content and an author, and a Like that exists mostly as a count. The index never stores content. The Search Service hydrates ids into posts by calling the Post service, and that separation is the difference between a terabyte index and a petabyte one. Placement is by hash of the keyword over consistent hashing, so one Redis shard owns a keyword entirely and a single-keyword query touches exactly one shard. That choice is called term sharding, and it echoes through the phrase-query and write-volume sections below, because its costs concentrate exactly where its benefit does not reach.

kw:{token}:recent    LIST   postIds newest first, trimmed to ~10k entries
kw:{token}:top       ZSET   postIds scored by like count, trimmed to ~10k
post:{postId}:likes  INT    exact counter, owned by the Like service

placement: shard = hash(token)  ->  one shard owns a keyword outright

The pieces, and how they fit

The write leg starts outside our boundary. A Post Service and a Like Service already exist in the larger product, and they forward create events through a load balancer to an Ingestion Service, which tokenizes content into keywords and writes each keyword's postings on the owning index shard. The read leg is a client hitting the API gateway for auth and rate limiting, then a stateless, horizontally scaled Search Service that looks up each query keyword on its shard, merges when there is more than one, hydrates ids through the Post service, and returns a page.

This first version works and is honest about where it will break. One ingestion tier is absorbing a hundred thousand like events per second synchronously. Every search hits the index fleet even when ten thousand people are typing the same two words during the same televised moment. The index grows without bound toward the four-billion-member ceiling of a Redis collection. Each of those failures gets its own section below, starting with the read path because its fix is the shortest.

Serving ten thousand searches a second

Two requirements were quietly designed to make this cheap. No personalization means identical queries return identical results, and the one-minute freshness budget means a result may legally be up to a minute old. Those are precisely the two conditions under which caching earns its keep, duplicated requests and bounded staleness. So the Search Service checks a Redis result cache keyed on the normalized query, the sort order, and the cursor, and it stores the fully assembled, fully hydrated result page with a TTL under a minute.

Caching the postings lists themselves would add almost nothing, since they already live in Redis memory. The savings come from skipping everything around the index read, the shard lookups, the merge, and above all the hydration calls to the Post service for every result on the page. Head queries dominate real search traffic, a celebrity name during an awards show gets searched thousands of times a minute, and bursts are exactly when duplication spikes, so the cache absorbs the ten-times surge that the raw fleet would otherwise eat. In front of it all a CDN can hold the hottest few thousand query pages at the edge on the same short TTL, because a response with no personalization in it is safe to serve from anywhere.

The alternative that also works is replication, extra read replicas of each index shard with reads balanced across them, and it is worth having anyway for availability. The approach that does not survive contact is per-user caching, because keying on the user multiplies entries by a billion and drops hit rates to nothing. That is why reinstating personalization would knock out this entire section and push the read path back onto replicas plus post-retrieval re-ranking.

Phrase queries without a query planner

A query like Taylor Swift is two posting lists, and the textbook answer is to intersect them at query time. In this design that answer has two problems. The lists for the two words live on different shards, since placement is by keyword hash, so every phrase query becomes a cross-shard fetch before intersection can begin. Worse, the lists are capped. The top ten thousand recent posts containing taylor and the top ten thousand containing swift can overlap on almost none of the posts that actually contain the phrase, so intersecting capped lists does not just cost latency, it silently loses correct results. Intersection was a legitimate design before the caps existed, and the caps are non-negotiable at this scale, so the caps kill it.

The fix moves the work to write time. Alongside single words the tokenizer emits bigrams, adjacent word pairs, so taylor swift becomes a first-class keyword with its own capped creation list and likes set, and a phrase query collapses back into a single-shard lookup. The bill is real. Bigrams roughly double the tokens written per post and they are most of why the keyword estimate sits near 500 million, but the write path is the buffered, horizontally scaled one, and shifting cost from the latency-bound read path onto it is the recurring shape of this whole system. Queries longer than two words chain bigram lookups, taylor swift plus swift tickets, then intersect those far smaller and more selective lists, accepting approximation at the tail.

Production engines make the opposite trade because their requirements are wider. Lucene-family engines and Twitter's Earlybird store positional postings, where each entry carries the term's positions inside the document, so any phrase or proximity query can be verified at query time, and Earlybird runs a full boolean query language over its in-memory segments. Positions are the right call when queries are arbitrary. Ours are one or two keywords with two fixed sort orders, which is why precomputation wins here and why the earlier de-scoping conversation was worth having.

Surviving the write volume

A million postings writes per second does not survive as synchronous fan-out inside an HTTP handler, and the failure mode is the bad one, a New Year's Eve burst overwhelms the ingestion tier and posts are simply lost. The fix is a log in the path. A thin event writer does nothing but append post and like events to Kafka, which buffers bursts durably, and a consumer group of ingestion workers drains the partitions in parallel, each worker tokenizing its posts and writing postings to the keyword shards. The one-minute freshness budget is what makes this legal, since a spike can queue for thirty seconds and still index in time. The same queue was the wrong answer on Robinhood's order-submit path, where the budget was a couple hundred milliseconds, and the pair of examples is worth holding together, the latency budget decides where a log belongs, not a general preference for or against queues.

Sharding the index by keyword spreads the postings writes across the Redis fleet, and the tokenizer drops stop words so the degenerate keywords never exist at all. For calibration that this pipeline shape reaches production scale, Earlybird ingested Twitter's full firehose with a single writer thread per in-memory index segment and made tweets searchable within about ten seconds, six times tighter than our budget, while serving two billion queries a day at a 50 millisecond average.

Likes are the real threat. At 100 thousand per second, writing every like into the sorted set of every keyword of the liked post is on the order of ten million sorted-set updates per second, and no amount of sharding fixes that, because sharding spreads a write storm without shrinking it. The observation that defuses it is that a popularity ranking does not need exact scores. The exact count lives in one cheap counter per post, owned by the Like service. The keyword indexes update only when a post's count crosses a power of two, so a post on its way to a million likes touches each of its keywords about twenty times instead of a million, and the index write rate for hot posts falls by four to five orders of magnitude. Scores in the index are stale by at most a factor of two, which cannot reorder posts whose popularity differs by more than that, and users never see the stale number because result pages hydrate exact counts from the Like service at render time. A Like Batcher on the stream adds one more layer, coalescing bursts of likes on the same post inside a short window before they reach the workers, the same aggregation move as the ad click aggregator.

def on_post_created(post):                    # ~100 tokens per post
    for token in tokenize(post.content):      # unigrams + bigrams, stop words dropped
        shard = redis_for(token)
        shard.lpush(f"kw:{token}:recent", post.id)
        shard.ltrim(f"kw:{token}:recent", 0, 9999)   # cap is enforced on every insert
        shard.zadd(f"kw:{token}:top", {post.id: 0})

def on_like(like):
    # exact count: one cheap counter write, no index fan-out
    count = counters.incr(f"post:{like.post_id}:likes")

    if count & (count - 1) == 0:              # only powers of two propagate: 1, 2, 4, 8...
        for token in tokenize(posts.fetch(like.post_id).content):
            redis_for(token).zadd(f"kw:{token}:top", {like.post_id: count})
            redis_for(token).zremrangebyrank(f"kw:{token}:top", 0, -10001)

The write path after scaling. The event writer only appends, so bursts land in the log instead of on the ingestion fleet, and a partitioned consumer group tokenizes posts and writes postings to keyword-sharded Redis at its own pace inside the one-minute freshness budget.

Keeping petabytes out of memory

The caps come first because they are load-bearing twice over. Nobody pages to result ten thousand, so each keyword's two orderings are trimmed to the top ten thousand entries on insert, an LTRIM on the recency list and a rank-range removal on the sorted set. Beyond shrinking storage by orders of magnitude, the caps keep the structures inside hard limits, since a Redis collection tops out around four billion members and a stop-word-adjacent keyword collecting a share of a billion daily posts would cross that within weeks. Uncapped, the terabyte-scale estimate quietly returns to petabytes and the in-memory design stops existing.

The second lever is that keyword popularity is brutally skewed. Most of the 500 million keywords are searched rarely or never, and the requirements explicitly allow slow answers for old and unpopular content. A batch job over search analytics finds keywords with no queries in the past month, serializes their postings to blobs in S3, and deletes them from Redis. The read path tries Redis first, and on a miss fetches the blob, pays tens of extra milliseconds, and can promote the keyword back to the hot tier if traffic returns. This is the hot and cold split the requirements were foreshadowing, and it converts memory cost into object-storage cost across the long tail.

The interaction between cold storage and likes is the detail that separates a complete answer from a hand-wave. A like on an old post whose keywords have gone cold would mean editing a blob, and blobs are slow and awkward to edit in place. The power-of-two rule mostly dissolves the problem, because an old post crosses a fresh threshold rarely, and when it does the event is rare enough that rewriting the affected blob, or promoting the keyword back to Redis, is affordable. Facebook's production systems answer the same pressure with money instead. Unicorn holds its entire social-graph index in RAM across thousands of machines to search trillions of edges at latencies in the hundreds of milliseconds. The tiered version is what the relaxed requirement buys when the budget is not Facebook's.

The full design

End to end, a post takes this route. The Post Service emits an event, the event writer appends it to Kafka, an ingestion worker tokenizes it into unigrams and bigrams and pushes its id into each keyword's recency list and likes set on the owning shard, trimming as it goes, and well inside the one-minute budget the post is searchable. A like increments one exact counter and, on a power-of-two crossing, refreshes the post's score in each of its keywords' sorted sets. A search comes through the CDN and the gateway, hits the result cache, and on a miss reads one or two keyword structures from one or two shards, merges, hydrates posts and exact like counts, caches the assembled page for under a minute, and returns.

The honest alternative to this whole layout is document sharding. Partition by postId instead of by keyword, send every query to all shards, let each shard match and rank its slice locally, and merge top results at a coordinator. That is the architecture of Unicorn, of Earlybird, and of the general-purpose search service design on this site, and it wins when queries are complex, when posting lists must never be split by cap boundaries, and when a document update should land on exactly one shard. Term sharding wins here because the query language was deliberately cut down to one or two keywords with precomputed sorts, so a read touches one shard instead of all of them. Widen the query language and the balance tips back toward document sharding, which is a trade worth naming explicitly rather than leaving implicit.

The assembled system. Writes flow through the log into keyword-sharded Redis with two orderings per keyword, cold keywords age out to blob storage via a batch job, and reads resolve from the CDN or result cache before ever touching the index, with exact like counts hydrated at render time.

Questions and answers

The core ideas as questions with the answers given outright. Each wrong multiple-choice option is marked with why it is wrong, and the ordering ones show the correct sequence.

References

1. Curtiss et al., Unicorn: A System for Searching the Social Graph (VLDB 2013), How Facebook actually serves social search, a document-sharded index held entirely in memory across thousands of commodity servers, searching trillions of edges at latencies in the hundreds of milliseconds.
2. Busch et al., Earlybird: Real-Time Search at Twitter (ICDE 2012), The production benchmark for real-time indexing, tweets searchable within about ten seconds via a single writer thread per in-memory segment, serving over two billion queries a day at a 50 millisecond average.
3. Manning, Raghavan and Schütze, Introduction to Information Retrieval, building an inverted index, The textbook construction of postings lists and Boolean queries, the foundation this design rebuilds by hand once the prebuilt engines are banned.
4. Redis sorted sets documentation, The data structure behind the by-likes ordering, logarithmic inserts with range reads by rank, and the operations used to enforce the posting-list caps.
5. Apache Kafka design documentation, The log as a durable buffer between producers and partitioned consumer groups, the mechanism that lets ingestion absorb bursts inside the one-minute freshness budget.