常见限流算法及实现思路
/ 9 min read
Table of Contents
限流简介
在实际的系统中，服务器所能承载的请求速率是有上限的。给定这个硬上限时，不能要求服务器处理每一个请求，否则流量太大早晚会耗尽资源。为此，请求在进入服务之前，首先要满足一定的请求速率——否则我们认为服务器有出问题的风险，不予放行。
这个「控制请求速率不超标」的中间件，被称为限流中间件，使用的算法称为限流算法。
分类-时间窗口类
固定窗口
固定窗口很好理解：把时间轴划分成一个个固定长度的窗口，每个窗口内允许通过的请求数量是有限的。当一个请求到来时，我们检查当前窗口内已经处理了多少请求，如果超过了限制，就拒绝这个请求。
确定固定窗口的两个参数：
- 时间窗口大小
- 一个窗口内的请求限制
图示一下：
|---- 1s ----|---- 1s ----|---- 1s ----|| * * * | * * * x | * * || 3 / 3 | 4 / 3 | 2 / 3 || Pass | Drop 1 req | Pass |缺陷
在窗口的边缘处容易出现突发流量，也就是所谓的流量突刺。
|------------ 1s --|-- 1s -------------|| ********|******** || 100 / 100 | 100 / 100 || Pass | Pass |上图表示一种可能发生的情况：在第一个窗口的最后时刻，来了 100 个请求，全部通过；在第二个窗口的开始时刻，又来了 100 个请求，也全部通过。
但限流是为保护服务器不过载；我们原本希望限制一个窗口内的请求为 100，如果在短时间内来了 200 个请求，土豆服务器可能会吃不消，导致服务中断。
滑动窗口
滑动窗口在固定窗口的思路上加以改进。
滑动窗口同样划分时间轴为固定长度的时间窗口片，但不同点是：计数不看某一个固定的窗口，而是统计连续的若干小时间片。随着时间流逝，过期时间片被移除、其数据也从限流统计中剔除，新的时间片接收请求并纳入限流统计。其实就是更细粒度的计数（如果只有一片，则退化为固定窗口）。
确定滑动窗口的参数：
- 时间片长度
- 总时间窗口长度（即连续统计的小窗口的总长度）
- 一个时间片内的请求限制
- 总时间窗口内的请求限制
后面两条限制不一定要同时满足，通常只需要满足总时间窗口的。
还是以 窗口边缘突发流量 为例，来看看滑动窗口的表现。做一些参数和场景设定：
- 时间片长度为 500ms，总时间窗口长度为 1000ms，总时间窗口内的请求限制为 100。
- 突发请求发生在第 1s 的后半段和第 2s 的前半段，各打来 100 个请求。
Time (ms) | 0-500 | 500-1000 | 1000-1500 | 1500-2000 | Incoming | 0 | 100 | 100 | 0 | Accepted | 0 | 100 | *0* | 0 | | | | | | [ Pass 100 ] [ Drop 100 ]
Fixed Win [ Pass 100 ][ Pass 100 ]固定窗口在边缘处放行 200 个请求，把土豆服务器打爆了。
另一边，注意看滑动窗口：当滑动窗口统计 [500, 1500] 这 1s 内的请求时，前面 [500-1000] 已经放行了 100 个请求，达到了限制，因此 [1000-1500] 打来的 100 个请求全部被拒绝。如此我们有效避免了「流量突刺」问题，保护下游服务器。
滑动窗口限流最大的优点就是平滑，即把一个尖峰磨平。（好像滑动窗口类算法都能平滑？）缺点是实现复杂。
一个具体的实现参考 Sentinel-Go源码系列（三）滑动时间窗口算法的工程实现，看了才知道远远没有理论这么简单。
分类-桶类
时间窗口类算法的核心思想是：硬性限制某段时间内的请求数量。这些算法都无法良好处理突发流量——如滑动窗口，在短时间大流量的情况下仍会丢弃请求。
桶类算法不再硬性限制请求速率，而是通过维护一个缓冲桶有效地处理突发流量，减少请求丢失。
漏桶
漏桶的原理非常简单。想象一个固定大小的漏斗（桶）：
- 开口端：请求尝试进入桶中，如果桶已满请求就被丢弃；否则进入。
- 出口端：桶以一个固定的速率漏出请求，即交给下游处理。
这样，即使在短时间内来了大量请求，桶也能缓冲住一部分，减少丢失。
确定漏桶的参数：
- 桶的容量
- 漏出速率
这么简单就不用画 ASCII 示意图了吧
令牌桶
令牌桶和漏桶的原理相近，区别只是桶里存的东西：桶里存的是令牌，而不是请求。这种算法引入一个「令牌」的概念：每个请求必须获取到一个令牌才能被处理。
- 开口端：令牌尝试进入桶中，如果桶已满令牌就被丢弃；否则进入。
- 出口端：每一个请求尝试从桶里取一个令牌，如果没有令牌，请求就被丢弃；否则被处理。
[T] | Generated at a fixed rate v ┌──────── ───────┐ │ \ [T] [T] / │ │ \ [T] [T] / │ │ \ [T] / │ │ \ / │ └──────── ───────┘ │Request needs 1 [T] ──> ┼ ───> Succeed if [T] is available | v Fail if no [T] is available, i.e. bucket is empty确定令牌桶的参数：
- 桶的容量
- 令牌生成速率
令牌桶相比漏桶的优点有两个：
- 无排队时延：一个请求要做的只是尝试查询并扣减令牌，时延短且固定。漏桶的请求则需要在桶里排队，时延不固定。
- 容许更多突发流量：即便瞬时请求速率超过令牌生成速率，桶里仍可能有先前留存的令牌，可处理突发流量；而漏桶装的就是请求，强制以固定速率漏出，无法应对瞬时高并发流量。
这可能冲击下游服务器，取决于桶的容量；但对外可用性确实更高