← System Design
Building Blocks

Consistent Hashing

Watch: "Consistent Hashing: Easy Explanation for System Design Interviews" — Hello Interview

Consistent hashing is a way of assigning keys to servers so that adding or removing a server moves only a small fraction of the keys. It is what lets distributed caches, key-value stores (Dynamo, Cassandra) and sharded databases grow and shrink without reshuffling all their data.

In simple words

Seats around a round table with guests (keys) sitting between hosts (servers); each guest is served by the next host clockwise. When a new host sits down, only the guests right before them change hosts. Everyone else keeps their host.

Adding a node moves only one arc of keyskey 'user42'hash → ringpositionServer S2New server S5Server S3next clockwisesome keys move
Keys go to the next server clockwise; a new server S5 takes over only the keys between S2 and S5.

Deep Dive: Why hash(key) % N Breaks

N = 4 servers:  server = hash(key) % 4
N = 5 servers:  server = hash(key) % 5

For a key to stay put, hash % 4 must equal hash % 5 -> true for only ~1/5
of keys. Adding ONE server moves ~80% of all keys.

For a cache: ~80% misses at once -> stampede on the database.
For a database: ~80% of the data has to be copied between machines.

Deep Dive: The Hash Ring

Hash both servers and keys onto the same circle (0 .. 2^32-1).
A key belongs to the first server clockwise from it.

                0
          S1 *     * k1 -> S2
       k4 *            * S2
     S4 *                 * k2 -> S3
          * k3 -> S4   * S3

Add S5 between S2 and S3: only keys in (S2, S5] move from S3 to S5.
Remove S3: only S3's keys move, to the next server clockwise.
On average only K/N keys move (K keys, N servers).

Deep Dive: Virtual Nodes

With a few servers placed at random points, arcs are uneven, so some servers own far more keys than others, and when one leaves, all its load dumps onto a single neighbour. The fix is virtual nodes: each physical server is hashed to many points on the ring (e.g. 100–200). Load evens out statistically, a departing server's keys spread across many servers, and a bigger machine can simply get more virtual nodes.

class Ring:
    def __init__(self, vnodes=150):
        self.vnodes, self.points, self.owner = vnodes, [], {}
    def add(self, server):
        for i in range(self.vnodes):
            h = hash64(f"{server}#{i}")
            bisect.insort(self.points, h); self.owner[h] = server
    def remove(self, server):
        for i in range(self.vnodes):
            h = hash64(f"{server}#{i}")
            self.points.remove(h); del self.owner[h]
    def lookup(self, key):
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owner[self.points[i]]      # O(log V) with binary search

For replication, a key is stored on the first R distinct physical servers clockwise (its "preference list"), which is how Dynamo-style stores place replicas.

Key Pointers

How It Works

  1. Hash each server's virtual node ids onto a ring and keep the positions sorted.
  2. To place a key, hash it and walk clockwise to the first position; that position's server owns it.
  3. For R replicas, keep walking until R distinct physical servers are found.
  4. On membership change, only keys in the affected arcs move; stream them in the background.

Follow-up Questions

Where is consistent hashing used in practice?
Distributed caches (client-side sharding for Memcached), Dynamo-style databases (Cassandra, Riak, DynamoDB's partitioning ideas), load balancers that need key affinity, and CDNs routing objects to cache servers.
Redis Cluster doesn't use a ring. Why is it still "consistent"?
Keys hash to one of 16,384 fixed slots, and slots are assigned to nodes. Adding a node moves some slots, not all keys; the slot table plays the role of the ring's arcs.
How do you handle a hot key?
Consistent hashing can't. Replicate the hot key to several nodes (read from any), add a local in-process cache, or split the key (key#1..key#k) and aggregate.

Trade-offs

You gain cheap scaling and smooth failure handling at the cost of a routing layer (every client or router must know the ring) and some complexity in rebalancing. Load is only statistically even, so monitor per-node load and adjust vnode counts.

Related