Consistent hashing

To find a key's shard, you hash the key. The simple way — hash mod the number of shards — breaks when that number changes, because almost every key lands on a different shard and the data must move. Consistent hashing puts shards and keys on a ring, and each key belongs to the next shard round the ring. Adding a shard then moves only the keys it takes over — about 1/N of them — and removing one hands on only its own keys. Giving each server many points on the ring (virtual nodes) keeps the slices even.

Use when

Shards or cache servers are added and removed while the system runs · A cache cluster where a reshuffle would send almost every lookup to the database at once · Mapping keys to servers without a central lookup table

Avoid when

The number of shards never changes — a plain hash is simpler · You need range scans over adjacent keys — hashing scatters them · One key gets more traffic than one server can take — the ring won't split it (see hot keys)

Trade-offs

Only ≈ 1/N of the keys move per change, but the ones that do still have to be copied · Many virtual nodes even out the slices, but add more neighbours and more maintenance work · Fixed slots (hash slots, virtual partitions) make moves simple, at the price of a slot → node map to keep

Requires

Sharding