限流算法

什么是限流，为什么要限流？

常见的限流算法有3类：计数器算法、 令牌桶算法、 漏桶算法

(1) 计数器算法

(1.1) 普通计数器算法

假设系统每秒能同时处理100个请求，保存一个计数器，如果开始处理一个请求，计数器加一，请求处理完毕之后计数器减一。

每次请求来的时候看看计数器的值，如果超过阈值要么拒绝。

计数器的值要是存内存中就算单机限流算法。存在分布式存储中，集群机器访问就算分布式限流算法。

缺点就是：假设我们允许的阈值是1万，此时计数器的值为0， 当1万个请求在前1秒内一股脑儿的都涌进来，这突发的流量可是顶不住的。
缓缓的增加处理和一下子涌入对于程序来说是不一样的。

(1.1) 固定窗口限流

它相比于计数限流主要是多了个时间窗口的概念。计数器每过一个时间窗口就重置。

(1.1.1) 定义

规则如下：

请求次数小于阈值，允许访问并且计数器 +1；
请求次数大于阈值，拒绝访问；
这个时间窗口过了之后，计数器清零；

(1.1.2) 问题

固定窗口临界问题
系统每秒最多接受100个请求
假设有一个恶意用户，他在09:59:800时，瞬间发送了100个请求，并且10:00:000又瞬间发送了100个请求，那么其实这个用户在1秒里面，瞬间发送了200个请求。

通过在时间窗口的重置节点处突发请求，可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？

(1.2) 滑动窗口算法

相对于固定窗口，滑动窗口除了需要引入计数器之外还需要记录时间窗口内每个请求到达的时间点，因此对内存的占用会比较多。

(1.2.1) 定义

将时间窗口进行划分，每过一个时间单位，时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter

规则如下，假设时间窗口为1秒：

记录每次请求的时间
统计每次请求的时间 至 往前推1秒这个时间窗口内请求数，并且 1 秒前的数据可以删除。
统计的请求数小于阈值就记录这个请求的时间，并允许通过，反之拒绝。

1s有1000ms，我们把1秒分成5个时间窗口，一个时间窗口就是200ms。
每过200ms，我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在09:59:800的时候到达，那么800~1000对应的counter就会加1。

(1.2.2) 短时间内的流量攻击

但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。

我们所想的限流场景，例如每秒限制100个请求。希望请求每 10ms 来一个，这样我们的流量处理就很平滑，但是真实场景很难控制请求的频率。因此可能存在 5ms 内就打满了阈值的情况。

当然对于这种情况还是有变型处理的，例如设置多条限流规则。不仅限制每秒100个请求，再设置每10ms不超过 2 个。

(1.2.3) 滑动窗口与TCP滑动窗口

这个滑动窗口可与TCP的滑动窗口不一样。TCP的滑动窗口是接收方告知发送方自己能接多少“货”，然后发送方控制发送的速率。

(2) 令牌桶算法

所有的请求在处理之前都需要拿到一个可用的令牌才会被处理
1、所有的请求在处理之前都需要拿到一个可用的令牌才会被处理；
2、根据限流大小，设置按照一定的速率往桶里添加令牌；
3、桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝；
4、请求达到后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除；
5、令牌桶有最低限额，当桶中的令牌达到最低限额的时候，请求处理完之后将不会删除令牌，以此保证足够的限流；

应对突发流量的时候令牌桶表现的更佳。

假设服务没预热，那是不是上线时候桶里没令牌？没令牌请求过来不就直接拒了么？这就误杀了，明明系统没啥负载现在。

(3) 漏桶算法

漏桶算法，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

定义

请求来了放入桶中
桶内请求量满了拒绝请求
服务定速从桶内拿请求处理

面对突发请求，漏桶算法的处理速度和平时是一样的，这其实不是我们想要的。
拿漏桶来说，漏桶中请求是暂时存在桶内的。这其实不符合互联网业务低延迟的要求。

(4) 总结

漏桶和令牌桶其实比较适合阻塞式限流场景，即没令牌我就等着，这就不会误杀了，而漏桶本就是等着。比较适合后台任务类的限流。
基于时间窗口的限流比较适合对时间敏感的场景，请求过不了您就快点儿告诉我。

参考资料

[1] 5种限流算法，7种限流方式，挡住突发流量？
[2] 图解+代码|常见限流算法以及限流在单机分布式场景下的思考
[3] 三种常见的限流算法