专项 · 系统设计第 3 课 / 共 5 课免费阅读

负载均衡与一致性哈希 · 系统设计

怎么把数据分到很多台服务器上，又能在加一台时不乱套？

为什么需要它

一台机器永远不会一直够用。请求要经过负载均衡器，而缓存或一张大表这样的数据要分到好几台服务器上。难点在于：同一个键必须总是去同一台服务器，而且加一台服务器不应该把所有东西都重新洗牌。一致性哈希解决了这个问题，分布式缓存和数据库都在用它。

直觉理解

无状态的请求去哪台都行：负载均衡器轮流分发（轮询），或者交给最不忙的服务器。

带键的数据需要一个固定的归宿。最直接的规则是：

服务器 = hash(键) % 服务器数量

它能把键分得很均匀，但只要把服务器从 4 台改成 5 台，大多数键的答案都会变。对缓存来说，这就像在最忙的时候把它清空。

一致性哈希把服务器和键放在同一个圆环上（哈希值首尾相接）。每个键归属于从它出发顺时针遇到的第一台服务器。加一台服务器时，只有它和前一台服务器之间的那些键会移动，其他的原地不动。

两点实际经验：

Python 内置的 hash() 对字符串的结果每次启动 Python 都会变，所以要用稳定的哈希，比如 zlib.crc32
服务器少时圆环上分布不均，所以真实系统会把每台服务器放在环上很多个点（虚拟节点）

定义

负载均衡器

A component that spreads incoming requests over several servers.
把进来的请求分散到多台服务器上的组件。

分片

Splitting data over several servers by key, so each holds part of it.
按键把数据拆分到多台服务器上，每台只存一部分。

一致性哈希

Placing servers and keys on a hash ring so that adding or removing a server moves only a small share of keys.
把服务器和键放在哈希环上，使得增加或移除一台服务器时只有一小部分键需要移动。

示例

取模几乎会挪动一切

动手试试

用 hash % n，从 4 台服务器变成 5 台。

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))

输出

moved: 801 of 1000

逐步执行

L6稳定的哈希：同一个键每次运行都得到同一个数。
L8数一数服务器变了的键。True 算作 1。
L9大约每 5 个键里有 4 个要搬家：缓存几乎会丢掉大部分内容。

哈希环

动手试试

在环上做同样的改动：只有现在归新服务器的键才会移动。

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))

输出

moved: 26 of 1000
all to e: True

逐步执行

L8服务器按照哈希值的顺序排在圆环上。
L10找到位于键的位置或之后的第一台服务器。
L11超过了最后一台？绕回第一台：这是一个圆。
L17只有 e 之前那一小段弧上的键移动了。这里 e 恰好落在很短的一段弧上，所以分到的键很少；虚拟节点能让它分得更公平。
L18每个移动的键都去了新服务器；旧服务器之间没有任何键移动。all to e: True

常见错误

用 Python 的 hash() 来决定放哪

字符串的哈希在每个进程里都是随机化的，所以两台服务器（或两次重启）会算出不同的结果。用 crc32 或 md5 这样稳定的哈希。

不均匀的环

只有几台服务器时，某一台可能占据圆环上很大的一段。虚拟节点可以把它摊平。

热点键

哈希分散的是键，不是流量。一位名人的主页仍然可能压垮它所在的服务器；对热点键要加缓存或做副本。

小测验

1. 这段代码会输出什么？

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
```

查看答案

答案：A

轮询：a、b、c、a、b、c、a。第 7 个是 a，a 出现了 3 次。

2. 你加了第五台缓存服务器。用一致性哈希时，哪些键会移动？

A只有现在落到新服务器上的键
B所有键里大约五分之四
C一个都不动；只有新的键去新服务器

查看答案

答案：A

每个键都去顺时针第一台服务器；只有新服务器之前的那一段弧换了主人。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出轮询
准确写出它打印的内容。
改需求走到了环的尽头
owner 在一个 0–99 的环上找出某个位置归哪台服务器。ring 是一个排好序的 (位置, 服务器) 列表。一旦位置超过了最后一台服务器，它就会崩溃。让它绕回第一台服务器。
从零写一致性哈希
写一个 owner_of(key, servers)，用一致性哈希返回 key 归属的服务器：
- 服务器的位置是 zlib.crc32(name.encode())，键也一样
- 归属者是位置大于等于键的位置的第一台服务器，超过末尾就绕回位置最小的那台
有一个测试会检查：加一台服务器时，只有键移到新服务器上。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
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.