The hash ring

Consistent hashingHash ringThe rehashing problemVirtual nodesLoad distributionHot keysRead replicas / salting

Splitting the data ended on a cliffhanger. Hash-based sharding spreads data beautifully — until you add or remove a shard, and shard = hash(key) % N reshuffles almost everything, because N changed. For a system that's growing, that's a dealbreaker: every time you add capacity, nearly all your data has to move at once. Consistent hashing is the fix — a different way to map keys to shards that moves only a thin slice of the data when the shard count changes.

The problem, precisely

Recall the formula: shard = hash(key) % N, where N is the number of shards. The % N is the weak point. Add one shard and N goes from, say, 4 to 5 — and because every key's shard is computed modulo N, changing N changes the answer for almost every key at once.Concretely: a key with hash = 10 lands on 10 % 4 = 2 with four shards; grow to five and it's 10 % 5 = 0 — a different shard. Do that for every key and almost none stay put. Nearly all the data has to migrate, all at the same moment. Removing a shard does the same thing in reverse. The result is a storm of data movement — heavy load on the databases and a degraded experience for users — striking exactly when you're trying to grow.

The fix: a ring

Consistent hashing's key insight is to stop treating shards as numbered slots and instead arrange both the data and the shards on a circle — the hash ring. The construction has three steps:

1. Take a big range of numbers — say 0 to 2³¹ − 1 (about two billion) — and bend it into a circle, so the largest number wraps back around to 0.
2. Place each shard on the ring by hashing something stable about it (its name or ID) to a point on that circle.
3. Place each key the same way: hash the key to a point on the ring, then walk clockwise until you hit a shard. That shard stores the key.

Data and shards share one ring. A key is hashed to a point, then walks clockwise to the first shard it meets — here, S2. Because a key belongs to the next shard clockwise, adding or removing a shard only moves the keys in one arc; everything else stays exactly where it is.

Now the payoff. Because each key belongs to the first shard clockwise of it, adding or removing a shard only affects the keys in one arc — the stretch of ring between the changed shard and its neighbour. Remove a shard, and only its keys move, passing to the next shard clockwise. Add a shard, and it takes over just the keys in the arc immediately counter-clockwise of its new position. Either way, every other key stays exactly where it was: instead of reshuffling everything, you move a single arc's worth of data — which is the whole point.

Removing a shard. Only S2's own arc — the stretch from S1 up to S2 — is affected; those keys pass clockwise to the next shard, S3. Every other key on the ring stays exactly where it was.

Adding a shard. S*, dropped between S1 and S2, carves out just one slice — the keys from S1 up to itself, which used to continue on to S2. S2 keeps the rest, and every other shard is untouched.

The catch: lopsided load

Consistent hashing kills the redistribution storm, but on its own it creates a different imbalance. When you remove a shard, all of its keys land on one shard — the next one clockwise — which suddenly inherits roughly double the load. Add a shard, and it relieves only its one clockwise neighbour, leaving every other shard as busy as before. Either way the change lands on a single neighbour rather than being shared out.There's a quieter version of the same problem even when nothing changes: with only a few shards dropped at random points, the arcs between them come out uneven — one shard owns a big arc, another a sliver — so the load is lopsided from the start. The result is uneven load across the cluster.

The fix for that: virtual nodes

The trick is to stop giving each shard a single spot on the ring and instead scatter it across many spots. Each physical shard is represented by dozens or hundreds of virtual nodes — separate points on the ring that all route back to the same underlying machine.

Now each shard owns many small arcs sprinkled all around the ring instead of one big contiguous one. So when a shard is removed, its many little arcs are inherited by many different neighbours — the departed load is spread across the whole cluster rather than dumped on one machine. Adding a shard works the same way in reverse: the newcomer lifts a little load off many shards at once.

Virtual nodes: each database sits at several points on the ring (here the highlighted points all belong to DB2). Because its arcs are scattered, removing DB2 hands them to several different shards — some to DB1, some to DB3 — instead of dumping all of its load on one. Real systems use hundreds of points per node, so the spread comes out very even.

The last problem: hot keys

Virtual nodes even out the load as long as every key gets roughly the same traffic. Some keys don't. A single viral key — a celebrity account, a trending video — can be hit so hard that the one virtual node (and so the one machine) holding it is overwhelmed, however evenly the keys were spread. This is the hot-key problem again, the same one we met as hot shards and hot cache keys, and it's unavoidable here because a single key still lives on a single node.

Three standard fixes:

• Read replicas — copy the hot key onto several nodes and balance reads across them. The most common approach.
• Key-space salting — append a small random suffix to the hot key (taylor-swift-0, taylor-swift-1, … taylor-swift-9) so the ten variants hash to ten different nodes. Reads then fan out across them and the results are combined.The cost is on the edges: a write has to update every salted copy, and a read has to query all the variants and merge them — so you salt only the few genuinely hot keys, not everything.
• Adaptive rebalancing — watch traffic in real time and move hot key-ranges off overloaded nodes. Operationally complex, but some systems (DynamoDB) do it automatically.

In an interview

If you're asked how to grow a sharded database or a distributed cache without downtime, "consistent hashing with virtual nodes" is the headline answer — then show you understand why: the ring moves only one arc of data when the cluster changes, and virtual nodes keep that movement evenly spread. Naming the hot-key caveat on top signals real depth.

---

That's the whole machine: data and shards on one circle, each key owned by the next shard clockwise, each shard scattered into many virtual nodes so the load stays even, and hot keys handled on top. It's what lets elastic distributed stores — DynamoDB from the section above, Cassandra, and others built on the same idea — add and remove nodes while live without reshuffling the world.