聊聊限流的一些事儿

一、背景

最近几年，随着微服务的流行，服务与服务之间依赖越来越强，调用也越来越复杂，服务间的稳定性变突显出来。特别是在遇到突发请求时，常常需要通过缓存、限流、熔断降级、负载均衡等多种方式保证服务的稳定性。其中限流是不可或缺的一环。一般每一个对外提供的接口都需要做流量控制，这与保险丝的原理一样。当接口的流量请求超过核定值时就得对请求进行引流或者直接拒绝等操作。特别是在系统应对大流量，高并发的访问时，限流算法可以很好地控制流量，从而避免系统负载过高而崩溃。

二、限流算法

下面介绍的限流方式主要是窗口算法和桶算法，各有优势。

窗口算法实现简单，逻辑清晰，可以很直观的得到当前的 QPS 情况，但是会有时间窗口的临界突变问题，而且不像桶一样有队列可以缓冲；另外，在细粒度上难以对流量曲线进行调整，即不能实现削峰填谷的效果，这可能对某些需要平滑流量的场景造成问题。限流简单暴力，对于C端产品来说，这可能不是一种友好的选择。
桶算法虽然稍微复杂，不好统计 QPS 情况，但是桶算法也有优势所在。
- 漏桶模式消费速率恒定，可以很好的保护自身系统，可以对流量进行整形，但是面对突发流量不能快速响应。应用场景：自身服务调用第三方服务时，第三方服务需要我们来限制速度。
- 令牌桶模式可以面对突发流量，但是启动时会有缓慢加速的过程，不过常见的开源工具中已经对此优化。应用场景：别人调用自身服务时可以使用（毕竟对自身服务qps有一定的了解）。

限流算法	原理	优点	缺点	使用场景	流量整形	处理延时
滑动窗口	窗口在时间轴上滑动，记录请求次数	实时控制，流量较均匀	难以实现流量曲线整形，无法削峰填谷	单机或单点网关限流	否	否
漏桶	流入请求如水流入桶，满则丢弃	能够控制突发流量（主要看容量）	流出速率恒定，对突发流量反应不够快速	瞬时高并发流量场景或调第三方服务	是	是
令牌桶	以一定速率产生令牌，请求需拿令牌	可动态调整处理速度，允许突发流量在一定程序上得到满足	实现复杂，以及令牌的数量控制	别人调用自身服务控制量级	是	是

2.1 漏桶算法

漏桶算法主要目的是控制请求速率，平滑网络上的突发流量。如上图示例，固定速率流出请求，流入请求速率任意，请求是否被处理看桶中的令牌是否足够。它常用于限制网络流量、控制数据传输率等场景，但是无法应用突发的高流量。

JSF不使用此类算法的原因：

1、由于漏桶出口速度固定，不能灵活应对后端能力的提升，如后端服务动态扩容后，漏桶没有办法。

2、无法有效利用资源，服务器处理能力并不是均衡绝对的，即任意时间都是固定的，如服务处理能力为1kqps，可能前6s为2k,后面时间为500，即一小段时间服务器资源是可以承受这段请求压力的，但是漏桶算法在这种情况下会丢弃一部分请求。

2.2 令牌桶算法

令牌桶算法是另一种经典的限流算法，它的原理是将请求放入一个令牌桶中。然后按照一定速度不断地放出令牌。只有在令牌桶中有令牌时，才能够发出令牌。令牌桶算法可以控制单位时间内的请求速率，同时可以应对突发流量（累积令牌）如后端能力的提升，因为只有在足够多的令牌，才可以放请求过去。

这里思考一个问题，令牌是如何添加的？如果按照指定时间间隔添加令牌，则需要开一个线程去定时添加，当有多个接口需要限流时，线程数就会随之增加，这显然不是一个好的办法。在Guava的RateLimiter是这样做的——每次令牌获取时计算令牌是否足够：它通过存储的下一个令牌生成的时间，和当前获取令牌的时间差，再结合阈值，去计算令牌是否足够，同时再记录下一个令牌的生成时间以便下一次调用。

下面是 Guava 中 RateLimiter 类的子类 SmoothRateLimiter 的resync()方法的代码分析，可以看到其中的令牌计算逻辑。

void resync(long nowMicros) { // 当前微秒时间
    // 当前时间是否大于下一个令牌生成时间
    if (nowMicros > this.nextFreeTicketMicros) { 
        // 可生成的令牌数 newPermits = （当前时间 - 下一个令牌生成时间）/ 令牌生成时间间隔。
        // 如果 QPS 为2，这里的 coolDownIntervalMicros 就是 500000.0 微秒(500ms)
        doublenewPermits= (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
        // 更新令牌库存 storedPermits。
        this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
        // 更新下一个令牌生成时间 nextFreeTicketMicros
        this.nextFreeTicketMicros = nowMicros;
    }
}