【系統設計】設計一個限流元件

限速器 (Rate Limiter) 相信大家都不會陌生，在網路系統中，限速器可以控制使用者端傳送流量的速度，比如 TCP, QUIC 等協定。而在 HTTP 的世界中， 限速器可以限制使用者端在一段時間內傳送請求的次數，如果超過設定的閾值，多餘的請求就會被丟棄。

生活中也有很多這樣的例子，比如

• 使用者一分鐘最多能發 5 條微博
• 使用者一天最多能投 3 次票
• 使用者一小時登入超過5次後，需要等待一段時間才能重試。

限速器（Rate Limiter）有很多好處，可以防止一定程度的 Dos 攻擊，也可以遮蔽掉一些網路爬蟲的請求，避免系統資源被耗盡，導致服務不可用。

設計要求

讓我們從一個面試開始吧！

面試官：你好，我想考察一下你的設計能力，如果讓你設計一個限速器 (Rate Limiter)，你會怎麼做？

面試者： 我們需要什麼樣的限速器？ 它是在使用者端限速還是在伺服器端限速？

面試官：這個問題很好，沒有固定要求，取決於你的設計。

面試者：我想了解一下限速的規則，我們是根據 IP、UserId，或者手機號碼進行限速嗎？

面試官：這個不固定，限速器應該是靈活的，要能很方便的支援不同的規則。

面試者：如果請求被限制了，需要提示給使用者嗎？

面試官：需要提示，要給使用者提供良好的體驗。

面試者：好吧，那系統的規模是多大的？是單機還是分散式場景？

面試官：我們是 TOC 的產品， 系統流量很大，並且是分散式的環境， 所以限速器要支援海量請求。

面試者：（小聲嘀咕）你這是造火箭呢？

我們總結一下限速器的設計要求：

• 低延遲，效能要好
• 需要適用於分散式場景。
• 使用者的請求受到限制時，需要提示具體的原因。
• 高容錯，如果限速器故障，不應該影響整個系統。

限速器應該放在哪裡？

從系統整體的角度上來看，我們的限速器應該放在哪裡？通常有三種選擇，如下

使用者端

是的，我們可以在使用者端設定限速器。但是有個問題是，我們都知道在 Web 前端做一些限制實際上是不安全的，同樣使用者端也是一樣的， 限速使用者端可以做，但是遠遠不夠。

伺服器端

在伺服器端設定限速器是很常見且安全的，如下

中介軟體

還有一種做法是，我們可以提供一個單獨的限速中介軟體，如下

假如限速器設定了每秒最大允許2個請求，那麼使用者端發出的多餘的請求就會被拒絕，並返回 HTTP 狀態碼 429, 表示使用者傳送了太多的請求。

實際上，很多閘道器都有限速的實現，包括認證、IP 白名單功能。

限速器應該放在哪裡？沒有固定的答案，它取決於公司的技術棧，系統規模。

限速演演算法

實際上，我們可以用演演算法實現限速器，下面是幾種經典的限速演演算法，每種演演算法都有自己的優點和缺點，瞭解這些可以幫助我們選擇更適合的演演算法。

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

令牌桶演演算法

令牌桶演演算法是實現限速使用很廣泛的演演算法，它很簡單也很好理解。

令牌桶是固定容量的容器。

一方面，按照一定的速率，向桶中新增令牌，桶裝滿後，多餘的令牌就會被丟棄。

如下圖，桶的容量為4，每次填充2個令牌。

另一方面，一個請求消耗一個令牌，如果桶中沒有令牌了，則拒絕請求。直到下個時間段，繼續向桶中填充新的令牌。

令牌桶演演算法有兩個重要的引數，分別是桶大小和填充率，另外有時候可能需要多個桶，比如多個 api 限速的規則是不一樣的。

令牌桶演演算法的優點是簡單易實現，並且允許短時間的流量並行。缺點是，在應對流量變化時，正確地調整桶大小和填充率，會比較有挑戰性。

漏桶演演算法

漏桶演演算法和令牌桶演演算法是類似的，同樣有一個固定容量的桶。

一方面，當一個請求進來時，會被填充到桶裡，如果桶滿了，就拒絕這個請求。

另一方面，想象桶下面有一個漏洞，桶裡的元素以固定的速率流出。

通常可以用先入先出的佇列實現，如下圖

漏桶演演算法有兩個引數，分別是桶大小和流出率，優點是使用佇列易實現，缺點是，面對突發流量時，雖然有的請求已經推到佇列中了，但是由於消費的速率是固定的，存在效率問題。

固定視窗計數器演演算法

固定視窗計數器演演算法的工作原理是，把時間劃分成固定大小的時間視窗，每個視窗分配一個計數器，接收到一個請求，計數器就加一，一旦計數器達到設定的閾值，新的請求就會被丟棄，直到新的時間視窗，新的計數器。

讓我們通過下面的例子，來看看它是如何工作的。一個時間視窗是1秒，每秒最多允許3個請求，超出的請求就會被丟棄。

不過這個演演算法有一個問題是，如果在時間視窗的邊緣出現突發流量時，可能會導致通過的請求數超過閾值，什麼意思呢？我們看看下面的情況

一個時間視窗是1分鐘，每分鐘最多允許5個請求。如果前一個時間視窗的後半段有5個請求，後一個時間視窗的前半段有5個請求，也就是 2:00:30 到 2:01:30 的一分鐘內，是可以通過10個請求的，這明顯超過了我們設定的閾值。

固定視窗計數器的優點是，簡單易於理解，缺點是，時間視窗的邊緣應對流量高峰時，可能會讓通過的請求數超過閾值。

滑動視窗紀錄檔演演算法

我們上面看到了，固定視窗計數器演演算法有一個問題，在視窗邊緣可能會突破限制，而滑動視窗紀錄檔演演算法可以解決這個問題。

它的工作原理是，假如設定1分鐘內最多允許2個請求，每個請求都需要記錄請求時間，比如儲存在 Redis 的 sorted sets 中，儲存之後還需要刪除掉過時的紀錄檔，過時紀錄檔是如何定義的？比如某次請求的時間是 1:01:36，那麼往前推1分鐘，1:00:36 之前的紀錄檔都算過時的，需要從集合中刪掉。同時，判斷集合中的數量是否大於閾值，如果大於2則丟棄請求，如果小於或等於2，則處理這個請求。

讓我們看看下面的例子

1. 在 1:00:01 來了一個請求，第一步，記錄請求時間到紀錄檔中，第二步，判斷是否有過時的紀錄檔, 也就是 0:59:01 之前的紀錄檔，明顯沒有，第三步判斷紀錄檔中的數量，沒有大於2，處理這次請求。
2. 在 1:00:30 來了一個請求，執行上面的三個步驟，最後處理這次請求。
3. 在 1:00:50 的新請求，沒有過時的紀錄檔，然後發現紀錄檔的數量為3，拒絕這次請求。
4. 在 1:01:40 的新請求，清除2條過時的紀錄檔，也就是 1:00:40 之前的紀錄檔，此時，紀錄檔中的數量為2，處理這次請求。

這個演演算法實現的限速非常準確，但是它可能會消耗較多的記憶體。

滑動視窗計數器演演算法

滑動視窗計數器可以說是固定視窗計數器的升級版，上面提到了，固定視窗計數器存在視窗邊緣可能會有超出限制的情況，如下

而滑動視窗把固定的視窗又分成了很多小的視窗單位，比如下圖，每個固定視窗的大小為1分鐘，又拆分成了6份，每次移動一個小的單位，保證總和不超過閾值。

這樣就可以避免上面的視窗邊緣超出限制的問題。

使用 Redis 實現高效計數器

限速器演演算法的思想其實很簡單，我們需要使用計數器記錄使用者的請求，如果超過閾值，服務這個請求，否則，拒絕這個請求。

一個很重要的問題是，我們應該把計數器放在哪裡？我們知道，磁碟速度比較慢，使用資料庫明顯是不太現實的方案，想要更快的話，可以使用記憶體快取，最常見的就是 Redis，是的，我們可以使用 Redis 實現高效計數器，如下

規則引擎

Lyft 是一個開源的限速元件，可以供我們參考，它通過 Yaml 組態檔實現靈活的限速規則，看下面的範例

這個設定表示系統每天只能傳送 5 條行銷資訊。

這個設定表示 1分鐘的登入次數不能超過 5 次。

可以看到，基於組態檔，宣告式的限速規則是非常靈活的，我們可以把組態檔儲存到磁碟中。

返回限速資訊

當請求超過限制時，限速器會拒絕掉其他的請求，這樣其實不夠，為了更好的使用者體驗，我們需要返回友好的錯誤資訊給使用者，並提示。

首先，限速器拒絕請求後，可以返回 HTTP 狀態碼 429，表示請求過多。

其次，我們可以返回更詳細的資訊，比如，剩餘請求次數、等待時間等。一種很常見的做法時，把這些資訊放到 Http 響應的 Header 中返回，如下

• X-Ratelimit-Remaining：表示剩餘次數
• X-Ratelimit-Limit：表示使用者端每個時間視窗可以進行多少次呼叫
• X-Ratelimit-Retry-After：表示等待多長時間可以進行重試

看起來不錯！讓我們看看現在的架構設計

首先，限速規則儲存在磁碟上，因為要經常存取，可以新增到快取中。當用戶端向伺服器傳送請求時，會先傳送到限速中介軟體。限速中介軟體從快取中拉取限速規則，同時把請求資料寫入到 Redis 的計數器，然後判斷是否超出限制。如果沒有超出限制，把請求轉發給我們的後端伺服器。如果超出了限制，第一種方案，丟棄多餘的請求，返回 429，第二種方案，把多餘的請求推播到訊息佇列中，後續再進行處理。使用哪種方案，取決於您的實際場景。

分散式環境

構建一個在單伺服器執行的限速器是很簡單的，但是在分散式環境中，支援多臺伺服器，那就完全是另外一回事了。

我們主要要考慮兩個問題：

• 並行問題
• 資料同步問題

並行問題，我們的限速器的工作原理是，當接收到新的請求時，從 Redis 中讀取計數器 counter，然後做加一的操作，在高並行場景中，可能存在多個執行緒讀到了舊的值，比如，兩個執行緒同時讀取到 counter 的值為3，然後都把 counter 改成了4，這樣是有問題的，其實最終應該是 5。

有朋友說，我們可以用鎖，但實際上，鎖的效率是不高的。解決這個問題通常有兩個方案，第一個是使用 Lua 指令碼，第二個是使用 Redis 的 sorted sets 資料結構，具體的細節本文不做過多介紹。

資料同步問題，在流量比較大的情況下，一個限速器是難以支撐的，我們需要多個限速器。由於 Web 層通常是無狀態的，使用者端的請求會隨機傳送給不同的限速器，如下

這種情況下，如果沒有資料同步，我們的限速器肯定是沒辦法正常工作的。

我們可以使用像 Redis 這樣的集中式資料儲存，如下

效能優化

當我們的系統是面向全球使用者時，為了讓各個地區的使用者都能有一個不錯的體驗，通常會在不同的地區設定多個資料中心。另外，現在很多雲服務商在全球各地都有邊緣伺服器，流量會自動路由到最近的邊緣伺服器，來減少網路的延遲。

當然，存在多個資料中心時，可能還要考慮到資料的最終一致性。

總結

在本文中，我們討論了不同的限速演演算法，以及它們有優缺點，演演算法包括：

• 令牌桶
• 漏桶
• 固定視窗計數器
• 滑動視窗紀錄檔
• 滑動視窗計數器

然後，我們討論了分散式環境中的系統架構，並行問題和資料同步問題，和靈活設定的限速規則，最後你會發現，實現一個限速器，其實沒有那麼難！

希望對您有用！

譯：等天黑

作者：Alex Xu

來源：《System Design Interview》

簡介: Alex Xu 是一位經驗豐富的軟體工程師, 曾在 Twitter, Apple 和 Oracle 任職，來自CS名校卡內基梅隆大學，熱衷於系統設計。