高并发系统限流算法详解

小咪咪 2023-05-29 13:17 11阅读 0赞

在大数据量高并发访问时，经常会出现服务或接口面对暴涨的请求而不可用的情况，甚至引发连锁反映导致整个系统崩溃。此时你需要使用的技术手段之一就是限流，当请求达到一定的并发数或速率，就进行等待、排队、降级、拒绝服务等。在限流时，常见的两种算法是漏桶和令牌桶算法算法，本文即对相关内容进行重点介绍。

四种常见的限流算法  
         1、计数器算法  
         2、滑动窗口算法  
         3、漏桶算法  
         4、令牌桶算法  
      两种限流控制的实现方式：RateLimiter、Semphore

### 一、计数器算法 ###

计数器算法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，具体算法的示意图如下：  
![在这里插入图片描述][20191106152844334.png]

public class CounterTest { 
        public long timeStamp = getNowTime();
        public int reqCount = 0;
        public final int limit = 100; // 时间窗口内最大请求数
        public final long interval = 1000; // 时间窗口ms
    
        public boolean grant() { 
            long now = getNowTime();
            if (now < timeStamp + interval) { 
                // 在时间窗口内
                reqCount++;
                // 判断当前时间窗口内是否超过最大请求控制数
                return reqCount <= limit;
            } else { 
                timeStamp = now;
                // 超时后重置
                reqCount = 1;
                return true;
            }
        }
    
        public long getNowTime() { 
            return System.currentTimeMillis();
        }
    }

这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题，我们看下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70]  
从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。

聪明的朋友可能已经看出来了，刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？或者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。

### 二、滑动窗口算法 ###

滑动窗口，又称rolling window。为了解决这个问题，我们引入了滑动窗口算法。如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。下面这张图，很好地解释了滑动窗口算法：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 1]  
在上图中，整个红色的矩形框表示一个时间窗口，在我们的例子中，一个时间窗口就是一分钟。然后我们将时间窗口进行划分，比如图中，我们就将滑动窗口 划成了6格，所以每格代表的是10秒钟。每过10秒钟，我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒的时候到达，那么0:30~0:39对应的counter就会加1。

那么滑动窗口怎么解决刚才的临界问题的呢？我们可以看上图，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格 子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触 发了限流。

我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。

由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

### 三、漏桶算法 ###

主要目的是控制数据注入到网络的速率，平滑网络上的突发流量。漏桶算法提供了一种机制，通过它，突发流量可以被整形以便为网络提供一个稳定的流量。漏桶算法的示意图如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 2]  
请求先进入到漏桶里，漏桶以一定的速度出水，当水请求过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

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

**这种算法，在使用过后也存在弊端：无法应对短时间的突发流量。**

### 四、令牌桶算法 ###

是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。令牌桶算法示意图如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 3]  
大小固定的令牌桶可自行以恒定的速率源源不断地产生令牌。如果令牌不被消耗，或者被消耗的速度小于产生的速度，令牌就会不断地增多，直到把桶填满。后面再产生的令牌就会从桶中溢出。最后桶中可以保存的最大令牌数永远不会超过桶的大小。  
放令牌这个动作是持续不断的进行，如果桶中令牌数达到上限，就丢弃令牌，所以就存在这种情况，桶中一直有大量的可用令牌，这时进来的请求就可以直接拿到令牌执行，**比如设置qps为100，那么限流器初始化完成一秒后，桶中就已经有100个令牌了，这时服务还没完全启动好，等启动完成对外提供服务时，该限流器可以抵挡瞬时的100个请求**。所以，只有桶中没有令牌时，请求才会进行等待，最后相当于以一定的速率执行。

**漏桶算法和令牌桶算法比较：**  
        两者主要区别在于“漏桶算法”能够强行限制数据的传输速率，而“令牌桶算法”在能够限制数据的平均传输速率外，还允许某种程度的突发传输。在“令牌桶算法”中，只要令牌桶中存在令牌，那么就允许突发地传输数据直到达到用户配置的门限，所以它适合于具有突发特性的流量。

### 五、使用Guava的RateLimiter进行限流控制 ###

Guava是google提供的java扩展类库，其中的限流工具类RateLimiter采用的就是令牌桶算法。RateLimiter 从概念上来讲，速率限制器会在可配置的速率下分配许可证，如果必要的话，每个acquire() 会阻塞当前线程直到许可证可用后获取该许可证，一旦获取到许可证，不需要再释放许可证。通俗的讲RateLimiter会按照一定的频率往桶里扔令牌，线程拿到令牌才能执行，比如你希望自己的应用程序QPS不要超过1000，那么RateLimiter设置1000的速率后，就会每秒往桶里扔1000个令牌。例如我们需要处理一个任务列表，但我们不希望每秒的任务提交超过两个，此时可以采用如下方式：

public class RateLimiterMain { 
       public static void main(String[] args) { 
           RateLimiter rateLimiter = RateLimiter.create(10);
           for (int i = 0; i < 10; i++) { 
               new Thread(new Runnable() { 
                   @Override
                   public void run() { 
                       rateLimiter.acquire()
     
                       System.out.println("pass");
                   }
               }).start();
           }
       }
    }

在上述例子中，创建了一个每秒生成10个令牌的限流器，即100ms生成一个，并最多保存10个令牌，多余的会被丢弃。

rateLimiter提供了acquire()和tryAcquire()接口  
1、使用acquire()方法，如果没有可用令牌，会一直阻塞直到有足够的令牌。  
2、使用tryAcquire()方法，如果没有可用令牌，就直接返回false。  
3、使用tryAcquire()带超时时间的方法，如果没有可用令牌，就会判断在超时时间内是否可以等到令牌，如果不能，就返回false，如果可以，就阻塞等待。

### 六、使用Semphore进行并发流控 ###

Java 并发库的Semaphore 可以很轻松完成信号量控制，Semaphore可以控制某个资源可被同时访问的个数，通过 acquire() 获取一个许可，如果没有就等待，而 release() 释放一个许可。单个信号量的Semaphore对象可以实现互斥锁的功能，并且可以是由一个线程获得了“锁”，再由另一个线程释放“锁”，这可应用于死锁恢复的一些场合。下面的Demo中申明了一个只有200个许可的Semaphore，而有5000个线程要访问这个资源，通过acquire()和release()获取和释放访问许可：

//请求总数
     private static int clientTotal = 5000;
     //同时并发执行的线程数
     private static int threadTotal = 200;
     public static void main(String[] args) throws InterruptedException { 
            ExecutorService executorService = Executors.newCachedThreadPool();
            final Semaphore semaphore = new Semaphore(threadTotal);
            
            for(int i=0; i<clientTotal; i++){ 
                executorService.execute(() -> { 
                    try { 
                        semaphore.acquire();
                        add();
                        semaphore.release();
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
                });
            }
        }

**进行限流控制还可以有很多种方法，针对不同的场景各有优劣，例如通过AtomicLong计数器控制、使用MQ消息队列进行流量消峰等等。**

[20191106152844334.png]: https://img-blog.csdnimg.cn/20191106152844334.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191106152936748.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191106164221599.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191106153606195.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191106153228286.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxOTk5NDU1,size_16,color_FFFFFF,t_70