優(yōu)秀系統(tǒng)設(shè)計(jì)背后的思考：API 速率限制服務(wù)系統(tǒng)

作者：MobotStone 2023-07-21 14:04:37

想象一下，我們有一個服務(wù)正在接收大量請求，但它每秒只能處理有限數(shù)量的請求。為了處理這個問題，我們需要某種節(jié)流或速率限制機(jī)制，只允許一定數(shù)量的請求，這樣我們的服務(wù)就能對所有請求進(jìn)行響應(yīng)。從高層次來看，速率限制器限制了一個實(shí)體（用戶、設(shè)備、IP等）在特定時間窗口內(nèi)可以執(zhí)行的事件數(shù)量。

API 速率限制器是一個用于控制應(yīng)用程序或服務(wù)對API請求的頻率的服務(wù)。速率限制通常用于控制資源的使用、防止濫用和維護(hù)服務(wù)的穩(wěn)定性。

類似的產(chǎn)品有：Express Rate Limit、Spring Boot Rate Limiter、Ratelimiter

難度級別：中等

1、什么是API速率限制服務(wù)？

一個用戶每秒只能發(fā)送一條消息。
用戶每天只能有三次信用卡交易失敗。
單個IP每天只能創(chuàng)建二十個賬號。

總的來說，速率限制器限制了發(fā)送者在特定時間窗口內(nèi)可以發(fā)出的請求數(shù)量，當(dāng)達(dá)到上限時，它會阻止請求。

2、為什么需要API速率限制？

速率限制的作用就好比是給你的服務(wù)穿上一件“防彈背心”，能夠抵御一些惡意攻擊，比如拒絕服務(wù)攻擊，暴力破解密碼或者信用卡信息等。這些攻擊往往像海量的HTTP/S請求砸過來，表面上看似乎是真實(shí)用戶在操作，實(shí)則可能是機(jī)器人在背后操控，因此這種攻擊更加難以發(fā)現(xiàn)，也更有可能導(dǎo)致你的服務(wù)、應(yīng)用或API被拖垮。

另外，速率限制還能幫助我們節(jié)省開支，降低維護(hù)網(wǎng)絡(luò)設(shè)施的費(fèi)用，避免垃圾郵件和網(wǎng)絡(luò)騷擾。以下是一些能從速率限制中獲益，使服務(wù)或API更穩(wěn)定可靠的情況：

控制不守規(guī)則的客戶端或腳本：有些用戶或者腳本可能會一股腦兒地發(fā)送大量請求，這無論是故意還是無意，都可能讓你的服務(wù)受不了。另外，有些用戶可能會頻繁地發(fā)送一些不那么重要的請求，我們得確保這種行為不會影響到重要的流量。比如，有的用戶可能頻繁地請求數(shù)據(jù)分析，我們不能讓這種行為妨礙到其他用戶的重要操作。
提升安全性：例如我們可以限制用戶在雙重認(rèn)證中嘗試密碼的次數(shù)，避免密碼被嘗試破解。
防止濫用和不合理的設(shè)計(jì)實(shí)踐：如果我們對API的使用沒有限制，開發(fā)者可能會懶散下來，比如反復(fù)請求同樣的信息，這樣不僅浪費(fèi)資源，也不符合好的開發(fā)習(xí)慣。
控制成本和資源使用：我們的服務(wù)通常是為正常使用情況設(shè)計(jì)的，比如一個用戶每分鐘發(fā)一篇帖子。如果沒有限制，一些計(jì)算機(jī)可能會一秒鐘就通過API推送成千上萬條信息。所以我們需要用速率限制來控制API的使用情況。
提高收入：某些服務(wù)可能會根據(jù)用戶的付費(fèi)級別來限制他們的操作，這樣就能根據(jù)限制來產(chǎn)生收入。例如，我們可以對所有的API設(shè)定一個默認(rèn)的使用上限，如果用戶想要更多使用權(quán)，就需要付費(fèi)升級。
避免流量突增：確保服務(wù)即使面臨大量請求，也能繼續(xù)正常為其他用戶提供服務(wù)。

3、系統(tǒng)需求和目標(biāo)

我們的流量控制器需要達(dá)到以下要求：

功能要求：

限制一個實(shí)體在一段時間內(nèi)可以向API發(fā)送的請求次數(shù)，例如每秒鐘15次請求。
API是通過集群來提供的，所以限流應(yīng)該在整個集群中進(jìn)行，跨服務(wù)器的請求都應(yīng)納入考慮。無論是在單臺服務(wù)器還是在多臺服務(wù)器上，只要超過了預(yù)設(shè)的閾值，用戶都應(yīng)該看到一個錯誤信息。

非功能要求：

系統(tǒng)是高可用。流量控制器需要隨時待命，因?yàn)樗俏覀兊姆?wù)對抗外部攻擊的重要工具。
我們的流量控制器不應(yīng)引入過多的延遲，以避免影響用戶體驗(yàn)。

4、怎樣進(jìn)行流量控制？

流量控制其實(shí)就是設(shè)定用戶可以多快、多頻繁地訪問API的規(guī)則。在一段時間內(nèi)，限制客戶對API的使用叫做"節(jié)流"。節(jié)流可以在應(yīng)用層面或者API層面進(jìn)行。一旦超出節(jié)流限制，服務(wù)器就會返回HTTP的"429 - 請求過多"狀態(tài)碼。

5、節(jié)流的類型有哪些？

以下是三種常見的節(jié)流類型，都被不同的服務(wù)使用過：

硬節(jié)流：API請求的次數(shù)絕對不能超過節(jié)流的限制。
軟節(jié)流：這種類型下，我們可以設(shè)定API請求的次數(shù)超過一定比例。例如，如果我們的流量限制是每分鐘100條消息，并且允許超過10%，那么我們的流量控制器每分鐘最多會允許110條消息。
彈性或動態(tài)節(jié)流：在彈性節(jié)流下，如果系統(tǒng)有剩余資源，那么請求次數(shù)就可以超過設(shè)定的閾值。例如，如果用戶每分鐘只能發(fā)100條消息，那么在系統(tǒng)有剩余資源的情況下，我們可以讓用戶每分鐘發(fā)送超過100條消息。

6、用于流量控制的都有哪些算法？

常用的流量控制算法有兩種：

固定窗口算法：在這種算法中，時間窗口是從時間單位的開始到時間單位的結(jié)束。比如說，對于一個分鐘，無論API請求在什么時候發(fā)出，我們都會看作是在0-60秒這個時間段內(nèi)。比如在下面的圖示中，0-1秒之間有兩條消息，1-2秒之間有三條消息。如果我們的流量限制是每秒鐘兩條消息，那么這個算法只會控制'm5'。

滑動窗口算法：在這個算法中，時間窗口從發(fā)出請求的那一刻開始，再加上窗口的長度。例如，如果在一秒的第300毫秒和第400毫秒各發(fā)送了一條消息，我們會把這兩條消息看作是從這一秒的第300毫秒開始到下一秒的第300毫秒之間的兩條消息。在上面的例子中，如果流量限制是每秒鐘兩條消息，我們就會控制'm3'和'm4'。

7、流量控制器的整體設(shè)計(jì)

流量控制器的職責(zé)是判斷哪些請求將由API服務(wù)器接收，哪些請求將被拒絕。當(dāng)新的請求來臨時，Web服務(wù)器首先向流量控制器詢問這個請求應(yīng)該被接收還是應(yīng)該被拒絕。如果請求沒有被拒絕，那么它就會被發(fā)送到API服務(wù)器進(jìn)行處理。

8、基本的系統(tǒng)設(shè)計(jì)和算法

我們以每個用戶的請求次數(shù)限制為例。在這種場景下，我們?yōu)槊總€用戶設(shè)置計(jì)數(shù)器，記錄用戶已經(jīng)發(fā)出了多少個請求，以及我們開始計(jì)數(shù)請求的時間戳。我們可以將這些信息存放在一個哈希表中，其中'key'是'UserID'，'value'是一個包含一個用于'Count'的整數(shù)和一個用于Epoch時間的整數(shù)的結(jié)構(gòu)：

假設(shè)我們的流量控制器允許每個用戶每分鐘發(fā)出三個請求，那么每當(dāng)有新請求進(jìn)來，我們的流量控制器將執(zhí)行以下步驟：

如果'UserID'在哈希表中不存在，將其插入，將'Count'設(shè)為1，將'StartTime'設(shè)為當(dāng)前時間（規(guī)范化為分鐘），然后允許該請求。
否則，找到'UserID'的記錄，如果 CurrentTime – StartTime >= 1分鐘，將'StartTime'設(shè)為當(dāng)前時間，'Count'設(shè)為1，并允許請求。
如果 CurrentTime - StartTime <= 1分鐘，且如果 'Count< 3'，增加計(jì)數(shù)并允許請求。如果 'Count>= 3'，拒絕請求。

我們的算法存在什么問題？

固定窗口算法：因?yàn)槲覀冊诿糠昼娊Y(jié)束時重置'StartTime'，這意味著可能每分鐘允許兩倍數(shù)量的請求。假設(shè)一個用戶在一分鐘的最后一秒發(fā)送了三個請求，然后她在下一分鐘的第一秒立即發(fā)送了三個更多的請求，這就導(dǎo)致在兩秒內(nèi)有6個請求。這個問題的解決方案是滑動窗口算法，我們稍后將討論。

原子性：在分布式環(huán)境中，“讀-然后-寫”的行為可能會產(chǎn)生競態(tài)條件。假設(shè)用戶當(dāng)前'Count'是"2"，并且她發(fā)出了兩個或者更多的請求。如果這兩個請求由兩個獨(dú)立的進(jìn)程處理，并且在任何一個進(jìn)程更新它之前同時讀取了Count，那么每個進(jìn)程都會認(rèn)為用戶還能有一個請求，并且她還沒有達(dá)到速率限制。

如果我們使用Redis來存儲我們的鍵值，解決原子性問題的一個解決方案是在讀取-更新操作期間使用Redis鎖。然而，這將以降低同一用戶的并發(fā)請求速度和增加另一層復(fù)雜性為代價(jià)。我們可以使用Memcached，但是它會有相似的問題。

如果我們使用簡單的哈希表，我們可以對每條記錄進(jìn)行鎖定以解決我們的原子性問題。

我們需要多少內(nèi)存來存儲所有的用戶數(shù)據(jù)呢？讓我們假設(shè)一個簡單的解決方案，即我們將所有的數(shù)據(jù)保存在一個哈希表中。

假設(shè)'UserID'需要8 bytes。我們也假設(shè)一個2 bytes的'Count'，可以計(jì)數(shù)到65k，對我們的使用場景來說已經(jīng)足夠了。盡管epoch時間需要4 bytes，我們可以選擇只存儲分鐘和秒部分，這可以用2 bytes來存儲。因此，我們需要總共12 bytes來存儲用戶的數(shù)據(jù)：

8+2+2=12bytes

假設(shè)我們的哈希表每條記錄需要額外20 bytes的開銷。如果我們需要在任何時候跟蹤一百萬用戶，我們需要的總內(nèi)存是32MB：

(12+20)bytes?1millinotallow=>32MB

如果我們假設(shè)需要一個4-byte的數(shù)來鎖定每個用戶的記錄以解決我們的原子性問題，我們將需要總共36MB的內(nèi)存。

這可以輕松地放在一臺服務(wù)器上；然而我們不希望將所有的流量都路由到一臺機(jī)器上。此外，如果我們假設(shè)一個速率限制為每秒10個請求，那么這將對我們的流量控制器產(chǎn)生1000萬QPS！這對一臺服務(wù)器來說太多了。實(shí)際上，我們可以假設(shè)我們將在一個分布式環(huán)境中使用類似Redis或Memcached這樣的解決方案。我們將所有的數(shù)據(jù)存儲在遠(yuǎn)程的Redis服務(wù)器中，所有的流量控制器服務(wù)器將在處理或節(jié)流任何請求之前讀取（和更新）這些服務(wù)器。

9、Sliding Window（滑動窗口）算法

如果我們能夠追蹤每個用戶的每個請求，我們就可以維護(hù)一個滑動窗口。我們可以在哈希表的'value'字段中的Redis Sorted Set（有序集合）中存儲每個請求的時間戳。

假設(shè)我們的速率限制器每分鐘每用戶允許3個請求，那么，每當(dāng)有新請求進(jìn)來，速率限制器將執(zhí)行以下步驟：

從Sorted Set中移除所有早于"CurrentTime（當(dāng)前時間） - 1分鐘"的時間戳。
計(jì)算Sorted Set中元素的總數(shù)。如果這個計(jì)數(shù)大于我們的閾值"3"，則拒絕請求。
在Sorted Set中插入當(dāng)前時間并接受請求。

我們使用滑動窗口，要存儲所有用戶的數(shù)據(jù)需要多少內(nèi)存呢？假設(shè)'UserID'需要8 byte。每個epoch時間將需要4byte。假設(shè)我們需要每小時500個請求的速率限制。假設(shè)哈希表有20 byte的開銷，Sorted Set有20 byte的開銷。最多，我們需要總共12KB來存儲一個用戶的數(shù)據(jù)：

8 + (4 + 20 (Sorted Set開銷)) * 500 + 20 (哈希表開銷) = 12KB

這里我們?yōu)槊總€元素預(yù)留了20 byte的開銷。在一個Sorted Set中，我們可以假設(shè)我們至少需要兩個指針來維護(hù)元素之間的順序 —— 一個指向前一個元素，一個指向后一個元素。在64位機(jī)器上，每個指針將占用8byte。所以我們將需要16byte用于指針。我們額外增加了一個word（4 byte）用于存儲其他開銷。

如果我們需要在任何時候跟蹤一百萬用戶，我們需要的總內(nèi)存將是12GB：

12KB?1million =12GB

與Fixed Window（固定窗口）相比，Sliding Window算法占用了大量的內(nèi)存；這會是一個可擴(kuò)展性問題。如果我們能夠結(jié)合使用上述兩種算法來優(yōu)化我們的內(nèi)存使用會怎樣呢？

10、帶計(jì)數(shù)器的滑動窗口

如果我們用多個固定的時間窗口來追蹤每個用戶的請求計(jì)數(shù)，例如，1/60的我們速率限制的時間窗口大小會怎樣呢？例如，如果我們有一個小時的速率限制，我們可以每分鐘計(jì)數(shù)一次，并在收到新請求時計(jì)算過去一個小時內(nèi)所有計(jì)數(shù)器的總和，以計(jì)算閾值。這樣可以減少我們的內(nèi)存占用。比如，我們限制每小時500次請求，每分鐘最多10次請求。這意味著，當(dāng)過去一小時內(nèi)帶時間戳的計(jì)數(shù)器之和超過請求閾值（500）時，用戶就超過了速率限制。此外，她每分鐘不能發(fā)送超過十個請求。這是一個合理而實(shí)用的考慮，因?yàn)闆]有真實(shí)的用戶會頻繁發(fā)送請求。即使他們這么做，他們也會因?yàn)槊糠昼娤拗贫紩刂枚吹街卦嚨某晒Α?/p>

我們可以在Redis哈希中存儲我們的計(jì)數(shù)器，因?yàn)樗鼮樯儆?00個鍵提供了極其高效的存儲。當(dāng)每個請求在哈希中增加一個計(jì)數(shù)器時，它也會設(shè)置哈希在一小時后過期。我們將每個'time'（時間）標(biāo)準(zhǔn)化到一分鐘。

我們使用帶計(jì)數(shù)器的滑動窗口，存儲所有用戶的數(shù)據(jù)需要多少內(nèi)存呢？假設(shè)'UserID'需要8byte。每個epoch時間將需要4byte，Counter（計(jì)數(shù)器）將需要2byte。假設(shè)我們需要每小時500個請求的速率限制。假設(shè)哈希表有20byte的開銷，Redis哈希有20byte的開銷。因?yàn)槲覀兠糠昼姸紩M(jìn)行計(jì)數(shù)，所以最多，每個用戶需要60個條目。我們需要總共1.6KB來存儲一個用戶的數(shù)據(jù)：

8 + (4 + 2 + 20 (Redis哈希開銷)) * 60 + 20 (哈希表開銷) = 1.6KB

如果我們需要在任何時候跟蹤一百萬用戶，我們需要的總內(nèi)存將是1.6GB：

1.6KB * 1百萬 ~= 1.6GB

所以，我們的'帶計(jì)數(shù)器的滑動窗口'算法比簡單的滑動窗口算法少用86%的內(nèi)存。

11、數(shù)據(jù)分片和緩存

對于用戶ID的數(shù)據(jù)，我們可以進(jìn)行分片處理以分散用戶數(shù)據(jù)。為了容錯和復(fù)制，我們應(yīng)該使用“一致性哈希”。如果我們希望對不同的API實(shí)施不同的限流標(biāo)準(zhǔn)，我們可以選擇每個用戶每個API進(jìn)行分片。以“URL短鏈接生成器”為例，我們可以對每個用戶或IP的createURL()和deleteURL() API設(shè)置不同的限流規(guī)則。

如果我們的API是分區(qū)的，一個實(shí)際的考慮是為每個API分片也設(shè)置一個相對較小的限流器。以我們的URL短鏈接生成器為例，我們希望限制每個用戶每小時不超過100個短URL的創(chuàng)建。假設(shè)我們使用基于哈希的分區(qū)方式對createURL() API進(jìn)行分區(qū)，我們可以設(shè)置每個分區(qū)的限流器，允許每個用戶每分鐘創(chuàng)建不超過3個短URL，另外每小時創(chuàng)建不超過100個短URL。

我們的系統(tǒng)可以從緩存近期活躍用戶中獲得巨大的好處。應(yīng)用服務(wù)器可以在擊中后端服務(wù)器之前快速檢查緩存是否有所需記錄。我們的限流器可以從Write-back緩存中獲得顯著的好處，只在緩存中更新所有計(jì)數(shù)器和時間戳。對永久存儲的寫入可以在固定的時間間隔進(jìn)行。這樣我們可以確保限流器對用戶請求增加的延遲最小。讀取操作始終先擊中緩存，這在用戶達(dá)到最大限制時非常有用，因?yàn)橄蘖髌鲗⒅蛔x取數(shù)據(jù)而不進(jìn)行任何更新。

對于API速率限制服務(wù)來說，最近最少使用（Least Recently Used，LRU）可能是一個合理的緩存驅(qū)逐策略。

12、我們應(yīng)該按照IP還是用戶進(jìn)行限流？

讓我們來討論一下使用這兩種方案的優(yōu)缺點(diǎn)：

IP：在此方案中，我們對每個IP的請求進(jìn)行限流；盡管在區(qū)分“好”與“壞”行為者方面并非最佳，但它仍然比完全沒有限流要好。基于IP的限流最大的問題在于，當(dāng)多個用戶共享一個公網(wǎng)IP時，如在網(wǎng)吧或使用相同網(wǎng)關(guān)的智能手機(jī)用戶。一個行為不當(dāng)?shù)挠脩艨赡軐?dǎo)致對其他用戶的限流。另一個問題可能出現(xiàn)在緩存IP限制時，因?yàn)榧词挂粋€計(jì)算機(jī)也有大量的IPv6地址可供黑客使用，讓服務(wù)器因跟蹤IPv6地址而耗盡內(nèi)存是輕而易舉的事！

用戶：限流可以在用戶認(rèn)證后對API進(jìn)行。一旦認(rèn)證成功，用戶將獲得一個令牌，用戶將在每次請求時傳遞該令牌。這將確保我們對具有有效認(rèn)證令牌的特定API進(jìn)行限流。但是，如果我們必須對登錄API本身進(jìn)行限流怎么辦？這種限流的弱點(diǎn)是，黑客可以通過輸入錯誤的憑證達(dá)到限流閾值來對用戶進(jìn)行拒絕服務(wù)攻擊；之后，實(shí)際的用戶將無法登錄。