限流演算法漏桶和令牌桶區別

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

漏桶演算法(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個的請求都會被拒絕，但由於漏桶演算法流出速率是一定的，所以請求可能會被緩沖在桶中，不能馬上得到處理，從而徒增了等待時間，而對於令牌桶演算法，沒有這種等待時間，有令牌則通過，無令牌則拋棄。

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

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

㈢ 令牌桶限流演算法

令牌桶限流演算法是一種通過令牌桶實現對數據流進行管理的流量控制機制。其主要特點和運作機制如下：

1. 令牌桶的構成：

   • 令牌桶是一個固定大小的容器，用於存儲令牌。
   • 系統以恆定速率向桶中添加令牌。

2. 請求處理機制：

   • 當有請求到來時，系統需要先從桶中取出一個令牌。
   • 若桶中有令牌，則請求被允許通過。
   • 若桶中無令牌，則請求被限流，即不被允許通過。

3. 令牌桶的狀態變化：

   • 請求速度超過令牌生成速度：桶中的令牌會被快速消耗殆盡，後續請求因無法獲取令牌而被限制，實現對流量的控制。
   • 請求速度與令牌生成速度相等：系統進入平穩運行狀態，流量管理達到平衡。
   • 請求速度低於令牌生成速度：桶內令牌積累，系統處理能力遠大於實際需求，請求可被正常處理。

4. 應對突發流量的能力：

   • 相較於漏桶演算法，令牌桶演算法能夠應對短時間內突發的流量高峰。
   • 桶的存在允許在短時間內快速消耗大量令牌，從而支持高並發請求的處理，有效防止系統因突發流量而過載。

綜上所述，令牌桶限流演算法通過控制令牌的生成和消耗，實現了對數據流的精細化管理，有效防止了系統因流量過大而過載，同時能夠靈活應對突發的流量高峰。

㈣ 常見限流演算法：計數器、滑動窗口、漏桶、令牌桶

在高並發系統開發中，緩存、降級與限流是三大關鍵策略。其中，限流主要用於控制並發與請求量，如在秒殺活動或保護系統免受巨大流量沖擊時。

常見的限流演算法包括計數器、滑動窗口、漏桶與令牌桶。每種演算法根據業務需求、統計精度與限流維度有所不同。

計數器演算法是簡單且易於實現的限流方法，主要限制一定時間內的總並發數。其優點在於實現簡單，單機環境下利用Java的原子類或分布式環境下的Redis incr即可。然而，該演算法存在臨界問題，即在時間窗口重置節點處突發請求可能導致快速超過限流閾值。

滑動窗口演算法通過將固定窗口細分成多個小窗口，有效減少了臨界值帶來的並發超限問題。Spring Cloud 的熔斷框架 Hystrix 和 Spring Cloud Alibaba 的 Sentinel 均採用了滑動窗口進行數據統計。

漏桶演算法是一種柔性限流方法，限制請求的流出速率，適用於以固定速率控制流量，具有較好的穩定性。其原理類似於漏斗注水過程，請求通過漏桶後以恆定速率流出。但該演算法無法應對突發流量，且處理請求時存在延遲。

令牌桶演算法進一步改進了漏桶演算法，允許一定程度的流量突發。其原理是按照固定速率往桶中添加令牌，請求是否被處理取決於桶中令牌數量。令牌桶演算法適合網關層面或介面調用的限流，支持介面的伸縮性。

總結而言，漏桶與令牌桶演算法適用於阻塞式限流場景，如後台任務處理。而基於時間窗口的限流演算法更適用於互聯網業務限流場景，能有效處理快速請求，避免長時間等待。

實現限流通常藉助現成的組件或工具，如Google Guava 提供的 RateLimiter、阿里開源的 Sentinel 與Nginx 的 limit_req_zone。這些組件均利用了上述限流演算法，並在功能上有所擴展。