关于用 Redis 限制用户行为频率的方法，麻烦 V 友帮看看

[yangbin9317]

需求：

这是昨天面试中遇到的一个问题，当用户 x 秒内请求 y 次，禁止用户访问

先写一些我自己想的方案，下面的windowStart为 x 秒之前的 timestamp，current为现在的 timestamp，threshold为请求次数限制。下列方法都需要设置和更新 key 过期时间，以免造成 key 泄漏。

方案 1:

用 Redis 的 List 数据结构记录用户访问的时间

当用户访问时 rpush 当前时间戳并删掉左侧 x 秒之前的时间戳，此时该列表的长度为 x 秒请求次数，注意此方法的timestamp需要用 Redis 的 Lua 脚本否则可能因为各机器时间不同出问题（例如某台机器时间为未来，则 ltrim 不到该条数据后面的正常时间戳）

伪代码：

redis.rpush(key, current);
redis.expire(key, current + y);
counter = 0;
while (redis.get(key, 0) < windowStart) {
	counter++;
}
redis.ltrim(0, counter);
if (redis.llen(key) > y) {
	doBanUser();
}

方案 1 的问题：

只需要最多存 y 条数据，但是这里用到了 List，Redis 中的 List 为双向链表，每个节点包含两个指针，在 64 位机器上占用 128bit，而实际有用的时间戳只要 64bit 。迭代链表时会更慢一些。

方案 2:

使用数组 ringbuffer 代替方案一的链表。

方案 2 的问题：

需要自己开发 Redis module，开发和运维成本较高。另外方案 1 和方案 2 中均存不方便重试和测试的问题。例如其他业务调自己服务但是自己服务超时，此时业务方重试，这种情况不应该算用户访问了两次。

方案 3:

使用 Redis 的 ZSet 数据结构

以用户请求的唯一 requestId 为 member，当前时间为 score，如果 requestId 已存在（ logn 复杂度)，不进行任何操作，如果不存在，则 ZADD，然后使用 ZRANGEBYSCORE 查看该时间段内请求数量。该方案同时需要使用 ZREMRANGEBYSCORE 来删除过老的元素，我认为可以每次或 N 次请求的时候删除，面试官说有更好的删除时机，但是我也没有问，这个问题就这么过去了。

想问问 V 友该方法应该如何删除，或者有没有更好的方法来用 Redis 限制用户行为频率？

[RihcardLu]

一种不太严密的算法，记录第一次请求次数和时间，每次访问后次数+1, 当达到 y 次时，和第一次请求时间做比较，小于 X，置 0

[yangbin9317]

@RihcardLu #1 嗯，很简单但不能做到任意窗口内小于 y

[Livid]

目前 V2EX 的做法的大概思路：

now = int(time.time())
x = 60
y = 10

redis_key = str(now - (now % x))

count = client.incr(redis_key)

if count >= y:

[Livid]

这个也基本上也就是 Redis 本身推荐的实现方式：

https://redis.io/commands/incr

[jugelizi]

令牌桶算法

[yangbin9317]

@Livid #4 谢谢 Livid，但是文档中的方法不能避免例如五十九秒的时候请求 9 次，下一分钟一秒的时候再请求 9 次这种情况。

[Livid]

@yangbin9317 这种情况的问题是？单位时间内的总数（也可以理解为是服务器能够接受的请求次数）是限制住了的。

[Mohanson]

令牌桶算法.

http://accu.cc/content/go/token_bucket/

[123444a]

y 不一样做法不同，如果单用户 QPS 等于 10 万，2 万用户，那么你要几万台 codis 集群

[123444a]

高 QPS 分布式一般使用预分配 token

[123444a]

脱离需求谈设计等于耍流氓

[Lax]

@yangbin9317
大部分生产环境用这种算法足够了。
在对齐的时间片上满足频率要求，不对齐的时间片上最多是频率限制的 2 倍，业务系统应该能满足这种波动。况且这是单个客户端的频率超出，对总体影响会比较小。

[yangbin9317]

@Lax 谢谢，但这是一个面试题，应该不能改需求，所以想搞清楚我的方法哪里还能优化

[yangbin9317]

@123444a 我错了，我一直在小公司工作没见过大场面

[yangbin9317]

@Livid 谢谢 Livid，这种方法在现实世界很好用，事实上我在日常开发中也是这么做的。

[gosansam]

推荐滑动窗口

[xuanbg]

咦，这不是简单生成一个 key 保存一下访问次数作为 value，并且设置一下 key 的过期时间就行了吗？如果没有 key 就写入一个 key，有 key 存在并且 value 超过次数就拦截掉，没有超过次数就对 value 进行累加。难道这样有问题？

[watzds]

@yangbin9317 其实面试官没你想的这么多

[skadi]

incr + ttl ?

[huntcool001]

看一下我这个设计怎么样:

假设 60 秒内允许访问 10 次

那么 redis 里插入一个 USER_ID_LIST, 里面存 10 个当前的时间戳

每次用户进来,调用 RPOPLPUSH 这个命令,会在 list 右边插入当前时间,左边返回一个时间.

当左边返回的返回小于当前时间戳减去 60 秒的时候,说明已经触发机制. 这时候禁止用户操作.


RPOPLPUSH 这个命令是 O(1)的

正常情况不用担心机器同步时间的问题,大部分情况也不会超过 1 秒吧. 除非是对精度要求很高,可以用 Lua 脚本返回服务端的时间.

[huntcool001]

@xuanbg

有. 如果要求 60 秒内访问 10 次. 你 key 60 秒过期一次. 那么我可以在 59 秒的节点访问十次,60 秒节点的时候你过期 key 了,数量清零. 61 秒的时候我又可以访问 10 次.

也就是说短短两秒的时间,我访问了 20 次. 这种情况要考虑到. 最坏情况就是访问到要求上限的两倍次数.

[clayyj1210]

@huntcool001 这个方案很不错啊。

[yangbin9317]

@huntcool001 感觉这个和方案 2 类似，缺点也都是每个用户都要创建长度为 10 的列表，我前面忘了写这个缺点了。之所以想用数组是想避免重复创建链表节点

[xuanbg]

@huntcool001 你想多了吧，这个 key 怎么来的？你第一次访问的时候生成的！所以不可能 59 秒来 10 次，下一秒还能来 10 次。无论你什么时候开始第一次访问，接下来的 60 秒内你只能再来 9 次。

[Lax]

@huntcool001 这个方法很不错，SCRIPT LOAD 进 redis 来然后 evalsha 执行更好，是原子操作，而且都是利用 redis 所在服务器的时间戳，还不用担心调用方出错破坏数据。

[labulaka521]

令牌桶或者漏桶 我使用 golang 实现的 https://labulaka521.top/posts/3462205/

[huntcool001]

@yangbin9317

我们可以来计算一下 Redis 内存占用. 比如说限制 1 分钟 10 次.

我们可以算一下内存如果用 Redis 链表储存,假设是电商秒杀.网站有一亿个用户, 网站一分钟内会有 20%的用户参加秒杀.也就是两千万用户,那么所占用的内存(64 位机器)是 2000W * (48+ 24) byte = 21.5GB (一个 Node 占用 3 个 byte,不是 2 个.因为除了前后指针还有一个存值)

可见这样还是很耗内存的. 不过实际上,对于这样很小的 list,redis 用的是 skiplist 储存的,占用内存空间小很多. list-max-ziplist-size 这个参数可以调多少个元素以下用 ziplist 储存. 那么会用类似数组的形式储存. 具体占用多少我也不知道,得实际测一下了.

还有需要注意的就是,ZREMRANGEBYSCORE 命令的是 O(log(N)+M) 的复杂度,ZADD 是 O(logN) .


不过我我想到一个更好的方法:

把当前的毫秒 Unix 时间戳减去 2020 年得到一个比较小的数 a 代表当前时间, 每个用户分配一个 redis 的 String. 用户进来一次,就用 SETBIT 命令把这个 String 的数 a 位置上的 bit 设置为 1. 然后用 BITCOUNT 统计 当前时间戳减去时间区间 到 当前时间戳内 的范围内的为 1 的数目,就是用户这个时间段内的访问次数. 那么一个用户就占用 8 个 byte 的时间戳 + 90byte 的 redis string 的占用空间=98byte.

两千万用户就是 1.8GB 的内存占用

(当然,这里假设用户一毫秒最多访问一次,如果还要精确,可以换成 nano second.)



其实还可以更省:

那就是把用户的时间戳都放到一个 hash 里 (或者按照用户 id 取模分成 n 个小的 hash)

这样的话,2000W 用户占用的空间大概是 15 个 byte * 2000W= 280MB

还想再缩的话,换成 32bit 的 redis,应该可以到 200MB 以下..

[huntcool001]

忘了说,上面的说放到 hash 里,然后把里面的值进行位运算的话,要 evalsha 或者写 lua 脚本.

[123444a]

@huntcool001 2 千万用户秒杀？淘宝跪着叫你爸爸

[tt67wq]

搜下令牌桶吧 一搜一大堆

[yangbin9317]

@huntcool001 非常感谢，我忘了 ziplist 这回事了

[RedisMasterNode]

建议了解一下 redis-cell，现成的东西不要造轮子了

[HelloAmadeus]

自己想的一般都不会很好， 直接用令牌桶或漏桶算法吧

[blessingsi]

@huntcool001 是不是我理解的不太对。bit 位这种方式，每毫秒一个 bit 的话，这个字符串岂不是要非常非常长

[brucefu]

不需要都用 redis 啊，内存很贵的，有规模的公司肯定要存用户的每次登陆记录的。
redis 中存每个用户的一个是否被禁止访问 flag，请求来了先 check 是否被禁止访问。
可以访问，就交给另一个线程、进程、服务去处理这个限流操作，持久化登录记录，然后计算是否应该被禁止访问，需要禁止更新 flag

[huntcool001]

@blessingsi 你可以从每天的零点开始算起，节省一些

[limitsy]

@yangbin9317 实现一个简单的滑动窗口呢？比方说。以每 10 秒进行计数。然后统计最近 60s 的请求数。其实就是把计数的粒度划细。不过个人认为。“例如五十九秒的时候请求 9 次，下一分钟一秒的时候再请求 9 次这种情况”这种极端例子感觉并不重要。因为在下一分钟一秒请求 9 次。意味着下一分钟的 59 秒时间内他都无法再进行请求。

[huntcool001]

@blessingsi 想了一下,你说的对,是我理解错了..

[ericgui]

不仅要限制总数，还要限制每个人

不然的话，你想啊，你限定 1 分钟可以请求 1 万次，结果一个人就请求了 9000 次
那还得了

[123444a]

@ericgui 禁止用户访问的原文，含义就是限流到人

[aliez1995]

@xuanbg 先访问一次，等待到第 59 秒访问 9 次，下一秒就可以再来十次了

[xuanbg]

@huntcool001
@aliez1995
你觉得过了 59 秒计时已经快结束了，可实际上 key 的 60 秒计时刚开始呢，下一秒你什么也干不了。key 是你访问接口的特征字符串，只有在你访问接口的时候才会在 Redis 中存在 60 秒。也就是说，只要 Redis 里面有 key，你就只能访问 10 次。要想访问第 11 次，得等这个 key 自己消失才行。但你一旦进行第 11 次访问，这个 key 就又自动出现了，所以你接下去也就只能是 10 次。

[TeslaLyon]

@labulaka521 站点不维护了？

[Evilk]

最近正在做类似的东西
某个接口,需要限制每个用户 1 分钟内,只能访问 10 次
打算使用 redis-cell 模块来做,应用层直接调用 redis 命令,直接交给 redis 自身来做
现成的轮子,方便,高效