当高并发遇到限流算法

前言

在解决系统面对高并发的场景下，有三把主要利器，分别是缓存，降级，限流。

缓存是通过提升系统访问速度和增大系统处理能力，能大幅度缓解高并发的冲击。

降级是当服务出现问题或者影响到核心流程时的性能时，需要暂时屏蔽掉，等高峰期过去或者问题解决后再打开。

限流是对稀缺资源访问时，比如秒杀，抢购的商品时，来限制并发和请求的数量，从而有效的进行削峰并使得流量曲线平滑。限流的目的是对并发访问和并发请求进行限速，或者一个时间窗口内请求进行限速从而来保护系统，一旦达到或超过限制速率就可以拒绝服务，或者进行排队等待等。

下面我们就来详细的来介绍下什么是限流，以及它有那几种手段和其思想原理。

单机限流算法

常见的限流算法有，固定时间窗口，滑动时间窗口，令牌桶算法和漏桶算法等。

（一）固定时间窗口和滑动时间窗口限流

基于固定时间窗口的限流算法是非常简单的，从某一个时间点开始之后每次接口请求到来都累加计数器，如果在当前时间窗口内，根据限流规则（比如每秒钟最大允许 100 次接口请求），累加访问次数超过限流值，则限流熔断拒绝接口请求。然后计数器清零重新计数。

这种固定时间窗口的限流算法的缺点在于，限制策略过于粗，没法很好的处理临界区。比如我们假设限制每秒的请求数不能超过1000，现在有个极端的例子，第一秒的时间窗口内，1000个请求在1秒区间的最后5ms中集中发生，第二秒的1000个请求，在第二秒区间的最左侧5ms集中发生，虽然这两个请求都符合限速定义，但是在临界区地方会出现10ms，集中访问2000次的特例，这样就有可能造成系统瘫痪，因为在流量曲线上并不平滑。

滑动窗口是对固定时间窗口的一种改动，改进后的算法可以保证任意时间窗口内都不会超过允许的最大值，这样可以让流量曲线更加平滑，但是实现滑动窗口算法会稍加复杂，并且维持的会话状态会多一点，所以相对来说会更占内存。

即便滑动时间窗口限流算法可以保证任意时间窗口内接口请求次数都不会超过最大限流值，但是仍然不能防止在细时间粒度上面访问过于集中的问题，比如上面说的所有的请求集中在5ms的区间内，也就是说基于时间窗口的限流，仅仅限制在窗口内的任意时间，对更加细粒度的时间区域其实是不做限制的。

当然，你会说我可以继续做多层级的优化，除了限制1s内的总请求数，我还可以继续追加规则，比如与10ms内的流量继续做限制，使得曲线更加平滑。这其实是治标不治本，限制的粒度过于小，其实限制本身的时间复杂度有可能就大于请求的复杂度了，得不偿失，只能采用更加高级的限流手段。

（二）令牌桶限流算法

令牌桶算法其实非常容易理解，想象一下有一个木桶，这个木桶的容量肯定是固定的，现在我们按照固定的速率例如每隔10ms向桶里面加入一个令牌token，如果桶满了，新添加的令牌就会被丢弃，如果新来了一个请求就拿走一个token，如果新来了一批请求，那就拿走一批token，如果token数目不够了，那么新来的请求就会被限流，进行排队等待或者丢弃。当然如果一段时间内没有请求到来，那么桶里的token也会按照固定的速率慢慢的增加直到桶满后溢出（丢弃）。

如图所示：

在实际开发中，我们可以直接使用Guava中RateLimiter框架，来模拟单机的令牌桶算法，一个简单的例子如下：

输出如下：

上面的代码是创建了一个桶容量为5，并且每秒增加5个令牌，也就是每200ms放入一个令牌的令牌桶，然后limiter.acquire()代表取走一个令牌，如果令牌个数足够那么直接返回，如果令牌不够就会暂停一段时间，等待每隔200ms流入的令牌，如上面的例子，后面的几个输出都接近200ms，这种实现可以将突发请求的速率平均为固定速率，并允许一定的最大并发量，最多不超过桶的容量。

（三）漏桶限流算法

漏桶算法(Leaky Bucket)是网络世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）时经常使用的一种算法，它的原理也很好理解，同样是一个木桶，我们把请求比喻成水，水可以先进入到固定容量的桶里，对于流入的速度我们不控制，反正水桶容量有限，满了就溢出丢弃，然后漏桶以固定的速率漏出水滴，当水流入速度过快时，一旦容量满就会丢弃，而出口的速率非常稳定，所以在特定场景下能够很好的控制请求量。

漏桶算法的原理还是比较简答的，其实现可以通过一个固定容量的队列来模拟水果，对写入速度不控制，但对消费速度可以控制在一个常数，比如每一秒读取1个或者n个，感兴趣的同学可以自己尝试下。

漏桶算法的图示如下：

关于令牌桶和漏桶算法的比较如下：

（1）请求何时被拒绝

令牌桶：流入速率固定，请求时如果桶中令牌不够，则拒绝新请求

漏桶：流入速率任意，当流入请求数积累到漏桶容量时，则拒绝新请求。常量固定速率流出请求。

（2）速率限制

令牌桶：限制平均流入速率，允许一定程度的突发请求（支持一次拿多个令牌）

漏桶：限制常量流出速率（流出速率是固定值），从而平滑突发流入速率

（3）丢包问题 其实丢包不丢包，完全取决于设计，这里只是对比简单场景下的说明。

令牌桶：令牌桶算法可积累发送数，桶满时会丢失令牌而不会丢失包

漏桶：当输入速率大于输出速率的时候，桶中会出现堆积，当堆积大于桶容量后会出现溢出现象，即数据丢包

分布式限流算法

前面介绍的都是单机版的限流策略，如果想在分布式下限流，通用的手段，可以借助redis+lua或者nginx+lua来实现，而限流算法本身其实就是上面介绍的几种，这里不在讨论，感兴趣的朋友可以自己研究下。

总结

本文主要对比介绍了目前主流的限流算法的原理和相关细节，限流思想非常实用，尤其是在面对高并发特定的场景下，可以极大的发挥其作用，从而为我们服务和系统提供更加可靠和健壮的保障。实际应用中常用的限流算法多为令牌桶和漏桶算法，回到文章开头，如果高并发真的遇到限流算法的时候，想我让起了，李白在《蜀道难》一文里面，描述剑阁时用的形容，真的是任你千军万马袭，我自“一夫当关，万夫莫开”。