DSA & System Design
All the basics

What is consistent hashing?

It matches keys to servers so that adding or removing a server moves only a small share of the keys.

Servers sit at spots around a clock face. Each key walks clockwise to the first server it meets.

Press Play to watch it run · 5 steps

With key mod N, adding a server reshuffles most keys. On a ring, only a small part moves, and only to the new server.

Adding a server: mod versus a ringWith key mod N, adding a server reshuffles most keys. On a ring, only a small part moves, and only to the new server.KeysServer AServer BServer CServer Dnew

Tap any box to see what it is and what it talks to.

  • Client
  • Cache
Open in playground
Text description
  1. Three cache servers share keys. Rule: key mod 3. Key 42 goes to Server A.
  2. Traffic grows, so Server D is added. The rule becomes key mod 4.
  3. Key 42 now maps to Server C, because 42 mod 4 is 2.
  4. About three keys in four change servers, so most lookups miss.
  5. With 100 servers, adding one still moves about 99 keys in 100.
  • Plain key mod N reshuffles almost every key when N changes.
  • On a ring, a new server takes keys only from its neighbour.
  • So adding or losing a server disturbs very little.

Reach for it when

When keys are spread over servers that come and go, like a 20-node cache. A fixed server count can use plain mod.

The catch

With few spots on the ring, one server can own a huge slice and melt, so each takes many spots.

Say it in an interview“I would use consistent hashing so adding or removing a node remaps only about 1/N of the keys, with virtual nodes to even out the load.”