4. 限流基础：令牌桶、漏桶、固定窗口、滑动窗口算法原理与 Go 实现

限流是保障分布式系统稳定性的第一道防线。在生产环境中，突发的流量尖峰、异常的重试风暴或恶意的 DDoS 攻击，都可能导致后端服务雪崩。本章将深入剖析四种经典限流算法的核心原理、适用场景，并给出可直接用于压测诊断的 Go 实现。

压测视角： 限流算法的选择直接影响尾延迟（Tail Latency）的分布形态。例如，固定窗口的“临界突变”会在压测曲线中产生周期性的毛刺，而令牌桶的平滑特性则能显著降低 P99 延迟的抖动。

4.1 令牌桶算法（Token Bucket）

4.1.1 原理

令牌桶以固定速率向桶中放入令牌，每个请求必须获取一个令牌才能被处理。桶有容量上限，允许突发流量消耗积攒的令牌。当桶空时，请求被拒绝或等待。

  • 关键参数： 速率 r（每秒放入令牌数）、容量 b（最大突发量）。
  • 行为特征： 长期平均速率被限制在 r，短期允许突发到 b。
  • 适用场景： 允许一定突发流量的网络接口、API 网关、流量整形。
算法核心： 令牌桶不记录请求时间戳，而是记录“上次填充时间”和“当前令牌数”，通过时间差计算应补充的令牌数，避免定时器开销。
令牌桶算法流程 令牌生成器 速率 r/s 令牌桶（容量 b） 令牌 令牌 令牌 请求到达 有令牌？ 通过处理 拒绝/等待 突发特性 桶满时可突发 消耗积攒令牌 桶空则限流

4.1.2 Go 实现

package limiter

import (
    "sync"
    "time"
)

type TokenBucket struct {
    rate       float64    // 每秒放入令牌数
    capacity   float64    // 桶容量
    tokens     float64    // 当前令牌数
    lastTime   time.Time  // 上次填充时间
    mu         sync.Mutex
}

func NewTokenBucket(rate, capacity float64) *TokenBucket {
    return &TokenBucket{
        rate:     rate,
        capacity: capacity,
        tokens:   capacity, // 初始满桶
        lastTime: time.Now(),
    }
}

func (tb *TokenBucket) Allow() 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 > tb.capacity {
        tb.tokens = tb.capacity
    }
    tb.lastTime = now

    if tb.tokens >= 1 {
        tb.tokens--
        return true
    }
    return false
}
压测陷阱： 上述实现使用 time.Now() 获取时间，在压测场景下（百万级 QPS），频繁调用 time.Now() 本身会成为性能瓶颈。生产环境可考虑使用 time.Now().UnixNano() 减少对象分配，或采用无锁化设计。

4.2 漏桶算法（Leaky Bucket）

4.2.1 原理

漏桶将请求视为水滴，以固定速率从桶底漏出处理。桶有容量上限，当桶满时新请求被丢弃。漏桶强制输出速率恒定，不允许突发。

  • 关键参数： 漏出速率 r（每秒处理请求数）、桶容量 b（最大排队数）。
  • 行为特征： 输出速率严格恒定，请求延迟与桶内积压量成正比。
  • 适用场景： 数据库连接池、下游处理能力固定的系统、需要平滑输出的场景。
与令牌桶对比： 令牌桶允许突发，漏桶强制平滑。在压测中，漏桶会导致请求排队延迟增加，而令牌桶则可能因突发导致下游瞬时压力。

4.2.2 Go 实现（基于队列）

type LeakyBucket struct {
    rate     time.Duration // 每个请求的处理间隔
    capacity int           // 桶容量
    queue    chan struct{} // 请求队列
}

func NewLeakyBucket(rate time.Duration, capacity int) *LeakyBucket {
    lb := &LeakyBucket{
        rate:     rate,
        capacity: capacity,
        queue:    make(chan struct{}, capacity),
    }
    go lb.leak()
    return lb
}

func (lb *LeakyBucket) leak() {
    ticker := time.NewTicker(lb.rate)
    defer ticker.Stop()
    for range ticker.C {
        select {
        case <-lb.queue:
            // 处理请求（实际业务逻辑）
        default:
            // 队列为空，跳过
        }
    }
}

func (lb *LeakyBucket) Allow() bool {
    select {
    case lb.queue <- struct{}{}:
        return true
    default:
        return false // 桶满，拒绝
    }
}

4.3 固定窗口算法（Fixed Window）

4.3.1 原理

将时间划分为固定长度窗口（如 1 秒），每个窗口内允许通过的请求数上限为阈值。窗口切换时计数器重置。

  • 关键参数： 窗口大小 w、窗口内阈值 limit。
  • 行为特征： 实现简单，但存在“临界突变”问题：窗口切换瞬间可能涌入 2 倍流量。
  • 适用场景： 对精度要求不高的简单限流、非关键路径的速率限制。
压测诊断重点： 固定窗口的临界突变会在压测的每秒请求数（RPS）曲线上产生“锯齿”状波动。如果压测发现 P99 延迟在每秒边界处出现规律性尖峰，应优先怀疑固定窗口限流。

4.3.2 Go 实现

type FixedWindow struct {
    limit    int
    window   time.Duration
    count    int
    startAt  time.Time
    mu       sync.Mutex
}

func NewFixedWindow(limit int, window time.Duration) *FixedWindow {
    return &FixedWindow{
        limit:   limit,
        window:  window,
        startAt: time.Now(),
    }
}

func (fw *FixedWindow) Allow() bool {
    fw.mu.Lock()
    defer fw.mu.Unlock()

    now := time.Now()
    if now.Sub(fw.startAt) >= fw.window {
        fw.count = 0
        fw.startAt = now
    }

    if fw.count < fw.limit {
        fw.count++
        return true
    }
    return false
}

4.4 滑动窗口算法（Sliding Window）

4.4.1 原理

滑动窗口将时间窗口细分为多个小格子（如 1 秒窗口分为 10 个 100ms 格子），每个格子独立计数。窗口滑动时，丢弃过期格子，累加当前窗口内所有格子的计数。

  • 关键参数： 窗口大小 w、格子数 n、窗口内阈值 limit。
  • 行为特征： 解决了固定窗口的临界突变问题，限流曲线平滑，精度由格子数决定。
  • 适用场景： 对限流精度要求高的生产环境、微服务网关、实时流量控制。
精度与性能权衡： 格子数越多，限流越平滑，但内存占用和计算开销也越大。通常 10~20 个格子即可满足大部分生产需求。
滑动窗口 vs 固定窗口：临界突变对比 固定窗口 窗口 1（已满） 窗口 2（重置） 临界点：流量瞬间翻倍 滑动窗口 当前 窗口滑动 滑动窗口：过期格子自动丢弃 新请求计入当前格子，窗口总计数平滑变化

4.4.2 Go 实现

type SlidingWindow struct {
    limit    int
    window   time.Duration
    slots    int
    counts   []int
    slotDur  time.Duration
    lastTime time.Time
    mu       sync.Mutex
}

func NewSlidingWindow(limit int, window time.Duration, slots int) *SlidingWindow {
    return &SlidingWindow{
        limit:    limit,
        window:   window,
        slots:    slots,
        counts:   make([]int, slots),
        slotDur:  window / time.Duration(slots),
        lastTime: time.Now(),
    }
}

func (sw *SlidingWindow) Allow() bool {
    sw.mu.Lock()
    defer sw.mu.Unlock()

    now := time.Now()
    elapsed := now.Sub(sw.lastTime)
    // 滑动过期格子
    if elapsed >= sw.slotDur {
        slideCount := int(elapsed / sw.slotDur)
        if slideCount > sw.slots {
            slideCount = sw.slots
        }
        // 移除过期格子，前移
        sw.counts = append(sw.counts[:0], sw.counts[slideCount:]...)
        // 补零
        for i := len(sw.counts); i < sw.slots; i++ {
            sw.counts = append(sw.counts, 0)
        }
        sw.lastTime = now
    }

    // 计算当前窗口总计数
    total := 0
    for _, c := range sw.counts {
        total += c
    }

    if total < sw.limit {
        sw.counts[sw.slots-1]++
        return true
    }
    return false
}

4.5 四种算法对比总结

算法 输出特性 突发能力 临界突变 实现复杂度 内存开销 压测推荐度
令牌桶 平均平滑，允许突发 是 无 低 低（仅计数器） ★★★★★
漏桶 严格平滑 否 无 中（需队列） 中（队列） ★★★★
固定窗口 阶梯状 是（窗口内） 严重 极低 极低 ★★
滑动窗口 平滑 是（窗口内） 无 中 中（格子数组） ★★★★★
压测选型建议： 对于生产环境的限流组件，优先选择令牌桶或滑动窗口。固定窗口仅适用于非关键路径的简单限制。漏桶适合下游处理能力固定的场景，但需注意队列堆积导致的延迟增加。

4.6 压测诊断视角的算法选择

在《限流尾延迟Go压测诊断》课程中，我们后续的压测实验将主要基于令牌桶和滑动窗口进行。原因如下：

  1. 尾延迟稳定性： 令牌桶的突发特性在压测中会产生可预测的延迟分布，便于诊断系统瓶颈。
  2. 临界突变规避： 滑动窗口消除了固定窗口的周期性毛刺，使压测曲线更真实反映系统处理能力。
  3. Go 标准库兼容： Go 官方扩展包 golang.org/x/time/rate 基于令牌桶实现，可直接用于压测工具链集成。
← 上一章 📖 返回目录 下一章 →