作者:架構(gòu)小菜
鏈接:https://www.jianshu.com/p/7987bf427b5b
簡單介紹 4 種非常好理解并且容易實(shí)現(xiàn)的限流算法!
規(guī)定我們單位時間處理的請求數(shù)量。比如我們規(guī)定我們的一個接口一分鐘只能訪問10次的話。使用固定窗口計數(shù)器算法的話可以這樣實(shí)現(xiàn):給定一個變量counter來記錄處理的請求數(shù)量,當(dāng)1分鐘之內(nèi)處理一個請求之后counter 1,1分鐘之內(nèi)的如果counter=100的話,后續(xù)的請求就會被全部拒絕。等到 1分鐘結(jié)束后,將counter回歸成0,重新開始計數(shù)(ps:只要過了一個周期就講counter回歸成0)。這種限流算法無法保證限流速率,因而無法保證突然激增的流量。比如我們限制一個接口一分鐘只能訪問10次的話,前半分鐘一個請求沒有接收,后半分鐘接收了10個請求。
二、滑動窗口計數(shù)器算法
算的上是固定窗口計數(shù)器算法的升級版?;瑒哟翱谟嫈?shù)器算法相比于固定窗口
計數(shù)器算法的優(yōu)化在于:它把時間以一定比例分片。例如我們的借口限流每分鐘處理60個請求,我們可以把 1 分鐘分為60個窗口。每隔1秒移動一次,每個窗口一秒只能處理 不大于 60(請求數(shù))/60(窗口數(shù)) 的請求, 如果當(dāng)前窗口的請求計數(shù)總和超過了限制的數(shù)量的話就不再處理其他請求。很顯然:當(dāng)滑動窗口的格子劃分的越多,
滑動窗口的滾動就越平滑,限流的統(tǒng)計就會越精確。
三、漏桶算法
我們可以把發(fā)請求的動作比作成注水到桶中,我們處理請求的過程可以比喻為漏桶漏水。我們往桶中以任意速率流入水,以一定速率流出水。當(dāng)水超過桶流量則丟棄,因?yàn)橥叭萘渴遣蛔兊模WC了整體的速率。如果想要實(shí)現(xiàn)這個算法的話也很簡單,準(zhǔn)備一個隊列用來保存請求,然后我們定期從隊列中拿請求來執(zhí)行就好了。
四、令牌桶算法
令牌桶算法也比較簡單。和漏桶算法算法一樣,我們的主角還是桶(這限流算法和桶過不去?。2贿^現(xiàn)在桶里裝的是令牌了,請求在被處理之前需要拿到一個令牌,請求處理完畢之后將這個令牌丟棄(刪除)。我們根據(jù)限流大小,按照一定的速率往桶里添加令牌。