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

Image.png

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

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

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

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

1. 令牌桶

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

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

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

Image.png

(1) 優(yōu)點(diǎn)

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

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

此外，該方法相對較容易實(shí)施。

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

(2) 缺點(diǎn)

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

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

2. 漏桶

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

想象一下漏桶的運(yùn)作方式，就像一個(gè)隊(duì)列，如果隊(duì)列達(dá)到其容量，任何進(jìn)入的請求都會(huì)被拒絕。

Image.png

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

(1) 它是如何運(yùn)作的?

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

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

(2) 優(yōu)點(diǎn)

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

(3) 缺點(diǎn)

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

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

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

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

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

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

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

1*EdG-thC8YV5khwiWGo-X-Q.png

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

(11) 它是如何運(yùn)作的?

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

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

(2) 優(yōu)點(diǎn)

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

(3) 缺點(diǎn)

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

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

4. 滑動(dòng)日志

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

與其堅(jiān)持剛性的窗口，這個(gè)方法隨著時(shí)間的推移而滑動(dòng)。

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

1*rGCamyRYi0ovqjvSozC0yQ.png

(1) 它是如何運(yùn)作的?

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

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

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

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

(2) 優(yōu)點(diǎn)

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

(3) 缺點(diǎn)

• 它需要更多的計(jì)算能力，因?yàn)槲覀儽仨殲槊總€(gè)新請求清理舊條目。
• 由于需要跟蹤時(shí)間戳，所以存儲(chǔ)需求更大，如果我們的規(guī)模很大，這可能會(huì)成為一個(gè)問題。

5. 滑動(dòng)窗口

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

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

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

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

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

它是如何運(yùn)作的?

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

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

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

current_weight = 90% * A_counter + 0 = 7.2

這允許大約再添加2個(gè)請求(因?yàn)?.2 + 2 < 10)。但第三個(gè)請求呢?

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

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