设计限流器：令牌桶与滑动窗口

设计限流器：令牌桶与滑动窗口

在高并发系统中，限流器是保护服务稳定性的第一道防线。它控制单位时间内的请求数量，防止资源被突发流量耗尽。本文将详细讲解两种经典限流算法——令牌桶与滑动窗口，帮助你从原理到实现彻底掌握限流器的设计。

为什么需要限流器

没有限流的系统就像没有刹车的汽车。流量突增可能由客户端bug、恶意攻击或营销活动引起。限流器的核心作用有三点：

1. 防止资源耗尽：保护数据库、缓存、下游API等有限资源。
2. 保障公平性：避免个别用户占用过多资源影响其他用户。
3. 削峰填谷：将突发流量平滑处理为匀速请求，提升系统弹性和可预测性。

一个好的限流器需要在精确度、内存占用和计算性能之间取得平衡。接下来我们深入两种实战中最常用的算法。

令牌桶算法

令牌桶是最常用的限流算法之一，它模拟一个固定容量的桶，系统以恒定速率向桶中投放令牌。请求到达时必须先从桶中取出一个令牌，取到则放行，否则拒绝。

核心要素

• 桶容量（Burst Size）：允许的最大令牌数，决定了允许的突发流量大小。
• 填充速率（Rate）：每秒向桶中添加的令牌数，即处理请求的稳定速率。
• 当前令牌数（Tokens）：桶中实时的令牌数量。

工作流程

1. 系统以每秒 rate 个令牌的固定速率向桶中添加令牌。若桶已满则丢弃多余令牌。
2. 当请求到达时，检查桶中是否有至少1个令牌。
3. 若有，则消耗1个令牌并处理请求；若没有，则拒绝请求或让其等待。
4. 重复上述过程。

令牌桶允许在短时间内消耗桶内积攒的全部令牌，即支持突发流量。突发过后，请求速率被强制回归到填充速率。

简单实现思路

一个高效的令牌桶实现不需要真正启动一个后台线程去放令牌，而是通过计算时间差动态补充令牌。伪代码如下（以Java为例）：

public class TokenBucket {
    private final long capacity;        // 桶容量
    private final double refillRate;    // 每秒填充令牌数
    private double tokens;              // 当前令牌数
    private long lastRefillTimestamp;   // 上次填充时间

    public TokenBucket(long capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity; // 初始装满，允许冷启动突发
        this.lastRefillTimestamp = System.currentTimeMillis();
    }

    public synchronized boolean tryConsume() {
        refill(); // 每次请求先补充令牌
        if (tokens >= 1) {
            tokens--;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.currentTimeMillis();
        double elapsedSeconds = (now - lastRefillTimestamp) / 1000.0;
        double tokensToAdd = elapsedSeconds * refillRate;
        tokens = Math.min(capacity, tokens + tokensToAdd);
        lastRefillTimestamp = now;
    }
}

这种惰性计算方式将时间复杂度控制在 O(1)，仅需存储少量状态，非常适合分布式场景下每个限流器实例独立工作。

适用场景

• 需要允许一定突发的API限流（如瞬时允许10个请求，后续速率为每秒5个）。
• 网关层面的全局流量整形。
• 消息消费速率控制。

滑动窗口算法

滑动窗口解决了传统固定窗口（计数器）的“边界突发”问题，能够更精确地控制请求的平均速率。

固定窗口的缺陷

固定窗口将时间划分为等长片段（如1秒），在窗口内维护计数器。当窗口结束时计数器清零。致命问题在于：如果窗口前半秒没流量，最后0.1秒来了100个请求，紧接着下一个窗口前0.1秒又来了100个请求，那么在0.2秒内系统实际承受了200个请求，远超100次/秒的限制。

滑动窗口日志

精确的做法是记录每次请求的时间戳，形成日志。当新请求到来时，删除所有早于 now - windowSize 的过期记录，然后检查剩余记录数是否小于阈值。这种方式精度极高，但内存占用和时间复杂度随请求量线性增长，不适合高并发场景。

滑动窗口计数器（近似方案）

实际应用更常用分段滑动窗口，将窗口切分为多个小格子（如1秒窗口切为10个100毫秒的格子）。每个格子维护独立计数器，窗口每前进一小格就丢弃最旧的一格数据。当前窗口的总计数为所有格子之和。

这样，边界突发流量会被平均分摊到相邻窗口的格子中，不再出现“并发翻倍”的问题。

实现思路

以1分钟窗口、切分为6个10秒格子为例：

import time
from collections import deque

class SlidingWindow:
    def __init__(self, limit, window_size_sec, bucket_count=10):
        self.limit = limit
        self.window_size = window_size_sec
        self.bucket_duration = window_size_sec / bucket_count
        self.buckets = deque([0] * bucket_count, maxlen=bucket_count)
        self.last_clear_time = time.time()
        self.current_count = 0

    def allow(self):
        self._slide()
        if self.current_count < self.limit:
            self.buckets[-1] += 1
            self.current_count += 1
            return True
        return False

    def _slide(self):
        now = time.time()
        elapsed = now - self.last_clear_time
        # 计算需要滑出多少个整格子
        steps = int(elapsed // self.bucket_duration)
        if steps > 0:
            for _ in range(min(steps, len(self.buckets))):
                removed = self.buckets.popleft()
                self.current_count -= removed
                self.buckets.append(0)
            self.last_clear_time += steps * self.bucket_duration

该实现将时间复杂度和内存占用降低为 O(bucket_count)，通过调整分段数量可以权衡精度与性能。

适用场景

• 需要严格控制均匀速率，不允许突发流量。
• 用户账户级别的限流（如“每分钟最多发送5条验证码”）。
• 对边界精度要求较高的资金操作或安全接口。

两种算法的深度对比

选择建议：如果系统需要处理带有“毛刺”的正常业务流量（例如GUI操作产生的批量请求），令牌桶更友好；如果面对的是需要严格打平峰的计费、安全场景，滑动窗口更可靠。

进阶设计考量

1. 分布式限流 单机限流在集群中会产生“35%的流量分到3台机器，每台都没超限”的假象。分布式限流需要集中式存储（如Redis）。使用Redis实现令牌桶时，可以用Lua脚本保证“读取-判断-扣减”的原子性；滑动窗口则可使用ZSET记录每个用户的时间戳，通过ZREMRANGEBYSCORE移除过期数据并计数。

2. 分层限流 大型系统通常在网络边缘（网关）做粗粒度限流（如IP、域名），服务内部做细粒度限流（用户ID、API Key）。两边算法可不同——边缘用令牌桶防DDoS，内部用滑动窗口保业务公平。

3. 动态调整 将限流参数配置化（如Nacos、Apollo），实时生效。关注被限流后的用户行为：立即返回429 Too Many Requests并携带Retry-After头部是标准做法。

4. 监控与告警 暴露限流命中次数、令牌耗尽次数等指标给Prometheus等监控系统，帮助调优容量和速率。

掌握令牌桶与滑动窗口，你就具备了设计生产级限流器的核心能力。根据业务需求选择合适的算法，并在性能和精度间找到自己的平衡点，每个初学者都能构建出稳固的流量防线。