前言
毕设的 API 模块中使用了 Guava RateLimter 进行 QPS 限流，顺便了解下常见的限流算法，主要包括令牌桶、漏桶、计数器。
漏桶算法(Leaky Bucket)
漏桶算法（Leaky Bucket）是计算机网络中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。
漏桶算法描述如下：
- 一个固定容量的漏桶，按照常量固定速率流出水滴（请求）
- 如果桶是空的，则不需流出水滴
- 可以以任意速率流入水滴到
- 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。
令牌桶算法(Token Bucket)
从某种意义上讲，令牌桶算法是对漏桶算法的一种改进，桶算法能够限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。
令牌桶算法是一个存放固定容量令牌（token）的桶，按照固定速率往桶里添加令牌。令牌桶的主要概念如下：
- 令牌按固定的速率被放入令牌桶中
- 桶中最多存放 n 个令牌，当桶满时，新添加的令牌被丢弃或拒绝
- 请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除
- 令牌桶根据放令牌的速率来控制访问的速率
可以准备一个队列，用来保存令牌，另外通过一个线程池定期生成令牌放到队列中，每来一个请求，就从队列中获取一个令牌，并继续执行。
Guava RateLimiter
Guava RateLimiter 中的令牌桶算法实现是 SmoothBursty，另一个实现 SmoothWarmingUp 则是漏桶算法。需要注意的是 SmoothBursty 中默认时间窗口仅能为 1s。
SmoothBursty 最大的特点在于允许瞬间的流量波峰超过 QPS，但瞬间过后的请求将会等待较长的时间来缓解上次的波峰，以使得平均的 QPS 等于预定值。原理是 SmoothBursty 有一个可以放 N 个时间窗口产生的令牌的桶，系统空闲的时候令牌会一直积攒，最好情况下可以扛 N 倍限流值的突发高峰而不影响后续请求。
令牌桶和漏桶的比较
| 令牌桶 | 漏桶 | |
|---|---|---|
| 请求何时拒绝 | 固定速率往桶中添加令牌，如果桶中令牌不够，则拒绝新请求 | 流入请求速率任意，常量固定速率流出请求。当流入请求数积累到漏桶容量时，则拒绝新请求 |
| 速率限制 | 限制平均流入速率，允许一定程度的突发请求（支持一次拿多个令牌） | 限制常量流出速率（流出速率是固定值），从而平滑突发流入速率 |
| 丢包问题 | 令牌桶算法可积累发送数，桶满时会丢失令牌而不会丢失包 | 当输入速率大于输出速率的时候，桶中会出现堆积，当堆积大于桶容量后会出现溢出现象，即数据丢包 |
计数器
计数器算法是限流算法里最简单也是最容易实现的一种算法。
例如，限制某接口的 1 秒内访问次数不能超过100次，则：
- 设置一个 1s 的滑动窗口，窗口有 100 个格子，每个格子 10ms，每 10ms 移动一次，每次移动都记录当前服务请求的次数。
内存中保存最近10次的次数（LinkedList）。格子每次移动的时候判断一次，最后一个格子和第一个格子的次数是否相差100，如果超过，则进行限流。
当格子划分的越多，那么滑动窗口的滚动越平滑，限流的统计就会越精确。
集群限流
以上的限流都是在单机上的限流，若要在集群中针对某个资源进行限流，则需要第三方如 Redis 进行计数。
比如，当访问某个接口/资源时，使用 Redis 的 incr 命令，并设置过期时间。