Consistent hashing: add servers without reshuffling data

What consistent hashing is: why splitting data with modulo moves 91% of it when you add one server, while a hash ring moves only about 9%.

8 phút đọcTrung cấpEyeBlogs

Đọc bản tiếng Việt →

A large circle on a dark background is the hash ring. On it are coloured squares for four servers A, B, C and D, each appearing three times in different places. Inside the ring are coloured dots, each a piece of data, with a curved arrow pointing to the first square clockwise, in the same colour.
Mục lục

On the night of a big sale, traffic to a shopping site jumps tenfold. Engineers add cache servers to absorb the load, and the site… gets much slower. It sounds absurd, but it really happens if data is split across machines in the simplest possible way. Consistent hashing is the technique that solves exactly this problem: a way of splitting data across many servers so that when you add or remove one server, only a small part of the data has to move, instead of almost all of it.

This article explains why the “usual” way of splitting collapses when the number of servers changes, the ring idea behind consistent hashing, the “virtual node” trick that evens out the load, and the systems that use it, from Akamai to Amazon. At the end there is a piece of code so you can count for yourself how much data has to move house.

Splitting data across servers: the easiest way

A large website does not keep all its data on one machine. The information of millions of users is spread over many servers, each holding a part. The first question: which server holds the data of user 12345?

The easiest way: turn the user ID into a random-looking number with a hash function (the same kind of “blender” as in the Bloom filter article), then take the remainder after dividing by the number of servers. With 10 servers, divide the number by 10; a remainder of 3 means server 3. It is fast, needs no memory, and spreads data fairly evenly.

The trouble starts when the number of servers changes. Add an 11th server and you now divide by 11 instead of 10, and almost every user’s remainder changes. The simulation at the end of this article with 100,000 users shows that 91% of the data has to move to another server just because one server was added.

For a cache, that means almost every lookup misses: new servers are asked for data they do not have, and at the same time a flood of requests hits the database behind them. Adding servers to absorb load creates a new wave of load, exactly when the system is at its weakest. For stored data, 91% of it has to be copied over the network, which can take hours.

The ring idea

In 1997 a research group at MIT published a different approach, in a paper about relieving websites hit by sudden floods of traffic[1]. Two of the co-authors, Tom Leighton and Danny Lewin, founded Akamai the following year, the content delivery company mentioned in the Bloom filter article.

The idea goes like this. Bend the range of numbers a hash function produces into a circle, like a clock face. Then:

  • Place the servers on the ring: hash each server’s name to get a position on the ring.
  • Place the data on the ring: hash the ID of each piece of data to get a position.
  • The rule: each piece of data belongs to the first server you reach going clockwise from its position.

The image at the top of this article is such a ring: the dots are data, the squares are servers, and each arrow points to the server holding that dot.

Now add a new server. It lands at some position on the ring and only “takes” the data just before it, data that used to belong to the next server along. All other data stays where it is. Going from 10 servers to 11, only about 1/11, or 9% of the data moves, exactly the share the new server has to take on. Removing a server is the reverse: only that server’s data moves to the next server.

To find which server a piece of data belongs to, you only need to find the first server position greater than the data’s position in the sorted list of positions. That is binary search, fast even with thousands of servers.

Virtual nodes: evening out the load

The ring has one weakness. With only a few servers, their random positions on the ring are rarely evenly spaced. A server that sits after a large gap has to hold a lot of data. In the simulation at the end of the article, with one position per server, the busiest server holds more than 30,000 users while the lightest holds only about 1,300, when the ideal is 10,000 each.

The fix is to give each server many positions on the ring, called virtual nodes: server A appears not once but 200 times, at 200 places scattered around the ring. Big and small gaps balance each other out, so each server gets close to its fair share. With 200 virtual nodes per server, the load ranges from about 8,900 to 11,300, much closer to the ideal.

Virtual nodes have two more benefits. A more powerful server can take more virtual nodes, and so a bigger share. And when a server fails, its data does not all fall on one neighbouring server but spreads over many, because its 200 positions have 200 different neighbours.

Who uses consistent hashing?

Caches and content delivery networks. This was the first application, in the 1997 paper: splitting web content across many cache servers so that adding or removing servers does not wipe out the whole cache[1].

Amazon Dynamo. In 2007 Amazon described Dynamo, the data store behind services that must always be available, such as the shopping cart. Dynamo splits data with consistent hashing and virtual nodes, and each piece of data is replicated on the next few servers along the ring, so that if one server fails another copy remains[2].

Cassandra. The distributed database Cassandra, originally developed at Facebook, also arranges its servers in a ring and splits data the same way[3].

Leaner variants. In 2014 two Google engineers published jump consistent hash, a function only a few lines of code long that needs no stored ring yet still guarantees that when the number of servers grows, only the necessary share of data moves. In return, it only suits cases where servers are numbered consecutively and are only added or removed at the end of the list[4].

Design questions

  • How many virtual nodes? More virtual nodes mean a more even load, but a longer list of positions and more memory. A few dozen to a few hundred per server is common.
  • How is the data moved? Consistent hashing tells you which data must move; it does not move it for you. The system still has to copy that data to the new server while serving users, and only then switch to the new positions.
  • Who holds the “map” of the ring? Every server and every caller must see the same ring. If two application servers have two different versions of the ring, the same data will be looked for in two places. It is the same kind of “where does the shared data live” question that the rate limiter and sliding window article faces when a hundred servers all count at once.
  • “Hot” data. Consistent hashing evens out the amount of data, not the amount of traffic. A product being viewed by a million people still sits entirely on one server. Cases like that need an extra cache of their own or copies of that data on several servers.

Count it yourself: how much data has to move house?

The Python below takes 100,000 keys (user IDs) and 10 servers, then adds an 11th. It counts the share of keys that must move to another server with three ways of splitting: modulo, a hash ring with one position per server, and a hash ring with 200 virtual nodes per server, and also counts how many keys each server holds. It draws the image at the top of the article too. You only need matplotlib.

consistent_hash.py
import bisect
import hashlib
import math
import matplotlib.pyplot as plt
plt.rcParams.update({"figure.facecolor": "#16181c", "axes.facecolor": "#16181c", "text.color": "#d4d7dc",
"axes.edgecolor": "#2a2e35", "xtick.color": "#878d97", "ytick.color": "#878d97", "font.size": 12})
def h(s):
"""Hash a string to a 64-bit integer (MD5 for easy reproducibility, not for security)."""
return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")
class Ring:
"""Hash ring: each server places `vnodes` points on the ring; a key belongs to the first point clockwise."""
def __init__(self, servers, vnodes=1):
self.points = sorted((h(f"{s}#{i}"), s) for s in servers for i in range(vnodes))
self.keys = [p for p, _ in self.points]
def owner(self, key):
i = bisect.bisect(self.keys, h(key)) % len(self.keys) # find the next point with binary search
return self.points[i][1]
keys = [f"user:{i}" for i in range(100_000)]
before, after = [f"server-{i}" for i in range(10)], [f"server-{i}" for i in range(11)]
# Method 1: modulo — server = hash(key) mod number of servers.
moved_mod = sum(h(k) % 10 != h(k) % 11 for k in keys) / len(keys)
# Methods 2 and 3: hash ring, 1 point or 200 points (virtual nodes) per server.
stats = {}
for v in (1, 200):
r10, r11 = Ring(before, v), Ring(after, v)
owners10 = [r10.owner(k) for k in keys]
moved = sum(a != r11.owner(k) for a, k in zip(owners10, keys)) / len(keys)
load = [owners10.count(s) for s in before]
stats[v] = (moved, min(load), max(load))
print(f"add an 11th server — modulo: {moved_mod:.1%} of keys must move")
for v, (moved, lo, hi) in stats.items():
print(f"add an 11th server — hash ring, {v:>3} point(s)/server: {moved:.1%} of keys move; "
f"the 10 servers hold {lo:,} to {hi:,} keys (ideal 10,000)")
print(f"theory: modulo moves ~{1 - 1 / 11:.1%}, hash ring moves ~{1 / 11:.1%}")
# Figure 1: share of keys that must move, and load imbalance between servers.
fig, (a1, a2) = plt.subplots(1, 2, figsize=(11, 4.6))
names = ["modulo", "hash ring\n1 point/server", "hash ring\n200 points/server"]
moved = [moved_mod, stats[1][0], stats[200][0]]
a1.bar(names, [100 * m for m in moved], color=["#c98f8f", "#8fa9c9", "#e8b05a"])
for i, m in enumerate(moved):
a1.text(i, 100 * m + 2, f"{m:.0%}", ha="center", color="#d4d7dc")
a1.set_ylim(0, 105)
a1.set_ylabel("% of keys moved to another server", color="#a4a9b2")
a1.set_title("Adding an 11th server to 10 servers", color="#d4d7dc", fontsize=12)
for i, v in enumerate((1, 200)):
_, lo, hi = stats[v]
a2.plot([i, i], [lo, hi], color=["#8fa9c9", "#e8b05a"][i], lw=10, solid_capstyle="butt")
a2.text(i + 0.12, hi, f"{hi:,}", color="#d4d7dc", va="center", fontsize=10)
a2.text(i + 0.12, lo, f"{lo:,}", color="#d4d7dc", va="center", fontsize=10)
a2.axhline(10_000, color="#878d97", ls="--", lw=1)
a2.text(-0.45, 10_400, "ideal", color="#878d97", fontsize=10, ha="left")
a2.set_xticks([0, 1], names[1:])
a2.set_xlim(-0.5, 1.6)
a2.set_ylabel("keys held per server (fewest → most)", color="#a4a9b2")
a2.set_title("Is the load even across 10 servers?", color="#d4d7dc", fontsize=12)
for ax in (a1, a2):
ax.grid(axis="y", color="#22262c")
ax.set_axisbelow(True)
fig.tight_layout()
fig.savefig("chuyen-cho-va-tai-en.png", dpi=150, bbox_inches="tight")
# Cover image: a hash ring with 4 servers, 3 points each; a few keys with arrows to the server holding them.
colors = ["#e8b05a", "#8fa9c9", "#c98f8f", "#9fc98f"]
ring4 = Ring([f"Server {c}" for c in "ABCD"], 3)
fig, ax = plt.subplots(figsize=(8, 8))
ax.add_patch(plt.Circle((0, 0), 1, fill=False, color="#4a4e57", lw=3))
pos = lambda x: (math.sin(2 * math.pi * x / 2**64), math.cos(2 * math.pi * x / 2**64))
for p, s in ring4.points:
x, y = pos(p)
ax.plot(x, y, "s", ms=16, color=colors["ABCD".index(s[-1])], zorder=3)
ax.text(1.17 * x, 1.17 * y, s[-1], ha="center", va="center", color="#d4d7dc", fontsize=13)
for k in [f"photo:{i}" for i in range(14)]:
kx, ky = pos(h(k))
owner = ring4.owner(k)
i = bisect.bisect(ring4.keys, h(k)) % len(ring4.keys)
ox, oy = pos(ring4.points[i][0])
ax.plot(kx * 0.82, ky * 0.82, "o", ms=7, color=colors["ABCD".index(owner[-1])])
ax.annotate("", xy=(ox * 0.95, oy * 0.95), xytext=(kx * 0.82, ky * 0.82),
arrowprops=dict(arrowstyle="->", color="#4a4e57", lw=1, connectionstyle="arc3,rad=-0.2"))
ax.set_xlim(-1.35, 1.35); ax.set_ylim(-1.35, 1.35); ax.set_aspect("equal"); ax.axis("off")
ax.set_title("Hash ring: each piece of data (dot) belongs to the first server clockwise (square)",
color="#d4d7dc", fontsize=11)
fig.savefig("vong-bam-en.png", dpi=150, bbox_inches="tight")
add an 11th server — modulo: 90.7% of keys must move
add an 11th server — hash ring, 1 point(s)/server: 7.9% of keys move; the 10 servers hold 1,291 to 30,515 keys (ideal 10,000)
add an 11th server — hash ring, 200 point(s)/server: 10.3% of keys move; the 10 servers hold 8,912 to 11,300 keys (ideal 10,000)
theory: modulo moves ~90.9%, hash ring moves ~9.1%
Two charts. Left: a bar chart of the percentage of keys that must move when an 11th server is added to 10: modulo 91% (tall red bar), hash ring with 1 point per server 8%, hash ring with 200 points per server 10%. Right: two vertical bars showing the fewest to most keys a server holds: hash ring with 1 point per server spans 1,291 to 30,515; hash ring with 200 points per server spans only 8,912 to 11,300, close to the dashed ideal line at 10,000.
Figure 1. Left: adding one server, modulo moves 91% of the data, a hash ring only about 9%. Right: a hash ring with one position per server splits the load very unevenly; 200 virtual nodes per server bring the load close to the ideal.

The results match the theory: modulo moves about 10/11 of the data, a hash ring only about 1/11. The figures of 7.9% and 10.3% vary around 9.1% because the new server’s position on the ring is random: it may land in a narrow gap or a wide one. With virtual nodes, the share that moves stays small, while the load across servers is far more even.

You can change 200 to 20 or 1000 to see the load even out as the number of virtual nodes grows, or add a line that removes a server to see which servers its data spreads to.

Only move what needs moving

Consistent hashing does not make splitting data faster. It makes change cheaper: adding servers, removing servers, servers failing, things that happen every day in a large system, only touch the data actually involved. It is a design habit worth remembering, and not only for servers: when choosing how to divide work, ask not just “is this split even?” but also “when one more person joins, how much of the work has to be divided again from scratch?”.

Free geometry illustrations for students and teachers: EyeViz.

Tài liệu tham khảo

  1. [1]David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine and Daniel Lewin. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. STOC ’97, 1997.
  2. [2]Giuseppe DeCandia et al.. Dynamo: Amazon’s Highly Available Key-value Store. SOSP ’07, 2007.
  3. [3]Avinash Lakshman and Prashant Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 44(2), 2010.
  4. [4]John Lamping and Eric Veach. A Fast, Minimal Memory, Consistent Hash Algorithm. arXiv (Google), 2014.