撸一个简单的 Rate Limiter 组件

…通过重造轮子理解 Rate Limiter 的原理及作用。

写过爬虫的人都知道，如果一个网站你抓取的频率高了，请求多半会失败 (不设防的小网站除外😃 )。

这是因为触发了被爬网站的防御措施。这种防御就是 流控(Rate Limiting)。

另外，一些开放平台为了保证自己服务的稳定性以及防止单个消费者的错误使用影响到其他消费者，也会对平台对外提供的开放 API 做一些限流。

比如我的公众号 API 就有下面这样的限制：

撸一个简单的 Rate Limiter 组件 — 一天调用超过2000次，后续调用就会失败

通常而言，流控都是做在服务提供方这边。即，你对外提供服务，为了保证服务可用性，你要对自己加一层流控。但有时消费者自己为了高效使用被分配的调用限额(比如上图中API一天只能调用2000次)，也会在自己这一方主动加入流控。

上面是流控的目的和作用，下面说说两种常见的实现方式。

固定时间窗口

假设你要为自己写的接口加入流控，要求 单个用户 每分钟 只能发来 5个请求。

我们很容易想到用下面这种结构来设计，即，按分钟累计每个用户的请求次数：

其中，用户的标识可以使用其 ID 或授权的TOKEN。如果你的系统也允许非登录人员访问，可以给非登录人员分配一个匿名的 TOKEN，无论如何，得存在辨别用户的机制。

分辨完用户，接下来就是在用户请求到来时，取出当前时间所在的分钟(0~59之间的值)，然后判断该分钟下的请求记数是否超过限定的值，超过就拒绝请求，否则给请求计数加 1 并正常处理请求。

考虑到如今的系统都是分布式的(多点部署)，为了保证流控状态的一致性(多个实例看到的计数是同步的)，对于上图中的数据结构，用 Redis 来处理非常适合，所以我们就用它做实现的参考吧。

使用 Redis 实现流控最主要的代码：

multi
incr [user]:[minute]
expire [user]:[minute] 59
exec

其中 [user] 和 [minute] 分别是用户的标识和分钟，比如 user-1:0 表示 user-1 这个用户在某个点0分时的数据。

通过 incr 命令增加请求记数，当整个命令完成后，判断返回的记数是否大于限制的数字即可。

expire 命令在这里的作用是，每个小时都有自己的 0~59 分钟，要确保下一小时的该分钟到来时，该分钟的数据已经被重置过。

另外，上面图中 user 和分钟是一对多的关系，而在具体实现时，我们把它铺展(flatten)开了，用 user+分钟 来代表用户在某一分钟下的数据，以简化实现。

你可能会想，每个用户都会在 Redis 中产生 60 个 key(0~59对应的key)，如果用户量很大，会不会增加 redis 的存储和清理负担？

。。可能会有负担吧，不过这里也提供一个优化方式。

可以对分钟取模，比如对 3 取模，这样一个用户只需要 3 个 key (即，0,1,2)：

m = minute % 3
multi
incr [user]:[m]
expire [user]:[m] 59
exec

以上的实现，用的是固定时间窗口算法(Fixed Window)，因为每个时间窗口(每1分钟)的时间范围是定死的，且和前后时间窗口没有交叉。但试想一下，上一分钟的后30秒和这一分钟的前30秒，其实也构成了一分钟，但它们却被分在了不同的时间窗口。

试想一下：

请求如果集中在上一分钟的后面几秒和这一分钟的前边几秒，系统在那几秒内请求会突然增加(系统负载会突然变高)。

比如一个系统本来一分钟只能撑住1万个请求，结果前1分钟只在第59秒时来了1万个请求，而后一分钟是在第1秒时来了1万个请求。

按固定时间窗口的算法，这些请求在各自的分钟内都是合法的，但这2万个请求其实是在短短的2秒内到来的，系统显然会扛不住。。。

怎么办？

滑动窗口算法

如果我们把用户每次请求发生的时间都记录在一个数组中，每次新请求到来时，先判断该数组中位于当前时间窗口内的元素有多少个，这个数量其实就是请求次数，基于它就能做限流判断了。

既要记录各个请求发生的时间，又要移除当前时间窗口之前的元素，Redis 中的 sorted set 就成了不二之选。

涉及的主要代码如下：

multi

# 移除时间窗口左侧的请求记录
zremrangebyscore [user] 0 [时间窗口开始时间]

# 查出时间窗口内总的请求次数
zcard [user]

# 将该次请求加到时间窗口内
zadd [user] [当前时间] [当前时间]

# 超过时间窗口后仍没有请求，则使数据过期
expire [user] <时间窗口长度>

exec

上面代码已经加了详细的注释。

外部拿到 zcard 的返回值后，如果其计数超过限制值，则拒绝请求。

这里还有个缺点，就是即使拒绝请求了，用户的该次请求还是被加入了当前时间窗口内，按理只有被处理过的请求才应该加进去。

一个解决办法是，使用 Lua 脚本，只有这样才能在一个事务中拿到 zcard 的值：

// 从参数中提取变量值
local user = KEYS[1] // 用户
local now = tonumber(ARGV[1]) // 当前请求时间
local window = tonumber(ARGV[2]) // 时间窗口长度
local limit = tonumber(ARGV[3]) // 限制的请求数

// 移除比 now - window 小的元素
local clearBefore = now - window
redis.call('ZREMRANGEBYSCORE', user, 0, clearBefore)

// 获取时间窗口内的请求数，即元素数量
local already_sent = redis.call('ZCARD', user)

if already_sent < limit then // 请求数小于限制请求数，记录该请求
redis.call('ZADD', user, now, now)
end

// 超过时间窗口长度没访问后，自动清理数据
redis.call('EXPIRE', user, window)

// 返回剩余可请求数据，如果返回值>=0，表示可以处理请求
return limit - already_sent

调用方式是：

eval [script] 1 [user] [当前时间(毫秒)] [时间窗口时长] [限制数量]

把 [script] 替换为上面的 Lua 脚本内容，其它变量也依次替换即可。

总结

通过上面2类 Rate Limiter 的实现，你不想自己编写试试吗。。

如果你感兴趣请留言说明，我用 Node.js 实现一款即时可用的。

文章参考：

Basic Rate Limiting^[1]。
Building a sliding window rate limiter with Redis^[2]。
Implementing a sliding log rate limiter with Redis and Golang^[3]。

参考资料

[1]

Basic Rate Limiting: https://redislabs.com/redis-best-practices/basic-rate-limiting

[2]

Building a sliding window rate limiter with Redis: https://engagor.github.io/blog/2017/05/02/sliding-window-rate-limiter-redis/

[3]

Implementing a sliding log rate limiter with Redis and Golang: https://levelup.gitconnected.com/implementing-a-sliding-log-rate-limiter-with-redis-and-golang-79db8a297b9e

– END –