Skip to content
learn
  1. Learn
  2. High Level System Design
  3. Scaling Data

System Design HLD-07.05

Consistent hashing

Learn how a hash ring lets you add or remove servers while moving only a small slice of your data, and why virtual nodes keep it balanced.

Intermediate 15 min Last reviewed

The big idea

You run a cache cluster with 4 servers. Every key goes to a server picked by hash(key) % 4. It works perfectly until traffic grows and you add a 5th server. Now the formula is hash(key) % 5, and for almost every key the answer changes. In one deploy, roughly 80 percent of your cache becomes useless, every miss falls through to the database, and the database falls over. This is called a cache avalancheA burst of cache misses that overloads the backing store, often after a mass invalidation or a cluster change., and it is a classic outage.

Consistent hashing fixes this. Instead of dividing by the number of servers, it places both servers and keys on the same circle and lets each key walk clockwise to the nearest server. Add a server and it only takes over the keys in its own small arc. Everything else stays where it was.

Think of a circular running track with water stations. Each runner drinks at the next station ahead of them. Add one new station and only the runners just behind it change where they drink. Nobody on the rest of the track notices.

How it works

Step 1: Why modulo hashing breaks

With N servers, server = hash(key) % N. The output depends on N, so changing N reshuffles nearly everything. Going from N to N + 1, a key keeps its server only when hash % N == hash % (N + 1), which happens for about 1 / (N + 1) of keys. From 4 to 5 servers, only about 20 percent of keys stay put.

Modulo hashing versus a hash ring when adding a fifth server Twelve keys are assigned to four servers, then a fifth server is added. With modulo hashing 10 of 12 keys change server. With a consistent hashing ring 3 of 12 change, all of them to the new server s4. hash(key) % N hash ring (50 vnodes each) key4 servers5 servers key4 servers5 servers user:100 s1 s3 moved user:100 s2 s4 moved user:107 s2 s0 moved user:107 s2 s2 user:114 s1 s0 moved user:114 s3 s3 user:121 s1 s4 moved user:121 s1 s1 user:128 s0 s3 moved user:128 s2 s4 moved user:135 s3 s3 user:135 s1 s1 user:142 s2 s2 user:142 s3 s3 user:149 s1 s3 moved user:149 s3 s4 moved user:156 s0 s3 moved user:156 s0 s0 user:163 s3 s2 moved user:163 s3 s3 user:170 s0 s1 moved user:170 s3 s3 user:177 s0 s2 moved user:177 s3 s3 10 of 12 keys moved 3 of 12 keys moved, all to s4 Figure 1. Same 12 keys, 4 to 5 servers. Left: modulo hashing moves most keys (red). Right: the ring moves only the keys in the new server's arcs, all to the new server (green).

Step 2: Put everything on a ring

Pick a hash function with a large output space, for example 32 bits, so outputs run from 0 to 2^32 - 1. Bend that range into a circle so the largest value wraps back to 0. Now:

  1. Hash each server's name (hash("cache-a")) to get its position on the ring.
  2. Hash each key (hash("user:42")) to get its position on the same ring.
  3. A key belongs to the first server you hit walking clockwise from the key's position. That server is the key's ownerThe node responsible for storing or serving a key..

Looking up an owner is a binary search over the sorted list of server positions: O(log S) for S positions. That is fast enough to do on every request.

Adding node E to a consistent hashing ring A ring with nodes A, B, C and D and fourteen keys. Node E joins between D and A. Only the keys on the arc between D and E move, from A to E; they glow green. All other keys stay with their owners. A B C D E keys walk clockwise to the next node Before: 4 nodes keys between D and A belong to A E joins between D and A E takes the keys in its arc only 3 of 14 keys move all moves are from A to E; B, C and D are untouched Figure 2. Adding node E only steals the arc between D and E. Glowing green keys move to E; every grey key stays where it was.

Step 3: Adding and removing a server

When server E joins between D and A, E takes only the keys that sit between D and E, which used to belong to A. With N servers spread evenly, that is about 1/N of all keys. When a server leaves, its keys move to the next server clockwise, again about 1/N. Compare that with modulo hashing, where almost every key moves.

Step 4: Virtual nodes fix the imbalance

With only a handful of servers, random positions are lumpy. One server might own 40 percent of the ring and another 10 percent. Worse, when a server dies, all of its load lands on a single neighbour, which may then also die.

The fix is virtual nodesMany positions on the ring for one physical server, created by hashing names like cache-a#0, cache-a#1, and so on. (vnodes). Each physical server is hashed many times (cache-a#0, cache-a#1, ... cache-a#199) and appears at 100 to 200 points around the ring. Now each server owns many small arcs instead of one big one:

  • Load evens out, because many small random arcs average out.
  • When a server dies, its many small arcs are spread across many different neighbours, so no single server takes the whole hit.
  • Bigger machines can get more vnodes, so they own a proportionally larger share. This is a simple way to do weighted capacity.

The cost is memory for the ring table (servers x vnodes entries) and slightly more work when membership changes. Both are tiny compared to the benefit.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. Start with 4 nodes and 1 vnode each. Add a node. Count how many keys flash: it should be roughly one quarter or less.
  2. Switch the mode to "modulo" and add a node again. Watch most of the keys move.
  3. Set vnodes to 1 and look at the load bars. Then set vnodes to 100. See how the bars flatten out.

Going deeper

A tiny implementation

ring.pyruns with python3 (standard library)
import bisect, hashlib

def h(s: str) -> int:
    # Stable 32-bit hash. Never use Python's built-in hash(): it is randomized per process.
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:4], "big")

class Ring:
    def __init__(self, vnodes: int = 100):
        self.vnodes, self.points, self.owner = vnodes, [], {}

    def add(self, node: str):
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            bisect.insort(self.points, p)
            self.owner[p] = node

    def remove(self, node: str):
        for i in range(self.vnodes):
            p = h(f"{node}#{i}")
            self.points.remove(p)
            del self.owner[p]

    def get(self, key: str) -> str:
        i = bisect.bisect(self.points, h(key)) % len(self.points)  # wrap around
        return self.owner[self.points[i]]

keys = [f"user:{i}" for i in range(10_000)]
ring = Ring(vnodes=100)
for n in ["cache-a", "cache-b", "cache-c", "cache-d"]:
    ring.add(n)
before = {k: ring.get(k) for k in keys}

ring.add("cache-e")
after = {k: ring.get(k) for k in keys}
moved = sum(before[k] != after[k] for k in keys)
print(f"ring, 4 -> 5 nodes:   {moved / len(keys):.0%} of keys moved, all to "
      f"{set(after[k] for k in keys if before[k] != after[k])}")

modulo_moved = sum(h(k) % 4 != h(k) % 5 for k in keys)
print(f"modulo, 4 -> 5 nodes: {modulo_moved / len(keys):.0%} of keys moved")

load = {n: list(after.values()).count(n) for n in sorted(set(after.values()))}
print("keys per node with 100 vnodes:", load)

Output

ring, 4 -> 5 nodes:   19% of keys moved, all to {'cache-e'}
modulo, 4 -> 5 nodes: 80% of keys moved
keys per node with 100 vnodes: {'cache-a': 2372, 'cache-b': 1530, 'cache-c': 2109, 'cache-d': 2106, 'cache-e': 1883}

Forty lines including a test: 10,000 keys, four nodes with 100 virtual nodes each, then a fifth node joins. About a fifth of the keys move, every one of them to the new node, while modulo hashing would move four fifths. Even with 100 vnodes the spread is not perfect; more vnodes, or capacity-aware weights, tighten it further.

Replication on the ring

To keep R copies of each key, walk clockwise from the key and take the first R distinct physical servers (skip vnodes that belong to a server you already picked). This list is called the preference listThe ordered list of nodes that store copies of a key.. It is exactly how Amazon's Dynamo and Apache Cassandra place replicas, and it combines with the quorum reads and writes from Multi-leader and leaderless replication .

Hot keys still hurt

Consistent hashing balances the number of keys, not the traffic per key. If one key is a celebrity profile getting 50,000 reads per second, the server that owns it is still overloaded. You need extra techniques from Hot partitions and the celebrity problem and Thundering herd, cache stampede and hot keys : replicate hot keys, add a local in-process cache, or split the key.

Alternatives worth knowing

  • Rendezvous (highest random weight) hashing: for each key, score every server with hash(key, server) and pick the highest. No ring and no vnodes, perfect balance, but lookup is O(N).
  • Jump consistent hash: a tiny algorithm that maps a key to one of N numbered buckets with minimal movement. Great when servers are numbered 0..N-1 and only added or removed at the end.
  • Fixed hash slots: Redis Cluster pre-splits the space into 16,384 slots and assigns slots to nodes. Moving a slot is an explicit operation, which makes rebalancing predictable.

Trade-offs

OptionWins whenLoses when
Modulo hashing Fixed number of servers that never changes; simplest possible code Any resize moves most keys, causing cache avalanches or massive data migration
Ring with vnodes Servers come and go often; you want about 1/N movement and smooth load Slightly more memory and code; hot keys still need separate handling
Rendezvous hashing Small clusters where perfect balance matters and O(N) lookup is cheap Lookup cost grows with cluster size
Fixed slots (Redis Cluster) You want explicit, operator-controlled rebalancing Needs a slot map shared by all clients and a migration process

Common mistakes

  • Using a language's built-in randomized hash (Python hash(), Java Object.hashCode on some types) so different processes disagree about owners.
  • Running with one position per server and wondering why one node is twice as busy as another.
  • Forgetting that removing a server dumps its keys on the next one clockwise; without vnodes that neighbour can cascade-fail.
  • Assuming consistent hashing solves hot keys. It balances key count, not request rate.
  • Moving data before the new node is ready: always warm the new node (or copy its arc) before switching traffic.

In the wild

Amazon

Dynamo: Amazon's highly available key-value store (opens in a new tab)

The Dynamo paper describes partitioning data with consistent hashing, using virtual nodes to spread load and to let machines of different capacity take different shares, and replicating each key to the next N nodes on the ring. It is the design many later databases, including Cassandra, borrowed.

Discord

How Discord stores trillions of messages (opens in a new tab)

Bo Ingram's 2023 post describes Discord's message store, partitioned by channel and time bucket, and its hot partition problem: a server with hundreds of thousands of members sends orders of magnitude more messages than a small group, and one busy channel could drive up latency on the node holding it. Discord put data services written in Rust in front of the database that route requests by consistent hashing on the channel id, so requests for the same channel reach the same service instance, where concurrent identical reads are coalesced into one database query. It then migrated from 177 Cassandra nodes to 72 ScyllaDB nodes, with p99 latency for fetching messages falling from 40 to 125 ms to 15 ms.

Check yourself

  1. You have 4 cache servers using hash(key) % 4 and you add a 5th. About how many keys stay on the same server?

    Show answer

    B. About 20 percent A key stays only if hash % 4 equals hash % 5, which holds for roughly 1 in 5 keys. That is why modulo hashing causes a cache avalanche on resize.

  2. On a consistent hashing ring with 10 evenly spread servers, one server is removed. Roughly what share of keys move?

    Show answer

    C. About 10 percent Only the keys owned by the removed server move, to the next server clockwise. That is about 1/N = 10 percent.

  3. Why do production rings give each server 100 or more virtual nodes?

    Show answer

    B. To spread load evenly and spread a failed server's keys across many neighbours Many small arcs average out the randomness of positions and mean a failure is absorbed by many servers instead of one.

  4. One key gets 50,000 reads per second and overloads its owner. Which change helps most?

    Show answer

    C. Replicate or locally cache that hot key Consistent hashing balances key counts, not per-key traffic. A hot key needs replication, local caching or splitting.

Recap

  • Modulo hashing moves almost every key when the server count changes; consistent hashing moves only about 1/N.
  • Servers and keys share one ring; a key belongs to the first server clockwise from it.
  • Virtual nodes give each server many small arcs, which evens out load and spreads failures.
  • Walking clockwise to the next R distinct servers gives you replica placement for free.
  • It balances keys, not traffic: hot keys still need their own fix.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up