Partitioning

When one machine can’t hold all your data, or answer all your writes, you cut the data into pieces and give each machine one piece; this lesson is about cutting it without sending all the work to one machine anyway. The story-first cut is Splitting the ledger (sharding); this adds what the board leaves out - splitting a secondary index, what moves when a machine joins, and how a client finds the right one.

Before you start. The previous lesson, replication Replication, put a copy of the whole dataset on every machine, so losing one machine cost you nothing. This lesson starts from a dataset too big, or too busy, for any one machine to hold at all: instead of copying it everywhere, you cut it into pieces and give each machine only its piece.

The idea in 30 seconds

One machine runs out of room eventually; the fix is to cut the dataset into pieces and give each machine one piece, not to buy a bigger machine.
Cutting by range keeps scans fast and sends every write for a growing key to one machine. Cutting by hash spreads writes evenly and kills scans.
A hash sends the same key to the same machine every time, so it cannot fix one key that gets more traffic than the rest - only the application can, by salting it into several keys.
Rebalancing by hash mod N moves nearly everything when the machine count changes; a large fixed pool of partitions, handed out whole, moves close to the unavoidable minimum instead.
A secondary index faces the same range-vs-hash choice all over again, and the answer trades fast writes for fast reads or the other way round.
Someone still has to tell a client which machine holds its key - that part is request routing, and it is its own small service-discovery problem.

Read the story · Skip to the numbers