Consistent hashing: a partition rule that survives resizing

What it is for. Any system that must spread data across machines by key — distributed caches, sharded databases, distributed storage — needs a rule that answers, given only a key: which machine holds this? Stateless compute layers never need it; it lives exactly where state is partitioned.

The property that matters is not the ring. It is locality under membership change: when a machine joins or leaves, only the keys near that machine change owner; keys are never reshuffled between the machines that stayed. Adding a machine should move about 1/N of the keys — no more.

The naive rule fails exactly there. Assign by hash(key) % N: the formula contains the machine count, so adding one machine changes nearly every key's answer. Values still sit on the old machines, but lookups are routed by the new formula — to the application this is a mass cache flush or a full data migration, triggered by the act of scaling.

The ring is one construction that buys the property. Take the hash output range (say 0..99, in reality 0..2^32) and join its ends — a circle only so that the last segment wraps into the first and no tail is left ownerless; every point obeys one rule with no edge cases. Each server hashes its own identity onto the circle: a marker, a coordinate. The numbers are coordinates, not operands — nothing is ever divided by them. A key hashes to a point, walks clockwise, and belongs to the first marker it meets; the segment behind each marker is that server's territory. Writing uses the rule to decide where a value goes; reading uses the same rule to find it. Add a server and you insert one marker: it takes over the one segment in front of it, and only those keys (≈1/N) move. Remove one and its segment passes to the next marker.

Balance needs virtual nodes. A single random marker per server cuts the circle unevenly — 60/25/15 splits happen. So each physical server places 100–200 markers (hashes of name#1, name#2, …). Its territory becomes the sum of many small random segments, and sums of many random lengths converge (law of large numbers): splits land within a few percent. Bonuses: bigger machines can place more markers and take a proportional share; when a server dies, its many scattered segments fall to many different neighbours instead of crushing the next one.

Relatives and alternatives, same property. Redis Cluster replaces the free-form ring with 16,384 fixed slots (a key hashes to a slot; slots are assigned to machines; resizing moves slots, not keys). Rendezvous hashing needs no ring at all: score every server by hash(key, server) and take the highest — a new server only wins the keys where it out-scores, so old assignments between old servers never move. The property is the soul; the ring is one skin.

In practice you rarely implement it. It ships inside the components: Cassandra's partitioner is this ring (virtual nodes are called tokens), memcached clients implement it (ketama), Envoy and HAProxy offer it as a load-balancing mode for stateful backends. Plain PostgreSQL has no sharding at all — the distributed answer there is an added layer (Citus: fixed shard count, a rebalancer that moves shards on resize). The decisions a practitioner actually owns are which component, and above all which column is the shard key — the algorithm is settled, the shard key is expensive to change.