后端限流算法：令牌桶、漏桶与滑动窗口

什么是限流？

在高并发系统中，限流（Rate Limiting）是保护系统稳定性的第一道防线。它通过控制单位时间内的请求量，防止流量突增导致服务过载、响应变慢甚至崩溃。常见的限流算法包括固定窗口计数器、滑动窗口、漏桶和令牌桶。本教程聚焦最经典、面试和工程中出现频率最高的三种：令牌桶、漏桶与滑动窗口，从原理到实现，带你彻底掌握后端限流的核心思想。

令牌桶算法 (Token Bucket)

令牌桶是目前应用最广泛的限流算法，能够很好地应对突发流量，并实现平滑的速率控制。

核心概念

• 令牌桶：一个固定容量的容器，系统以恒定速率向桶中放入令牌。
• 令牌生成速率：每秒生成的令牌数，决定了系统允许的平均请求速率。
• 桶容量：最大可以容纳的令牌数，决定了系统可接受的突发流量大小。
• 请求处理：每个请求需要从桶中获取一个令牌才能被处理。如果桶中无令牌，请求被拒绝（或排队等待）。

工作原理

1. 系统按照固定速率（如每秒 10 个）生成令牌，放入桶中。如果桶已满，新生成的令牌将被丢弃。
2. 每当有请求到达，它需要消耗一个令牌：
   • 如果桶内有令牌，则取走一个令牌，请求被放行。
   • 如果桶内没有令牌，则请求被限流（拒绝或降级）。
3. 令牌的生成与消耗是解耦的，可以平滑流量突发。

算法示例（伪代码）

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate = rate          # 令牌生成速率（个/秒）
        self.capacity = capacity  # 桶的容量
        self.tokens = capacity    # 当前令牌数，初始满桶
        self.last_time = time.time()

    def allow_request(self):
        now = time.time()
        # 计算距离上次请求过去了多久，应生成多少令牌
        elapsed = now - self.last_time
        self.tokens += elapsed * self.rate
        # 令牌数不能超过容量
        if self.tokens > self.capacity:
            self.tokens = self.capacity
        self.last_time = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True   # 允许请求
        else:
            return False  # 拒绝请求

特性与适用场景

• 允许突发流量：当桶内令牌积累到容量上限时，可以瞬间处理 capacity 个请求，之后速率回落至 rate。
• 平滑输出：长时间来看，输出速率被限制在令牌生成速率。
• 常见实现：Guava RateLimiter（SmoothBursty模式）就是令牌桶的变体。
• 适用场景：需要应对偶然突发，同时保护后端处理能力不变的场景，如秒杀接口、API 网关。

漏桶算法 (Leaky Bucket)

漏桶算法强调绝对平滑的输出速率，像一个底部有漏孔的水桶，无论进水速率多快，出水速率始终保持恒定。

核心概念

• 漏桶：一个容量有限的水桶，底部有一个固定速率的漏水孔。
• 输入速率：请求到达的速度，可快可慢。
• 输出速率：请求被处理的恒定速率，由漏水速率决定。
• 桶容量：如果桶满，新到达的请求将被丢弃（溢出）。

工作原理

1. 将每个请求视作一滴水，请求到达时先放入桶中。
2. 桶底以固定速率（如每秒 10 个请求）漏水，即处理请求。
3. 若桶中水量未满，请求可入桶排队；若桶已满，新请求被直接丢弃。
4. 任何情况下，请求的流出速率绝对固定，无法应对突发。

算法实现思路

通常使用一个计数器记录当前桶中积压的请求数，再结合一个出队速率定时清理。

class LeakyBucket:
    def __init__(self, rate, capacity):
        self.rate = rate          # 出水速率（请求/秒）
        self.capacity = capacity  # 桶容量
        self.water = 0            # 当前水量（积压请求数）
        self.last_leak_time = time.time()

    def allow_request(self):
        now = time.time()
        # 计算应该漏掉多少水
        elapsed = now - self.last_leak_time
        leak_amount = elapsed * self.rate
        self.water = max(0, self.water - leak_amount)
        self.last_leak_time = now

        if self.water < self.capacity:
            self.water += 1
            return True
        else:
            return False

特性与适用场景

• 强制平滑：输出速率完全恒定，完全消除突发流量。
• 无突发能力：即使一段时间内无请求，也不能积累处理能力用于后续突发。
• 常用于：流量整型（Traffic Shaping）、保护下游服务有恒定处理能力的场景，如消息队列消费、网络流量控制。
• 与令牌桶对比：漏桶限制的是流出速率，令牌桶限制的是平均流入速率并允许短时突发。

滑动窗口算法 (Sliding Window)

滑动窗口解决了传统固定窗口计数器存在的边界突发问题，使限流更加平滑和精确。

固定窗口的缺陷

固定窗口（如 1 分钟窗口，最多允许 100 个请求）会在窗口交替瞬间产生临界突发：如前 59 秒无请求，最后 1 秒和后 1 秒分别涌入 100 个请求，实际在 2 秒内处理了 200 个请求，远超限制。

核心概念

• 滑动窗口：将时间线划分为多个小窗口（如将 1 分钟划分为 60 个 1 秒窗口），窗口随时间向前滑动。
• 窗口大小：统计的时间范围（例如 60 秒）。
• 小窗口（桶）：将大窗口细分为若干固定时间段，每个小窗口记录该时间段内的请求计数。
• 当前窗口计数 = 过去一个大窗口内所有小窗口计数之和。

工作原理

1. 维护一个时间轴上的环形数组或链表，每个元素记录某个时间片（如 1 秒）的请求数。
2. 每次请求到来时：
   • 根据当前时间计算时间片索引。
   • 清理掉超过大窗口范围的旧时间片计数。
   • 将该时间片计数加 1，并检查所有时间片总计数是否超过阈值。
3. 如果总计数超过阈值，拒绝请求；否则放行。

实现示例（简易伪码）

class SlidingWindow:
    def __init__(self, window_size, limit):
        self.window_size = window_size  # 窗口大小（秒）
        self.limit = limit              # 窗口内允许的最大请求数
        self.slots = {}                 # 时间戳对应的计数，或使用sorted map
        self.slot_duration = 1          # 每个槽代表1秒

    def allow_request(self):
        now = int(time.time())
        # 清理过期槽位（当前时间 - window_size 之前的记录）
        expired = now - self.window_size
        keys_to_delete = [t for t in self.slots if t <= expired]
        for k in keys_to_delete:
            del self.slots[k]

        # 统计当前窗口内总请求数
        total = sum(self.slots.values())
        if total < self.limit:
            self.slots[now] = self.slots.get(now, 0) + 1
            return True
        else:
            return False

生产环境通常使用 Redis 的 ZSET 或 INCR + EXPIRE 实现分布式滑动窗口。

特性与适用场景

• 避免临界突发：平滑了时间窗口的边界，限流更精确。
• 内存占用可控：若窗口为 1 小时，需存储 3600 个时间槽计数，可通过优化数据结构（如定时清理、合并槽位）降低内存。
• 实现复杂度：高于固定窗口，低于令牌桶的预测生成。
• 适用场景：对精确度要求高的 API 限流，如用户级别的限制、网关级精确限流。

总结对比

没有万能的算法，选择取决于业务对突发容忍度、精确度和系统性能的要求。令牌桶以其实用性和灵活性成为多数微服务网关和基础库的首选，滑动窗口则在精确控制场景中不可或缺，漏桶适合做整形器。理解这三种算法，你就握住了后端流量控制的钥匙。