令牌桶算法限流

版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/SunnyYoona/article/details/51228456

今天觀看QCon大會講述了阿裡線上管控體系，其中主要使用了令牌桶算法來實作限流的目的。表示非常好奇，故此學習一下什麼是令牌桶算法。

1. 簡介

令牌桶算法最初來源于計算機網絡。在網絡傳輸資料時，為了防止網絡擁塞，需限制流出網絡的流量，使流量以比較均勻的速度向外發送。令牌桶算法就實作了這個功能，可控制發送到網絡上資料的數目，并允許突發資料的發送。

令牌桶算法是網絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發送到網絡上的資料的數目，并允許突發資料的發送。

大小固定的令牌桶可自行以恒定的速率源源不斷地産生令牌。如果令牌不被消耗，或者被消耗的速度小于産生的速度，令牌就會不斷地增多，直到把桶填滿。後面再産生的令牌就會從桶中溢出。最後桶中可以儲存的最大令牌數永遠不會超過桶的大小。

傳送到令牌桶的資料包需要消耗令牌。不同大小的資料包，消耗的令牌數量不一樣。

令牌桶這種控制機制基于令牌桶中是否存在令牌來訓示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。是以，如果突發門限被合理地配置并且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。

2.算法過程

算法描述：

• 假如使用者配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中（每秒會有r個令牌放入桶中）；
• 假設桶中最多可以存放b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丢棄；
• 當一個n個位元組的資料包到達時，就從令牌桶中删除n個令牌（不同大小的資料包，消耗的令牌數量不一樣），并且資料包被發送到網絡；
• 如果令牌桶中少于n個令牌，那麼不會删除令牌，并且認為這個資料包在流量限制之外（n個位元組，需要n個令牌。該資料包将被緩存或丢棄）；
• 算法允許最長b個位元組的突發，但從長期運作結果看，資料包的速率被限制成常量r。對于在流量限制外的資料包可以以不同的方式處理：（1）它們可以被丢棄；（2）它們可以排放在隊列中以便當令牌桶中累積了足夠多的令牌時再傳輸；（3）它們可以繼續發送，但需要做特殊标記，網絡過載的時候将這些特殊标記的包丢棄。

注意：

令牌桶算法不能與另外一種常見算法漏桶算法相混淆。這兩種算法的主要差別在于漏桶算法能夠強行限制資料的傳輸速率，而令牌桶算法在能夠限制資料的平均傳輸速率外，還允許某種程度的突發傳輸。在令牌桶算法中，隻要令牌桶中存在令牌，那麼就允許突發地傳輸資料直到達到使用者配置的門限，是以它适合于具有突發特性的流量。

3.Java實作

我們可以使用Guava 的 RateLimiter 來實作基于令牌桶的流控，RateLimiter 令牌桶算法是單桶實作。RateLimiter 對簡單的令牌桶算法做了一些工程上的優化，具體的實作是 SmoothBursty。需要注意的是，RateLimiter

的另一個實作SmoothWarmingUp，就不是令牌桶了，而是漏桶算法。也許是出于簡單起見，RateLimiter 中的時間視窗能且僅能為 1s。

SmoothBursty 有一個可以放 N 個時間視窗産生的令牌的桶，系統空閑的時候令牌就一直攢着，最好情況下可以扛 N 倍于限流值的高峰而不影響後續請求。RateLimite允許某次請求拿走超出剩餘令牌數的令牌，但是下一次請求将為此付出代價，一直等到令牌虧空補上，并且桶中有足夠本次請求使用的令牌為止。當某次請求不能得到所需要的令牌時，這時涉及到一個權衡，是讓前一次請求幹等到令牌夠用才走掉呢，還是讓它先走掉後面的請求等一等呢？Guava 的設計者選擇的是後者，先把眼前的活幹了，後面的事後面再說。