Build Your Own Dynamo

One pile of data cut into slices, one slice per machine, and the ways of deciding which slice a name goes to. The warning in its bottom half, never pick the machine by dividing by the machine count, is the first wall this build hits.

Before you start. This series builds a small copy of Dynamo, the store Amazon wrote to keep each saved value on several machines and keep answering while some of those machines are dead. You need two ideas, refreshed here: a hash is a scrambler that turns any name into a big number, the same number every time for the same name, and a replica is one copy of a value kept on another machine, so the value survives when the first machine dies (if Go is new to you, Enough Go to read these builds is an optional read first).

Code: teaching/code/from-scratch/kv/ - one Go module, each stage runs alone: go run ./01-ring … go run ./04-anti-entropy. Nothing listens on a network: the five machines are five entries in one program’s memory, so every run prints the same lines.

The idea in 30 seconds

In 2009 LinkedIn’s databases could spread out reading but not writing, so it built its own store on the design in Amazon’s Dynamo paper.
A key-value store answers only “what is filed under this key?”, and giving up everything else is what lets it spread over many machines easily.
Picking a machine by the remainder after dividing by the machine count moves most keys whenever a machine is added; placing machines and keys on one circle moves only the keys the new machine takes.
Each key is copied to three machines. If a write waits for two of them to confirm and a read asks two of them, two plus two is more than three, so at least one machine is in both groups and the read sees the write.
When a machine is down, another holds its copies with a note and hands them back later, and a background comparison between machines repairs whatever the notes missed.

Read the story · Skip to the numbers