常用的限流算法

简单计数

计数器算法是使用计数器在周期内累加访问次数，当达到设定的阈值时，触发限流策略。下一个周期开始时，进行清零，重新计数。比如 1 分钟内限制请求总数为 100。如果超过 100 则返回失败。

滑动窗口计数

简单计数然简单，但是有一个致命的问题，即临界问题。比如 1 分钟内限制请求总数为 100 的场景下，前一个一分钟内直到这一分钟快结束的时候才来了 100 个请求，而后一个一分钟刚开始就立即来了 100 个请求。虽然是在两个不同的一分钟区间，但是事实上不到一分钟的时间内，来了 200 个请求，因此计数器限流失效。

滑动窗口算法是将时间周期进一步划分为 N 个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。 如下图，假设时间周期为 1min，将 1min 再分为 6 个小周期，统计每个小周期的访问数量。如果第 6 个小周期内，访问数量为 100，到了第 7 个小周期内，访问数量也为 100，那么 即触发滑动窗口(红色虚线框出)内的访问次数限制。由此可见，滑动窗口的单位区间划分越多，滑动窗口的滚动就越平滑，限流统计就会越精确。

漏斗桶

漏斗桶算法顾名思义，算法内部有一个容器，类似生活中的漏斗。当请求进来时，相当于水倒入漏斗，然后从下方出水口匀速流出。不管进水速率如何增减，出水速率始终保持一致，直到漏桶为空。由于进水速度未知，突发流量来不及处理就会在桶中累积。如果突破了桶容量就会溢出，即丢弃请求。漏斗桶的示意图如下：

令牌桶

令牌桶算法某种程度上是对漏斗桶算法的改进。令牌桶能够在限制请求平均速率的同时还允许一定程度的突发调用。在令牌桶算法中，存在一个桶，用来存放固定数量的令牌。该算法以一定的速率往桶中放入令牌。每次请求需要先获取到桶中的令牌才能继续执行，否则等待可用的令牌，或者直接拒绝。

放令牌的动作是持续不断进行的，如果桶中令牌数达到上限，则丢弃令牌，因此桶中可能一直持有大量的可用令牌。此时请求进来可以直接拿到令牌执行。比如设置 qps 为 100，那么限流器初始化完成 1 秒后，桶中就已经有 100 个令牌了，如果此前还没有请求过来，这时突然来了 100 个请求，该限流器可以抵挡瞬时的 100 个请求。由此可见，只有桶中没有令牌时，请求才会进行等待，最终表现的效果即为以一定的速率执行。令牌桶的示意图如下：