四種常用限流演算法掌握一身，面試必過

在高並發訪問下，例如電商大促活動，流量持續不斷的湧入，服務之間的相互調用頻率突然增加，引發系統負載過高，這時系統所依賴的服務的穩定性對系統的影響非常大，而且還有很多不確定因素引起雪崩，如網路連線中斷，服務宕機等。一般微服務容錯組件提供了限流、隔離、降級、熔斷等手段，可以有效保護我們的微服務系統。本文主要說說限流。

限流，就是限制最大流量，防止操作頻率超過定義的限制。系統能提供的最大並發有限，同時請求又太多，這就需要限流，比如秒殺、大促活動業務，瞬時大量請求湧入，伺服器服務不過來，就只好限流了。速率限制透過限制在給定時間段內可以到達 API 的請求數量來保護服務免受意外或惡意過度使用。在沒有速率限制的情況下，任何用戶都可以用請求轟炸您的伺服器，從而導致其他用戶餓死的情況。

為什麼要限速？

• 防止資源匱乏：速率限制的最常見原因是透過避免資源匱乏來提高基於 API 的服務的可用性。如果應用速率限制，則可以防止基於負載的拒絕服務 (doS) 攻擊。即使有用戶用大量請求轟炸 API，其他用戶也不會挨餓。
• 安全性：速率限制可防止暴力破解登入、促銷代碼等安全密集型功能。對這些功能的請求數量在用戶層級受到限制，因此暴力破解演算法在這些場景中不起作用。
• 防止營運成本：在按使用付費模式自動擴展資源的情況下，速率限制透過對資源擴展設定虛擬上限來幫助控制營運成本。如果不採用速率限制，資源可能會不成比例地擴展，從而導致指數級的帳單。

速率限制策略速率限制可套用於下列參數：

• #使用者：限制在給定時間段內允許用戶的請求數。基於使用者的速率限制是最常見和最直觀的速率限制形式之一。
• 並發性：這裡限制了在給定時間範圍內使用者可以允許的平行會話數。並行連接數量的限制也有助於緩解 DDOS 攻擊。
• 位置/ID：這有助於運行基於位置或以人口統計為中心的活動。可以限制不是來自目標人口統計的請求，以提高目標區域的可用性
• #伺服器：基於伺服器的速率限制是一種利基策略。這通常在特定伺服器需要大部分請求時使用，即伺服器與特定功能強耦合

接下來，我們將介紹四種常見的限流演算法

1.漏桶演算法

漏桶演算法的思路，是一種簡單直覺的演算法，就是⼀個固定容量的漏桶，依照常量固定速率流出⽔滴。如果桶子是空的，則不需流出水滴。可以任意速率流入水滴到漏桶。如果流入水滴超出了桶的容量，則流入的水滴溢出了（被丟棄），而漏桶容量是不變的。

這種演算法的優點是它可以平滑請求的突發並以恆定的速率處理它們。它也很容易在負載平衡器上實現，並且對每個用戶來說都是高效的記憶體。無論請求的數量如何，都保持到伺服器的恆定接近均勻的流量。

缺點是請求的爆發可能會填滿儲存桶，導致新請求的匱乏。它也不能保證請求在給定的時間內完成。

優點：

• #平滑流量。 由於漏桶演算法以固定的速率處理請求，可以有效地平滑和整形流量，避免流量的突發和波動（類似於訊息佇列的削峰填谷的作用）。
• 防止過載。 當流入的請求超過桶的容量時，可以直接丟棄請求，防止系統過載。

缺點：

• 無法處理突發流量：由於漏桶的出口速度是固定的，無法處理突發流量。例如，即使在流量較小的時候，也無法以更快的速度處理要求。
• 可能會遺失資料：如果入口流量過大，超過了桶的容量，那麼就需要丟棄部分請求。在一些不能接受遺失請求的場景中，這可能是一個問題。

2、令牌桶演算法

令牌桶演算法：假設限制2r/s，則依照500毫秒的固定速率往桶中添加令牌。桶中最多存放b個令牌，當桶滿時，新加入的令牌被丟棄或拒絕。當一個n個位元組大小的封包到達，將從桶中刪除n個令牌，接著封包被傳送到網路上。如果桶中的令牌不足n個，則不會刪除令牌，且該封包將被限流（要么丟棄，要么緩衝區等待）。令牌桶限流原理，如圖所示。

限流伺服器端的令牌桶可以根據實際服務效能和時間段來調整產生令牌的速度和桶的容量。當需要提高速率時，可以按需增加放入桶中的令牌速率

產生令牌的速度是恆定的，而請求取得令牌的速度沒有限制。這意味著當面對瞬時大流量時，該演算法可以在短時間內獲取大量令牌，而且獲取令牌的過程並不會消耗很多資源

當每次新的請求到達伺服器時，會執行兩個動作：

• 取得令牌：取得該使用者的目前令牌數。如果它大於定義的限制，則丟棄請求。
• 更新令牌：如果取得的令牌小於持續時間 d 的限制，則接受請求並附加令牌。

該演算法具有記憶體效率，因為我們為我們的應用程式為每個用戶節省了更少的資料量。這裡的問題是它可能導致分散式環境中的競爭條件。當來自兩個不同應用程式伺服器的兩個請求同時嘗試取得令牌時，就會發生這種情況。

優點：

• 可以處理突發流量##：令牌桶演算法可以處理突發流量。當桶滿時，能夠以最大速度處理請求。這對於需要處理突發流量的應用場景非常有用。
• 限制平均速率：在長期運行中，資料的傳輸率會被限制在預先定義的平均速率（即生成令牌的速率）。
• 靈活性：與漏桶演算法相比，令牌桶演算法提供了更大的靈活性。例如，可以動態地調整產生令牌的速率。

缺點：

• 可能導致過載：如果令牌產生的速度太快，可能會導致大量的突發流量，這可能會使網路或服務過載。
• 需要儲存空間：令牌桶需要一定的儲存空間來保存令牌，可能會導致記憶體資源的浪費。
• 實作稍微複雜：比起計數器演算法，令牌桶演算法的實作稍微複雜一些。

3、固定時間窗⼝演算法

在固定的時間視窗內，允許一定數量的請求進入。超過數量則拒絕或排隊等待下一個時段。這種計數器限流的實作方式是在時間間隔內進行限制。如果使用者在上一個時間間隔結束前發送請求（但未超過限制），同時在當前時間間隔開始時也發送請求（同樣未超過限制），那麼在各自的時間間隔內，這些請求都是正常的。然而，當請求在時間間隔的臨界時間段內超過系統限制時，可能會導致系統過載

由於計數器演算法存在時間臨界點缺陷，因此在時間臨界點左右的極短時間段內容易遭到攻擊。例如設定每分鐘最多可以請求100次某個接口，如12:00:00-12:00:59時間段內沒有資料請求，而12:00:59-12:01:00時間段突然並發100次請求，而緊接著跨入下一個計數週期，計數器清零，在12:01:00-12:01:01內又有100次請求。那麼也就是說在時間臨界點左右可能同時有2倍的閥值進行請求，從而造成後台處理請求過載的情況，導致系統運作能力不足，甚至導致系統崩潰。

缺點：

• 限流不夠平滑。例如：限流是每秒3個，在第一毫秒發送了3個請求，達到限流，視窗剩餘時間的請求都會被拒絕，體驗不好。
• 無法處理視窗邊界問題。因為是在某個時間視窗內進行流量控制，所以可能會出現視窗邊界效應，即在時間視窗的邊界處可能會有大量的請求被允許通過，導致突發流量。

例如：限流是每秒3個，在第一秒的最後毫秒發送了3個請求，在第二秒的第一毫秒又發送了3個請求。在這兩毫米內處理了6個請求，但是並沒有觸發限流。如果出現突發流量，可能會壓垮伺服器。

4、滑動時間窗⼝演算法

滑動視窗⼝演算法是把固定時間間進行劃分，並且隨著時間移動，移動方式為開始時間點變成時間列表中的第二時間點，結束時間點增加一個時間點，不斷重複，透過這種方式可以巧妙的避開計數器的臨界點的問題。

滑動視窗演算法可以有效的規避計數器演算法中時間臨界點的問題，但是仍然存在時間片段的概念。同時滑動視窗演算法計數運算也相對固定時間視窗演算法比較耗時。

缺點：# 還是有限流不夠平滑的問題。例如：限流是每秒3個，在第一毫秒發送了3個請求，達到限流，剩餘視窗時間的請求都會被拒絕，體驗不好。

總結

介紹了四種常用的限流演算法：固定視窗演算法、滑動視窗演算法、漏桶演算法和令牌桶演算法。每種演算法都有其特點和適用場景，下面我們將它們進行簡單的總結和比較。

• 令牌桶演算法既能平滑流量，又能處理突發流量，適用於需要處理突發流量的場景。
• 漏桶演算法的優點是流量處理更平滑，但是無法應對突發流量，適用於需要平滑流量的場景。
• 固定視窗演算法 實作簡單，但是限流不夠平滑，存在視窗邊界問題，適用於需要簡單實作限流的場景。
• 滑動視窗演算法解決了視窗邊界問題，但是還是存在限流不夠平滑的問題，適用於需要控制平均請求速率的場景。

#

以上是四種常用限流演算法掌握一身，面試必過的詳細內容。更多資訊請關注PHP中文網其他相關文章！