漏桶算法
漏桶算法(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個的請求都會被拒絕,但由于漏桶算法流出速率是一定的隔心,所以請求可能會被緩沖在桶中白群,不能馬上得到處理,從而徒增了等待時間济炎,而對于令牌桶算法川抡,沒有這種等待時間,有令牌則通過,無令牌則拋棄崖堤。