Consistent Hashing

A trading firm shards its market-data cache across 8 machines by ordinary hashing: server = hash(symbol) mod 8. One machine dies, so it moves to 7. Nearly every symbol's hash(symbol) mod 7 lands on a different machine than hash(symbol) mod 8 did — almost the entire cache is now a miss, and every downstream system has to refetch nearly everything at once. Consistent hashing exists to make that kind of resizing cheap instead of catastrophic.

How it works

Imagine a circle of hash values from 0 to some large maximum, then wrapping back to 0. Hash each server's identifier onto a point on this circle. To find which server owns a given key, hash the key onto the same circle and walk clockwise to the first server point you hit.

Worked example

Three servers A, B, C hash to positions 10, 40, 75 on a ring of size 100. Keys hash to: key1 → 15, key2 → 50, key3 → 90. Walking clockwise: key1 (15) lands on B (next point after 15 is 40); key2 (50) lands on C (next point after 50 is 75); key3 (90) wraps around to A (next point after 90, wrapping past 100, is 10).

Now add server D at position 60. Re-check ownership: key1 still lands on B (40 is still its next point going clockwise from 15). key2, previously landing on C at 75, now lands on D at 60 — it moves. key3 is unaffected, still landing on A. Only key2, the one sitting between D's new position and its old owner, ever moved; keys owned by A and unaffected parts of B and C stayed put.

What this means in practice

Consistent hashing is the backbone of distributed caches (Memcached client libraries), distributed databases (DynamoDB, Cassandra), and CDN routing, anywhere a set of servers can grow or shrink and a full reshuffle on every change would be too expensive. In practice, each physical server is usually hashed to many points on the ring ("virtual nodes"), not just one — a single point risks one server inheriting a wildly uneven, oversized arc of the ring, while dozens of virtual nodes per server smooth that out to a roughly even split of keys.