限流系列之RateLimiter解析（一）：SmoothBursty

一、简介

限流是服务治理的重要工具，在google的guava包里提供了关于速率限流器RateLimiter，可以帮助我们针对速率进行限流。

1. 类图

2. 原理

SmoothBursty是关于限流算法中令牌桶算法的一个实现，通过固定速率生成令牌，当流量进入时，申请令牌，令牌充足时则直接获取成功，不充足时返回等待时间。
需要注意的是，SmoothBursty支持预支令牌，如果本次申请令牌不足，可以直接对令牌进行预支，不会导致本次申请进行等待，而是影响下发申请。

二、创建和初始化

SmoothBursty的构造方法并没有对外开发，我们只能通过DateLimiter的create创建和初始化一个对象。

1. 成员变量

对象的创建本质上就是对成员变量的赋值，因此在介绍对象创建和初始化之前先介绍一下SmoothBursty的几个核心的成员变量。
基于我们对令牌桶算法的理解，其实我们大概也能揣测出SmoothBursty主要需要哪些字段：
令牌生成速率，最大令牌数，当前令牌数和当前时间。
下面我们验证一下对比和验证一下是不是和我们想象的一样。

//SmoothRateLimiter
/**
 * The currently stored permits.
 */
double storedPermits;

/**
 * The maximum number of stored permits.
 */
double maxPermits;

/**
 * The interval between two unit requests, at our stable rate. E.g., a stable rate of 5 permits
 * per second has a stable interval of 200ms.
 */
double stableIntervalMicros;

/**
 * The time when the next request (no matter its size) will be granted. After granting a
 * request, this is pushed further in the future. Large requests push this further than small
 * requests.
 */
private long nextFreeTicketMicros = 0L; // could be either in the past or future
/**
 * The underlying timer; used both to measure elapsed time and sleep as necessary. A separate
 * object to facilitate testing.
 */
private final SleepingStopwatch stopwatch;

//SmoothBUrsty
/** The work (permits) of how many seconds can be saved up if this RateLimiter is unused? */
final double maxBurstSeconds; 

如上面的代码，也有一些对应的注释，我们简单的过一遍

1. SmoothRateLimiter类的成员变量
   （1）storedPermits 库存的令牌数量
   （2）maxPermits 可以容纳的最大令牌数量
   （3）stableIntervalMicros 令牌生成的时间间隔，令牌生成速率的另一种描述。举个例子，我们一般用5个/秒来描述令牌生成的速度，那么对应stableIntervalMicros 就是 200毫秒/个
   （4）nextFreeTicketMicros 最新的令牌生成时间，和storedPermits 是对应的，在这个时刻还有storedPermits 个库存令牌。
   （5）stopwatch：计时器，用来计算时间
2. SmoothBursty类的成员变量
   SmoothBursty只有一个成员变量：maxBurstSeconds，和maxPermits 对应，在令牌不消费的情况下可以生成多长时间的令牌

2. RateLimiter#create

public static RateLimiter create(double permitsPerSecond) {
  /*
   * The default RateLimiter configuration can save the unused permits of up to one second.
   * This is to avoid unnecessary stalls in situations like this: A RateLimiter of 1qps,
   * and 4 threads, all calling acquire() at these moments:
   *
   * T0 at 0 seconds
   * T1 at 1.05 seconds
   * T2 at 2 seconds
   * T3 at 3 seconds
   *
   * Due to the slight delay of T1, T2 would have to sleep till 2.05 seconds,
   * and T3 would also have to sleep till 3.05 seconds.
   */
  return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond);
}

@VisibleForTesting
static RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond) {
  RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
  rateLimiter.setRate(permitsPerSecond);
  return rateLimiter;
}

从方法名就可以看到分两步：1. 构造方法，2.设置令牌生成速率

3. SmoothBursty构造方法

SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
  super(stopwatch);
  this.maxBurstSeconds = maxBurstSeconds;
}
private SmoothRateLimiter(SleepingStopwatch stopwatch) {
  super(stopwatch);
}
RateLimiter(SleepingStopwatch stopwatch) {
  this.stopwatch = checkNotNull(stopwatch);
}

构造方法很简单没什么好说的，设置stopwatch 和 maxBurstSeconds 两个局部变量。

4. SmoothBursty#doSetRate

// DateLimiter#setRate
public final void setRate(double permitsPerSecond) {
  checkArgument(
      permitsPerSecond > 0.0 && !Double.isNaN(permitsPerSecond), "rate must be positive");
  synchronized (mutex()) {
    doSetRate(permitsPerSecond, stopwatch.readMicros());
  }
}

在RateLimiter里就是一个同步方法，具体实现交给子类自己处理，所以我们直接看SmoothBursty#doSetRate方法

@Override
final void doSetRate(double permitsPerSecond, long nowMicros) {
  resync(nowMicros);
  //速度转化为stableIntervalMicros ，取倒数
  double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
  this.stableIntervalMicros = stableIntervalMicros;
  doSetRate(permitsPerSecond, stableIntervalMicros);
}
@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
  double oldMaxPermits = this.maxPermits;
  //最大令牌数计算，最大令牌持续生成时间*速率
  maxPermits = maxBurstSeconds * permitsPerSecond;
  if (oldMaxPermits == Double.POSITIVE_INFINITY) {
    // if we don't special-case this, we would get storedPermits == NaN, below
    storedPermits = maxPermits;
  } else {
  	//设置速率后，库存令牌数按比例放大或缩小，初始时为0
    storedPermits = (oldMaxPermits == 0.0)
        ? 0.0 // initial state
        : storedPermits * maxPermits / oldMaxPermits;
  }
}

1. resync方法的执行，主要是计算库存令牌和storedPermits 和 最新令牌计算时间nextFreeTicketMicros
2. 其他几个成员变量的设置和赋值

5. SmoothRateLimiter#resync

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

逻辑也不复杂，如果令牌还没有计算到当前时间，就按速率计算到当前。保证当前的库存令牌数要么是最新的，要么是预支的。
回顾到doSetRate方法，注意到是先执行resync方法再给stableIntervalMicros赋值的，这时候的库存令牌还是按照修改前的速率计算的，这样子在后续缩放令牌数时才是合理的。

三、限流判断

1. DateLimiter#acquire

RateLimiter的限流入口是acquire等相关的方法，具体如下

public double acquire(int permits) {
	//令牌足够本次需要的时间
    long microsToWait = this.reserve(permits);
    this.stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0D * (double)microsToWait / (double)TimeUnit.SECONDS.toMicros(1L);
}

方法返回本次请求需要等待的时间，0代表令牌足够使用。

final long reserve(int permits) {
    checkPermits(permits);
    synchronized(this.mutex()) {
        return this.reserveAndGetWaitLength(permits, this.stopwatch.readMicros());
    }
}
final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = this.reserveEarliestAvailable(permits, nowMicros);
    //返回需要等待的时间，小于0只需要等于0
    return Math.max(momentAvailable - nowMicros, 0L);
}

2. SmoothBursty#reserveEarliestAvailable

@Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  //更新库存令牌
  resync(nowMicros);
  long returnValue = nextFreeTicketMicros;
  //库存中需要被本次请求消耗的令牌
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
  //不足的还需要预支的令牌
  double freshPermits = requiredPermits - storedPermitsToSpend;
  //需要预支的时间
  long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
      + (long) (freshPermits * stableIntervalMicros);
  //更新库存令牌和对应计算的时间
  this.nextFreeTicketMicros = nextFreeTicketMicros + waitMicros;
  this.storedPermits -= storedPermitsToSpend;
  //可以看到，本次请求即使令牌不足，对于预支令牌的时间也不会影响本次请求，智慧影响后续请求
  return returnValue;
}

1. resync方法前面已经分析过，对于令牌计算时间小于当前时间的情况进行更新，更新到当前时间
2. 把本次请求需要的令牌分成两部分，即库存部分和预支部分
3. 库存部分需要的时间根据storedPermitsToWaitTime方法计算，对于SmoothBursty该方法固定为0，即库存令牌消耗不需要时间
4. 预支部分根据令牌生成速率进行计算：freshPermits * stableIntervalMicros（令牌数*每个令牌需要的时间）
5. 更新库存令牌及对应的令牌计算时间
6. 返回，可以看到返回的是上次令牌计算时间，而不是第5步中更新的最新时间。说明对于令牌预支情况并不会影响本次请求，只会影响后续请求

四、总结
对于令牌桶，按照算法设计师每秒生成固定数量的令牌。在SmoothBursty中并不是简单的通过一个定时任务生成，而是通过令牌生成速率和时间段进行计算：相差的时间段 / 每块令牌需要的时间。
而且对于库存令牌，要么计算到预支时间到，要么计算到当前锁时间，保证是最新的。
在DateLimiter的实现中，运用了模板模式，对限流器进行抽象成若干方法，分别写在DateLimiter，SmoothDateLimiter和具体的子类中，这对于阅读和理解代码可能会有一定影响，但理解原理后整理逻辑并不复杂，而且对于后续阅读和理解其他子类或者自定义子类都很方便。