源码漏桶算法底层原理？

访客源码剖析 2026-06-08 01:05:58 1

从令牌桶到流量整形，一文带你彻底搞懂

目录导读

什么是漏桶算法？核心思想与演化背景
漏桶算法的数学建模与流量整形逻辑
源码级拆解：漏桶算法的三种常见实现
漏桶 vs 令牌桶：本质区别与适用场景选择
经典面试问答：漏桶算法高频问题深度解析

什么是漏桶算法？核心思想与演化背景

漏桶算法（Leaky Bucket Algorithm）是一种经典的流量整形（Traffic Shaping）与限流（Rate Limiting）算法，其核心思想来源于日常生活中“水桶漏水”的物理模型。

算法本质：将任意速率的请求（水流）注入一个固定容量的桶中，桶底部有一个恒定速率的“漏孔”向外滴水（处理请求），当桶被注满时，新注入的水会溢出（请求被拒绝或丢弃），这一机制保证了无论外部请求多猛烈，系统始终以固定速率处理请求，从而保护后端服务不被突发流量冲垮。

演化背景：在计算机早期网络通信中，漏桶算法最早应用于ATM（异步传输模式）网络的数据包整形，后来逐渐被引入分布式系统、API网关和微服务限流中，与后来流行的令牌桶算法不同，漏桶更强调“输出速率恒定”，而非“允许突发”。

关键参数：

capacity：桶的最大容量（最大请求积压量）
rate：漏孔速率（每秒流出请求数）
bucket：当前桶中水量（当前等待处理的请求数）

适用场景：需要严格平滑流量的场景，如日志收集、数据库写入限流、稳定的MQ消费速率控制。

漏桶算法的数学建模与流量整形逻辑

1 队列模型

漏桶本质是一个单服务器队列系统（M/D/1模型的近似），桶相当于有限容量的缓冲区，漏孔速率相当于服务速率，数学上，漏桶的状态由以下方程决定：

bucket(t) = min(capacity, max(0, bucket(t-1) + incoming_requests - rate * Δt))

incoming_requests：Δt时间内新到达的请求数
rate * Δt：Δt时间内流出的请求数
bucket(t-1)：上一时刻桶中积压量

2 流量整形机制

漏桶的流量整形体现在两个方面：

输出平滑：无论输入是突发还是平稳，输出速率恒定为 rate（在桶未空的情况下）。
过载保护：当桶满时，新到达的请求被直接拒绝（溢出丢弃），实现硬性限流。

相比于令牌桶：令牌桶可以允许短时间内的突发流量（只要令牌足够），而漏桶在任何时刻都严格限制输出速率，不允许任何意义上的突发输出。

源码级拆解：漏桶算法的三种常见实现

以下以Go语言伪代码为例,展示漏桶算法的底层实现逻辑，实际生产环境可参考Nginx的limit_req模块、Guava RateLimiter（虽叫RateLimiter但底层是令牌桶变种）或开源库 go-simple-rate-limit。

1 基础版本：基于时间滑动窗口

type LeakyBucket struct {
    capacity   int       // 桶容量
    rate       float64   // 漏出速率（请求/秒）
    water      float64   // 当前水量
    lastTime   time.Time // 上次漏水时间
    mu         sync.Mutex
}
func (lb *LeakyBucket) Allow() bool {
    lb.mu.Lock()
    defer lb.mu.Unlock()
    now := time.Now()
    // 先漏水：根据时间差计算流出的水量
    elapsed := now.Sub(lb.lastTime).Seconds()
    leaked := elapsed * lb.rate
    lb.water = math.Max(0, lb.water - leaked)
    lb.lastTime = now
    if lb.water < float64(lb.capacity) {
        lb.water++
        return true
    }
    return false
}

底层原理：每次调用Allow()时，先根据时间差计算出这段时间内漏出的水量，然后判断剩余水量是否小于桶容量，若小于则加水（允许请求），否则拒绝。

2 高性能版本：基于队列与定时器

type LeakyBucketQueue struct {
    queue chan struct{}  // 用带缓冲channel模拟漏桶
    ticker *time.Ticker  // 定时器控制漏出速率
}
func NewLeakyBucketQueue(capacity int, rate int) *LeakyBucketQueue {
    b := &LeakyBucketQueue{
        queue: make(chan struct{}, capacity),
        ticker: time.NewTicker(time.Second / time.Duration(rate)),
    }
    go func() {
        for range b.ticker.C {
            <-b.queue  // 每 tick 一次从队列取出一个请求（模拟漏水）
        }
    }()
    return b
}
func (b *LeakyBucketQueue) Allow() bool {
    select {
    case b.queue <- struct{}{}:
        return true
    default:
        return false  // 桶满，溢出丢弃
    }
}

底层原理：利用带缓冲的channel做桶，定时器控制输出速率，每次定时器触发时从channel中取出一个元素（处理一个请求），新请求尝试放入channel，若channel已满则拒绝。

3 纯数学版本：适用于分布式环境

// 使用Redis实现分布式漏桶
const (
    BUCKET_KEY = "leaky_bucket:%s"
    capacity   = 100
    rate       = 10 // 每秒10个请求
)
func RedisLeakyBucket(ctx context.Context, userId string) bool {
    key := fmt.Sprintf(BUCKET_KEY, userId)
    // 1. 获取当前水量（使用ZSET按时间戳排序，模拟队列）
    // 2. 移除超过1秒的旧请求（模拟漏水）
    // 3. 判断当前数量是否超过容量
    // 实际操作：使用LUA脚本保证原子性
}

底层原理：利用Redis的有序集合（Sorted Set）模拟时间窗口，每次请求时，先移除时间窗口外的旧请求（相当于漏水），再判断当前请求数是否小于容量。

漏桶 vs 令牌桶：本质区别与适用场景选择

特性	漏桶算法	令牌桶算法
输出速率	严格恒定	恒定的峰值速率，允许突发
突发处理	不允许突发输出	允许短时突发（有令牌积累）
实现复杂度	低（只需桶+定时器）	中等（需维护令牌生成）
典型应用	日志采集、数据库限流	API限流、网络流量整形
溢出行为	请求直接丢弃	请求等待令牌或立即丢弃