Consistent Hashing

How it works

Consistent hashing maps both keys and servers onto a ring, so each key belongs to the next server clockwise. Adding or removing a node only moves the keys in one arc — not the whole keyspace — making it ideal for distributed caches and sharded stores.

Mental models

• Keys and nodes share one hash ring; a key goes to the next node clockwise.
• Virtual nodes smooth out uneven key distribution.
• Removing a node only reassigns its arc — minimal data movement.
• This is what makes sharding rebalancing cheap: only ~1/n of the keyspace moves when a node joins or leaves, not all of it.

Common pitfalls

• Too few virtual nodes per physical node and the ring stays lumpy — some nodes still get more traffic than others.
• The lookup structure (sorted ring) still needs O(log n) search per key — not free, just far cheaper than a full reshuffle.