基于 Redis 的速率限制算法

爱被打了一巴掌 2022-08-07 09:36 134阅读 0赞

在[Rate Limiting with Redis][]这篇文章中，作者介绍了一个十分惊艳的速率限制算法，该算法基于 Redis 实现，能够支持多个限制条件。

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

*  严格的速率限制，避免时间边界（time boundary）问题
 *  支持多个限制条件
 *  支持手动阻塞
 *  分布式，多个系统可以并发使用

举例说明下时间边界（time boundary）问题。假如我们想每分钟限制20个请求，则有可能遇到这种情况，在头一分钟的最后一秒发生了20次请求，然后在接下来的一分钟的头一秒发生了20次请求。这样，在短短的2秒内总共发生了40次请求。这并不是严格的速率限制，我们需要的是在任何一个60秒的滑动窗口内，请求个数都不超过20.

上述情况也引出了对多个速率限制条件的需求。举例来说，不仅仅希望每分钟限制20个请求，还希望每秒不超过1个请求，每30秒不超过15个请求等等。

那么原作者是如何利用 Redis 来解决上面的需求呢？原作者使用 Redis 的 list 数据类型来按序记录每次请求的时刻。

举例说明下算法的逻辑。假设前五次请求的时刻如下表所示：

![3479982-2061faddc9565006.png][]

并且，有两个速率限制条件：每秒1个和每分钟5个。

*  如果接下来的请求时刻小于12:34:29，由于它与12:34:28的时间间隔不超过1秒并且在这1秒内已经有了1次请求，所以触犯了每秒1个这个限制条件
 *  如果接下来的请求时刻小于12:34:35，由于它与12:33:35的时间间隔不超过1分钟并且在这1分钟内已经有了5次请求，所以触犯了每分钟5个这个限制条件
 *  如果接下来的请求时刻是12:34:40，那么与最近一次请求相比时间已经过了12秒，与五次前的请求相比时间已经过了65秒，于是通过了这两个速率限制

现在，我们把这次请求的时刻12:34:40追加到时刻表中。从上面两个速率限制条件可知，只需要关心最近5次请求的时刻就可以了，所以可以把5次以前的请求时刻删除掉。于是，请求时刻表变成了这样：

![3479982-1fe77957662011cf.png][]

如果想进一步的理解该算法，可以参考原作者[速率限制的Python实现][Python]。

[Rate Limiting with Redis]: https://link.jianshu.com?t=http://blog.domaintools.com/2013/04/rate-limiting-with-redis/
[3479982-2061faddc9565006.png]: /images/20220805/86d76ce71c8f44f7ab3a328b4c2abc59.png
[3479982-1fe77957662011cf.png]: /images/20220805/66f39c7581664c218c33bf77d0ae6622.png
[Python]: https://link.jianshu.com?t=https://github.com/DomainTools/rate-limit