Consistent Hashing

You have a cache spread across N servers, and you need to decide which server holds a given key. The obvious answer — server = hash(key) % N — is correct, fast, and a trap. It works flawlessly right up until the day N changes, and then it detonates. Consistent hashing is the fix, and like most great distributed-systems ideas, it’s an idea about minimizing change rather than an idea about cleverness.

The rehashing catastrophe

Start with the naive scheme. Three cache servers, modulo placement:

key "alice"  → hash=17 → 17 % 3 = 2 → server 2
key "bob"    → hash=22 → 22 % 3 = 1 → server 1
key "carol"  → hash=30 → 30 % 3 = 0 → server 0

Now one server dies, or you add a fourth to handle load. N goes from 3 to 4 (or to 2). Recompute:

                N=3        N=4
key "alice"  →  17%3=2  →  17%4=1   MOVED
key "bob"    →  22%3=1  →  22%4=2   MOVED
key "carol"  →  30%3=0  →  30%4=2   MOVED

Almost every key maps to a different server. For a cache, that means a near-total miss storm: the data is still in the cluster, but nobody can find it at the new address, so every request falls through to the database at once. For a sharded database, it means physically moving nearly all your data across the network. Changing N by one shouldn’t require touching N-1/N of your keys — but modulo hashing does exactly that. The scheme couples the address of a key to the exact count of servers, and that coupling is the disease.

The hash ring

Consistent hashing breaks the coupling with one move: hash the servers onto the same space as the keys. Imagine the output of your hash function bent into a circle — a ring of, say, 0 to 2³²-1 that wraps around. Place each server on the ring by hashing its identifier. Place each key on the ring by hashing the key. Then the rule is:

A key belongs to the first server you meet walking clockwise from the key’s position.

                 0 / 2^32
                    │
            S3 ●    │    ● S1
                ╲   │   ╱
                 ╲  │  ╱
     keyB ○───────╲ │ ╱───────○ keyA  → walks clockwise to S1
                   ╲│╱
        ────────────●────────────
                   ╱│╲  S2
                  ╱ │ ╲
                 ╱  │  ╲
            keyC ○  │   (keyC → walks clockwise to S3)

Each server “owns” the arc of the ring between itself and the previous server going counter-clockwise. Now watch what happens when a server leaves:

S2 dies. Only the keys in S2's arc are affected — they walk
clockwise to the NEXT server (S1). Every other key stays put.

Adding a server is the mirror image: a new node inserted on the ring steals only the slice of keys between it and its clockwise neighbor. On average, a membership change relocates just K/N keys (one server’s share) instead of nearly all of them. That is the whole point: the blast radius of a change is one node’s worth of keys, not the entire keyspace.

The balance problem, and virtual nodes

The ring as described has two flaws, both rooted in the same cause — you only get a handful of random points on the circle.

Uneven load. Three random points rarely cut a circle into three equal arcs. One server might own 50% of the ring by bad luck, becoming a hotspot while others idle.
Uneven failover. When a server dies, all of its keys dump onto its single clockwise neighbor, doubling that one node’s load instead of spreading the orphaned keys across the cluster.

The fix is virtual nodes (vnodes): instead of placing each physical server at one point, place it at many points — hash S1#1, S1#2, … S1#200 and scatter all 200 around the ring.

Without vnodes:           With vnodes (each server = many small arcs):
  ●S1      ●S2              ·S1 ·S3 ·S2 ·S1 ·S2 ·S3 ·S1 ·S2 ·S3 ·S1
      ●S3                   (interleaved all around the ring)
  3 big lumpy arcs          hundreds of tiny arcs, ~even per server

Now each physical server owns hundreds of tiny arcs sprinkled everywhere. The law of large numbers takes over: total load per server converges to near-even, and when a server dies its many small arcs spill onto many different neighbors, so the orphaned load spreads across the whole cluster instead of crushing one node. Vnodes also let you give a beefier machine more virtual points, weighting it to take a larger share — heterogeneity for free.

Where you’ll actually meet it

Consistent hashing is the placement engine underneath a surprising amount of infrastructure: distributed caches (memcached client libraries, client-side Redis sharding — though Redis Cluster itself uses fixed hash slots instead), Dynamo-style databases (Amazon DynamoDB, Cassandra, Riak), CDN edge selection, and request load balancers that want session affinity (the same user keeps landing on the same backend, and a backend leaving only reshuffles its own users). Anywhere you must map a huge keyspace onto a changing set of nodes and you care about minimizing movement on change, this is the tool. It’s the natural partner to everything in Partitioning & Sharding — consistent hashing is one specific, churn-minimizing answer to the “which shard owns this key?” question, and the one most clusters that resize dynamically reach for.

What it buys, what it costs

The benefit is precise: a membership change moves one node’s share of keys instead of nearly all of them — bounded, predictable churn that turns cluster resizing from a catastrophe into a routine operation. The costs are real too: you maintain a ring data structure (a sorted map you binary-search per lookup), vnodes multiply your metadata, and you give up the dead-simple, stateless % N arithmetic for something you must implement, test, and keep consistent across every client. As ever, no free lunch — but for a cluster that grows, shrinks, and loses nodes, it’s a bargain.

By the numbers — the churn of % N vs. the ring

Put real numbers on the headline. You run a 100-node cache and add one node (100 → 101).

modulo  hash(key) % N :  a key keeps its home only if  hash % 100 == hash % 101
                         → only ~1% stay put; ~99% of keys relocate
consistent hashing    :  the new node steals one node's share of the ring
                         → ≈ 1/101 ≈ 1% of keys move; the other ~99% stay put

The two schemes swap places: modulo gives perfect balance but moves nearly everything on any resize, while consistent hashing moves one node’s worth and accepts a few percent of load imbalance (tamed by virtual nodes). For a 100-node cache, that’s the difference between a ~99% miss storm that buries your database and a routine ~1% reshuffle nobody notices. The benefit isn’t smaller movement by a little — it’s smaller by a factor of N.

The architect’s lens

Before you reach for the hash ring, answer the five questions:

Why does it exist? Because the obvious hash(key) % N couples a key’s address to the exact server count, so changing N by one relocates roughly (N−1)/N of all keys — a near-total miss storm for a cache, a near-total data move for a sharded DB.
What problem does it solve? Bounded churn on membership change. Hashing servers and keys onto the same ring and walking clockwise means a node joining or leaving moves only its own arc — about K/N keys — turning cluster resizing from a catastrophe into a routine operation.
What are the trade-offs? You give up % N’s dead-simple, stateless arithmetic and perfect balance for a ring structure you must implement, test, and keep consistent across clients. A handful of random points cuts the circle unevenly, so you add virtual nodes (~128–few hundred per server) to smooth load — trading more metadata for lower variance.
When should I avoid it? When N is fixed and never changes, plain modulo is simpler and perfectly balanced. And when you need range queries (scan keys k1..k2), hashing scatters them — range partitioning fits better.
What breaks if I remove it? Every resize triggers the rehashing catastrophe: a 100→101 node change relocates ~99% of keys instead of ~1%, and without vnodes a dead node dumps its entire load onto a single clockwise neighbor instead of spreading across the cluster.

Check your understanding

Walk through why hash(key) % N relocates almost every key when N changes by one, and quantify the fraction that moves.
State the clockwise placement rule, and explain why only one node’s worth of keys move when a server joins or leaves the ring.
What two distinct problems do virtual nodes solve, and what is the underlying cause both share?
Why does adding more virtual nodes improve balance, and what is the cost of pushing that number very high?
How would you use vnodes to make a cluster of unequal machines (some with twice the RAM) take load proportional to capacity?

Show answers

hash(key) % N couples a key’s address to the exact server count, so changing N by one recomputes the modulus for nearly every key. Concretely, roughly (N−1)/N of all keys relocate on any membership change — at small N that’s “most of them,” and for a cache it triggers a near-total miss storm.
Hash both servers and keys onto the same ring; a key belongs to the first server met walking clockwise from the key’s position. When a node joins or leaves, only the keys in its single arc are affected — they shift to the next clockwise server while every other key stays put — so on average just K/N keys (one node’s share) move. The blast radius of a change is one node’s worth of keys, not the whole keyspace.
Uneven load (a few random points rarely cut the ring into equal arcs, so one server can own a hotspot share) and uneven failover (a dead node dumps all its keys onto its single clockwise neighbor). Both share one cause: you only get a handful of random points on the circle. Virtual nodes give each server many scattered points, fixing both.
More vnodes means each server owns many tiny arcs, so by the law of large numbers total load per server converges toward even and a failure spills onto many neighbors. The cost is more ring metadata to store and binary-search per lookup — the classic accuracy-vs-overhead dial (practically ~128 to a few hundred per server).
Give the bigger machine proportionally more virtual points — e.g. a node with twice the RAM gets twice as many vnodes. Since each vnode owns roughly an equal slice of the ring, more points means a larger total share of keys, so load lands proportional to capacity — heterogeneity for free.