Low Level Design: Consistent Hashing

By /

Consistent hashing solves the data redistribution problem in distributed systems. With naive modulo hashing (key % N), adding or removing a server requires remapping nearly all keys. Consistent hashing maps both servers and keys onto a virtual ring, so adding or removing a server only redistributes keys that were assigned to that server — O(K/N) keys instead of O(K). This makes consistent hashing fundamental to distributed caches (Memcached, Redis Cluster), DHTs (Chord, DynamoDB), and load balancers.

The Hash Ring

The hash ring maps hash values from 0 to 2^32 – 1 arranged in a circle. Both servers and keys are hashed to positions on this ring. To find which server owns a key: hash the key, walk clockwise on the ring to find the first server position. When a server is added, it takes ownership of keys between its predecessor and its own position. When a server is removed, its keys transfer to the next server clockwise. Only 1/N of all keys need remapping on each add/remove operation.

type ConsistentHash struct {
    ring     map[uint32]string   // hash position -> server ID
    sorted   []uint32            // sorted hash positions
    replicas int                 // virtual nodes per server
}

func (ch *ConsistentHash) AddServer(server string) {
    for i := 0; i < ch.replicas; i++ {
        key := fmt.Sprintf("%s:%d", server, i)
        hash := crc32.ChecksumIEEE([]byte(key))
        ch.ring[hash] = server
        ch.sorted = append(ch.sorted, hash)
    }
    sort.Slice(ch.sorted, func(i, j int) bool { return ch.sorted[i] = hash
    idx := sort.Search(len(ch.sorted), func(i int) bool { return ch.sorted[i] >= hash })
    if idx == len(ch.sorted) { idx = 0 }  // wrap around
    return ch.ring[ch.sorted[idx]]
}

Virtual Nodes for Load Balancing

With few physical servers, hash positions cluster unevenly on the ring, causing hot spots (one server gets 60% of keys). Virtual nodes solve this: each physical server is assigned V positions on the ring (e.g., V=150). Keys distribute across V×N positions, averaging out to even load. When a server with more capacity is added (a larger machine), give it more virtual nodes (proportional to capacity). DynamoDB uses 150 virtual nodes per physical node. The trade-off: memory for the ring metadata grows with V×N, but this is manageable.

Replication with Preference Lists

For fault tolerance, data is replicated to the next R servers clockwise on the ring (skipping virtual nodes of the same physical server). This is the preference list. For a key owned by server A, it is also stored on servers B and C (the next two distinct physical servers clockwise). Reads and writes can be sent to any replica using quorum: write to W replicas, read from R replicas, where W + R > N ensures at least one overlap. DynamoDB and Cassandra use N=3, W=2, R=2 as their default quorum.

Rendezvous Hashing: An Alternative

Rendezvous hashing (highest random weight hashing) is simpler: for a key, compute a hash score for each server (hash(key + server_id)), assign the key to the server with the highest score. When a server is added/removed, only keys that would have been assigned to it change. No ring data structure needed. Drawback: O(N) per lookup vs. O(log N) for ring-based consistent hashing. For small N (≤ 50 servers), rendezvous hashing is simpler and equally effective.

Key Interview Discussion Points

  • Why modulo hashing fails: adding one server remaps K×(N-1)/N keys — nearly all keys change servers, defeating caching
  • Virtual node count tuning: too few and load is uneven; too many and ring metadata grows large
  • Hotspot keys: even with consistent hashing, viral content creates hotspots — add a random suffix to key and fan out reads across multiple positions
  • Bounded load: Google extension to consistent hashing that limits maximum load per server to (1 + epsilon) times the average load
  • Jump consistent hash: Google algorithm producing uniform results with O(1) space and O(ln N) time, but no virtual nodes
Scroll to Top