Consistent Hashing
Consistent hashing puts keys and servers on a ring so adding a node moves about 1/N of keys, not nearly all. Simulated with 100,000 keys: mod-N moved 90.7%, the ring moved 8.3%.
Consistent hashing maps keys and servers onto the same circular hash space and assigns each key to the next server clockwise, so adding or removing a server moves only the keys in its arc, about 1/N of them. Interviewers also expect virtual nodes: many ring points per server, which even out load and spread a failed node's keys.
Consistent hashing maps both keys and servers onto the same circular hash space and gives each key to the next server clockwise. When a server joins or leaves, only the keys in its arc move, roughly 1/N of them, whereas hash(key) mod N reshuffles almost everything.
- With hash(key) mod N, growing from 10 to 11 servers moved 90.7% of 100,000 keys in a simulation using an MD5-based hash.
- On a consistent hashing ring, growing from 10 to 11 nodes moved 8.27% of 100,000 keys, close to the ideal 1/11 or 9.09%.
- When a node is added to a consistent hashing ring, every moved key goes to the new node, so no key moves between two existing servers.
- Consistent hashing lookup is a binary search over the sorted ring points, which costs O(log M) for M points on the ring.
- With one point per server on a consistent hashing ring, the busiest server held 2.26 times its fair share; with 1,000 virtual nodes it held 1.05 times.
- Consistent hashing does not fix hot keys, because a single very popular key still maps to one server.
01The problem with hash(key) mod N
The simplest way to spread keys over N servers is server = hash(key) mod N. It is fast, stateless and evenly balanced. It also falls apart when N changes. Going from 10 servers to 11 changes the divisor for every key, and a key keeps its server only when hash mod 10 happens to equal hash mod 11.
For a cache that means a deploy or a failure turns most lookups into misses at once, and all those misses hit the database together. For a sharded store it means moving most of the data. I measured it with 100,000 keys and an MD5-based hash: growing from 10 to 11 servers moved 90.7% of the keys. Roughly one key in ten stayed put, which is about what chance would give.
02The ring: keys and servers share one hash space
Imagine the hash output as a circle, from 0 up to its maximum and wrapping back to 0. Hash each server name to a point on the circle. To place a key, hash it to a point and walk clockwise until you meet a server. That server owns the key.
In code the ring is a sorted list of server points. Lookup is a binary search for the first point greater than the key's hash, wrapping to index 0 at the end. That makes lookup O(log M) for M points on the ring, and a node join or leave touches only the arc between the new point and its predecessor.
When a server is added, it takes over the part of the circle just behind its point, and the keys it takes come from one neighbour. Nothing else moves. When a server dies, its arc is absorbed by the next server clockwise.
03Measuring how few keys move
This is a simulation, written to check the claim rather than copied from a source.
import hashlib, bisect, statistics
def h(s):
return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")
class Ring:
def __init__(self, nodes, vnodes=100):
self.vnodes = vnodes
self.keys, self.owner = [], {}
for n in nodes:
self.add(n)
def add(self, node):
for i in range(self.vnodes):
p = h(f"{node}#{i}")
bisect.insort(self.keys, p)
self.owner[p] = node
def get(self, key):
i = bisect.bisect(self.keys, h(key)) % len(self.keys)
return self.owner[self.keys[i]]
keys = [f"user:{i}" for i in range(100_000)]
nodes = [f"n{i}" for i in range(10)]
# modulo hashing: 10 -> 11 servers
before = {k: h(k) % 10 for k in keys}
after = {k: h(k) % 11 for k in keys}
moved = sum(before[k] != after[k] for k in keys)
print("mod-N moved:", moved / len(keys))
# ring: 10 -> 11 servers
r = Ring(nodes, 100)
b = {k: r.get(k) for k in keys}
r.add("n10")
a = {k: r.get(k) for k in keys}
moved = sum(b[k] != a[k] for k in keys)
print("ring moved:", moved / len(keys), "ideal", 1/11)
print("all moved keys went to new node:", all(a[k] == "n10" for k in keys if a[k] != b[k]))
# load balance vs vnodes
for v in (1, 10, 100, 1000):
r = Ring(nodes, v)
cnt = {}
for k in keys:
cnt[r.get(k)] = cnt.get(r.get(k), 0) + 1
c = [cnt.get(n, 0) for n in nodes]
print(v, "max/mean", round(max(c) / (len(keys) / 10), 2), "min/mean", round(min(c) / (len(keys) / 10), 2))Run on Python 3.13 it printed:
mod-N moved: 0.90707
ring moved: 0.0827 ideal 0.0909090909090909
all moved keys went to new node: TrueThe ideal fraction is 1/11 = 9.09%, because the new node should end up with one eleventh of the data. The ring moved 8.27%, a little less than ideal because of random placement of the virtual points. The last line is the important property: no key moved between two old servers, so existing nodes only lose keys, never swap them.
04Virtual nodes: fixing uneven load
With one point per server the arcs are random, and random arcs differ a lot in size. Some server ends up with a big arc and a lot of traffic. The fix is virtual nodes: hash each server many times, for example n3#0, n3#1, up to n3#99, and place all of those points on the ring. A server's load is then the sum of many small random arcs, which averages out.
The same simulation, 10 servers and 100,000 keys, measuring the busiest and the lightest server against the mean:
vnodes per server max/mean min/mean
1 2.26 0.06
10 1.46 0.65
100 1.19 0.90
1000 1.05 0.96With a single point, the busiest server held 2.26 times its fair share and the lightest almost nothing. At 100 virtual nodes the busiest was 19% over. More virtual nodes cost memory for the ring and slower rebuilds, and they let you give a bigger machine more points to take more load.
05Replication, failures and where it is used
To survive a crash, systems store each key on the owner and also on the next R-1 distinct servers clockwise. The Dynamo paper from Amazon describes this idea with virtual nodes, and consistent hashing is the placement rule in Apache Cassandra and in many cache clients. Content delivery networks and load balancers use it so a request for the same object keeps landing on the same server.
The technique is not free of trouble. Hot keys still overload one server however the ring is arranged. Skipping virtual points that belong to the same physical machine matters when picking replicas. Variants such as rendezvous hashing and jump consistent hash solve the same problem with different trade-offs; I have not benchmarked them here.
06Common interview questions
Q: Why not use hash(key) mod N?
A: When N changes, almost every key maps to a different server, so a cache is flushed or a store must reshuffle nearly all data.
Q: What fraction of keys move when you add one server to N?
A: About 1/(N+1), only the keys in the arc the new server takes over.
Q: What are virtual nodes and why use them?
A: Many ring points per physical server. They even out load, spread a failed node's keys over many survivors and allow weighting by machine size.
Q: How do you find the owner of a key efficiently?
A: Keep the ring points sorted and binary search for the first point at or after the key's hash, wrapping around. O(log M).
Q: How does replication work on the ring?
A: Store the key on the next R distinct physical servers clockwise from its position.
Q: Does consistent hashing solve hot keys?
A: No. A single very popular key still maps to one server, so you need caching in front or key splitting.