限流令牌桶演算法

㈠ 漏桶演算法的漏桶演算法和令牌桶演算法的區別

漏桶演算法與令牌桶演算法在表面看起來類似，很容易將兩者混淆。但事實上，這兩者具有截然不同的特性，且為不同的目的而使用。漏桶演算法與令牌桶演算法的區別在於：
l 漏桶演算法能夠強行限制數據的傳輸速率。
l 令牌桶演算法能夠在限制數據的平均傳輸速率的同時還允許某種程度的突發傳輸。
需要說明的是：在某些情況下，漏桶演算法不能夠有效地使用網路資源。因為漏桶的漏出速率是固定的，所以即使網路中沒有發生擁塞，漏桶演算法也不能使某一個單獨的數據流達到埠速率。因此，漏桶演算法對於存在突發特性的流量來說缺乏效率。而令牌桶演算法則能夠滿足這些具有突發特性的流量。通常，漏桶演算法與令牌桶演算法結合起來為網路流量提供更高效的控制。

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

什麼是令牌桶
在我們討論突發數據量之前，我們首先要理解令牌桶的概念。令牌桶本身沒有丟棄
和優先順序策略，
令牌桶是這樣工作的：
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

㈢ mysql 大流量，高並發問題

限流演算法目前程序開發過程常用的限流演算法有兩個：漏桶演算法和令牌桶演算法。

漏桶演算法

漏桶演算法的原理比較簡單，請求進入到漏桶中，漏桶以一定的速率漏水。當請求過多時，水直接溢出。可以看出，漏桶演算法可以強制限制數據的傳輸速度。如圖所示，把請求比作是水滴，水先滴到桶里，通過漏洞並以限定的速度出水，當水來得過猛而出水不夠快時就會導致水直接溢出，即拒絕服務。

圖片來自網路

漏桶演算法和令牌桶演算法的選擇

兩者的主要區別漏桶演算法能夠強行限制處理數據的速率，不論系統是否空閑。而令牌桶演算法能夠在限制數據的平均處理速率的同時還允許某種程度的突發流量。如何理解上面的含義呢？漏桶演算法，比如系統吞吐量是 120/s，業務請求 130/s，使用漏斗限流 100/s，起到限流的作用，多餘的請求將產生等待或者丟棄。對於令牌桶演算法，每秒產生 100 個令牌，系統容量 200 個令牌。正常情況下，業務請求 100/s 時，請求能被正常被處理。當有突發流量過來比如 200 個請求時，因為系統容量有 200 個令牌可以同一時刻處理掉這 200 個請求。如果是漏桶演算法，則只能處理 100 個請求，其他的請求等待或者被丟棄。