2. 限流算法基础：令牌桶算法原理与适用场景

在自愈剧本的 Runbook 验证中，限流是防止系统被突发流量冲垮的第一道防线。令牌桶算法（ Bucket）因其兼顾平均速率限制与突发流量容忍的特性，成为生产环境中最广泛使用的限流模型。本节从算法原理、数学模型到适用场景，建立完整的认知基础。

2.1 算法核心原理

令牌桶算法基于一个直观的比喻：系统以一个固定速率向桶中放入令牌，每个请求必须从桶中获取一个令牌才能被处理；桶有最大容量，超出容量的令牌被丢弃。当桶中令牌耗尽时，新请求被拒绝或排队等待。

关键参数：
  • r（rate）：令牌生成速率，单位：个/秒，决定长期平均请求速率。
  • b（burst）：桶的最大容量，单位：个，决定允许的突发请求数量。
  • 当前令牌数：动态变化，初始为 b，上限为 b。
令牌桶算法核心流程 令牌桶算法核心流程 令牌生成器 速率 r 个/秒 令牌桶（容量 b） 令牌 令牌 令牌 令牌 令牌 令牌 溢出 请求到达 有令牌？ 放行处理 拒绝/等待 关键特性 • 平均速率 = r • 突发上限 = b • 令牌不累积超过 b

2.2 算法执行步骤

令牌桶算法的执行逻辑可以拆解为以下 5 个步骤，Runbook 验证时需要逐项确认实现正确性：

  1. 初始化：设置令牌生成速率 r 和桶容量 b，桶初始令牌数 = b。
  2. 定时填充：每隔 1/r 秒向桶中放入 1 个令牌；若桶已满（令牌数 = b），则丢弃新令牌。
  3. 请求到达：每个请求到达时，检查当前桶中令牌数是否 > 0。
  4. 决策分支：
    • 令牌数 > 0：消耗 1 个令牌，请求放行。
    • 令牌数 = 0：请求被拒绝（返回 429 Too Many Requests）或进入等待队列。
  5. 状态更新：放行后桶中令牌数减 1，等待下一次定时填充。
实现注意：生产代码通常使用延迟计算（lazy refill）优化性能——不在定时器中填充，而是在每次请求时根据时间差计算应补充的令牌数。这种方式避免了定时器开销，且精度更高。

2.3 数学模型与关键公式

令牌桶算法的行为可以用以下数学模型描述，这些公式在 Runbook 的限流阈值验证步骤中直接用于计算预期结果：

指标 公式 说明
当前令牌数 min(b, last_tokens + (now - last_time) × r) 基于时间差补充令牌，不超过桶容量
最大突发请求数 b 桶容量直接决定瞬时可处理的突发请求上限
长期平均速率 r（请求/秒） 在足够长的时间窗口内，平均处理速率趋近于 r
突发恢复时间 b / r（秒） 桶从空到满所需的最短时间

2.4 适用场景分析

令牌桶算法并非万能，其适用性取决于业务对突发容忍度和公平性的要求。下表对比了典型场景的匹配度：

场景 推荐度 原因
API 网关限流 ★★★★★ 允许短时流量尖峰，符合 Web 流量特征
数据库连接池保护 ★★★★☆ 突发连接可被桶容量缓冲，避免连接风暴
消息队列消费速率控制 ★★★★☆ 平滑消费速率，同时允许批量拉取
严格公平限流（如投票系统） ★★☆☆☆ 令牌桶不保证请求间公平，突发时后到请求可能被连续拒绝
资金交易类（不允许突发） ★☆☆☆☆ 突发可能带来资金风险，建议使用漏桶或滑动窗口

2.5 与漏桶算法的对比

在限流算法家族中，令牌桶常与漏桶算法（Leaky Bucket）并列讨论。理解两者的差异有助于在 Runbook 验证中选择正确的限流策略：

对比维度 令牌桶 漏桶
核心思想 以固定速率生成令牌，请求消耗令牌 请求进入桶中，以固定速率漏出处理
突发处理 允许突发（桶容量 b 决定突发量） 严格平滑（桶满则丢弃，输出速率恒定）
输出速率 平均速率 = r，瞬时可高于 r 严格等于 r，无瞬时波动
实现复杂度 中等（需处理时间差计算） 较低（队列 + 定时器）
典型场景 API 限流、微服务保护 流量整形、带宽控制
Runbook 验证陷阱：在自愈剧本中，如果使用令牌桶限流，验证用例必须覆盖突发场景——连续发送 b+1 个请求，确认前 b 个被放行、第 b+1 个被拒绝。仅测试平均速率无法暴露桶容量配置错误。

2.6 代码实现示例（Go 语言）

以下是一个生产级令牌桶的简化实现，展示了延迟计算的核心逻辑。Runbook 验证时可直接引用此代码作为预期行为参考：

package tokenbucket

import (
    "sync"
    "time"
)

type TokenBucket struct {
    mu         sync.Mutex
    rate       float64       // 令牌生成速率（个/秒）
    capacity   float64       // 桶容量
    tokens     float64       // 当前令牌数
    lastRefill time.Time     // 上次补充时间
}

func NewTokenBucket(rate, capacity float64) *TokenBucket {
    return &TokenBucket{
        rate:       rate,
        capacity:   capacity,
        tokens:     capacity,
        lastRefill: time.Now(),
    }
}

// TryConsume 尝试消耗一个令牌，成功返回 true，失败返回 false
func (tb *TokenBucket) TryConsume() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    // 延迟计算：根据时间差补充令牌
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens += elapsed * tb.rate
    if tb.tokens > tb.capacity {
        tb.tokens = tb.capacity
    }
    tb.lastRefill = now

    // 判断是否允许请求
    if tb.tokens >= 1 {
        tb.tokens--
        return true
    }
    return false
}
验证要点：
  • 确认 tokens 上限为 capacity，不会无限累积。
  • 确认 lastRefill 在每次消耗时更新，而非仅在补充时更新。
  • 确认并发安全：sync.Mutex 保护了所有共享状态。

2.7 自愈剧本中的令牌桶验证策略

在 Runbook 验证案例中，针对令牌桶限流需要设计以下三类测试用例：

  • 稳态测试：以速率 r 持续发送请求，持续 10 秒，确认所有请求均被放行，无拒绝。
  • 突发测试：瞬间发送 b+1 个请求，确认前 b 个成功、第 b+1 个返回 429。
  • 恢复测试：突发后等待 b/r 秒，再次发送请求，确认桶已恢复、请求被放行。

这三类测试覆盖了令牌桶的填充、消耗、溢出和恢复四个核心状态，是自愈剧本验证限流组件正确性的最低要求。

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