4. 限流算法（中）：漏桶算法与令牌桶算法

在模型 Serving 层，限流算法的选择直接决定了流量整形效果与资源利用率。本节深入剖析两种最经典的限流算法——漏桶算法（Leaky Bucket）与令牌桶算法（Token Bucket），从原理、实现到适用场景进行完整对比。

4.1 漏桶算法（Leaky Bucket）

4.1.1 核心原理

漏桶算法将请求视为水滴，系统是一个底部有固定速率漏水孔的桶。无论上游请求多么突发，桶以恒定速率向下游处理单元漏水；当桶满时，新请求被丢弃或排队等待。

• 恒定输出速率：无论输入流量如何波动，输出始终为固定速率。
• 突发吸收能力：桶容量允许短时突发被缓存，但不会加速处理。
• 强制整形：适用于需要严格平滑流量的场景，如数据库写入、下游慢服务保护。

4.1.2 实现方式

漏桶的常见实现有两种：队列式（FIFO 队列 + 定时消费）和计数器式（记录上次漏水时间 + 当前水量）。以下为计数器式伪代码：

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity          # 桶容量（最大水量）
        self.leak_rate = leak_rate        # 漏水速率（水滴/秒）
        self.water = 0                    # 当前水量
        self.last_leak_time = time.now()  # 上次漏水时间

    def allow_request(self, drop=1):
        now = time.now()
        # 计算从上次漏水到现在漏掉的水量
        elapsed = now - self.last_leak_time
        leaked = elapsed * self.leak_rate
        self.water = max(0, self.water - leaked)
        self.last_leak_time = now

        # 尝试加入水滴
        if self.water + drop <= self.capacity:
            self.water += drop
            return True   # 允许请求
        else:
            return False  # 桶满，拒绝请求

4.1.3 适用场景与局限

4.2 令牌桶算法（Token Bucket）

4.2.1 核心原理

令牌桶算法以固定速率向桶中放入令牌，每个请求必须获取一个或多个令牌才能被处理。桶有最大容量，允许积累令牌以应对突发流量。与漏桶不同，令牌桶允许在桶满时以峰值速率消费令牌，从而支持突发。

• 允许突发：桶中积累的令牌可被一次性消耗，支持短时高吞吐。
• 长期限速：令牌生成速率决定了长期平均速率。
• 灵活控制：每个请求可消耗多个令牌，实现权重限流。

4.2.2 实现方式

令牌桶的经典实现使用时间差计算，避免定时器开销：

class TokenBucket:
    def __init__(self, capacity, fill_rate):
        self.capacity = capacity          # 桶容量（最大令牌数）
        self.fill_rate = fill_rate        # 令牌生成速率（令牌/秒）
        self.tokens = capacity            # 当前令牌数（初始满桶）
        self.last_fill_time = time.now()  # 上次填充时间

    def allow_request(self, tokens=1):
        now = time.now()
        # 计算从上次填充到现在应生成的令牌数
        elapsed = now - self.last_fill_time
        new_tokens = elapsed * self.fill_rate
        self.tokens = min(self.capacity, self.tokens + new_tokens)
        self.last_fill_time = now

        # 检查是否有足够令牌
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True   # 允许请求
        else:
            return False  # 令牌不足，拒绝请求

4.2.3 适用场景与局限

4.3 漏桶 vs 令牌桶：核心对比