高性能限流器Guava RateLimiter

Hi我是阿昌今天学习记录的是关于高性能限流器Guava RateLimiter的内容。

Guava RateLimiter 是如何解决高并发场景下的限流问题的。

Guava 是 Google 开源的 Java 类库提供了一个工具类 RateLimiter。先来看看 RateLimiter 的使用对限流有个感官的印象。

假设有一个线程池它每秒只能处理两个任务如果提交的任务过快可能导致系统不稳定这个时候就需要用到限流。

在下面的示例代码中创建了一个流速为 2 个请求 / 秒的限流器这里的流速该怎么理解呢

直观地看2 个请求 / 秒指的是每秒最多允许 2 个请求通过限流器其实在 Guava 中流速还有更深一层的意思是一种匀速的概念2 个请求 / 秒等价于 1 个请求 /500 毫秒。

在向线程池提交任务之前调用 acquire() 方法就能起到限流的作用。

通过示例代码的执行结果任务提交到线程池的时间间隔基本上稳定在 500 毫秒。

//限流器流速2个请求/秒
RateLimiter limiter = RateLimiter.create(2.0);
//执行任务的线程池
ExecutorService es = Executors.newFixedThreadPool(1);
//记录上一次执行时间
prev = System.nanoTime();
//测试执行20次
for (int i=0; i<20; i++){
  //限流器限流
  limiter.acquire();
  //提交任务异步执行
  es.execute(()->{
    long cur=System.nanoTime();
    //打印时间间隔毫秒
    System.out.println(
      (cur-prev)/1000_000);
    prev = cur;
  });
}

输出结果
…
500
499
499
500
499

---

一、经典限流算法令牌桶算法

Guava 的限流器使用上还是很简单的那它是如何实现的呢

Guava 采用的是令牌桶算法其核心是要想通过限流器必须拿到令牌。

也就是说只要能够限制发放令牌的速率那么就能控制流速了。

令牌桶算法的详细描述如下

1. 令牌以固定的速率添加到令牌桶中假设限流的速率是 r/ 秒则令牌每 1/r 秒会添加一个
2. 假设令牌桶的容量是 b 如果令牌桶已满则新的令牌会被丢弃
3. 请求能够通过限流器的前提是令牌桶中有令牌。

这个算法中限流的速率 r 还是比较容易理解的但令牌桶的容量 b 该怎么理解呢b 其实是 burst 的简写意义是限流器允许的最大突发流量。

比如 b=10而且令牌桶中的令牌已满此时限流器允许 10 个请求同时通过限流器当然只是突发流量而已这 10 个请求会带走 10 个令牌所以后续的流量只能按照速率 r 通过限流器。

令牌桶这个算法如何用 Java 实现呢很可能直觉会告诉你生产者 - 消费者模式

一个生产者线程定时向阻塞队列中添加令牌而试图通过限流器的线程则作为消费者线程只有从阻塞队列中获取到令牌才允许通过限流器。这个算法看上去非常完美而且实现起来非常简单如果并发量不大这个实现并没有什么问题。可实际情况却是使用限流的场景大部分都是高并发场景而且系统压力已经临近极限了此时这个实现就有问题了。

问题就出在定时器上在高并发场景下当系统压力已经临近极限的时候定时器的精度误差会非常大同时定时器本身会创建调度线程也会对系统的性能产生影响。

那还有什么好的实现方式呢当然有Guava 的实现就没有使用定时器下面就来看看它是如何实现的。

---

二、Guava 如何实现令牌桶算法

Guava 实现令牌桶算法用了一个很简单的办法其关键是记录并动态计算下一令牌发放的时间。下面以一个最简单的场景来介绍该算法的执行过程。

假设令牌桶的容量为 b=1限流速率 r = 1 个请求 / 秒如下图所示如果当前令牌桶中没有令牌下一个令牌的发放时间是在第 3 秒而在第 2 秒的时候有一个线程 T1 请求令牌此时该如何处理呢

对于这个请求令牌的线程而言很显然需要等待 1 秒因为 1 秒以后第 3 秒它就能拿到令牌了。

此时需要注意的是下一个令牌发放的时间也要增加 1 秒为什么呢

因为第 3 秒发放的令牌已经被线程 T1 预占了。处理之后如下图所示。

假设 T1 在预占了第 3 秒的令牌之后马上又有一个线程 T2 请求令牌如下图所示。

很显然由于下一个令牌产生的时间是第 4 秒所以线程 T2 要等待两秒的时间才能获取到令牌同时由于 T2 预占了第 4 秒的令牌所以下一令牌产生时间还要增加 1 秒完全处理之后如下图所示。

上面线程 T1、T2 都是在下一令牌产生时间之前请求令牌如果线程在下一令牌产生时间之后请求令牌会如何呢

假设在线程 T1 请求令牌之后的 5 秒也就是第 7 秒线程 T3 请求令牌如下图所示。

由于在第 5 秒已经产生了一个令牌所以此时线程 T3 可以直接拿到令牌而无需等待。

在第 7 秒实际上限流器能够产生 3 个令牌第 5、6、7 秒各产生一个令牌。

由于假设令牌桶的容量是 1所以第 6、7 秒产生的令牌就丢弃了其实等价地也可以认为是保留的第 7 秒的令牌丢弃的第 5、6 秒的令牌也就是说第 7 秒的令牌被线程 T3 占有了于是下一令牌的的产生时间应该是第 8 秒如下图所示。

通过上面简要地分析会发现只需要记录一个下一令牌产生的时间并动态更新它就能够轻松完成限流功能。可以将上面的这个算法代码化示例代码如下所示依然假设令牌桶的容量是 1。

关键是 reserve() 方法这个方法会为请求令牌的线程预分配令牌同时返回该线程能够获取令牌的时间。其实现逻辑就是上面提到的

如果线程请求令牌的时间在下一令牌产生时间之后那么该线程立刻就能够获取令牌
反之如果请求时间在下一令牌产生时间之前那么该线程是在下一令牌产生的时间获取令牌。

由于此时下一令牌已经被该线程预占所以下一令牌产生的时间需要加上 1 秒。

class SimpleLimiter {
  //下一令牌产生时间
  long next = System.nanoTime();
  //发放令牌间隔纳秒
  long interval = 1000_000_000;
  //预占令牌返回能够获取令牌的时间
  synchronized long reserve(long now){
    //请求时间在下一令牌产生时间之后
    //重新计算下一令牌产生时间
    if (now > next){
      //将下一令牌产生时间重置为当前时间
      next = now;
    }
    //能够获取令牌的时间
    long at=next;
    //设置下一令牌产生时间
    next += interval;
    //返回线程需要等待的时间
    return Math.max(at, 0L);
  }
  //申请令牌
  void acquire() {
    //申请令牌时的时间
    long now = System.nanoTime();
    //预占令牌
    long at=reserve(now);
    long waitTime=max(at-now, 0);
    //按照条件等待
    if(waitTime > 0) {
      try {
        TimeUnit.NANOSECONDS
          .sleep(waitTime);
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }
  }
}

如果令牌桶的容量大于 1又该如何处理呢

按照令牌桶算法令牌要首先从令牌桶中出所以需要按需计算令牌桶中的数量当有线程请求令牌时先从令牌桶中出。具体的代码实现如下所示。

增加了一个 resync() 方法在这个方法中如果线程请求令牌的时间在下一令牌产生时间之后会重新计算令牌桶中的令牌数新产生的令牌的计算公式是(now-next)/interval可对照上面的示意图来理解。

reserve() 方法中则增加了先从令牌桶中出令牌的逻辑不过需要注意的是如果令牌是从令牌桶中出的那么 next 就无需增加一个 interval 了。

class SimpleLimiter {
  //当前令牌桶中的令牌数量
  long storedPermits = 0;
  //令牌桶的容量
  long maxPermits = 3;
  //下一令牌产生时间
  long next = System.nanoTime();
  //发放令牌间隔纳秒
  long interval = 1000_000_000;
  
  //请求时间在下一令牌产生时间之后,则
  // 1.重新计算令牌桶中的令牌数
  // 2.将下一个令牌发放时间重置为当前时间
  void resync(long now) {
    if (now > next) {
      //新产生的令牌数
      long newPermits=(now-next)/interval;
      //新令牌增加到令牌桶
      storedPermits=min(maxPermits, 
        storedPermits + newPermits);
      //将下一个令牌发放时间重置为当前时间
      next = now;
    }
  }
  //预占令牌返回能够获取令牌的时间
  synchronized long reserve(long now){
    resync(now);
    //能够获取令牌的时间
    long at = next;
    //令牌桶中能提供的令牌
    long fb=min(1, storedPermits);
    //令牌净需求首先减掉令牌桶中的令牌
    long nr = 1 - fb;
    //重新计算下一令牌产生时间
    next = next + nr*interval;
    //重新计算令牌桶中的令牌
    this.storedPermits -= fb;
    return at;
  }
  //申请令牌
  void acquire() {
    //申请令牌时的时间
    long now = System.nanoTime();
    //预占令牌
    long at=reserve(now);
    long waitTime=max(at-now, 0);
    //按照条件等待
    if(waitTime > 0) {
      try {
        TimeUnit.NANOSECONDS
          .sleep(waitTime);
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }
  }
}

---

三、总结

经典的限流算法有两个

• 一个是令牌桶算法Token Bucket
• 另一个是漏桶算法Leaky Bucket。

令牌桶算法是定时向令牌桶发送令牌请求能够从令牌桶中拿到令牌然后才能通过限流器

漏桶算法里请求就像水一样注入漏桶漏桶会按照一定的速率自动将水漏掉只有漏桶里还能注入水的时候请求才能通过限流器。

令牌桶算法和漏桶算法很像一个硬币的正反面所以你可以参考令牌桶算法的实现来实现漏桶算法。

Guava 是如何实现令牌桶算法的示例代码是对 Guava RateLimiter 的简化Guava RateLimiter 扩展了标准的令牌桶算法比如还能支持预热功能。

对于按需加载的缓存来说预热后缓存能支持 5 万 TPS 的并发但是在预热前 5 万 TPS 的并发直接就把缓存击垮了所以如果需要给该缓存限流限流器也需要支持预热功能在初始阶段限制的流速 r 很小但是动态增长的。

预热功能的实现非常复杂Guava 构建了一个积分函数来解决这个问题可以继续深入研究。

---