Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 225 ยท Hashing

Consistent Hashing

Understand consistent hashing: why hash(key) % n breaks when servers change, how a hash ring moves few keys, and how virtual nodes balance the load.

Suppose you spread data over several cache servers. The obvious rule is server = hash(key) % n. It balances nicely, and it works until n changes. Add a server, or lose one, and almost every key suddenly maps somewhere else. All your caches go cold at the same moment and the database behind them is flooded. In a system that grows and shrinks, that is a disaster.

Consistent hashing fixes this. When a node joins or leaves, only about 1/n of the keys move, instead of nearly all of them. It is used by distributed caches, key-value stores such as Dynamo-style databases, load balancers and content delivery networks. In this lesson you will see the problem with modulo hashing, build a hash ring in Python, and use virtual nodes to even out the load. It builds on hash functions and hash tables, and uses binary search for lookups.

The problem with modulo

Let us measure it. We map 10,000 keys to 4 servers with hash % n, then add a fifth server and count how many keys changed server.

Python How many keys move with modulo hashing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Around 80% of the keys move, even though we only added one server out of five. The ideal is 20%: the new server should take a fair share from the others, and nobody else should shuffle.

The hash ring

Instead of dividing by n, imagine the output range of the hash function bent into a circle, from 0 up to the maximum value and then wrapping around to 0. This is the hash ring.

  1. Hash each server name onto the ring. Each server owns a position (a point on the circle).
  2. To store or find a key, hash the key onto the same ring.
  3. From the key's position, walk clockwise until you meet a server. That server is responsible for the key.
flowchart LR
    subgraph Ring["Hash ring (clockwise)"]
        direction LR
        A["server A<br/>at 100"] --> K1["key k1<br/>at 130"] --> B["server B<br/>at 200"] --> K2["key k2<br/>at 260"] --> C["server C<br/>at 320"] --> A
    end

Each key belongs to the next server clockwise: k1 goes to B, k2 goes to C, and a key at 350 would wrap around to A.

Now see what happens when server D is added at position 280. Only the keys between server B's position 200 and D's position 280 are affected, because D now sits before C for them. Keys between 280 and 320 still go to C, and everything else is untouched. When a server is removed, only its keys move, to the next server clockwise.

Implementing the ring

A sorted list of server positions plus bisect finds the next server clockwise in O(log n). If the key's position is past the last server, the index wraps around to 0.

Python A consistent hash ring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Compared with modulo hashing, far fewer keys move, and every moved key lands on the new node. That is the defining property of consistent hashing. However, the amount that moves depends on where the new node happened to land, and that brings us to the weakness of this simple ring.

Uneven load and virtual nodes

With only a handful of points on the circle, the gaps between servers are random and often very different. One server may own 40% of the ring and another 8%. And if a server fails, its entire range goes to a single neighbour, which can overload it and cascade into more failures.

The fix is virtual nodes (vnodes): hash each server many times, using names such as cache-1#0, cache-1#1, ..., cache-1#99. Each server now has a hundred small, scattered slices of the ring instead of one large slice. By the law of large numbers the total size of the slices evens out, and when a server dies its load is spread over many neighbours.

flowchart LR
    S["server cache-1"] --> V0["vnode cache-1#0"]
    S --> V1["vnode cache-1#1"]
    S --> V2["vnode cache-1#2"]
    V0 --> R["positions scattered<br/>around the ring"]
    V1 --> R
    V2 --> R

One physical server owns many points on the ring. More points mean a more even split.

Python Virtual nodes even out the load

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see the smallest and largest shares converge towards the ideal as the number of virtual nodes grows. Real systems use from tens to hundreds of vnodes per server. They also let you give a stronger machine more vnodes than a weaker one, which is a simple way to do weighted load balancing.

Replication and other details

  • Replication: to keep r copies of each key, store it on the first r distinct physical servers clockwise. Skip vnodes that belong to a server you already picked.
  • Hash function: it only needs to spread values uniformly and be the same on every machine. MD5, MurmurHash or xxHash are common; do not use Python's built-in hash(), which is randomized per process.
  • Lookup cost: O(log (n * v)) with a sorted array and binary search. Adding or removing a node costs O(v log(n * v)) to update the sorted structure, which is rare compared to lookups.
  • Alternatives: rendezvous (highest-random-weight) hashing picks, for each key, the server with the highest hash(server + key). It needs no ring and also moves only a fraction of keys, at O(n) cost per lookup. Jump consistent hash is a tiny, memory-free algorithm for servers numbered 0 .. n-1.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is hash(key) % n a poor choice when the number of servers changes?

    When n changes, key % n changes for most keys, so almost all cached data is suddenly in the wrong place.
  2. 2. On a hash ring, which server is responsible for a key?

    The key is hashed onto the ring and assigned to the next server clockwise, wrapping around to the first position if needed.
  3. 3. Roughly what fraction of keys move when one server is added to a ring of n servers?

    The new node takes over only the slice of the ring it now owns, which is about its fair share, 1/(n+1) of the keys.
  4. 4. What problem do virtual nodes solve?

    Giving each server many scattered points makes the slices average out and spreads a failed server's keys over many neighbours.

Summary

  • Modulo hashing remaps most keys whenever the server count changes; consistent hashing remaps only about 1/n of them.
  • Keys and servers are hashed onto a circle; a key belongs to the next server clockwise, found with binary search on a sorted list.
  • Virtual nodes give each server many positions, which balances load and spreads the work of a failed server.
  • Replicas go to the next distinct physical servers clockwise; rendezvous hashing and jump hash are alternatives.

Next: Recursion