常见限流算法

引言

         保护高并发系统的稳定性的三把利器：缓存、降级和限流。

l  缓存：提升系统的访问速度，增大系统处理容量；

l  降级：在系统过载时提供有损服务，通过减少非核心业务，降低业务质量等措施降低系统负载；

l  限流：在系统过载时主动丢弃部分业务请求。

         而降级、限流的本质都是基于限流算法，常见的限流算法有如下4种。

计数器固定窗口算法

计数器固定窗口算法是最简单的限流算法，实现方式也比较简单。就是通过维护一个单位时间内的计数值，每当一个请求通过时，就将计数值加1，当计数值超过预先设定的阈值时，就拒绝单位时间内的其他请求。如果单位时间已经结束，则将计数器清零，开启下一轮的计数。

代码实现：https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/CounterRateLimit.java

问题：这个算法很简单，但是却有十分致命的问题，那就是临界问题，还会有突刺现象导致拒绝大部分请求。

例如：第一秒的最后200ms和第二秒的最初200ms，极有可能超过1000的阈值，但并不会被限流。

计数器滑动窗口算法

计算器滑动窗口算法就是为解决计数器固定窗口临界问题而诞生的。简单来说，把1秒切割成2段，每段独立计数，通过滑动窗口内计数器累加统计结果限流。

代码实现：https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/SlidingWindowRateLimit.java

问题：滑动窗口算法就是固定窗口算法的变种，但突刺现象仍然无法解决。不难发现，切割的片段越多，统计越精确，但若要做到平滑限流，就需要漏洞算法、令牌桶算法。

漏桶算法

漏桶算法以一个常量限制了出口流量速率，因此漏桶算法可以平滑突发的流量。其中漏桶作为流量容器我们可以看做一个FIFO的队列，当入口流量速率大于出口流量速率时，因为流量容器是有限的，当超出流量容器大小时，超出的流量会被丢弃。

算法实现：可以准备一个队列，用来保存请求，另外通过一个线程池（ScheduledExecutorService）来定期从队列中获取请求并执行，可以一次性获取多个并发执行。

代码实现：https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/LeakyBucketRateLimit.java

特点：

1)         入口流量无限制

2)         出口流量固定不变，即解决平滑限流问题

3)         桶容量固定，即限流阈值

问题：不过因为漏桶算法限制了流出速率是一个固定常量值，所以漏桶算法不支持出现突发流出流量。但是在实际情况下，流量往往是突发的。

令牌桶算法

令牌桶算法是漏桶算法的改进版，可以支持突发流量。不过与漏桶算法不同的是，令牌桶算法的漏桶中存放的是令牌而不是流量。

那么令牌桶算法是怎么突发流量的呢？

最开始，令牌桶是空的，我们以恒定速率往令牌桶里加入令牌，令牌桶被装满时，多余的令牌会被丢弃。当请求到来时，会先尝试从令牌桶获取令牌（相当于从令牌桶移除一个令牌），获取成功则请求被放行，获取失败则阻塞活拒绝请求。

算法实现：可以准备一个队列，用来保存令牌，另外通过一个线程池定期生成令牌放到队列中，每来一个请求，就从队列中获取一个令牌，并继续执行。

代码实现：https://github.com/WangJunnan/learn/blob/master/algorithm/src/main/java/com/walm/learn/algorithm/ratelimit/TokenBucketRateLimit.java

特点：

1)         入口流量固定，即解决平滑限流问题

2)         出口流量在不固定，即解决突发流量问题

3)         桶容量固定，即限流阈值

令牌桶算法限制的是平均流量，因此其允许突发流量（只要令牌桶中有令牌，就不会被限流）

总结：