guava►源码剖析

Guava RateLimiter 的使用与源码分析（令牌桶算法实现思路）

Guava RateLimiter 的使用与源码分析（令牌桶算法实现思路）

Guava RateLimiter基本使用

学东西时我们应该尽量去看官网、看源码、看官方给出的单元测试。

比如Guava RateLimiter，从RateLimiter类的源码注释中可以看到，官方给出的典型应用场景与使用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
As an example, imagine that we have a list of tasks to execute, but we don't want to submit more than 2 per second:
 
 final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is "2 permits per second"
 void submitTasks(List<Runnable> tasks, Executor executor) {
   for (Runnable task : tasks) {
     rateLimiter.acquire(); // may wait
     executor.execute(task);
   }
 }
 
As another example, imagine that we produce a stream of data, and we want to cap it at 5kb per second. This could be accomplished by requiring a permit per byte, and specifying a rate of 5000 permits per second:
 
 final RateLimiter rateLimiter = RateLimiter.create(5000.0); // rate = 5000 permits per second
 void submitPacket(byte[] packet) {
   rateLimiter.acquire(packet.length);
   networkService.send(packet);
 }

一个是限制执行任务的数量，一个是限制每次发送的字节数量。注意，如果超过RateLimiter.create所容许的permits数量，acquire方法将阻塞，直到产生新的permit。当然，如果不想一直阻塞，可以使用tryAcquire(Duration timeout)，该方法，指定一个超时时间，一旦判断出在timeout时间内还无法取得令牌，就返回false。

此外RateLimiter还支持预热功能，预热后缓存能支持 5 万 TPS 的并发，但是在预热前 5 万 TPS 的并发直接就把缓存击垮。

原理

Guava RateLimiter采用的是令牌桶算法。

经典的令牌桶算法描述如下：

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

如何用Java实现？

直观思路：生产者-消费者模式，生产者线程定时向阻塞队列添加令牌，被限流的线程作为消费者从阻塞队列获取令牌。

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

Guava如何实现令牌桶算法？

核心思想：记录并动态计算下一令牌发放的时间。

基本思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
​
class SimpleLimiter {
  /*
  当前令牌桶中的令牌数量。
  notes:注意此处的令牌数量是从当前时刻往后开始计算。但是这个变量只有在消费者线程调用acquire()方法时才会更新。这将导致在调用acquire()方法时，storedPermits是滞后的，需要先更新该值。所以有了resync方法
  */
  long storedPermits = 0;
  //令牌桶的容量
  long maxPermits = 3;
  //下一令牌产生时间
  long next = System.nanoTime();
  //发放令牌间隔：纳秒
  long interval = 1000_000_000;
  
  //请求时间在下一令牌产生时间之后,则
  // 1.重新计算令牌桶中的令牌数
  // 2.将下一个令牌发放时间重置为当前时间。
  //notes:因为此时已经更新了令牌桶中已有令牌数量，必须将next更新
  void resync(long now) {
    if (now > next) {
      //新产生的令牌数
      long newPermits=(now-next)/interval;
      //新令牌增加到令牌桶，由于桶的容量有限，通过取两者最小值来丢弃掉多出来的令牌
      storedPermits=min(maxPermits, 
        storedPermits + newPermits);
      //将下一个令牌发放时间重置为当前时间。
      next = now;
    }
  }
  //预占令牌，返回能够获取令牌的时间
  synchronized long reserve(long now){
    //notes:先更新当前桶中的令牌数量、下一个令牌的发放时间。如果令牌桶中已有令牌够用，此时resync方法中将执行next=now，也就是立即发放令牌。
    //如果令牌不够用、需要等待，那么需要等到next时间。
    resync(now);
    //能够获取令牌的时间
    long at = next;
    //令牌桶中能提供的令牌。本身只需要1个令牌，但需要先看令牌桶中的数量storedPermits是否够用。
    long fb=min(1, storedPermits);
    //令牌净需求：首先减掉令牌桶中的令牌
    /*
    两种情况：
    1. 令牌桶已经有足够的令牌：storedPermits >= 1, fb=1, 此时nr=0, 下一个令牌产生时间 next = next，而通过上面可知此时的next就是当前时间now，接着剩余令牌数量减一、更新库存(this.storedPermits -= fb;)
    2. 令牌桶内令牌不够： <= storedPermits < 1, fb=storedPermits, 此时 0 < nr <= 1, nr是接下来还需要产生的令牌数量（需要平滑产生），next = next + nr*interval,  就是说等待nr*interval时间之后，令牌桶中将产生1个完整的令牌可供调用。
    
    */
    long nr = 1 - fb;
    //重新计算下一令牌产生时间
    next = next + nr*interval;
    //重新计算令牌桶中的令牌
    this.storedPermits -= fb;
    //返回本次调用获取令牌的时间
    return at;
  }
  //申请令牌
  void acquire() {
    //申请令牌时的时间
    long now = System.nanoTime();
    //预占令牌
    long at=reserve(now);
    /*
    还是要分两种情况：
    1. 令牌桶已经有足够的令牌: 此时at=now，waitTime=0，获得令牌，直接返回
    2. 令牌桶内令牌不够： 此时at=下次产生令牌时间，需要等待
    */
    long waitTime=max(at-now, 0);
    //按照条件等待
    if(waitTime > 0) {
      try {
        TimeUnit.NANOSECONDS
          .sleep(waitTime);
      }catch(InterruptedException e){
        e.printStackTrace();
      }
    }
  }
}

有关算法的简要解释：

next 变量的意思是下一个令牌的生成时间，可以理解为当前线程请求的令牌的生成时刻，如第一张图所示：线程 T1 的令牌的生成时刻是第三秒。

线程 T 请求时，存在三种场景：

  1. 桶里有剩余令牌。
  2. 刚创建令牌，线程同时请求。
  3. 桶里无剩余令牌。

场景 2 可以想象成线程请求的同时令牌刚好生成，没来得及放入桶内就被线程 T 拿走了。因此将场景 2 和场景 3 合并成一种情况，那就是桶里没令牌。即线程请求时，桶里可分为有令牌和没令牌。

“桶里没令牌”，线程 T 需要等待；需要等待则意味着 now(线程 T 请求时刻) 小于等于 next(线程 T 所需的令牌的生成时刻)。这里可以想象一下线程 T 在苦苦等待令牌生成的场景，只要线程 T 等待那么久之后，就会被放行。放行这一刻令牌同时生成，立马被线程拿走，令牌没放入桶里。对应到代码就是 resync 方法没有进入 if 语句内。

“桶里有令牌”，线程 T 不需要等待。说明线程 T 对应的令牌已经早早生成，已在桶内。代码就是：now > next（请求时刻大于对应令牌的生成时刻）。因此在分配令牌给线程之前，需要计算线程 T 迟到了多久，迟到的这段时间，有多少个令牌生成¹；然后放入桶内，满了则丢弃²；未来的线程的令牌在这个时刻已经生成放入桶内³（即 resync 方法的逻辑）。线程无需等待，所以不需要增加一个 interval 了。

角标分别对应 resync 方法内的代码： ¹: long newPermits=(now-next)/interval; ²: storedPermits=min(maxPermits, storedPermits + newPermits); ³: next = now;

对于reverse方法，首先肯定是计算令牌桶里面的令牌数量，然后取令牌桶中的令牌数量storedPermits 与当前的需要的令牌数量 1 做比较，大于等于 1，说明令牌桶至少有一个令牌，此时下一令牌的获取是不需要等待的，表现为 next 不需要变化；而当令牌桶中的令牌没有了即storedPermits等于 0 时，next 就会变化为下一个令牌的获取时间，注意 nr 的值变化

参考资料

  • java并发编程实战 专栏课