令牌桶算法原理及应用

public static RateLimiter create(double permitsPerSecond) {
    return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond);
}
@VisibleForTesting
static RateLimiter create(SleepingStopwatch stopwatch, double permitsPerSecond) {
    //permitsPerSecond是我们设定的限流值
    //这里maxBurstSeconds固定是1.0，表示桶里最多预留1倍的permitsPerSecond
    //比如限流值是10，桶里最多就只能放10个令牌。
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
}
public final void setRate(double permitsPerSecond) {
    checkArgument(
        permitsPerSecond > 0.0 && !Double.isNaN(permitsPerSecond), "rate must be positive");
    synchronized (mutex()) {
        doSetRate(permitsPerSecond, stopwatch.readMicros());
    }
}
final void doSetRate(double permitsPerSecond, long nowMicros) {
    resync(nowMicros);
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
    this.stableIntervalMicros = stableIntervalMicros;
    doSetRate(permitsPerSecond, stableIntervalMicros);
}

//这是SmoothBursty的实现
@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
    //有oldMaxPermits和maxPermits是因为，可以动态地修改permitsPerSecond的值
    double oldMaxPermits = this.maxPermits;
    maxPermits = maxBurstSeconds * permitsPerSecond;
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        storedPermits = maxPermits;
    } else {

        //动态修改限流值时，桶里的剩余令牌数也要按照比例来缩放
        storedPermits = (oldMaxPermits == 0.0)
            ? 0.0 // initial state
            : storedPermits * maxPermits / oldMaxPermits;
    }
}

public double acquire(int permits) {
    //1. 计算这次请求需要等到多少时间
    long microsToWait = reserve(permits);
    //2. 阻塞这次请求上面计算出的时间
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    //3. 返回等待的时间（转化为微秒）
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
}
final long reserve(int permits) {
    //检查参数，不多说
    checkPermits(permits);
    synchronized (mutex()) {
        //获取等待的时间
        return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
}
final long reserveAndGetWaitLength(int permits, long nowMicros) {
    //又包了一层方法，获取等待时间
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
    //等待时间一定是>0的
    return max(momentAvailable - nowMicros, 0);
}

@Override
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    //将时间重新“同步”到当前时间，直观理解成给桶里补充令牌
    resync(nowMicros);
    //将下次获取令牌的时间返回。
    long returnValue = nextFreeTicketMicros;
    //判断存储的令牌数够不够这次请求用的。如果够，那么下面的freshPermits就是0，就不用往后推迟时间
    //如果存储的不够，就需要把“下次获取令牌时间”往后推迟
    //下面这段代码将的就是计算推迟时间
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;
    long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
        + (long) (freshPermits * stableIntervalMicros);

    try {
        this.nextFreeTicketMicros = LongMath.checkedAdd(nextFreeTicketMicros, waitMicros);
    } catch (ArithmeticException e) {
        this.nextFreeTicketMicros = Long.MAX_VALUE;
    }

    //桶里存储的令牌要扣除掉本次消耗的
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
}

void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    if (nowMicros > nextFreeTicketMicros) {
        //补充令牌，注意不能超了
        storedPermits = min(maxPermits,
                            storedPermits + (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros());
        //下次可以获取令牌的时间变成现在
        nextFreeTicketMicros = nowMicros;
    }
}

public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) {
    checkArgument(warmupPeriod >= 0, "warmupPeriod must not be negative: %s", warmupPeriod);
    return create(SleepingStopwatch.createFromSystemTimer(), permitsPerSecond, warmupPeriod, unit,
                  3.0);
}

@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {

    double oldMaxPermits = maxPermits;
    //coldFactor固定是3
    double coldIntervalMicros = stableIntervalMicros * coldFactor;
    //0.5的系数也是固定的，可以认为令牌的阈值是一个折中值
    thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;
    //见下方解释1
    maxPermits = thresholdPermits
        + 2.0 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
    //见下方解释2
    slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        // if we don't special-case this, we would get storedPermits == NaN, below
        storedPermits = 0.0;
    } else {
        storedPermits = (oldMaxPermits == 0.0)
            ? maxPermits // initial state is cold
            : storedPermits * maxPermits / oldMaxPermits;
    }
}

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);

    try {
        this.nextFreeTicketMicros = LongMath.checkedAdd(nextFreeTicketMicros, waitMicros);
    } catch (ArithmeticException e) {
        this.nextFreeTicketMicros = Long.MAX_VALUE;
    }
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
}
long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {

    double availablePermitsAboveThreshold = storedPermits - thresholdPermits;
    long micros = 0;
    //判断是否会经过预热阶段
    if (availablePermitsAboveThreshold > 0.0) {
        //注意这一行，将两种情况合并为一个公式计算，具体理解可以看下面的图示
        double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);
        //这里计算，在预热阶段的令牌会多出多少时间
        //这个就是一个计算梯形面积的公式，(上底+下底)*高/2
        micros = (long) (permitsAboveThresholdToTake
                         * (permitsToTime(availablePermitsAboveThreshold)
                            + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake)) / 2.0);
        permitsToTake -= permitsAboveThresholdToTake;
    }
    // 这个是假设都在稳定阶段，所需要的时间
    micros += (stableIntervalMicros * permitsToTake);
    return micros;
}
//这个方法是计算在当前令牌数下，生产每个令牌需要的时间
private double permitsToTime(double permits) {
    return stableIntervalMicros + permits * slope;
}