SD notes

Consistent Hashing

Intermediate · 6 min read · updated 29 October 2026

Quick answer

What is consistent hashing?

Consistent hashing places servers and keys on the same circular hash space, and stores each key on the first server clockwise from it. When a server joins or leaves, only the keys on its arc move, about 1/N of them, instead of almost every key moving as with hash mod N.

On this page

The problem with mod N
The hash ring
Adding a server
Removing a server
Virtual nodes
Ring vs mod N
In practice
Interview questions
Common questions

Sharding needs a rule for which server owns a key. Consistent hashing is a rule that barely changes when the set of servers does.

The problem with mod N

server = hash(key) mod N spreads keys evenly, but depends on N.
Add or remove one server and most keys get a new home.
From 3 to 4 servers about 3 in 4 keys move (a key stays only if h mod 3 = h mod 4).
For a cache that is a stampede of misses at once.

The hash ring

Hash space bent into a circle (here 0–360°).
Servers are hashed onto it (by address or name).
Keys are hashed onto the same ring.
A key belongs to the first server clockwise from it.
Lookup: binary search over the sorted server positions.

A hash ring: each key belongs to the first server clockwise from it

Each server's address is hashed to a point on a ring of 0–360°: A lands at 322°, B at 141° and C at 44°.

0:01 / 0:26Step 1 of 10

Transcript · 10 steps

Adding a server

The new server takes only the arc from its predecessor up to itself.
Keys on that arc move to it; no other key moves.
Expected keys moved: about K / N, not most of K.

Adding a server: the ring moves one arc of keys, mod N moves most of them

Three servers and 8 keys, each key stored on the first server clockwise from it. Now the pool grows: server D is added.

0:01 / 0:16Step 1 of 5

Transcript · 5 steps

Removing a server

The server's arc joins its clockwise neighbour's.
Only the removed server's keys move, all to that neighbour.
mod N, by contrast, reshuffles keys that were never on it.

Removing a server: only its own keys move, to the next server clockwise

The same ring: A, B and C share 8 keys. Now server B fails and has to leave the pool.

0:01 / 0:11Step 1 of 4

Transcript · 4 steps

Virtual nodes

One point per server leaves arcs as uneven as the hashes fall.
Give each server many points (A#0, A#1, …): small arcs average out.
Bonus: a failed server's keys scatter over many servers, not one.
Weighted capacity: a bigger server gets more virtual nodes.

Virtual nodes: many points per server even out the load

With one point per server, the arcs are as uneven as the hashes fall: C owns the arc before it, 68% of the whole ring.

0:01 / 0:16Step 1 of 5

Transcript · 5 steps

Ring vs mod N

	mod N	Hash ring
Lookup	O(1) arithmetic	O(log S) binary search
Keys moved on a change	Most of them	About K / N
Balance	Even	Even with virtual nodes
State needed	N	Sorted server positions

In practice

Replication: store a key on the next R distinct servers clockwise, not just the first.
Hot keys are not fixed by the ring; one popular key still lands on one server.
Alternatives with the same goal: rendezvous (highest random weight) hashing, jump consistent hash.

Interview questions

Why does mod N fail when scaling? Changing N changes almost every key's server, so data or cache entries move en masse.
How many keys move when a server joins the ring? About K / N, only those on the new server's arc.
Why use virtual nodes? To even out load and to spread a failed server's keys across many servers.
How do you find a key's server fast? Binary search the sorted ring positions for the first one at or after the key's hash, wrapping to the start.

Next: Message Queues · Before this: CAP Theorem

Common questions

Why not use hash(key) mod N?

Because the result depends on N. When a server is added or removed, N changes and most keys map to a different server; going from 3 to 4 servers moves about three quarters of them. For a cache that means a flood of misses; for a datastore, a mass migration.

How does a lookup work on the ring?

Hash the key to a position, then find the first server position clockwise from it, wrapping past the top. Keeping server positions in a sorted array makes this one binary search, O(log S) for S points on the ring.

What happens when a server is added?

The new server takes over the arc between the previous server and itself. Only the keys on that arc move, and they all move to the new server; every other key stays where it was.

What are virtual nodes?

Each physical server is placed on the ring many times, at hash(server#0), hash(server#1) and so on. Many small arcs average out the luck of where single points land, so load is far more even, and a leaving server's keys spread over many servers instead of one neighbour.

Where is consistent hashing used?

In distributed caches and key-value stores to decide which node owns a key (Amazon's Dynamo design and Apache Cassandra use ring-based partitioning), in client-side sharding for memcached, and in load balancers that need sticky routing that survives pool changes.

Consistent Hashing in System Design, Animated

Consistent hashing for system design interviews: the hash ring, adding and removing servers, keys moved versus mod N, and virtual nodes, shown as animations.

Subject: System Design
Level: Intermediate
Reading time: 6 min
Updated: 2026-10-29

What is consistent hashing?

Sharding needs a rule for which server owns a key. Consistent hashing is a rule that barely changes when the set of servers does.

The problem with mod N

server = hash(key) mod N spreads keys evenly, but depends on N.
Add or remove one server and most keys get a new home.
From 3 to 4 servers about 3 in 4 keys move (a key stays only if h mod 3 = h mod 4).
For a cache that is a stampede of misses at once.

The hash ring

Hash space bent into a circle (here 0–360°).
Servers are hashed onto it (by address or name).
Keys are hashed onto the same ring.
A key belongs to the first server clockwise from it.
Lookup: binary search over the sorted server positions.

A hash ring: each key belongs to the first server clockwise from it.

Each server's address is hashed to a point on a ring of 0–360°: A lands at 322°, B at 141° and C at 44°.
user:62 hashes to 65°. Walking clockwise from there, the first server it meets is B, so B stores it.
user:63 hashes to 295°. Walking clockwise from there, the first server it meets is A, so A stores it.
user:66 hashes to 124°. Walking clockwise from there, the first server it meets is B, so B stores it.
user:68 hashes to 255°. Walking clockwise from there, the first server it meets is A, so A stores it.
user:69 hashes to 353°. Walking clockwise from there, the first server it meets is C, so C stores it.
user:70 hashes to 17°. Walking clockwise from there, the first server it meets is C, so C stores it.
user:74 hashes to 170°. Walking clockwise from there, the first server it meets is A, so A stores it.
user:79 hashes to 78°. Walking clockwise from there, the first server it meets is B, so B stores it.
All 8 keys placed: A holds 3, B holds 3, C holds 2. A lookup needs only the sorted server positions and one binary search.

Adding a server

The new server takes only the arc from its predecessor up to itself.
Keys on that arc move to it; no other key moves.
Expected keys moved: about K / N, not most of K.

Adding a server: the ring moves one arc of keys, mod N moves most of them.

Three servers and 8 keys, each key stored on the first server clockwise from it. Now the pool grows: server D is added.
D hashes to 102°, between C and the next server. It takes over only the arc from C (44°) up to itself; every other arc is untouched.
Only the keys on that arc move: 2 of 8 (user:62, user:79), all from B to D. No other server's keys change hands.
Compare plain modulo hashing, server = hash(key) mod N: with three servers each key's index is hash mod 3. The 2 keys the ring moved are highlighted.
Adding D makes it hash mod 4, and 8 of 8 keys change server (red). On average mod N moves 75% of keys going from 3 to 4; the ring moves only the new arc's share.

Removing a server

The server's arc joins its clockwise neighbour's.
Only the removed server's keys move, all to that neighbour.
mod N, by contrast, reshuffles keys that were never on it.

Removing a server: only its own keys move, to the next server clockwise.

The same ring: A, B and C share 8 keys. Now server B fails and has to leave the pool.
B owned the arc from C (44°) to itself (141°), holding 3 keys. Those keys now have no server.
Each of B's keys keeps walking clockwise and reaches A, so 3 keys move, all to A. A's arc now runs from C to itself; no other key moves.
With mod N, losing B turns hash mod 3 into hash mod 2: 6 of 8 keys change server (red), including keys that were never on B.

Virtual nodes

One point per server leaves arcs as uneven as the hashes fall.
Give each server many points (A#0, A#1, …): small arcs average out.
Bonus: a failed server's keys scatter over many servers, not one.
Weighted capacity: a bigger server gets more virtual nodes.

Virtual nodes: many points per server even out the load.

With one point per server, the arcs are as uneven as the hashes fall: C owns the arc before it, 68% of the whole ring.
Hash 1200 keys onto the ring and C stores 815 of them, against 280 and 105 for the others: 7.8× between busiest and idlest.
Give each server 4 virtual nodes (hash "C#0", "C#1", …). C's share is now 4 smaller arcs scattered round the ring, and the counts are 563 / 438 / 199.
At 16 points per server C's arcs are short and spread all round the ring: 368 / 470 / 362 keys, 1.30× between busiest and idlest.
At 64 points each: 406 / 371 / 423, within 1.14×. More points per server gives smaller, more even arcs, and a leaving server's keys scatter over many neighbours instead of one.

Ring vs mod N

	mod N	Hash ring
Lookup	O(1) arithmetic	O(log S) binary search
Keys moved on a change	Most of them	About K / N
Balance	Even	Even with virtual nodes
State needed	N	Sorted server positions

In practice

Replication: store a key on the next R distinct servers clockwise, not just the first.
Hot keys are not fixed by the ring; one popular key still lands on one server.
Alternatives with the same goal: rendezvous (highest random weight) hashing, jump consistent hash.

Interview questions

Why does mod N fail when scaling? Changing N changes almost every key's server, so data or cache entries move en masse.
How many keys move when a server joins the ring? About K / N, only those on the new server's arc.
Why use virtual nodes? To even out load and to spread a failed server's keys across many servers.
How do you find a key's server fast? Binary search the sorted ring positions for the first one at or after the key's hash, wrapping to the start.

Next: Message Queues · Before this: CAP Theorem

Common questions

Why not use hash(key) mod N?

How does a lookup work on the ring?

What happens when a server is added?

The new server takes over the arc between the previous server and itself. Only the keys on that arc move, and they all move to the new server; every other key stays where it was.

What are virtual nodes?

Where is consistent hashing used?

← CAP Theorem · Message Queues →