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

限流 · 系统设计

怎么防止一个客户端把你的 API 淹没？

为什么需要它

一个陷入死循环的脚本、一个爬虫或者一次攻击，每秒都能发出几千个请求，拖慢所有其他人的服务。限流器限制每个客户端调用你的速度，超出的请求用 HTTP 429 Too Many Requests（由 RFC 6585 定义）回应。你选的算法决定了是否允许短时间的突发，以及限流是否公平。

直觉理解

固定窗口：按每分钟（或任意窗口）统计每个客户端的请求数，超过上限就拒绝。很简单，但客户端可以在一个窗口的末尾用完全部额度，紧接着在下一个窗口开头再用一次：一瞬间就达到了两倍的上限。

令牌桶：每个客户端有一个桶，最多装 capacity 个令牌，每秒补充 rate 个。每个请求拿走一个令牌；没有令牌就不服务。

安静一阵子之后桶是满的，所以最多 capacity 个请求的突发没问题
长期来看，平均速度不会超过 rate
不管闲置多久，桶里都不会超过 capacity 个令牌

补充令牌不需要定时器：请求到来时，按过去的时间加上 (now − last) × rate 个令牌，上限是容量。

定义

限流

Capping how many requests a client may make in a period of time.
限制一个客户端在一段时间内能发出多少请求。

令牌桶

A limiter that allows bursts up to a capacity and an average rate set by the refill speed.
一种限流器：允许最多到容量的突发，平均速度由补充速度决定。

HTTP 429

The status code for "Too Many Requests". It can include a Retry-After header saying when to try again.
表示「请求过多」的状态码。它可以带一个 Retry-After 头，告诉对方什么时候再试。

示例

固定窗口

动手试试

每 60 秒限 3 次，以及边界上的突发。

def fixed_window(times, limit, window):
    counts = {}
    result = []
    for t in times:
        w = t // window
        counts[w] = counts.get(w, 0) + 1
        result.append(counts[w] <= limit)
    return result

print(fixed_window([1, 2, 3, 4, 61], 3, 60))
print(fixed_window([58, 59, 59, 60, 60, 61], 3, 60))

输出

[True, True, True, False, True]
[True, True, True, True, True, True]

逐步执行

L5请求落在哪个窗口：0–59 秒是 0，60–119 秒是 1。
L10窗口 0 里的第 4 个请求被拒绝；61 秒开始一个新窗口。
L114 秒之内 6 个请求全部放行：边界前 3 个，边界后 3 个。

令牌桶

动手试试

容量 3，每秒补充 1 个令牌。

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = 0

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

bucket = TokenBucket(capacity=3, rate=1)
for t in [0, 0, 0, 0, 0.5, 1.0, 5.0, 5.0, 5.0, 5.0]:
    print(t, bucket.allow(t))

输出

0 True
0 True
0 True
0 False
0.5 False
1.0 True
5.0 True
5.0 True
5.0 True
5.0 False

逐步执行

L9按过去的时间补充令牌，但绝不超过容量。
L11一个请求需要一个完整的令牌。
L17t = 0 时突发 3 个，之后每秒一个。隔了很久之后，最多也还是 3 个。

常见错误

按服务器限流而不是按客户端

10 台服务器各自允许每分钟 100 次，一个客户端实际上能用到 1,000 次。把计数器放在 Redis 这样的共享存储里。

拒绝了却不说什么时候能重试

客户端会立刻重试，让情况更糟。返回 429 并带上 Retry-After 头。

不封顶的补充

如果客户端闲置时令牌不断累积，它之后就能发出一次巨大的突发。桶的令牌要以容量封顶。

小测验

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

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last = 0

    def allow(self, now):
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

b = TokenBucket(capacity=2, rate=0.5)
print([b.allow(t) for t in [0, 0, 0, 2]])

A
```
[True, True, False, True]
```
B
```
[True, True, True, True]
```
C
```
[True, False, False, True]
```

查看答案

答案：A

开始有两个令牌；第三个请求时一个都没有了。过了 2 秒，按每秒 0.5 个，补回一个令牌。

2. 固定窗口限流的弱点是什么？

A在窗口边界附近，客户端能拿到大约两倍的额度
B它最多只能数到 60 个请求
C每个客户端都需要一个定时器

查看答案

答案：A

一个窗口末尾的全部额度，加上下一个窗口开头的全部额度。

动手练习

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

预测输出哪个窗口？
准确写出它打印的内容。
改需求没有底的桶
这个令牌桶在客户端闲置时不停地加令牌，所以停一大段时间后，它会放过一次巨大的突发。补充令牌时要以 capacity 封顶。
从零写令牌桶函数
写一个 token_bucket(times, capacity, rate)。times 是按顺序排列的请求时间（秒）。桶在时间 0 时是满的。为每个请求返回 True（放行）或 False（拒绝），组成一个列表。
```
token_bucket([0, 0, 0, 0, 0.5, 1.0], 3, 1)
# [True, True, True, False, False, True]
```

在互动课里练这一课

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

打开互动课课程地图

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

本课术语

术语	中文	英文定义
Rate limiting	限流	Capping how fast a client may send requests.
Token bucket	令牌桶	Allows bursts up to a capacity and an average rate.
429 Too Many Requests	429 请求过多	The HTTP status for a rate-limited request.