Consistent hashing — resharding without a full data migration

The sharding lesson showed that naive hash(key) % number_of_shards breaks badly when number_of_shards changes: adding one more shard changes the modulo result for nearly every existing key, meaning nearly all data has to physically move between machines just to add capacity. Consistent hashing is the specific technique that fixes this — not by avoiding hashing, but by changing what gets hashed onto what.

Both the shards themselves and the individual keys are hashed onto positions on the same circular space — imagine a clock face with an enormous number of positions instead of 12. A shard sits at whatever position its own hash lands on; a key is assigned to whichever shard's position is the next one found going clockwise from the key's own hashed position. This is the entire mechanism: "walk clockwise from the key until you hit a shard."

When a new shard is added, it takes a position somewhere on the ring — and only the keys that fall in the ring segment between the new shard and the next shard clockwise need to move, to the new shard. Every key anywhere else on the ring still walks clockwise to exactly the same shard it did before, because nothing about their position or the position of their previous "next shard clockwise" changed. This is the entire improvement over modulo: instead of touching nearly every key, only the keys in one specific ring segment are affected.

Removing a shard works identically: only the keys that were mapped to the removed shard need reassignment, to whichever shard is now next clockwise in its place. Every other key's clockwise walk is unaffected, for the same reason adding a shard didn't touch them — nothing changed about their own position or about the nearest shard in their direction.

With only one ring position per shard, pure chance in where each shard's hash happens to land can leave one shard responsible for a much larger arc of the ring than the others — an uneven, "hot" shard, similar to the imbalance problem from a poorly chosen shard key. The standard fix is virtual nodes: each real shard is given many positions around the ring (dozens or hundreds) instead of just one, so its total coverage is the sum of many small arcs scattered around the ring rather than one large contiguous one — which averages out far more evenly across shards, the more virtual nodes each one has.

The exact same ring mechanism is how many distributed caches (Memcached client libraries, for instance) decide which cache server holds which key — and it matters for the identical reason: adding or removing a cache server should invalidate/relocate only a fraction of the cached keys, not force every client to recompute where nearly everything lives, which would effectively empty the entire cache at once (a "cache stampede" the moment a server is added or removed). It's also the underlying mechanism in distributed hash tables (DHTs) used by some peer-to-peer systems, for the same "minimize what has to move when membership changes" reason.

Consistent hashing doesn't make hashing itself more sophisticated for its own sake — it exists entirely to solve one operational problem: scaling a hashed, partitioned system (shards, cache servers, DHT nodes) up or down without a full-system data migration every single time. The plain hash(key) % N approach is simpler to reason about and completely fine for a system that will never resize — the cost of consistent hashing's extra complexity (the ring, virtual nodes) is worth paying specifically once resizing a live system without massive data movement becomes a real, recurring requirement, not a one-time event.