02.5 Consistent hashing

Mid-level · Component

Core idea

When you add or remove servers, naive modulo (key % N) remaps almost all keys → massive cache miss storm or data movement. Consistent hashing ensures only K/N keys are remapped when a server is added/removed.

Mental model

Picture a clock face (hash ring). Servers are placed at positions on the ring. A key maps to the first server clockwise from its position. Add a server → only keys between the new server and its predecessor move. Remove a server → only its keys move to the next server. No global reshuffle.

Why it matters

  • Used by DynamoDB, Cassandra, Memcached, Akamai CDN
  • Solves the scaling problem of distributed caches and storage
  • Interviewers test this because it reveals distributed systems depth

What to know

  • Hash ring: 0 to 2^32 circle, servers and keys both mapped via hash function
  • Virtual nodes: each physical server gets 100+ virtual nodes — better load distribution
  • Without virtual nodes: uneven load if few servers
  • Replication with consistent hashing: replicate to next N nodes clockwise
  • Used in: distributed cache, distributed DB, load balancing, content delivery

Common traps

  • Without virtual nodes, load is highly uneven — always use virtual nodes
  • Not handling node failure — need replication factor ≥ 2
  • Hash function choice matters — poor hash → clustering

Recognise it

Recognition trigger: Any system with a dynamic cluster of caches or storage nodes → consistent hashing. Key interview signal: ‘what happens when you add a server?’ — if your answer requires moving everything, that’s wrong.

Practice question

You have a Redis cluster with 10 nodes. You need to add a node to reduce load. How do you do this without invalidating all cached keys?

Go deeper