一腥泥、常見(jiàn)的限流算法
目前常用的限流算法有兩個(gè)：漏桶算法和令牌桶算法蛔外。
1.漏桶算法
漏桶算法的原理比較簡(jiǎn)單蛆楞，請(qǐng)求進(jìn)入到漏桶中豹爹，漏桶以一定的速率漏水帅戒。當(dāng)請(qǐng)求過(guò)多時(shí)崖技，水直接溢出迎献∮趸校可以看出播演，漏桶算法可以強(qiáng)制限制數(shù)據(jù)的傳輸速度写烤。
2.令牌桶算法
令牌桶算法的原理是系統(tǒng)以一定速率向桶中放入令牌，如果有請(qǐng)求時(shí)感局，請(qǐng)求會(huì)從桶中取出令牌询微，如果能取到令牌狂巢，則可以繼續(xù)完成請(qǐng)求，否則等待或者拒絕服務(wù)藻雌。這種算法可以應(yīng)對(duì)突發(fā)程度的請(qǐng)求疹吃，因此比漏桶算法好。
在 Wikipedia 上歉摧，令牌桶算法是這么描述的：
- 每秒會(huì)有 r 個(gè)令牌放入桶中叁温，或者說(shuō)，每過(guò) 1/r 秒桶中增加一個(gè)令牌
- 桶中最多存放 b 個(gè)令牌冲九，如果桶滿了莺奸，新放入的令牌會(huì)被丟棄
- 當(dāng)一個(gè) n 字節(jié)的數(shù)據(jù)包到達(dá)時(shí)冀宴，消耗 n 個(gè)令牌略贮，然后發(fā)送該數(shù)據(jù)包
- 如果桶中可用令牌小于 n逃延，則該數(shù)據(jù)包將被緩存或丟棄
二、RateLimiter
Guava中開(kāi)源出來(lái)一個(gè)令牌桶算法的工具類RateLimiter讽膏，可以輕松實(shí)現(xiàn)限流的工作桅打。RateLimiter 對(duì)簡(jiǎn)單的令牌桶算法做了一些工程上的優(yōu)化挺尾，具體的實(shí)現(xiàn)是 SmoothBursty站绪。需要注意的是，RateLimiter 的另一個(gè)實(shí)現(xiàn) SmoothWarmingUp魂挂，就不是令牌桶了涂召，而是漏桶算法果正。也許是出于簡(jiǎn)單起見(jiàn)，RateLimiter 中的時(shí)間窗口能且僅能為 1s潦闲，如果想搞其他時(shí)間單位的限流迫皱，只能另外造輪子。
RateLimiter 有一個(gè)有趣的特性是「前人挖坑后人跳」和敬，也就是說(shuō) RateLimiter 允許某次請(qǐng)求拿走超出剩余令牌數(shù)的令牌概龄，但是下一次請(qǐng)求將為此付出代價(jià)，一直等到令牌虧空補(bǔ)上，并且桶中有足夠本次請(qǐng)求使用的令牌為止蚕键。這里面就涉及到一個(gè)權(quán)衡，是讓前一次請(qǐng)求干等到令牌夠用才走掉呢锣光，還是讓它先走掉后面的請(qǐng)求等一等呢笆怠？Guava 的設(shè)計(jì)者選擇的是后者，先把眼前的活干了誊爹，后面的事后面再說(shuō)蹬刷。
測(cè)試代碼：
public class RateLimiterMain {
public static void main(String[] args) {
RateLimiter rateLimiter = RateLimiter.create(2);
System.out.println(rateLimiter.acquire(5));
System.out.println(rateLimiter.acquire(2));
System.out.println(rateLimiter.acquire(1));
}
}
輸出內(nèi)容：
0.0
2.496889
0.992149
可以看出，令牌桶每秒只能產(chǎn)生2個(gè)令牌频丘，我們可以第一次取出5個(gè)办成，但是第二個(gè)再去取令牌的時(shí)候，需要等2.5s搂漠，也就是第一次令牌取完后迂卢，需要等2.5s才能取到令牌。同樣的桐汤，第三次取1個(gè)令牌的時(shí)候而克，也需要等待第二次的1s的時(shí)間。也就是怔毛，取的速率可以超過(guò)令牌產(chǎn)生的速率螃壤，但是下一次再次去取的時(shí)候，需要阻塞等待蚁滋。
當(dāng)然也可以使用tryAcquire來(lái)非阻塞的獲取，可以實(shí)時(shí)返回結(jié)果。另外tryAcquire也可以傳入?yún)?shù)，也就是等待的時(shí)間塞绿，超時(shí)直接返回false喜庞。這點(diǎn)等同于常見(jiàn)的lock雷猪，tryLock。
三、并發(fā)控制Semaphore
一般來(lái)說(shuō)，在網(wǎng)關(guān)系統(tǒng)中簸搞，還有一個(gè)參數(shù)叫并發(fā)控制，就是某一個(gè)資源可以被同時(shí)訪問(wèn)的個(gè)數(shù)。這種情況下垦细，我們可以使用Semaphore來(lái)控制家坎。
Semaphore不同于互斥鎖。互斥鎖是某個(gè)資源只能支持同時(shí)一個(gè)訪問(wèn)穿扳，而Semaphore可以支持多個(gè)訪問(wèn)跪但，但是加上了總數(shù)的控制。
感興趣的同學(xué)可以繼續(xù)深入了解Semaphore的使用。
