Design a Search Engine

A web search engine takes a few words and returns the most relevant documents out of billions, in well under a second. The web crawler page already built the part that gathers pages; this page builds what happens next — turning that raw corpus into a structure you can query at the speed of thought. The single data structure at the heart of it, the inverted index, is also the engine inside Elasticsearch, Lucene, and your database’s full-text search. We’ll follow the framework.

1. Requirements

Functional

• Accept a free-text query; return a ranked list of relevant documents.
• Support multi-word queries, phrases, and basic operators.
• Freshness — newly crawled/updated pages become findable quickly.

Non-functional

• Low query latency — tens of milliseconds at the index, a fraction of a second end to end.
• Relevance — good precision and recall; the best results on page one.
• Scale — billions of documents, high query throughput.

Search is read-optimized indexing

The corpus changes slowly relative to how often it’s queried, so you do expensive work once at index time to make every query cheap. That asymmetry — heavy write/index path, light read/query path — is the inverse of a write-heavy system and dictates the whole design.

2. Back-of-envelope estimation

CORPUS
  documents:     ~10B web pages (illustrative)
  avg unique terms/doc: ~1,000
  postings:      term→doc entries number in the trillions → far too big for one machine

QUERY PATH
  query QPS:     say ~100,000 queries/sec at peak (illustrative)
  latency budget: ~200 ms end-to-end → ~tens of ms at the index tier
  fan-out:       each query must consult EVERY index shard (scatter-gather)

Two facts fall out. First, the index is far too large for one machine, so it must be sharded across hundreds/thousands of servers. Second, a query has to ask all of them (“does anyone have a good match for these terms?”) and merge the answers — a scatter-gather whose latency is governed by the slowest shard, dragging in the tail-latency problem.

3. API sketch

GET /search?q=distributed+systems&start=0&num=10
   → { results: [ { url, title, snippet, score }, ... ], total_estimate, took_ms }

internal (indexing side):
   index(doc_id, url, tokens[])          // add/update a document in the index
   delete(doc_id)                        // remove (or tombstone) a document

4. The data model: forward vs inverted index

FORWARD index (doc → terms)            INVERTED index (term → docs)   ← what search needs
  doc_1 : {the, quick, brown, fox}       "fox"   → [doc_1, doc_7, doc_42, ...]
  doc_2 : {the, lazy, dog}               "lazy"  → [doc_2, doc_19, ...]
                                         "quick" → [doc_1, doc_88, ...]

A forward index answers “what words are in this doc?” — useless for search. The inverted index answers “which docs contain this word?” — exactly the query. Each term maps to a postings list of the documents containing it, typically with extra payload per posting:

"fox" → [ (doc_1, tf=3, positions=[5,40,77]), (doc_7, tf=1, positions=[12]), ... ]
         doc id   term frequency   where it appears (for phrase queries)

A multi-word query intersects/unions postings lists; positions enable phrase matching (“brown fox” as adjacent words). Postings lists are sorted by doc id and compressed with gap (delta) encoding — storing differences between consecutive ids, which are small — plus variable-length integers, shrinking trillions of entries dramatically. This is an indexing problem at web scale.

5. Ranking: TF-IDF and BM25

Matching is binary (does the doc contain the term?); ranking is the art. The classic intuition is TF-IDF:

• Term Frequency (TF): a term appearing often in a document signals that document is about it.
• Inverse Document Frequency (IDF): a term appearing in few documents is more discriminating — “the” is in every doc and tells you nothing; “thermodynamics” is rare and tells you a lot.

Multiply them: a document scores high for a query term it uses frequently and that is rare across the corpus. But raw TF-IDF has flaws: term frequency grows without bound (a page repeating “shoes” 500 times shouldn’t win), and it ignores document length. BM25 (“Best Matching 25”) fixes both and is the de-facto baseline in modern search (it’s Lucene/Elasticsearch’s default scorer).

Under the hood — what BM25 adds

score(D, Q) = Σ over query terms qi:
                 IDF(qi) · ( f(qi,D) · (k1 + 1) )
                 ───────────────────────────────────────────────
                 f(qi,D) + k1 · ( 1 − b + b · |D| / avgdl )

  f(qi,D) = how many times term qi appears in doc D
  |D|     = length of D;  avgdl = average doc length in the corpus
  k1 (≈1.2–2.0): term-frequency saturation — extra repeats matter less and less
  b  (≈0.75):     length normalization — long docs don't win just by being long

The two knobs are the whole point. k1 makes term frequency saturate — going from 1→2 occurrences helps a lot, 50→51 barely moves the score — so keyword stuffing stops paying off. b normalizes for length, so a focused short page can outrank a sprawling one that mentions the term in passing. Real engines layer more on top — link-based authority (PageRank-style), freshness, personalization, and machine-learned ranking over hundreds of features — but BM25 remains the workhorse first pass that selects the candidate set those rerankers refine.

6. Sharding the index and the query path

You can’t hold trillions of postings on one box. The standard layout is document partitioning: each shard holds the complete inverted index for a subset of documents.

                                ┌──────── query: "distributed systems" ────────┐
                                ▼              ▼               ▼                ▼
   query ─► aggregator ──► shard 1 ──► shard 2 ──► shard 3 ──► ... ──► shard N   (SCATTER)
                │           each returns its local top-k by BM25
                ▼
            merge top-k from every shard → global top-k → fetch titles/snippets   (GATHER)

Each shard scores its own documents and returns its local top-k; the aggregator merges them into the global top-k. Buys: every shard works in parallel over a slice of the corpus, and adding documents means adding shards — near-linear scale. Costs: every query fans out to every shard, so the response waits on the slowest one (tail latency), and you replicate each shard for throughput and availability. See partitioning and sharding.

The alternative: term partitioning

You could instead partition by term — shard A owns postings for terms a–m, shard B owns n–z. Then a query only touches the shards holding its terms (less fan-out). But popular terms create hot shards, multi-term queries must ship long postings lists between shards to intersect them, and load is wildly uneven. Document partitioning’s even load and parallel scoring win in practice — which is why web-scale engines use it despite the full fan-out.

By the numbers — the latency budget of a scatter-gather

Say the end-to-end budget is 200 ms and the index spans 1,000 shards queried in parallel:

per-shard work:    decode postings + score + local top-k ≈ a few ms (index in RAM/SSD)
fan-out is parallel, so total ≈ slowest shard, NOT sum of shards
the killer is the TAIL: with 1,000 shards, the query waits on the 99.9th-percentile shard
  P(all 1,000 fast) = (0.999)^1000 ≈ 0.37  ⇒ ~63% of queries hit at least one slow shard

That math is why search engines obsess over tail latency: the more shards you fan out to, the more likely some shard is slow, so a 99th-percentile shard becomes the median query experience. Defenses: replicate shards and send the query to two replicas (take the first to answer), set tight per-shard deadlines and return partial results, and cache hot queries. Sharding buys parallel scale; it costs you a tail-latency problem that grows with shard count.

Freshness — fast index vs big index

A from-scratch index rebuild is too slow for “news from five minutes ago.” The standard fix is a tiered index: a small, frequently-rebuilt (or incrementally-updated) fresh tier holds recent documents, while a massive base tier is rebuilt rarely; queries hit both and merge. Updates to an inverted index are awkward (you don’t edit postings in place — you write new segments and merge), so freshness is fundamentally a batch-size trade: smaller, more frequent index segments mean fresher results but more merge overhead.

It actually happened — Google’s “Caffeine” made the index incremental (2010)

Until 2010, Google’s index was rebuilt in layered batches: the web was crawled, processed, and the index regenerated on a periodic cycle, so a page could wait a long time to appear. In June 2010 Google rolled out a new indexing system, Caffeine, that abandoned the batch rebuild for continuous, incremental indexing — analyzing and indexing pages in small increments as they were crawled, rather than waiting for a global rebuild. Google reported it provided ~50% fresher search results and could index far more of the web. It’s the freshness-vs-batch trade of this section made real: moving from big infrequent rebuilds to small continuous updates bought dramatically fresher results, at the cost of a much more complex, always-running indexing pipeline.

Key trade-offs

• Inverted vs forward index: the inverted index buys “which docs contain this term?” in one lookup; it costs an expensive index-time build and awkward in-place updates.
• BM25 vs raw TF-IDF: BM25 buys term-frequency saturation and length normalization (resisting keyword stuffing); it costs two tuning parameters (k1, b) to set.
• Document vs term partitioning: document partitioning buys even load and parallel scoring at the cost of full per-query fan-out; term partitioning cuts fan-out but creates hot shards and cross-shard intersections.
• Fresh tier vs big batch: small, frequent index segments buy freshness; they cost merge overhead and pipeline complexity.

Check your understanding

1. Why is an inverted index, not a forward index, the right structure for search? What does a postings list store beyond doc ids, and why?
2. Explain TF-IDF intuitively, then name the two problems BM25’s k1 and b parameters solve.
3. What is document partitioning, and why does it lead to a scatter-gather query? What does it buy and cost versus term partitioning?
4. Why does fanning out a query to 1,000 shards make tail latency the dominant concern, and name two defenses.
5. What problem did Google’s Caffeine address, and what trade-off did moving to incremental indexing represent?

Show answers

1. A forward index maps doc→terms (“what words are in this doc?”), which doesn’t answer a search; the inverted index maps term→docs (“which docs contain this word?”), exactly the query. A postings list stores, per matching doc, the term frequency (for ranking) and term positions (for phrase queries like “brown fox” as adjacent words) — and is compressed with gap/delta encoding to shrink trillions of entries.
2. TF-IDF: a term that appears often in a document (TF) and is rare across the corpus (IDF) is a strong relevance signal — “thermodynamics” discriminates, “the” doesn’t. BM25 adds two fixes: k1 saturates term frequency so repeating a word 500 times stops helping (defeats keyword stuffing), and b normalizes for document length so long documents don’t rank highly just for being long.
3. Document partitioning gives each shard the complete inverted index for a subset of documents, so a query must ask every shard (scatter), each returns its local top-k, and the aggregator merges (gather). It buys even load and fully parallel scoring with near-linear scale; it costs full per-query fan-out (waiting on the slowest shard). Term partitioning cuts fan-out but creates hot shards for popular terms and forces cross-shard postings intersections with uneven load.
4. With 1,000 shards queried in parallel, the query finishes only when the slowest shard responds, so even a rare per-shard slowdown almost always hits some shard — e.g. with 99.9%-fast shards, 0.999^1000 ≈ 0.37, so ~63% of queries touch a slow shard. Defenses: replicate shards and query two replicas, taking the first answer, and set tight per-shard deadlines with partial results (plus caching hot queries).
5. Until 2010 Google rebuilt its index in periodic layered batches, so fresh pages waited to appear. Caffeine (June 2010) switched to continuous incremental indexing, reporting ~50% fresher results. The trade-off: small continuous updates buy much fresher results but cost a far more complex, always-running indexing pipeline (versus simpler big infrequent rebuilds).