接口限流算法有哪些？？

0x01：限流

限流顾名思义，提前对各个类型的请求设置最高的QPS阈值，若高于设置的阈值则对该请求直接返回，不再调用后续资源。限流需要结合压力测等，了解系统的最高水位，也是在实际开发中应用最多的一种稳定性保障手段。

应用场景：如秒杀、抢购、发帖、评论、恶意爬虫等。

0x02：限流算法的三种实现

实际应用时，不大可能在单机执行限流。实际限流可以考虑在 Nginx 层对请求限流，或者如果真的要自己在业务方实现一套限流策略的话，可以考虑基于 Redis 实现分布式限流策略。并且在实际应用中，可能还会基于不同的维度进行限流，如用户 id，请求 IP 等，实际应用需要考虑的东西更多。

• 计数器

计数器法是限流算法里最简单也是最容易实现的一种算法。

假设一个接口限制一分钟内的访问次数不能超过100个，维护一个计数器，每次有新的请求过来，计数器加一，这时候判断，如果计数器的值小于限流值，并且与上一次请求的时间间隔还在一分钟内，允许请求通过，否则拒绝请求；如果超出了时间间隔，要将计数器清零。

计数器限流可以比较容易的应用在分布式环境中，用一个单点的存储来保存计数值，比如用Redis，并且设置自动过期时间，这时候就可以统计整个集群的流量，并且进行限流。计数器方式的缺点是不能处理临界问题，或者说限流策略不够平滑。

假设在限流临界点的前后，分别发送100个请求，实际上在计数器置0前后的极短时间里，处理了200个请求，这是一个瞬时的高峰，可能会超过系统的限制。计数器限流允许出现 2*permitsPerSecond 的突发流量，可以使用滑动窗口算法去优化。

• 滑动窗口计数器

滑动窗口其实就是细分之后的计数器！

这样假设，先把一分钟划分成6段！也就是10s一个段，在第一段里，假如请求61次，那么直接触发了规则，肯定就过不去了；如果只请求了1次，则是正常的。当时间走到第二个段里，即10s~20s这段范围里，请求数不能超过总的限定条件，且当前段的请求数量 加上之前段的总数量也不能超过总限定数量。当时间到了50s~60s，依然是一样。

如果过了60s，所以请求数都是正常的；则把划分段往右移一段。那么此时的6个分段是 10 ~ 20、20 ~ 30、30 ~ 40、40 ~ 50、50 ~ 60、60 ~ 70，然后统计规则还跟上面一样。所以只有划分的越细，请求限制越平滑。

• 漏桶算法

漏桶(Leaky Bucket)算法思路很简单，水(请求)先进入到漏桶里,先触发出水，给漏斗腾出空间，漏桶会以一定的速度出水(接口有响应速率)，当水流入速度过大会直接溢出(访问频率超过接口响应速率)，然后就拒绝请求，可以看出漏桶算法能强行限制数据的传输速率.示意图如下：

• 令牌桶

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法，更加容易理解。随着时间流逝，系统会按恒定1/QPS时间间隔(如果QPS=100，则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水)，如果桶已经满了就不再加了。新请求来临时，会各自拿走一个Token，如果没有Token可拿了就阻塞或者拒绝服务。

令牌桶的另外一个好处是可以方便的改变速度。一旦需要提高速率,则按需提高放入桶中的令牌的速率。一般会定时(比如100毫秒)往桶中增加一定数量的令牌，有些变种算法则实时的计算应该增加的令牌的数量。

0x04： 漏桶和令牌桶的比较

这两种算法的主要区别在于漏桶算法能够强行限制数据的传输速率，而令牌桶算法在能够限制数据的平均传输速率外，还允许某种程度的突发传输。

在令牌桶算法中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，因此它适合于具有突发特性的流量。

漏桶和令牌桶算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。

主要区别在于令牌桶允许一定程度的突发，漏桶主要目的是平滑流入速率，考虑一个临界场景，令牌桶内积累了100个token，可以在一瞬间通过，但是因为下一秒产生token的速度是固定的，所以令牌桶允许出现瞬间出现permitsPerSecond的流量，但是不会出现2*permitsPerSecond的流量，漏桶的速度则始终是平滑的。