接口限流算法有哪些？？
點擊上方「藍字」關(guān)注我們
0x01：限流
限流顧名思義，提前對各個類型的請求設(shè)置最高的QPS閾值，若高于設(shè)置的閾值則對該請求直接返回，不再調(diào)用后續(xù)資源。限流需要結(jié)合壓力測等，了解系統(tǒng)的最高水位，也是在實際開發(fā)中應(yīng)用最多的一種穩(wěn)定性保障手段。
應(yīng)用場景：如秒殺、搶購、發(fā)帖、評論、惡意爬蟲等。
?0x02：限流算法的三種實現(xiàn)
實際應(yīng)用時，不大可能在單機執(zhí)行限流。實際限流可以考慮在 Nginx 層對請求限流，或者如果真的要自己在業(yè)務(wù)方實現(xiàn)一套限流策略的話，可以考慮基于 Redis 實現(xiàn)分布式限流策略。并且在實際應(yīng)用中，可能還會基于不同的維度進行限流，如用戶 id，請求 IP 等，實際應(yīng)用需要考慮的東西更多。
?計數(shù)器
計數(shù)器法是限流算法里最簡單也是最容易實現(xiàn)的一種算法。
假設(shè)一個接口限制一分鐘內(nèi)的訪問次數(shù)不能超過100個，維護一個計數(shù)器，每次有新的請求過來，計數(shù)器加一，這時候判斷，如果計數(shù)器的值小于限流值，并且與上一次請求的時間間隔還在一分鐘內(nèi)，允許請求通過，否則拒絕請求；如果超出了時間間隔，要將計數(shù)器清零。
計數(shù)器限流可以比較容易的應(yīng)用在分布式環(huán)境中，用一個單點的存儲來保存計數(shù)值，比如用Redis，并且設(shè)置自動過期時間，這時候就可以統(tǒng)計整個集群的流量，并且進行限流。計數(shù)器方式的缺點是不能處理臨界問題，或者說限流策略不夠平滑。
假設(shè)在限流臨界點的前后，分別發(fā)送100個請求，實際上在計數(shù)器置0前后的極短時間里，處理了200個請求，這是一個瞬時的高峰，可能會超過系統(tǒng)的限制。計數(shù)器限流允許出現(xiàn) 2*permitsPerSecond 的突發(fā)流量，可以使用滑動窗口算法去優(yōu)化。
滑動窗口計數(shù)器
滑動窗口其實就是細(xì)分之后的計數(shù)器！
這樣假設(shè)，先把一分鐘劃分成6段！也就是10s一個段，在第一段里，假如請求61次，那么直接觸發(fā)了規(guī)則，肯定就過不去了；如果只請求了1次，則是正常的。當(dāng)時間走到第二個段里，即10s~20s這段范圍里，請求數(shù)不能超過總的限定條件，且當(dāng)前段的請求數(shù)量 加上之前段的總數(shù)量也不能超過總限定數(shù)量。當(dāng)時間到了50s~60s，依然是一樣。
如果過了60s，所以請求數(shù)都是正常的；則把劃分段往右移一段。那么此時的6個分段是 10 ~ 20、20 ~ 30、30 ~ 40、40 ~ 50、50 ~ 60、60 ~ 70，然后統(tǒng)計規(guī)則還跟上面一樣。所以只有劃分的越細(xì)，請求限制越平滑。
漏桶算法
漏桶(Leaky Bucket)算法思路很簡單，水(請求)先進入到漏桶里,先觸發(fā)出水，給漏斗騰出空間，漏桶會以一定的速度出水(接口有響應(yīng)速率)，當(dāng)水流入速度過大會直接溢出(訪問頻率超過接口響應(yīng)速率)，然后就拒絕請求，可以看出漏桶算法能強行限制數(shù)據(jù)的傳輸速率.示意圖如下：
令牌桶
令牌桶算法(Token Bucket)和 Leaky Bucket 效果一樣但方向相反的算法，更加容易理解。隨著時間流逝，系統(tǒng)會按恒定1/QPS時間間隔(如果QPS=100，則間隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有個水龍頭在不斷的加水)，如果桶已經(jīng)滿了就不再加了。新請求來臨時，會各自拿走一個Token，如果沒有Token可拿了就阻塞或者拒絕服務(wù)。
令牌桶的另外一個好處是可以方便的改變速度。一旦需要提高速率,則按需提高放入桶中的令牌的速率。一般會定時(比如100毫秒)往桶中增加一定數(shù)量的令牌，有些變種算法則實時的計算應(yīng)該增加的令牌的數(shù)量。
?
0x04：?漏桶和令牌桶的比較
這兩種算法的主要區(qū)別在于漏桶算法能夠強行限制數(shù)據(jù)的傳輸速率，而令牌桶算法在能夠限制數(shù)據(jù)的平均傳輸速率外，還允許某種程度的突發(fā)傳輸。
在令牌桶算法中，只要令牌桶中存在令牌，那么就允許突發(fā)地傳輸數(shù)據(jù)直到達到用戶配置的門限，因此它適合于具有突發(fā)特性的流量。
漏桶和令牌桶算法實現(xiàn)可以一樣，但是方向是相反的，對于相同的參數(shù)得到的限流效果是一樣的。
主要區(qū)別在于令牌桶允許一定程度的突發(fā)，漏桶主要目的是平滑流入速率，考慮一個臨界場景，令牌桶內(nèi)積累了100個token，可以在一瞬間通過，但是因為下一秒產(chǎn)生token的速度是固定的，所以令牌桶允許出現(xiàn)瞬間出現(xiàn)permitsPerSecond的流量，但是不會出現(xiàn)2*permitsPerSecond的流量，漏桶的速度則始終是平滑的。
掃碼二維碼
獲取更多精彩
Java樂園
