設(shè)計(jì)一個(gè)限速器

限速器 (Rate Limiter) 相信大家都不會(huì)陌生，在網(wǎng)絡(luò)系統(tǒng)中，限速器可以控制客戶端發(fā)送流量的速度，比如 TCP, QUIC 等協(xié)議。而在 HTTP 的世界中， 限速器可以限制客戶端在一段時(shí)間內(nèi)發(fā)送請求的次數(shù)，如果超過設(shè)定的閾值，多余的請求就會(huì)被丟棄。

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

? 用戶一分鐘最多能發(fā) 5 條微博? 用戶一天最多能投 3 次票? 用戶一小時(shí)登錄超過5次后，需要等待一段時(shí)間才能重試。

限速器（Rate Limiter）有很多好處，可以防止一定程度的 Dos 攻擊，也可以屏蔽掉一些網(wǎng)絡(luò)爬蟲的請求，避免系統(tǒng)資源被耗盡，導(dǎo)致服務(wù)不可用。

讓我們從一個(gè)面試開始吧！

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

面試者：我們需要什么樣的限速器？它是在客戶端限速還是在服務(wù)端限速？

面試官：這個(gè)問題很好，沒有固定要求，取決于你的設(shè)計(jì)。

面試者：我想了解一下限速的規(guī)則，我們是根據(jù) IP、UserId，或者手機(jī)號(hào)碼進(jìn)行限速嗎？

面試官：這個(gè)不固定，限速器應(yīng)該是靈活的，要能很方便的支持不同的規(guī)則。

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

面試官：需要提示，要給用戶提供良好的體驗(yàn)。

面試者：好吧，那系統(tǒng)的規(guī)模是多大的？是單機(jī)還是分布式場景？

面試官：我們是 TOC 的產(chǎn)品， 系統(tǒng)流量很大，并且是分布式的環(huán)境， 所以限速器要支持海量請求。

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

我們總結(jié)一下限速器的設(shè)計(jì)要求：

? 低延遲，性能要好? 需要適用于分布式場景。? 用戶的請求受到限制時(shí)，需要提示具體的原因。? 高容錯(cuò)，如果限速器故障，不應(yīng)該影響整個(gè)系統(tǒng)。

從系統(tǒng)整體的角度上來看，我們的限速器應(yīng)該放在哪里？通常有三種選擇，如下

客戶端

是的，我們可以在客戶端設(shè)置限速器。但是有個(gè)問題是，我們都知道在 Web 前端做一些限制實(shí)際上是不安全的，同樣客戶端也是一樣的， 限速客戶端可以做，但是遠(yuǎn)遠(yuǎn)不夠。

服務(wù)端

在服務(wù)端設(shè)置限速器是很常見且安全的，如下

中間件

還有一種做法是，我們可以提供一個(gè)單獨(dú)的限速中間件，如下

假如限速器設(shè)置了每秒最大允許2個(gè)請求，那么客戶端發(fā)出的多余的請求就會(huì)被拒絕，并返回 HTTP 狀態(tài)碼 429, 表示用戶發(fā)送了太多的請求。

實(shí)際上，很多網(wǎng)關(guān)都有限速的實(shí)現(xiàn)，包括認(rèn)證、IP 白名單功能。

限速器應(yīng)該放在哪里？沒有固定的答案，它取決于公司的技術(shù)棧，系統(tǒng)規(guī)模。

實(shí)際上，我們可以用算法實(shí)現(xiàn)限速器，下面是幾種經(jīng)典的限速算法，每種算法都有自己的優(yōu)點(diǎn)和缺點(diǎn)，了解這些可以幫助我們選擇更適合的算法。

? 令牌桶 （Token bucket）? 漏桶（Leaking bucket）? 固定窗口計(jì)數(shù)器（Fixed window counter）? 滑動(dòng)窗口日志（Sliding window log）? 滑動(dòng)窗口計(jì)數(shù)器（Sliding window counter）

令牌桶算法是實(shí)現(xiàn)限速使用很廣泛的算法，它很簡單也很好理解。

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

一方面，按照一定的速率，向桶中添加令牌，桶裝滿后，多余的令牌就會(huì)被丟棄。

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

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

令牌桶算法有兩個(gè)重要的參數(shù)，分別是桶大小和填充率，另外有時(shí)候可能需要多個(gè)桶，比如多個(gè) api 限速的規(guī)則是不一樣的。

令牌桶算法的優(yōu)點(diǎn)是簡單易實(shí)現(xiàn)，并且允許短時(shí)間的流量并發(fā)。缺點(diǎn)是，在應(yīng)對(duì)流量變化時(shí)，正確地調(diào)整桶大小和填充率，會(huì)比較有挑戰(zhàn)性。

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

一方面，當(dāng)一個(gè)請求進(jìn)來時(shí)，會(huì)被填充到桶里，如果桶滿了，就拒絕這個(gè)請求。

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

通?？梢杂孟热胂瘸龅年?duì)列實(shí)現(xiàn)，如下圖

漏桶算法有兩個(gè)參數(shù)，分別是桶大小和流出率，優(yōu)點(diǎn)是使用隊(duì)列易實(shí)現(xiàn)，缺點(diǎn)是，面對(duì)突發(fā)流量時(shí)，雖然有的請求已經(jīng)推到隊(duì)列中了，但是由于消費(fèi)的速率是固定的，存在效率問題。

固定窗口計(jì)數(shù)器算法的工作原理是，把時(shí)間劃分成固定大小的時(shí)間窗口，每個(gè)窗口分配一個(gè)計(jì)數(shù)器，接收到一個(gè)請求，計(jì)數(shù)器就加一，一旦計(jì)數(shù)器達(dá)到設(shè)定的閾值，新的請求就會(huì)被丟棄，直到新的時(shí)間窗口，新的計(jì)數(shù)器。

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

不過這個(gè)算法有一個(gè)問題是，如果在時(shí)間窗口的邊緣出現(xiàn)突發(fā)流量時(shí)，可能會(huì)導(dǎo)致通過的請求數(shù)超過閾值，什么意思呢？我們看看下面的情況

一個(gè)時(shí)間窗口是1分鐘，每分鐘最多允許5個(gè)請求。如果前一個(gè)時(shí)間窗口的后半段有5個(gè)請求，后一個(gè)時(shí)間窗口的前半段有5個(gè)請求，也就是 2:00:30 到 2:01:30 的一分鐘內(nèi)，是可以通過10個(gè)請求的，這明顯超過了我們設(shè)置的閾值。

固定窗口計(jì)數(shù)器的優(yōu)點(diǎn)是，簡單易于理解，缺點(diǎn)是，時(shí)間窗口的邊緣應(yīng)對(duì)流量高峰時(shí)，可能會(huì)讓通過的請求數(shù)超過閾值。

我們上面看到了，固定窗口計(jì)數(shù)器算法有一個(gè)問題，在窗口邊緣可能會(huì)突破限制，而滑動(dòng)窗口日志算法可以解決這個(gè)問題。

它的工作原理是，假如設(shè)定1分鐘內(nèi)最多允許2個(gè)請求，每個(gè)請求都需要記錄請求時(shí)間，比如保存在 Redis 的 sorted sets 中，保存之后還需要?jiǎng)h除掉過時(shí)的日志，過時(shí)日志是如何定義的？比如某次請求的時(shí)間是 1:01:36，那么往前推1分鐘，1:00:36 之前的日志都算過時(shí)的，需要從集合中刪掉。同時(shí)，判斷集合中的數(shù)量是否大于閾值，如果大于2則丟棄請求，如果小于或等于2，則處理這個(gè)請求。

讓我們看看下面的例子

1.在 1:00:01 來了一個(gè)請求，第一步，記錄請求時(shí)間到日志中，第二步，判斷是否有過時(shí)的日志, 也就是 0:59:01 之前的日志，明顯沒有，第三步判斷日志中的數(shù)量，沒有大于2，處理這次請求。

2.在 1:00:30 來了一個(gè)請求，執(zhí)行上面的三個(gè)步驟，最后處理這次請求。

3.在 1:00:50 的新請求，沒有過時(shí)的日志，然后發(fā)現(xiàn)日志的數(shù)量為3，拒絕這次請求。

4.在 1:01:40 的新請求，清除2條過時(shí)的日志，也就是 1:00:40 之前的日志，此時(shí)，日志中的數(shù)量為2，處理這次請求。

這個(gè)算法實(shí)現(xiàn)的限速非常準(zhǔn)確，但是它可能會(huì)消耗較多的內(nèi)存。

滑動(dòng)窗口計(jì)數(shù)器可以說是固定窗口計(jì)數(shù)器的升級(jí)版，上面提到了，固定窗口計(jì)數(shù)器存在窗口邊緣可能會(huì)有超出限制的情況，如下

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

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

限速器算法的思想其實(shí)很簡單，我們需要使用計(jì)數(shù)器記錄用戶的請求，如果超過閾值，服務(wù)這個(gè)請求，否則，拒絕這個(gè)請求。

一個(gè)很重要的問題是，我們應(yīng)該把計(jì)數(shù)器放在哪里？我們知道，磁盤速度比較慢，使用數(shù)據(jù)庫明顯是不太現(xiàn)實(shí)的方案，想要更快的話，可以使用內(nèi)存緩存，最常見的就是 Redis，是的，我們可以使用 Redis 實(shí)現(xiàn)高效計(jì)數(shù)器，如下

Lyft 是一個(gè)開源的限速組件，可以供我們參考，它通過 Yaml 配置文件實(shí)現(xiàn)靈活的限速規(guī)則，看下面的示例

這個(gè)配置表示系統(tǒng)每天只能發(fā)送 5 條營銷信息。

這個(gè)配置表示 1分鐘的登錄次數(shù)不能超過 5 次。

可以看到，基于配置文件，聲明式的限速規(guī)則是非常靈活的，我們可以把配置文件保存到磁盤中。

當(dāng)請求超過限制時(shí)，限速器會(huì)拒絕掉其他的請求，這樣其實(shí)不夠，為了更好的用戶體驗(yàn)，我們需要返回友好的錯(cuò)誤信息給用戶，并提示。

首先，限速器拒絕請求后，可以返回 HTTP 狀態(tài)碼 429，表示請求過多。

其次，我們可以返回更詳細(xì)的信息，比如，剩余請求次數(shù)、等待時(shí)間等。一種很常見的做法時(shí)，把這些信息放到 Http 響應(yīng)的 Header 中返回，如下

? X-Ratelimit-Remaining：表示剩余次數(shù)?? X-Ratelimit-Limit：表示客戶端每個(gè)時(shí)間窗口可以進(jìn)行多少次調(diào)用?? X-Ratelimit-Retry-After：表示等待多長時(shí)間可以進(jìn)行重試

看起來不錯(cuò)！讓我們看看現(xiàn)在的架構(gòu)設(shè)計(jì)

首先，限速規(guī)則存儲(chǔ)在磁盤上，因?yàn)橐?jīng)常訪問，可以添加到緩存中。當(dāng)客戶端向服務(wù)器發(fā)送請求時(shí)，會(huì)先發(fā)送到限速中間件。限速中間件從緩存中拉取限速規(guī)則，同時(shí)把請求數(shù)據(jù)寫入到 Redis 的計(jì)數(shù)器，然后判斷是否超出限制。如果沒有超出限制，把請求轉(zhuǎn)發(fā)給我們的后端服務(wù)器。如果超出了限制，第一種方案，丟棄多余的請求，返回 429，第二種方案，把多余的請求推送到消息隊(duì)列中，后續(xù)再進(jìn)行處理。使用哪種方案，取決于您的實(shí)際場景。

構(gòu)建一個(gè)在單服務(wù)器運(yùn)行的限速器是很簡單的，但是在分布式環(huán)境中，支持多臺(tái)服務(wù)器，那就完全是另外一回事了。

我們主要要考慮兩個(gè)問題：

? 并發(fā)問題? 數(shù)據(jù)同步問題

并發(fā)問題，我們的限速器的工作原理是，當(dāng)接收到新的請求時(shí)，從 Redis 中讀取計(jì)數(shù)器 counter，然后做加一的操作，在高并發(fā)場景中，可能存在多個(gè)線程讀到了舊的值，比如，兩個(gè)線程同時(shí)讀取到 counter 的值為3，然后都把 counter 改成了4，這樣是有問題的，其實(shí)最終應(yīng)該是 5。

有朋友說，我們可以用鎖，但實(shí)際上，鎖的效率是不高的。解決這個(gè)問題通常有兩個(gè)方案，第一個(gè)是使用 Lua 腳本，第二個(gè)是使用 Redis 的 sorted sets 數(shù)據(jù)結(jié)構(gòu)，具體的細(xì)節(jié)本文不做過多介紹。

數(shù)據(jù)同步問題，在流量比較大的情況下，一個(gè)限速器是難以支撐的，我們需要多個(gè)限速器。由于 Web 層通常是無狀態(tài)的，客戶端的請求會(huì)隨機(jī)發(fā)送給不同的限速器，如下

這種情況下，如果沒有數(shù)據(jù)同步，我們的限速器肯定是沒辦法正常工作的。

我們可以使用像 Redis 這樣的集中式數(shù)據(jù)存儲(chǔ)，如下

當(dāng)我們的系統(tǒng)是面向全球用戶時(shí)，為了讓各個(gè)地區(qū)的用戶都能有一個(gè)不錯(cuò)的體驗(yàn)，通常會(huì)在不同的地區(qū)設(shè)置多個(gè)數(shù)據(jù)中心。另外，現(xiàn)在很多云服務(wù)商在全球各地都有邊緣服務(wù)器，流量會(huì)自動(dòng)路由到最近的邊緣服務(wù)器，來減少網(wǎng)絡(luò)的延遲。

當(dāng)然，存在多個(gè)數(shù)據(jù)中心時(shí)，可能還要考慮到數(shù)據(jù)的最終一致性。

在本文中，我們討論了不同的限速算法，以及它們有優(yōu)缺點(diǎn)，算法包括：

? 令牌桶? 漏桶? 固定窗口計(jì)數(shù)器? 滑動(dòng)窗口日志? 滑動(dòng)窗口計(jì)數(shù)器

然后，我們討論了分布式環(huán)境中的系統(tǒng)架構(gòu)，并發(fā)問題和數(shù)據(jù)同步問題，和靈活配置的限速規(guī)則，最后你會(huì)發(fā)現(xiàn)，實(shí)現(xiàn)一個(gè)限速器，其實(shí)沒有那么難！

希望對(duì)您有用！

? 譯：等天黑

? 作者：Alex Xu

? 來源：System Design Interview