学习笔记：常见的分布式限流解决方案（一）之限流概念、基于Guava RateLimiter的客户端限流

1、分布式限流

1.1、限流的概念

对于限流场景，一般需要考虑两个维度的信息：

时间
限流基于某段时间范围或者某个时间点，也就是我们常说的“时间窗口”，比如对每分钟、每秒钟的时间窗口做限定
资源
基于可用资源的限制，比如设定最大访问次数，或最高可用连接数。

限流就是在某个时间窗口对资源访问做限制，比如设定每秒最多100个访问请求。在实际的业务场景中，一般都是多种限流规则同时使用，主要的几种限流规则如下：

其中，

QPS（query per second）和连接数控制
针对上图中的连接数和QPS限流来说，我们可以设定IP维度的限流，也可以设置基于单个服务器的限流。在真实环境中通常会设置多个维度的限流规则，比如设定同一个IP每秒访问频率小于10，连接数小于5，再设定每台机器QPS最高1000，连接数最大保持200。更进一步，我们可以把某个服务器组或整个机房的服务器当做一个整体，设置更high-level的限流规则，这些所有限流规则都会共同作用于流量控制。
传输速率
对于“传输速率”大家都不会陌生，比如资源的下载速度。有的网站在这方面的限流逻辑做的更细致，比如普通注册用户下载速度为100k/s，购买会员后是10M/s，这背后就是基于用户组或者用户标签的限流逻辑。
黑白名单
黑白名单是各个大型企业应用里很常见的限流和放行手段，而且黑白名单往往是动态变化的。举个例子，如果某个IP在一段时间的访问次数过于频繁，被系统识别为机器人用户或流量攻击，那么这个IP就会被加入到黑名单，从而限制其对系统资源的访问，这就是我们俗称的“封IP”。

1.2、分布式限流

分布式限流，区别于单机限流，它把整个分布式环境中所有服务器当做一个整体来考量。比如说针对IP的限流，我们限制了1个IP每秒最多10个访问，不管来自这个IP的请求落在了哪台机器上，只要是访问了集群中的服务节点，那么都会受到限流规则的制约。

为了实现分布式限流，我们需要将限流信息保存在一个“中心化”的组件上，这样它就可以获取到集群中所有机器的访问状态。

2、常见的限流方案

基于Guava的客户端限流
Guava是一个客户端组件，在其多线程模块下提供了以RateLimiter为首的几个限流支持类。它只能对“当前”服务进行限流，即它不属于分布式限流的解决方案。
网关层限流
服务网关，作为整个分布式链路中的第一道关卡，承接了所有用户来访请求。我们在网关层进行限流，就可以达到了整体限流的目的了。目前，主流的网关层有以软件为代表的Nginx，还有Spring Cloud中的Gateway和Zuul这类网关层组件，也有以硬件为代表的F5。
中间件限流
将限流信息存储在分布式环境中某个中间件里（比如Redis缓存），每个组件都可以从这里获取到当前时刻的流量统计，从而决定是拒绝服务还是放行流量。
限流组件
目前也有一些开源组件提供了限流的功能，比如Sentinel就是一个不错的选择。Sentinel是阿里出品的开源组件，并且包含在了Spring Cloud Alibaba组件库中。Hystrix也具有限流的功能。

3、常见限流算法

常见的限流算法有：令牌桶算法、漏桶算法、滑动窗口和计数器算法等。

3.1、令牌桶算法（Token Bucket）

令牌桶算法是目前应用最为广泛的限流算法。它有以下两个关键角色：

令牌获取到令牌的Request才会被处理，其他Requests要么排队要么被直接丢弃
桶用来装令牌的地方，所有Request都从这个桶里面获取令牌

令牌桶算法实现原理

令牌桶算法算法主要包括了令牌生成和令牌获取两个步骤。其中，

令牌生成
这个流程涉及到令牌生成器和令牌桶。令牌桶是一个装令牌的地方，令牌桶所能容纳的令牌数量是有限度的。对于令牌生成器来说，它会根据一个预定的速率向桶中添加令牌，比如我们可以配置让它以每秒100个请求的速率发放令牌，或者每分钟50个。
注意这里的发放速度是匀速，也就是说这50个令牌并非是在每个时间窗口刚开始的时候一次性发放，而是会在这个时间窗口内匀速发放。
令牌发放器就是一个水龙头，假如在下面接水的桶子满了，那么自然这个水（令牌）就流到了外面。在令牌发放过程中也一样，令牌桶的容量是有限的，如果当前已经放满了额定容量的令牌，那么新来的令牌就会被丢弃掉。
令牌获取
每个访问请求到来后，必须获取到一个令牌才能执行后面的逻辑。假如令牌的数量少，而访问请求较多的情况下，一部分请求自然无法获取到令牌，那么这个时候我们可以设置一个“缓冲队列”来暂存这些多余的令牌。
缓冲队列其实是一个可选的选项，并不是所有应用了令牌桶算法的程序都会实现队列。当有缓存队列存在的情况下，那些暂时没有获取到令牌的请求将被放到这个队列中排队，直到新的令牌产生后，再从队列头部拿出一个请求来匹配令牌。
当队列已满的情况下，这部分访问请求将被丢弃。在实际应用中我们还可以给这个队列加一系列的特效，比如设置队列中请求的存活时间，或者将队列改造为PriorityQueue，根据某种优先级排序，而不是先进先出。算法是死的，人是活的，先进的生产力来自于不断的创造，在技术领域尤其如此。

3.2、漏桶算法（Leaky Bucket）

漏桶算法的前半段和令牌桶类似，但是操作的对象不同，令牌桶是将令牌放入桶里，而漏桶是将访问请求的数据包放到桶里。同样的是，如果桶满了，那么后面新来的数据包将被丢弃。

漏桶算法的后半程是有鲜明特色的，它永远只会以一个恒定的速率将数据包从桶内流出。打个比方，如果我设置了漏桶可以存放100个数据包，然后流出速度是1s一个，那么不管数据包以什么速率流入桶里，也不管桶里有多少数据包，漏桶能保证这些数据包永远以1s一个的恒定速度被处理。

漏桶 vs 令牌桶的区别

根据它们各自的特点不难看出来，这两种算法都有一个“恒定”的速率和“不定”的速率。令牌桶是以恒定速率创建令牌，但是访问请求获取令牌的速率“不定”，反正有多少令牌发多少，令牌没了就干等。而漏桶是以“恒定”的速率处理请求，但是这些请求流入桶的速率是“不定”的。

从这两个特点来说，漏桶的天然特性决定了它不会发生突发流量，就算每秒1000个请求到来，那么它对后台服务输出的访问速率永远恒定。而令牌桶则不同，其特性可以“预存”一定量的令牌，因此在应对突发流量的时候可以在短时间消耗所有令牌，其突发流量处理效率会比漏桶高，但是导向后台系统的压力也会相应增多。

3.3、滑动窗口（Rolling Window）

上图中黑色的大框就是时间窗口，我们设定窗口时间为5秒，它会随着时间推移向后滑动。我们将窗口内的时间划分为五个小格子，每个格子代表1秒钟，同时这个格子还包含一个计数器，用来计算在当前时间内访问的请求数量。那么这个时间窗口内的总访问量就是所有格子计数器累加后的数值。

比如说，我们在每一秒内有5个用户访问，第5秒内有10个用户访问，那么在0到5秒这个时间窗口内访问量就是15。如果我们的接口设置了时间窗口内访问上限是20，那么当时间到第六秒的时候，这个时间窗口内的计数总和就变成了10，因为1秒的格子已经退出了时间窗口，因此在第六秒内可以接收的访问量就是20-10=10个。

滑动窗口其实也是一种计算器算法，它有一个显著特点，当时间窗口的跨度越长时，限流效果就越平滑。打个比方，如果当前时间窗口只有两秒，而访问请求全部集中在第一秒的时候，当时间向后滑动一秒后，当前窗口的计数量将发生较大的变化，拉长时间窗口可以降低这种情况的发生概率

3.4、计数器算法

除了前面提到的滑动窗口这种计数器算法，一般还会采用更加简单粗暴的方式进行限流，直接限制一段时间能够通过的请求数，比如限流qps为100/min。

3.4.1、访问量限流（通过限制单位时间段内调用量来限流）

确定方法的最大访问量MAX，每次进入方法前计数器+1，将结果和最大并发量MAX比较，如果大于等于MAX，则直接返回；如果小于MAX，则继续执行。

优缺点：

对于访问量限流这种限流方式，实现简单，适用于大多数场景，阈值可以通过服务端来动态配置，甚至可以当做业务开关来使用

但也有一定的局限性，因为我们的阈值是通过分析单位时间段内调用量来设置的，如果它在单位时间段的前几秒就被流量突刺消耗完了，将导致该时间段内剩余的时间内该服务“拒绝服务”，可以将这种现象称为“突刺现象”。

3.4.2、并发量限流（通过限制系统的并发调用程度来限流）

确定方法的最大并发量MAX，每次进入方法前计数器+1，将结果和最大并发量MAX比较，如果大于等于MAX，则直接返回；如果小于MAX，则继续执行；退出方法后计数器-1。比如限制服务的并发访问数是100，而服务处理的平均耗时是10毫秒，那么1分钟内，该服务平均能提供( 1000 / 10 ) * 60 * 100 = 6000 次

优缺点：
并发量限流一般用于对于服务资源有严格限制的场景，但是某个服务在业务高峰期和低峰期的并发量很难评估，这给并发阈值的设置带来了困难，但我们可以通过线上业务的监控数据来逐步对并发阈值进行调优，只要肯花时间，我们总能找到一个即能保证一定服务质量又能保证一定服务吞吐量的合理并发阈值，从表面上看并发量限流似乎很有用，但也不可否认，它仍然可以造成流量尖刺，即每台服务器上该服务的并发量从0上升到阈值是没有任何“阻力”的，这是因为并发量考虑的只是服务能力边界的问题。

4、基于Guava RateLimiter的客户端限流

Guava的限流基于令牌桶算法实现，提供了平滑突发限流方案和平滑预热限流两种方式。

4.1、平滑突发限流

平滑突发限流，具备以下特点：

以固定的速率生成令牌
RateLimiter使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。
RateLimiter在没有足够令牌发放时，采用滞后处理的方式，也就是前一个请求获取令牌所需等待的时间由下一次请求来承受，也就是代替前一个请求进行等待。

4.2、平滑预热限流

平滑预热限流，是在平滑突发限流的基础上，增加了带有预热期的一种平滑限流，即它启动后会有一段预热期，逐步将分发频率提升到配置的速率。

平滑预热限流，通过动态调整令牌发放速度，可以让流量变化更加平滑。假设，现在有一个接口，限定100QPS，当前如果没有请求到来，令牌桶就会有100个令牌，如果突发的到来100个请求，这个时候就会瞬间消耗掉令牌，并产生较大的冲击力。而平滑预热限流，则可以根据桶内的令牌数量动态控制令牌的发放速率，让忙时流量和闲时流量可以互相平滑过渡。

其中，横坐标是令牌桶的当前容量，纵坐标是令牌发放速率。在横坐标上，有两个关键坐标：“令牌桶最大容量”和“Half容量”，它们会影响令牌的发送速率。纵坐标，则有三个重要坐标点：稳定时间间隔，2倍间隔，3倍间隔，间隔表示发放两个个令牌的时间间隔。其中，稳定间隔就是一个基准时间间隔，假设，我们设置了每秒10个令牌的限流规则，那么稳定间隔也就是1s/10=0.1秒，即每隔0.1秒发一个令牌。而，3倍间隔的数值是用稳定间隔乘以系数3，即，3倍间隔就是0.3秒。

两种场景会导致横坐标的变化

闲时流量流量较小或者压根没流量的时候，横坐标会逐渐向右移动，表示令牌桶中令牌数量增多，这个时候，令牌的放行速率会降低
忙时流量当访问流量增大的时候，横坐标向左移动，令牌桶中令牌数量变少，令牌的放行速率会提高。

4.3、实践

4.3.1、准备

这里提供了一个getTokenByNewThread()方法，是模拟了消耗令牌的方法，可以设置多线程、消耗令牌数、获取令牌次数等。

public class RateLimiterDemo {

    public static void main(String[] args) {
    	//根据测试内容，调整调用方法
        RateLimiterDemo.testSmoothBursty();
    }
   
	/**
     * 模拟，多线程，消耗令牌
     * @param threadNum 线程数量
     * @param tokenNum 每个线程一次消耗的令牌数
     * @param count 获取几次令牌
     * @param r 限流对象
     */
    public static void getTokenByNewThread(int threadNum, int tokenNum, int count, RateLimiter r){

        for(int i= 0; i < threadNum; i++){
            new Thread(new Runnable() {
                @Override
                public void run() {
                    for(int k = 0; k < count; k++){
                        System.out.println(Calendar.getInstance().getTime() + " " + Thread.currentThread().getName()
                                + " get tokens: " + r.acquire());
                    }
                }
            }).start();
        }
    }
}

4.3.2、平滑突发限流

 /**
     * 平滑突发限流，
     * 1、以固定的速率生成令牌
     * 2、RateLimiter使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。
     * 3、RateLimiter在没有足够令牌发放时，采用滞后处理的方式，也就是前一个请求获取令牌所需等待的时间由下一次请求来承受，也就是代替前一个请求进行等待。
     */
    public static void testSmoothBursty() {
        RateLimiter r = RateLimiter.create(2);
        RateLimiterDemo.getTokenByNewThread(1,1,5, r);
    }

这里创建了一个限流器，每秒产生2个令牌，即0.5秒产生一个令牌。我们假设一个线程，一次消耗一个令牌，连续消耗五次，打印结果如下，说明限流器以每秒产生两个令牌的固定速率生成令牌。

Sat Feb 20 11:11:13 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 11:11:13 CST 2021 Thread-1 get tokens: 0.460514
Sat Feb 20 11:11:13 CST 2021 Thread-1 get tokens: 0.497051
Sat Feb 20 11:11:14 CST 2021 Thread-1 get tokens: 0.499428
Sat Feb 20 11:11:14 CST 2021 Thread-1 get tokens: 0.498949

假设，限流器和消耗线程不变，我们在开始消耗线程前，先休眠了3秒，再开始消耗，输出如下。说明RateLimiter使用令牌桶算法，会进行令牌的累积，如果获取令牌的频率比较低，则不会导致等待，直接获取令牌。那么，三秒应该产生6个令牌，为什么后面有开始需要等待了呢？这是因为限流器，默认可以存储的令牌数为一秒产生的令牌数量，所以，超过这个数量的令牌也会被丢弃。

 public static void testSmoothBursty() {
     RateLimiter r = RateLimiter.create(2);

     try {
         Thread.sleep(1000 * 3);
     } catch (Exception e) {
         e.printStackTrace();
     }
     RateLimiterDemo.getTokenByNewThread(1,1,5, r);
 }
 
/*打印结果：
Sat Feb 20 11:31:27 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 11:31:27 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 11:31:27 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 11:31:27 CST 2021 Thread-1 get tokens: 0.498489
Sat Feb 20 11:31:27 CST 2021 Thread-1 get tokens: 0.498442
*/

假设，限流器不变，调整令牌消耗线程：6个线程（尽量保证同时消耗令牌），每个线程每次消耗2个令牌（限流器一秒产生一个），消耗一次，打印结果如下，说明RateLimiter在没有足够令牌发放时，采用滞后处理的方式，也就是前一个请求获取令牌所需等待的时间由下一次请求来承受，也就是代替前一个请求进行等待。

 public static void testSmoothBursty() {
     RateLimiter r = RateLimiter.create(1);
      RateLimiterDemo.getTokenByNewThread(6,2,1, r);
  }
/*打印结果：
Sat Feb 20 11:41:23 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 11:41:23 CST 2021 Thread-4 get tokens: 0.966329
Sat Feb 20 11:41:23 CST 2021 Thread-7 get tokens: 1.964799
Sat Feb 20 11:41:23 CST 2021 Thread-2 get tokens: 2.962133
Sat Feb 20 11:41:23 CST 2021 Thread-3 get tokens: 3.962082
Sat Feb 20 11:41:23 CST 2021 Thread-6 get tokens: 4.962072
*/

4.3.3、平滑预热限流

 /**
  * 平滑预热限流，带有预热期的平滑限流，即它启动后会有一段预热期，逐步将分发频率提升到配置的速率。
  */
public static void testSmoothwarmingUp() {
     RateLimiter r = RateLimiter.create(2, 3, TimeUnit.SECONDS);
     RateLimiterDemo.getTokenByNewThread(1,2,8, r);
 }

预热限流，这里首先是创建了一个预热限流器，每秒产生2个令牌，不过有3秒的预热时间，这个时候，创建一个消费线程，消费8次，打印结果如下，刚开始需要阻塞的实际比较长，后续逐渐趋于稳定。

Sat Feb 20 13:28:29 CST 2021 Thread-1 get tokens: 0.0
Sat Feb 20 13:28:29 CST 2021 Thread-1 get tokens: 1.33173
Sat Feb 20 13:28:31 CST 2021 Thread-1 get tokens: 0.994883
Sat Feb 20 13:28:32 CST 2021 Thread-1 get tokens: 0.66637
Sat Feb 20 13:28:32 CST 2021 Thread-1 get tokens: 0.499793
Sat Feb 20 13:28:33 CST 2021 Thread-1 get tokens: 0.49911
Sat Feb 20 13:28:33 CST 2021 Thread-1 get tokens: 0.499754
Sat Feb 20 13:28:34 CST 2021 Thread-1 get tokens: 0.499107

4.3.4、阻塞 or 非阻塞

前面的示例，我们获取令牌的方法都是使用了r.acquire()方式，该方法是阻塞方法，即获取不到令牌会一直等到，RateLimiter还提供了一种非阻塞的方式，r.tryAcquire()方法，如果获取不到令牌，会直接返回false。

 public static void testNonBlock(){
    RateLimiter r = RateLimiter.create(2);
     while (true) {
         try {//为了避免不停的打印日志
             Thread.sleep(500 * 1);
         } catch (Exception e) {
             e.printStackTrace();
         }
         System.out.println(Calendar.getInstance().getTime() + "get tokens: " + r.tryAcquire(3));
     }
 }

通过tryAcquire()方式获取令牌，获取城管直接返回true，失败则返回false。

Sat Feb 20 13:37:34 CST 2021get tokens: true
Sat Feb 20 13:37:35 CST 2021get tokens: false
Sat Feb 20 13:37:35 CST 2021get tokens: true
Sat Feb 20 13:37:36 CST 2021get tokens: false
Sat Feb 20 13:37:36 CST 2021get tokens: false
Sat Feb 20 13:37:37 CST 2021get tokens: true
Sat Feb 20 13:37:37 CST 2021get tokens: false
Sat Feb 20 13:37:38 CST 2021get tokens: false
Sat Feb 20 13:37:38 CST 2021get tokens: true