Concepts
Search: index shards, replicas, and scatter-gather
Intuition
Imagine a library so large that no single librarian can search everything in a reasonable time. You split the collection into several sections, and each section has several identical librarians. When a question arrives, it is handed at the same time to one librarian from each section; each one searches only their own part and, at the end, someone merges the partial answers into a single list. If a librarian falls ill, another one from the same section takes over, and nobody has to shut down the library.
How it works
According to Barroso, Dean and Hölzle, the documents and the inverted index derived from them add up to many terabytes, so the index is split into index shards, each with a randomly chosen subset of the documents. For each shard there is a pool of replica machines, and the index cluster has one pool per shard. A query is served by a web server (GWS) that sends it, via a load balancer, to one machine from each pool. Each shard queries the inverted index, intersects the document lists of the words and computes relevance only over its own subset. The partial results are combined into a ranked list of document identifiers (docids). Then the document servers, which use the same scheme of random shards with multiple replicas and a load balancer, fetch the title, URL and the keyword-in-context snippet from disk. Because the shards do not need to communicate with each other, the speedup from parallelizing is nearly linear and average latency drops. The two axes of growth are independent: more machines per pool increase serving capacity, and more shards accommodate a larger index. If a replica goes down, the load balancer avoids using it, cluster management tries to revive or replace it, capacity drops in proportion to the slice lost, and all parts of the index remain available. This works because access is mostly read-only, with rare updates done by diverting queries away from the replica.
In practice
The same design appears in search systems that split a large index into replicated partitions and combine the partial results. You choose it when the load is read-heavy and the index does not fit on one machine, and when you want to scale capacity and index size separately. The article shows that it allows building reliability into the software, with replicas on commodity PCs and no fault-tolerant hardware, and increasing the number of shards to compensate for slower CPUs. This concept covers how the index is partitioned and replicated. The effect of waiting for the slowest shard in a wide fan-out and the hedging techniques to contain it are covered separately, in concept_tail_latency_fanout and concept_hedged_tied_requests.
Use it in a design
Practice the cases that rely on this concept in the System Design school.