Appearance
想象一下，我们现在要去一个热门景点，景点为了控制人流，会设置一些关卡。这三个算法就像是三种不同的关卡放行策略。
1. 滑动窗口 (Sliding Window) / 滑动窗口计数器
核心思想： 将时间划分为多个小的窗口（或格子），统计当前时间窗口内接收到的请求数量。如果请求数量超过了阈值，则拒绝新的请求。窗口会随着时间的推移向前滑动。
图文解释：
时间轴: -------------------------------------------------->
|---- W1 ----|---- W2 ----|---- W3 ----| ...
^ ^ ^ ^
| | | |
当前时间点
假设窗口大小为1分钟，限制为100个请求/分钟
情况1 (固定窗口的缺陷):
00:00:00 00:00:59 | 00:01:00 00:01:59
[-- W1 (90 RQs) -----------------] [-- W2 (TO BE PROCESSED) ------]
如果在00:00:59 - 00:01:00 之间突然来了90个请求，然后在00:01:00 - 00:01:01 之间又来了90个请求，
虽然每个窗口都没超限，但实际上在200毫秒内处理了180个请求，这远远超过了每秒100个请求的处理能力。
情况2 (真正的滑动窗口 - 更精确):
时间: ... t-60s ......... t-1s | t (当前时间)
[-------------------- 当前的1分钟滑动窗口 --------------------]
统计这个动态窗口内的请求总数。
更细化的滑动窗口 (将大窗口切成小格子):
大窗口 (例如1分钟)
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| <-- 小格子 (例如每格6秒)
+---+---+---+---+---+---+---+---+---+---+
随着时间推移，最左边的格子移出窗口，最右边加入新的当前时间的格子。
计算当前所有格子内的请求总和。- 想象场景：
- 一个景点入口的检票员，他面前有一个计数器和一块表。
- 规定是“过去1分钟内，最多只能放100名游客”。
- 每来一个游客，检票员就看一下“从现在往前推1分钟，这段时间进去了多少人？”
- 如果加上当前这个游客还没到100人，就放行，并在计数器上记录这个游客进入的时间点。
- 如果已经满了100人，就告诉游客稍等。
- 随着时间的流逝，1分钟前进入的游客记录会自动失效，不再计入当前的1分钟统计。
工作流程 (以细粒度滑动窗口为例)：
- 划分时间： 将一个大的时间窗口（例如1分钟）划分成若干个更小的时间片（例如6秒一个，共10个时间片）。
- 计数： 每个小时间片独立记录其时间段内到达的请求数。
- 窗口滑动： 当时间向前推移，最老的小时间片会移出窗口，新的小时间片会加入窗口。
- 判断限流： 当前窗口内所有小时间片的请求数之和，即为当前时间窗口的总请求数。如果该总数超过了预设的阈值，则新请求被拒绝。
优点：
- 控制精确： 相比固定窗口（在窗口边界可能出现两倍流量），滑动窗口能更平滑和精确地控制任意时间片段内的请求速率。
- 灵活性： 可以通过调整窗口大小和小时间片的数量来平衡精度和系统开销。
缺点：
- 实现复杂度较高： 需要存储每个小时间片的计数，并进行滑动计算。
- 存储开销： 如果小时间片划分得很细，或者窗口很大，需要存储的数据会比较多。
适用场景：
- 需要较精确控制时间段内请求总数的场景，如API接口的精细化限流（例如，每分钟不超过100次，每小时不超过1000次）。
- 防止短时间内集中的恶意攻击或爬虫。
2. 漏桶 (Leaky Bucket)
核心思想： 请求像水一样进入漏桶，漏桶以恒定的速率漏出（处理）请求。如果进入的速率过快，桶会溢出，多余的请求就会被丢弃或排队。
图文解释：
请求 (水流)
|
V
+---------+
| ~~~ | <-- 漏桶 (有固定容量)
| ~~~ | 溢出的请求被丢弃 --> X
+---------+
|
V 以恒定速率漏出 (处理请求)
处理队列/下游服务- 想象场景：
- 一个顶部开口、底部有个小洞的木桶（漏桶）。
- 游客（请求）像水一样被倒入这个木桶。
- 无论倒水的速度有多快（请求来得多急），水只能以固定的速度从小洞流出（请求被匀速处理）。
- 如果倒水太快，木桶满了，后来的水就会溢出（请求被丢弃）。
- 关键点： 输出的速率是恒定的，它能有效地平滑输入流量的波动。
工作流程：
- 请求进入： 请求到达时，被放入一个固定容量的队列（桶）。
- 匀速处理： 系统以固定的速率
r从队列中取出请求并处理。 - 溢出处理： 如果请求到达时队列已满，则新请求被拒绝或丢弃。
优点：
- 平滑流量： 强制输出速率恒定，能有效地保护下游系统不受突发流量冲击。
- 实现简单： 实现简单，易于理解。
缺点：
- 无法应对突发流量： 即使桶是空的，突发的大量请求也无法被立即处理，因为出口速率是固定的。这可能导致响应延迟或请求丢失。
- 不灵活： 对于那些确实需要处理一些突发情况的系统来说，漏桶显得过于严格。
适用场景：
- 需要严格控制输出速率的场景，例如：
- CDN边缘节点回源流量控制，确保源站不会被突发流量打垮。
- 消息队列的消费者，以稳定的速率处理消息。
- 保护数据库或第三方API等处理能力有限的下游服务。
3. 令牌桶 (Token Bucket)
核心思想： 系统以恒定的速率往桶里放入令牌，处理请求时需要从桶里消耗一个令牌。如果桶里有足够的令牌，请求就能被快速处理（允许一定程度的突发流量）；如果桶里没有令牌，请求就需要等待或者被拒绝。
图文解释：
+-------------------+ 以恒定速率放入令牌 +---------+
| 令牌生成器 +------------------------> | 令牌桶 | <-- 请求需要消耗令牌
+-------------------+ +---------+
|
V
处理请求 (如果拿到令牌)
丢弃/等待 (如果没拿到令牌)- 想象场景：
- 一个游乐园入口，每隔一段时间（比如1秒）就发一张门票（令牌）放入一个票箱（令牌桶）里。
- 票箱有最大容量（比如最多放100张票）。
- 游客（请求）来了，想进去玩，就得从票箱里拿一张票。
- 如果票箱里有票，游客拿了票就进去了。
- 如果票箱里没票，游客要么排队等新票发放，要么就被告知今天满员了（请求被拒绝）。
- 关键点： 如果短时间内没有游客，票箱里的票会越积越多（但不会超过票箱容量）。这时如果突然来了一小队游客（突发流量），只要票箱里的票够，他们都能立刻进去。
工作流程：
- 令牌生成： 系统以固定的速率
r(例如：每秒10个令牌) 向桶中添加令牌。 - 桶的容量： 桶有一个最大容量
b(例如：100个令牌)。如果桶满了，新生成的令牌会被丢弃。 - 请求处理： 当一个请求到达时：
- 如果桶中有令牌，消耗一个令牌，请求被处理。
- 如果桶中没有令牌，请求被拒绝或放入等待队列。
优点：
- 允许突发流量： 只要桶内有足够的令牌，短时间内的大量请求可以被立即处理，这对于那些平均流量不高但偶尔有峰值的场景非常友好。
- 控制平均速率： 长期来看，请求的处理速率受限于令牌的生成速率。
缺点：
- 突发流量可能过大： 如果桶的容量设置得过大，瞬时的突发流量可能会对下游系统造成压力。
- 实现稍复杂： 实现相对漏桶稍复杂一点（需要一个定时器或机制来添加令牌）。
适用场景：
- 需要允许并处理一定程度突发流量的场景，如API接口限流，允许用户偶尔的快速操作。
- 网络流量整形，希望在控制平均速率的同时，也能应对突发的数据包。
三者区别总结
| 特性 | 令牌桶 (Token Bucket) | 漏桶 (Leaky Bucket) | 滑动窗口 (Sliding Window) |
|---|---|---|---|
| 核心机制 | 攒令牌，凭令牌通过 | 水桶匀速漏水，满了则溢出 | 统计过去一段时间内的请求总数 |
| 突发流量 | 允许 (消耗累积的令牌) | 不允许 (输出速率恒定) | 允许 (只要窗口内总数未超限) |
| 输出速率 | 可变 (平均速率受令牌生成速率限制) | 恒定 | 可变 (但有明确的上限) |
| 平滑流量 | 一般 (突发时依然是突发) | 强 (强制平滑) | 较好 (比令牌桶平滑，但不如漏桶严格) |
| 实现复杂度 | 中等 | 简单 | 较高 |
| 关注点 | 控制平均速率，同时允许一定突发 | 严格控制输出速率，保护下游 | 精确控制一个时间窗口内的总请求量 |
| 典型比喻 | 游乐园门票 | 带孔的漏水桶 | 检票员看表和计数器 |
简单来说：
- 滑动窗口： “过去这一小段时间内，进来的人数不能超过某个数。” —— 适合需要精确控制某个时间段内总量的场景。
- 漏桶： “不管来多少人，出口每次只能走一个，排队慢慢来。” —— 适合需要严格匀速处理，保护脆弱下游的场景。
- 令牌桶： “我有票就能走，票会攒起来，所以能一下子走一批人。” —— 适合需要应对突发，但整体可控的场景。
选择哪种算法取决于你的具体需求：是想允许一些突发、还是想严格平滑流量、或者是想精确控制某个时间段的总量。