3、漏桶算法原理

漏桶算法（Leaky Bucket）是流量整形与限流领域最经典的算法之一。它通过一个固定容量的“桶”和恒定速率的“漏水”行为，将任意速率、任意突发程度的输入流量，平滑为固定速率的输出流量。理解漏桶的工作机制、与令牌桶的差异以及适用场景，是构建可靠限流骨架的基础。

3.1 工作机制

漏桶算法的核心思想可以用一个底部有漏洞的水桶来类比：

• 桶（Bucket）：一个固定容量的容器，用于暂存请求或数据包。桶的容量决定了系统能够容忍的最大突发量。
• 漏水速率（Leak Rate）：桶底部漏洞的流出速率，即系统处理请求的恒定速率。无论桶内积压了多少请求，漏出的速率始终固定。
• 流入（Inflow）：外部请求以任意速率注入桶中。如果桶未满，请求被暂存；如果桶已满，新请求被丢弃（拒绝服务）。
• 流出（Outflow）：桶以恒定速率将请求漏出，交由后端处理。

下图展示了漏桶算法的完整工作流程：

3.2 与令牌桶算法的区别

漏桶算法与令牌桶算法是限流领域最常被对比的两种算法。虽然它们都用于控制流量速率，但设计哲学和适用场景截然不同。下表从多个维度进行对比：

下图直观对比了两种算法在相同输入下的输出行为差异：

3.3 适用场景

漏桶算法在以下场景中具有明显优势：

• 网络流量整形（Traffic Shaping）：在路由器、交换机中，漏桶用于将突发的网络数据包平滑为恒定速率，避免拥塞。例如，ATM网络中的漏桶整形。
• 音视频流媒体传输：视频流需要恒定比特率（CBR）传输，漏桶可以保证数据包以固定间隔发送，防止播放端缓冲溢出或欠载。
• 数据库连接池限流：当数据库连接池的处理能力固定时，漏桶可以确保请求以不超过连接池处理能力的速率进入，避免连接池被突发请求打满。
• 硬件资源保护：对于磁盘I/O、GPU计算等具有固定处理能力的硬件资源，漏桶可以防止突发请求导致硬件过载。
• 消息队列消费速率控制：当消费者处理能力固定时，漏桶可以控制消息投递速率，避免消费者被压垮。

3.4 Go语言实现要点

在Go中实现漏桶算法时，通常有两种方式：

1. 基于时间戳的计数器实现：记录上次漏水时间和当前水位，每次请求到达时计算应漏水量，更新水位。
2. 基于定时器的队列实现：使用一个固定长度的队列，定时器以固定速率从队列头部取出请求处理。

以下是一个基于时间戳的漏桶限流器核心代码：

package leakybucket

import (
    "sync"
    "time"
)

type LeakyBucket struct {
    rate       float64       // 漏水速率（请求/秒）
    capacity   float64       // 桶容量
    water      float64       // 当前水位
    lastLeakMs int64         // 上次漏水时间戳（毫秒）
    mu         sync.Mutex
}

func NewLeakyBucket(rate, capacity float64) *LeakyBucket {
    return &LeakyBucket{
        rate:       rate,
        capacity:   capacity,
        water:      0,
        lastLeakMs: time.Now().UnixMilli(),
    }
}

// Allow 判断是否允许请求通过
func (lb *LeakyBucket) Allow() bool {
    lb.mu.Lock()
    defer lb.mu.Unlock()

    now := time.Now().UnixMilli()
    elapsed := float64(now - lb.lastLeakMs) / 1000.0 // 转为秒

    // 计算这段时间内漏掉的水量
    leaked := elapsed * lb.rate
    lb.water = lb.water - leaked
    if lb.water < 0 {
        lb.water = 0
    }

    lb.lastLeakMs = now

    // 判断桶是否已满
    if lb.water < lb.capacity {
        lb.water++
        return true
    }
    return false
}