Sharding a search index: scatter, gather and merge

Why shard

One machine cannot hold or search a very large index within the latency budget. Sharding splits the index into pieces, each on its own machine, so storage and work are spread out. Replicas copy each shard for availability and extra read capacity.

Two ways to partition

• Document-partitioned (local index): each shard indexes a subset of the documents and holds a complete inverted index for them. Writes touch one shard. Every query must visit every shard. This is what Elasticsearch and Solr do.
• Term-partitioned (global index): each shard holds the postings for a subset of terms. A query touches only the shards for its terms, but a write touches many shards and long posting lists must be combined across machines. It is rare in practice.

100%

Figure SDA-SAG-05-1 · Scatter, gather and merge · © forcsguy.com

Decisions that matter

• Shard size and count. Too many tiny shards waste memory and add fan-out; too few huge shards recover slowly and cannot spread load. Many teams aim for tens of gigabytes per shard. The primary shard count is hard to change later, so plan for growth or use time-based indexes.
• Routing. By default a document goes to a shard by hashing its id, which spreads data evenly. Routing by tenant or user keeps one customer's data together so queries can hit a single shard, at the risk of uneven shards.
• Tail latency. A query is as slow as its slowest shard. Use replicas, timeouts, and hedged requests (send to a second replica if the first is slow).
• Deep pagination. Page N needs the first N x pageSize results from every shard. Use cursors (search-after) instead of large offsets.
• Scoring across shards. Each shard computes statistics such as IDF from its own documents. Even, large shards make the difference small; otherwise gather global statistics first.
• Rebalancing and reindexing. Plan how to add capacity without downtime, usually by indexing into a new index and switching an alias.

100%

Figure SDA-SAG-05-2 · Time-based indexes · © forcsguy.com

Keeping the index fresh

Documents usually live in a primary database and are copied to the search index. Use a change stream or an outbox so updates are not lost, accept that search is eventually consistent, and keep a way to rebuild the whole index from the source of truth.

Real-world reading