java令牌桶演算法

❶ 令牌桶演算法的分類

基於令牌桶的典型標記器有多種演算法實現方案，基本演算法主要有IN/OUT公平標記器（FM）和三色標記器（TCM），擴展的演算法主要有單速率三色標記器（srTCM）和雙速率三色標記器（trTCM）。其中單速率標記器和雙速率標記器已分別稱為IETF的標准建議。
IN/OUT 公平標記器（FM）
FM是一種雙色單令牌桶標記器，它的Tspec是系統的分組平均速錄為R，允許的突發度為B，工作原理就是當IP分組到達時若桶中有足夠的令牌，則將符合Tspec的分組標記為IN；若此時沒有足夠的令牌，則認為該到達分組不符合Tpsec，不符合Tpsec的分組將被標記為OUT，網路將可能對這些被標記為不同屬性的分組依據相應的策略進行不同的處理。
單速率三色標記器（srTCM）
srTCM是一種三色雙令牌桶標記器，它的Tpsec有三個參數：承諾信息速率，承諾突發尺寸和超額突發尺寸。CIR的單位是bps，CBS及EBS的單位是Byte。
srTCM由兩個令牌桶C和E組成，它們的CIR相同，容量則分別為CBS和EBS，C桶內存放黃色令牌，開始時令牌桶C與E都是滿的。進入的分組沒有超過CBS就標記為綠色；超過了CBS而沒有超過EBS就標記為黃色；否則標記為紅色。在DiffServ中，紅、黃、綠可映射為不同的DSCP值。
雙速率標記器（trTCM）
trTCM也是一種三色雙令牌桶標記器，它的Tpsec有4個參數：峰值信息速率（PIR）、峰值突發尺寸（PBS）、承諾信息速率（CIR）和承諾突發尺寸（CBS）。PIR和CIR的單位是bps，PBS和CBS的單位是Byte。

❷ 令牌桶（Token Bucket）

想像有一個木桶，系統按照固定速率，例如10ms每次，往桶里加入Token，如果桶已經滿了就不再添加。新請求來臨時，會各自拿走一個Token，如果沒有Token 就拒絕服務。這里如果一段時間沒有請求時，桶內就會積累一些token，下次一旦有突發流量，只要token足夠，也能一次處理。

總結下令牌桶演算法的特點，令牌桶即可以控制進入系統的請求請求量，同時允許突發流量。

在秒殺活動中，用戶的請求速率是不固定的，這里我們假定為10r/s，令牌按照5個每秒的速率放入令牌桶，桶中最多存放20個令牌，那系統就只會允許持續的每秒處理5 個請求，或者每隔4 秒，等桶中20 個令牌攢滿後，一次處理20個請求的突發情況，保證系統穩定性。

go簡易版實現

❸ java限流原理

Google的guava包中已有相關的限流解決方案(令牌桶演算法)
基於redis的限流演算法可以去參考redis-cell

❹ 令牌桶演算法的令牌桶工作參數

工作過程包括3個階段：產生令牌、消耗令牌和判斷數據包是否通過。其中涉及到2個參數：令牌產生的速率CIR（Committed Information Rate）/EIR（Excess Information Rate）和令牌桶的大小CBS（Committed Burst Size）/EBS（Excess Burst Size）。下面用圖形簡要概括一下這3個階段與2個參數的關系。
產生令牌：周期性的以速率CIR/EIR向令牌桶中增加令牌，桶中的令牌不斷增多。如果桶中令牌數已到達CBS/EBS，則丟棄多餘令牌。 消耗令牌：輸入數據包會消耗桶中的令牌。在網路傳輸中，數據包的大小通常不一致。大的數據包相較於小的數據包消耗的令牌要多。 判斷是否通過：輸入數據包經過令牌桶後的結果包括輸出的數據包和丟棄的數據包。當桶中的令牌數量可以滿足數據包對令牌的需求，則將數據包輸出，否則將其丟棄。

❺ 雲南java課程分享分布式限流的運行原理

分布式編程架構技術我們在前幾期的文章中已經給大家簡單分析過很多次了，今天我們就一起來了解一下API網關分布式限流的運行原理都有哪些。

API網關中針對一個API、API分組、接入應用APPID,IP等進行限流。這些限流條件都將會產生一個限流使用的key，在後續的限流中都是對這個key進行限流。

限流演算法通常在API網關中可以採用令牌桶演算法實現。

必須說明一點的是分布式限流由於有網路的開銷，TPS的支持隔本地限流是有差距的，因此在對於TPS要求很高的場景，建議採用本地限流進行處理。

下面討論我們應該採用redis的哪一種分布式鎖的方案：

由於redis事務要得到鎖的效果需要在高TPS時會產生大量的無效的訪問請求，所以不建議在這種場景下使用。

SETNX/EX的鎖方案會產生在過期時間的問題，同時也有非同步復制master數據到slave的問題。相比lua方案會產生更多的不穩定性。

我建議採用lua的方案來實施分布式鎖，因為都是單進程單線程的執行，因此在TPS上和二種方案沒有大的區別，而且由於只是一個lua腳本在執行，甚至是可能純lua執行可能會有更高的TPS。當然是lua腳本中可能還是會去設置過期時間，但是應用server宕機並不會影響到redis中的鎖。當然master非同步復制的問題還是有，但是並不會造成問題，因為數據只會有1個lua腳本執行問題，下一個執行就正常了。

在實現方案的時候使用了Jedis庫，雲南java課程http://www.kmbdqn.com/認為有一些問題在方案的實現層面我已經去做過驗證了，可能也會是讀者的疑問。

❻ 超出esb吞吐量,啟用流量控制是什麼意思

流量控制是匯流排系統非常核心的模塊，它能有效控制在高並發交易場景的流量情況，達到在業務突發狀況下的業務系統以及平台的穩定和可靠性。
典型的流量控制演算法採用令牌桶的演算法控制網路流量，網路令牌桶演算法如下：
令牌桶演算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。典型情況下，令牌桶演算法用來控制發送到網路上的數據的數目，並允許突發數據的發送。

令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。
————————————————
版權聲明：本文為CSDN博主「smartesb」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/smartesb/article/details/39478981

❼ 限流演算法之漏桶、令牌桶的區別

漏桶演算法(Leaky Bucket)是網路世界中流量整形（Traffic Shaping）或速率限制（Rate Limiting）時經常使用的一種演算法，它的主要目的是控制數據注入到網路的速率，平滑網路上的突發流量。漏桶演算法提供了一種機制，通過它，突發流量可以被整形以便為網路提供一個穩定的流量。

漏桶可以看作是一個帶有常量服務時間的單伺服器隊列，如果漏桶（包緩存）溢出，那麼數據包會被丟棄。 在網路中，漏桶演算法可以控制埠的流量輸出速率，平滑網路上的突發流量，實現流量整形，從而為網路提供一個穩定的流量。

如圖所示，把請求比作是水，水來了都先放進桶里，並以限定的速度出水，當水來得過猛而出水不夠快時就會導致水直接溢出，即拒絕服務。

可以看出，漏桶演算法可以很好的控制流量的訪問速度，一旦超過該速度就拒絕服務。

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

令牌桶演算法的原理是系統會以一個恆定的速度往桶里放入令牌，而如果請求需要被處理，則需要先從桶里獲取一個令牌，當桶里沒有令牌可取時，則拒絕服務。從原理上看，令牌桶演算法和漏桶演算法是相反的，一個「進水」，一個是「漏水」。

Google的Guava包中的RateLimiter類就是令牌桶演算法的解決方案。

漏桶演算法與令牌桶演算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。

漏桶演算法與令牌桶演算法的區別在於，漏桶演算法能夠強行限制數據的傳輸速率，令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。

需要注意的是，在某些情況下，漏桶演算法不能夠有效地使用網路資源，因為漏桶的漏出速率是固定的，所以即使網路中沒有發生擁塞，漏桶演算法也不能使某一個單獨的數據流達到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法結合起來為網路流量提供更高效的控制。

查看原文可以戳這里
限流技術早期被應用於控制網路介面收發通信數據的速率，在互聯網領域，也借鑒了這個概念，用於為服務控制請求的速率。

這段話怎麼理解呢，比如說存在兩個系統A、B，公用一個網路，網路帶寬為2M, A、B各分得1M，此時通過漏桶演算法控制兩個系統使用網路的速率，A、B系統使用網路的速率固定最大值為1M,無論A、B系統接受多少流量，但流出的速率都限制在最大1M,當網路中沒有發生擁塞，也就是可能出現B系統可能空閑沒有使用網路，對應分給B系統的1M帶寬是空閑的，而A系統這一時刻接收了5M的流量，由於漏桶限流的存在，A只能使用1M帶寬，我們的帶寬有2M,此刻我們只能使用1M,也就是達不到帶寬的最大速率，另外1M帶寬是浪費的，因此不能充分利用，缺乏效率；當然從另一方面來講也帶來了好處，就是隔離性，A系統無論收到多大的流量沖擊，對於B系統的無感的，不會因為流量沖擊A,而B受到影響.

這段又該怎麼理解呢，比如我們的目標現在是每秒鍾處理10個請求，使用漏桶法，我們設置桶的大小為10，流出的速率為0.1s流出一個請求，我們可以達成我們的目標；而使用令牌桶的話，我們會設置每1s向桶中放入10個令牌，請求如果是平穩的，每0.1s過來一個請求，來十個，同樣能達到我們的目標，這里所說的某種程度的突發傳輸是指，比如在一秒內前0.5請求是平穩的，每0.1s來一個，但在0.6s的時候突發請求同時來個5個請求，此時令牌演算法是可以承受這個突發流量的，並且讓5個請求成功立刻同時通過，完成了所謂的某種程度的突發傳輸，而漏桶演算法，也可以應對這種突發流量，但不同的是沒有讓5個請求同時立刻通過，而是緩沖在桶中，然後仍然以固定速率每0.1s通過一個。

這兩種演算法，都可以實現流速的控制，1s處理10個請求，多於10個的請求都會被拒絕，但由於漏桶演算法流出速率是一定的，所以請求可能會被緩沖在桶中，不能馬上得到處理，從而徒增了等待時間，而對於令牌桶演算法，沒有這種等待時間，有令牌則通過，無令牌則拋棄。

❽ RateLimiter令牌桶演算法淺析

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

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

傳送到令牌桶的數據包需要消耗令牌。不同大小的數據包，消耗的令牌數量不一樣。令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。

令牌桶演算法的基本過程：
假如用戶配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中；桶最多可以存發b個令牌。如果令牌到達時令牌桶已滿，則這個令牌會被丟棄；
當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被發送到網路；
如果令牌桶中少於n個令牌，則不會刪除令牌，並且認為這個數據包在流量限制之外；
演算法允許最長b個位元組的突發，數據包的速率被限製成常量r。對於在流量限制外的數據包可以以不同的方式處理：
1）被丟棄；
2）放在隊列中當令牌桶中累積了足夠多的令牌時再傳輸；
3）繼續發送，但需要做特殊標記，網路過載時將這些特殊標記的包丟棄。

令牌桶演算法與漏桶演算法（Leaky Bucket）的主要區別：
1）漏桶演算法能夠強行限制數據的傳輸速率，而令牌桶演算法在能夠限制數據的平均傳輸速率外，還允許某種程度的突發傳輸。
2）令牌桶演算法中，只要令牌桶中存在令牌，就允許突發地傳輸數據直到達到用戶配置的上限，它適合於具有突發特性的流量。

RateLimiter是Guava中開源的一個令牌桶演算法工具類，可以輕松實現限流工作。
RateLimiter有兩個實現類：SmoothBursty和SmoothWarmingUp;
兩者區別：
1）都是令牌桶演算法的變種實現
2）SmoothBursty加令牌的速度是恆定的，SmoothWarmingUp會有個預熱期，在預熱期內加令牌的速度是慢慢增加的，直到達到固定速度為止。其適用場景是，對於有的系統而言剛啟動時能承受的QPS較小，需要預熱一段時間後才能達到最佳狀態。

測試示例：

示例1：創建一個令牌桶，每秒生成一個令牌，申請失敗立即返回。使用CountdownLatch計數器模擬多線程並發，調用await()方法阻塞當前線程，當計數完成後，喚醒所有線程並發執行。

示例2：創建一個令牌桶，每秒生成0.1個令牌，即每10s才會有一個令牌，超時時間設置成20s，20s內獲取不到令牌返回失敗，20s內可以生成2個令牌，加上創建時桶里會有一個令牌，超時前最終會有3條線程拿到令牌，並且每個令牌獲取時間相隔10s。使用CountdownLatch計數器模擬多線程並發：調用await()方法阻塞當前線程，當計數完成後，喚醒所有線程並發執行。

參考文檔：
https://ke..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

❾ 什麼是漏桶演算法和令牌桶演算法

什麼是令牌桶
在我們討論突發數據量之前，我們首先要理解令牌桶的概念。令牌桶本身沒有丟棄
和優先順序策略，
令牌桶是這樣工作的：
1． 令牌以一定的速率放入桶中。
2． 每個令牌允許源發送一定數量的比特。
3． 發送一個包，流量調節器就要從桶中刪除與包大小相等的令牌數。
4． 如果沒有足夠的令牌發送包，這個包就會等待直到有足夠的令牌（在整形
器的情況下）或者包被丟棄，也有可能被標記更低的DSCP（在策略者的情況下）。
5． 桶有特定的容量，如果桶已經滿了，新加入的令牌就會被丟棄。因此，在
任何時候，源發送到網路上的最大突發數據量與桶的大小成比例。令牌桶允許突發，
但是不能超過限制。
Cisco IOS 流量策略（Traffic Policers）
IOS支持兩種流量策略：
1． 傳統的Cisco流量策略：CAR承諾接入速率，使用命令
Router(config-if)#rate-limit {input | output} CIR (bps)
Bc（burst-normal） Be(burst-max) conform-action action exceed-action action
2． 新型的Cisco流量策略：基於類的策略（Class-based policer），使用模
塊化Qos CLI（MQC）語法。可以使用MQC命令建立流量策略並把策略應用到介面。
一個流量策略包括一個流量類（traffic class）和一個或多個Qos特性。Policy
命令用來執行流量策略特性，它指定了一個流量類所需要的最大速率，超過這個速
率Qos系統會立刻執行一個操作，標準的操作是丟棄或重置包頭的DSCP欄位。Policy
命令的語法是：
police cir<bps> Bc<bc> Be<be> conform<conform-action> exceed
<exceed-action> violate<violate-action>
理解Bc和Be
對於超額的數據包，流量策略並不會把它們緩存稍候轉發，只有整形器（shaper）
會這樣做。流量策略只執行一個發送或不發送的策略。因為不能緩存數據包，所以
在發生擁塞時，所能做的最好的方法就是通過配置適當的超額突發數據量Be來不那
么過分的丟棄數據包。這一點對理解流量策略使用Bc和Be來保證達到CIR是非常
重要的。
超額參數模仿路由器的通用緩存規則。The rule recommends configuring buffering
equal to the round-trip time bitrate to accommodate the outstanding TCP
windows of all connections in times of congestion.
突發參數 目的 推薦公式
普通突發 · 執行標準的令牌桶 · 設置最大數量的令牌(盡管如
果Be>Bc的話可以借到令牌). · 決定令牌桶有多大，因為如果桶已經滿了那麼令
牌將被丟棄而不會再加入到桶中。 CIR [bps] * (1 byte)/(8 bits) * 1.5
seconds Note: 1.5 seconds is the typical round trip time.
超額突發 · 為令牌桶提供超額突發能力 · 如果Bc = Be那麼不
支持超額突發 · 當Bc = Be，流量調節器就不能借令牌，當令牌不夠時只能丟棄數
據包 兩倍的Bc
對TCP流量的測試表明，Bc 和Be的數值應該近似等於配置的平均速率在兩秒鍾內
的流量。如果你想限制流量在1Mb，應該把Bc 設置在1-2Mb，Be在2-4Mb。
舉個例子，如果我們想把輸出速率限制在1.5Mbps，我們可以做一下步驟：
1． 把承諾速率從比特轉換成位元組，因為突發數據量的單位為位元組。
1500000 bits / 8 bits = 187500 bytes
2． 使用標準的1.5秒往返時間（round-trip time）計算Bc
187500 bytes * 1.5秒 = 281250 bytes
3． 兩倍的Bc為Be
281250 bytes * 2 = 562500 bytes
使用命令
rate-limit input 1500000 281250 562500 conform-action {action}
exceed-action {action}
超額突發數據量
當數據包到達時可用的令牌數目小於包的大小，就可以使用超額突發數據量。包會
請求借用令牌。可以通過配置大於Bc的Be的數值來為令牌桶提供超額突發能力。
可以通過下面兩個例子來理解Be。
第一個例子說明怎樣配置CAR策略來允許所有的IP流量。管理員在T3線路上提供
了便宜的20Mbps的子速率服務。用戶只花費子速率帶寬的金額，也可以按需要增加
帶寬。CAR限制了用戶可用的流量速率，用戶只能使用規定的速率加上承諾的突發
數據量。可以適當的設置Be=32000。
interface hssi 0/0/0
rate-limit output 20000000 24000 32000 conform-action transmit
exceed-action drop
下一個例子，用戶只能發送24000位元組的突發數據量，所有超過限制的數據包都要
被丟棄，因為設置Bc=Be，數據包流不能通過超額突發能力來借用令牌。
interface Hssi0/0/0
rate-limit output 20000000 24000 24000 conform-action transmit
exceed-action drop
正確設置突發數據量的重要性
策略以位元組為單位指定了突發數據量，基於類的策略（class-based policer）支持
最小的突發數據量為1000位元組，包括第二層包頭。
突發數據量的目的是逐漸的丟棄數據包，就像RED那樣，並且避免尾丟棄。設置足
夠高的突發數據量對保證良好的吞吐量是非常重要的。
設置突發數據量時，考慮一下內容：
1． 如果突發數據量設置的過低，數據到達的速率將遠遠低於配置的速率。
2． 懲罰暫時突發對TCP流的吞吐量來說是相當不利的，具體情況請察看RFC
2001 and Random Early Detection (RED) gateways for Congestion Avoidance。
設置突發數據量來允許路由器容納暫時突發。
3． 對離開介面的數據包的處理基於包的大小和桶中剩餘的令牌數。
4． 在基於類的策略中，流量測量器不論介面是否擁塞都是激活的。每個包都
會經過令牌桶測量系統來決定是否符合配置的參數。
5． 如果數據突發量非常大而且非常突然，那麼配置較高的超額突發數據量可
以保證超額令牌桶中存放較多的令牌。而且可以調整介面的MTU等於或大於突發數
據量大小。
允許的突發數據量數值
最初，包括IOS12.0，rate-limit命令支持承諾和超額的突發數據量的范圍是：
Router1(config-if)#rate-limit input 18000000 ?
<8000-2000000> Normal burst bytes
Router1(config-if)#rate-limit input 18000000 2000000 ?
<8000-8000000> Maximum burst bytes
Router1(config-if)#rate-limit input 18000000 2000000
IOS12.1增加了突發數據量的最大值：
7500-107(config)#interface atm 1/0/0
7500-107(config-if)#rate-limit output ?
<8000-2000000000> Bits per second
access-group Match access list
qos-group Match qos-group ID<b

❿ 令牌桶演算法的簡介

在網路中傳輸數據時，為了防止網路擁塞，需限制流出網路的流量，使流量以比較均勻的速度向外發送。令牌桶演算法就實現了這個功能，可控制發送到網路上數據的數目，並允許突發數據的發送。
令牌桶演算法是網路流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種演算法。典型情況下，令牌桶演算法用來控制發送到網路上的數據的數目，並允許突發數據的發送。
大小固定的令牌桶可自行以恆定的速率源源不斷地產生令牌。如果令牌不被消耗，或者被消耗的速度小於產生的速度，令牌就會不斷地增多，直到把桶填滿。後面再產生的令牌就會從桶中溢出。最後桶中可以保存的最大令牌數永遠不會超過桶的大小。
傳送到令牌桶的數據包需要消耗令牌。不同大小的數據包，消耗的令牌數量不一樣。
令牌桶這種控制機制基於令牌桶中是否存在令牌來指示什麼時候可以發送流量。令牌桶中的每一個令牌都代表一個位元組。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。因此，如果突發門限被合理地配置並且令牌桶中有足夠的令牌，那麼流量就可以以峰值速率發送。
令牌桶演算法的基本過程如下：
假如用戶配置的平均發送速率為r，則每隔1/r秒一個令牌被加入到桶中；
假設桶最多可以存發b個令牌。如果令牌到達時令牌桶已經滿了，那麼這個令牌會被丟棄；
當一個n個位元組的數據包到達時，就從令牌桶中刪除n個令牌，並且數據包被發送到網路；
如果令牌桶中少於n個令牌，那麼不會刪除令牌，並且認為這個數據包在流量限制之外；
演算法允許最長b個位元組的突發，但從長期運行結果看，數據包的速率被限製成常量r。對於在流量限制外的數據包可以以不同的方式處理：
它們可以被丟棄；
它們可以排放在隊列中以便當令牌桶中累積了足夠多的令牌時再傳輸；
它們可以繼續發送，但需要做特殊標記，網路過載的時候將這些特殊標記的包丟棄。
注意：令牌桶演算法不能與另外一種常見演算法「漏桶演算法（Leaky Bucket）」相混淆。這兩種演算法的主要區別在於「漏桶演算法」能夠強行限制數據的傳輸速率，而「令牌桶演算法」在能夠限制數據的平均傳輸速率外，還允許某種程度的突發傳輸。在「令牌桶演算法」中，只要令牌桶中存在令牌，那麼就允許突發地傳輸數據直到達到用戶配置的門限，因此它適合於具有突發特性的流量。