Part 4 of 8 · 3 min read
Partition and replicate
Spread the keys, keep N copies.
Partition. The data is split into pieces across servers. Two aims: spread the data evenly, and move as little as possible when servers are added or removed. Consistent hashing (Level 4) does both. Servers sit on a hash ring. A key is hashed to a point on the ring and is stored on the first server met when walking clockwise. The book names two benefits: servers can be added or removed automatically as load changes, and a bigger server can be given more virtual nodes (extra points on the ring) so it takes a share in proportion to its size.
Replicate. For availability, each pair is copied to N servers, where N is a setting, often 3. After hashing a key onto the ring, walk clockwise and pick the first N servers. With virtual nodes, the first N points may belong to fewer than N machines, so only distinct machines are counted. Copies should also go to different data centres, since nodes in one data centre can fail together through a power or network fault. The copies are made without making the client wait for all of them.
Quorums. Copies must be kept in step. The book uses three numbers:
- N, the number of copies.
- W, the write quorum: a write succeeds when W copies confirm it.
- R, the read quorum: a read succeeds when R copies answer.
A coordinator node acts as a go-between: it takes the client's request, sends it to the copies, and waits for W or R answers. W = 1 does not mean one copy exists. It means the coordinator needs only one confirmation before it replies, while the others are still being written.
The settings trade speed against consistency:
| Setting (N = 3) | Effect |
|---|---|
| W = 1, R = 1 | Fastest, but a read may miss the latest write |
| R = 1, W = N | Fast reads, slow writes |
| W = 1, R = N | Fast writes, slow reads |
| W = 2, R = 2 (W + R > N) | Strong consistency. Any read set overlaps any write set in at least one node |
| W + R at most N | Strong consistency is not guaranteed |
Why does W + R > N help? With N = 3, W = 2 and R = 2, a write reached 2 nodes and a read asks 2 nodes. Two groups of 2 out of 3 must share at least 1 node, so some node in the read has the latest value.
Consistency models. The book names three: strong (a read always sees the latest write), weak (a read may not), and eventual, a kind of weak where all copies agree after enough time. Strong consistency usually needs a copy to refuse reads and writes until all copies have the latest, which costs availability. Dynamo and Cassandra choose eventual consistency, and rely on clients to cope with a few differing versions.
Check yourself: 1. Where is a key stored on the ring? 2. Why must the walk pick distinct machines? 3. Why does W + R > N give strong consistency?