限流算法之漏桶众羡、令牌桶的區(qū)別

限流

漏桶算法

漏桶算法(Leaky Bucket)是網(wǎng)絡(luò)世界中流量整形(Traffic Shaping)或速率限制(Rate Limiting)時經(jīng)常使用的一種算法侨赡,它的主要目的是控制數(shù)據(jù)注入到網(wǎng)絡(luò)的速率,平滑網(wǎng)絡(luò)上的突發(fā)流量粱侣。漏桶算法提供了一種機(jī)制羊壹,通過它,突發(fā)流量可以被整形以便為網(wǎng)絡(luò)提供一個穩(wěn)定的流量齐婴。

漏桶可以看作是一個帶有常量服務(wù)時間的單服務(wù)器隊列油猫,如果漏桶(包緩存)溢出,那么數(shù)據(jù)包會被丟棄柠偶。 在網(wǎng)絡(luò)中眨攘,漏桶算法可以控制端口的流量輸出速率主慰,平滑網(wǎng)絡(luò)上的突發(fā)流量,實(shí)現(xiàn)流量整形鲫售,從而為網(wǎng)絡(luò)提供一個穩(wěn)定的流量共螺。

如圖所示,把請求比作是水情竹,水來了都先放進(jìn)桶里藐不,并以限定的速度出水,當(dāng)水來得過猛而出水不夠快時就會導(dǎo)致水直接溢出秦效,即拒絕服務(wù)雏蛮。



可以看出,漏桶算法可以很好的控制流量的訪問速度阱州,一旦超過該速度就拒絕服務(wù)挑秉。

令牌桶算法

令牌桶算法是網(wǎng)絡(luò)流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一種算法。典型情況下苔货,令牌桶算法用來控制發(fā)送到網(wǎng)絡(luò)上的數(shù)據(jù)的數(shù)目犀概,并允許突發(fā)數(shù)據(jù)的發(fā)送。

令牌桶算法的原理是系統(tǒng)會以一個恒定的速度往桶里放入令牌夜惭,而如果請求需要被處理姻灶,則需要先從桶里獲取一個令牌,當(dāng)桶里沒有令牌可取時诈茧,則拒絕服務(wù)产喉。從原理上看,令牌桶算法和漏桶算法是相反的敢会,一個“進(jìn)水”曾沈,一個是“漏水”。



Google的Guava包中的RateLimiter類就是令牌桶算法的解決方案鸥昏。

漏桶算法和令牌桶算法的選擇

漏桶算法與令牌桶算法在表面看起來類似塞俱,很容易將兩者混淆。但事實(shí)上互广,這兩者具有截然不同的特性敛腌,且為不同的目的而使用。

漏桶算法與令牌桶算法的區(qū)別在于惫皱,漏桶算法能夠強(qiáng)行限制數(shù)據(jù)的傳輸速率像樊,令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時還允許某種程度的突發(fā)傳輸。

需要注意的是旅敷,在某些情況下生棍,漏桶算法不能夠有效地使用網(wǎng)絡(luò)資源,因為漏桶的漏出速率是固定的媳谁,所以即使網(wǎng)絡(luò)中沒有發(fā)生擁塞涂滴,漏桶算法也不能使某一個單獨(dú)的數(shù)據(jù)流達(dá)到端口速率友酱。因此,漏桶算法對于存在突發(fā)特性的流量來說缺乏效率柔纵。而令牌桶算法則能夠滿足這些具有突發(fā)特性的流量缔杉。通常,漏桶算法與令牌桶算法結(jié)合起來為網(wǎng)絡(luò)流量提供更高效的控制搁料。

以上都是摘抄或详,下面才是重點(diǎn),自己的理解

查看原文可以戳這里
限流技術(shù)早期被應(yīng)用于控制網(wǎng)絡(luò)接口收發(fā)通信數(shù)據(jù)的速率郭计,在互聯(lián)網(wǎng)領(lǐng)域霸琴,也借鑒了這個概念,用于為服務(wù)控制請求的速率昭伸。

在某些情況下梧乘,漏桶算法不能夠有效地使用網(wǎng)絡(luò)資源,因為漏桶的漏出速率是固定的庐杨,所以即使網(wǎng)絡(luò)中沒有發(fā)生擁塞选调,漏桶算法也不能使某一個單獨(dú)的數(shù)據(jù)流達(dá)到端口速率。因此辑莫,漏桶算法對于存在突發(fā)特性的流量來說缺乏效率

這段話怎么理解呢学歧,比如說存在兩個系統(tǒng)A罩引、B各吨,公用一個網(wǎng)絡(luò),網(wǎng)絡(luò)帶寬為2M, A袁铐、B各分得1M揭蜒,此時通過漏桶算法控制兩個系統(tǒng)使用網(wǎng)絡(luò)的速率,A剔桨、B系統(tǒng)使用網(wǎng)絡(luò)的速率固定最大值為1M,無論A屉更、B系統(tǒng)接受多少流量,但流出的速率都限制在最大1M,當(dāng)網(wǎng)絡(luò)中沒有發(fā)生擁塞洒缀,也就是可能出現(xiàn)B系統(tǒng)可能空閑沒有使用網(wǎng)絡(luò)瑰谜,對應(yīng)分給B系統(tǒng)的1M帶寬是空閑的,而A系統(tǒng)這一時刻接收了5M的流量树绩,由于漏桶限流的存在萨脑,A只能使用1M帶寬,我們的帶寬有2M,此刻我們只能使用1M,也就是達(dá)不到帶寬的最大速率饺饭,另外1M帶寬是浪費(fèi)的渤早,因此不能充分利用,缺乏效率瘫俊;當(dāng)然從另一方面來講也帶來了好處鹊杖,就是隔離性悴灵,A系統(tǒng)無論收到多大的流量沖擊,對于B系統(tǒng)的無感的骂蓖,不會因為流量沖擊A,而B受到影響.

令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時還允許某種程度的突發(fā)傳輸积瞒。

這段又該怎么理解呢,比如我們的目標(biāo)現(xiàn)在是每秒鐘處理10個請求登下,使用漏桶法赡鲜,我們設(shè)置桶的大小為10,流出的速率為0.1s流出一個請求庐船,我們可以達(dá)成我們的目標(biāo)银酬;而使用令牌桶的話,我們會設(shè)置每1s向桶中放入10個令牌筐钟,請求如果是平穩(wěn)的揩瞪,每0.1s過來一個請求,來十個篓冲,同樣能達(dá)到我們的目標(biāo)李破,這里所說的某種程度的突發(fā)傳輸是指,比如在一秒內(nèi)前0.5請求是平穩(wěn)的壹将,每0.1s來一個嗤攻,但在0.6s的時候突發(fā)請求同時來個5個請求,此時令牌算法是可以承受這個突發(fā)流量的诽俯,并且讓5個請求成功立刻同時通過妇菱,完成了所謂的某種程度的突發(fā)傳輸,而漏桶算法暴区,也可以應(yīng)對這種突發(fā)流量闯团,但不同的是沒有讓5個請求同時立刻通過,而是緩沖在桶中仙粱,然后仍然以固定速率每0.1s通過一個房交。

這兩種算法,都可以實(shí)現(xiàn)流速的控制伐割,1s處理10個請求候味,多于10個的請求都會被拒絕,但由于漏桶算法流出速率是一定的隔心,所以請求可能會被緩沖在桶中白群,不能馬上得到處理,從而徒增了等待時間济炎,而對于令牌桶算法川抡,沒有這種等待時間,有令牌則通過,無令牌則拋棄崖堤。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末侍咱,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子密幔,更是在濱河造成了極大的恐慌楔脯,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,277評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件胯甩,死亡現(xiàn)場離奇詭異昧廷,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)偎箫,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,689評論 3 393
  • 文/潘曉璐 我一進(jìn)店門木柬,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人淹办,你說我怎么就攤上這事眉枕。” “怎么了怜森?”我有些...
    開封第一講書人閱讀 163,624評論 0 353
  • 文/不壞的土叔 我叫張陵速挑,是天一觀的道長。 經(jīng)常有香客問我副硅,道長姥宝,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,356評論 1 293
  • 正文 為了忘掉前任恐疲,我火速辦了婚禮腊满,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘流纹。我一直安慰自己糜烹,他們只是感情好违诗,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,402評論 6 392
  • 文/花漫 我一把揭開白布漱凝。 她就那樣靜靜地躺著,像睡著了一般诸迟。 火紅的嫁衣襯著肌膚如雪茸炒。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,292評論 1 301
  • 那天阵苇,我揣著相機(jī)與錄音壁公,去河邊找鬼。 笑死绅项,一個胖子當(dāng)著我的面吹牛紊册,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播,決...
    沈念sama閱讀 40,135評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼囊陡,長吁一口氣:“原來是場噩夢啊……” “哼芳绩!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起撞反,我...
    開封第一講書人閱讀 38,992評論 0 275
  • 序言:老撾萬榮一對情侶失蹤妥色,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后遏片,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體嘹害,經(jīng)...
    沈念sama閱讀 45,429評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,636評論 3 334
  • 正文 我和宋清朗相戀三年吮便,在試婚紗的時候發(fā)現(xiàn)自己被綠了笔呀。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,785評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡髓需,死狀恐怖凿可,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情授账,我是刑警寧澤枯跑,帶...
    沈念sama閱讀 35,492評論 5 345
  • 正文 年R本政府宣布,位于F島的核電站白热,受9級特大地震影響敛助,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜屋确,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,092評論 3 328
  • 文/蒙蒙 一纳击、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧攻臀,春花似錦焕数、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,723評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至设联,卻和暖如春善已,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背离例。 一陣腳步聲響...
    開封第一講書人閱讀 32,858評論 1 269
  • 我被黑心中介騙來泰國打工换团, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人宫蛆。 一個月前我還...
    沈念sama閱讀 47,891評論 2 370
  • 正文 我出身青樓艘包,卻偏偏與公主長得像,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子想虎,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,713評論 2 354