Search Engine / Typeahead
Design a web-scale search engine with an inverted index, distributed crawling and indexing, relevance ranking, and low-latency autocomplete backed by tries.
By Ratish Jain · Updated
Problem
A search engine must turn billions of documents into a structure that answers full-text queries in tens of milliseconds, while a typeahead endpoint suggests completions on every keystroke. The core challenge is building and serving an inverted index — a map from each term to the list of documents containing it — at a scale where no single machine holds the full corpus, then ranking matches by relevance so the best results appear first.
We split the system into an offline pipeline (crawl → parse → index) and an online serving path (query → retrieve → rank). Both must scale horizontally and tolerate node failure without dropping to zero results.
Functional Requirements
- Full-text search over a large document corpus returning ranked results.
- Autocomplete/typeahead suggestions as the user types a prefix.
- Crawl and (re)index new and updated documents continuously.
- Support boolean and phrase queries with relevance ranking.
- Pagination of results and basic query analytics.
Non-Functional Requirements
- Query latency p99 under ~200ms; typeahead under ~50ms.
- High availability — partial index outages degrade, not fail.
- Freshness: new docs searchable within minutes to hours.
- Horizontal scalability of both index size and query throughput.
- Eventual consistency between crawl pipeline and served index.
Capacity Estimation
- Corpus size
- 10B documents, ~10 KB each ≈ 100 TB raw
- Inverted index
- ~30% of raw ≈ 30 TB, sharded 100+ ways
- Query QPS
- 100K queries/sec peak
- Typeahead QPS
- ~1M keystroke lookups/sec
- Crawl rate
- ~50K pages/sec sustained
- Index shards
- 128 shards × 3 replicas ≈ 384 servers
APIs
- GET /search
- search(q, page, size) -> {results[], total}
- GET /suggest
- suggest(prefix, limit) -> {completions[]}
- POST /index
- index(docId, url, content) -> {status}
- POST /crawl
- enqueue(seedUrls[]) -> {jobId}
Components
- Crawler: distributed fetchers with a URL frontier, politeness/rate limits, and a bloom filter to skip already-seen URLs.
- Indexer: parses documents, tokenizes, builds per-shard inverted index segments, computes term frequencies.
- Index servers: hold shards of the inverted index; each answers postings for its slice of the corpus.
- Query API / coordinator: parses queries, fans out to shards, merges and paginates.
- Ranker: scores documents (TF-IDF/BM25 + signals like PageRank, freshness) and returns top-K.
- Typeahead service: in-memory trie or FST of popular queries/terms, cached per prefix.
- Result cache: Redis layer for hot query results.
Request Flow
- 1Client sends a query to the Query API, which parses and normalizes terms.
- 2API checks the result cache; on hit it returns immediately.
- 3On miss, the coordinator fans the query out to all relevant index shards in parallel.
- 4Each shard returns matching postings with local scores for its documents.
- 5The ranker merges shard results, applies global signals, and selects the top-K.
- 6Results are cached and returned; typeahead follows a separate trie-lookup path.
Flow Diagram
Data / Storage Design
The inverted index maps term -> postings list, where each posting holds (docId, term-frequency, positions). Positions enable phrase queries. The index is sharded by document (document partitioning): each shard indexes a subset of docs and can answer any term, so every query fans out to all shards. The alternative — term partitioning — concentrates hot terms and complicates multi-term queries, so document sharding is the common choice.
Document metadata (URL, title, static rank) lives in a separate store keyed by docId. Index segments are immutable and periodically merged (LSM-style) so writes append new segments rather than mutating in place. The typeahead trie is a compact structure of top queries, rebuilt offline and loaded into memory.
Data Model
Scaling Strategy
Read scaling comes from replicating each shard — replicas serve reads round-robin and provide failover. Corpus growth is handled by adding shards; consistent hashing on docId keeps rebalancing cheap when the shard count changes.
The crawl/index pipeline scales independently as a batch/stream system. Hot query results are absorbed by the cache, cutting fanout cost. Typeahead is served entirely from memory and can be replicated widely since the trie is small relative to the full index.
Bottlenecks & Failure Scenarios
- Fanout tail latency — one slow shard delays the whole query; use hedged requests and timeouts.
- Hot terms with huge postings lists (e.g., stopwords) blow up scoring cost.
- Crawler traps and duplicate URLs waste capacity without bloom-filter dedup.
- Index staleness if the merge/publish pipeline falls behind crawl volume.
- Cache stampede when a popular query expires simultaneously across nodes.
Design Tradeoffs
- Document sharding makes every query embarrassingly parallel.
- Immutable segments simplify replication and caching.
- Separate offline pipeline keeps serving latency stable under indexing load.
- Every query hits all shards, so tail latency dominates.
- Full re-ranking is expensive; global signals need precomputation.
- Freshness lags because indexing is batch-oriented.
Common Interview Questions
Document partitioning spreads docs across shards so any query fans out to all shards but each is balanced; term partitioning routes a term to one shard, avoiding fanout but creating hotspots and painful multi-term intersections. Most engines choose document partitioning.
Suggestions are served from an in-memory trie/FST of popular prefixes, precomputed offline and cached. Each keystroke is a cheap prefix walk returning top completions by popularity, avoiding the full index path.
A base relevance score like BM25/TF-IDF is combined with query-independent signals (static rank/PageRank, freshness, click data). Shards compute local scores; the coordinator merges and applies global signals to pick top-K.
- →Inverted index maps terms to postings lists; the heart of retrieval.
- →Shard by document so queries fan out and parallelize across shards.
- →Ranking = base relevance (BM25) + global signals (rank, freshness).
- →Typeahead uses an in-memory trie for sub-50ms prefix lookups.
- →Offline crawl/index pipeline is decoupled from online serving.
Related
Everything on Archprimer is connected — follow the graph.