4 設計限速器

在網路系統中，限速器用於控制客戶端或服務發送流量的速率。在HTTP世界中，限速器限制在指定時間內允許發送的客戶端請求數量。如果API請求數超過了限速器定義的閾值，超出調用都會被阻止。下麵是幾個例子：

• 用戶每秒最多只能寫2篇文章。

• 同一IP地址每天最多只能創建10個賬戶。

• 同一設備每周最多可申請5次獎勵。

本章將要求您設計限速器。在開始設計之前，我們首先瞭解一下使用API限速器的好處：

• 防止拒絕服務（DoS Denial of Service）攻擊造成的資源枯竭。

幾乎所有大型科技公司發佈的API都會強制執行某種形式的速率限制。例如，Twitter將推文數量限製為每3小時 300條。Google docs API的預設限制如下：每個用戶每60秒讀取請求300次。限速器通過阻止多餘的調用來防止有意或無意的DoS攻擊。

• 降低成本

限制過量請求意味著減少伺服器數量，將更多資源分配給優先順序高的API。對於使用付費第三方API的公司來說，速率限制極為重要。例如，以下外部應用程式介面按調用次數收費：檢查信用、付款、檢索健康記錄等。限制調用次數對降低成本至關重要。

-防止伺服器過載

為減少伺服器負載，可使用限速器來過濾機器人或用戶不當行為造成的多餘請求。

4.1 步驟 1 - 理解問題並確定設計範圍

速率限制可以使用不同的演算法來實現，每種演算法都有其優缺點。面試官和應聘者之間的互動有助於明確我們要構建的限速器類型。

候選人：我們要設計哪種限速器？是客戶端限速器還是伺服器端API限速器？

面試官：問得好。我們的重點是伺服器端API限速器。

候選人：限速器是根據IP、用戶ID還是其他屬性來限制API請求？

面試官：限速器應該足夠靈活，以支持不同的節流規則。

應聘者：系統的規模有多大？是為初創公司還是擁有龐大用戶群的大公司構建的？

面試官：系統必須能夠處理大量請求。

應聘者：系統能否在分散式環境中運行？

面試官：可以。

應聘者：限速器是單獨的服務，還是應該在應用程式代碼中實現？

面試官：這取決於你的設計決定。

應聘者：我們需要通知被節流的用戶嗎？

面試官：需要。

要求

以下是系統要求的摘要：

• 準確限制過多請求。
• 低延遲。限速器不應減慢HTTP響應時間。
• 使用儘可能少的記憶體。
• 分散式速率限制。限速器可在多個伺服器或進程中共用。
• 異常處理。當用戶的請求被節流時，向用戶顯示明確的異常。
• 高容錯性。如果限速器出現任何問題（例如，緩存伺服器離線），不會影響整個系統。

4.2 第2步 - 提出概要設計方案並獲得支持

讓我們保持簡單，使用基本的客戶端和伺服器通信模型。

4.2.1 在哪裡設置限速器？

直觀地說，可以在客戶端或伺服器端實施限速器。

• 客戶端

一般來說客戶端是實施速率限制的不可靠的，因為客戶端請求很容易被惡意行為者偽造。此外，我們可能無法控制客戶端的實施。

• 伺服器端

假設我們的API允許每秒發出2個請求，而客戶端在一秒鐘內向伺服器發送了3個請求。前兩個請求被路由到API伺服器。但是，限速器中間件會對第三個請求進行節流，並返回HTTP狀態代碼 429。HTTP429響應狀態代碼表示用戶發送的請求過多。

雲微服務已廣為流行，速率限制通常在API網關的組件中實現。API網關是一種完全托管的服務，支持速率限制、SSL終止、身份驗證、IP白名單、靜態內容服務等。目前，我們只需知道API網關是支持速率限制的中間件。

速率限制器應該在哪裡實施，是在伺服器端還是在網關中？這個問題沒有絕對的答案。這取決於貴公司當前的技術堆棧、工程資源、優先順序、目標等。以下是幾條一般指導原則：

評估當前的技術堆棧，如編程語言、緩存服務等。確保您當前的編程語言能夠有效地在伺服器端實施速率限制。

確定適合您業務需求的速率限制演算法。在伺服器端實施一切時，您可以完全控制演算法。但是，如果使用第三方網關，您的選擇可能會受到限制。

• 如果您已經使用了微服務架構，併在設計中加入了API網關來執行身份驗證、IP白名單等功能，您可以在API網關中添加速率限制器。

• 創建自己的速率限制服務需要時間。如果沒有足夠的工程資源來實施速率限制器，商業API網關是更好的選擇。

參考資料

• 軟體測試精品書籍文檔下載持續更新 https://github.com/china-testing/python-testing-examples 請點贊，謝謝！
• 本文涉及的python測試開發庫 謝謝點贊！ https://github.com/china-testing/python_cn_resouce
• python精品書籍下載 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
• Linux精品書籍下載 https://www.cnblogs.com/testing-/p/17438558.html
• https://docs.platformio.org/en/latest
• 限制速率的策略和技術：https://cloud.google.com/solutions/rate-limiting-strategies-techniques
• Twitter 使用率限制：https://developer.twitter.com/en/docs/basics/rate-limits
• 谷歌文檔使用限制：https://developers.google.com/docs/api/limits
• IBM 微服務：https://www.ibm.com/cloud/learn/microservices
• 節流 API 請求以提高吞吐量：https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html
• Stripe 速率限制器：https://stripe.com/blog/rate-limiters
• Shopify REST 管理 API 速率限制：https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits
• 利用 Redis 排序集更好地限制速率：https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
• 系統設計--速率限制器和數據建模：https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250
• 我們如何建立能夠擴展到數百萬域的速率限制：https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
• Redis 網站：https://redis.io/
• Lyft 速率限制：https://github.com/lyft/ratelimit
• 利用速率限制器擴展 API：https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter
• 什麼是邊緣計算：https://www.cloudflare.com/learning/serverless/glossary/what-is-edge-computing/
• 使用 Iptables 對請求進行速率限制：https://blog.programster.org/rate-limit-requests-with-iptables
• OSI 模型：https://en.wikipedia.org/wiki/OSI_model#Layer_architecture

4.2.2 限速演算法

限速可以使用不同的演算法來實現，每種演算法都有明顯的優缺點。儘管本章的重點不是演算法，但從高層次瞭解這些演算法有助於選擇合適的演算法或演算法組合，以適應我們的使用情況。以下是常用演算法的列表：

• 令牌桶（Token bucket）
• 泄漏桶（Leaking bucket）
• 固定視窗計數器（Fixed window counter）
• 滑動視窗日誌（Sliding window log）
• 滑動視窗計數器（Sliding window counter）

4.2.2.1 令牌桶演算法

令牌桶演算法廣泛用於限速。它簡單易懂，常用於互聯網公司。亞馬遜和都使用這種演算法。

令牌桶演算法的工作原理如下：

• 令牌桶是一個具有預定容量的容器。令牌以預設的速率定期放入令牌桶。一旦桶滿，就不再添加令牌。如圖所示，令牌桶的容量為4，加油員每秒向桶中投入2枚令牌。一旦桶滿，多餘的代幣就會溢出。

• 每個請求消耗一個代幣。當請求到達時，我們會檢查桶中是否有足夠的代幣。
  • 如果有足夠的令牌，我們會為每個請求取出令牌，然後請求通過。
  • 如果沒有足夠的令牌，請求就會被放棄。

令牌桶演算法需要兩個參數：

• 令牌桶大小：令牌桶中允許的最大令牌數量

• 填充率：每秒放入代幣桶的代幣數量

我們需要多少代幣桶？這取決於限速規則。下麵是幾個例子。

• 通常需要為不同的API端點設置不同的桶。例如，如果允許用戶每秒發表1篇文章，每天添加150個好友，每秒喜歡5篇文章，那麼每個用戶需要3個桶。
• 如果我們需要根據IP地址來限制請求，那麼每個IP地址都需要一個桶。
• 如果系統每秒最多允許 10,000 個請求，那麼所有請求共用一個全局桶是合理的。

優點

• 演算法易於實現。
• 記憶體效率高。
• 代幣桶允許短時間內的突發流量。只要還有代幣，請求就可以通過。

缺點

• 演算法中的兩個參數是代幣桶大小和代幣填充率。然而，對它們進行適當調整可能具有挑戰性。

4.2.2.2 漏桶演算法

泄漏桶演算法與令牌桶類似，只是以固定速率處理請求。它通常使用先進先出隊列（FIFO）來實現。該演算法的工作原理如下：

• 當請求到達時，系統會檢查隊列是否已滿。如果隊列未滿，則將請求添加到隊列中。
• 否則，請求將被丟棄。
• 從隊列中取出請求，並定期進行處理。

泄漏桶演算法需要以下兩個參數：

• 桶大小：等於隊列大小。隊列容納以固定速率處理的請求。

• 流出率：它定義了以固定速率（通常以秒為單位）處理的請求數量。

電子商務公司Shopify使用泄漏桶來限速。

優點

-由於隊列大小有限，因此記憶體效率高。
-請求以固定速率處理，因此適用於需要穩定流出速率的用例。

缺點

-突發流量會使隊列中充滿舊請求，如果不及時處理，最近的請求就會受到速率限制。
-演算法中有兩個參數。演算法中有兩個參數，可能不容易正確調整。

4.2.2.3 固定視窗計數器演算法

固定視窗計數器演算法的工作原理如下：

• 將時間線劃分為固定大小的時間視窗，併為每個視窗分配一個計數器。

• 每次請求都會使計數器遞增1。

• 一旦計數器達到預定義的閾值，新的請求就會被放棄，直到新的時間視窗開始。

下圖中，時間單位為1秒，系統每秒最多允許3個請求。在每秒鐘的視窗中，如果收到的請求超過3個，系統就會丟棄多餘的請求。

這種演算法的一個主要問題是，時間視窗邊緣的突發流量可能會導致超過允許配額的請求通過。請考慮以下情況：

下圖，系統每分鐘最多允許5個請求，可用配額在人性化的整數分鐘重置。如圖所示，2:00:00至2:01:00之間有5個請求，2:01:00 至 2:02:00之間又有5個請求。在2:00:30和2:01:30之間的一分鐘視窗中，有10個請求通過。這是允許請求數的兩倍。

優點

-節省記憶體。
-易於理解。
-在單位時間視窗結束時重置可用配額，適合某些使用情況。

缺點

• 視窗邊緣的尖峰流量可能導致超過允許配額的請求通過。

4.2.2.4 滑動視窗日誌演算法

如前所述，固定視窗計數器演算法有一個主要問題：它允許更多請求在視窗邊緣通過。滑動視窗日誌演算法解決了這個問題。其工作原理如下：

• 該演算法跟蹤請求時間戳。時間戳數據通常保存在緩存中，如Redis的排序集。
• 當有新請求時，刪除所有過期的時間戳。過時的時間戳是指比當前時間視窗開始時間更早的時間戳。
• 將新請求的時間戳添加到日誌中。
  -如果日誌大小與允許計數相同或更小，則接受請求。否則，請求將被拒絕。

在本例中，速率限制器允許每分鐘2個請求。通常，Linux時間戳會存儲在日誌中。不過，為了提高可讀性，我們在示例中使用了人類可讀的時間表示法。

• 當新請求在 1:00:01 到達時，日誌為空。因此，該請求是允許的。
• 新請求在 1:00:30 到達時，時間戳 1:00:30 將被插入日誌。插入後，日誌大小為 2，不大於允許計數。因此，該請求是允許的。
• 新請求在 1:00:50 到達，時間戳被插入日誌。插入後，日誌大小為 3，大於允許的 2。因此，即使時間戳仍保留在日誌中，該請求也會被拒絕。
• 一個新請求在 1:01:40 到達。1:00:40,1:01:40）範圍內的請求在最新時間範圍內，但在 1:00:40 之前發送的請求已經過時。兩個過時的時間戳 1:00:01 和 1:00:30 將從日誌中刪除。刪除操作後，日誌大小變為 2，因此請求被接受。

優點

• 該演算法實現的速率限制非常精確。在任何滾動視窗中，請求都不會超過速率限制。

缺點

• 該演算法消耗大量記憶體，因為即使請求被拒絕，其時間戳仍可能存儲在記憶體中。

4.2.2.5 滑動視窗計數器演算法

滑動視窗計數器演算法是一種混合方法，它結合了固定視窗計數器和滑動視窗日誌。該演算法可以通過兩種不同的方法實現。我們將在本節中解釋其中一種實現方法，併在本節末尾提供另一種實現方法的參考。下圖展示了該演算法的工作原理。

假設速率限制器每分鐘最多允許7個請求，前一分鐘有5個請求，當前一分鐘有3個請求。對於到達當前分鐘 30% 位置的新請求，滾動視窗中的請求數按以下公式計算：

• 當前視窗中的請求數 + 上一視窗中的請求數 * 滾動視窗與上一視窗的重疊百分比
• 根據這一公式，我們得到 3 + 5 * 0.7% = 6.5 個請求。根據使用情況，該數字可以向上或向下舍入。在我們的例子中，四捨五入為6。

由於速率限制器每分鐘最多允許7個請求，因此當前請求可以通過。不過，再收到一個請求後就會達到限制。

優點

• 由於速率基於前一個視窗的平均速率，因此可以平滑流量峰值。
• 節省記憶體。

缺點

• 只適用於不太嚴格的回看視窗。它是實際速率的近似值，因為它假定前一個視窗中的請求是均勻分佈的。不過，這個問題可能沒有想象中那麼嚴重。根據 Cloudflare 的實驗，在 4 億個請求中，只有 0.003% 的請求被錯誤地允許或限制了速率。

4.2.3 高層架構

我們需要一個計數器來跟蹤來自同一用戶、IP 地址等的請求數量。如果計數器大於限制，請求就會被禁止。

我們應該在哪裡存儲計數器呢？由於磁碟訪問速度較慢，使用資料庫並不是一個好主意。選擇記憶體緩存是因為它速度快，而且支持基於時間的過期策略。例如Redis是實現速率限制的常用選擇。它是一種記憶體存儲，提供兩種命令：INCREXPIRE。

• INCR：將存儲的計數器加1。
• EXPIRE：為計數器設置超時。如果超時，計數器將自動刪除。

• 客戶端向限速中間件發送請求。
• 限速中間件從Redis中相應的桶中獲取計數器，並檢查是否達到限制。
  • 如果達到限制，則拒絕請求。
  • 如果未達到限制，則將請求發送到API伺服器。同時，系統會遞增計數器並將其保存回Redis。

4.3 第3步 - 深入設計

上圖中的高層設計沒有回答以下問題：

• 如何創建速率限制規則？規則存儲在哪裡？
• 如何處理速率受限的請求？

4.3.1 限速規則

Lyft將其速率限制組件開源在https://github.com/lyft/ratelimit。我們將深入瞭解該組件，並舉例說明一些速率限制規則：

domain: messaging

descriptors:

  - key: message_type

    Value: marketing

    rate_limit:

      unit: day

      requests_per_unit: 5

在上例中，系統配置為每天最多允許發送5條營銷信息。下麵是另一個示例：

domain: auth

descriptors:

  - key: auth_type

    Value: login

    rate_limit:

      unit: minute

      requests_per_unit: 5

這條規則規定，1 分鐘內客戶端登錄次數不得超過5次。規則一般寫入配置文件並保存在磁碟上。

4.3.2 限速

如果請求受到限速，API會向客戶端返回HTTP響應代碼429（請求過多）。根據使用情況，我們可能會將速率受限的請求排入隊列，以便稍後處理。例如，如果一些訂單因系統超載而受到速率限制，我們可能會保留這些訂單，以便稍後處理。

4.3.3 速率限制器標頭

客戶端如何知道自己是否被節流？客戶端又如何知道被節流前允許的剩餘請求數？答案就在HTTP響應頭中。速率限制器會向客戶端返回以下HTTP頭信息：

• X-Ratelimit-Remaining：視窗內允許的剩餘請求數。
• X-Ratelimit-Limit：表示客戶端在每個時間視窗內可進行的調用次數。
• X-Ratelimit-Retry-After： 在不被節流的情況下再次發出請求前需要等待的秒數。

當用戶發送的請求過多時，會向客戶端返回429請求過多錯誤和X-Ratelimit-Retry-After頭信息。

4.3.4 詳細設計

• 規則存儲在磁碟上。工作站經常從磁碟中提取規則並將其存儲到緩存中。
• 當客戶端向伺服器發送請求時，請求會首先發送到限速器中間件。
• 限速器中間件從緩存中載入規則。它從Redis緩存中獲取計數器和上次請求的時間戳。根據響應，速率限制器決定
• 如果請求不受速率限制，則將其轉發給API伺服器。
• 如果請求有速率限制，速率限制器會向客戶端返回429請求過多錯誤信息。同時，請求會被丟棄或轉發到隊列中。

4.3.5 分散式環境中的限速器

建立能在單伺服器環境中運行的速率限制器並不困難。但是，將系統擴展到支持多台伺服器和併發線程則是另一回事。這其中有兩個難題：

• 競賽條件
• 同步問題

如前所述，速率限制器的高級工作原理如下：

• 從Redis讀取計數器值。
• 檢查(counter + 1)是否超過閾值。
• 如果沒有，則將Redis中的計數器值遞增 1。

在高併發環境中可能會出現競賽條件。

假設Redis中的計數器值為3，如果兩個請求同時讀取計數器值，然後再寫回計數器值，那麼每個請求都會將計數器值遞增 1，然後寫回計數器值，而不會檢查其他線程。兩個請求（線程）都會認為自己的計數器值是 4。然而，正確的計數器值應該是5。

鎖是解決競賽條件最明顯的方法。但是，加鎖會大大降低系統運行速度。通常有兩種策略可以解決這個問題：Lua腳本 和 Redis中的排序集數據結構。

同步是分散式環境中需要考慮的另一個重要因素。要支持數百萬用戶，一臺速率限制器伺服器可能不足以處理流量。當使用多個速率限制器伺服器時，就需要同步。例如下圖的左側，客戶端1向速率限制器1發送請求，客戶端2向速率限制器2發送請求。由於網路層是無狀態的，客戶端可以向不同的速率限制器發送請求。如果不進行同步，速率限制器1就不包含任何有關客戶端2的數據。因此，速率限制器無法正常工作。

一種可能的解決方案是使用粘性會話，允許客戶端向同一個速率限制器發送流量。這種解決方案並不可取，因為它既不可擴展，也不靈活。更好的辦法是使用Redis等集中式數據存儲。

4.3.6 性能優化

性能優化是系統設計訪談中的一個常見話題。我們將從兩個方面進行改進。

首先，多數據中心設置對於速率限制器來說至關重要，因為對於遠離數據中心的用戶來說，延遲很高。大多數雲服務提供商都在全球建立了許多邊緣伺服器位置。例如，截至2020年5月20日，Cloudflare擁有194個地理分佈廣泛的邊緣伺服器。流量會自動路由到最近的邊緣伺服器，以減少延遲。

第二，使用最終一致性模型同步數據。

4.3.7 監控

設置速率限制器後，收集分析數據以檢查速率限制器是否有效非常重要。首先，我們要確保

• 速率限制演算法是否有效。
• 速率限制規則有效。

例如，如果速率限制規則過於嚴格，許多有效請求就會被丟棄。在這種情況下，我們希望稍微放寬規則。再比如，我們發現當流量突然增加（如閃購）時，我們的速率限制器就會失效。在這種情況下，我們可以更換演算法來支持突發流量。令牌桶就是一個很好的選擇。

4.4 步驟4 - 總結

在本章中，我們討論了不同的速率限制演算法及其優缺點。討論的演算法包括

• 令牌桶
• 泄漏桶
• 固定視窗
• 滑動視窗日誌
• 滑動視窗計數器

然後，我們討論了系統架構、分散式環境中的速率限制器、性能優化和監控。與任何系統設計面試問題類似，如果時間允許，你還可以提到一些額外的談話要點：

• 硬性與軟性速率限制。

  • 硬性：請求數不能超過閾值。
  • 軟：請求數可以在短時間內超過閾值。

• 不同級別的速率限制。在本章中，我們只討論了應用層（HTTP：第 7 層）的速率限制。也可以在其他層應用速率限制。例如，可以使用 Iptables （IP：第 3 層）按 IP 地址限制速率。

• 避免速率受限。以最佳實踐設計客戶端：

• 使用客戶端緩存，避免頻繁調用API。

• 瞭解限制，不要在短時間內發送過多請求。

• 包含捕獲異常或錯誤的代碼，以便客戶端可以從容地從異常中恢復。

• 為重試邏輯添加足夠的後退時間。