4. 令牌桶算法详解：算法原理、参数、实现伪代码与适用场景

令牌桶（ Bucket）是分布式系统中最常用的限流算法之一，也是 etcd 客户端限流模块的核心实现基础。与漏桶算法的“恒定排水”不同，令牌桶允许一定程度的突发流量，更适合微服务与 RPC 调用的实际负载模式。

4.1 算法核心原理

令牌桶算法基于一个简单的数学模型：

  • 桶：一个容量固定的容器，用于存放令牌（）。
  • 令牌生成：系统以恒定速率 rate 向桶中添加令牌，直到桶满为止。
  • 请求消费：每个请求到达时，必须从桶中获取一个（或多个）令牌才能被放行；如果桶中令牌不足，请求被拒绝或等待。
  • 突发能力：桶的容量 burst 决定了最大突发流量——当桶满时，可以一次性消耗所有令牌，应对瞬时高峰。
关键洞察：令牌桶的“桶”本质是一个缓冲池，它允许短时间内的流量超过平均速率，但长期平均速率仍被 rate 约束。这是它与漏桶算法最本质的区别。
令牌桶算法核心流程 令牌桶算法核心流程 令牌生成器 rate 个/秒 令牌桶 容量 = burst 请求到达 令牌足够？ 放行 / 处理 拒绝 / 等待

4.2 核心参数详解

令牌桶算法有两个关键参数，它们共同决定了限流行为：

参数 符号 含义 对限流的影响 典型值（etcd 场景）
速率 rate 令牌生成的恒定速率（个/秒） 决定长期平均 QPS 上限 1000 req/s
突发容量 burst 桶的最大令牌存储量 决定瞬时突发流量上限 2000（2×rate）
参数关系公式：
最大瞬时 QPS = burst（桶满时一次性消耗）
长期平均 QPS ≤ rate（令牌生成速率约束）
桶满时间 = burst / rate（从空桶到满桶所需秒数）

4.3 算法实现伪代码

以下是用 Go 语言风格实现的令牌桶核心逻辑。注意，实际生产级实现（如 etcd 使用的 golang.org/x/time/rate）会使用浮点数精度和更高效的数学计算，但核心思想与此一致。

// TokenBucket 令牌桶限流器
type TokenBucket struct {
    rate     float64       // 令牌生成速率（个/秒）
    burst    int           // 桶容量
    tokens   float64       // 当前令牌数
    lastTime time.Time     // 上次更新令牌的时间
    mu       sync.Mutex    // 并发安全锁
}

// NewTokenBucket 创建令牌桶
func NewTokenBucket(r float64, b int) *TokenBucket {
    return &TokenBucket{
        rate:     r,
        burst:    b,
        tokens:   float64(b), // 初始时桶满
        lastTime: time.Now(),
    }
}

// Allow 判断是否允许一个请求通过
func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    // 1. 计算时间差，补充令牌
    elapsed := now.Sub(tb.lastTime).Seconds()
    tb.tokens += elapsed * tb.rate
    // 2. 令牌数不能超过桶容量
    if tb.tokens > float64(tb.burst) {
        tb.tokens = float64(tb.burst)
    }
    // 3. 判断是否有足够令牌
    if tb.tokens >= 1.0 {
        tb.tokens -= 1.0
        tb.lastTime = now
        return true
    }
    // 4. 令牌不足，拒绝请求
    tb.lastTime = now
    return false
}

// ReserveN 预留 N 个令牌（用于批量请求场景）
func (tb *TokenBucket) ReserveN(n int) bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(tb.lastTime).Seconds()
    tb.tokens += elapsed * tb.rate
    if tb.tokens > float64(tb.burst) {
        tb.tokens = float64(tb.burst)
    }
    if tb.tokens >= float64(n) {
        tb.tokens -= float64(n)
        tb.lastTime = now
        return true
    }
    tb.lastTime = now
    return false
}
实现注意事项：
1. 时间精度：使用 time.Now() 的纳秒精度，避免整数秒截断导致限流偏差。
2. 并发安全：必须加锁，因为 tokens 和 lastTime 是共享状态。
3. 浮点数误差：长时间运行后，tokens 的浮点数累加可能产生微小误差，建议定期重置或使用 math.Nextafter 修正。
4. 初始状态：通常初始化为桶满（tokens = burst），允许服务启动时立即处理突发请求。

4.4 令牌桶 vs 漏桶：关键对比

对比维度 令牌桶 漏桶
突发处理 允许突发（burst 参数控制） 严格平滑，不允许突发
长期速率 受 rate 约束 受 rate 约束
实现复杂度 中等（需维护时间戳和令牌计数） 较低（队列 + 定时器）
内存开销 O(1)，仅需几个变量 O(burst)，需要队列存储等待请求
适用场景 RPC 调用、API 网关、微服务 网络流量整形、数据流处理
etcd 使用 客户端限流（golang.org/x/time/rate） 不适用
令牌桶 vs 漏桶行为对比 令牌桶 vs 漏桶：突发流量行为对比 令牌桶 输入：突发 2000 QPS 桶容量 = 2000 令牌充足 输出：2000 QPS （突发全部放行） → 允许瞬时突发，长期平均受 rate 约束 漏桶 输入：突发 2000 QPS 队列溢出 丢弃 1000 请求 输出：1000 QPS （严格平滑，丢弃一半） → 强制平滑，不允许任何突发

4.5 适用场景分析

令牌桶算法在 etcd 客户端限流中表现出色，主要基于以下场景特性：

  • 微服务 RPC 调用：服务间调用天然具有突发性（如批量查询、缓存回填），令牌桶允许这些突发而不影响长期平均速率。
  • etcd 客户端请求：客户端可能同时发起多个 watch、put、get 请求，令牌桶的 burst 参数可以容忍短时间内的请求堆积。
  • API 网关限流：网关需要区分不同租户的速率限制，令牌桶的 rate 和 burst 可以独立配置，灵活性高。
  • 批处理系统：当请求可以批量处理时（如 etcd 的 Txn 事务），ReserveN 方法可以一次性预留多个令牌。
etcd 实战建议：在配置 etcd 客户端限流时，建议将 burst 设置为 rate 的 2~3 倍。例如，如果期望长期 QPS 为 1000，则设置 rate=1000, burst=2500。这样既能容忍 2.5 秒的请求暂停后恢复时的突发，又不会让瞬时流量过高导致服务端过载。

4.6 令牌桶的变体与扩展

变体名称 核心差异 适用场景
标准令牌桶 固定 rate 和 burst 通用限流
动态令牌桶 rate 可根据系统负载动态调整 自适应限流、过载保护
分层令牌桶 多个桶级联，不同层级不同 rate 多租户限流、资源隔离
加权令牌桶 不同请求消耗不同数量的令牌 按请求成本限流（如大查询消耗更多）

在 etcd 的 golang.org/x/time/rate 实现中，使用的是标准令牌桶的变体——“松弛令牌桶”（也称为“带借用的令牌桶”）。它允许令牌数为负数（即“欠债”），从而在短时间内允许超过 burst 的流量，但后续请求必须等待“还债”。这种设计进一步提高了突发容忍度，同时保证了长期平均速率。

← 上一章 📖 返回目录 下一章 →