Consistent Hashing

Consistent hashing places servers and keys on a ring, so adding or removing a server only moves the keys next to it — not almost all of them, as hash % N does.

The ring

0°90°180°270°ABC

Key → server

  • user:1B
  • user:2A
  • user:3B
  • cart:9C
  • order:4C
  • img:7A
  • post:5C
  • tag:2B
  • feed:8B
  • msg:6C
  • Moved in this step

Hash every key to a point on a circle (0–359); servers sit on the circle too. A key belongs to the first server clockwise from it. (Server points are fixed here so the arcs are easy to see.)

Step 1 / 8
Servers
3
Keys moved
0

Step by step

The example above, written out — the same steps the animation plays.

  1. 1The ring. Hash every key to a point on a circle (0–359); servers sit on the circle too. A key belongs to the first server clockwise from it. (Server points are fixed here so the arcs are easy to see.)
  2. 2user:1 → B. user:1 hashes to 187°; walking clockwise, the first server is B.
  3. 3user:2 → A. user:2 hashes to 6°; walking clockwise, the first server is A.
  4. 4user:3 → B. user:3 hashes to 185°; walking clockwise, the first server is B.
  5. 5Every key placed. Each server owns the arc just before it.
  6. 6Add server D. D lands at 180°. Only the keys on the arc just before D move to it: 2 of 10 (tag:2, feed:8). With hash % N, going from 3 to 4 servers would move 8 of 10.
  7. 7Server B leaves. B's keys move to the next server clockwise; nothing else changes: 2 moved.
  8. 8Done. Real systems (Cassandra, DynamoDB, CDNs) give each server many virtual points on the ring so the arcs — and the load — even out.

What's happening?

  1. Every key is hashed to a point on a circle; servers sit on the circle too.
  2. A key belongs to the first server clockwise from it.
  3. A new server only takes over the arc just before it; a departing server hands its arc to the next one.

Complexity

Time
O(log N) to find a key's server (binary search over the ring)
Space
O(N × virtual nodes)

Where you'll meet it

Distributed caches (Memcached clients), databases like Cassandra and DynamoDB, CDNs and load balancers that need the same client to reach the same server.

Common mistake

Using a single point per server: arcs end up very uneven. Real systems give each server many virtual points.

FAQ

Why does hash % N move so many keys?

Changing N changes the result for almost every key — here 8 of 10 would move from 3 to 4 servers, against 2 on the ring.

What are virtual nodes?

Each server is placed at many points on the ring, which evens out the arcs and spreads a departing server's keys over many others.

Are the positions here real hashes?

The keys are (FNV-1a). The server points are fixed so the arcs are easy to see.