從上一篇接過來上一篇把限流拆成三問——在哪層限、限誰、被限者看到什么——并留下一個沒答的問題每層那道窗口容量的閘門內(nèi)部到底怎么記賬本篇正面回答。場景換一條戰(zhàn)線還是大促但這次看商家開放平臺一千多個 ISV獨立軟件服務(wù)商通過 API 拉訂單、推庫存平臺給每個 AppKey 配每 10 秒 20 次的配額。這個配額背后可以是四種截然不同的實現(xiàn)固定窗口計數(shù)、滑動窗口日志、漏桶、令牌桶。它們對每 10 秒 20 次的誠實程度不一樣對突發(fā)的態(tài)度不一樣內(nèi)存和分布式代價也不一樣。四種算法我都用同一份確定性請求流跑一遍隨機種子固定、虛擬時鐘推進不依賴系統(tǒng)時間數(shù)字當場對比。四種記賬方式的核心語義固定窗口計數(shù)最省內(nèi)存一個計數(shù)器加一個窗口起點過窗清零。它的軟肋是只保證每個對齊窗口不超不保證任意時刻起的一秒滑窗不超。滑動窗口日志把每個放行請求的時間戳存進隊列來了新請求先踢掉窗口外的舊項再數(shù)長度——語義最嚴格真正的任意 10 秒不超 20代價是內(nèi)存與放行數(shù)成正比高 QPS 下隊列本身就是壓力。漏桶這里指節(jié)流器形態(tài)不管外面來多急出口恒定每隔WINDOW/LIMIT秒滴一個出去天生削峰但下游永遠吃不到突發(fā)。令牌桶以恒定速率往桶里放令牌、請求取走令牌才放行桶有容量攢夠了可以一次性放出一小段突發(fā)——它是平均速率受限、瞬時突發(fā)受容的折中也是網(wǎng)關(guān)類系統(tǒng)最常用的那個。一句話對比漏桶承諾的是形狀輸出恒定令牌桶承諾的是預(yù)算長期速率 突發(fā)上限滑動日志承諾的是嚴格語義固定窗口只承諾便宜的近似。實驗一同一份流量流過四種算法構(gòu)造 120 個請求穩(wěn)態(tài)到達間隔服從指數(shù)分布固定種子random.Random(42)均值約 0.71 秒即約 1.6 請求/秒第 40~51 個是間隔僅 0.05 秒的突發(fā)簇。四種算法都按每 10 秒 20 次配置importrandom rndrandom.Random(42)WINDOW,LIMIT10.0,20# 語義目標: 任意 10 秒內(nèi)最多放行 20 個# 請求流: 穩(wěn)態(tài)到達 第 40~51 個請求為突發(fā)簇 (虛擬時鐘, 不依賴系統(tǒng)時間)stamps,t[],0.0foriinrange(120):dt0.05if40i52elsernd.expovariate(1.4)tdt stamps.append(t)print(請求總數(shù) %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:# 漏桶(節(jié)流器): 恒定 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[(固定窗口計數(shù),FixedWindow()),(滑動窗口日志,SlidingLog()),(漏桶(節(jié)流),LeakyMeter()),(令牌桶,TokenBucket())]:oksum(1forsinstampsifalgo.allow(s))print(%-12s 放行 %3d / 拒絕 %3d%(name,ok,len(stamps)-ok))運行輸出請求總數(shù) 120, 時間跨度 75.2 秒 固定窗口計數(shù) 放行 111 / 拒絕 9 滑動窗口日志 放行 104 / 拒絕 16 漏桶(節(jié)流) 放行 62 / 拒絕 58 令牌桶 放行 120 / 拒絕 0四個數(shù)字講出四種性格。請求流平均 1.6/秒、低于 2/秒的長期限額令牌桶全部放行——穩(wěn)態(tài)吃不完回填速率突發(fā)靠存量令牌吸收這正是限平均、容突發(fā)的設(shè)計意圖。漏桶卻拒掉了近一半它不看預(yù)算看形狀0.05 秒的突發(fā)間隔全被恒定出口頂回去而且注意它只放行 62 個連穩(wěn)態(tài)都沒喂飽——因為每放行一個就把出口撥后 0.5 秒突發(fā)段擠占的檔期再也補不回來?；瑒尤罩颈裙潭ù翱诙嗑?7 個多拒的正是貼著窗口邊界混進來的那批——固定窗口的賬本在邊界處重置滑窗不會。實驗二固定窗口的兩倍漏洞與令牌桶的容量語義把兩波各 40 個的突發(fā)分別壓在對齊窗口的邊界兩側(cè)t9.x 與 t10.x限額 50/10 秒# 固定窗口的邊界疊加: 兩波請求各 40 個, 分別落在窗口 0 和窗口 1# 限額 50 個/10 秒 - 固定窗口全放行, 任意 10 秒滑窗內(nèi)實際放過 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 秒窗口內(nèi)最大放行數(shù) %d%(n_slide,worst))print(結(jié)論: 突發(fā)貼著邊界來, 固定窗口最多可放過 2 倍限額 - %d %d%(n_fixed,LIMIT))# 令牌桶的容量語義陷阱: rate 與 capacity 是兩個獨立旋鈕# capacity20, rate2/s: 攢滿一桶后, 下游會在一瞬間被 20 個請求打臉bucket20.0rate2.0idle60.0bucketmin(20.0,bucketidle*rate)print(空轉(zhuǎn) %.0f 秒后桶內(nèi)令牌 %.0f 個 - 突發(fā)放行上限 %.0f, 相當于 %.0f 秒的穩(wěn)態(tài)配額%(idle,bucket,bucket,bucket/rate))運行輸出固定窗口: 放行 80 個 (窗口0 記 40, 窗口1 記 40) 滑動日志: 放行 50 個, 期間任意 10 秒窗口內(nèi)最大放行數(shù) 50 結(jié)論: 突發(fā)貼著邊界來, 固定窗口最多可放過 2 倍限額 - 80 50 空轉(zhuǎn) 60 秒后桶內(nèi)令牌 20 個 - 突發(fā)放行上限 20, 相當于 10 秒的穩(wěn)態(tài)配額固定窗口在邊界處放過了 80 個——限額的 1.6 倍理論上最多逼近 2 倍滑著窗看才發(fā)現(xiàn)真相滑動日志把任意 10 秒嚴格釘死在 50。下半段是令牌桶最容易踩的坑rate 和 capacity 是兩個獨立旋鈕。2 個/秒、桶容量 20意味著低峰期攢滿桶后瞬間可以砸出相當于 10 秒穩(wěn)態(tài)配額的突發(fā)給下游。如果下游連接池只有 5桶容量就該按下游能吞下的突發(fā)設(shè)而不是按配額設(shè)很多平時好好的、一到大促第一秒就打掛 DB的事故根源就是容量配置完全沒參與容量規(guī)劃。生產(chǎn)環(huán)境的三個坑**坑一分布式部署下的多桶漂移。**網(wǎng)關(guān)有 50 個實例每實例本地令牌桶 20/秒全局實際是 1000/秒。要么集中記賬Redis 單點原子操作接受一跳延遲和 Redis 本身成為依賴要么把全局配額除以實例數(shù)再留 5~10% 余量給流量不均但實例數(shù)變化時要跟著重算彈性擴縮容會把它玩壞。nginx 的limit_req在多 worker 下用共享內(nèi)存解決單機并發(fā)跨機仍是各限各的——共享內(nèi)存不等于全局精確?？佣孟到y(tǒng)時鐘做窗口和令牌回填。now - last用墻鐘計算NTP 校時或虛擬機遷移造成時間跳變時令牌可能瞬間回填一大桶或干脆倒掛。工程做法是用單調(diào)時鐘源做差值或?qū)未位靥钤隽吭O(shè)上限min(capacity, last Δt·rate)里的 capacity 截斷就是保命符。窗口算法里跨窗口清零同理要防陳舊窗口被遲到請求復(fù)活。**坑三突發(fā)請求被拒的語義誤傷。**批量對賬型 ISV 合法地每天兩次突發(fā)拉單按滑動日志它必被拒對這類調(diào)用方要么發(fā)令牌代金券預(yù)留突發(fā)配額要么單獨配桶容量更大的桶。限流算法沒有對錯只有和調(diào)用方行為模式匹不匹配。選型速查與清單要求任意時刻起算的窗口內(nèi)不超對下游保護極強滑動日志接受內(nèi)存成本或用滑動計數(shù)近似按上一窗口計數(shù)×重疊比例折算Redis 里兩個鍵就能實現(xiàn)想容忍合理突發(fā)、控制平均速率對外 API 配額令牌桶容量按下游突發(fā)承受力設(shè)要求輸出絕對平滑打日志、寫庫等忌抖動場景漏桶節(jié)流粗粒度保護、維度極多每 IP 每分鐘固定窗口心里記住最多 2 倍漏洞所有選型最后都要回答集中記賬還是本地近似能接受多少偏差四種算法解決的是單資源、單窗口的記賬。但報名接口被打掛往往不是單個接口的事——下游的庫存服務(wù)、風控服務(wù)一旦失敗上游就算放行得再精確也是在制造超時。下一篇《高并發(fā)流量治理實戰(zhàn)3熔斷器原理實戰(zhàn)失敗率度量、半開恢復(fù)與參數(shù)調(diào)優(yōu)》把治理對象從流量切到依賴。參考來源Wikipedia: Token bucket: https://en.wikipedia.org/wiki/Token_bucketWikipedia: Leaky bucket: https://en.wikipedia.org/wiki/Leaky_bucketCloudflare: Rate limiting 規(guī)則文檔固定/滑動窗口實踐: https://developers.cloudflare.com/waf/rate-limiting-rules/nginx 官方文檔: ngx_http_limit_req_module漏桶 溢出突發(fā): https://nginx.org/en/docs/http/ngx_http_limit_req_module.htmlEnvoy 文檔: Local rate limiting令牌桶實現(xiàn): https://www.envoyproxy.io/docs/envoy/latest/configuration/http/http_filters/local_rate_limit_filtertags: 限流, 令牌桶, 漏桶, 高并發(fā)本系列已結(jié)集為免費專欄《高并發(fā)流量治理實戰(zhàn)從限流到全鏈路壓測》 https://blog.csdn.net/weixin_67153745/category_13213830.html 系統(tǒng)性進階推薦付費專欄《提示詞工程實戰(zhàn)從入門到生產(chǎn)級 Prompt 設(shè)計》限時 ￥19.9首篇免費試讀https://blog.csdn.net/weixin_67153745/category_13213600.html