限流
每個API接口都是有訪問上限的，當訪問頻率或者并發(fā)量超過其承受范圍時候，我們就必須考慮限流來保證接口的可用性或者降級，即接口也需要安裝上保險絲，以防止非預期的請求對系統(tǒng)壓力過大而引起的系統(tǒng)癱瘓。
通常的策略就是拒絕多余的訪問，或者讓多余的訪問排隊等待服務，或者引流。
限流算法
常用的更平滑的限流算法有兩種：漏桶算法和令牌桶算法。
漏桶算法
漏桶(Leaky Bucket)算法思路很簡單，水(請求)先進入到漏桶里，漏桶以一定的速度出水(接口有響應速率)，當水流入速度過大會直接溢出(訪問頻率超過接口響應速率)，然后就拒絕請求，可以看出漏桶算法能強行限制數(shù)據(jù)的傳輸速率。示意圖如下：
可見這里有兩個變量，一個是桶的大小，支持流量突發(fā)增多時可以存多少的水(burst)，另一個是水桶漏洞的大小(rate)，偽代碼如下：
double rate; // leak rate in calls/s
double burst; // bucket size in calls
long refreshTime; // time for last water refresh
double water; // water count at refreshTime
refreshWater() {
long now = getTimeOfDay();
//水隨著時間流逝,不斷流走,最多就流干到0.
water = max(0, water- (now - refreshTime)*rate);
refreshTime = now;
}
bool permissionGranted() {
refreshWater();
if (water < burst) { // 水桶還沒滿,繼續(xù)加1
water ++;
return true;
} else {
return false;
}
}
因為漏桶的漏出速率是固定的參數(shù)，所以，即使網(wǎng)絡中不存在資源沖突(沒有發(fā)生擁塞)，漏桶算法也不能使流突發(fā)(burst)到端口速率。因此，漏桶算法對于存在突發(fā)特性的流量來說缺乏效率。
令牌桶算法
令牌桶算法(Token Bucket)和 Leaky Bucket 效果一樣，但方向相反的算法。隨著時間流逝，系統(tǒng)會按恒定1/QPS時間間隔(如果QPS=100，則間隔是10ms)往桶里加入Token(想象和漏洞漏水相反，有個水龍頭在不斷的加水)，如果桶已經(jīng)滿了就不再加了。新請求來臨時，會各自拿走一個Token，如果沒有Token可拿了就阻塞或者拒絕服務。
大小固定的令牌桶可自行以恒定的速率源源不斷地產(chǎn)生令牌。如果令牌不被消耗，或者被消耗的速度小于產(chǎn)生的速度，令牌就會不斷地增多，直到把桶填滿。后面再產(chǎn)生的令牌就會從桶中溢出。最后桶中可以保存的最大令牌數(shù)永遠不會超過桶的大小。
傳送到令牌桶的數(shù)據(jù)包需要消耗令牌。不同大小的數(shù)據(jù)包，消耗的令牌數(shù)量不一樣。
令牌桶這種控制機制基于令牌桶中是否存在令牌來指示什么時候可以發(fā)送流量。令牌桶中的每一個令牌都代表一個字節(jié)。如果令牌桶中存在令牌，則允許發(fā)送流量；而如果令牌桶中不存在令牌，則不允許發(fā)送流量。因此，如果突發(fā)門限被合理地配置并且令牌桶中有足夠的令牌，那么流量就可以以峰值速率發(fā)送。
Guava RateLimiter 簡介
google開源工具包Guava提供了限流工具類RateLimiter，該類基于令牌桶算法(Token Bucket)來完成限流，非常易于使用。RateLimiter經(jīng)常用于限制對一些物理資源或者邏輯資源的訪問速率。它支持兩種獲取permits接口，一種是如果拿不到立刻返回false，一種會阻塞等待一段時間看能不能拿到。
RateLimiter和JAVA中的信號量(java.util.concurrent.Semaphore)類似，Semaphore通常用于限制并發(fā)量。
源碼中的一個例子，比如我們有很多任務需要執(zhí)行，但是我們不希望每秒超過兩個任務執(zhí)行，那么我們就可以使用RateLimiter：
final RateLimiter rateLimiter = RateLimiter.create(2.0);
void submitTasks(List<Runnable> tasks, Executor executor) {
for (Runnable task : tasks) {
rateLimiter.acquire(); // may wait
executor.execute(task);
}
}
另外一個例子，假如我們會產(chǎn)生一個數(shù)據(jù)流，然后我們想以每秒5kb的速度發(fā)送出去。我們可以每獲取一個令牌(permit)就發(fā)送一個byte的數(shù)據(jù)，這樣我們就可以通過一個每秒5000個令牌的RateLimiter來實現(xiàn)：
final RateLimiter rateLimiter = RateLimiter.create(5000.0);
void submitPacket(byte[] packet) {
rateLimiter.acquire(packet.length);
networkService.send(packet);
}
另外，我們也可以使用非阻塞的形式達到降級運行的目的，即使用非阻塞的tryAcquire()方法：
if(limiter.tryAcquire()) { //未請求到limiter則立即返回false
doSomething();
}else{
doSomethingElse();
}
漏桶算法和令牌桶算法的選擇
漏桶算法與令牌桶算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。
漏桶算法與令牌桶算法的區(qū)別在于，漏桶算法能夠強行限制數(shù)據(jù)的傳輸速率，令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時還允許某種程度的突發(fā)傳輸。
需要注意的是，在某些情況下，漏桶算法不能夠有效地使用網(wǎng)絡資源，因為漏桶的漏出速率是固定的，所以即使網(wǎng)絡中沒有發(fā)生擁塞，漏桶算法也不能使某一個單獨的數(shù)據(jù)流達到端口速率。因此，漏桶算法對于存在突發(fā)特性的流量來說缺乏效率。而令牌桶算法則能夠滿足這些具有突發(fā)特性的流量。通常，漏桶算法與令牌桶算法結合起來為網(wǎng)絡流量提供更高效的控制。
