KV: the ring

One big book cut into several, with a rule that says which book each name goes into. This build writes that rule in Go, and then asks what happens to it on the day a new book arrives.

Before you start. Splitting the ledger (sharding) cut one book into several because one book, on one machine, could not keep up: every name had to live in exactly one of them, and a rule that anyone could work out on their own said which. Partitioning priced the part this lesson is about, which is what has to move when a machine joins. That is all you need: many machines, each holding a slice of the data, and a rule that picks the slice. This is the first of four builds; by the last one you will have a small key-value store (a program that stores a value under a name, like a coat check) spread across five machines, and you will kill two of them and watch it survive.

The idea in 30 seconds

A hash turns any name into a big number, the same one every time, so every client can work out where a key lives without asking anyone.
Picking a node by the remainder, hash % nodes, moves about four keys in five when a fifth node joins, because the divisor changed. For a cache that means going cold all at once.
The ring puts nodes and keys on the same clock face; a key belongs to the first node clockwise. A new node takes keys only from the arcs it lands in, and every moved key moves to it.
One mark per node makes lumpy arcs. Virtual nodes, many marks per machine, even the load out; with 100 each the busiest node carried 1.03 times the average.
A key’s preference list is the first few different machines clockwise from it, and it is where the copies of that key live.

Read the story · Skip to the numbers