限流算法

作者： /

为什么需要限流

限流（Rate Limiting）控制单位时间内的请求数量，目标：防止资源耗尽、避免服务雪崩、保证服务质量、抵御恶意攻击。核心是选对算法——四种主流算法各有取舍。

1. 计数器（固定窗口）

最简单：一个窗口周期内计数，超过阈值拒绝。临界问题：窗口边界前后各放行一批，可能出现”两倍阈值”的瞬时流量。

type CounterLimiter struct {
    rate  int
    begin time.Time
    cycle time.Duration
    count int
    mu    sync.Mutex
}

func (l *CounterLimiter) Allow() bool {
    l.mu.Lock(); defer l.mu.Unlock()
    if time.Now().After(l.begin.Add(l.cycle)) {
        l.begin = time.Now()
        l.count = 0
    }
    if l.count >= l.rate { return false }
    l.count++
    return true
}

2. 滑动窗口

把窗口切成多个小段（segment），随时间滑动，统计”当前窗口内”所有段的计数——消除临界问题，更精确。

type SlidingWindowLimiter struct {
    rate        int
    segmentSize time.Duration
    segments    []int   // 环形/滑动数组，每段一个计数
    mu          sync.Mutex
    lastTime    time.Time
}

func (l *SlidingWindowLimiter) Allow() bool {
    l.mu.Lock(); defer l.mu.Unlock()
    now := time.Now()
    // 推进窗口：把过期的段清零
    steps := int(now.Sub(l.lastTime) / l.segmentSize)
    l.lastTime = now
    for i := 0; i < steps && i < len(l.segments); i++ {
        l.segments = append(l.segments[1:], 0)
    }
    total := 0
    for _, c := range l.segments { total += c }
    if total >= l.rate { return false }
    l.segments[len(l.segments)-1]++
    return true
}

代价：实现更复杂、内存开销与段数成正比。

3. 漏桶

请求任意速率进桶，固定速率流出；桶满拒绝。输出平滑，但不能应对突发。

type LeakyBucketLimiter struct {
    rate     float64   // 流出速率（请求/秒）
    capacity float64
    water    float64
    lastMs   int64
    mu       sync.Mutex
}

func (l *LeakyBucketLimiter) Allow() bool {
    l.mu.Lock(); defer l.mu.Unlock()
    nowMs := time.Now().UnixNano() / 1e6
    elapsed := nowMs - l.lastMs
    l.lastMs = nowMs
    l.water -= float64(elapsed) * l.rate / 1000   // 按时间漏水
    if l.water < 0 { l.water = 0 }
    if l.water >= l.capacity { return false }
    l.water++
    return true
}

4. 令牌桶（业界主流）

以固定速率生成令牌存进桶（有容量上限），请求消耗令牌。桶里有囤积的令牌 → 允许突发流量，同时长期速率被平均速率约束——兼顾平滑与弹性，是 Nginx/guava/rate 库的默认选择。

type TokenBucketLimiter struct {
    rate     float64   // 令牌生成速率（个/秒）
    capacity float64   // 桶容量（最大突发）
    tokens   float64
    lastMs   int64
    mu       sync.Mutex
}

func (l *TokenBucketLimiter) Allow() bool {
    l.mu.Lock(); defer l.mu.Unlock()
    nowMs := time.Now().UnixNano() / 1e6
    elapsed := nowMs - l.lastMs
    l.lastMs = nowMs
    l.tokens += float64(elapsed) * l.rate / 1000   // 生成令牌
    if l.tokens > l.capacity { l.tokens = l.capacity }
    if l.tokens < 1 { return false }
    l.tokens--
    return true
}

算法对比

算法实现难度平滑度突发流量适用
计数器简单低不支持简单限流
滑动窗口中等中部分支持需要更精确
漏桶中等高不支持要求输出平滑
令牌桶中等高支持主流方案

生产首选：golang.org/x/time/rate

标准生态里直接用官方限流器（令牌桶实现），别自己造轮子：

limiter := rate.NewLimiter(rate.Limit(10), 10)   // 每秒 10 个，桶容量 10

if limiter.Allow() {
    // 放行
} else {
    // 限流
}

分布式限流

单机限流在多实例下各自计数，总量会超。常见方案：

  • Redis + Lua：脚本原子执行”计数+过期”，如固定窗口的 INCR + EXPIRE；
  • Redis 令牌桶：令牌存 Redis，分布式共享；
  • 网关层：Nginx（limit_req）、Envoy 内置限流。
// Redis + Lua 固定窗口（原子，防并发超发）
script := `
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local current = redis.call('GET', key)
if not current then
    redis.call('SET', key, 1, 'EX', window)
    return 1
end
if tonumber(current) >= limit then return 0 end
redis.call('INCR', key)
return 1`
// rdb.Eval(ctx, script, []string{key}, limit, window.Seconds())

最佳实践

  • 按业务选算法：普通接口计数器/滑动窗口够用；突发容忍场景上令牌桶；
  • 多级限流：网关层 + 服务层 + 方法层叠加；
  • 区分用户：VIP 与普通用户不同阈值；
  • 被限流时优雅降级：返回明确的 429/排队提示，而不是让客户端超时重试打爆；
  • 监控限流命中率，动态调整阈值。
滚动至顶部