Design Search Engine

Three independent pipelines: crawl (continuous), index build (periodic batch), query serving (real-time). They communicate via large shared data stores — the crawled page corpus and the inverted index.

An inverted index maps each term to the list of documents containing it — the posting list. Query "climate change" becomes: fetch posting list for "climate", fetch for "change", intersect, score, return top-K. The whole design is shaped around making this fast at 100K QPS over 100B pages.

Sharding choice. Two strategies:

• Document-sharded (Google's choice): each shard holds a subset of docs + the posting lists for those docs. A query scatter-gathers to every shard; each returns local top-K; aggregator merges to global top-K. Scales well to many QPS; wastes some work because every query hits every shard.
• Term-sharded: each shard owns a subset of terms' full posting lists. Query routes only to the shards holding the queried terms. Very efficient per query — but hot terms ("the", "COVID") create pathological load; rebalancing is painful. Used for specialty verticals only.

Query pipeline, in order of execution:

1. Parse + normalize. Lowercase, stemming, stop-word handling, query expansion (synonyms, abbreviations). Spell-correction against a dictionary + query-log bigram model.
2. Scatter to all index shards. Aggregator sends query to ~1000 shards in parallel. Each shard returns its local top-100 with scores.
3. Shard-local scoring (first-pass ranker). Classic BM25 or similar. Cheap; runs over millions of candidate docs per shard.
4. Aggregator merges to top-1000. Heap-merge, take global top-1000 by BM25.
5. Reranker (second-pass). A heavy ML model (e.g., BERT-based cross-encoder) scores the top-1000 with query+doc pairs. 100× more expensive per doc but only on a small set.
6. Snippet generation. Extract sentence(s) best matching the query from each of the top-10 docs. This is lightweight but user-visible; lives on the critical path.

sequenceDiagram
    participant U as User
    participant AG as Aggregator
    participant S1 as Shard 1..N
    participant RR as Reranker
    participant RS as Response

    U->>AG: query "climate change 2026"
    Note over AG: parse + expand~5 ms
    AG->>S1: scatter to ~1000 shards
    S1-->>AG: shard top-100 + BM25~50 ms (parallel)
    Note over AG: merge to global top-1000~10 ms
    AG->>RR: top-1000 with query
    RR-->>AG: top-10 ML-reranked~80 ms (BERT batched)
    AG->>RS: snippet gen + render~20 ms
    RS-->>U: resultstotal ~165 ms p50
          

Caching. A massive query cache sits in front of the whole pipeline. The long tail is huge, but the head is tiny — a surprising fraction of queries are repeats within minutes. A simple LRU on normalized query strings serves ~30–40% of traffic without touching the index at all. Result cache TTL is short (minutes) to preserve freshness.

Ranking signals. The modern ranker combines:

• Lexical (BM25). Term frequency × inverse document frequency. Still the baseline.
• Link authority (PageRank variants). Computed offline weekly over the web graph.
• Freshness. News-y queries favor recent docs; evergreen queries don't.
• User signals. Click-through rate, dwell time, bounce rate per (query, doc) pair — trained into the reranker.
• Semantic relevance (neural). Dense vector similarity between query and doc embeddings. Retrieves semantically-matching docs that don't share exact terms. Google's "neural matching" + BERT for reranking.

• Scatter to all shards vs smart routing. Scatter wastes work but is resilient and uniform. Routing only to "relevant" shards saves work but requires shard-term statistics everywhere. Google uses scatter — CPU is cheap relative to the ops complexity of routing.
• Two-stage ranking. BM25 is cheap but dumb; BERT is smart but 100× slower. Two-stage ranking (cheap over millions → expensive over thousands) is the standard modern answer. Single-stage BERT over all docs would be 1000× too slow.
• Batch index rebuild vs real-time updates. Full index is rebuilt nightly via MapReduce. Fresh content (news, social) goes into a small "live index" served in parallel and merged at query time. Two-index architecture hits both scale and freshness.
• Inverted index in RAM vs on disk. Hot posting lists in RAM (top N terms cover most queries); cold on SSD. Disk-backed portions use skip pointers + delta-compressed posting lists to stream fast.
• Personalization. Pure relevance is simpler; personalization improves user satisfaction but creates filter-bubble complaints and makes ranking harder to reason about. Google personalizes lightly (geo, recent queries, signed-in history).

1. Name the three pipelines. Crawl, index build, query serving. Many candidates conflate them or only discuss query serving. Show you know crawl is a separate beast.
2. Document-sharding is the default answer. If you say "term-sharded," be ready to defend the hot-term problem. Google uses document-sharded; most interviewers expect that.
3. Two-stage ranking. Explicitly call out: cheap first-pass over all candidates → expensive neural reranker over a small set. This is the modern pattern and shows you're current.
4. Query cache answers "how do you handle 100K QPS?" A big fraction of queries are repeats; a simple LRU slashes load by 30%+. Mention it early.
5. Fresh index + main index. If asked "how do you handle breaking news?" — two-index architecture is the answer, not "rebuild more often."