Specialty · System designLesson 3 of 5Free to read

Load balancing and consistent hashing · System Design

How do you spread data over many servers, and add one without chaos?

Why you need it

One machine is never enough forever. Requests go through a load balancer, and data such as a cache or a big table is split over several servers. The tricky part is that a key must always go to the same server, and adding a server shouldn't reshuffle everything. Consistent hashing solves this, and it's used in distributed caches and databases.

The intuition

Stateless requests can go anywhere: a load balancer hands them out in turn (round robin) or to the least busy server.

Keyed data needs a fixed home. The obvious rule:

server = hash(key) % number_of_servers

It spreads keys evenly, but change the number of servers from 4 to 5 and most keys get a different answer. For a cache, that's like emptying it during your busiest hour.

Consistent hashing puts servers and keys on the same circle (the hash values wrap around). Each key belongs to the first server clockwise from it. Add a server, and only the keys between it and the server before it move; everything else stays put.

Two practical notes:

Python's built-in hash() of a string changes every time Python starts, so use a stable hash such as zlib.crc32
with few servers the circle is uneven, so real systems place each server at many points (virtual nodes)

Definition

Load balancer

A component that spreads incoming requests over several servers.

Sharding

Splitting data over several servers by key, so each holds part of it.

Consistent hashing

Placing servers and keys on a hash ring so that adding or removing a server moves only a small share of keys.

Examples

Modulo moves almost everything

Try it yourself

Going from 4 to 5 servers with hash % n.

import zlib

keys = [f"user{i}" for i in range(1000)]

def server(key, n):
    return zlib.crc32(key.encode()) % n

moved = sum(server(k, 4) != server(k, 5) for k in keys)
print("moved:", moved, "of", len(keys))

Output

moved: 801 of 1000

Step by step

L6A stable hash: the same key gives the same number every run.
L8Count the keys whose server changed. True counts as 1.
L9Roughly 4 in 5 keys move: a cache would lose most of its contents.

A hash ring

Try it yourself

The same change on a ring: only keys that now belong to the new server move.

import bisect
import zlib

def pos(name):
    return zlib.crc32(name.encode())

def owner(servers, key):
    ring = sorted((pos(s), s) for s in servers)
    positions = [p for p, s in ring]
    i = bisect.bisect_left(positions, pos(key))
    return ring[i % len(ring)][1]

keys = [f"user{i}" for i in range(1000)]
old = ["a", "b", "c", "d"]
new = old + ["e"]
moved = [k for k in keys if owner(old, k) != owner(new, k)]
print("moved:", len(moved), "of", len(keys))
print("all to e:", all(owner(new, k) == "e" for k in moved))

Output

moved: 26 of 1000
all to e: True

Step by step

L8Servers sit on the circle in order of their hash.
L10Find the first server at or after the key's position.
L11Past the last server? Wrap around to the first: it's a circle.
L17Only keys on the arc just before e moved. e landed on a small arc here, so it got few keys; virtual nodes would give it a fairer share.
L18Every key that moved went to the new server; nothing moved between old ones.all to e: True

Common mistakes

Using Python's hash() for placement

String hashes are randomised per process, so two servers (or two restarts) disagree. Use a stable hash such as crc32 or md5.

Uneven rings

With a handful of servers, one may own a huge arc of the circle. Virtual nodes even it out.

Hot keys

Hashing spreads keys, not traffic. One celebrity's profile can still overload its server; cache or replicate hot keys.

Quick quiz

1. What does this print?

1
2
3

servers = ["a", "b", "c"]
picks = [servers[i % len(servers)] for i in range(7)]
print(picks[-1], picks.count("a"))

A
```
a 3
```
B
```
c 2
```
C
```
a 2
```

Show the answer

Answer: A

Round robin: a, b, c, a, b, c, a. The 7th is a, and a appears 3 times.

2. You add a fifth cache server. With consistent hashing, which keys move?

AOnly keys that now fall to the new server
BAbout four in five of all keys
CNone; new keys go to the new server

Show the answer

Answer: A

Each key goes to the first server clockwise; only the arc before the new server changes owner.

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictRound robin
Type exactly what this prints.
ModifyOff the end of the ring
owner finds which server owns a position on a ring of 0–99. ring is a sorted list of (position, server). It works until a position is past the last server; then it crashes. Make it wrap around to the first server.
WriteConsistent hashing
Write owner_of(key, servers) that returns the server owning key with consistent hashing:
- a server's position is zlib.crc32(name.encode()), and the same for the key
- the owner is the first server whose position is at or after the key's, wrapping around to the lowest position
A test checks that adding a server only moves keys to the new one.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Interactive lessons open in order. If you have not done the earlier ones yet, you start at the course map.

Terms in this lesson

Term	Chinese	Definition
Load balancer	负载均衡器	Spreads requests over servers.
Sharding	分片	Splitting data over servers by key.
Consistent hashing	一致性哈希	A hash ring where adding a server moves few keys.
Virtual node	虚拟节点	One of many ring positions for the same server.