题干与适用场景
请实现一个按用户隔离的 Token Bucket 限流器。每个桶有最大容量 capacity、每秒补充速率 refillRate 和当前 token 数；请求携带用户 ID、时间戳和消耗量 cost。如果补充后的 token 足够，扣除成本并允许请求，否则拒绝。需要说明接口设计、复杂度、时间精度、并发安全和测试。
这道题适合后端、平台和基础设施编程面试。AWS 文档把 token bucket 描述为“token 代表请求、按速率补充、每次请求消耗 token”的限流模型，并强调容量和补充速率要通过测试验证。
面试官考察点
- 是否能写出懒惰补充公式，而不是用定时器逐桶加 token。
- 是否使用单调时间，避免墙上时钟回拨造成 token 增发。
- 是否限制 token 不超过容量，且拒绝请求时不错误扣减。
- 是否明确单机内存状态与分布式共享状态的边界。
- 是否能覆盖并发、浮点精度、超大时间间隔和无效参数。
回答前需要澄清的问题
先确认：
cost是否始终为正整数，还是支持按 token 计费的浮点成本？- 时间戳由调用方传入用于测试，还是限流器自行读取时钟？
- 只要求单进程实现，还是多个实例必须共享同一用户配额？
- 拒绝时是否需要返回预计可重试时间或剩余 token？
若没有补充，可以假设单进程、非负整数成本、纳秒级单调时钟，允许突发但不能超过桶容量。
30 秒回答框架
我会为每个用户保存 tokens 和 lastRefillAt，在请求到达时按经过的单调时间懒惰补充：min(capacity, tokens + elapsed * refillRate)。确认补充后的 token 不小于 cost 才扣减并返回允许，否则保持状态并返回拒绝。单机版本用每用户锁或原子临界区保证读改写不可分割；分布式版本把同一公式放在支持原子脚本的共享存储中。参数、时钟回拨、边界时间和并发请求都用模型测试验证。
分步骤深入解答
1. 数据结构与不变量
每个用户记录 tokens、lastRefillAt 和可选的版本号。状态必须满足 0 <= tokens <= capacity，且 lastRefillAt 不倒退。容量和补充速率在创建时校验为正值；成本必须大于零且不超过容量，否则直接返回参数错误，不改变桶状态。
2. 懒惰补充
设当前时间为 now，经过时间为 elapsed = now - lastRefillAt。补充量是 elapsed * refillRate，新 token 为 min(capacity, tokens + refill)。当桶已满时，仍把 lastRefillAt 推进到 now，避免下一次重复计算同一段时间。使用整数纳秒和有理数计算可减少浮点误差；若实现使用浮点数，要规定舍入方式并测试长期漂移。
3. 允许与拒绝
补充后若 tokens >= cost，扣除成本并返回允许；否则不扣 token，返回拒绝和可选的 retryAfter。估算重试时间可以用 (cost - tokens) / refillRate，但要向上取整，并处理速率为零或成本超过容量的情况。拒绝结果不应伪造为成功，也不应更新成一个比当前时间更早的游标。
4. 并发与状态存储
单机实现必须把读取、补充、判断和写回放在同一临界区；按用户分片锁可以减少全局锁竞争。多个进程共享配额时，应用内锁不够，需要 Redis Lua、数据库行锁或其他原子事务，把整段状态转换作为一次操作。网络重试要携带请求 ID，避免客户端在响应丢失时重复消费业务 token。
5. 过期与容量控制
长期不活跃的用户状态应按 lastRefillAt 和租约过期清理，清理不能影响新请求的正确初始化。高基数用户要有最大状态数、分片和淘汰策略；淘汰后新桶从满容量开始可能形成突发，因此生产策略要明确是否允许这种行为。不要用无限 map 让攻击者通过伪造用户 ID 耗尽内存。
6. 测试与可观测性
测试至少覆盖初始满桶、连续拒绝、恰好补足、成本等于容量、时间不前进、时间回拨、超长空闲、并发争用和重复请求。用可控时钟跑性质测试，持续验证 token 不越界、成功扣减总量不超过补充总量加初始容量。指标包括允许率、拒绝率、当前 token 分布、状态数、锁等待、原子脚本错误和内存占用。
高质量示范回答
我会把核心操作定义成 allow(userId, now, cost)。用户状态只有 tokens 和 lastRefillAt，每次请求在同一临界区计算经过时间、补充 token、截断到容量，再判断是否足够。成功时扣除成本并把游标推进到 now；失败时保留补充后的 token，但不扣除成本。整个过程中使用单调时间，状态不允许回退。
单机用按用户分片锁；分布式场景把相同转换放到 Redis Lua 或数据库原子事务，不能先读后写多个网络往返。请求 ID 只解决重试幂等，不能把限流器误称为业务操作的 exactly-once。状态需要过期清理和高基数保护，避免伪造用户键消耗内存。
测试用可控时钟覆盖零时间、恰好补足、成本等于容量、超长空闲、时钟回拨和并发。用性质断言 token 始终在零到容量之间，允许请求的累计成本不超过初始容量加补充量。上线后观察拒绝率、token 分布、状态增长、锁等待和存储脚本错误；AWS 的实践也要求先测试拟定限额，再逐步提高。
常见错误
- 为每个桶启动定时器，导致用户数增长时线程和调度开销失控。
- 用墙上时间计算 elapsed，NTP 回拨后产生额外 token。
- 补充后忘记
min(capacity, ...)，让桶无限增长。 - 拒绝请求仍扣除 token，造成用户配额被虚假消耗。
- 把应用内锁当成跨实例原子性。
- 允许
cost > capacity，让请求永远等待或返回错误的重试时间。 - 用浮点数却不说明舍入与长期漂移。
- 只测顺序调用，不测同一用户的并发读改写。
追问及应对
为什么不用固定窗口计数？
固定窗口实现简单，但边界可能允许短时间双倍突发。Token Bucket 用容量表达允许的突发，用补充速率表达长期速率；如果业务不允许任何突发，再比较滑动窗口或漏桶。
如何返回 Retry-After？
根据缺口除以补充速率并向上取整；速率为零或成本超过容量时返回不可重试或配置错误，不返回无限等待的时间戳。
Redis 不可用时怎么办？
按接口风险选择 fail-closed、受限的本地预算或明确降级，并记录原因。不能让每个实例都无限放行，也不能把故障伪装成普通业务拒绝。
修改容量和速率时如何迁移？
先按旧参数补充到变更时刻，再按策略截断或换算 token，记录配置版本。降低容量时必须处理现有 token 超过新上限的情况，并保证变更原子化。
如何证明实现没有超发？
用模型状态机和随机时间序列做性质测试，断言每个时间区间的累计允许成本不超过初始 token 加该区间理论补充量；再用并发压力测试验证原子临界区。