从上一篇接过来上一篇把限流拆成三问——在哪层限、限谁、被限者看到什么——并留下一个没答的问题每层那道窗口容量的闸门内部到底怎么记账本篇正面回答。场景换一条战线还是大促但这次看商家开放平台一千多个 ISV独立软件服务商通过 API 拉订单、推库存平台给每个 AppKey 配每 10 秒 20 次的配额。这个配额背后可以是四种截然不同的实现固定窗口计数、滑动窗口日志、漏桶、令牌桶。它们对每 10 秒 20 次的诚实程度不一样对突发的态度不一样内存和分布式代价也不一样。四种算法我都用同一份确定性请求流跑一遍随机种子固定、虚拟时钟推进不依赖系统时间数字当场对比。四种记账方式的核心语义固定窗口计数最省内存一个计数器加一个窗口起点过窗清零。它的软肋是只保证每个对齐窗口不超不保证任意时刻起的一秒滑窗不超。滑动窗口日志把每个放行请求的时间戳存进队列来了新请求先踢掉窗口外的旧项再数长度——语义最严格真正的任意 10 秒不超 20代价是内存与放行数成正比高 QPS 下队列本身就是压力。漏桶这里指节流器形态不管外面来多急出口恒定每隔WINDOW/LIMIT秒滴一个出去天生削峰但下游永远吃不到突发。令牌桶以恒定速率往桶里放令牌、请求取走令牌才放行桶有容量攒够了可以一次性放出一小段突发——它是平均速率受限、瞬时突发受容的折中也是网关类系统最常用的那个。一句话对比漏桶承诺的是形状输出恒定令牌桶承诺的是预算长期速率 突发上限滑动日志承诺的是严格语义固定窗口只承诺便宜的近似。实验一同一份流量流过四种算法构造 120 个请求稳态到达间隔服从指数分布固定种子random.Random(42)均值约 0.71 秒即约 1.6 请求/秒第 40~51 个是间隔仅 0.05 秒的突发簇。四种算法都按每 10 秒 20 次配置importrandom rndrandom.Random(42)WINDOW,LIMIT10.0,20# 语义目标: 任意 10 秒内最多放行 20 个# 请求流: 稳态到达 第 40~51 个请求为突发簇 (虚拟时钟, 不依赖系统时间)stamps,t[],0.0foriinrange(120):dt0.05if40i52elsernd.expovariate(1.4)tdt stamps.append(t)print(请求总数 %d, 时间跨度 %.1f 秒%(len(stamps),stamps[-1]))classFixedWindow:def__init__(self):self.win,self.n-1,0defallow(self,now):wint(now//WINDOW)ifw!self.win:self.win,self.nw,0ifself.nLIMIT:self.n1returnTruereturnFalseclassSlidingLog:def__init__(self):self.hits[]defallow(self,now):self.hits[xforxinself.hitsifxnow-WINDOW]iflen(self.hits)LIMIT:self.hits.append(now)returnTruereturnFalseclassLeakyMeter:# 漏桶(节流器): 恒定 2 个/秒出厂, 间隔不足就拒def__init__(self):self.next_ok0.0self.gapWINDOW/LIMITdefallow(self,now):ifnowself.next_ok:self.next_oknowself.gapreturnTruereturnFalseclassTokenBucket:# 令牌桶: 恒定回填 2 个/秒, 桶容量 20 允许攒令牌def__init__(self):self.tokens,self.lastfloat(LIMIT),0.0self.rateLIMIT/WINDOWdefallow(self,now):self.tokensmin(LIMIT,self.tokens(now-self.last)*self.rate)self.lastnowifself.tokens1.0:self.tokens-1.0returnTruereturnFalseforname,algoin[(固定窗口计数,FixedWindow()),(滑动窗口日志,SlidingLog()),(漏桶(节流),LeakyMeter()),(令牌桶,TokenBucket())]:oksum(1forsinstampsifalgo.allow(s))print(%-12s 放行 %3d / 拒绝 %3d%(name,ok,len(stamps)-ok))运行输出请求总数 120, 时间跨度 75.2 秒 固定窗口计数 放行 111 / 拒绝 9 滑动窗口日志 放行 104 / 拒绝 16 漏桶(节流) 放行 62 / 拒绝 58 令牌桶 放行 120 / 拒绝 0四个数字讲出四种性格。请求流平均 1.6/秒、低于 2/秒的长期限额令牌桶全部放行——稳态吃不完回填速率突发靠存量令牌吸收这正是限平均、容突发的设计意图。漏桶却拒掉了近一半它不看预算看形状0.05 秒的突发间隔全被恒定出口顶回去而且注意它只放行 62 个连稳态都没喂饱——因为每放行一个就把出口拨后 0.5 秒突发段挤占的档期再也补不回来。滑动日志比固定窗口多拒 7 个多拒的正是贴着窗口边界混进来的那批——固定窗口的账本在边界处重置滑窗不会。实验二固定窗口的两倍漏洞与令牌桶的容量语义把两波各 40 个的突发分别压在对齐窗口的边界两侧t9.x 与 t10.x限额 50/10 秒# 固定窗口的边界叠加: 两波请求各 40 个, 分别落在窗口 0 和窗口 1# 限额 50 个/10 秒 - 固定窗口全放行, 任意 10 秒滑窗内实际放过 80 个WINDOW,LIMIT10,50fixed,n_fixed{},0stamps[9.0i*0.02foriinrange(40)][10.0i*0.02foriinrange(40)]fornowinstamps:wint(now//WINDOW)fixed[w]fixed.get(w,0)iffixed[w]LIMIT:fixed[w]1n_fixed1print(固定窗口: 放行 %d 个 (窗口0 记 %d, 窗口1 记 %d)%(n_fixed,fixed[0],fixed[1]))recent,n_slide[],0worst0fornowinstamps:recent[xforxinrecentifxnow-WINDOW]iflen(recent)LIMIT:recent.append(now)n_slide1worstmax(worst,len(recent))print(滑动日志: 放行 %d 个, 期间任意 10 秒窗口内最大放行数 %d%(n_slide,worst))print(结论: 突发贴着边界来, 固定窗口最多可放过 2 倍限额 - %d %d%(n_fixed,LIMIT))# 令牌桶的容量语义陷阱: rate 与 capacity 是两个独立旋钮# capacity20, rate2/s: 攒满一桶后, 下游会在一瞬间被 20 个请求打脸bucket20.0rate2.0idle60.0bucketmin(20.0,bucketidle*rate)print(空转 %.0f 秒后桶内令牌 %.0f 个 - 突发放行上限 %.0f, 相当于 %.0f 秒的稳态配额%(idle,bucket,bucket,bucket/rate))运行输出固定窗口: 放行 80 个 (窗口0 记 40, 窗口1 记 40) 滑动日志: 放行 50 个, 期间任意 10 秒窗口内最大放行数 50 结论: 突发贴着边界来, 固定窗口最多可放过 2 倍限额 - 80 50 空转 60 秒后桶内令牌 20 个 - 突发放行上限 20, 相当于 10 秒的稳态配额固定窗口在边界处放过了 80 个——限额的 1.6 倍理论上最多逼近 2 倍滑着窗看才发现真相滑动日志把任意 10 秒严格钉死在 50。下半段是令牌桶最容易踩的坑rate 和 capacity 是两个独立旋钮。2 个/秒、桶容量 20意味着低峰期攒满桶后瞬间可以砸出相当于 10 秒稳态配额的突发给下游。如果下游连接池只有 5桶容量就该按下游能吞下的突发设而不是按配额设很多平时好好的、一到大促第一秒就打挂 DB的事故根源就是容量配置完全没参与容量规划。生产环境的三个坑**坑一分布式部署下的多桶漂移。**网关有 50 个实例每实例本地令牌桶 20/秒全局实际是 1000/秒。要么集中记账Redis 单点原子操作接受一跳延迟和 Redis 本身成为依赖要么把全局配额除以实例数再留 5~10% 余量给流量不均但实例数变化时要跟着重算弹性扩缩容会把它玩坏。nginx 的limit_req在多 worker 下用共享内存解决单机并发跨机仍是各限各的——共享内存不等于全局精确。坑二用系统时钟做窗口和令牌回填。now - last用墙钟计算NTP 校时或虚拟机迁移造成时间跳变时令牌可能瞬间回填一大桶或干脆倒挂。工程做法是用单调时钟源做差值或对单次回填增量设上限min(capacity, last Δt·rate)里的 capacity 截断就是保命符。窗口算法里跨窗口清零同理要防陈旧窗口被迟到请求复活。**坑三突发请求被拒的语义误伤。**批量对账型 ISV 合法地每天两次突发拉单按滑动日志它必被拒对这类调用方要么发令牌代金券预留突发配额要么单独配桶容量更大的桶。限流算法没有对错只有和调用方行为模式匹不匹配。选型速查与清单要求任意时刻起算的窗口内不超对下游保护极强滑动日志接受内存成本或用滑动计数近似按上一窗口计数×重叠比例折算Redis 里两个键就能实现想容忍合理突发、控制平均速率对外 API 配额令牌桶容量按下游突发承受力设要求输出绝对平滑打日志、写库等忌抖动场景漏桶节流粗粒度保护、维度极多每 IP 每分钟固定窗口心里记住最多 2 倍漏洞所有选型最后都要回答集中记账还是本地近似能接受多少偏差四种算法解决的是单资源、单窗口的记账。但报名接口被打挂往往不是单个接口的事——下游的库存服务、风控服务一旦失败上游就算放行得再精确也是在制造超时。下一篇《高并发流量治理实战3熔断器原理实战失败率度量、半开恢复与参数调优》把治理对象从流量切到依赖。参考来源Wikipedia: Token bucket: https://en.wikipedia.org/wiki/Token_bucketWikipedia: Leaky bucket: https://en.wikipedia.org/wiki/Leaky_bucketCloudflare: Rate limiting 规则文档固定/滑动窗口实践: https://developers.cloudflare.com/waf/rate-limiting-rules/nginx 官方文档: ngx_http_limit_req_module漏桶 溢出突发: https://nginx.org/en/docs/http/ngx_http_limit_req_module.htmlEnvoy 文档: Local rate limiting令牌桶实现: https://www.envoyproxy.io/docs/envoy/latest/configuration/http/http_filters/local_rate_limit_filtertags: 限流, 令牌桶, 漏桶, 高并发本系列已结集为免费专栏《高并发流量治理实战从限流到全链路压测》 https://blog.csdn.net/weixin_67153745/category_13213830.html 系统性进阶推荐付费专栏《提示词工程实战从入门到生产级 Prompt 设计》限时 ¥19.9首篇免费试读https://blog.csdn.net/weixin_67153745/category_13213600.html
高并发流量治理实战（2）：令牌桶、漏桶、滑动窗口：四种限流算法的实现与坑
从上一篇接过来上一篇把限流拆成三问——在哪层限、限谁、被限者看到什么——并留下一个没答的问题每层那道窗口容量的闸门内部到底怎么记账本篇正面回答。场景换一条战线还是大促但这次看商家开放平台一千多个 ISV独立软件服务商通过 API 拉订单、推库存平台给每个 AppKey 配每 10 秒 20 次的配额。这个配额背后可以是四种截然不同的实现固定窗口计数、滑动窗口日志、漏桶、令牌桶。它们对每 10 秒 20 次的诚实程度不一样对突发的态度不一样内存和分布式代价也不一样。四种算法我都用同一份确定性请求流跑一遍随机种子固定、虚拟时钟推进不依赖系统时间数字当场对比。四种记账方式的核心语义固定窗口计数最省内存一个计数器加一个窗口起点过窗清零。它的软肋是只保证每个对齐窗口不超不保证任意时刻起的一秒滑窗不超。滑动窗口日志把每个放行请求的时间戳存进队列来了新请求先踢掉窗口外的旧项再数长度——语义最严格真正的任意 10 秒不超 20代价是内存与放行数成正比高 QPS 下队列本身就是压力。漏桶这里指节流器形态不管外面来多急出口恒定每隔WINDOW/LIMIT秒滴一个出去天生削峰但下游永远吃不到突发。令牌桶以恒定速率往桶里放令牌、请求取走令牌才放行桶有容量攒够了可以一次性放出一小段突发——它是平均速率受限、瞬时突发受容的折中也是网关类系统最常用的那个。一句话对比漏桶承诺的是形状输出恒定令牌桶承诺的是预算长期速率 突发上限滑动日志承诺的是严格语义固定窗口只承诺便宜的近似。实验一同一份流量流过四种算法构造 120 个请求稳态到达间隔服从指数分布固定种子random.Random(42)均值约 0.71 秒即约 1.6 请求/秒第 40~51 个是间隔仅 0.05 秒的突发簇。四种算法都按每 10 秒 20 次配置importrandom rndrandom.Random(42)WINDOW,LIMIT10.0,20# 语义目标: 任意 10 秒内最多放行 20 个# 请求流: 稳态到达 第 40~51 个请求为突发簇 (虚拟时钟, 不依赖系统时间)stamps,t[],0.0foriinrange(120):dt0.05if40i52elsernd.expovariate(1.4)tdt stamps.append(t)print(请求总数 %d, 时间跨度 %.1f 秒%(len(stamps),stamps[-1]))classFixedWindow:def__init__(self):self.win,self.n-1,0defallow(self,now):wint(now//WINDOW)ifw!self.win:self.win,self.nw,0ifself.nLIMIT:self.n1returnTruereturnFalseclassSlidingLog:def__init__(self):self.hits[]defallow(self,now):self.hits[xforxinself.hitsifxnow-WINDOW]iflen(self.hits)LIMIT:self.hits.append(now)returnTruereturnFalseclassLeakyMeter:# 漏桶(节流器): 恒定 2 个/秒出厂, 间隔不足就拒def__init__(self):self.next_ok0.0self.gapWINDOW/LIMITdefallow(self,now):ifnowself.next_ok:self.next_oknowself.gapreturnTruereturnFalseclassTokenBucket:# 令牌桶: 恒定回填 2 个/秒, 桶容量 20 允许攒令牌def__init__(self):self.tokens,self.lastfloat(LIMIT),0.0self.rateLIMIT/WINDOWdefallow(self,now):self.tokensmin(LIMIT,self.tokens(now-self.last)*self.rate)self.lastnowifself.tokens1.0:self.tokens-1.0returnTruereturnFalseforname,algoin[(固定窗口计数,FixedWindow()),(滑动窗口日志,SlidingLog()),(漏桶(节流),LeakyMeter()),(令牌桶,TokenBucket())]:oksum(1forsinstampsifalgo.allow(s))print(%-12s 放行 %3d / 拒绝 %3d%(name,ok,len(stamps)-ok))运行输出请求总数 120, 时间跨度 75.2 秒 固定窗口计数 放行 111 / 拒绝 9 滑动窗口日志 放行 104 / 拒绝 16 漏桶(节流) 放行 62 / 拒绝 58 令牌桶 放行 120 / 拒绝 0四个数字讲出四种性格。请求流平均 1.6/秒、低于 2/秒的长期限额令牌桶全部放行——稳态吃不完回填速率突发靠存量令牌吸收这正是限平均、容突发的设计意图。漏桶却拒掉了近一半它不看预算看形状0.05 秒的突发间隔全被恒定出口顶回去而且注意它只放行 62 个连稳态都没喂饱——因为每放行一个就把出口拨后 0.5 秒突发段挤占的档期再也补不回来。滑动日志比固定窗口多拒 7 个多拒的正是贴着窗口边界混进来的那批——固定窗口的账本在边界处重置滑窗不会。实验二固定窗口的两倍漏洞与令牌桶的容量语义把两波各 40 个的突发分别压在对齐窗口的边界两侧t9.x 与 t10.x限额 50/10 秒# 固定窗口的边界叠加: 两波请求各 40 个, 分别落在窗口 0 和窗口 1# 限额 50 个/10 秒 - 固定窗口全放行, 任意 10 秒滑窗内实际放过 80 个WINDOW,LIMIT10,50fixed,n_fixed{},0stamps[9.0i*0.02foriinrange(40)][10.0i*0.02foriinrange(40)]fornowinstamps:wint(now//WINDOW)fixed[w]fixed.get(w,0)iffixed[w]LIMIT:fixed[w]1n_fixed1print(固定窗口: 放行 %d 个 (窗口0 记 %d, 窗口1 记 %d)%(n_fixed,fixed[0],fixed[1]))recent,n_slide[],0worst0fornowinstamps:recent[xforxinrecentifxnow-WINDOW]iflen(recent)LIMIT:recent.append(now)n_slide1worstmax(worst,len(recent))print(滑动日志: 放行 %d 个, 期间任意 10 秒窗口内最大放行数 %d%(n_slide,worst))print(结论: 突发贴着边界来, 固定窗口最多可放过 2 倍限额 - %d %d%(n_fixed,LIMIT))# 令牌桶的容量语义陷阱: rate 与 capacity 是两个独立旋钮# capacity20, rate2/s: 攒满一桶后, 下游会在一瞬间被 20 个请求打脸bucket20.0rate2.0idle60.0bucketmin(20.0,bucketidle*rate)print(空转 %.0f 秒后桶内令牌 %.0f 个 - 突发放行上限 %.0f, 相当于 %.0f 秒的稳态配额%(idle,bucket,bucket,bucket/rate))运行输出固定窗口: 放行 80 个 (窗口0 记 40, 窗口1 记 40) 滑动日志: 放行 50 个, 期间任意 10 秒窗口内最大放行数 50 结论: 突发贴着边界来, 固定窗口最多可放过 2 倍限额 - 80 50 空转 60 秒后桶内令牌 20 个 - 突发放行上限 20, 相当于 10 秒的稳态配额固定窗口在边界处放过了 80 个——限额的 1.6 倍理论上最多逼近 2 倍滑着窗看才发现真相滑动日志把任意 10 秒严格钉死在 50。下半段是令牌桶最容易踩的坑rate 和 capacity 是两个独立旋钮。2 个/秒、桶容量 20意味着低峰期攒满桶后瞬间可以砸出相当于 10 秒稳态配额的突发给下游。如果下游连接池只有 5桶容量就该按下游能吞下的突发设而不是按配额设很多平时好好的、一到大促第一秒就打挂 DB的事故根源就是容量配置完全没参与容量规划。生产环境的三个坑**坑一分布式部署下的多桶漂移。**网关有 50 个实例每实例本地令牌桶 20/秒全局实际是 1000/秒。要么集中记账Redis 单点原子操作接受一跳延迟和 Redis 本身成为依赖要么把全局配额除以实例数再留 5~10% 余量给流量不均但实例数变化时要跟着重算弹性扩缩容会把它玩坏。nginx 的limit_req在多 worker 下用共享内存解决单机并发跨机仍是各限各的——共享内存不等于全局精确。坑二用系统时钟做窗口和令牌回填。now - last用墙钟计算NTP 校时或虚拟机迁移造成时间跳变时令牌可能瞬间回填一大桶或干脆倒挂。工程做法是用单调时钟源做差值或对单次回填增量设上限min(capacity, last Δt·rate)里的 capacity 截断就是保命符。窗口算法里跨窗口清零同理要防陈旧窗口被迟到请求复活。**坑三突发请求被拒的语义误伤。**批量对账型 ISV 合法地每天两次突发拉单按滑动日志它必被拒对这类调用方要么发令牌代金券预留突发配额要么单独配桶容量更大的桶。限流算法没有对错只有和调用方行为模式匹不匹配。选型速查与清单要求任意时刻起算的窗口内不超对下游保护极强滑动日志接受内存成本或用滑动计数近似按上一窗口计数×重叠比例折算Redis 里两个键就能实现想容忍合理突发、控制平均速率对外 API 配额令牌桶容量按下游突发承受力设要求输出绝对平滑打日志、写库等忌抖动场景漏桶节流粗粒度保护、维度极多每 IP 每分钟固定窗口心里记住最多 2 倍漏洞所有选型最后都要回答集中记账还是本地近似能接受多少偏差四种算法解决的是单资源、单窗口的记账。但报名接口被打挂往往不是单个接口的事——下游的库存服务、风控服务一旦失败上游就算放行得再精确也是在制造超时。下一篇《高并发流量治理实战3熔断器原理实战失败率度量、半开恢复与参数调优》把治理对象从流量切到依赖。参考来源Wikipedia: Token bucket: https://en.wikipedia.org/wiki/Token_bucketWikipedia: Leaky bucket: https://en.wikipedia.org/wiki/Leaky_bucketCloudflare: Rate limiting 规则文档固定/滑动窗口实践: https://developers.cloudflare.com/waf/rate-limiting-rules/nginx 官方文档: ngx_http_limit_req_module漏桶 溢出突发: https://nginx.org/en/docs/http/ngx_http_limit_req_module.htmlEnvoy 文档: Local rate limiting令牌桶实现: https://www.envoyproxy.io/docs/envoy/latest/configuration/http/http_filters/local_rate_limit_filtertags: 限流, 令牌桶, 漏桶, 高并发本系列已结集为免费专栏《高并发流量治理实战从限流到全链路压测》 https://blog.csdn.net/weixin_67153745/category_13213830.html 系统性进阶推荐付费专栏《提示词工程实战从入门到生产级 Prompt 设计》限时 ¥19.9首篇免费试读https://blog.csdn.net/weixin_67153745/category_13213600.html