在Rate Limiting with Redis這篇文章中，作者介紹了一個十分驚艷的速率限制算法，該算法基于 Redis 實(shí)現(xiàn)，能夠支持多個限制條件。

先看看原作者在工作中對速率限制的需求：

• 嚴(yán)格的速率限制，避免時間邊界（time boundary）問題
• 支持多個限制條件
• 支持手動阻塞
• 分布式，多個系統(tǒng)可以并發(fā)使用

舉例說明下時間邊界（time boundary）問題。假如我們想每分鐘限制20個請求，則有可能遇到這種情況，在頭一分鐘的最后一秒發(fā)生了20次請求，然后在接下來的一分鐘的頭一秒發(fā)生了20次請求。這樣，在短短的2秒內(nèi)總共發(fā)生了40次請求。這并不是嚴(yán)格的速率限制，我們需要的是在任何一個60秒的滑動窗口內(nèi)，請求個數(shù)都不超過20.

上述情況也引出了對多個速率限制條件的需求。舉例來說，不僅僅希望每分鐘限制20個請求，還希望每秒不超過1個請求，每30秒不超過15個請求等等。

那么原作者是如何利用 Redis 來解決上面的需求呢？原作者使用 Redis 的 list 數(shù)據(jù)類型來按序記錄每次請求的時刻。

舉例說明下算法的邏輯。假設(shè)前五次請求的時刻如下表所示：

并且，有兩個速率限制條件：每秒1個和每分鐘5個。

• 如果接下來的請求時刻小于12:34:29，由于它與12:34:28的時間間隔不超過1秒并且在這1秒內(nèi)已經(jīng)有了1次請求，所以觸犯了每秒1個這個限制條件
• 如果接下來的請求時刻小于12:34:35，由于它與12:33:35的時間間隔不超過1分鐘并且在這1分鐘內(nèi)已經(jīng)有了5次請求，所以觸犯了每分鐘5個這個限制條件
• 如果接下來的請求時刻是12:34:40，那么與最近一次請求相比時間已經(jīng)過了12秒，與五次前的請求相比時間已經(jīng)過了65秒，于是通過了這兩個速率限制

現(xiàn)在，我們把這次請求的時刻12:34:40追加到時刻表中。從上面兩個速率限制條件可知，只需要關(guān)心最近5次請求的時刻就可以了，所以可以把5次以前的請求時刻刪除掉。于是，請求時刻表變成了這樣：

如果想進(jìn)一步的理解該算法，可以參考原作者速率限制的Python實(shí)現(xiàn)。