实现限流的几种方案
4月 4, 2021
限流是服务在高并发的情况下，通过限制处理请求的速率，以达到保证服务不过载的目的，实现高可用和稳定性的目标。限流的方案一般有计数法、滑动窗口、漏桶、令牌桶几种，其中各有各的特点，通常需要根据场景采用不同的方案。
计数法 #
相对于滑动窗口，计数法也叫固定窗口。就是说接口在固定时间内的访问次数不能超过多少个，在实现的时候，假设限流为每分钟 100 个请求，设置一个开始时间 start 和计数器 counter，每有一个请求 counter++，如果 counter 大于 100 并且此时与开始时间相比小于 1 分钟，则触发限流；如果 counter 大于 100 并且与开始时间相比大于 1 分钟，则重置开始时间 start 和 counter 的值。
计数法存在的一个比较严重的问题就是临界点问题，如果有恶意用户在第一个时间段的最后一秒钟触发 100 个请求，在第二个时间段的第一秒钟触发了 100 个请求，那么在短短一秒内其实服务器收到了 200 个请求，并没有触发限流，这种就可能会对服务造成影响。
滑动窗口 #
针对固定窗口的问题进行优化，就产生了滑动窗口的方案。滑动窗口最核心的思想在于，任何时间段的 1 分钟，最多都是 100 个请求。滑动窗口把 100 个请求分摊到了每一个格子，成个格子就是 10 秒钟，就是 6 个格子。counter 值就是可滑动的 6 个格子的总和。
当遇到恶意用户再次在 00:59 请求时，服务可以成功处理 100 个请求，可是到 1:00 时触发 100 个请求时，由于窗口的滑动，counter 总数已经到了第 2- 第7 个格子的和，counter 得到 200 个请求从而触发了限流。可见滑动窗口的时间段永远是最新的 “1 分钟”。只要格子分的粒度足够细，限流实现的精度就越高。
通常考虑使用 Redis 的 zset 结构来实现滑动窗口限流功能。
漏桶（Leaky Bucket） #
漏桶算法很形象，就是一个漏桶，它的桶里是请求的流量，然后按照固定速率漏掉的水滴（看到固定速率我们就知道肯定像固定窗口一样，有更优解了，我们下面会继续说）。漏掉的水滴，就是服务的处理速度，我们发现漏桶的特点很明显：
- 可以任意速率接收大量请求，瞬间也可以。
- 容量是固定的，超出了就会触发限流；
- 流量的处理速度是匀速的。
这种特性，特别适合有生产者-消费者的场景，Uber 针对漏桶开源了一个 go语言的包 uber-go/ratelimit，源码实现可以参考这篇博客。
令牌桶（Token Bucket） #
令牌桶限流可能是实际工作中最可能遇到的方式了，与漏桶最大不同的是，令牌桶不是以匀速来处理流量的，而装的是令牌，如下图，生成令牌的速度是恒定的，每有一个请求过来时，会从桶里取走一个令牌，当桶里没有令牌时，则触发限流。
可见，令牌桶即可以处理一定程度的突发流量（漏桶），也可以解决滑动时间段计数问题（滑动窗口），它拥有其他几个限流算法的优点，复杂度就是多了一个“令牌”的概念。
Go 扩展库也提供了一个基于令牌桶算法的限流器实现 time/rate，在 Go 的官方实现里面，有针对令牌桶做了优化，比如生成令牌的速率不一定是匀速的，具体实现可以参考这篇博客。下面简单介绍下使用：
安装方法
go get golang.org/x/time/rate
初始化
// 每秒放入 10 个 token，桶的容量为 1
limiter := NewLimiter(10, 1);
// Every 表示放入 token 速率时间粒度;
limit := Every(100 * time.Millisecond);
limiter := NewLimiter(limit, 1);
触发限流时有三种处理方式：
- wait
- allow
- reserve
Wait/WaitN 示例 #
Wait 获取 token 时如果数组不足(小于N)，将会阻塞一段时间，直至 token 满足条件, 如果充足则直接返回，阻塞时间可以通过 context 设置。
func main() {
limiter := rate.NewLimiter(10, 1)
ctx, _ := context.WithCancel(context.TODO())
for {
l.Wait(ctx)
time.Sleep(200 * time.Millisecond)
fmt.Println(time.Now().Format("2016-01-02 15:04:05.000"))
}
}
Allow/AllowN 示例 #
Allow获取 token 充足返回 true，同时 token 减少，否则返回 false，不会阻塞。
Reserve/ReserveN 示例 #
ReserveN 的用法就相对来说复杂一些，当调用完成后，无论 Token 是否充足，都会返回一个 Reservation 对象。
func (r *Reservation) OK() bool // 判断是否获取到token
// Delay is shorthand for DelayFrom(time.Now()).
func (r *Reservation) Delay() time.Duration // 获取延迟等待时间,此时Cancel不起作用
func (r *Reservation) DelayFrom(now time.Time) time.Duration
// Cancel is shorthand for CancelAt(time.Now()).
func (r *Reservation) Cancel() // 取消，将获取的Token重新放入桶中
func (r *Reservation) CancelAt(now time.Time)