限流器：令牌桶和漏桶怎么实现

做的事:四个限流器,同一个接口

令牌桶(核心) class TokenBucket: def __init__(self, rate, cap): self.rate, self.cap, self.tokens, self.last = rate, cap, cap, 0.0 def allow(self, t): # t 由调用者传入 → 测试时可以用假时钟 self.tokens = min(self.cap, self.tokens + (t - self.last) * self.rate) # 按流逝时间补令牌 self.last = t if self.tokens >= 1: self.tokens -= 1; return True return False

所有限流器都提供 allow(t),时间由调用者传入——这样可以用完全确定的「假时钟」重放各种请求序列(见第 105 篇)。限制统一是每秒 10 个;令牌桶与漏桶的容量是 5。

验证一:跨窗口边界的突发

  固定窗口                         放行 20/20 个 | 其中任意 0.2 秒内最多放行 20 个
  滑动窗口日志                       放行 10/20 个 | 其中任意 0.2 秒内最多放行 10 个
  令牌桶(速率10/s, 容量5)             放行  6/20 个 | 其中任意 0.2 秒内最多放行  6 个
  漏桶(泄漏10/s, 容量5)              放行  6/20 个 | 其中任意 0.2 秒内最多放行  6 个

固定窗口每秒重置计数器,所以「0.9–0.999 秒的 10 个」和「1.0–1.09 秒的 10 个」分属两个窗口,20 个全部放行:约 0.2 秒里通过了限制的两倍。滑动窗口日志(任意 1 秒内至多 10 个)只放行 10 个;令牌桶和漏桶放行 6 个(容量 5 + 途中补充的 1 个)。

验证二:瞬间涌来 50 个

  固定窗口                         放行 10/50 个
  滑动窗口日志                       放行 10/50 个
  令牌桶(速率10/s, 容量5)             放行 5/50 个
  漏桶(泄漏10/s, 容量5)              放行 5/50 个

固定窗口和滑动窗口放行 10 个(等于每秒限额),令牌桶和漏桶放行 5 个(等于桶的容量)。也就是说:窗口类算法的「突发上限」等于限额;令牌桶/漏桶的突发上限等于容量——可以独立于平均速率来调。空闲很久之后再来 30 个,令牌桶仍然只放行容量那么多(下面第四节:5 个):闲置不会无限「攒」额度,因为令牌数有上限。

验证三:持续高压下的输出是否平滑

  固定窗口                         每秒放行 [10, 10, 10, 10, 10] | 任意 0.1 秒内最多 10 个
  滑动窗口日志                       每秒放行 [10, 10, 10, 10, 10] | 任意 0.1 秒内最多 10 个
  令牌桶(速率10/s, 容量5)             每秒放行 [14, 10, 10, 10, 10] | 任意 0.1 秒内最多  5 个
  漏桶(泄漏10/s, 容量5)              每秒放行 [14, 10, 10, 10, 10] | 任意 0.1 秒内最多  5 个

100 请求/秒的压力下,四种算法的平均放行都是约每秒 10 个(令牌桶第 1 秒多放行了初始满桶的那 4 到 5 个令牌)。差别在集中程度:固定窗口在每个窗口刚开始的那一小段时间内就把 10 个额度全用光——任意 0.1 秒内最多放行 10 个;令牌桶把放行均匀地摊开,任意 0.1 秒最多 5 个。如果下游怕的是「瞬时」流量,令牌桶/漏桶比固定窗口友好得多。

验证四:每种算法记多少东西

  滑动窗口日志: 保存 100,000 个时间戳 | 固定窗口: 保存 2 个整数 (count, start) | 令牌桶 / 漏桶: 保存 2 个浮点数 (tokens 或 level, last)

滑动窗口日志最精确,但要保存窗口内每个放行请求的时间戳,限制越大内存越大(限制 10 万次时是 10 万个);固定窗口、令牌桶、漏桶都是 O(1)。精确性和内存的取舍:窗口类里想兼顾两者,可以用「滑动窗口计数」(两个相邻固定窗口按比例加权),这里没有实现。

验证五:多线程下必须加锁

  理论最多放行 ≈ rate×时长+容量 = 420
  加锁:   放行 419 个 / 尝试 7,308,428 次
  不加锁: 放行 976 个 / 尝试 9,892,649 次  (超出理论上限 556 个)
  单次 allow() 的开销约 154 ns(纯 Python 令牌桶, 不含锁)

限流器的状态(令牌数、上次时间)是「读—改—写」,多个线程同时调用会互相覆盖。8 个线程 2 秒内拼命请求:加锁的令牌桶放行 419 个,和理论上限约 420 个吻合;不加锁放行了 976 个,超出限额一倍多。(这次实验是在有 GIL 的 3.14 上做的;自由线程构建我没有测这一项。)另外,加锁的纯 Python 令牌桶单次 allow() 的开销约百纳秒量级(不含锁),不是瓶颈。多进程/多机器要限流,状态还得放到共享存储里,这里没有涉及。

分步演示:同一批请求,四种算法放行了多少