罗罗编程学习记录
本页内容 展开查看

09.2.1.2 令牌桶与漏桶

所属:全栈开发面试题库 / 09 高阶架构:高并发与分布式 / 09.2 流量治理 / 09.2.1 限流算法与实现

09.2.1.2-001 令牌桶的基本原理是什么?

一句话结论

令牌桶以固定速率往桶里放令牌,桶有容量上限;每个请求取一个令牌,有令牌才放行,没有则拒绝或排队;桶内积存的令牌允许短时间突发,突发上限等于桶容量。

概念解释

  • 生成速率 r:每秒补充令牌数,代表长期平均速率。
  • 桶容量 b:最多积存令牌数,限制瞬时突发。
  • 令牌不足:拒绝、排队或降级。

原理流程

每隔 1/r 秒生成一个令牌入桶(上限 b)
请求到达 → 取 1 个令牌
  有令牌 → 放行
  无令牌 → 拒绝/排队

常见误区

  • 误区:令牌桶只能匀速放行。桶内积存令牌时可以一次性放行一批,突发能力由桶容量决定。
  • 误区:令牌生成要靠定时任务。常用惰性计算:按距上次补充的时间差折算令牌数,无需后台线程。

追问

  • 问:长期空闲后桶是满的吗?答:是,令牌积存到容量上限;随后突发可消耗这批令牌。
  • 问:令牌桶保护的是什么速率?答:长期平均速率不超过 r,瞬时突发不超过 b 对应的量。

09.2.1.2-002 令牌桶怎么取令牌?伪代码怎么写?

一句话结论

惰性补充:先按时间差补令牌(不超过桶容量),再判断令牌数是否足够;够则扣减放行,不够则拒绝;补充与扣减必须在同一临界区/Lua 中完成,保证并发下判定一致。

概念解释

  • 惰性补充:tokens = min(capacity, tokens + rate × dt)。
  • 扣减:tokens -= 1 后放行。
  • 并发:多线程/多实例下原子更新计数与时间戳。

原理流程

now = currentTime()
dt = now - lastRefill
tokens = min(capacity, tokens + rate * dt)
lastRefill = now
if tokens >= 1:
    tokens -= 1; accept
else:
    reject

常见误区

  • 误区:补充和扣减分两步执行。并发下两个请求同时读到旧令牌数,会超额放行。
  • 误区:dt 用墙钟时间直接累加。时钟回拨会导致令牌计算异常,需用单调时间或服务端时间并做防护。

追问

  • 问:令牌数为小数怎么处理?答:可用浮点令牌计数,或按最小单位(如 0.1 个令牌)整数化;批量请求扣多个令牌。
  • 问:批量请求怎么取令牌?答:一次扣 N 个,余量不足则整批拒绝或部分放行,按业务约定。

09.2.1.2-003 令牌桶为什么允许短时突发?突发上限是多少?

一句话结论

空闲期间令牌持续积存到桶容量,突发到达时可一次性消耗积存令牌;单次突发上限约等于桶容量 b(加上速率在突发期间补充的少量令牌),超过 b 的部分只能等待令牌补充。

概念解释

  • 突发上限:桶容量决定,不是生成速率。
  • 突发之后:消耗积存令牌,随后回到速率 r 的匀速节奏。
  • 容量越大突发越强,但对下游的冲击也越大。

原理流程

空闲:令牌积累至 b
突发 N 请求:
  N ≤ b → 全部放行(消耗积存令牌)
  N > b → 仅 b 个左右放行,其余等待/拒绝

常见误区

  • 误区:桶容量可以设得很大来兼容所有突发。过大的桶等于允许长期击穿下游,突发保护失效。
  • 误区:突发只发生在空闲后。持续负载下令牌也会少量积存,突发能力受当前余量限制。

追问

  • 问:下游抗突发能力弱时桶容量怎么设?答:调小桶容量,接近匀速;必要时在出口再用漏桶队列整形。
  • 问:突发 200、长期 1000 QPS 怎么配?答:速率 r=1000/s,桶容量 b≈200(按允许的突发量定)。

09.2.1.2-004 漏桶的基本原理是什么?

一句话结论

漏桶把请求当作水倒入桶中,桶底以固定速率漏水(流出);入口可承受波动,出口速率恒定;桶满时新请求拒绝或等待,从而把突发输入整形为匀速输出。

概念解释

  • 入口:请求随时进入桶(队列缓冲)。
  • 出口:按固定速率 μ 取出请求处理。
  • 桶容量:缓冲上限,满则拒绝。

原理流程

请求到达 → 入桶(队列),桶满则拒绝
后台按速率 μ 从桶中取出请求 → 处理
输出速率恒定,与入口突发无关

常见误区

  • 误区:漏桶入口也限制速率。漏桶主要靠出口匀速整形,入口先缓冲;若入口无缓冲则退化为计数器。
  • 误区:漏桶能消除排队。突发超过出口能力时请求在桶内等待,延迟增加,桶满仍拒绝。

追问

  • 问:漏桶适合什么场景?答:下游必须匀速接收(如 DB、第三方接口),需要削峰整形的链路。
  • 问:漏桶积存的是什么?答:待处理请求队列,而不是令牌;队列长度与等待时长需要监控。

09.2.1.2-005 漏桶如何保证恒定速率流出?

一句话结论

出口由独立消费节奏控制:固定周期取固定数量请求,或按时间片限速;无论入口多忙,下游看到的处理速率不超过漏水速率 μ;队列只是缓冲,不改变出口节奏。

概念解释

  • 消费器:按速率 μ 从队列取任务。
  • 空桶:出口空闲等待,不主动造流量。
  • 满桶:入口拒绝,保护队列不无限增长。

原理流程

每间隔 1/μ 秒:
  if 队列非空: 取出 1 个请求处理
出口速率 = μ,不受入口突发影响

常见误区

  • 误区:只要用了队列就是漏桶。没有固定出口速率的队列只是缓冲,突发仍会原样打到下游。
  • 误区:匀速出口不会积压。入口长期超过 μ 时队列必然增长,需要入口限流配合。

追问

  • 问:出口速率 μ 依据什么定?答:下游压测得出的安全匀速能力,留余量。
  • 问:漏桶队列空时怎么处理?答:消费者等待新任务,避免空转占 CPU。

09.2.1.2-006 漏桶 + 队列是什么形态?队列满了怎么办?

一句话结论

漏桶 + 有界队列:入口请求进入内存队列或 MQ,消费者按匀速取出;队列长度设上限,满后按策略拒绝、降级或转其他缓冲;队列积压必须可观测并设置过期丢弃。

概念解释

  • 队列形态:内存队列(短等待)或 MQ(跨进程削峰)。
  • 有界:长度上限对应可接受积压时长。
  • 满策略:拒绝、降级、入死信/兜底。

原理流程

请求 → [有界队列] → 匀速消费者
队列满 → 拒绝/降级/转 MQ
积压超期 → 丢弃或补偿

常见误区

  • 误区:队列越大越能扛峰值。无界队列把突发延迟转化为内存积压,最终 OOM 或超时。
  • 误区:入队成功即业务成功。异步队列要跟踪消费结果与超时,不能把排队当完成。

追问

  • 问:队列容量怎么估?答:可接受积压时长 × 出口速率,再结合单请求内存占用。
  • 问:内存队列与 MQ 怎么选?答:短时、低等待用内存队列;跨进程、可持久化削峰用 MQ。

09.2.1.2-007 令牌桶与漏桶的核心差异是什么?

一句话结论

令牌桶允许消耗积存令牌形成受控突发,出口速率可短时高于平均速率;漏桶出口严格匀速,入口突发被队列吸收;前者偏重“平均速率 + 突发额度”,后者偏重“整形匀速输出”。

概念解释

维度 令牌桶 漏桶
突发 允许(受桶容量限) 不允许,出口匀速
缓冲 令牌积存 请求队列
输出节奏 可突发后回落 恒定速率
适用 一般接口限流 下游需匀速整形

原理流程

令牌桶:匀速生成令牌入桶 → 请求取令牌 → 无令牌排队或拒绝
漏桶:请求入桶排队 → 出口按固定速率放出

常见误区

  • 误区:两者可以随意互换。允许突发的场景用漏桶会增加不必要排队;必须匀速的场景用令牌桶会把突发打到下游。
  • 误区:令牌桶不排队。令牌不足时同样可以排队等令牌补充,策略可配置。

追问

  • 问:网关默认常用哪种?答:令牌桶,兼顾正常突发与长期速率控制。
  • 问:能组合吗?答:令牌桶控入口额度,漏桶队列控下游匀速,双层整形。

09.2.1.2-008 桶容量、生成速率、当前令牌数如何取值?

一句话结论

生成速率 r 按下游长期安全能力定;桶容量 b 按允许的瞬时突发量与下游承受能力定;当前令牌数初始可设满(允许冷启动突发)或设 0(平稳起步),取值要结合业务对突发的容忍度。

概念解释

  • r:长期平均速率上限。
  • b:突发额度,约等于允许一次放行的最大请求数。
  • 初始令牌:满桶起步允许突发,空桶起步更保守。

原理流程

r = 下游安全 QPS(压测值)
b = 允许突发请求数 ≈ 突发 QPS × 突发持续时长
初始 tokens = 0 或 b(按策略)

常见误区

  • 误区:b 取越大越稳。b 过大会让突发直接冲击下游,等于没有突发保护。
  • 误区:r 照搬接口标称 QPS。应按下游压测安全能力与整体链路预算设定。

追问

  • 问:1000 QPS、允许 200 突发怎么配?答:r=1000/s,b=200;突发消耗后回落到 1000/s 节奏。
  • 问:容量 b 与队列长度关系?答:b 限制令牌突发;队列长度是漏桶缓冲,两者分别约束瞬时入口与排队量。

09.2.1.2-009 令牌生成是定时补还是惰性计算?

一句话结论

两种都可实现:定时任务周期性补令牌;惰性计算在请求到达时按时间差折算应补令牌。惰性计算无需后台线程、无请求时不消耗资源,是高频实现方式;定时补充便于批量与观察令牌存量。

概念解释

  • 惰性:以 lastRefill 时间戳折算。
  • 定时:周期任务更新令牌数。
  • 一致性:两种方式都要在并发下保护令牌计数。

原理流程

惰性:dt = now - lastRefill; tokens += rate×dt
定时:每周期 tokens = min(cap, tokens + 周期增量)

常见误区

  • 误区:惰性计算没有并发问题。多个请求同时计算 dt 与补令牌仍需加锁/原子操作。
  • 误区:定时任务精度高。周期长度决定补充粒度,过细增加调度成本。

追问

  • 问:本地内存用哪种?答:惰性计算 + 锁/原子变量简单直接;定时任务适合需要主动观察桶状态的场景。
  • 问:Redis 令牌桶怎么补?答:Lua 脚本内按时间差惰性折算,避免依赖定时任务精度。

09.2.1.2-010 漏桶的入口突发流量如何缓冲?

一句话结论

突发请求进入有界队列暂存,消费者按匀速取出;缓冲容量由队列长度决定,队列设计要区分可异步排队的请求与必须即时响应的请求,后者不应进入长队列。

概念解释

  • 缓冲对象:请求上下文、任务参数。
  • 缓冲期限:等待时间不超过业务时效。
  • 不可缓冲:强同步、强时效请求,应快速失败。

原理流程

突发 → 入队缓冲
匀速消费 → 下游平稳
队列满/超时 → 拒绝或降级

常见误区

  • 误区:所有突发都该排队。同步用户请求排队过久等于超时体验,应快速失败给兜底结果。
  • 误区:队列缓冲不占资源。队列任务占内存、连接与在途槽位,容量要计入评估。

追问

  • 问:哪些请求适合进漏桶队列?答:可异步化的写操作、消息通知、非实时任务。
  • 问:队列等待如何告知用户?答:返回受理状态 + 进度查询/通知,避免用户重复提交。

09.2.1.2-011 为什么多数网关默认用令牌桶?

一句话结论

实际流量天然带有短时突发(用户集中点击、批量重试),令牌桶既用生成速率约束长期平均负载,又用桶容量容纳合理突发;漏桶的严格排队会增加延迟,更适合特定下游整形场景。

概念解释

  • 真实流量:突发与持续混合。
  • 令牌桶:平均可控 + 突发可解释。
  • 漏桶:匀速优先,延迟代价高。

原理流程

网关诉求:不击穿长期能力,也不过度拒绝正常突发
  → 令牌桶:r 控长期,b 控突发

常见误区

  • 误区:默认算法最适合所有接口。对匀速敏感的下游接口仍应单独用漏桶/队列整形。
  • 误区:令牌桶在网关层就够了。应用层与下游仍需各自限流兜底,形成多层防护。

追问

  • 问:网关令牌桶参数按什么定?答:按集群整体下游能力分配到各网关实例,b 按正常突发峰值估算。
  • 问:网关限流失败怎么办?答:本地兜底限流或降级策略,不能因限流组件故障放开全部流量。

09.2.1.2-012 恒定速率要求高的场景选哪种?

一句话结论

下游只接受匀速请求(如数据库写入、第三方配额接口、按令牌计费的外部服务)时选漏桶 + 队列,出口严格按 μ 流出;令牌桶的突发能力在此类场景反而会造成冲击或配额违规。

概念解释

  • 匀速要求:下游连接/配额按固定速率设计。
  • 漏桶:队列吸收波动,出口不变形。
  • 风险:突发直接打到下游导致连接耗尽或被对端限流。

原理流程

下游匀速能力 μ
  → 漏桶出口 = μ
  → 入口突发由队列缓冲,满则拒绝

常见误区

  • 误区:下游慢就用令牌桶大桶冲过去。下游能力固定时,突发只会变成连接等待与超时。
  • 误区:队列越长匀速效果越好。长队列只是延后冲击,出口速率不变,延迟却持续增长。

追问

  • 问:第三方接口有每分钟配额怎么控?答:漏桶/窗口按配额控制出口,超出部分排队到下一周期或拒绝。
  • 问:匀速场景如何监控?答:队列长度、出口速率、等待 P99、满桶拒绝数。

09.2.1.2-013 桶容量设过大或过小分别有什么问题?

一句话结论

过大:突发冲击下游,限流失去保护意义,积压与超时风险上升;过小:正常突发也被拒绝,误伤率高,用户体验差;容量应按下游可承受突发与业务峰值共同校准。

概念解释

  • 过大后果:下游被瞬时打满、连接池耗尽。
  • 过小后果:合法请求被拒、重试加剧流量。
  • 校准:压测观察下游在突发下的表现。

原理流程

b 过大 → 瞬时请求 ≫ 下游能力
b 过小 → 正常峰值即拒绝

常见误区

  • 误区:桶容量等于每秒速率。两者语义不同:速率是长期均值,容量是突发额度。
  • 误区:容量一次设定不再调。业务流量形态变化后要根据拒绝率与下游水位复核。

追问

  • 问:怎么判断桶过大?答:限流放行后下游连接池/队列频繁饱和,RT 长尾升高。
  • 问:怎么判断桶过小?答:拒绝集中在正常峰值时段,下游仍有充足余量。

09.2.1.2-014 令牌桶实现中并发取令牌怎么保证原子?

一句话结论

本地用锁或原子变量保护“补充 + 判断 + 扣减”的临界区;分布式用 Lua 脚本把读取时间戳、折算令牌、判断、扣减、写回时间戳合并执行,Redis 单线程顺序执行脚本,保证不超发。

概念解释

  • 本地:synchronized/ReentrantLock 或 CAS 循环。
  • 分布式:Lua 原子脚本。
  • 风险:非原子的读-改-写会让并发请求都看到足够余量。

原理流程

临界区:
  折算令牌 → 判断余量 → 扣减 → 记录时间戳

常见误区

  • 误区:用 Redis INCR 就能实现令牌桶。INCR 只做计数,令牌补充的时间折算仍需 Lua 一并处理。
  • 误区:分布式加分布式锁保护令牌桶。锁开销大且易超时,Lua 原子脚本更直接。

追问

  • 问:Lua 脚本为什么原子?答:Redis 执行单个 Lua 脚本期间不会插入其他命令,读写一致。
  • 问:批量扣令牌失败如何回滚?答:脚本内一次性判断总量,不足返回拒绝,不部分扣减。

09.2.1.2-015 冷热 key 令牌桶在内存中如何回收?

一句话结论

长期无请求的维度桶(冷 key)应设置空闲 TTL 回收;频繁访问的热点 key 常驻内存;本地实现定期清理超时桶,分布式实现靠 Redis TTL,避免稀疏维度占满内存。

概念解释

  • 冷 key:偶发维度,访问后长期空闲。
  • 回收:删除桶状态与时间戳。
  • 热 key:保留令牌状态以维持突发判定。

原理流程

桶最后访问时间 > 空闲阈值 → 清除
热 key → 保留,继续计数

常见误区

  • 误区:限流状态全部永久缓存。海量用户/IP 维度下冷 key 累积会耗尽内存。
  • 误区:回收冷 key 不影响判定。新请求重建空桶即可,不影响长期速率语义。

追问

  • 问:本地内存怎么扫描冷 key?答:定期遍历桶的最后访问时间,超过空闲期删除;注意扫描成本。
  • 问:Redis 冷 key TTL 设多久?答:略长于窗口/空闲观察期,保证当前判定有效后回收。

09.2.1.2-016 漏桶出口速率与下游服务能力如何对齐?

一句话结论

出口速率 μ 取下游压测得出的安全匀速能力并留余量;定期根据下游水位与容量变化复核 μ,不能按应用自身能力设定;下游扩容或降级时同步调整漏桶速率。

概念解释

  • μ 依据:下游单机/集群安全 QPS、连接池与 RT 拐点。
  • 余量:留故障与波动缓冲。
  • 联动:下游故障时降低 μ 或切熔断。

原理流程

下游压测安全能力 → μ = 能力 × 余量系数
下游故障 → 调小 μ / 熔断

常见误区

  • 误区:出口速率按应用 CPU 能力定。瓶颈常在下游,应用空闲不代表下游能承受。
  • 误区:μ 一次配死。下游版本、数据量、依赖变化后要重新压测复核。

追问

  • 问:多下游依赖时出口怎么分?答:按依赖分别设漏桶与隔离队列,速率各自对齐对应下游。
  • 问:μ 略高于下游能力会怎样?答:队列持续积压,下游 RT 与错误率上升,进入恶性循环。

09.2.1.2-017 突发请求被放行后排队处理的语义是什么?

一句话结论

令牌桶放行只代表获得进入资格,不等于立即被下游处理;若下游有队列,请求仍按消费节奏排队,令牌控制入口额度,队列控制出口节奏,两层语义不能混为一谈。

概念解释

  • 令牌放行:进入系统/队列的资格。
  • 队列排队:等待下游槽位。
  • 超时:排队超过预算应释放并降级。

原理流程

令牌通过 → 进入队列
队列 → 匀速/并行消费
等待超时 → 拒绝/补偿

常见误区

  • 误区:拿到令牌就保证成功。下游仍可能排队、超时或熔断。
  • 误区:令牌桶出口也是匀速。令牌桶允许突发进入,下游队列的节奏由消费能力决定。

追问

  • 问:如何区分入口限流拒绝与下游排队超时?答:分别记录阶段指标,便于定位是入口保护还是下游能力问题。
  • 问:排队请求要占用令牌吗?答:进入时扣令牌,排队期间不重复扣;退出队列时不再归还令牌(按业务可设计归还策略)。

09.2.1.2-018 令牌桶与滑动窗口能否组合?

一句话结论

可以:滑动窗口控制周期总量配额,令牌桶控制瞬时速率与突发;两级判定都通过才放行,分别对应“一段时间内总量不超”和“瞬时节奏可控”,常见于配额 + 速率双重治理。

概念解释

  • 窗口:周期总量上限。
  • 令牌桶:瞬时速率与突发。
  • 组合:AND 判定,各自独立计数。

原理流程

check 滑动窗口总量 < 周期配额
check 令牌桶有令牌
都通过 → 放行并更新两套计数

常见误区

  • 误区:组合算法越复杂越好。两级以上限流要明确各自保护目标,否则阈值互相干扰、排查困难。
  • 误区:两套计数共享一个 key。状态独立,分别维护窗口记录与令牌桶状态。

追问

  • 问:什么业务需要组合?答:既限制长期调用配额(如租户日额度),又限制瞬时并发冲击的开放平台接口。
  • 问:组合时拒绝原因怎么记?答:记录命中窗口还是令牌桶,便于分别调阈值。

09.2.1.2-019 算法参数调优实例:1000 QPS、允许突发 200,怎么配?

一句话结论

长期速率 r=1000/s,桶容量 b=200;即正常情况下每秒放行约 1000 个请求,空闲积存后单次最多可突发约 200 个;超过部分等待令牌或拒绝,具体数值需按压测下游承受能力复核。

概念解释

  • r:长期平均上限 1000 QPS。
  • b:突发额度 200。
  • 校验:突发 200 进入后下游连接池与队列不越饱和拐点。

原理流程

rate = 1000 token/s
capacity = 200
空闲后满桶:一次性放 200,随后按 1000/s 补充

常见误区

  • 误区:b=200 意味着每秒可以放 1200。突发只在有积存令牌时成立,长期平均仍受 r=1000 约束。
  • 误区:参数直接照搬。该示例为说明口径,真实 r 与 b 必须以下游压测安全水位为准。

追问

  • 问:突发持续 1 秒以上怎么算?答:积存令牌消耗完后,出口回落到 r;队列等待时长按消费速率估算。
  • 问:下游只能承受 800 QPS 匀速怎么办?答:r 调到 800,b 按下游突发承受力缩小,必要时加漏桶队列。

09.2.1.2-020 常见限流实现(Guava RateLimiter、Sentinel)采用哪种思路?

一句话结论

Guava RateLimiter 是令牌桶思路(含平稳突发与预热两种模式);Sentinel 以滑动窗口/统计指标为基础,支持匀速排队、突发阈值等流控形态;具体参数语义以各框架官方文档为准,选型时对齐算法行为而非只看名称。

概念解释

  • RateLimiter:单机令牌桶,acquire 阻塞等待或 tryAcquire 快速判定。
  • Sentinel:统计窗口 + 流控规则(QPS、线程数、直接/关联/链路),支持匀速排队。
  • 注意:框架内部实现细节随版本演进,使用前核对版本文档。

原理流程

单机本地限速 → Guava 令牌桶
网关/应用多维度规则 → Sentinel 类统计 + 流控

常见误区

  • 误区:叫“令牌桶”的行为都一样。不同框架的突发控制、排队等待、预热实现存在差异。
  • 误区:框架限流可以替代分布式配额。单机计数不代表全局总量,跨实例需共享计数(见分布式限流页)。

追问

  • 问:预热模式解决什么?答:冷启动后端能力未就绪时逐步放快速率,避免起步突发压垮下游。
  • 问:选型看哪些点?答:单机/分布式、维度支持、排队与拒绝策略、规则动态推送与监控能力。