Design Distributed Search
Inverted index, sharding, replication, ranking, and query fan-out at billions of documents.
Interview tip Separate indexing pipeline (async) from query path (sync). Mention inverted index, BM25 ranking, shard routing, and replica load balancing for hot queries.
① Functional requirements
- Index documents with JSON fields; support full-text search on title/body
- Filter by metadata (date range, category, geo bounding box)
- Return ranked results with snippets/highlights
- Faceted counts (e.g. brand, price bucket) alongside hits
- Near-real-time indexing — documents searchable within seconds
- Delete/update documents by ID
Out of scope (state in interview)
- ML re-ranking models
- Multi-language stemming tuning
- Federated cross-cluster search
② Non-functional requirements
- Query p99 < 200ms for 95% of queries
- Horizontally scale to 10B+ documents
- 99.9% availability — tolerate shard replica loss
- 5K QPS aggregate with burst to 20K
- Index throughput 100K docs/sec sustained
③ Back-of-the-envelope scale
Assumptions
- 10B docs × 2KB avg inverted index overhead ≈ 20TB index data
- 5K QPS × 50ms shard latency → ~250 concurrent shard queries
- 100 shards × 100M docs each; 2 replicas → 300 shard copies
- Ingest 100K docs/sec → Kafka buffer + bulk index every 5s
- Hot query fan-out: coordinator hits all shards → merge top-K
Use routing key (user_id or tenant) when queries are scoped — reduces fan-out from 100 shards to 1–3. Cache top queries at coordinator for 30s.
④ High-level architecture
Distributed Search Cluster
Clients / API Gateway
Query Coordinator (scatter-gather)
Shard 1 Primary + Replicas
Shard 2 Primary + Replicas
Shard N…
Ingest Pipeline (Kafka → bulk indexer)
Object store / segment files
Query→Coordinator→Shard fan-out→Merge + rank
Each shard holds inverted index segments (postings lists). Coordinator parses query → builds shard requests → gathers top-K per shard → global merge. Writes go to primary; replicas catch up asynchronously.
⑤ Data flow & execution path
Query execution path
① Parse query→② Route shards→③ Parallel shard search→④ Merge BM25 scores→⑤ Return page
Index path: Kafka → bulk buffer → segment build → refresh reader
Query path: scatter to primaries/replicas → top-K heap per shard
Slow shard: coordinator uses partial results + timeout cutoff
Rebalance: relocate segments with dual-write window
Walk both write and read paths. Emphasize that indexing is async and search reads immutable segments for predictable latency.
⑥ API & interfaces
| Endpoint / flow | Purpose | Notes |
|---|---|---|
| POST /index/{id} | Upsert document | Async ack after Kafka enqueue |
| GET /search?q=… | Full-text search | Coordinator scatter-gather |
| POST /search | Complex query DSL | Filters + facets in one request |
| DELETE /index/{id} | Remove document | Tombstone in segment |
| GET /health | Cluster status | Shard allocation + lag metrics |
⑦ Data model & storage
Document:
id, fields (text, keyword, numeric, geo). Inverted index: term → postings list (doc_id, positions, norms). Segment: immutable Lucene-style file set per shard.| Store | What | Why |
|---|---|---|
| Shard local disk | Inverted index segments | Fast random access; merge compactions |
| Kafka | Ingest log | Durability before index |
| ZooKeeper / etcd | Cluster metadata | Shard map, leader election |
| S3 (optional) | Cold segment snapshots | Backup and rehydrate |
⑧ Deep dive — core components
Inverted index and BM25 ranking
Tokenizer → terms → postings. BM25 balances term frequency and document length. Coordinator merges shard-level scores; optional second-stage reranker on top 100.
Shard routing and hot keys
Default hash(doc_id) for even spread. Scoped queries use routing key to limit fan-out. Hot shard: add replica read preference + query cache; split shard if sustained hot.
⑨ Trade-offs & alternatives
| Decision | Option A | Option B | Pick when |
|---|---|---|---|
| Shard count | More shards | Fewer shards | More shards = more fan-out overhead but smaller rebalance blast |
| Consistency | Primary read | Replica read | Replica lowers load; primary for freshest writes |
| Index refresh | 1s NRT | 30s batch | Faster refresh = more CPU on segment merges |
| Coordinator cache | Cache query results | Always fan-out | Cache helps trending queries; stale risk |
⑩ 45-minute interview script
- 0–5 min: Requirements — search, filter, facets, NRT indexing
- 5–12 min: Scale math — docs, QPS, index size
- 12–20 min: Architecture — coordinator, shards, ingest pipeline
- 20–28 min: Query fan-out and merge ranking
- 28–35 min: Indexing pipeline and segment merges
- 35–42 min: Failure modes — slow shard, node loss, rebalance
⑪ Likely follow-up questions
| Question | Short answer |
|---|---|
| How handle typo tolerance? | Fuzzy query expansion, phonetic tokens, or dedicated spell-check index on query side |
| Reindex mapping change on 10B docs? | Dual-write to new index version; alias swap when ready; background reindex from source |
| Cross-field search vs per-field boosts? | Multi-match query with per-field weights in DSL; tune boosts via offline eval |
⑫ Revision checklist
- Inverted index + BM25
- Scatter-gather coordinator
- Shard primary + replicas
- Kafka ingest buffer
- Routing key for scoped queries
- Segment merges and refresh
- Query timeout + partial results
- Rebalance without downtime