Section 7: The Ring Amazon Re-Cut Twice - Deep Dive: Partitioning & the Three Strategies

Executive Summary: Amazon got textbook consistent hashing working, then re-cut the ring twice. The 2007 paper describes three strategies. In Strategy 1, random tokens define the ranges, so every join means scanning neighbors' stores and rebuilding Merkle trees. Strategy 2 uses equal partitions placed by random tokens, which gives the worst balance of the three. Strategy 3 uses Q fixed, equal partitions with about Q/S per node, moved whole. We adopt Strategy 3 with Q = 1,024, which comes to ≈ 46.5 partition replicas per node, ≈ 1.46 GB each. A 67th node bootstraps by copying ≈ 65 GB of whole partition files in ≈ 55 minutes at a 20 MB/s throttle. The cost is that Q is a planned migration, not a dial. We revisit it before the fleet passes ~128 nodes.

Interviewer: "You put 1,024 partitions on the board in Section 6. Plenty of designs just give each node a bag of random virtual nodes. Why fixed partitions?"

You: "Random virtual nodes solve balance, not range churn, and churn is what hurts in production. The 2007 paper describes three strategies, each fixing the previous one's operational pain."

Consistent Hashing in One Paragraph

MD5 maps each key to a position on a 128-bit ring. Each node takes one or more tokens (ring positions), and a node owns the range that ends at its token. Adding a node only moves the keys in the ranges it takes over. Mod-N hashing, the rejected baseline, moves almost every key whenever the node count changes. Many tokens per node (virtual nodes) even out load and let a bigger machine take more. The Distributed Key-Value Store module covers this from first principles. What matters here is that "what do the tokens mean?" turned out to be an operational decision, not just a balance one.