The Catastrophic Cache Miss

Memcached at Facebook in the early days used simple modulo hashing: server = hash(key) % N. With 100 cache servers, adding one more server (N becomes 101) caused 99% of keys to remap to different servers. In an instant, their cache hit rate dropped to nearly zero. Every request hit the database. The database buckled. Consistent hashing was the fix - adding a server only moves ~1% of keys.

The Problem with Modulo Hashing

Simple modulo: server = hash(key) % N

With 4 servers (N=4):
  hash('user:42') = 17  --> 17 % 4 = 1  --> Server B
  hash('user:73') = 26  --> 26 % 4 = 2  --> Server C
  hash('user:99') = 11  --> 11 % 4 = 3  --> Server D

Now add Server E (N=5):
  hash('user:42') = 17  --> 17 % 5 = 2  --> Server C  (MOVED!)
  hash('user:73') = 26  --> 26 % 5 = 1  --> Server B  (MOVED!)
  hash('user:99') = 11  --> 11 % 5 = 1  --> Server B  (MOVED!)

Result: ~80% of keys remapped! Massive cache miss storm.
        Database gets hammered. Potential cascading failure.

The Hash Ring Solution

Consistent Hashing Ring (0 to 2^32):

           0
          /|\
         / | \
     S_A  key1  S_B
     /     |       \
    /      |        \
   /       |         \
  S_D   (ring)     S_C
   \       |        /
    \      |       /
     \     |      /
      key2 | key3
         \ | /
          \|/
         2^32

  Rules:
  1. Hash each server to a point on the ring
  2. Hash each key to a point on the ring
  3. Walk clockwise from key's position
  4. First server you hit = that key's home

  Adding Server E:
  - E lands between S_A and S_B on the ring
  - Only keys between S_A and E move to E
  - All other keys stay on their current server
  - Only ~1/N keys move (1/5 = 20%, not 80%!)

Virtual Nodes: Even Distribution

With only a few physical servers on the ring, distribution can be uneven. One server might own 40% of the ring by bad luck of hash placement. Virtual nodes fix this:

Without virtual nodes (uneven):
  Server A: owns 15% of ring
  Server B: owns 40% of ring  <-- overloaded!
  Server C: owns 20% of ring
  Server D: owns 25% of ring

With virtual nodes (100 vnodes per server):
  Server A: 100 points scattered on ring --> owns ~25%
  Server B: 100 points scattered on ring --> owns ~25%
  Server C: 100 points scattered on ring --> owns ~25%
  Server D: 100 points scattered on ring --> owns ~25%

  More vnodes = more even distribution.
  Cassandra uses 256 vnodes per physical node by default.

Who Uses Consistent Hashing

System             How They Use It
-----------------  ------------------------------------------
Amazon DynamoDB    Partition data across storage nodes
Apache Cassandra   Assign token ranges to cluster nodes
Redis Cluster      Distribute 16384 hash slots across nodes
Memcached clients  Route keys to cache servers
CDNs (Akamai)      Assign content to edge servers
Discord            Route users to the right voice server
Load balancers     Sticky routing to backend servers

Traditional Hashing vs Consistent Hashing

Interview Tip

Consistent hashing comes up in nearly every system design interview that involves distributed data. Say: 'I would use consistent hashing with virtual nodes to distribute data across servers. When we add a new server, only 1/N of keys are remapped instead of reshuffling everything. Each physical server gets 100-200 virtual nodes on the hash ring for even distribution. This is the same approach used by DynamoDB, Cassandra, and Redis Cluster.'

Key Takeaway

Consistent hashing maps both keys and servers onto a ring. Adding or removing a server only affects 1/N of keys instead of all of them. Virtual nodes ensure even distribution. This is the foundation of virtually every distributed storage and caching system.