Guava RateLimiter与限流算法

• RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率。与Semaphore 相比，Semaphore 限制了并发访问的数量而不是使用速率。（注意尽管并发性和速率是紧密相关的）
• 对QPS的限制 = 对单位时间内的可用令牌数的限制（假设每个请求只消耗一个令牌）
• RateLimiter／SmoothRateLimiter的做法是以时间换令牌，令牌的抢占使得"下次可用时间（nextFreeTicketMicros）"往前推进，如果请求（tryAcquire）的"当前时间 + 超时时间" < "下次可用时间"，则tryAcquire返回false。
• 注意，RateLimiter 并不提供公平性的保证。

限流算法：令牌桶（Token Bucket）和漏桶（Leaky Bucket）是最常用的两种限流算法。

1. 漏桶算法
   漏桶算法思路很简单，水（请求）先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出，可以看出漏桶算法能强行限制数据的传输速率。

   
   leaky_bucket.png

   对于很多应用场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，相比之下令牌桶算法更为合适。

2. 令牌桶算法
   令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

   
   token_bucket.png

限流工具类：Guava提供了限流工具类RateLimiter，该类基于令牌桶算法来完成限流。

/**
 * Acquires a permit from this {@code RateLimiter}, blocking until the request can be granted.
 *
 * <p>This method is equivalent to {@code acquire(1)}.
 */
public void acquire() {
  acquire(1);
}

/**
 * Acquires the given number of permits from this {@code RateLimiter}, blocking until the
 * request be granted.
 *
 * @param permits the number of permits to acquire
 */
public void acquire(int permits) {
  checkPermits(permits);
  long microsToWait;
  synchronized (mutex) {
    // 如果“下次可用时间”大于当前时间，则需要等待
    microsToWait = reserveNextTicket(permits, readSafeMicros());
  }
  ticker.sleepMicrosUninterruptibly(microsToWait);
}


/**
 * Reserves next ticket and returns the wait time that the caller must wait for.
 */
private long reserveNextTicket(double requiredPermits, long nowMicros) {
  // 如果“下次可用时间”小于当前时间，则将它更新到当前时间；同时，“可用令牌数”根据时间增长而增长，最多不超过最大令牌数
  resync(nowMicros);
  // 需要等待的时间即“下次可用时间”减去“当前时间”
  long microsToNextFreeTicket = nextFreeTicketMicros - nowMicros;
  double storedPermitsToSpend = Math.min(requiredPermits, this.storedPermits);
  double freshPermits = requiredPermits - storedPermitsToSpend;

  // 如果最新的“可用令牌数”小于requiredPermits，则可能需要预支一定量的时间，这也将导致“下次可用时间”的推进
  long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
      + (long) (freshPermits * stableIntervalMicros);

  // 推进“下次可用时间”
  this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
  // 减少“可用令牌数”
  this.storedPermits -= storedPermitsToSpend;
  return microsToNextFreeTicket;
}


private void resync(long nowMicros) {
  // if nextFreeTicket is in the past, resync to now
  if (nowMicros > nextFreeTicketMicros) {
    storedPermits = Math.min(maxPermits,
        storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
    nextFreeTicketMicros = nowMicros;
  }
}