调度与限流 #05：漏桶

漏桶（Leaky Bucket）将请求放入有界队列，以固定速率匀速处理，无论输入多快输出永远恒定；Nginx limit_req、TCP 流量整形、QoS 调度广泛采用此模型。

相关文章：令牌桶 · 滑动窗口计数器 · 滑动窗口日志

目录

问题背景

简单计数器与令牌桶的不足

固定窗口计数器有临界突发问题；令牌桶虽然解决了突发，但允许在桶容量范围内的瞬时冲击。在某些场景下，这种瞬时冲击仍然会压垮下游：

• 数据库写入：后端 DB 每秒只能稳定处理 500 写操作，一次 500 个请求同时到来会导致连接池耗尽。
• 网络带宽整形：ISP 需要保证用户流量严格不超过签约带宽，而不仅仅是"平均不超过"。
• 消息队列消费：消费者处理能力固定，突发消息需要排队而非直接丢弃。

漏桶的解法

漏桶模型将请求视为"水"，桶为有界队列：

• 请求进入队列（入水）；队列满则丢弃新请求（溢出）。
• 后台以固定速率 rate 从队列头取出请求处理（匀速漏水）。
• 无论输入速率多高，输出速率永远恒定等于 rate。

两种实现变体：

核心数据结构

LeakyBucket {
    queue:        Queue<Request>   // 有界 FIFO 队列，存放待处理请求
    capacity:     int              // 队列最大容量（桶的大小），决定最大缓冲量
    rate:         float            // 处理速率，单位：请求/秒（出水速率）
    lastLeakTime: long             // 上次执行漏水的时间戳（纳秒），懒惰计算用
}

字段说明：

注：后台线程实现不需要 lastLeakTime，每隔 1/rate 秒唤醒一次直接取一个请求；懒惰计算实现（类似令牌桶的填充方式）则需要此字段在请求到来时批量处理积累的出队操作。

enqueue(request) 伪代码

function enqueue(bucket, request):
    lock(bucket)
    try:
        if queue.size() < bucket.capacity:
            bucket.queue.addLast(request)    // 入队尾部，FIFO
            return QUEUED                    // 告知调用方：已排队
        else:
            return DROPPED                   // 桶满，直接丢弃
    finally:
        unlock(bucket)

流量整形变体（不丢弃，阻塞等待空位）：

function enqueue_blocking(bucket, request, timeoutNanos):
    deadline = currentTimeNanos() + timeoutNanos
    loop:
        lock(bucket)
        try:
            if queue.size() < bucket.capacity:
                bucket.queue.addLast(request)
                return QUEUED
            if currentTimeNanos() >= deadline:
                return TIMEOUT               // 等待超时才丢弃
        finally:
            unlock(bucket)
        sleep(1_000_000)                     // 等 1ms 后重试

leak() 伪代码

4.1 后台线程实现（简单直接）

// 后台线程：每隔 intervalNanos = 1_000_000_000 / rate 纳秒唤醒一次
function leakLoop(bucket):
    intervalNanos = (long)(1_000_000_000.0 / bucket.rate)
    loop forever:
        sleep(intervalNanos)
        lock(bucket)
        try:
            if not bucket.queue.isEmpty():
                request = bucket.queue.removeFirst()  // 取队头
                process(request)                      // 交给处理线程
        finally:
            unlock(bucket)

缺点：精度受 OS 调度抖动影响；高 rate（如 10000/s）时线程频繁唤醒开销大。

4.2 懒惰计算实现（推荐，批量出队）

function leak(bucket):
    lock(bucket)
    try:
        now          = currentTimeNanos()
        elapsed      = now - bucket.lastLeakTime          // 距上次漏水的纳秒数
        elapsedSec   = max(0.0, elapsed / 1_000_000_000.0) // 防时钟回拨
        canLeak      = (int)(elapsedSec * bucket.rate)    // 本次应漏出的请求数

        processed = 0
        while processed < canLeak and not bucket.queue.isEmpty():
            request = bucket.queue.removeFirst()
            process(request)
            processed++

        if canLeak > 0:
            bucket.lastLeakTime = now                     // 仅当有进展时更新时间戳
    finally:
        unlock(bucket)

调用时机：在每次 enqueue 之前调用 leak()，先清理已到期的出队操作，再判断队列是否有空位。完整流程：

function handleRequest(bucket, request):
    leak(bucket)           // 先漏水（清理队列头部）
    return enqueue(bucket, request)  // 再尝试入队

执行追踪

参数：rate = 10 请求/秒，capacity = 20，初始队列为空，lastLeakTime = T0

场景 A：突发 100 个请求同时到来（T0 时刻）

T0+0s: 100 个请求同时调用 handleRequest

第 1 次 leak():
  elapsed = 0s, canLeak = 0  → 无请求被处理（队列本就为空）

enqueue 循环（100 次）：
  请求 1  ~ 请求 20：queue.size() 0→20，全部入队   ✓  QUEUED
  请求 21 ~ 请求 100：queue.size() = 20 = capacity → DROPPED  ✗（80 个被丢弃）

最终状态：queue = [req1..req20], size = 20

场景 B：T0+0.5s 到来 5 个新请求

T0+0.5s: leak() 被调用
  elapsed = 0.5s, canLeak = int(0.5 * 10) = 5
  取出 req1..req5，process 5 个请求
  queue = [req6..req20], size = 15
  lastLeakTime = T0+0.5s

enqueue 5 个新请求：
  queue.size() = 15 < 20 → 5 个请求全部入队   ✓
  queue = [req6..req20, new1..new5], size = 20

场景 C：T0+2s，队列已空后来了 3 个请求

T0+2s: leak() 被调用
  elapsed = 1.5s（T0+0.5s → T0+2s），canLeak = int(1.5 * 10) = 15
  队列中只有 15 个（req6..new5），全部处理完
  queue = [], size = 0
  lastLeakTime = T0+2s

enqueue 3 个新请求：
  queue.size() = 0 < 20 → 全部入队   ✓
  → 这 3 个请求在下次 leak() 时立即被处理，无额外等待

关键观察

时间轴（每 0.1s 一格）：
T0+0s  入队 20，丢弃 80
T0+0.1s               leak→处理 1 个
T0+0.2s               leak→处理 1 个
...（匀速，每 0.1s 处理 1 个）
T0+2s  队列清空，之后到来的请求零等待

输出速率始终严格等于 rate = 10/s，不受输入突发影响——这是漏桶与令牌桶最根本的区别。

Nginx limit_req 详解

Nginx 的 ngx_http_limit_req_module 是漏桶限流的工业级实现。

基本配置

http {
    # 声明共享内存区，按客户端 IP 限流
    limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;

    server {
        location /api/ {
            limit_req zone=api burst=20 nodelay;
            limit_req_status 429;
        }
    }
}

参数精确含义

nodelay 的行为差异

不加 nodelay（纯漏桶）：

T0: 21 个请求同时到来
  请求 1：立即处理（本时间窗口配额）
  请求 2~21：排入 burst 队列，每隔 100ms 依次处理
  请求 22+：返回 503/429

加 nodelay（漏桶 + 立即处理）：

T0: 21 个请求同时到来
  请求 1~21：全部立即处理（burst 队列内不等待）
  请求 22+：返回 503/429
  → 后续 2s 内新请求被限速，等待 burst 计数恢复

nodelay 让 Nginx 漏桶在突发行为上接近令牌桶，但底层仍是漏桶计数——突发消耗完 burst 配额后，恢复速度严格等于 rate。

漏桶 vs 令牌桶在 Nginx 中的等价配置

# 漏桶（Nginx 原生）：强制匀速，burst 内排队
limit_req zone=api burst=20;

# 模拟令牌桶效果：burst 内立即处理，允许合理突发
limit_req zone=api burst=20 nodelay;

# 令牌桶（需第三方模块 lua-resty-limit-traffic）：
# local lim = require "resty.limit.req"
# lim:set_conn(20)  -- capacity
# lim:set_rate(10)  -- rate

异常与边界场景

7.1 rate 设置过低导致队列积压（背压）

下游处理能力：rate = 10/s
输入速率：持续 50/s（超出 5 倍）

队列增长速率 = 50 - 10 = 40/s
capacity = 20 → 0.5s 后队列满，所有新请求被丢弃
丢弃率 = (50 - 10) / 50 = 80%

问题：调用方大量收到 429，可能触发重试，进一步加剧压力（见场景 7.3）。

处理方式：

1. rate 应设置为下游实测稳定吞吐量，而非峰值。
2. 监控队列深度（queue.size()），接近 capacity 时触发扩容告警。
3. 结合背压传播：上游感知队列深度，主动降低发送速率（如 TCP 滑动窗口机制）。

7.2 服务重启后队列状态丢失

漏桶队列通常存储在进程内存中，服务重启后队列清空：

重启前：queue = [req1..req20]（20 个请求排队等待）
重启后：queue = []

影响：
- 排队中的 20 个请求全部丢失，调用方感知超时或连接断开
- 重启瞬间队列空，下游压力骤降（但调用方可能立即重试，造成新的冲击）

处理方式：

1. 无状态化：对于限流器变体，丢失队列是预期行为，调用方应实现幂等重试。
2. 持久化队列：对于流量整形变体，使用 Redis List 或消息队列（Kafka）存储，重启后可继续消费。
3. 优雅停机：重启前停止 enqueue，等待 queue.isEmpty() 后再关闭（drain 模式）。

7.3 漏桶与重试机制结合（重试风暴）

场景：客户端遇到 429 后立即重试（无退避）

T0:   100 请求 → 20 入队，80 被丢弃（返回 429）
T0+0s: 80 个客户端立即重试
T0+0s: leak() 处理了 0 个（elapsed=0），队列仍满
       → 80 个重试全部被丢弃，再次返回 429
T0+0s: 80 个客户端再次立即重试……（死循环）

结果：服务器 CPU 被无效请求打满，有效吞吐量反而下降

处理方式：

1. 指数退避 + 抖动：retryDelay = base * 2^attempt + random(0, base)，避免同步重试。
2. Retry-After 响应头：服务端在 429 响应中返回建议等待时间：

   HTTP/1.1 429 Too Many Requests
   Retry-After: 1
   

3. 客户端熔断：连续多次 429 后触发熔断，暂停一段时间不再发送请求。

7.4 时钟回拨（懒惰计算实现）

正常：T1=1000ms, T2=1100ms → elapsed=100ms, canLeak=1
回拨：T1=1100ms, T2=1000ms → elapsed=-100ms

若不处理：
  canLeak = int(-0.1 * 10) = int(-1) = -1
  while processed < -1: 永远不执行（正常，但 lastLeakTime 不更新）
  → 时钟追上后下次 elapsed 会翻倍，可能一次漏出过多请求

处理方式：

elapsedSec = max(0.0, elapsed / 1_000_000_000.0)

时钟回拨时 canLeak = 0，不处理也不更新 lastLeakTime，等时钟追上后自然恢复，不会出现补偿性突发。

漏桶 vs 令牌桶精确对比

生产选型指南

选漏桶（严格匀速）：

• 下游是数据库、外部 API 等对突发敏感的系统。
• 需要严格的出口带宽控制（ISP、CDN 回源）。
• 要求 FIFO 公平排队，防止请求饥饿。

选令牌桶（允许突发）：

• 下游有一定弹性（如无状态微服务、缓存层）。
• 业务有明确的突发场景（秒杀开始瞬间、推送批量发送）。
• 需要"平均限速但允许短暂超出"的用户体验。

核心判断原则：

如果下游处理一批请求的代价与处理单个请求成正比（无批处理优化），选漏桶； 如果下游能够吸收短暂突发（如连接池有余量），选令牌桶。

秒杀场景示例：

秒杀开始瞬间 10000 QPS 冲击：

漏桶（capacity=100, rate=500/s）：
  → 100 个请求入队，9900 个被丢弃，之后以 500/s 匀速处理
  → 大量用户立即看到"系统繁忙"，体验差

令牌桶（capacity=1000, rate=500/s）：
  → 前 1000 个请求立即通过（消耗积累令牌），9000 个等待或拒绝
  → 1000 个用户获得即时响应，体验好
  → 但下游需能承受瞬时 1000 并发

参考资料

1. Leaky Bucket — Wikipedia https://en.wikipedia.org/wiki/Leaky_bucket

2. Turner, J.S. (1986)："New directions in communications (or which way to the information age?)"，IEEE Communications Magazine 24(10):8–15 — 漏桶算法的原始文献。

3. RFC 2697 — A Single Rate Three Color Marker https://datatracker.ietf.org/doc/html/rfc2697 — IETF 对漏桶在流量着色中的规范定义。

4. RFC 2698 — A Two Rate Three Color Marker https://datatracker.ietf.org/doc/html/rfc2698

5. Nginx ngx_http_limit_req_module 官方文档 https://nginx.org/en/docs/http/ngx_http_limit_req_module.html

6. Linux tc qdisc tbf（Token Bucket Filter） https://man7.org/linux/man-pages/man8/tc-tbf.8.html — 内核级漏桶/令牌桶实现。

7. 《System Design Interview Vol.2》Alex Xu — Chapter 4: Rate Limiter 漏桶与令牌桶的工程对比分析。

8. OpenResty lua-resty-limit-traffic https://github.com/openresty/lua-resty-limit-traffic — Nginx Lua 实现的令牌桶，可与漏桶对比研究。