5 / 5 Consistent Hashing & Rebalancing

Why Strategy One Died

Dynamo originally gave each node T random tokens on the ring and let every pair of consecutive tokens define a range, so ranges varied in size and shifted whenever membership changed. Amazon later migrated production instances to fixed, equally sized partitions.

Select every operational problem the paper reports with the original scheme. More than one applies.

A

Lookups got slower, because resolving a key meant searching an ordered list of T times S tokens instead of indexing a fixed partition table

B

A joining node had to make its donors scan their local stores to find the items in the range being handed over, and during peak season that bootstrap took close to a day

C

Any join or leave changed the ranges many nodes owned, so Merkle trees had to be recomputed for the new ranges on a live system

D

Randomly sized ranges made a whole-keyspace snapshot impractical, so archival meant pulling keys out of each node separately