Consistent Hashing

Hash servers and keys onto a ring; each key belongs to the next server clockwise. Adding or removing a server remaps only ~1/N of keys.

What to know

Virtual nodes (100–200 per server) smooth load imbalance.
Naive mod-N hashing remaps nearly everything on membership change — the problem this solves.
Jump hash and rendezvous hashing are compact alternatives.

In the wild: DynamoDB, Cassandra, Memcached clients, CDN request routing, Kafka partitioners.

Ring placement + binary search

O(log S)

Route key → owning server

Virtual-node rebalancing

O(1) per key

Even load across heterogeneous servers