設計一個限速器

限速器 (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 層通常是無狀態的，客戶端的請求會隨機發送給不同的限速器，如下