Course contentsShow
← System Design
Lesson 1769 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Horizontal Scaling of Search Infrastructure

Partitioning the index across multiple machines using document sharding and query routing strategies.

Horizontal Scaling of Search Infrastructure

What you'll learn: How to partition a search index across multiple machines to handle billions of documents and thousands of queries per second.

The Challenge of Growing Beyond One Machine

As your document corpus grows from millions to billions of entries, a single machine's memory, CPU, and I/O eventually hit their limits. Horizontal scaling distributes your inverted index across multiple servers, allowing you to scale both storage capacity and query throughput.

Document Sharding Strategies

Document sharding splits your index by dividing documents across machines:

  • Hash-based sharding: Apply a hash function to document_id (e.g., hash(doc_id) % num_shards). Documents distribute evenly, but queries must fan out to all shards since any shard might contain relevant documents.

  • Range-based sharding: Partition documents by ranges (e.g., shard 1 handles docs 1-1M, shard 2 handles 1M-2M). Easier to rebalance incrementally, but hot spots can emerge if document IDs correlate with popularity.

Think of it like a library system: instead of one giant library holding all books, you build ten regional libraries. Every search query must check all ten locations because a relevant book could be anywhere.

Query Routing and Aggregation

A query router receives search requests and:

  1. Broadcasts the query to all relevant shards (often all of them)
  2. Each shard returns its top-K results
  3. The router merges results using the scoring function (like BM25) to produce the final ranked list

This scatter-gather pattern parallelizes work but requires fast shard responses to keep overall latency low (usually 10-50ms per shard).

Trade-offs

More shards = better parallelism but higher query fanout overhead. Fewer shards = simpler routing but less capacity per machine.

Key Takeaway: Horizontal scaling partitions the index across machines using document sharding, requiring a query router to scatter requests to all shards and merge ranked results—trading increased coordination overhead for virtually unlimited capacity and throughput.