令牌桶算法 (Token Bucket)

令牌桶算法是限流中最常用的算法之一，它最大的特点是允许一定程度的突发流量。

工作原理

逻辑图解

流量生成速率 R 个/秒
      ↓
+-----------+
|  令牌生成  |
+-----------+
      ↓
+-----------+
|   令牌桶   |  ← 容量上限 B
|  (Tokens) |
+-----------+
      ↓ 取出令牌 (如果没令牌则拦截)
      ↓
   [ 请求 ] → 通过

1. 生成令牌：系统以恒定的速率（如每秒 $R$ 个）往桶里放入令牌。
2. 桶的容量：桶有一个固定的容量 $B$。如果桶满了，新生成的令牌会被丢弃。
3. 消耗令牌：每个请求进入系统时，必须先从桶里取出一个令牌：
   • 如果桶里有令牌，请求被允许通过并消耗一个令牌。
   • 如果桶里没令牌，请求被拒绝（或进入排队等待）。

Go 语言实现 (示例)

type TokenBucket struct {
    capacity  float64    // 桶容量 B
    rate      float64    // 令牌生成速率 R (个/秒)
    tokens    float64    // 当前令牌数
    lastTime  time.Time  // 上次更新时间
    mu        sync.Mutex
}
 
func (b *TokenBucket) Allow() bool {
    b.mu.Lock()
    defer b.mu.Unlock()
    
    now := time.Now()
    // 1. 根据经过的时间补充令牌
    passedTime := now.Sub(b.lastTime).Seconds()
    b.tokens += passedTime * b.rate
    
    if b.tokens > b.capacity {
        b.tokens = b.capacity
    }
    b.lastTime = now
 
    // 2. 判断令牌是否足够
    if b.tokens >= 1 {
        b.tokens--
        return true
    }
    return false
}

核心特点

• 允许突发流量：如果一段时间内没有请求，桶里会积攒令牌（最高达到 $B$ 个）。当突发流量到来时，系统可以瞬间处理这 $B$ 个请求，而不会被限流。
• 平均速率稳定：虽然允许短时间的突发，但长期的平均处理速率仍被限制在令牌生成的速率 $R$ 左右。

应用场景

• API 网关：如 Spring Cloud Gateway 中的 RequestRateLimiter 默认就是基于 Redis 实现的令牌桶。
• 流量整形：需要保证长期平均速率，但可以接受短期高峰的业务。