国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

打開APP
userphoto
未登錄

開通VIP,暢享免費(fèi)電子書等14項(xiàng)超值服

開通VIP
高并發(fā)之接口限流算法總結(jié)!
作者:Young來源:http://www.kissyu.org/2016/08/13/限流算法總結(jié)/

背景

曾經(jīng)在一個(gè)大神的博客里看到這樣一句話:在開發(fā)高并發(fā)系統(tǒng)時(shí),有三把利器用來保護(hù)系統(tǒng):緩存、降級和限流。那么何為限流呢?顧名思義,限流就是限制流量,就像你寬帶包了1個(gè)G的流量,用完了就沒了。通過限流,我們可以很好地控制系統(tǒng)的qps,從而達(dá)到保護(hù)系統(tǒng)的目的。本篇文章將會介紹一下常用的限流算法以及他們各自的特點(diǎn)。

算法介紹

計(jì)數(shù)器法

計(jì)數(shù)器法是限流算法里最簡單也是最容易實(shí)現(xiàn)的一種算法。比如我們規(guī)定,對于A接口來說,我們1分鐘的訪問次數(shù)不能超過100個(gè)。那么我們可以這么做:在一開始的時(shí)候,我們可以設(shè)置一個(gè)計(jì)數(shù)器counter,每當(dāng)一個(gè)請求過來的時(shí)候,counter就加1,如果counter的值大于100并且該請求與第一個(gè)請求的間隔時(shí)間還在1分鐘之內(nèi),那么說明請求數(shù)過多;如果該請求與第一個(gè)請求的間隔時(shí)間大于1分鐘,且counter的值還在限流范圍內(nèi),那么就重置counter,具體算法的示意圖如下:

具體的偽代碼如下:

public class CounterDemo { public long timeStamp = getNowTime(); public int reqCount = 0; public final int limit = 100; // 時(shí)間窗口內(nèi)最大請求數(shù) public final long interval = 1000; // 時(shí)間窗口ms public boolean grant() { long now = getNowTime(); if (now < timestamp="" +="" interval)="" {="" 在時(shí)間窗口內(nèi)="" reqcount++;="" 判斷當(dāng)前時(shí)間窗口內(nèi)是否超過最大請求控制數(shù)="" return="" reqcount=""><= limit;="" }="" else="" {="" timestamp="now;" 超時(shí)后重置="" reqcount="1;" return="" true;="" }="">

這個(gè)算法雖然簡單,但是有一個(gè)十分致命的問題,那就是臨界問題,我們看下圖:

從上圖中我們可以看到,假設(shè)有一個(gè)惡意用戶,他在0:59時(shí),瞬間發(fā)送了100個(gè)請求,并且1:00又瞬間發(fā)送了100個(gè)請求,那么其實(shí)這個(gè)用戶在1秒里面,瞬間發(fā)送了200個(gè)請求。我們剛才規(guī)定的是1分鐘最多100個(gè)請求,也就是每秒鐘最多1.7個(gè)請求,用戶通過在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請求,可以瞬間超過我們的速率限制。用戶有可能通過算法的這個(gè)漏洞,瞬間壓垮我們的應(yīng)用。

聰明的朋友可能已經(jīng)看出來了,剛才的問題其實(shí)是因?yàn)槲覀兘y(tǒng)計(jì)的精度太低。那么如何很好地處理這個(gè)問題呢?或者說,如何將臨界問題的影響降低呢?我們可以看下面的滑動窗口算法。

滑動窗口

滑動窗口,又稱rolling window。為了解決這個(gè)問題,我們引入了滑動窗口算法。如果學(xué)過TCP網(wǎng)絡(luò)協(xié)議的話,那么一定對滑動窗口這個(gè)名詞不會陌生。下面這張圖,很好地解釋了滑動窗口算法:

在上圖中,整個(gè)紅色的矩形框表示一個(gè)時(shí)間窗口,在我們的例子中,一個(gè)時(shí)間窗口就是一分鐘。然后我們將時(shí)間窗口進(jìn)行劃分,比如圖中,我們就將滑動窗口劃成了6格,所以每格代表的是10秒鐘。每過10秒鐘,我們的時(shí)間窗口就會往右滑動一格。每一個(gè)格子都有自己獨(dú)立的計(jì)數(shù)器counter,比如當(dāng)一個(gè)請求在0:35秒的時(shí)候到達(dá),那么0:30~0:39對應(yīng)的counter就會加1。

那么滑動窗口怎么解決剛才的臨界問題的呢?我們可以看上圖,0:59到達(dá)的100個(gè)請求會落在灰色的格子中,而1:00到達(dá)的請求會落在橘黃色的格子中。當(dāng)時(shí)間到達(dá)1:00時(shí),我們的窗口會往右移動一格,那么此時(shí)時(shí)間窗口內(nèi)的總請求數(shù)量一共是200個(gè),超過了限定的100個(gè),所以此時(shí)能夠檢測出來觸發(fā)了限流。

我再來回顧一下剛才的計(jì)數(shù)器算法,我們可以發(fā)現(xiàn),計(jì)數(shù)器算法其實(shí)就是滑動窗口算法。只是它沒有對時(shí)間窗口做進(jìn)一步地劃分,所以只有1格。

由此可見,當(dāng)滑動窗口的格子劃分的越多,那么滑動窗口的滾動就越平滑,限流的統(tǒng)計(jì)就會越精確。

漏桶算法

漏桶算法,又稱leaky bucket。為了理解漏桶算法,我們看一下維基百科上的對于該算法的示意圖:

從圖中我們可以看到,整個(gè)算法其實(shí)十分簡單。首先,我們有一個(gè)固定容量的桶,有水流進(jìn)來,也有水流出去。對于流進(jìn)來的水來說,我們無法預(yù)計(jì)一共有多少水會流進(jìn)來,也無法預(yù)計(jì)水流的速度。但是對于流出去的水來說,這個(gè)桶可以固定水流出的速率。而且,當(dāng)桶滿了之后,多余的水將會溢出。

我們將算法中的水換成實(shí)際應(yīng)用中的請求,我們可以看到漏桶算法天生就限制了請求的速度。當(dāng)使用了漏桶算法,我們可以保證接口會以一個(gè)常速速率來處理請求。所以漏桶算法天生不會出現(xiàn)臨界問題。具體的偽代碼實(shí)現(xiàn)如下:

public class LeakyDemo { public long timeStamp = getNowTime(); public int capacity; // 桶的容量 public int rate; // 水漏出的速度 public int water; // 當(dāng)前水量(當(dāng)前累積請求數(shù)) public boolean grant() { long now = getNowTime(); water = max(0, water - (now - timeStamp) * rate); // 先執(zhí)行漏水,計(jì)算剩余水量 timeStamp = now; if ((water + 1) < capacity)="" {="" 嘗試加水,并且水還未滿="" water="" +="1;" return="" true;="" }="" else="" {="" 水滿,拒絕加水="" return="" false;="" }="">

令牌桶算法

令牌桶算法,又稱token bucket。為了理解該算法,我們再來看一下維基百科上對該算法的示意圖:

從圖中我們可以看到,令牌桶算法比漏桶算法稍顯復(fù)雜。首先,我們有一個(gè)固定容量的桶,桶里存放著令牌(token)。桶一開始是空的,token以一個(gè)固定的速率r往桶里填充,直到達(dá)到桶的容量,多余的令牌將會被丟棄。每當(dāng)一個(gè)請求過來時(shí),就會嘗試從桶里移除一個(gè)令牌,如果沒有令牌的話,請求無法通過。

具體的偽代碼實(shí)現(xiàn)如下:

public class TokenBucketDemo { public long timeStamp = getNowTime(); public int capacity; // 桶的容量 public int rate; // 令牌放入速度 public int tokens; // 當(dāng)前令牌數(shù)量 public boolean grant() { long now = getNowTime(); // 先添加令牌 tokens = min(capacity, tokens + (now - timeStamp) * rate); timeStamp = now; if (tokens < 1)="" {="" 若不到1個(gè)令牌,則拒絕="" return="" false;="" }="" else="" {="" 還有令牌,領(lǐng)取令牌="" tokens="" -="1;" return="" true;="" }="">

相關(guān)變種

若仔細(xì)研究算法,我們會發(fā)現(xiàn)我們默認(rèn)從桶里移除令牌是不需要耗費(fèi)時(shí)間的。如果給移除令牌設(shè)置一個(gè)延時(shí)時(shí)間,那么實(shí)際上又采用了漏桶算法的思路。Google的guava庫下的SmoothWarmingUp類就采用了這個(gè)思路。

臨界問題

我們再來考慮一下臨界問題的場景。在0:59秒的時(shí)候,由于桶內(nèi)積滿了100個(gè)token,所以這100個(gè)請求可以瞬間通過。但是由于token是以較低的速率填充的,所以在1:00的時(shí)候,桶內(nèi)的token數(shù)量不可能達(dá)到100個(gè),那么此時(shí)不可能再有100個(gè)請求通過。所以令牌桶算法可以很好地解決臨界問題。下圖比較了計(jì)數(shù)器(左)和令牌桶算法(右)在臨界點(diǎn)的速率變化。我們可以看到雖然令牌桶算法允許突發(fā)速率,但是下一個(gè)突發(fā)速率必須要等桶內(nèi)有足夠的token后才能發(fā)生:

總結(jié)

計(jì)數(shù)器 VS 滑動窗口

計(jì)數(shù)器算法是最簡單的算法,可以看成是滑動窗口的低精度實(shí)現(xiàn)?;瑒哟翱谟捎谛枰鎯Χ喾莸挠?jì)數(shù)器(每一個(gè)格子存一份),所以滑動窗口在實(shí)現(xiàn)上需要更多的存儲空間。也就是說,如果滑動窗口的精度越高,需要的存儲空間就越大。

漏桶算法 VS 令牌桶算法

漏桶算法和令牌桶算法最明顯的區(qū)別是令牌桶算法允許流量一定程度的突發(fā)。因?yàn)槟J(rèn)的令牌桶算法,取走token是不需要耗費(fèi)時(shí)間的,也就是說,假設(shè)桶內(nèi)有100個(gè)token時(shí),那么可以瞬間允許100個(gè)請求通過。

令牌桶算法由于實(shí)現(xiàn)簡單,且允許某些流量的突發(fā),對用戶友好,所以被業(yè)界采用地較多。當(dāng)然我們需要具體情況具體分析,只有最合適的算法,沒有最優(yōu)的算法。

本站僅提供存儲服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請點(diǎn)擊舉報(bào)
打開APP,閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
高并發(fā)的場景下,不能不說的限流算法
這可能是全網(wǎng)Spring Cloud Gateway限流最完整的方案了!
微服務(wù)接口限流的設(shè)計(jì)與思考(附GitHub框架源碼)
分布式服務(wù)限流實(shí)戰(zhàn),已經(jīng)為你排好坑了
一文搞懂高頻面試題之限流算法,從算法原理到實(shí)現(xiàn),再到對比分析
設(shè)計(jì)抗住千萬級流量的架構(gòu)思路
更多類似文章 >>
生活服務(wù)
分享 收藏 導(dǎo)長圖 關(guān)注 下載文章
綁定賬號成功
后續(xù)可登錄賬號暢享VIP特權(quán)!
如果VIP功能使用有故障,
可點(diǎn)擊這里聯(lián)系客服!

聯(lián)系客服