速率限制定義了系統(tǒng)在指定時間段內(nèi)可以處理的最大請求數(shù)量。

Image.png

速率限制是一種策略，我們在工作中常常使用，它定義了系統(tǒng)在設(shè)定的時間框架內(nèi)可以處理的最大請求數(shù)量。

• 防御策略：這不僅僅是關(guān)于控制流量，而且還關(guān)于保護系統(tǒng)免受像DDoS攻擊和潛在濫用等威脅。此外，不受限制的請求有時會成為攻擊者利用漏洞的入口。
• 確保公平性：我可以確保系統(tǒng)為每個人都表現(xiàn)出色，確保每個用戶都能公平分享系統(tǒng)的資源。
• 分層訪問：對于高級用戶，可以有更高的請求限制，而對于免費用戶，則有一個標準限制。

在選擇算法時，我遇到了幾種不同的方法。

選擇合適的方法至關(guān)重要，它應(yīng)該與您的系統(tǒng)的特定需求以及您試圖解決的挑戰(zhàn)相一致。

1. 令牌桶

在速率限制方面，有一種方法我經(jīng)常使用，這是由于它的簡單性，對于本示例，我將在用戶級別進行設(shè)置。

“那么‘在用戶級別’到底是什么意思呢?” 實質(zhì)上，它表示速率限制是為每個單獨的用戶定制的，確保為他們定制了獨特的限制。想象一下，每個用戶都被分配一個容量為5個令牌的桶，每當用戶發(fā)出請求時，就會消耗1個令牌。在10分鐘的時間內(nèi)，系統(tǒng)被設(shè)計為能夠在每個桶中重新填充3個令牌。如果用戶的桶是空的，他們將無法再發(fā)出更多的請求，直到添加了一些令牌。以下是根據(jù)我的配置的詳細說明：

• 桶限制：5個令牌。
• 請求使用：1個令牌。
• 重新填充速率：10分鐘/3個令牌。

Image.png

(1) 優(yōu)點

我觀察到這種方法的一個關(guān)鍵優(yōu)勢是它相當節(jié)約資源。它在內(nèi)存上占用較少的空間，不會對CPU造成太大的負擔。

“您提到每10分鐘進行一次重新填充。如果有1000萬用戶，這不是很占資源嗎?” 與其為每個用戶不斷重新填充令牌，您可以采用一種“懶惰重新填充策略”。這意味著只有在用戶實際提交請求時才會更新令牌計數(shù)。

此外，該方法相對較容易實施。

它旨在支持突發(fā)行為。在閑置期間，令牌會積累到其最大限制，使用戶偶爾能夠快速連續(xù)發(fā)出多個請求。

(2) 缺點

調(diào)整參數(shù)可能需要一些權(quán)衡，因此確定理想的桶大小、重新填充速率和請求使用可能需要一些試驗。

盡管允許突發(fā)行為可能是有利的，但它也有其缺點。存在用戶在短時間內(nèi)發(fā)送大量請求的潛在風險。為了避免突發(fā)行為，我們可以應(yīng)用“漏桶”策略以實現(xiàn)更一致的工作流。

2. 漏桶

而令牌桶會快速處理每個請求，漏桶采用了不同的方法。對于這種方法，每個請求都有一個固定的處理時間。

想象一下漏桶的運作方式，就像一個隊列，如果隊列達到其容量，任何進入的請求都會被拒絕。

Image.png

“但為什么要給它起名字‘漏桶’呢?這里哪里有漏洞呢?” 想象一下，桶底部有一個小孔，可以讓水穩(wěn)定滴出。如果您比桶內(nèi)的水流得更快，會發(fā)生什么?確切地說，它會溢出，任何多余的水，就像我們的多余請求一樣，都會被丟棄。

(1) 它是如何運作的?

我們從一個最多可以容納10個單位的桶開始，每個請求需要1秒來處理。

• 時間0秒：桶是空的。
• 時間1秒：您向桶內(nèi)倒入8個單位，現(xiàn)在它有了8個單位。
• 時間2秒：1個單位泄漏出去，剩下7個單位。
• 時間4秒：還有6個單位，我們嘗試添加5個單位，但只有4個可以放下，導(dǎo)致1個溢出。現(xiàn)在桶滿了，有10個單位。

(2) 優(yōu)點

• 實施簡單，在許多方面，它甚至比令牌桶更簡單。
• 平滑突發(fā)行為，因此沒有突發(fā)，客戶可以急匆匆，但我們總是保持冷靜。

(3) 缺點

• 不適合處理突發(fā)情況，比如特殊活動或假期期間。
• 太多被丟棄的請求可能會成為問題

“但如果一個讀取請求只需要100毫秒，而我們的排水速度設(shè)置為1秒呢?” 請求仍然需要1秒處理。不過，可以調(diào)整設(shè)置：允許低于1秒的請求以其自然速度進行處理。然而，這樣做可能會促使用戶淹沒系統(tǒng)，從而抵消了漏桶的優(yōu)勢，也許在這種情況下有更適合的方法。

“如果我們有一個較慢的請求，比如1秒，但桶的排水速率只有200毫秒呢?” 桶會繼續(xù)釋放該請求，但這可能是我們的排水速率設(shè)置得太低的一個指標，所以要小心。

3. 固定窗口計數(shù)器

移向基于時間的算法，讓我們討論一下固定窗口計數(shù)器。雖然聽起來有所不同，但我們?nèi)匀豢梢允褂梦覀兪煜さ摹巴啊焙汀傲钆啤眮斫忉屵@個概念。

每小時(這個時間很關(guān)鍵)，客戶端都會得到一個空的請求桶。每次他們發(fā)出請求時，一個令牌就會被放入這個桶中。一旦桶滿了，就不允許再發(fā)出更多的請求。

(您可以想象客戶端從帶有令牌的桶開始，每次請求都會拿走一個令牌，沒有令牌意味著不能再發(fā)出更多請求。)

1*EdG-thC8YV5khwiWGo-X-Q.png

“但這與令牌桶方法有什么不同呢?” 我理解您的困惑，這兩種方法似乎都在隨時間分配令牌。固定窗口計數(shù)器在小時結(jié)束時不考慮以前的令牌使用情況，計數(shù)器在每個窗口結(jié)束時重置為0，與以前的活動無關(guān)。相反，令牌桶方法根據(jù)剩余的令牌重新填充：previous_tokens += refill_rate(但始終在其最大容量內(nèi))。

(11) 它是如何運作的?

我們正在使用一個1分鐘的窗口，并且我們的計數(shù)器的上限設(shè)置為10

• 時間0秒：計數(shù)器為0，一個客戶端發(fā)送了5個請求，將計數(shù)器提升到5。
• 時間10秒：又來了3個請求，將計數(shù)器推到8。
• 時間30秒：另外2個請求，我們的計數(shù)器達到了10，這就是這個窗口的限制。
• 時間40秒：一個客戶端嘗試另一個請求，但被拒絕了，限制已經(jīng)達到。
• 時間60秒：一個新的窗口開始了，我們的計數(shù)器重置為0。

(2) 優(yōu)點

• 這種方法易于實施和監(jiān)控。
• 一旦時間窗口重新開始，客戶端可以立刻發(fā)送一整組請求，允許突發(fā)行為。

(3) 缺點

• 存在一種突發(fā)請求在窗口邊界的機會。
• 用戶必須等待重置才能發(fā)出請求

例如，對于一個1小時的窗口和一個10個請求的限制，客戶端可以在7:59:59和8:00:00之間的過渡時刻發(fā)送20個請求

4. 滑動日志

將滑動日志視為固定窗口的更好版本。它旨在處理窗口邊緣的請求太多的問題。

與其堅持剛性的窗口，這個方法隨著時間的推移而滑動。

對于每個傳入的請求，我們的系統(tǒng)將迅速記下其時間戳。每個新的請求都會引發(fā)快速的回顧，以查看“過去N秒內(nèi)有多少請求。

1*rGCamyRYi0ovqjvSozC0yQ.png

(1) 它是如何運作的?

想象一下，我們將時間窗口設(shè)置為10秒，并將其限制為3個請求，這意味著在任何給定的10

秒內(nèi)只允許3個請求。

• 時間0秒：一個請求進來，我們做個標記 - [0]。
• 時間4秒、8秒：又來了兩個請求 - [0, 4, 8]。
• 時間9秒：另一個請求嘗試進來，但被拒絕，因為我們已經(jīng)達到了限制。
• 時間11秒：首先，我們?nèi)サ袅顺^10秒的舊條目，留下了[4, 8]。由于還有空間，這個請求被允許 - [4, 8, 11]。
• 時間15秒：兩個請求到達后，刪除過時的條目后，我們的列表看起來像[8, 11]。但我們只能接受其中的一個，更新日志為 - [8, 11, 15]。

這個過程很清楚：刪除舊日志，檢查新請求，更新日志。

(2) 優(yōu)點

• 有助于避免在窗口邊緣太多的請求
• 客戶端不需要等待完全重置，提供更均勻的請求流。

(3) 缺點

• 它需要更多的計算能力，因為我們必須為每個新請求清理舊條目。
• 由于需要跟蹤時間戳，所以存儲需求更大，如果我們的規(guī)模很大，這可能會成為一個問題。

5. 滑動窗口

對于滑動窗口，與滑動日志不同，我們略微簡化了事情。我們關(guān)注的是最后一個窗口中的請求數(shù)量。

所以，如果你發(fā)現(xiàn)自己處于當前窗口的75%，你會權(quán)衡請求。25%來自上一個窗口，其余來自當前窗口：

權(quán)重 = (100 - 75)% * 上一個窗口的請求 + 當前窗口的請求

現(xiàn)在，當一個新請求試圖加入這個過程時，你將這個權(quán)重加1(權(quán)重+1)。如果這個新的總數(shù)超過了我們設(shè)定的限制，我們必須拒絕這個請求。

1*js-77Ra-5xS-VVcVFlhdpw.png

它是如何運作的?

假設(shè)有一個每分鐘10個請求的窗口。

讓我們將這個過程分為兩個階段，窗口A為第一分鐘，窗口B為第二分鐘。

• 在0秒：我們收到一個初始請求，這意味著窗口A的計數(shù)器開始計時，現(xiàn)在為A_counter = 1。
• 在59秒：又來了7個請求，所以A_counter = 8。
• 在1分6秒：一個客戶端決定發(fā)送另外3個請求。記住我們從窗口A的計數(shù)器中得到的8?因為我們已經(jīng)進入窗口B，大約有10%消失，我們將使用90%的窗口A計數(shù)器值進行下一次計算。

current_weight = 90% * A_counter + 0 = 7.2

這允許大約再添加2個請求(因為7.2 + 2 < 10)。但第三個請求呢?

很遺憾，它被拒絕了，B_counter現(xiàn)在為2。

“但如果一個客戶在59秒時發(fā)送8個突發(fā)請求，然后在1分鐘6秒時偷偷再發(fā)送2個，他們?nèi)匀荒軌蛲ㄟ^，對嗎?” 正是如此，這就是與滑動日志相比的一個小權(quán)衡。我們選擇更少的計算工作和存儲空間來換取更高的準確性。使用方程式(1 - 百分比通過)* 上一個窗口 + 當前窗口，我們猜測上一個窗口的請求在時間上是均勻分布的，而不是一次性全部到來。這是一個戰(zhàn)略性的選擇，旨在尋求一種更高效的方法，即使這意味著在準確性上有所減少?？紤]到您的資源、如何管理突發(fā)流量、準確性以及您愿意處理多少復(fù)雜性，選擇適合您需求的正確速率限制器。