Consistent Hashing

Keys on a ring

Prerequisites

graph TD
  Hash[Hash functions] --> CH[Consistent Hashing]
  Bloom[Bloom Filters] --> CH
  Scale[Scalable architectures] --> CH

When to use

Distributed caches and CDNs where keys must stick to a stable shard until topology changes.
Cluster resize (add/remove nodes) when you cannot afford to reshuffle the entire dataset like hash(key) % N.
Load balancing with virtual nodes when a few physical machines must own roughly equal ring arcs.

When not to use

The cluster is tiny or static — simple modulo or round-robin may be enough.
You need strict per-key quotas or range queries on keys (use a directory service or range partitioning).
Strong ordering across the whole keyspace matters more than minimal migration (consider explicit shard maps).

Lab

On the interactive consistent hashing lab, tune Virtual nodes (replicas) to balance the ring, Remove a server to watch keys remap clockwise, and compare keys remapped vs stable against the ideal ~1/N bound and a modulo baseline. Try 3 servers, Remove one node, or High vnodes presets, then predict how many sample keys move when a node leaves.

Simple Fundamental Explanation

Imagine you run a massive online library with 4 identical warehouses (servers) to store millions of books. To find a book quickly, you hash the book’s title and use the modulo operator based on the number of warehouses: hash("Harry Potter") % 4 = 1 (Store in Warehouse 1).

This works great until Warehouse 1 catches fire and burns down. Now you only have 3 warehouses. You update your formula: hash("Harry Potter") % 3 = 2.

Suddenly, every single book in your library is assigned to a new warehouse! You have to physically move millions of books just because one warehouse went down. If you add a 5th warehouse, the same disaster happens.

Consistent Hashing solves this. Instead of a rigid mathematical grid, imagine a giant Roulette Wheel (a Hash Ring). Both the books AND the warehouses are placed on this wheel based on their hashes. To find where a book lives, you find its spot on the wheel, and walk clockwise until you hit the first warehouse.

If a warehouse burns down, its books are simply handed to the next warehouse on the wheel. The books in all the other warehouses stay exactly where they are.

Consistent hashing is a probabilistic-ish strategy that minimizes the reshuffling of data when servers are added or removed from a distributed system.

Deep Dive: How It Works Under the Hood

The Hash Ring

We use a hashing algorithm (like SHA-256 or MurmurHash) that outputs a massive range of integers, for example, $0$ to $2^{32} - 1$ . We imagine this line of integers wrapped end-to-end to form a ring.

Placing Servers and Data

Hash the Servers: Take the IP address or ID of Server A, hash it, and place it on the ring. Do the same for Servers B and C.
Hash the Data: Take the key of your data (e.g., user ID), hash it, and place it on the ring.
Routing: From the data’s position on the ring, scan strictly clockwise. The data is assigned to the first server it encounters.

The Problem: Uneven Distribution

Because hash functions are pseudo-random, Servers A, B, and C might end up clustered right next to each other on the ring. This means Server C might be responsible for 90% of the ring, while A and B handle almost nothing.

The Solution: Virtual Nodes (vnodes)

To achieve probabilistic load balancing, we don’t place Server A on the ring just once. We place it 100 times using variations of its name (e.g., ServerA-1, ServerA-2, …, ServerA-100). By having hundreds of “Virtual Nodes” for every physical server scattered randomly around the ring, the ownership of the ring balances out statistically. Every server ends up owning roughly equal, interleaved slices of the pie.

Visual Diagram

The Hash Ring (0 to 360 degrees)

      [Server A]
       /      \
[Data 1]      [Data 2]
     |          |
[Server C]----[Server B]

- Data 1 hashes to here. Moving clockwise, it hits Server A.
- Data 2 hashes to here. Moving clockwise, it hits Server B.

If Server A dies:
- Data 1 now continues clockwise past A's old spot, and hits Server B.
- Data 2 was already pointing to Server B, it does not move.
Data reshuffling is isolated!

Practical Example: Content Delivery Networks (CDNs)

Cloudflare operates thousands of edge servers worldwide. When a user requests an image logo.png, Cloudflare must route the request to a server that has the image cached.

If they used simple load balancing (random server), the image would eventually be copied to all thousands of servers, wasting massive amounts of storage. By using Consistent Hashing, hash("logo.png") always resolves to the same specific edge server (and maybe one backup).

When Cloudflare upgrades their network by adding 50 new servers, standard modulo hashing would invalidate their entire global cache, causing a massive traffic spike to origin servers. With consistent hashing, only a tiny fraction of the cached files (the ones that land between the new servers and their previous targets on the ring) are reassigned. 99% of the cache remains perfectly intact.

The Mathematics: Equations and In-Depth Analysis

1. Data Movement on Resizing

In traditional modulo hashing (hash(key) % N), changing $N$ to $N + 1$ changes the result for almost all keys. The fraction of keys that must move is:

\frac{N}{N + 1}

If you have 100 servers and add 1, roughly 99% of data must move.

In Consistent Hashing, when moving from $N$ to $N + 1$ servers, the new server takes over an average arc length of $1/ (N + 1)$ of the ring. Therefore, the fraction of keys that must move is only:

\frac{1}{N + 1}

If you have 100 servers and add 1, only ~1% of the data moves. This is the optimal minimum amount of movement required to balance the cluster.

2. Load Variance and Virtual Nodes

Let $K$ be the number of keys and $N$ be the number of servers. Ideally, each server holds $K / N$ keys. If we map $N$ physical servers directly to the ring, the variance in load is extremely high. The maximum load on a single server can be $O (K lo g N / N)$ .

By introducing $V$ virtual nodes per physical server, the load distribution approaches a uniform distribution. The standard deviation of the load drops relative to $V$ . To achieve a max load within $(1 + ϵ)$ of the average load with high probability, the number of virtual nodes needed is:

V = O (\frac{lo g N}{ϵ ^{2}})

This is why systems like Amazon Dynamo or Riak typically default to 128 or 256 virtual nodes per physical server. It provides tight probabilistic guarantees on load balancing without overloading the routing tables.

Lab

Keys and servers sit on an MD5 hash ring. Removing a node only reassigns keys that belonged to it — same recipe as consistent_hashing.py.

Virtual nodes (replicas)3 vnodes per server

user123 → Server_B
user456 → Server_C
image.png → Server_C
dataset.json → Server_B
session_abc → Server_B
cache_key_7 → Server_C

Remove a server (or use Remove one node): how many keys will remap vs stay stable?

3 servers, 3 vnodes each. Remove a server to see minimal remapping.