跳到主要内容

谷歌Guava限流器的设计与实现

· 阅读需 10 分钟

介绍​

谷歌Guava工具包提供了一个单机限流工具，它基于令牌桶算法实现，主要被用于限制访问资源的速度。

Guava限流器的简单使用例子：

// 每秒2个令牌
RateLimiter rateLimiter = RateLimiter.create(2);
DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern("HH:mm:ss.SSS");
TimeUnit.SECONDS.sleep(1);
for (int i = 0; i < 10; i++) {
    // 阻塞式获取1个令牌
    rateLimiter.acquire(1);
    System.out.println(LocalDateTime.now().format(dateTimeFormatter));
}

其输出如下：

23:49:48.131
23:49:48.132
23:49:48.132
23:49:48.628
23:49:49.127
23:49:49.627
23:49:50.128
23:49:50.628
23:49:51.128
23:49:51.627

Guava限流器有两种模式：突发模式与预热模式。默认是突发模式，它可以在空闲状态下保存一部分令牌，用于后续处理突发请求，从而避免大量阻塞或拒绝。预热模式适合大流量场景，可以让服务端从空闲状态平滑过渡到高负载状态。

令牌桶算法​

原理与特性​

令牌桶算法是一种针对请求速度的限流算法，核心是一个令牌桶，桶内令牌数量以固定速度增长，每个请求都需要从桶中获取到足够的令牌后才能被放行，否则就会被阻塞或拒绝。只需要设置令牌的生成速度，令牌桶算法就能通过令牌发放来限制请求通过的速度。

image

令牌桶算法有两个重要特性：流量整形、方便处理突发流量。

流量整形是指令牌桶算法将原本不规则的流量在经过限流器后变得平滑且均匀。流量整形的效果有利于服务端的稳定运行，类似MQ的削峰填谷手段。经过流量整形后，服务端能以稳定的状态接收并处理请求。

突发流量是指随机出现的、短时间的流量突刺。如果严格遵循流量整形，在遇到突发流量时会突然拒绝一大批请求，如果客户端有重试机制还可能导致进一步恶化。因此，如果服务端资源充足，限流器应具有一定的弹性，允许服务端处理一些突发请求。

在令牌桶算法模型中，可以通过给桶内生成的令牌设置有效期即可实现对于突发流量的弹性处理。有突发流量时，限流器可以使用有效期内的剩余令牌来通过更多请求，从而临时提高服务端的处理效率，避免大量请求被拒绝。

实现​

image

Guava限流器以一种简洁的方式实现了令牌桶算法，它的核心思想是计算令牌桶算法中令牌数量与时间的线性关系。在空闲情况下，桶内令牌数量会以预设的速度稳定增加，通过最近一次通过请求的时间以及剩余令牌的数量，可以计算出后续任意时间点的令牌数量，如图中的公式所示。

基于上述公式，Guava限流器可以在请求到达时计算出当前的令牌桶状态，然后计算出何时可以通过请求。

令牌桶的实现位于com.google.common.util.concurrent.SmoothRateLimiter#reserveEarliestAvailable ：

/**
 * 令牌桶算法
 * @param requiredPermits 请求所需的令牌数
 * @param nowMicros 当前时间
 * @return 可以放行请求的时间点
 */
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    // 计算令牌桶内的令牌数量
    resync(nowMicros);

    // 返回何时可以通过请求
    long returnValue = nextFreeTicketMicros;
    // 消耗的令牌数 = min(需要的令牌数, 桶内存储的令牌)
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    // 桶内令牌数不足，还需要新的令牌数
    double freshPermits = requiredPermits - storedPermitsToSpend;

    // 等待时间 = 桶内令牌发放时间 + 后续生成令牌所需时间
    // 后续生成令牌所需时间 = 还需要新的令牌数 * 请求时间间隔
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);

    // 下一个请求允许的时间点 += 等待时间
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    // 桶内存储的令牌 -= 消耗的令牌数
    this.storedPermits -= storedPermitsToSpend;
    // 返回增加等待时间之前的请求允许的时间点
    return returnValue;
}

void resync(long nowMicros) {
    // nextFreeTicketMicros 的含义是下一个请求允许的时间点
    // 如果当前时间比 nextFreeTicketMicros 晚，说明这期间空闲（冷状态），可以生成一些令牌
    if (nowMicros > nextFreeTicketMicros) {
        // 空闲时间内生成的令牌数 = (当前时间 - 请求允许的时间) / 空闲状态令牌生成时间间隔
        double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
        // 桶内令牌数 = min(桶容量, 剩余令牌数 + 空闲时间内生成的令牌数)
        storedPermits = min(maxPermits, storedPermits + newPermits);
        nextFreeTicketMicros = nowMicros;
    }
}

两个主要的计算步骤：先计算当前令牌桶中令牌数量，再计算发放足够令牌需要的时间。

上述令牌桶计算过程有一个请求阻塞等待的优化，即返回的放行时间是增加等待时间waitMicros 之前的时间。这样的效果是阻塞等待不会影响当前请求，而是影响后续等待时间内到达的请求。例如，对于1QPS的限流器，收到一个需要100个令牌才能通过的请求，会先放行这个请求，之后100秒内阻塞后续到达的请求，而不是直接阻塞当前请求100秒再放行。这种“赊账”机制能够以更小的阻塞代价达到同样的限流效果。

桶内令牌发放时间​

桶内令牌发放时间由限流器的模式决定，Guava限流器包含突发模式和预热模式，有着不同的桶内令牌发放模型。

突发模式​

突发模式下，桶内令牌可以直接发放，故桶内令牌发放时间为0。

在空闲状态下，桶内令牌也以stableInterval 时间间隔匀速增加。

预热模式​

预热模式下，限流器通过请求的速度会随着流量的上涨而逐渐加快，以让服务端平滑地从空闲状态过渡到高负载状态。

下图为Guava限流器所定义的预热模型，限流器令牌生成的时间间隔（纵轴）与令牌桶内的令牌数量（横轴）相关：当桶内令牌较多时，说明此时流量较小，限流器处于冷状态，令牌生成速度较慢，令牌生成间隔为cold interval ；当流量变大时，桶内令牌被消耗，令牌生成间隔缩短，限流器逐渐转为热状态，直到桶内令牌数耗到thresholdPermits 及以下时，限流器处于热状态，令牌生成间隔为stable interval ，进入稳定状态。

image

了解预热模型之后，就可以计算桶内令牌发放时间了。假设请求通过需要的令牌数在预热期间即可满足，那么桶内令牌发放时间即为图中的梯形的面积。否则，只需要再加上稳定状态期间矩形的面积即可。

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
    double availablePermitsAboveThreshold = storedPermits - thresholdPermits;
    long micros = 0;
    // 说明当前令牌桶处于预热状态，计算梯形面积
    if (availablePermitsAboveThreshold > 0.0) {
        // 预热状态需要的令牌数
        double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);
        // 梯形的上底+下底
        double length =
                permitsToTime(availablePermitsAboveThreshold)
                        + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake);
        // 梯形面积 = (上底 + 下底) * 高 / 2
        micros = (long) (permitsAboveThresholdToTake * length / 2.0);
        permitsToTake -= permitsAboveThresholdToTake;
    }
    // 令牌桶预热完毕，计算稳定状态矩形面积
    micros += (long) (stableIntervalMicros * permitsToTake);
    return micros;
}

/**
 * 根据令牌数计算间隔时间。
 * @param permits 预热状态下的令牌数，也就是以 thresholdPermits 为原点的令牌数
 * @return 对应的间隔时间，也就是纵轴的值
 */
private double permitsToTime(double permits) {
    return stableIntervalMicros + permits * slope;
}

在空闲状态下，桶内令牌匀速增加，增加至maxPermits需要的时间为warmupPeriod 。

double coolDownIntervalMicros() {
    return warmupPeriodMicros / maxPermits;
}