调度与限流 #04：令牌桶

令牌桶（Token Bucket）以固定速率向桶中注入令牌、请求消耗令牌的方式实现限流，允许一定程度的突发流量；Guava RateLimiter、AWS API Gateway、Nginx（ngx_stream_limit_conn）等广泛采用此模型。

相关文章：漏桶 · 滑动窗口计数器 · 滑动窗口日志

token bucket

章节	说明
问题背景	为什么需要令牌桶，与简单计数器限流的区别
核心数据结构	懒惰填充法的四个字段定义
acquire(n) 完整伪代码	含懒惰填充的阻塞获取令牌流程
tryAcquire(n, timeout) 非阻塞版	非阻塞/带超时版本
执行追踪	rate=10/s, capacity=20 的具体数值演示
Guava RateLimiter 实现细节	SmoothBursty vs SmoothWarmingUp
异常与边界场景	时钟回拨、超大请求、并发、停机恢复
令牌桶 vs 漏桶	核心差异与适用场景
参考资料	论文、文档、源码

问题背景

简单计数器的缺陷

最朴素的限流方案是固定窗口计数器：每秒允许 N 个请求，超过则拒绝。但它有两个致命问题：

临界突发：00:59.9 到 01:00.1 之间可以打出 2N 个请求（两个窗口的配额叠加）。
无法吸收合理突发：系统空闲 5 秒后突然来了 50 个请求，即使平均速率远低于限制，也会被大量拒绝。

令牌桶的解法

令牌桶引入一个"桶"作为缓冲：

以固定速率 rate（令牌/秒）向桶中持续注入令牌。
桶的容量上限为 capacity，超出部分溢出丢弃。
每个请求消耗 n 个令牌，桶中令牌不足时等待或拒绝。

关键性质：

长期平均速率 ≤ rate（令牌产生速率决定上限）。
短期突发上限 = capacity（桶中积攒的令牌量）。
闲置越久，积攒的令牌越多（但不超过 capacity），突发能力越强。

核心数据结构

采用懒惰填充法（Lazy Refill）：不用后台线程定时填充，而是在每次 acquire 时根据时间差一次性补充令牌。

TokenBucket {
    tokens:         float   // 当前桶中的令牌数，初始值 = capacity
    lastRefillTime: long    // 上次填充时间戳（纳秒），初始值 = now()
    rate:           float   // 令牌生成速率，单位：令牌/秒
    capacity:       float   // 桶的最大容量（决定最大突发量）
}

字段说明：

字段	类型	说明
`tokens`	float	当前可用令牌数；float 避免整数截断误差
`lastRefillTime`	long (ns)	用纳秒时间戳，避免毫秒精度丢失
`rate`	float	每秒生成多少令牌，等于目标 QPS
`capacity`	float	桶容量，控制最大突发；通常设为 `rate` 的 1～5 倍

acquire(n) 完整伪代码

function acquire(bucket, n):
    lock(bucket)                            // 多线程安全
    try:
        // --- 懒惰填充 ---
        now       = currentTimeNanos()
        elapsed   = now - bucket.lastRefillTime    // 距上次填充经过的秒数（纳秒转换）
        elapsedSec = elapsed / 1_000_000_000.0

        bucket.tokens = min(
            bucket.capacity,
            bucket.tokens + elapsedSec * bucket.rate
        )
        bucket.lastRefillTime = now

        // --- 消耗令牌 ---
        if bucket.tokens >= n:
            bucket.tokens -= n
            return 0                        // 立即通过，等待时间 = 0

        else:
            deficit   = n - bucket.tokens  // 还差多少令牌
            waitSec   = deficit / bucket.rate
            waitNanos = (long)(waitSec * 1_000_000_000)

            bucket.tokens = 0              // 令牌全部预支
            bucket.lastRefillTime = now + waitNanos  // 时间戳向前推，等效于预扣未来令牌
    finally:
        unlock(bucket)

    sleep(waitNanos)                       // 在锁外等待，不阻塞其他线程计算
    return waitSec

关键设计点：

lastRefillTime 向前推移（预支未来令牌）：等待期间如果有新请求到来，填充计算会看到更少的 elapsed，从而自动限制后续请求。
sleep 在锁外执行：持锁期间只做计算，不阻塞后续请求的令牌检查。
使用 min(capacity, ...) 防止令牌无限积累。

tryAcquire(n, timeout) 非阻塞版

function tryAcquire(bucket, n, timeoutNanos):
    lock(bucket)
    try:
        // 懒惰填充（同 acquire）
        now        = currentTimeNanos()
        elapsedSec = (now - bucket.lastRefillTime) / 1_000_000_000.0
        bucket.tokens = min(bucket.capacity,
                            bucket.tokens + elapsedSec * bucket.rate)
        bucket.lastRefillTime = now

        // 计算需要等待多久
        if bucket.tokens >= n:
            bucket.tokens -= n
            return true                     // 立即成功

        deficit   = n - bucket.tokens
        waitNanos = (long)(deficit / bucket.rate * 1_000_000_000)

        if waitNanos > timeoutNanos:
            return false                    // 超出容忍等待时间，直接拒绝

        // 在 timeout 内可以等到，预支令牌
        bucket.tokens = 0
        bucket.lastRefillTime = now + waitNanos
    finally:
        unlock(bucket)

    sleep(waitNanos)
    return true

与 acquire 的区别：增加一个 timeoutNanos 上界判断，超出则不预支令牌直接返回 false，调用方可立即降级或返回 429。

执行追踪

参数：rate = 10 令牌/秒，capacity = 20，初始 tokens = 20，lastRefillTime = T0

场景 A：正常请求（令牌充足）

T0+0s:   acquire(1)
  elapsed = 0s, 填充 0 令牌
  tokens = min(20, 20 + 0) = 20
  20 >= 1 → tokens = 19, 等待 = 0ms  ✓

T0+0.1s: acquire(1)
  elapsed = 0.1s, 填充 0.1 * 10 = 1 令牌
  tokens = min(20, 19 + 1) = 20
  20 >= 1 → tokens = 19, 等待 = 0ms  ✓

场景 B：突发 20 个请求（桶满时一次性消耗）

T0+2s:   acquire(20)   // 此时桶已满（空闲 2s 补充 20 令牌，上限 20）
  elapsed = 2s, 填充 2 * 10 = 20 令牌
  tokens = min(20, 0 + 20) = 20   // 假设之前已消耗完
  20 >= 20 → tokens = 0, 等待 = 0ms  ✓  突发被桶容量吸收

场景 C：桶空时请求（需等待）

T0+2.001s: acquire(5)   // 紧接上面桶空的情况
  elapsed = 0.001s, 填充 0.001 * 10 = 0.01 令牌
  tokens = min(20, 0 + 0.01) = 0.01
  0.01 < 5 → deficit = 4.99
  waitSec = 4.99 / 10 = 0.499s
  waitNanos ≈ 499_000_000ns
  tokens = 0, lastRefillTime = T0+2.001s + 0.499s = T0+2.5s
  → sleep 499ms 后执行  ⏳

T0+2.5s:   acquire(3)   // 在上面的等待期间到来
  elapsed = now(2.5s) - lastRefillTime(2.5s) = 0s
  tokens = min(20, 0 + 0) = 0
  0 < 3 → waitSec = 3 / 10 = 0.3s
  → sleep 300ms 后执行  ⏳

观察：第二个请求计算时 lastRefillTime 已被第一个请求推到 T0+2.5s，即使真实时间也到了 2.5s，elapsed = 0，令牌仍为 0，自然排队。

Guava RateLimiter 实现细节

Guava 的 RateLimiter（com.google.common.util.concurrent）是令牌桶的工业级实现，有两个子类：

SmoothBursty（默认）

RateLimiter limiter = RateLimiter.create(10.0);  // 10 QPS

允许突发：空闲积累的 storedPermits 可以被立即消耗，不收额外等待费。
storedPermits 的含义：已积累的令牌数，上限由构造时传入的 maxBurstSeconds（默认 1s）决定，即 maxBurstSeconds * rate。
冷启动时桶是满的，第一批请求可以零等待地打出 maxBurstSeconds * rate 个请求。

SmoothWarmingUp（预热曲线）

RateLimiter limiter = RateLimiter.create(10.0, 3, TimeUnit.SECONDS);

为冷启动（如数据库连接池未预热）设计，防止突发把下游压垮。
storedPermits 的双重含义：在预热区间内，storedPermits 越多，消耗每个 permit 的代价（等待时间）越高；系统 "热起来" 后才恢复正常速率。
内部用梯形面积模拟预热曲线：storedPermits 在 [thresholdPermits, maxPermits] 区间时，等待时间从 coldInterval 线性降至 stableInterval。

storedPermits 的核心区别

实现	storedPermits 的消耗代价
SmoothBursty	消耗积累令牌 = 0 等待（允许突发）
SmoothWarmingUp	消耗积累令牌 = 更长等待（越冷越慢）

异常与边界场景

7.1 时钟回拨（NTP 调整导致 now < lastRefillTime）

elapsed = now - lastRefillTime  // 结果为负数
elapsedSec < 0
tokens + elapsedSec * rate < tokens  // 令牌会减少！

处理方式：

elapsedSec = max(0, (now - lastRefillTime) / 1_000_000_000.0)

将负值截断为 0，时钟回拨时不填充也不扣减令牌，等待时钟追上后恢复正常。

7.2 超大请求（n > capacity）

acquire(100)  // capacity = 20
桶永远最多积累 20 个令牌，而请求需要 100 个

两种策略：

永久阻塞：按 (n - currentTokens) / rate 计算等待，会等待极长时间（Guava 允许此行为）。
快速失败：if n > capacity: throw IllegalArgumentException，在构造或调用时校验。

Guava RateLimiter.acquire(permits) 允许请求超过容量，会产生极长等待，因此调用方应自行校验。

7.3 并发 acquire（多线程竞争）

问题：两个线程同时读到 tokens = 5，都认为可以拿 5 个令牌，导致令牌被消耗 10 个（double spending）。

解决方案：

方案	实现	适用场景
`synchronized` 方法锁	简单，`lock(bucket)` 整体加锁	单机，低并发
`ReentrantLock`	支持 `tryLock(timeout)`，可避免死锁	单机，中高并发
CAS + 自旋	`AtomicLong` 存 tokens（放大整数），无锁	单机，超高并发
Redis + Lua 脚本	原子执行填充+消耗逻辑	分布式限流

Guava RateLimiter 内部使用 synchronized 方法，锁粒度为整个 acquire 计算过程（不含 sleep）。

7.4 系统停机再恢复（令牌积累）

系统停机 1 小时后重启：
elapsed = 3600s
tokens = min(20, 0 + 3600 * 10) = min(20, 36000) = 20

min(capacity, ...) 保证令牌积累上限为 capacity，不会因为停机时间过长而在恢复时放出超大突发流量。这是令牌桶设计的重要保障。

令牌桶 vs 漏桶

维度	令牌桶（Token Bucket）	漏桶（Leaky Bucket）
突发处理	允许突发，桶容量决定最大突发量	强制匀速输出，突发被队列吸收
空闲积累	空闲期积累令牌，恢复后可突发	队列清空后下一请求立即通过，无积累
超出处理	桶空时等待或拒绝（可配置）	队列满时直接丢弃
输出速率	平均速率 ≤ rate，瞬时可超	严格等于 rate（匀速）
典型实现	Guava RateLimiter，AWS API GW	Nginx `limit_req`，TCP 整形
适用场景	API 限流、允许合理突发	网络流量整形、严格 SLA

Nginx limit_req 的漏桶模型：

limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
limit_req zone=api burst=20 nodelay;

rate=10r/s：漏桶出水速率。
burst=20：队列长度（允许 20 个请求排队）。
nodelay：队列中的请求立即处理（类似令牌桶效果，但底层仍是漏桶）。

参考资料

Guava RateLimiter 源码：com.google.common.util.concurrent.SmoothRateLimiter https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java
Token Bucket — Wikipedia https://en.wikipedia.org/wiki/Token_bucket
Turner, J.S. (1986)："New directions in communications (or which way to the information age?)"，IEEE Communications Magazine — 令牌桶算法的早期文献。
RFC 2697 — A Single Rate Three Color Marker https://datatracker.ietf.org/doc/html/rfc2697 — IETF 对令牌桶在流量着色中的规范定义。
Nginx ngx_http_limit_req_module 文档 https://nginx.org/en/docs/http/ngx_http_limit_req_module.html
《System Design Interview Vol.2》Alex Xu — Chapter 4: Rate Limiter 令牌桶与漏桶的工程对比分析。