3. 限流基础理论：令牌桶算法、漏桶算法、计数器算法原理与对比

在深入 etcd 客户端限流实战之前，必须理解三种最经典的限流算法。etcd 的 --experimental-enable-request-limiter 和客户端侧的限流器均基于这些理论实现。本节将剖析令牌桶、漏桶、计数器算法的核心原理、适用场景及本质差异。

3.1 计数器算法（Counter Algorithm）

计数器是最直观的限流实现，在固定时间窗口内维护一个计数器，请求到达时计数器加 1，超过阈值则拒绝。

核心逻辑： 将时间划分为固定大小的窗口（如 1 秒），每个窗口内记录请求总数，窗口结束时计数器归零。

3.1.1 原理与实现

  • 数据结构： 一个原子整数 + 窗口起始时间戳。
  • 判定流程： 请求到达 → 检查当前时间是否在窗口内 → 是则计数器 +1 并判断是否超限 → 否则重置窗口。
  • 临界问题： 窗口切换瞬间可能出现两倍阈值的突发流量（如 0:59 秒 100 个请求 + 1:00 秒 100 个请求，实际 1 秒内 200 个请求）。
// 简化版计数器限流（Go 伪代码）
type CounterLimiter struct {
    mu       sync.Mutex
    limit    int
    window   time.Duration
    count    int
    startAt  time.Time
}

func (c *CounterLimiter) Allow() bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    now := time.Now()
    if now.Sub(c.startAt) > c.window {
        c.count = 0
        c.startAt = now
    }
    if c.count >= c.limit {
        return false
    }
    c.count++
    return true
}

3.2 漏桶算法（Leaky Bucket）

漏桶将请求视为水滴，桶以固定速率漏水（处理请求），桶满则新请求被丢弃。核心是 强制平滑流量，不允许任何突发。

类比： 水龙头以任意速率向桶中注水，桶底小孔以恒定速率漏水。桶满时水溢出（请求被拒绝）。

3.2.1 两种实现方式

实现方式 描述 特点
队列 + 定时消费 请求入队，后台协程以固定速率从队列取出处理 实现简单，但队列长度受内存限制
漏桶算法（数学计算） 记录上次漏水时间和水量，计算当前桶内剩余水量 无队列，无锁竞争，性能高 
// 数学计算版漏桶（Go 伪代码）
type LeakyBucket struct {
    mu       sync.Mutex
    rate     float64   // 每秒漏出速率
    capacity float64   // 桶容量
    water    float64   // 当前水量
    lastTime time.Time
}

func (l *LeakyBucket) Allow() bool {
    l.mu.Lock()
    defer l.mu.Unlock()
    now := time.Now()
    elapsed := now.Sub(l.lastTime).Seconds()
    // 先漏水
    l.water = math.Max(0, l.water - elapsed * l.rate)
    l.lastTime = now
    if l.water < l.capacity {
        l.water++
        return true
    }
    return false
}

3.3 令牌桶算法（ Bucket）

令牌桶是 etcd 客户端限流器 rate.Limiter 的底层实现。它以固定速率向桶中放入令牌，请求到达时消耗一个令牌，桶空则请求等待或拒绝。与漏桶不同，令牌桶 允许一定程度的突发。

关键参数： 令牌生成速率 r（个/秒）、桶容量 b（最大突发量）。突发时最多可一次性消耗 b 个令牌。

3.3.1 工作原理

  • 令牌生成： 后台或惰性计算方式，以速率 r 向桶中添加令牌，桶满则停止。
  • 请求处理： 从桶中取出 1 个令牌（或 N 个），成功则放行，失败则阻塞或拒绝。
  • 突发能力： 桶中最多积累 b 个令牌，空闲时桶满，突发时可一次性消耗所有令牌。
// Go 标准库 rate.Limiter 核心逻辑（简化）
type Limiter struct {
    limit    Limit       // 每秒令牌数
    burst    int         // 桶容量
    mu       sync.Mutex
    tokens   float64
    lastTime time.Time
}

func (lim *Limiter) reserveN(now time.Time, n int) bool {
    lim.mu.Lock()
    defer lim.mu.Unlock()
    // 计算时间差，补充令牌
    elapsed := now.Sub(lim.lastTime).Seconds()
    lim.tokens += elapsed * float64(lim.limit)
    if lim.tokens > float64(lim.burst) {
        lim.tokens = float64(lim.burst)
    }
    lim.lastTime = now
    if lim.tokens < float64(n) {
        return false  // 令牌不足
    }
    lim.tokens -= float64(n)
    return true
}

3.4 三种算法对比

维度 计数器 漏桶 令牌桶
突发处理 窗口内允许突发，但窗口边界有漏洞 完全禁止突发 允许突发（最多消耗桶容量）
流量平滑度 窗口内不平滑 严格平滑 短期可突发，长期平滑
实现复杂度 低 中 中高（需处理时间精度）
内存开销 低（1 个计数器） 低（队列版需内存） 低（2 个浮点数）
适用场景 简单 API 限流，可接受边界毛刺 数据库连接池、网络带宽控制 etcd 客户端、微服务网关、通用限流
etcd 使用 etcd 服务端 --max-request-bytes 等简单限制 不直接使用 客户端 rate.Limiter、服务端限流器

3.5 算法选择建议

etcd 客户端限流场景： 推荐使用令牌桶算法。原因：etcd 客户端需要容忍短时突发（如 Watch 重连、批量写入），同时保证长期平均 QPS 可控。漏桶过于严格，计数器存在窗口边界问题。
  • 需要严格平滑： 选择漏桶（如网络带宽限速、数据库连接池）。
  • 需要简单实现且能接受毛刺： 选择计数器（如非关键路径的日志限流）。
  • 需要兼顾突发与长期限制： 选择令牌桶（etcd 客户端、API 网关、微服务限流）。

3.6 三种算法核心流程对比（SVG）

三种限流算法核心流程对比 三种限流算法核心流程对比 计数器算法 固定时间窗口 • 窗口内计数 +1 • 超阈值则拒绝 • 窗口结束归零 • 边界存在双倍突发风险 适用：简单 API 限流 漏桶算法 固定速率漏水 • 请求入桶（注水） • 桶底以固定速率漏水 • 桶满则溢出（拒绝） • 完全禁止突发 适用：带宽控制、连接池 令牌桶算法 固定速率生成令牌 • 定时向桶中放令牌 • 请求消耗 1 个令牌 • 桶空则等待或拒绝 • 允许突发（桶容量） 适用：etcd 客户端、网关 核心差异总结 • 计数器：时间窗口 + 计数，实现最简单，但窗口边界存在双倍流量漏洞。 • 漏桶：强制平滑，不允许任何突发，适合需要严格整形流量的场景。 • 令牌桶：允许突发 + 长期平滑，etcd 客户端限流器（rate.Limiter）的底层实现。 etcd 客户端推荐：令牌桶

3.7 本章小结

  • 计数器 适合简单场景，但存在窗口边界漏洞。
  • 漏桶 强制平滑，适合带宽控制等不允许突发的场景。
  • 令牌桶 兼顾突发与长期限制，是 etcd 客户端限流的最佳选择。
  • etcd 的 rate.Limiter 基于令牌桶实现，后续章节将深入其源码与调优。
← 上一章 📖 返回目录 下一章 →