Consistent Hashing

A cache cluster has 4 nodes holding 10 million keys and serves 50,000 reads a second. 95% are hits, so the database sees 50,000 × 0.05 = 2,500 reads a second. Each key's node is chosen with hash(key) mod 4. Traffic grows, so someone adds a fifth node and the code switches to mod 5.

A key stays on the same node only if its hash leaves the same remainder for 4 and 5, which happens for 4 values in every 20. So 80% of keys now point at a node that does not have them. The hit rate falls to about 0.95 × 0.2 = 19%, and the database goes from 2,500 to 50,000 × 0.81 = 40,500 reads a second. Adding capacity caused the outage.

#The idea

Consistent hashing places keys so that when a node joins or leaves, only about 1/N of them move, not almost all. Going from 4 to 5 nodes, the new node takes its fair share of 10 million ÷ 5 = 2 million keys, and every other key stays where it was.

It fits wherever keys spread over a changing set of machines: cache clusters, partitioned key-value stores, sticky load balancing. The cost is a little bookkeeping in every client.

#The ring

Hash every server name and every key into the same range of numbers, and bend that range into a circle. Real rings use 0 to 2³² − 1 or more; to trace by hand, use 0 to 99. A key belongs to the first server clockwise from its position, wrapping past 99 to 0.

Each arrow points from a key to its owner. Watch what moves when a server joins, then leaves.

#Virtual nodes

The fix is to give each server many points on the ring, called virtual nodes: hash "A#0", "A#1", up to "A#99". Each server owns 100 small scattered arcs instead of one big one. Three things improve:

• Even shares. A server's share is the sum of many random arcs, so its deviation from the average shrinks roughly as 1 ÷ √v for v points each: about 10% at 100 points.
• Even recovery. When a server leaves, each of its 100 arcs goes to a different neighbour, so its load spreads over all the others instead of landing on one.
• Weights. A server with twice the memory gets 200 points and about twice the keys.

A lookup is a binary search in the sorted list of points: the first point at or after the key's hash, wrapping to the start. The hash must mix its input well (here, the first 32 bits of MD5); a hash that mixes poorly can bunch the points of similar names like "A#0" and "A#1",. If hashing itself is new, see hash tables.

const crypto = require("crypto");
 
function hash(s) {                           // first 32 bits of MD5
  return parseInt(crypto.createHash("md5").update(s).digest("hex").slice(0, 8), 16);
}
 
class Ring {
  constructor(vnodes = 100) {
    this.vnodes = vnodes;
    this.points = [];                        // [position, node], sorted
  }
  add(node) {
    for (let i = 0; i < this.vnodes; i++) this.points.push([hash(`${node}#${i}`), node]);
    this.points.sort((a, b) => a[0] - b[0]);
  }
  remove(node) {
    this.points = this.points.filter(([, n]) => n !== node);
  }
  lookup(key) {
    const h = hash(key);
    let lo = 0, hi = this.points.length;     // first point at or after h
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid][0] < h) lo = mid + 1; else hi = mid;
    }
    return this.points[lo % this.points.length][1];  // past the end: wrap to 0
  }
}

import bisect
import hashlib
 
def ring_hash(s):
    # first 32 bits of MD5
    return int(hashlib.md5(s.encode()).hexdigest()[:8], 16)
 
class Ring:
    def __init__(self, vnodes=100):
        self.vnodes = vnodes
        self.points = []                    # (position, node), sorted
 
    def add(self, node):
        for i in range(self.vnodes):
            bisect.insort(self.points, (ring_hash(f"{node}#{i}"), node))
 
    def remove(self, node):
        self.points = [p for p in self.points if p[1] != node]
 
    def lookup(self, key):
        # first point at or after the key's hash; past the end: wrap to 0
        i = bisect.bisect_left(self.points, (ring_hash(key), ""))
        return self.points[i % len(self.points)][1]

#When a cache node dies

Back to the 4-node cache cluster, now on a ring with 100 virtual nodes each. Every app server holds the same ring and finds a key's node.

#Other ways to place keys

#Numbers worth remembering

• Adding the (N+1)th node moves about 1/(N+1) of keys with consistent hashing; with mod N, about N/(N+1).
• Virtual nodes: 100 to 200 per server is a common range; spread shrinks as 1 ÷ √v.

#In the interview

Bring it up when keys are spread across nodes that come and go. Say the problem it solves in numbers, then mention virtual nodes.

Follow-ups you should expect:

• "How do clients agree on the ring?" Membership comes from a configuration service or gossip. During a change clients briefly disagree, so a few requests miss.
• "How does replication fit?" Store each key on the next 3 distinct servers clockwise, skipping extra points of a server already chosen.

#Common mistakes

#What to practise next

Next in this module, blob storage moves from rows to large files. A ring with replication is the core of Design a Key-Value Store.