[TOC]

高并发保护的三把利器之限流

前言

在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流；

那么何为限流呢？

顾名思义，限流就是限制流量，就像你宽带包了1个G的流量，用完了就没了。
通过限流，我们可以很好地控制系统的qps，从而达到保护系统的目的。

算法

滑动窗口

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

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

那么滑动窗口怎么解决刚才的临界问题的呢？我们可以看上图，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘黄色的格子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发了限流。
我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。
由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

计数器算法

计数器是最简单的一种，针对资源设置访问最大总量（上限）Max，以及定义一个计数器Counter，每当需要对资源访问时，Counter++，当Counter小于Max,访问可以通过，否则不可用。
image.png
基于单位时间的计数器
限制指定时间内的请求数量，比如1秒内最大的请求量为2个

  1. public class PerTimeUnitCounterFlowControl {
  2.     private static final long INTERVAL = 5 * 1000;//时间间隔ms
  3.     private long timestamp;
  4.     private int counter;
  5.     private int limit;
  6.     private long interval;
  7.     public PerTimeUnitCounterFlowControl(long interval,int limit) {
  8.         this.interval = interval <= 0? INTERVAL:interval;
  9.         this.timestamp = SystemClock.now();
  10.         this.limit = limit;
  11.     }
  12.     /**
  13.      *
  14.      * @return
  15.      */
  16.     public boolean acquire(){
  17.         long now = SystemClock.now();
  18.         if (now < timestamp + interval){
  19.             counter++;
  20.             return counter <= limit;
  21.         }
  22.         timestamp = now;
  23.         counter = 1;
  24.         return true;
  25.     }
  26. }

该算法的缺陷是，在时间节点重置的时隙里可能被突发请求超限。

漏桶算法

以下是wikipedia对Leaky bucket的算法描述：

[A] fixed capacity bucket, associated with each virtual connection or user, leaks at a fixed rate.
If the bucket is empty, it stops leaking.
For a packet to conform, it has to be possible to add a specific amount of water to the bucket: The specific amount added by a conforming packet can be the same for all packets, or can be proportional to the length of the packet.
If this amount of water would cause the bucket to exceed its capacity then the packet does not conform and the water in the bucket is left unchanged.

翻译过来的意思为:

  • 一个固定容量的漏桶，按照常量固定速率流出水滴；
  • 如果桶是空的，则不需流出水滴；
  • 可以以任意速率流入水滴到漏桶；
  • 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

image.png
首先，我们有一个固定容量的桶，有水流进来，也有水流出去。
对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。
但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。

  1. public class LeakyBucketFlowControl{
  2.     private int capacity;
  3.     private LinkedBlockingQueue bucket;
  4.     private int flowOutNum;//以恒定的速率流出
  5.     private int flowOutTimeUnit;//
  6.     private static final int VALUE = 1;
  7.     private Thread thread;
  8.     private volatile boolean stop = false;
  9.     public LeakyBucketFlowControl(int capacity, int flowOutNum, int flowOutTimeUnit) {
  10.         this.capacity = capacity;
  11.         this.flowOutNum = flowOutNum;
  12.         this.flowOutTimeUnit = flowOutTimeUnit;
  13.         this.bucket = new LinkedBlockingQueue<>(capacity);
  14.         this.thread = new Thread(new Worker());
  15.     }
  16.     /**
  17.      * init
  18.      */
  19.     public void init(){
  20.         thread.start();
  21.     }
  22.     /**
  23.      * 获取许可
  24.      * @return
  25.      */
  26.     protected boolean acquire(){
  27.         boolean of = bucket.offer(VALUE);
  28.         return of;
  29.     }
  30.     /**
  31.      * shutdown
  32.      */
  33.     public void shutdown(){
  34.         stop = true;
  35.         System.out.println("当前漏桶的容量：" + bucket.size());
  36.     }
  37.     /**
  38.      * 内部worker
  39.      */
  40.     class Worker implements Runnable{
  41.         @Override
  42.         public void run() {
  43.             while (!Thread.currentThread().isInterrupted() && !stop){
  44.                 try {
  45.                     TimeUnit.MILLISECONDS.sleep(flowOutTimeUnit);
  46.                     for(int i = 1;i <= flowOutNum;i++){
  47.                         bucket.take();
  48.                     }
  49.                     System.out.println("漏桶流出容量为：" + bucket.size());
  50.                 } catch (InterruptedException e) {
  51.                     Thread.currentThread().interrupt();
  52.                 }
  53.             }
  54.         }
  55.     }
  56. }

令牌桶算法

使用场景：比如Auth的access token，计算机网络中轮转访问MAC协议中的Token passing等
现在是关于token在限流中的算法描述：

[A] token is added to the bucket every 1/r seconds.
The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded.
When a packet (network layer PDU) of n bytes arrives, n tokens are removed from the bucket, and the packet is sent to the network.
If fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.

  • 令牌将按照固定的速率被放入令牌桶中。比如每秒放10个。
  • 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。
  • 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。
  • 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）

image.png
首先，我们有一个固定容量的桶，桶里存放着令牌（token）。
桶一开始是空的，token以一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。
每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过

实现

https://cloud.tencent.com/developer/article/1028633
算法实现直接使用Guava的RateLimiter:

  1. public class RateLimiterTester {
  2.     public static void main(String[] args) {
  3.         RateLimiter limiter = RateLimiter.create(2);//发令牌的间隔时间约500ms
  4.         double x = limiter.acquire(5) * 1000;
  5.         System.out.println(x + "....");
  6.         for (int i = 1;i <= 5;i++){
  7.             double y = limiter.acquire()  * 1000;
  8.             System.out.println(y);
  9.         }
  10.     }
  11. }
  12. 输出
  13. 0.0....
  14. 2497.7299999999996
  15. 491.842
  16. 495.838
  17. 497.392
  18. 498.442

令牌桶算法可以应对突发流量，RateLimiter提供了SmoothBursty和SmoothWarmingUp两种需求。

其他思考

若仔细研究算法，我们会发现我们默认从桶里移除令牌是不需要耗费时间的。如果给移除令牌设置一个延时时间，那么实际上又采用了漏桶算法的思路。Google的guava库下的·SmoothWarmingUp类就采用了这个思路。

区别

计数器 VS 滑动窗口

计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。
滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。
也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。
因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。
令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。

Java实现

Guava RateLimiter

Google Guava RateLimiter是一个速度控制器，可以根据配置的速度发放许可(令牌)。
每次调用acquire(), 如果有可用的许可，则拿走许可，否则被阻塞。拿走的许可毋须被释放。
和JDK中的Semaphore不同，

  • Semaphore控制访问资源的并发数，而RateLimiter控制访问资源的速度。
  • RateLimter以每秒N个许可的方式按照固定速率分发许可。

你可以warmup让RateLimter能够一开始就稳定的按照固定的速率发放许可。
tryAcquire()是一个非阻塞的调用方法。

  1. RateLimiter limiter = RateLimiter.create(20);
  3. public void run() {
  4.     for (Item item : items) {
  5.         limiter.acquire(); //获取许可
  6.         server.sync(item); //只有获得许可后才会被执行
  7.     }
  8. }