S6 · Build a Replicated Key-Value Store (Dynamo-style)

One key-value server: a port, a protocol, a table in memory and a log underneath. This project runs many of them and answers the question the drawing never had to: which ones hold each key, and what happens when one of them dies.

Before you start. You’ve built S2, a door in front of identical servers, and S3, a key-value server. Both lessons end by suggesting you put the first in front of three copies of the second. This project starts with what goes wrong when you do. The slow build of the fix, one lesson per stage, is Build Your Own Dynamo in From Scratch; this page turns it into one repo and does not repeat its detail. Enough Go is an optional first read.

The idea in 30 seconds

Putting a round-robin balancer in front of several key-value servers makes each server hold a different slice of the data, and a GET usually misses the server that took the SET.
Routing by hash-of-key modulo the server count finds the key again, but moves most keys when a server is added and loses a server’s keys when it dies.
A hash ring moves only the keys next to a new machine, and storing each key on the next N machines clockwise keeps it alive when one dies.
With N copies, a write waiting for W and a read asking R, R + W greater than N means a read always reaches the latest write.
Hinted handoff keeps writes accepted while home machines are down, and Merkle-tree anti-entropy finds what the hints missed without comparing every key.

Read the story · Skip to the numbers