Consistent Hashing: The Algorithm That Lets Cassandra Add a Server Without Breaking Everything

Covers: The Modulo Problem, Hash Ring, Virtual Nodes, Real Implementations in Cassandra and Dynamo

The Promise We Made on Day 3 (Now Fulfilled)

Back on Day 3, when discussing hash-based sharding, we hit a wall: adding a server to a hash-based shard remaps almost everything.

4 shards: shard = hash(key) % 4