令牌桶限流 从补充速率到突发预算

SYSTEMS NOTES阅读地图

8个主要章节

1段代码示例

6组图片与图表

从一个具体请求或状态变化出发，追踪数据流与方法成立的条件。

章节速览8 节 · 展开选择

1. 01令牌桶保存哪些状态
2. 02六次到达的完整时间线
3. 03为什么预算界是容量加补充量
4. 04用整数时间避免边界漂移
5. 05代码1：不等待真实时钟的最小计量器
6. 06它与并发、队列和重试怎样组合
7. 07验证与部署边界
8. 08参考文献与适用位置

“每秒允许两次请求”没有说明能否在同一瞬间通过三次，也没有说明上一秒没用掉的额度能否保留。若这些约定不清楚，服务端、客户端和测试程序可能各自实现了不同规则。

本篇讨论单个额度键、顺序处理、按到达时间立即判定的令牌桶。时间由调用者显式传入整数毫秒，不访问网络、不等待真实时钟，也不实现分布式锁。它与有界准入和背压衔接，但限制的是累计消耗速度，而不是正在执行的任务数量。

先固定单位容量与速率是两个参数

容量用令牌表示，速率用令牌/秒表示；一条请求可消耗多个令牌，不能把请求数与费用混为一谈。

再检查行为等待估计不是预约

不足时本实现立即拒绝，返回的毫秒数只描述没有其他消耗时的最早补足时间，不保证未来一定被接纳。

令牌桶保存哪些状态

设容量C>0、补充速率r>0，桶内余额b限制在[0,C]。请求在时刻t到达，费用为c；上次处理时间为t₀。先按经过时间补充额度，再检查是否足够，足够才一次性扣除全部费用。本文起始时刻为0，初始余额为C，允许一开始就使用满桶突发额度。

公式1｜先补充，再判定和扣除

b前 = min(C, b旧 + r·(t − t₀))
若 b前 ≥ c：接纳，b后 = b前 − c
若 b前 < c：拒绝，b后 = b前

本式时间单位为秒，费用与余额单位为令牌；要求t≥t₀、0<c≤C。拒绝不扣费用，但处理时间和已补充余额仍更新。令牌桶背景见文献1。

容量不是每秒次数。C控制能够积累的突发余额，r控制持续补充速度。长时间空闲最多恢复到C，超出容量的额度丢弃；它不会无限积累成可以任意使用的“历史欠账”。

RFC 3290讨论的是Diffserv管理模型与流量计量，属于Informational文档，不是本文应用限流接口的协议规范。这里借用容量和速率的预算模型，把计量单位明确改为应用令牌，不声称模拟路由器报文调度、颜色标记或所有令牌桶变体。

六次到达的完整时间线

取C=3令牌，r=2令牌/秒。相同时间戳按表中行序处理；不是给它们各复制一份独立的桶。第一行结束只剩1令牌，所以第二行即使也发生在0ms，费用2也无法通过。

到达ms	费用	判定前余额	结果	判定后余额	无其他消耗时还需等待ms
0	2	3	接纳	1	0
0	2	1	拒绝	1	500
250	1	1.5	接纳	0.5	0
500	2	1	拒绝	1	500
1000	2	2	接纳	0	0
5000	3	3	接纳	0	0

从1000到5000ms，理论补充8令牌，但桶只能容纳3，另外5不保留。表中的小数余额不要求代码使用浮点数：下面以一千分之一个令牌为整数单位保存，0.5令牌就是500毫令牌。

图1｜原创离散到达示意，横向卡片不是等比例时间轴；完整六行见表。查看原图

重点｜拒绝既不扣费，也不让时间倒退

如果拒绝后保留旧时间，却又保存已经补充过的余额，下次会重复计算同一段补充时间。必须把余额和时间视为一对状态进行更新。

自检1：第二行返回等待500ms，是否保证500ms时费用2一定通过？

不保证。第三行在250ms消耗1令牌，所以500ms时只剩1令牌，费用2仍被拒绝。等待值没有预约额度，也没有阻止其他调用消耗同一个桶。

为什么预算界是容量加补充量

在任一长度为Δt秒的时间区间里，开始时桶内至多有C令牌，区间内最多补充rΔt，因容量溢出被丢弃的部分只会减少可用额度。因此已接纳的总费用满足下式。若区间端点上有多个同刻请求，计数必须采用一致的事件先后约定，不能在相邻区间重复计入端点事件。

公式2｜任意时间段的消耗上界

已接纳费用总和 ≤ C + r·Δt

这是桶余额守恒给出的上界，不保证每个区间都达到上界。费用单位必须与C一致；参照RFC 3290 Appendix A的突发与持续速率讨论。

本例从0到1000ms一共接纳费用2+1+2=5，恰为3+2×1。令牌桶因此不是“任何一秒最多两令牌”的滑动窗口：容量3允许额外突发。若服务合同要求严格的滑动窗口上限，应实现相应窗口规则，而不是把令牌桶参数名称改成窗口参数。

用整数时间避免边界漂移

令q=1000b表示毫令牌，t_ms为整数毫秒，r仍以整数令牌/秒给出。经过Δms毫秒，新增毫令牌数恰为r·Δms；容量和请求费用分别乘1000。所有判定都是整数比较，不需要写一个任意的epsilon来容忍“几乎够用”。

公式3｜整数状态与等待估计

q前 = min(1000C, q旧 + r·Δms)
费用整数单位 = 1000c
不足时 wait_ms = ⌈(1000c − q前)/r⌉

r为正整数，费用为正整数；等待值向上取整。该实现只承诺整数毫秒观察点的结果，不模拟亚毫秒到达或分数令牌/秒的配置。

整数化解决的是数值表示，不解决时钟问题。部署在单进程中时，经过时间通常应来自单调时钟；跨主机不能直接比较各自的单调时钟原点。Python的monotonic语义见文献2；本文为可复验而使用调用者传入的逻辑时间。

代码1：不等待真实时钟的最小计量器

代码1｜Python 3 标准库、整数逻辑毫秒：保存为token_bucket_demo.py运行。返回(是否接纳,等待估计毫秒)。拒绝并不排队，也不代表取消已经执行的业务。此类只支持顺序调用，不是线程安全或分布式限流服务。

class TokenBucket:
    def __init__(self, capacity, rate):
        if type(capacity) is not int or type(rate) is not int:
            raise TypeError("capacity and rate must be int, excluding bool")
        if capacity <= 0 or rate <= 0:
            raise ValueError("capacity and rate must be positive")
        self.capacity = capacity
        self.rate = rate
        self.balance = capacity * 1000  # 毫令牌
        self.last_ms = 0

    def take(self, now_ms, cost=1):
        if type(now_ms) is not int or type(cost) is not int:
            raise TypeError("time and cost must be int, excluding bool")
        if now_ms < self.last_ms:
            raise ValueError("time must be nondecreasing and nonnegative")
        if cost <= 0 or cost > self.capacity:
            raise ValueError("cost must be in [1, capacity]")
        available = min(
            self.capacity * 1000,
            self.balance + (now_ms - self.last_ms) * self.rate,
        )
        needed = cost * 1000
        accepted = available >= needed
        if accepted:
            remaining, wait_ms = available - needed, 0
        else:
            remaining = available
            deficit = needed - available
            wait_ms = (deficit + self.rate - 1) // self.rate
        self.balance, self.last_ms = remaining, now_ms
        return accepted, wait_ms


if __name__ == "__main__":
    bucket = TokenBucket(capacity=3, rate=2)
    events = [(0, 2), (0, 2), (250, 1), (500, 2), (1000, 2), (5000, 3)]
    for now, cost in events:
        ok, wait = bucket.take(now, cost)
        print(now, cost, ok, bucket.balance, wait)

六行预期输出依次为0 2 True 1000 0、0 2 False 1000 500、250 1 True 500 0、500 2 False 1000 500、1000 2 True 0 0、5000 3 True 0 0。余额列单位是毫令牌，不能把1000误读成一千个完整令牌。

校验发生在提交状态之前；非法参数不推进时间。费用大于容量时永远不能以一次完整请求通过，本文直接拒绝这种配置为ValueError，而不是返回一个虚假的有限等待时间。Python整数支持大数，但运算成本会随位数增加；通常固定宽度范围下每次调用O(1)次算术操作、状态O(1)，并不保证任意大整数的位复杂度为常数。

自检2：余额恰好等于费用，应该接纳吗？

应该。公式1使用大于等于；代码比较整数毫令牌。接纳后余额为零。把比较写成严格大于，会在边界上错误拒绝合法请求。

它与并发、队列和重试怎样组合

假设桶允许某次突发通过3个请求，而每个任务执行10秒。令牌桶不会自动阻止后续补充额度继续接纳新任务；慢任务可能不断叠加。要限制同时执行数，还需要并发上限；要限制等待内存，还需要有限队列与明确的背压策略。

控制项	管什么	单独使用时不保证什么
令牌桶	一段时间的接纳费用及突发余额	同时执行的任务数
并发上限	正在执行的任务数	长期调用速率和等待队列大小
有限队列	系统接受的等待数量	等待时间一定满足截止时间
超时与重试预算	尝试与等待的总时间	操作无副作用或不会重复执行

这个顺序只是一个设计选择，不是唯一正确架构。若先扣额度再因本地队列满而拒绝，是否退回额度必须定义；若额度代表已经消耗的外部API费用，盲目退款又可能制造超额调用。应先写出费用含义和业务边界，再决定控制器顺序。可继续读超时与安全重放，避免把限流拒绝变成没有总预算的重试风暴。

图2｜原创职责对照，不是吞吐量测试或某种部署拓扑的保证。查看原图

自检3：有了每秒两令牌，就能保证最多两个任务同时运行吗？

不能。执行时间可能远大于一秒，初始突发也可能超过两次。令牌桶只按费用和经过时间记账，需要另设并发约束，并决定等待队列与拒绝行为。

自检4：两个工作线程各自复制一个满桶，是否等价于共享一个桶？

不等价。每个副本都有独立突发余额和补充速率，总预算可能成倍增加。共享状态的检查与扣除必须原子化；仅在读取时加锁、扣除时再加另一把锁，仍可能超额接纳。

验证与部署边界

本模型适合先验证接纳语义：同刻到达、恰好够用、长时间空闲、拒绝后的补充、不同费用和非法时间都应纳入。可以用逐毫秒补充的独立参考，对照按时间差一次补充的实现，再检查任意事件区间的费用上界。

真实系统还需定义额度键的生命周期、配置变更、状态持久化、重启是否恢复满桶，以及多副本如何共享预算。若每次重启都获得C额度，频繁重启就可能绕过持续限额；若无限保存每个用户的桶状态，又可能形成内存问题。这些问题不在本文几十行计量代码的保证范围内。

参考文献与适用位置

1. Y. Bernet等. RFC 3290: An Informal Management Model for Diffserv Routers, 2002. Appendix A：Token Buckets与Leaky Buckets。Informational管理模型；用于容量、速率和流量预算背景，不是本文应用接口规范。返回公式2。
2. Python官方文档：time.monotonic。 单调时钟语义。只保证该时钟不倒退，参考点未定义；本文代码使用逻辑毫秒，没有读取真实时钟。返回公式3。
3. 本站：有界准入与排队预算；超时与安全重放。 并发与背压、重试预算。用于解释本篇之外的系统控制边界，不作为RFC原文的替代。