beginnerintermediateadvanced

System Design · Consistent Hashing

Consistent Hashing

Routing keys to nodes on a ring, so scaling a cluster up or down moves only a small slice of the data

The ringnodes and keys hashed into one circular space
Virtual nodes~100-200 points per node evens out load
Minimal movement~1/N of keys move per node change

1.What consistent hashing is for, and the ring concept

Consistent hashing is a way to map both data (keys) and servers (nodes) onto the same circular hash space, called a ring, so that each key belongs to whichever node comes next on the ring in clockwise order. It solves a specific problem with plain "hash(key) % N" routing: with modulo hashing, adding or removing a single server changes the result of the modulo for almost every key, so almost every key gets remapped to a different server at once. On a ring, only the keys that fall between the changed node and its neighbor move — everyone else keeps pointing at the same node they always did. That is why it shows up anywhere a distributed cache, a partitioned datastore, or a load balancer needs to route the same key to the same node consistently, even as nodes come and go.

Key features

Both nodes (servers) and keys are hashed into the same numeric space and placed as points on a circle (the "ring").
A key belongs to the first node found walking clockwise from the key's position on the ring.
Used for three related problems: distributed caching (which cache node holds a key), data partitioning (which shard owns a row), and request routing/load balancing (which backend server a request goes to).
The alternative, "hash(key) % N", ties every key's owner to the exact current node count N — changing N remaps nearly all keys at once, which is the specific failure consistent hashing avoids.
Amazon's Dynamo, Apache Cassandra and Akamai's CDN are real systems documented as using consistent hashing for this reason.

Modulo hashing vs. ring-based consistent hashing

Modulo hashing vs. ring-based consistent hashing
Property	hash(key) % N	Consistent hashing (ring)
Where a key routes	Depends on the current node count N	Depends only on ring position, not N
Effect of adding/removing a node	Nearly all keys remap	Only the keys near the changed node remap
Needs to know total node count upfront	Yes — every lookup uses N	No — lookup only needs the ring
Typical use	Fixed-size shard counts decided in advance	Caches/stores that scale nodes up or down

Modulo hashing vs. ring-based consistent hashing

hash(key) % N

Routing depends on the current node count N
Adding/removing a node remaps nearly all keys
Every lookup needs to know N upfront

Consistent hashing (ring)

Routing depends only on ring position
Only keys near the changed node remap
Lookup only needs the ring, not N

Command

text

ring = sorted positions of hash(node_id) for every node
key's owner = first node position >= hash(key), walking
              clockwise (wrap around to the smallest
              position if none is found before 360°/2^32)

Ring-based lookup (hash the key, walk clockwise to the next node) means only the keys near a changed node move when that node joins or leaves — unlike hash(key) % N, where changing N remaps nearly everything.

2.Virtual nodes and why they even out load

A plain ring with one point per physical node has an uneven-load problem: hashing a handful of node IDs onto a large circular space produces gaps of very different sizes, purely by chance, so some nodes end up owning far more of the ring — and far more keys — than others. Virtual nodes fix this by hashing each physical node to many points on the ring (commonly on the order of 100-200 per node) instead of one. Each of those points is a separate "virtual" node that maps back to the same physical machine, so a physical node's total share of the ring is the sum of many small, scattered arcs rather than one large-or-small arc decided by a single unlucky or lucky hash.

Key features

Each physical node is hashed to many positions on the ring (often ~100-200 virtual nodes per physical node) instead of just one.
A key's owner is still found the same way — walk clockwise to the next ring position — but that position now maps to a virtual node, which maps to a physical node.
More virtual nodes per physical node produces a more even key distribution, at the cost of more ring metadata to store and traverse.
Virtual nodes also make heterogeneous clusters possible: a physical node with more capacity can be given proportionally more virtual nodes, so it takes a proportionally larger share of the keyspace.
When a physical node joins or leaves, its virtual nodes are scattered all over the ring, so the resulting key movement is spread thinly across many other physical nodes instead of dumping it all on one neighbor.

One point per node vs. virtual nodes

One point per node vs. virtual nodes
Property	1 point per physical node	Many virtual nodes per physical node
Load distribution	Uneven — depends on luck of a few hash values	Even — averages out over many hash values
Effect of a node leaving	Its entire arc dumps onto one neighbor	Its keys spread thinly across many nodes
Supports unequal node capacity	No — every node gets one equal-ish arc	Yes — give bigger nodes more virtual nodes
Ring metadata size	O(number of physical nodes)	O(number of physical nodes x virtual nodes each)

1 ring point per node vs. ~150 virtual nodes each

1 point per node

Load distribution is uneven — pure chance
A node leaving dumps its whole arc on one neighbor
Every node gets one equal-ish arc, no tuning

Virtual nodes

Load distribution averages out and is even
A leaving node's keys spread thinly across many
Bigger nodes can get proportionally more points

Command

text

for physical_node in cluster:
    for i in range(virtual_nodes_per_node):   # e.g. 150
        ring_position = hash(f"{physical_node.id}-{i}")
        ring[ring_position] = physical_node

One hash point per physical node lets chance create big, uneven arcs; ~100-200 virtual points per physical node averages that out, spreads a leaving node's keys across many neighbors instead of one, and lets unequal-capacity nodes get proportionally more points.

3.Adding or removing a node moves about 1/N of the keys

This is the payoff of the whole ring design: when a node joins or leaves an N-node ring, only the keys that fall on the arc immediately owned by that node need to move — everyone else's owner is unaffected, because everyone else's "next node clockwise" hasn't changed. For a roughly balanced ring that works out to about a 1/N fraction of all keys moving per membership change, compared to hash(key) % N remapping close to (N-1)/N of all keys — nearly everything — for the same change. That difference is the entire practical reason distributed caches and partitioned stores use a ring instead of modulo hashing: adding capacity, or losing a node to a crash, costs a small, roughly predictable amount of data movement instead of a near-total reshuffle.

Key features

Adding a node: a new arc is carved out of exactly one existing node's territory (the node whose arc the new node lands inside) — only the keys in that carved-out slice move to the new node.
Removing a node: that node's entire arc is absorbed by the next node clockwise — only the keys that node owned move, and they all move to one place (its clockwise neighbor).
With virtual nodes, both effects are spread across many physical nodes at once instead of concentrated on a single neighbor, because a physical node's arcs are scattered around the ring.
The commonly cited bound is that roughly K/N keys move for K total keys and N nodes, versus close to all of them for hash(key) % N — this is the headline result consistent hashing is built to deliver.
This bound assumes reasonably even ring coverage (helped by virtual nodes); a poorly balanced ring can still see a disproportionate share of keys move from whichever arc happens to be largest.

Key movement on a membership change, ring vs. modulo

Key movement on a membership change, ring vs. modulo
Change	hash(key) % N	Ring-based consistent hashing
Add 1 node (N -> N+1)	Nearly all keys remap (N/(N+1) of them)	About 1/(N+1) of keys move, to the new node
Remove 1 node (N -> N-1)	Nearly all keys remap	About 1/N of keys move, to one clockwise neighbor
Keys unaffected by the change	Very few	All keys not on the changed arc(s)

Adding node E splits only C's arc — 1 of 8 keys moves

splitsk5 movesno change

C owns (35, 60]

before: k4, k5

C owns (35, 50]

after: k4 stays

E owns (50, 60]

after: k5 moves here

A, B, D

6 other keys, untouched

Command

text

add node X at ring position P:
    only keys between P and the previous node
    (walking counter-clockwise from P) move to X

remove node Y at ring position Q:
    all keys Y owned move to the next node
    clockwise from Q

Adding or removing one node only changes the arc(s) adjacent to that node — roughly 1/N of keys move, versus nearly all of them under hash(key) % N — and virtual nodes spread even that movement across many physical neighbors instead of dumping it on one.

Spotted a mistake on this page? Tell us.

Read Sheet