Primary concepts and the hard part
Requirements
Documents: 1B Queries: 100,000/sec search Typeahead: 500,000/sec (fires per keystroke — 5x search volume!) Index size: 1B docs × ~1KB indexed → ~1 TB → ~20 shards of 50 GB Query cache hit rate: 60-80% (head queries are extremely repetitive)
API / Model
High-level architecture
The design has an indexing path that keeps the inverted index a few seconds behind the source of truth, and a query path with two services: the Search Service for submitted queries and the Suggest Service for keystrokes. Only search touches the index shards.
- When the user submits a query, the Search Service checks the Redis query cache under a normalized key, and 60-80% of queries are answered there.
- On a miss, the Query parser runs the same analysis chain used at index time, plus spell correction.
- The parser scatters the query to every shard. The index is document-partitioned, so each shard holds a complete index for its share of documents.
- Each shard scores its matches with BM25 and returns its top 20.
- The gather step merges and re-ranks those lists into the global top 20, using hedged requests and a timeout so one slow shard can only cost partial results.
- Hydrate adds titles, snippets and facets, caches the result, and returns it to the user.
Typeahead runs beside this. Every keystroke, debounced by 50ms, goes to the Suggest Service, which walks an in-memory trie of top-K completions per prefix in about 5ms; the trie is rebuilt offline from query logs. Documents reach the shards through the indexing path: changes in the source of truth flow through CDC into Kafka document.changed, the analysis pipeline tokenizes, lowercases, drops stopwords, stems and enriches them, and each document goes to the shard chosen by hash(doc_id).
Same engine over a 100x larger corpus. Query volume here is already web-search sized, so this tab grows the index 100x and queries about 3x. Dashed outlines mark what's new or reshaped compared with today's design.
| Today | At 100x corpus | |
|---|---|---|
| Documents | 1B | 100B |
| Index size | ~1 TB | ~100 TB |
| Shards at ~50 GB each | ~20 | ~2,000 |
| Search queries | 100k/sec | ~300k/sec |
| Typeahead | 500k/sec | ~1.5M/sec |
What changes, and the number that forces it
- Scattering to every shard stops working. With ~2,000 shards, some shard is always slow, so p99 becomes roughly "the worst shard of the moment". Hedged requests contained tail amplification at 20 shards; at 2,000 nothing below works unless a query touches far fewer shards.
- A hot tier answers most queries. Quality and popularity are power-law, so a small tier holding the best ~2% of documents (~40 shards) contains the top results for most queries. The router always asks the hot tier and only fans out to the full tier when the hot tier returns too few strong hits, which in practice means rare, long-tail queries. Most queries now touch dozens of shards, not thousands.
- The router prunes shards. Full-tier shards are partitioned by values queries commonly filter on (language, tenant, category), hashed by
doc_idwithin each partition. A query carrying those filters goes only to the matching shards. Still document-partitioned, but by a key the router can use. - Shards stop early. Posting lists are sorted by a static quality score, so a shard can stop once it has enough strong candidates instead of scoring every match. The gather step re-ranks the top ~500 with the expensive signals. The cost is that a relevant document with a low static score can be cut before it's ever scored.
- Indexing splits into a base and a delta. Rebuilding 100B documents through the change stream one update at a time would take weeks. A batch job rebuilds the base index offline from the source of truth and ships finished segments to shards, while recent changes go into a small real-time delta index that every query also reads. Freshness stays in seconds, and a mapping change becomes a scheduled rebuild rather than an emergency.
- Typeahead moves toward the edge. At ~1.5M keystrokes/sec, the head prefixes for each locale are served from edge caches, and tries are sharded by locale and leading prefix so every Suggest node holds a bounded trie.
What stays the same
The index is derived and never the source of truth. Index-time and query-time analysis stay identical, ranking is still BM25 layered with business signals, the query cache still normalizes keys, and partial results still beat a spinner. Sharding stays document-partitioned rather than term-partitioned.
Trade-offs and deep dives
WHERE body LIKE '%distributed%' cannot use a B-tree index (leading wildcard) and scans every row. The inverted index flips the mapping so lookup is O(1) on the term plus a posting-list intersection. For a multi-word query, intersect the posting lists, starting with the shortest one to minimize work.
If you stem at index time but not at query time, a search for "running" won't match the indexed token "run". This is the single most common real-world search bug and a good thing to mention.
TF-IDF says a term matters if it's frequent in this document but rare in the corpus. BM25 adds saturation (the 50th occurrence of a word adds less than the 2nd) and document-length normalization (so long documents don't win by accident). Then layer business signals — recency, popularity, quality — as a weighted combination or a learned model.
- Document-partitioned (standard): each shard holds a complete index for its subset of documents. Every query hits every shard (scatter-gather), but each shard's work is small and the system is easy to grow.
- Term-partitioned: each shard holds all postings for a subset of terms. A single-term query hits one shard, but multi-term queries require shipping huge posting lists across the network, and popular terms create brutal hotspots. Almost always the wrong choice — worth knowing so you can reject it with a reason.
With 20 shards, your p99 is roughly the p99 of the maximum of 20 samples, which is far worse than any single shard's p99 (Module 1's tail amplification). Mitigations to name:
- Hedged requests: after waiting the p95 latency, send a duplicate request to another replica and take whichever answers first.
- Timeout with partial results: return what you have from 19 shards rather than waiting for the 20th. Search users tolerate slightly worse results far better than a spinner.
- Replica load balancing away from slow nodes.
Engines buffer writes in memory and periodically flush to a new immutable segment (Elasticsearch refreshes ~once per second by default). Segments are later merged in the background. So there is a ~1s window where a written document isn't searchable. Say this out loud; claiming instant searchability is a credibility hit. If a user must see their own new item immediately, special-case it from the source of truth rather than tightening the refresh interval globally.
Requirements differ on every axis: 5x the query volume, 10x tighter latency, and only prefixes matter. So:
- Use an in-memory trie with the top-K completions precomputed and stored at each node, so a lookup is a walk down the prefix with no ranking work at query time.
- Rebuild it offline from query logs (hourly or daily) — suggestions don't need to be fresh to the second.
- Debounce on the client (~50ms) and cancel in-flight requests when the user keeps typing. This alone cuts backend load by more than half.
- Cache aggressively at the edge; prefix distribution is extremely head-heavy.
Edit-distance matching is expensive over 1B docs. Practical approaches: precomputed common misspelling → correction mappings from query logs, n-gram indexes for fuzzy matching, and "did you mean" suggestions rather than silently expanding the query.
Normalize the query (lowercase, sort filters, strip whitespace) before using it as a cache key, or you'll cache the same query a dozen ways. Head queries repeat enormously, so hit rates of 60-80% are realistic and this is the cheapest latency win available.
Feed it from CDC or an event stream, never make it the write path's dependency, and be able to rebuild it from scratch by replaying. If the index is corrupted or the mapping changes, you reindex — which is only possible because the source of truth is elsewhere.
Possible follow-up questions
search_after semantics instead, or cap depth — most search products cap at ~1,000 results and that's an acceptable product decision.