Part 6 of 8 · 3 min read
Replicas on the ring, and where it is used
Placing copies by walking clockwise, and real systems that rely on the ring.
Think of the clock edge once more. To keep three copies of a parcel, put one with the first person met clockwise and a copy with each of the next two people. If two of the three people are the same twin in two coats, the copy is no safer, so skip the twin.
The book "System Design Interview" describes data replication on the ring in its key-value store chapter. To keep data safe, data is copied asynchronously to N servers, where N is configurable. After a key is mapped to a position on the ring, walk clockwise and choose the first N servers on the ring to store copies. In its figure with N = 3, key0 is stored on s1, s2 and s3.
With virtual nodes, the first N positions on the ring may belong to fewer than N real servers (the same server's virtual nodes may sit next to each other). To avoid it, only unique servers are chosen on the clockwise walk. For better reliability, nodes in the same data centre often fail together (power, network, disaster), so replicas are placed in distinct data centres.
A worked example on the ring from section 2 (S0 at 10, S1 at 35, S2 at 60, S3 at 85), N = 3. Key k1 at 20: first server clockwise S1, then S2, then S3. Copies on S1, S2, S3. Now with virtual nodes: suppose the clockwise order from a key is s0_4, s0_9, s1_2, s2_7. The first three positions hold only two real servers (S0, S0, S1). Skipping the duplicate gives S0, S1, S2.
The book lists the advantages of using consistent hashing to partition data:
- Automatic scaling. Servers can be added and removed as load requires.
- Heterogeneity. Virtual nodes proportional to capacity.
- Less hot-spot trouble. Spreading data more evenly helps stop popular keys that happen to be neighbours from landing on one shard (the book's example is three famous singers whose data lands on one shard).
Real systems the book names: the partitioning of Amazon's Dynamo database, data partitioning across the Apache Cassandra cluster, the Discord chat application, the Akamai content delivery network and the Maglev network load balancer.
A caution from the other book. "Designing Data-Intensive Applications" points out that the original consistent hashing, by Karger and others, was a way of spreading load across an internet-wide system of caches such as a CDN. Its random partition boundaries avoid the need for central control. But it says this approach does not work very well for databases, so it is rarely used for them in practice, and the term is often used inaccurately in database documents. It prefers the name hash partitioning. The partitioning schemes of module 5 (fixed partitions, dynamic splitting, partitions per node) are what databases mainly use. The partitions-per-node scheme, used by Cassandra, is the closest to the original consistent hashing. In an interview, the sensible stance: use the ring for caches and similar stores, explain virtual nodes, and say that databases often use fixed or dynamic partitions.
| Use | Fit |
|---|---|
| Cache cluster | Excellent: a moved key is just a miss |
| Load balancing by key (sticky) | Excellent |
| Dynamo-style key-value store | Good, with replicas on the ring |
| Relational or range-scanned database | Poor: fixed or dynamic partitions are better |
Check yourself:
- Why does the replica walk skip servers it has already chosen?
- Why is the ring a better fit for a cache than for a database that must move data safely?