一、簡介
百度百科中的定義：
令牌桶算法是網(wǎng)絡流量（Traffic Shaping）整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發(fā)送到網(wǎng)絡上的數(shù)據(jù)的數(shù)目，并允許突發(fā)數(shù)據(jù)的發(fā)送。
大小固定的令牌桶可自行以恒定的速率源源不斷地產(chǎn)生令牌。如果令牌不被消耗，或者被消耗的速度小于產(chǎn)生的速度，令牌就會不斷地增多，直到把桶填滿。后面再產(chǎn)生的令牌就會從桶中溢出。最后桶中可以保存的最大令牌數(shù)永遠不會超過桶的大小。
傳送到令牌桶的數(shù)據(jù)包需要消耗令牌。不同大小的數(shù)據(jù)包，消耗的令牌數(shù)量不一樣。令牌桶這種控制機制基于令牌桶中是否存在令牌來指示什么時候可以發(fā)送流量。令牌桶中的每一個令牌都代表一個字節(jié)。如果令牌桶中存在令牌，則允許發(fā)送流量；而如果令牌桶中不存在令牌，則不允許發(fā)送流量。因此，如果突發(fā)門限被合理地配置并且令牌桶中有足夠的令牌，那么流量就可以以峰值速率發(fā)送。
二、限流算法：漏桶算法和令牌桶算法
- 漏桶算法(Leaky Bucket)：基本原理是水(請求)先進入到漏桶里，漏桶以一定的速度出水(接口有響應速率)，當水流入速度過大超出了桶的容量，會直接溢出而被丟棄(訪問頻率超過接口響應速率)，就拒絕請求。
- 令牌桶算法：它是一個存放固定容量令牌的桶，按照固定速率往桶里添加令牌。
假設限制2r/s，則按照500毫秒的固定速率往桶中添加令牌；
桶中最多存放b個令牌，當桶滿時，新添加的令牌被丟棄或拒絕；
當一個n個字節(jié)大小的數(shù)據(jù)包到達，將從桶中刪除n個令牌，接著數(shù)據(jù)包被發(fā)送到網(wǎng)絡上；
如果桶中的令牌不足n個，則不會刪除令牌，且該數(shù)據(jù)包將被限流（要么丟棄，要么緩沖區(qū)等待）。
令牌桶算法的基本過程：
假如用戶配置的平均發(fā)送速率為r，則每隔1/r秒一個令牌被加入到桶中；桶最多可以存發(fā)b個令牌。如果令牌到達時令牌桶已滿，則這個令牌會被丟棄；
當一個n個字節(jié)的數(shù)據(jù)包到達時，就從令牌桶中刪除n個令牌，并且數(shù)據(jù)包被發(fā)送到網(wǎng)絡；
如果令牌桶中少于n個令牌，則不會刪除令牌，并且認為這個數(shù)據(jù)包在流量限制之外；
算法允許最長b個字節(jié)的突發(fā)，數(shù)據(jù)包的速率被限制成常量r。對于在流量限制外的數(shù)據(jù)包可以以不同的方式處理：
1）被丟棄；
2）放在隊列中當令牌桶中累積了足夠多的令牌時再傳輸；
3）繼續(xù)發(fā)送，但需要做特殊標記，網(wǎng)絡過載時將這些特殊標記的包丟棄。
令牌桶算法與漏桶算法（Leaky Bucket）的主要區(qū)別：
1）漏桶算法能夠強行限制數(shù)據(jù)的傳輸速率，而令牌桶算法在能夠限制數(shù)據(jù)的平均傳輸速率外，還允許某種程度的突發(fā)傳輸。
2）令牌桶算法中，只要令牌桶中存在令牌，就允許突發(fā)地傳輸數(shù)據(jù)直到達到用戶配置的上限，它適合于具有突發(fā)特性的流量。
三、Guava-RateLimiter
RateLimiter是Guava中開源的一個令牌桶算法工具類，可以輕松實現(xiàn)限流工作。
RateLimiter有兩個實現(xiàn)類：SmoothBursty和SmoothWarmingUp;
兩者區(qū)別：
1）都是令牌桶算法的變種實現(xiàn)
2）SmoothBursty加令牌的速度是恒定的，SmoothWarmingUp會有個預熱期，在預熱期內(nèi)加令牌的速度是慢慢增加的，直到達到固定速度為止。其適用場景是，對于有的系統(tǒng)而言剛啟動時能承受的QPS較小，需要預熱一段時間后才能達到最佳狀態(tài)。
測試示例：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version>
</dependency>
示例1：創(chuàng)建一個令牌桶，每秒生成一個令牌，申請失敗立即返回。使用CountdownLatch計數(shù)器模擬多線程并發(fā)，調(diào)用await()方法阻塞當前線程，當計數(shù)完成后，喚醒所有線程并發(fā)執(zhí)行。
//每秒生成一個令牌，返回SmoothBursty實現(xiàn)類
RateLimiter rateLimiter = RateLimiter.create(1D);
CountDownLatch countDownLatch = new CountDownLatch(1);
ExecutorService executor = Executors.newCachedThreadPool();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
for (int i = 0; i < 10; i++) {
Runnable runnable = () -> {
try {
countDownLatch.await();
//嘗試獲取令牌桶中一個令牌，失敗立即返回
if (rateLimiter.tryAcquire()) {
System.out.println(Thread.currentThread().getName() + ": " + sdf.format(new Date()) + "獲取到令牌");
} else System.out.println(Thread.currentThread().getName());
} catch (InterruptedException e) {e.printStackTrace();}
};
executor.submit(runnable);
}
countDownLatch.countDown();
executor.shutdown();
示例2：創(chuàng)建一個令牌桶，每秒生成0.1個令牌，即每10s才會有一個令牌，超時時間設置成20s，20s內(nèi)獲取不到令牌返回失敗，20s內(nèi)可以生成2個令牌，加上創(chuàng)建時桶里會有一個令牌，超時前最終會有3條線程拿到令牌，并且每個令牌獲取時間相隔10s。使用CountdownLatch計數(shù)器模擬多線程并發(fā)：調(diào)用await()方法阻塞當前線程，當計數(shù)完成后，喚醒所有線程并發(fā)執(zhí)行。
//每秒生成0.1個令牌，返回SmoothBursty實現(xiàn)類
RateLimiter rateLimiter = RateLimiter.create(0.1D);
CountDownLatch countDownLatch = new CountDownLatch(1);
ExecutorService executor = Executors.newCachedThreadPool();
SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
for (int i = 0; i < 10; i++) {
Runnable runnable = () -> {
try {
countDownLatch.await();
//嘗試獲取令牌桶中一個令牌，最多等待20秒
if (rateLimiter.tryAcquire(20, TimeUnit.SECONDS)) {
System.out.println(Thread.currentThread().getName() + ": " + sdf.format(new Date()) + "獲取到令牌");
} else System.out.println(Thread.currentThread().getName());
} catch (InterruptedException e) {e.printStackTrace();}
};
executor.submit(runnable);
}
countDownLatch.countDown();
executor.shutdown();
參考文檔：
https://baike.baidu.com/item/%E4%BB%A4%E7%89%8C%E6%A1%B6%E7%AE%97%E6%B3%95/6597000?fr=aladdin
https://blog.csdn.net/unclecoco/article/details/99583154
