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

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

難度級(jí)別：中等

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

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

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

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

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

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

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

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

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

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

功能要求：

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

非功能要求：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

我們的算法存在什么問(wèn)題？

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

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

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

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

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

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

8+2+2=12bytes

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

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

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

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

9、Sliding Window（滑動(dòng)窗口）算法

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

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

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

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

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

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

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

12KB?1million =12GB

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

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

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

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

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

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

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

1.6KB * 1百萬(wàn) ~= 1.6GB

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

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

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

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

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

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

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

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

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

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

如果我們結(jié)合以上兩種方案會(huì)怎么樣呢？

混合：一個(gè)正確的方法可能是同時(shí)進(jìn)行每IP和每用戶的限流，因?yàn)樗鼈冊(cè)趩为?dú)實(shí)施時(shí)都有弱點(diǎn)，然而，這將導(dǎo)致更多的緩存條目，每個(gè)條目需要更多的細(xì)節(jié)，因此需要更多的內(nèi)存和存儲(chǔ)空間。