返回文章列表

用 Rust 从零实现限流器:令牌桶和漏桶差的不是一点

503 字·4 分钟阅读
Rust从零造轮子限流

"限流就是每秒超过 N 个请求就拒绝"——这句话漏掉了两个关键问题:单位是"每秒"还是"每 N 毫秒"?超出的请求是拒绝还是排队?

不同的答案对应不同的实现:固定窗口、令牌桶、漏桶。它们看起来都是"限流",但对流量的塑形能力完全不同。


先看最朴素的:固定窗口

最简单的实现是维护一个计数器:

pub struct FixedWindow {
    limit: u64,
    window: std::time::Duration,
    count: u64,
    window_start: std::time::Instant,
}
 
impl FixedWindow {
    pub fn allow(&mut self) -> bool {
        let now = std::time::Instant::now();
 
        if now.duration_since(self.window_start) >= self.window {
            // 进入新窗口,重置
            self.window_start = now;
            self.count = 0;
        }
 
        if self.count < self.limit {
            self.count += 1;
            true
        } else {
            false
        }
    }
}

简单、省内存、够快。但它有一个致命的边界问题:

限制:每 1 秒 100 次
 
第 1 秒的最后 10ms:  通过 100 次
第 2 秒的最前 10ms:  通过 100 次
────────────────────────────────
20ms 内通过了 200 次 —— 是限制值的 2 倍

这叫"窗口临界问题"。任何固定窗口实现都有它,只是幅度不同。

修复:滑动窗口

把"1 秒"切成多个小格(比如 10 个 100ms 的格子),每次统计"最近的 10 格之和":

pub struct SlidingWindow {
    /// 每格的时间跨度
    slot: std::time::Duration,
    /// 格子数量
    slots: usize,
    /// 每格当前的计数
    counters: Vec<u64>,
    /// 每格的起始时间
    slot_starts: Vec<std::time::Instant>,
    limit: u64,
}
 
impl SlidingWindow {
    fn current_slot(&self, now: std::time::Instant) -> usize {
        (now.duration_since(self.slot_starts[0]).as_nanos() / self.slot.as_nanos()) as usize
            % self.slots
    }
 
    pub fn allow(&mut self) -> bool {
        let now = std::time::Instant::now();
        let idx = self.current_slot(now);
 
        // 这一格的窗口已经过去,重置它
        if now.duration_since(self.slot_starts[idx]) >= self.slot {
            self.counters[idx] = 0;
            self.slot_starts[idx] = now;
        }
 
        let total: u64 = self.counters.iter().sum();
 
        if total < self.limit {
            self.counters[idx] += 1;
            true
        } else {
            false
        }
    }
}

格子越多,精度越高,内存开销也越大。 典型做法是用 10-100 个格子,能把临界问题压到可接受范围。

代价是:它只能"近似"滑动窗口。 真正的滑动窗口要精确到每个请求的时间戳。

令牌桶:限制平均速率,允许突发

令牌桶的模型是:

桶里最多放 burst 个令牌
每秒往里放 rate 个令牌(或者按时间连续生成)
每个请求要消耗一个令牌
桶空 → 拒绝(或等待)
桶满放的令牌会溢出

关键在于"桶"本身可以积累令牌——这就是突发的来源。如果一个服务空闲了 10 秒,桶里攒了 10 * rate 个令牌(上限 burst),接下来可以一次性放行 burst 个请求。

pub struct TokenBucket {
    /// 每秒生成多少令牌
    rate: f64,
    /// 桶的容量(也就是允许的最大突发)
    capacity: f64,
    /// 当前令牌数
    tokens: f64,
    /// 上次更新令牌的时间
    last_refill: std::time::Instant,
}
 
impl TokenBucket {
    pub fn new(rate: f64, capacity: f64) -> Self {
        Self {
            rate,
            capacity,
            tokens: capacity, // 初始满桶
            last_refill: std::time::Instant::now(),
        }
    }
 
    fn refill(&mut self, now: std::time::Instant) {
        let elapsed = now.duration_since(self.last_refill).as_secs_f64();
        // 按时间连续补充,不"每秒一次"
        self.tokens = (self.tokens + elapsed * self.rate).min(self.capacity);
        self.last_refill = now;
    }
 
    pub fn try_acquire(&mut self, n: f64) -> bool {
        let now = std::time::Instant::now();
        self.refill(now);
 
        if self.tokens >= n {
            self.tokens -= n;
            true
        } else {
            false
        }
    }
}

注意 refill 是"按经过的时间连续补充",而不是"每秒加一次"。

如果用定时器每秒加一次,会有两个问题:定时器精度导致误差累积;空闲时桶的补充不准确。

用 elapsed * rate 这个写法,桶的容量是"逻辑上的连续量",不需要任何后台任务。 这是令牌桶最优雅的地方。

令牌桶的语义是"限制平均速率,但允许不超过 capacity 的突发"。 这是它和漏桶最本质的区别。

等待而不是拒绝

令牌桶还有另一种用法:不拒绝,而是算出"还要等多久"。

    /// 返回需要等待的时间;None 表示立即可用
    pub fn time_until_available(&mut self, n: f64) -> Option<std::time::Duration> {
        let now = std::time::Instant::now();
        self.refill(now);
 
        if self.tokens >= n {
            return None;
        }
 
        let needed = n - self.tokens;
        let secs = needed / self.rate;
        Some(std::time::Duration::from_secs_f64(secs))
    }

这个接口对客户端限流特别有用:与其返回 429,不如告诉调用方"100ms 后重试"。这也是很多 SDK 的 RateLimiter.Acquire(timeout) 背后的实现。

漏桶:强制平滑输出

漏桶的模型是"桶底有个洞,水以固定速率漏出":

请求是"倒进桶里的水"
桶有容量上限,满了就溢出(拒绝)
水以固定的速率从底部漏出(被处理)
pub struct LeakyBucket {
    /// 漏出速率(每秒处理多少)
    rate: f64,
    /// 桶容量(等待队列长度)
    capacity: f64,
    /// 当前水位
    level: f64,
    last_leak: std::time::Instant,
}
 
impl LeakyBucket {
    fn leak(&mut self, now: std::time::Instant) {
        let elapsed = now.duration_since(self.last_leak).as_secs_f64();
        // 水在漏,速率固定
        self.level = (self.level - elapsed * self.rate).max(0.0);
        self.last_leak = now;
    }
 
    pub fn try_accept(&mut self) -> bool {
        let now = std::time::Instant::now();
        self.leak(now);
 
        if self.level < self.capacity {
            self.level += 1.0;
            true // 进水成功(会被"排队处理")
        } else {
            false // 桶满,溢出
        }
    }
}

注意和令牌桶的结构差异:漏桶用 level < capacity 判断,令牌桶用 tokens >= n。这两个条件看起来对称,但语义完全不同:

令牌桶 漏桶
桶里存的是 可用的"许可" 待处理的"积压"
空闲时 攒令牌,允许突发 水位降到 0,不攒
突发流量 可以一次性放行(受 capacity 限制) 超出速率的部分排队,不会加速处理
溢出条件 令牌不够 队列满

一句话概括:令牌桶允许"先欠后还"(突发),漏桶只管"匀速流出"(平滑)。

需要"允许突发"用令牌桶;需要"强制匀速"用漏桶。 这两者的选择取决于你要保护的是下游(用漏桶平滑),还是限制用户(用令牌桶允许合理突发)。

代码形态上的一个关键差异

上面两个实现是"惰性计算"的:没有任何定时器,只在请求到来时按时间差推算状态。

这个写法有几个明显好处:

  • 不需要后台线程
  • 没有定时器精度误差
  • 状态只有几个浮点数,可以直接存进 Redis

第三种情况很重要。分布式限流必须把状态放到共享存储里,而"惰性 + 少量状态"意味着可以用一个 Redis 脚本一次搞定。

分布式限流:Redis + Lua

单机限流只在"单实例"时有效。多副本部署下,每个实例各限 100 QPS,实际上限就变成了 实例数 × 100。

Redis 的令牌桶实现,核心是用 Lua 保证"读-算-写"的原子性:

-- token_bucket.lua
-- KEYS[1]: 桶的 key
-- ARGV[1]: rate(每秒令牌数)
-- ARGV[2]: capacity
-- ARGV[3]: 当前时间(秒,浮点)
-- ARGV[4]: 请求的令牌数
 
local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
 
local bucket = redis.call('HMGET', key, 'tokens', 'last')
local tokens = tonumber(bucket[1])
local last = tonumber(bucket[2])
 
if tokens == nil then
  tokens = capacity
  last = now
end
 
-- 补充令牌
local elapsed = math.max(0, now - last)
tokens = math.min(capacity, tokens + elapsed * rate)
 
local allowed = 0
if tokens >= requested then
  tokens = tokens - requested
  allowed = 1
end
 
redis.call('HMSET', key, 'tokens', tokens, 'last', now)
-- 设置过期,避免空桶永久占用内存
redis.call('EXPIRE', key, math.ceil(capacity / rate) * 2)
 
return allowed

为什么必须用 Lua?

因为"读 tokens → 算补充 → 判断 → 减 tokens → 写回"必须是一个原子操作。如果用 GET + 计算 + SET,两个并发请求会读到同一个 tokens 值,各自通过判断,然后各减一次——限流就失效了。

Redis 执行 Lua 脚本期间是单线程且不可中断的,这保证了原子性。

注意 EXPIRE 那一行。 没有它,每个不同的限流 key 都会永久占着 Redis 内存。限流场景的 key 往往很多(按用户、按 IP、按接口),内存泄漏会很快暴露。

分布式限流的两个真实问题

1. 精度 vs 性能。 每次请求都调 Redis,会增加 1ms 左右的延迟,而且 Redis 本身成为瓶颈。折中方案是**"本地预限流 + 全局兜底"**:

第一层:本地令牌桶,配额 = 总配额 / 实例数 × 1.2(略微超配)
第二层:Redis 全局桶,只在本地通过后才检查

2. 时钟依赖。 上面的实现依赖 now 由客户端传入。多实例时钟不同步会导致令牌计算错误——某台机器的时钟快 5 秒,它的桶就永远有令牌。

正确做法是用 Redis 服务端时间:

local now = redis.call('TIME')
local now_sec = tonumber(now[1]) + tonumber(now[2]) / 1000000

任何分布式限流都不该信任客户端的时间戳。

该限多少:这不是代码问题

实现完限流器,真正的难题才开始:阈值定多少?

几个实践中总结的原则:

1. 限流阈值要低于容量上限。 如果系统在 1000 QPS 时会崩,限流应该设在 700-800,而不是 1000。限流的目的是"在崩溃之前生效",不是"精确顶到极限"。

2. 分层限流。 不同维度都要限:

维度 示例 目的
全局 10000 QPS 保护整个系统
按接口 /search 500 QPS 保护昂贵的接口
按用户 10 QPS 防单用户刷
按 IP 100 QPS 防爬虫

3. 拒绝要好于排队(在保护自己的场景下)。 排队会让延迟上升,而延迟上升又会拖垮上游。快速失败 + 明确的 429 + Retry-After 头,比"让请求慢慢排"更友好。

4. 一定要留"逃生通道"。 内部调用、健康检查、管理接口不能被限流——否则限流生效时,你连排查都做不了。

结论

三种限流器,三套语义:

固定窗口最简单但有临界问题;滑动窗口用格子近似解决它;令牌桶限制平均速率并允许突发;漏桶强制匀速输出。

选哪个取决于你要什么:

"允许用户偶尔连发几个请求,但长期速率要控住"  -> 令牌桶
"不管上游多快,我这一层必须匀速处理"          -> 漏桶
"精度要求不高,实现越简单越好"                -> 固定窗口 + 格子

还有一个贯穿始终的提醒:限流器的实现只占工作的三分之一。 剩下的三分之二是"阈值该定多少"和"被限流之后调用方怎么办"——而后者往往需要配合重试、退避、降级一起设计,这也是下一篇要讲的熔断器的起点。