SyntaxPilot
Courses/System Design/Lesson 13

System Design · Lesson 13 of 40 · 12 min

Consistent hashing

queued

These are the notes for System Design episode 13. Last episode we sharded ChaiNow's data with hash % N, and adding one shard made 80% of users move. Here you invent the fix that Amazon's Dynamo and Apache Cassandra are built on: consistent hashing. Servers and keys go on a hash ring, adding a server disturbs only one neighbour, virtual nodes fix unfair shares, a dead server's keys spread out, bigger servers get more weight, and replicas (copies) live on the ring too. Every demo is plain Python and runs as-is; outputs are real (Python 3.13), and since they come from MD5 they're the same on every machine.

The six problems

Problem What it teaches
% N moves almost everything Why modulo fails when N changes, even when you double
A circle of numbers The hash ring: a key belongs to the first server clockwise
Add a server Only one neighbour's keys move
Unfair shares Virtual nodes: many points per server
A server dies Its keys spread over everyone, nobody else moves
Big servers and copies Weights (more points) and replicas (next 3 different servers)

Problem 1: % N moves almost everything

A quick reminder. A hash is a function that turns any key (a user id, a name) into a big, random-looking number; the same key always gives the same number. We use MD5, a hash function built into Python's hashlib. Last episode, a user's shard was hash(user) % N: the modulo (remainder) after dividing by N, the number of shards. It spreads users evenly. But what happens when N changes?

Demo 1: how many users move?

For one lakh users (100,000), we compare each user's shard before and after a change. Three changes: 4 to 5 shards, 4 to 8 (doubling, which sounds clever: maybe each old shard just splits in two), and 10 to 11.

import hashlib
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16)

users = range(1, 100_001)
for old, new in [(4, 5), (4, 8), (10, 11)]:
    moved = sum(1 for u in users if h(u) % old != h(u) % new)
    print(f"{old:2} -> {new:2} shards: {moved / 1000:.0f}% of users move")

Output:

 4 ->  5 shards: 80% of users move
 4 ->  8 shards: 50% of users move
10 -> 11 shards: 91% of users move

Doubling halves the damage, but moving half your data while customers keep ordering is still a disaster. And the more shards you have, the worse adding one gets: 10 to 11 moves 91%. The problem is modulo itself: change N, and almost every remainder changes. The Cassandra docs say the same about naive modulo: "adding a single node might invalidate almost all of the mappings".

What we want: a rule where adding a server only touches the keys that server should take. Moving data from one server to another to even things out is called rebalancing; we want as little of it as possible.

Problem 2: a circle of numbers (the hash ring)

On a ring road On a hash ring
A circular ring road: it goes all the way round, no start, no end The hash ring: every hash value from 0 up to 2³², bent into a circle
Delivery hubs placed at fixed points along it Servers: hash(server name) is the server's spot on the ring
Each house drives clockwise; the first hub it reaches is its hub Each key: hash(key), then walk clockwise to the first server. That server owns it.

2³² (2 to the power 32) is 4,294,967,296. We take MD5's huge number % 2**32, so every point lands between 0 and 4,294,967,295. Then we imagine that line bent into a circle, so the number after the biggest one is 0 again. That's the wrap-around: a key past the last server keeps walking, comes back in at 0, and meets the first server.

The ring picture (real MD5 positions)

To draw the ring, turn each point into degrees: h(x) / 2**32 * 360. These are the real MD5 positions behind the ring animation in the video (the same h as Demo 2): four servers, a fifth server E that joins later, and seven users.

Server Degrees Key Degrees Owner (A–D) After adding E After E, then B dies
C 28.5 user 15 44.4 A A A
A 65.6 user 7 106.8 B B E
B 172.9 user 11 183.4 D E E
E (joins later) 229.5 user 12 219.4 D E E
D 254.6 user 75 263.5 C C C
user 2 287.0 C C C
user 42 344.1 C C C

Here is the same ring cut open at 0° and laid flat. Walking clockwise means walking right; walking off the right end brings you back in on the left.

 0°                                                                         360° = 0°
 |--C----u15---A-----u7---------B--u11-----u12--E--D--u75----u2--------u42--|
   28.5       65.6            172.9            229.5 254.6
                                                                  └─ wraps to 0°, meets C

 Who owns which stretch (4 servers):
   C owns 254.6° -> 28.5° (wrapping through 0°)   users 75, 2, 42
   A owns  28.5° -> 65.6°                         user 15
   B owns  65.6° -> 172.9°                        user 7
   D owns 172.9° -> 254.6°                        users 11, 12

User 7 meets B first. User 15 meets A. User 42, near the top, walks past the end of the numbers, wraps around to zero, and meets C.

Demo 2: the Ring in code

h gives any key a point on the ring. The Ring keeps the servers' points in a sorted list. server_for finds the first point bigger than the key with bisect, Python's built-in binary search (episode 10): it finds where a value would go in a sorted list in about log N steps, without checking every item. If the key is past the last server, i equals the length of the list, and i % len(...) wraps it to 0.

import hashlib, bisect
def h(key):                                # a point on a ring of 0 .. 2^32-1
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

class Ring:
    def __init__(self, servers):
        self.points = sorted((h(s), s) for s in servers)

    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))   # first point clockwise
        return self.points[i % len(self.points)][1]    # past the end? wrap to 0

ring = Ring(["A", "B", "C", "D"])
for s_point, s in ring.points:
    print(f"server {s} sits at {s_point:>13,}")
print("user 42 ->", ring.server_for(42), "| user 7 ->", ring.server_for(7))

Output:

server C sits at   339,612,247
server A sits at   783,072,809
server B sits at 2,063,250,801
server D sits at 3,037,444,021
user 42 -> C | user 7 -> B

C at 339 million, A at 783 million, B at about 2 billion, D at 3 billion. User 42 goes to C and user 7 to B, exactly like the picture. (Why (h(key), "")? The list holds (point, name) pairs, and the empty string is smaller than any name, so the search lines up with the point alone.)

The Dynamo paper (DeCandia et al., SOSP 2007) describes exactly this: each item is assigned to a node by "walking the ring clockwise to find the first node with a position larger than the item's position". A node is just one machine (server) in the system.

Problem 3: add a server

We add server E. Its name hashes to 229.5°, between B (172.9°) and D (254.6°). Users 11 and 12 used to walk past this spot to reach D; now they meet E first. Every other user still meets the same server as before (look at the +E column above).

Demo 3: count every move

Same Ring class. Before: four servers. After: we add E. For one lakh users, we record every move, from which server to which.

import hashlib, bisect
def h(key): return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32
class Ring:
    def __init__(self, servers):
        self.points = sorted((h(s), s) for s in servers)
    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]

before = Ring(["A", "B", "C", "D"])
after = Ring(["A", "B", "C", "D", "E"])            # add server E
moves = {}
for u in range(1, 100_001):                        # 1 lakh users
    a, b = before.server_for(u), after.server_for(u)
    if a != b:
        moves[f"{a} -> {b}"] = moves.get(f"{a} -> {b}", 0) + 1
print("moves:", moves)
print(f"moved: {sum(moves.values()) / 1000:.0f}% of users")

Output:

moves: {'D -> E': 15711}
moved: 16% of users

Only one kind of move: D to E. 16% of users. Nobody else moved. With modulo, 80% moved; on the ring, only the users that E should take, and all of them came from its one neighbour. The Dynamo paper says it directly: "departure or arrival of a node only affects its immediate neighbors and other nodes remain unaffected". You just invented consistent hashing!

Problem 4: unfair shares (virtual nodes)

Look at the arcs again. Hashing puts each server at a random spot; nobody chose those spots, so the gaps between servers are uneven. A server's arc (its share) is the stretch of ring it owns, from the server before it up to itself. A big arc means many keys; a small arc means few. The amount of work a server has to do (here, how many users it stores) is its load. The Dynamo paper names this problem: "the random position assignment of each node on the ring leads to non-uniform data and load distribution". And when E arrived, it only took load from D: A, B and C got no help at all.

Here are the arcs with one point per server. (From here on, a server's points are the hashes of "A#0", "A#1" and so on, so with one point A sits at h("A#0"), not h("A").) Each server owns the stretch from the point before it, wrapping through 0°:

Point Degrees Owns Share of the ring
C#0 47.6 298.0° → 47.6° 30%
B#0 85.6 47.6° → 85.6° 11%
D#0 185.9 85.6° → 185.9° 28%
A#0 298.0 185.9° → 298.0° 31%

A owns 31% of the ring, B only 11%. Same machines, nearly three times the load.

In a city On the ring
Each dairy has one big milk depot; whoever happens to sit in a crowded area gets most customers, by luck 1 point per server: luck decides the share. Unfair.
Each dairy opens many small milk booths, spread all over the city; luck evens out Virtual nodes: many points per server (A#0, A#1 ...)
A new dairy opens its booths and takes a few customers from every neighbourhood A new server joins with many points and takes a little from every server

A virtual node (vnode) is one of a server's many points on the ring. The Dynamo paper: "instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring". Dynamo and Cassandra call these points tokens. In the video's second ring, 8 points per server, mixed all around the ring, already bring the shares to 18 to 28 percent (see practice 1).

Demo 4: 1 point vs 256 points per server

The Ring now takes vnodes: how many points each server gets. We share one lakh users first with 1 point per server, then with 256, the number Cassandra used as its default in version 2 (its docs: "the default number of tokens per node had to be quite high, at 256").

import hashlib, bisect
from collections import Counter
def h(key): return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32
class Ring:
    def __init__(self, servers, vnodes=1):
        self.points = sorted((h(f"{s}#{v}"), s)          # A#0, A#1, A#2 ...
                             for s in servers for v in range(vnodes))
    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]

for vnodes in [1, 256]:
    ring = Ring(["A", "B", "C", "D"], vnodes)
    load = Counter(ring.server_for(u) for u in range(1, 100_001))
    print(f"{vnodes:3} point(s) per server:",
          {s: f"{load[s] / 1000:.0f}%" for s in "ABCD"})

Output:

  1 point(s) per server: {'A': '31%', 'B': '11%', 'C': '30%', 'D': '28%'}
256 point(s) per server: {'A': '27%', 'B': '23%', 'C': '24%', 'D': '26%'}

One point: 31, 11, 30 and 28 percent, the same as the arcs above. 256 points: 27, 23, 24 and 26, close to a fair quarter each. More points, fairer shares. Cassandra's docs explain it the same way: "Virtual nodes solve the problem by assigning multiple tokens in the token ring to each physical node". (Counter from collections counts how many times each value appears.)

Demo 5: a new server takes a little from everyone

Add server E again, now with 256 points per server, and count where E's users came from.

import hashlib, bisect
from collections import Counter
def h(key): return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32
class Ring:
    def __init__(self, servers, vnodes=256):
        self.points = sorted((h(f"{s}#{v}"), s)
                             for s in servers for v in range(vnodes))
    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]
users = range(1, 100_001)
before = Ring(["A", "B", "C", "D"])
after = Ring(["A", "B", "C", "D", "E"])            # add server E
moved_from = Counter(before.server_for(u) for u in users
                     if before.server_for(u) != after.server_for(u))
print("E took users from:", dict(sorted(moved_from.items())))
print(f"moved: {sum(moved_from.values()) / 1000:.0f}% of users")

Output:

E took users from: {'A': 4951, 'B': 3778, 'C': 4417, 'D': 5241}
moved: 18% of users

E took a few thousand users from each of A, B, C and D. 18% moved in total, close to the fair one fifth (with 5 servers, E's fair share is 20%).

Method Users moved when E joins Taken from
hash % N (4 → 5) 80% everyone, all mixed up
Ring, 1 point per server 16% D only
Ring, 256 points per server 18% a little from A, B, C and D

Problem 5: a server dies

The opposite case. In the ring picture with E added, server B dies. Its only user there, user 7, keeps walking clockwise to the next server, E. Nobody else is touched (the -B column). But with one point per server, one neighbour takes all of B's load at once.

Demo 6: where do B's users go?

With 256 points each, B dies. Where do B's users go? And did anyone else move?

import hashlib, bisect
from collections import Counter
def h(key): return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32
class Ring:
    def __init__(self, servers, vnodes=256):
        self.points = sorted((h(f"{s}#{v}"), s)
                             for s in servers for v in range(vnodes))
    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]
users = range(1, 100_001)
before = Ring(["A", "B", "C", "D"])
after = Ring(["A", "C", "D"])                      # server B dies
went_to = Counter(after.server_for(u) for u in users
                  if before.server_for(u) == "B")
print("B's users now live on:", dict(sorted(went_to.items())))
others = sum(before.server_for(u) not in ("B", after.server_for(u)) for u in users)
print("users of A, C, D that moved:", others)

Output:

B's users now live on: {'A': 5893, 'C': 9982, 'D': 7306}
users of A, C, D that moved: 0

B's users spread over A, C and D, and zero users of A, C and D moved. No single neighbour gets crushed by a dead server's whole load. Virtual nodes matter twice: when servers join, and when they fail. (Practice 4 shows the one-point version, where all of B's users land on D.)

Problem 6: big servers and copies (weights and replicas)

ChaiNow buys a new server with twice the disk and twice the CPU. With equal points, it gets the same share as the old ones, and half of it sits idle. Machines that differ like this are called heterogeneous (heterogeneity = being different). The Dynamo paper calls it out: "the basic algorithm is oblivious to the heterogeneity in the performance of nodes" (it doesn't notice that machines differ).

Fix 1, weights: a server's weight is how big a share it should get. Give a server with twice the capacity twice as many points: 512 instead of 256.

Fix 2, replicas: from episode 11, we want copies. A replica is a copy of the data on another machine. On the ring, each key is stored on the next 3 different servers clockwise. Dynamo calls this list of servers for a key its preference list. Different matters: two neighbouring points may belong to the same server.

Demo 7: weights and replicas

Servers now come with a number of points: BIG gets 512, the others 256. replicas_for keeps walking clockwise and skips any server it already has, until it has 3 different servers. There's no server_for this time: the owner of a key is just its first replica, so the load is counted with ring.replicas_for(u, 1)[0].

import hashlib, bisect
from collections import Counter
def h(key): return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32
class Ring:
    def __init__(self, servers):           # servers: {name: number of points}
        self.points = sorted((h(f"{s}#{v}"), s)
                             for s, n in servers.items() for v in range(n))
    def replicas_for(self, key, n=3):      # next n DIFFERENT servers clockwise
        i, found = bisect.bisect(self.points, (h(key), "")), []
        while len(found) < n:
            s = self.points[i % len(self.points)][1]
            if s not in found: found.append(s)   # skip repeats
            i += 1
        return found
ring = Ring({"A": 256, "B": 256, "C": 256, "BIG": 512})   # BIG has 2x the disk
load = Counter(ring.replicas_for(u, 1)[0] for u in range(1, 100_001))
print("load:", {s: f"{load[s] / 1000:.0f}%" for s in ["A", "B", "C", "BIG"]})
print("user 42 is stored on:", ring.replicas_for(42))

Output:

load: {'A': '20%', 'B': '18%', 'C': '19%', 'BIG': '42%'}
user 42 is stored on: ['A', 'B', 'C']

BIG carries 42%, about twice each of the others (512 of the 1,280 points is a fair 40%). User 42 is stored on A, B and C: three different machines. If A dies, B and C still have it, and the ring already knows who's next. This is how Dynamo-style databases like Cassandra place and copy data: the Cassandra docs say it "partitions data over storage nodes using a special form of hashing called consistent hashing" and "maps every node to one or more tokens on a continuous hash ring".

The whole chain

  1. hash % N: change N → 50 to 91% of keys move, even when doubling.
  2. Servers and keys on a hash ring → each key belongs to the first server clockwise (wrap around past the end).
  3. Add a server → only its neighbour's keys move (16%, all from D).
  4. Random spots → unfair arcs (31% vs 11%) → virtual nodes (A#0, A#1 ...): 256 points each ≈ 25% each, and a new server takes a little from everyone (18%).
  5. A server dies → its keys spread over the others; nobody else moves.
  6. Bigger server → more points (weight). Copies → the next 3 different servers clockwise.

Common mistakes (and the real errors)

Mistake Code Error / result Fix
Forgetting the wrap-around return points[i][1] IndexError: list index out of range points[i % len(points)]
One point per server Ring(["A", "B", "C", "D"]) # 1 point each {'A': '31%', 'B': '11%', 'C': '30%', 'D': '28%'} (no error, unfair load) Virtual nodes: hundreds of points per server
Next 3 points as replicas [points[(i + k) % len(points)][1] for k in range(3)] 65% of users have 2 copies on the same server Skip servers you already picked

Mistake 1. User 7 works, because there's a server after it. User 42 (344.1°) is past the last server, D at 254.6°, so bisect returns 4, the length of the list, and there is no points[4].

import hashlib, bisect
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

points = sorted((h(s), s) for s in ["A", "B", "C", "D"])

def server_for(key):
    i = bisect.bisect(points, (h(key), ""))
    return points[i][1]                    # forgot to wrap around

print("user 7 ->", server_for(7))
print("user 42 ->", server_for(42))

Output:

user 7 -> B
Traceback (most recent call last):
  File "main.py", line 12, in <module>
    print("user 42 ->", server_for(42))
                        ~~~~~~~~~~^^^^
  File "main.py", line 9, in server_for
    return points[i][1]                    # forgot to wrap around
           ~~~~~~^^^
IndexError: list index out of range

This bug hides in testing: it only fires for keys past the last server, so a few test keys may all pass.

Mistake 2. No error at all, just unfair load.

import hashlib, bisect
from collections import Counter
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

points = sorted((h(f"{s}#0"), s) for s in "ABCD")      # 1 point each
def owner(u):
    return points[bisect.bisect(points, (h(u), "")) % len(points)][1]

load = Counter(owner(u) for u in range(1, 100_001))
print({s: f"{load[s] / 1000:.0f}%" for s in "ABCD"})

Output:

{'A': '31%', 'B': '11%', 'C': '30%', 'D': '28%'}

Mistake 3. With 256 points each, neighbouring points often belong to the same server. Taking the next 3 points puts two copies on one machine for most users; when that machine dies, two copies die with it.

import hashlib, bisect
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

points = sorted((h(f"{s}#{v}"), s) for s in "ABCD" for v in range(256))

def replicas_wrong(key, n=3):              # next n POINTS clockwise
    i = bisect.bisect(points, (h(key), ""))
    return [points[(i + k) % len(points)][1] for k in range(n)]

users = range(1, 100_001)
bad = sum(1 for u in users if len(set(replicas_wrong(u))) < 3)
print(f"{bad / 1000:.0f}% of users have 2 copies on the same server")
print("example:", next((u, replicas_wrong(u)) for u in users
                       if len(set(replicas_wrong(u))) < 3))

Output:

65% of users have 2 copies on the same server
example: (1, ['C', 'C', 'A'])

User 1's "three copies" are really two machines. The fix is replicas_for from Demo 7: skip servers already in the list.

Misconceptions

  • "Consistent hashing means nothing moves." Something always moves: the new server has to get its share from somewhere. Consistent hashing moves only that share (about 1/N of the keys), instead of almost everything.
  • "The ring has 4 points if you have 4 servers." Only in the basic version. Real systems give each server many points (virtual nodes), like Cassandra's 256 default in version 2.
  • "More points always means a fairer split." On average, yes, but it's still luck: in practice 1, 10 points per server came out less even than 8. Hundreds of points make the luck small.
  • "A new server only helps its neighbour." True with one point per server; with virtual nodes it takes a little from everyone.

Mini project: a consistent hash ring

Build a ConsistentHashRing with add_server (with a weight), remove_server, server_for and replicas_for, then test it: how many keys move when servers join and leave, and is the load fair?

# Mini project: a consistent hash ring with vnodes, weights and replicas
import hashlib, bisect
from collections import Counter

def h(key):                                    # a point on the ring 0 .. 2^32-1
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

class ConsistentHashRing:
    def __init__(self, points_per_weight=256):
        self.points_per_weight = points_per_weight
        self.points = []                       # sorted list of (position, server)
        self.weights = {}                      # server -> weight

    def add_server(self, name, weight=1):
        if name in self.weights:
            raise ValueError(f"server {name} is already on the ring")
        self.weights[name] = weight
        for v in range(self.points_per_weight * weight):   # name#0, name#1 ...
            bisect.insort(self.points, (h(f"{name}#{v}"), name))

    def remove_server(self, name):
        del self.weights[name]                 # KeyError if it was never added
        self.points = [p for p in self.points if p[1] != name]

    def server_for(self, key):
        if not self.points:
            raise LookupError("the ring has no servers")
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]        # wrap around

    def replicas_for(self, key, n=3):          # next n DIFFERENT servers clockwise
        n = min(n, len(self.weights))          # can't have more copies than servers
        i, found = bisect.bisect(self.points, (h(key), "")), []
        while len(found) < n:
            s = self.points[i % len(self.points)][1]
            if s not in found:
                found.append(s)
            i += 1
        return found

def snapshot(ring, keys):                      # key -> server, right now
    return {k: ring.server_for(k) for k in keys}

def report(title, ring, before, after):
    moved = sum(1 for k in before if before[k] != after[k])
    load = Counter(after.values())
    print(f"{title:<22} moved {moved / len(before):4.0%}   load:",
          {s: f"{load[s] / len(after):.0%}" for s in sorted(ring.weights)})

keys = [f"user:{i}" for i in range(1, 50_001)]
ring = ConsistentHashRing()
for s in ["A", "B", "C", "D"]:
    ring.add_server(s)
start = snapshot(ring, keys)

ring.add_server("E")                           # a new server joins
s1 = snapshot(ring, keys)
report("add E", ring, start, s1)

ring.add_server("BIG", weight=2)               # twice the disk, twice the points
s2 = snapshot(ring, keys)
report("add BIG (weight 2)", ring, s1, s2)

ring.remove_server("B")                        # B dies
s3 = snapshot(ring, keys)
report("remove B", ring, s2, s3)
others = sum(1 for k in keys if s2[k] != "B" and s2[k] != s3[k])
print("keys not on B that moved:", others)

copies = [ring.replicas_for(k) for k in keys]
print("every key has 3 different servers:", all(len(set(c)) == 3 for c in copies))
print("user:42 is stored on:", ring.replicas_for("user:42"))
print("ask for 10 copies of user:42:", ring.replicas_for("user:42", n=10))

Output:

add E                  moved  19%   load: {'A': '22%', 'B': '19%', 'C': '20%', 'D': '21%', 'E': '19%'}
add BIG (weight 2)     moved  29%   load: {'A': '15%', 'B': '14%', 'BIG': '29%', 'C': '14%', 'D': '15%', 'E': '13%'}
remove B               moved  14%   load: {'A': '16%', 'BIG': '34%', 'C': '17%', 'D': '17%', 'E': '16%'}
keys not on B that moved: 0
every key has 3 different servers: True
user:42 is stored on: ['BIG', 'C', 'D']
ask for 10 copies of user:42: ['BIG', 'C', 'D', 'A', 'E']

Check each line against the fair answer. Adding E moved 19% (fair: 1/5 = 20%). BIG has weight 2 out of 7, a fair 29%, and it took exactly that. Removing B moved only B's 14%, and no other key moved. Asking for 10 copies with only 5 servers gives 5: without the min(...) line, the while loop would never find a sixth server and would run forever. (bisect.insort puts a value into a sorted list at the right place, keeping it sorted.)

Practice

  1. Homework from the video: in the virtual nodes demo, try 10 and 50 points per server. How fast does it even out?
  2. Homework: add two servers, E and F. Who moves? Try 1 point and 256 points per server.
  3. Homework: fix the IndexError mistake yourself.
  4. With 1 point per server, server B dies. Where do B's users go? Compare with 256 points.
  5. On a ring from 0 to 100 with A = 10, B = 40, C = 75, who owns keys 5, 10, 41, 75 and 90? Work it out by hand, then check with bisect.
  6. In Demo 7's replicas_for, what happens if you ask for 5 copies with only 4 servers? How would you fix it?
  7. With 4 equal servers, about what fraction of keys should move when a fifth joins? When one of five leaves?
Solutions and hints

1, 2 and 4 in one script (Demo 4's Ring, plus two helpers):

import hashlib, bisect
from collections import Counter
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

class Ring:
    def __init__(self, servers, vnodes=1):
        self.points = sorted((h(f"{s}#{v}"), s)
                             for s in servers for v in range(vnodes))
    def server_for(self, key):
        i = bisect.bisect(self.points, (h(key), ""))
        return self.points[i % len(self.points)][1]

users = range(1, 100_001)
def load(ring):
    c = Counter(ring.server_for(u) for u in users)
    return {s: f"{c[s] / 1000:.0f}%" for s in sorted(c)}
def moves(before, after):
    return dict(sorted(Counter(f"{before.server_for(u)} -> {after.server_for(u)}"
        for u in users if before.server_for(u) != after.server_for(u)).items()))

print("1) points per server and the shares")
for v in [1, 8, 10, 50, 256]:
    print(f"   {v:3}:", load(Ring("ABCD", v)))
print("2) add E and F")
for v in [1, 256]:
    m = moves(Ring("ABCD", v), Ring("ABCDEF", v))
    print(f"   {v:3}:", m, f"= {sum(m.values()) / 1000:.0f}%")
print("4) B dies")
for v in [1, 256]:
    print(f"   {v:3}:", moves(Ring("ABCD", v), Ring("ACD", v)),
          "| new load:", load(Ring("ACD", v)))

Output:

1) points per server and the shares
     1: {'A': '31%', 'B': '11%', 'C': '30%', 'D': '28%'}
     8: {'A': '18%', 'B': '26%', 'C': '28%', 'D': '28%'}
    10: {'A': '17%', 'B': '15%', 'C': '32%', 'D': '35%'}
    50: {'A': '27%', 'B': '22%', 'C': '27%', 'D': '24%'}
   256: {'A': '27%', 'B': '23%', 'C': '24%', 'D': '26%'}
2) add E and F
     1: {'C -> F': 5346, 'D -> E': 16829} = 22%
   256: {'A -> E': 4420, 'A -> F': 4257, 'B -> E': 3430, 'B -> F': 4504, 'C -> E': 3698, 'C -> F': 4055, 'D -> E': 4787, 'D -> F': 3493} = 33%
4) B dies
     1: {'B -> D': 10558} | new load: {'A': '31%', 'C': '30%', 'D': '38%'}
   256: {'B -> A': 5893, 'B -> C': 9982, 'B -> D': 7306} | new load: {'A': '33%', 'C': '34%', 'D': '33%'}
  • 1. More points, fairer shares, but it's still luck: 10 points came out worse than 8. By 50 it's close; 256 is closer.
  • 2. With 1 point each, E takes only from D and F only from C (22%). With 256, E and F each take a little from all four old servers: 2/6 = 33%, the fair amount. Nothing moved between old servers (no A -> B).
  • 4. With 1 point, all of B's users land on its one clockwise neighbour, D, which jumps to 38%. With 256 points they spread out and everyone ends near a third.

3. Wrap the index with % len(points):

import hashlib, bisect
def h(key):
    return int(hashlib.md5(str(key).encode()).hexdigest(), 16) % 2**32

points = sorted((h(s), s) for s in ["A", "B", "C", "D"])

def server_for(key):
    i = bisect.bisect(points, (h(key), ""))
    return points[i % len(points)][1]      # past the end? wrap to 0

print("user 7 ->", server_for(7))
print("user 42 ->", server_for(42))

Output:

user 7 -> B
user 42 -> C

5. 5 → A, 10 → A, 41 → C, 75 → C, 90 → A (wraps). A key exactly on a server's point belongs to that server in our code, because (10, "") sorts just before (10, "A").

import bisect
ring = [(10, "A"), (40, "B"), (75, "C")]   # a tiny ring: 0 .. 100

def owner(key):
    i = bisect.bisect(ring, (key, ""))     # first point at or after the key
    return ring[i % len(ring)][1]          # past 75? wrap round to A

for key in [5, 10, 41, 75, 90]:
    print(f"key {key:>2} -> {owner(key)}")

Output:

key  5 -> A
key 10 -> A
key 41 -> C
key 75 -> C
key 90 -> A

6. It never finds a fifth different server, so the while loop runs forever (the program just hangs, no error). Fix: n = min(n, number of servers), as in the mini project (10 asked, 5 returned).

7. About 1/5 (20%) when a fifth joins: the new server's fair share, and nothing else. When one of five leaves, only its own share, about 1/5. With hash % N, 4 → 5 moved 80%.

Quick quiz

# ring positions (0 … 100 for short)
# A = 10   B = 40   C = 75

key = 90

# which server owns key 90?
  • A. A
  • B. B
  • C. C
  • D. No server
Answer

A. Walk clockwise from 90: there's no server before 100, so you wrap around to 0 and meet A at 10. (Checked in practice 5.)

Interview questions

  • Why does hash(key) % N cause a problem when you add or remove a server? Roughly what fraction of keys move? (Most of them: 80% for 4 → 5 in our demo.)
  • Explain consistent hashing. How do you find which server owns a key? (Hash it, walk clockwise to the first server, wrap around past the end.)
  • When a server joins a ring of N servers, about how many keys move, and from where? (About 1/(N+1), from its neighbour; with virtual nodes, a little from everyone.)
  • What are virtual nodes, and what two problems do they solve? (Uneven shares, and a dead or new server affecting only one neighbour.)
  • How do you handle bigger servers, and how do you pick replicas on a ring? (More points; the next 3 different servers.)
  • Which real systems use consistent hashing? (Amazon's Dynamo and Apache Cassandra, from this episode.)

Glossary

Term Meaning
Hash / hash function Turns any key into a big, random-looking number; the same key always gives the same number
MD5 A hash function in Python's hashlib; here used only to spread keys evenly around the ring
Key The thing we look up and store, like a user id
Server / node One machine that stores data; Dynamo's paper says "node"
Shard One piece of the data, stored on one server (episode 12)
Modulo (%) The remainder after division: 17 % 5 = 2
Rebalancing Moving data between servers after the set of servers changes
Hash ring All hash values from 0 to 2³² − 1 bent into a circle; servers and keys are points on it
2³² 4,294,967,296; we take % 2**32 so every point fits on the ring
Point / position Where a server or key sits on the ring: its hash value
Degrees A point drawn on a circle: point / 2**32 * 360
Clockwise The direction of increasing numbers on the ring
Wrap-around Past the biggest number, the ring continues at 0; in code, i % len(points)
bisect / binary search Python's binary search: finds where a value fits in a sorted list in about log N steps (episode 10)
bisect.insort Inserts a value into a sorted list, keeping it sorted
Consistent hashing Placing keys on a hash ring so that adding or removing a server moves only that server's share
Token Dynamo and Cassandra's word for a server's point on the ring
Virtual node / vnode One of a server's many points on the ring (A#0, A#1 ...)
Arc / share The stretch of ring a server owns, from the point before it up to its own point
Load How much work a server has; here, how many keys it stores
Uneven / non-uniform distribution Some servers get much more data than others
Heterogeneity Machines being different in size or speed
Weight How big a share a server should get; on the ring, its number of points
Replica A copy of the data on another machine (episode 11)
Preference list Dynamo's term for the list of servers that hold a key: here, the next 3 different servers clockwise
Counter From collections: counts how many times each value appears
IndexError Python error when a list index is past the end
Lakh 100,000

Summary

  • hash % N moves most keys when N changes: 80% for 4 → 5, 50% even for doubling, 91% for 10 → 11.
  • On a hash ring, servers and keys are points; each key belongs to the first server clockwise, wrapping around past the end. Lookup is a binary search (bisect).
  • Adding a server moves only the keys it should take (16%, all from its neighbour D). Removing one moves only its own keys.
  • One point per server gives unfair shares (31% vs 11%). Virtual nodes (256 points each) give about a quarter each, and a new server takes a little from everyone (18%).
  • A dead server's keys spread over everyone; nobody else moves.
  • Weights: more points for bigger servers (512 points → 42% load). Replicas: the next 3 different servers clockwise.
  • Amazon's Dynamo and Apache Cassandra place their data this way.

Next episode: our data is now copied and spread across many machines. But what happens when the network between them breaks? Do you stop answering, or answer with data that might be stale? The CAP theorem and PACELC.