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

Distributed Index Sharding

Partitioning the inverted index across machines by document ID or term for horizontal scaling.

Distributed Index Sharding

You'll learn how to partition inverted indexes across multiple machines to handle billions of documents and thousands of queries per second.

When your search corpus grows beyond what a single machine can store or serve efficiently, you must shard (partition) your inverted index horizontally across multiple machines. This distributes both storage burden and query load.

Core Sharding Strategies

Document-based sharding splits documents into groups (e.g., by document ID ranges or hash). Each shard contains the complete inverted index for its subset of documents. When a query arrives, you fan it out to all shards in parallel, then merge results.

Shard 1: docs 0-999      → complete index for those docs
Shard 2: docs 1000-1999  → complete index for those docs
Shard 3: docs 2000-2999  → complete index for those docs

Term-based sharding partitions by terms themselves—each shard handles a specific range of vocabulary (e.g., terms "a-f" on shard 1, "g-m" on shard 2). Queries go only to relevant term shards, but result merging becomes more complex since a single document may span multiple shards.

Why Document-Based Wins

Most large-scale search systems use document sharding because:

  • Queries typically involve multiple terms, so all shards are needed anyway
  • Uniform load distribution per query
  • Simpler operational reasoning (each shard is an independent search engine)
  • Adding shards is straightforward rebalancing

Trade-offs

Document sharding requires querying all shards for every search, introducing fanout latency. You mitigate this with fast networks, parallel execution, and aggressive timeouts. Term sharding can skip irrelevant shards but complicates ranking (documents split across machines).

Key Takeaway: Distributed index sharding partitions your inverted index by document ID ranges across machines, enabling horizontal scaling by parallelizing both storage and query processing—each shard operates as an independent search instance.