这是一个创建于 1699 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求：
这是昨天面试中遇到的一个问题，当用户 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 限制用户行为频率？
 |
1
RihcardLu 2020-03-28 19:42:52 +08:00
一种不太严密的算法，记录第一次请求次数和时间，每次访问后次数+1, 当达到 y 次时，和第一次请求时间做比较，小于 X，置 0
|
 |
2
yangbin9317 OP @RihcardLu #1 嗯，很简单但不能做到任意窗口内小于 y
|
 |
3
Livid MOD  1
目前 V2EX 的做法的大概思路：
now = int(time.time()) x = 60 y = 10 redis_key = str(now - (now % x)) count = client.incr(redis_key) if count >= y: |
|
4
Livid MOD |
 |
5
jugelizi 2020-03-28 19:51:41 +08:00
令牌桶算法
|
|
6
yangbin9317 OP @Livid #4 谢谢 Livid，但是文档中的方法不能避免例如五十九秒的时候请求 9 次，下一分钟一秒的时候再请求 9 次这种情况。
|
|
7
Livid MOD @yangbin9317 这种情况的问题是？单位时间内的总数（也可以理解为是服务器能够接受的请求次数）是限制住了的。
|
 |
8
Mohanson 2020-03-28 20:43:10 +08:00
|
 |
9
123444a 2020-03-28 20:43:35 +08:00 via Android
y 不一样做法不同，如果单用户 QPS 等于 10 万，2 万用户，那么你要几万台 codis 集群
|
|
10
123444a 2020-03-28 20:45:10 +08:00 via Android
高 QPS 分布式一般使用预分配 token
|
|
11
123444a 2020-03-28 20:46:05 +08:00 via Android
脱离需求谈设计等于耍流氓
|
 |
12
Lax 2020-03-28 21:02:40 +08:00 2
@yangbin9317
大部分生产环境用这种算法足够了。 在对齐的时间片上满足频率要求，不对齐的时间片上最多是频率限制的 2 倍，业务系统应该能满足这种波动。况且这是单个客户端的频率超出，对总体影响会比较小。 |
|
13
yangbin9317 OP @Lax 谢谢，但这是一个面试题，应该不能改需求，所以想搞清楚我的方法哪里还能优化
|
|
14
yangbin9317 OP @123444a 我错了，我一直在小公司工作没见过大场面
|
|
15
yangbin9317 OP @Livid 谢谢 Livid，这种方法在现实世界很好用，事实上我在日常开发中也是这么做的。
|
 |
16
gosansam 2020-03-28 21:18:03 +08:00
推荐滑动窗口
|
 |
17
xuanbg 2020-03-28 21:21:26 +08:00
咦，这不是简单生成一个 key 保存一下访问次数作为 value，并且设置一下 key 的过期时间就行了吗？如果没有 key 就写入一个 key，有 key 存在并且 value 超过次数就拦截掉，没有超过次数就对 value 进行累加。难道这样有问题？
|
 |
18
watzds 2020-03-28 21:22:38 +08:00 via Android
@yangbin9317 其实面试官没你想的这么多
|
 |
19
skadi 2020-03-28 21:53:46 +08:00
incr + ttl ?
|
 |
20
huntcool001 2020-03-28 21:59:53 +08:00
看一下我这个设计怎么样:
假设 60 秒内允许访问 10 次 那么 redis 里插入一个 USER_ID_LIST, 里面存 10 个当前的时间戳 每次用户进来,调用 RPOPLPUSH 这个命令,会在 list 右边插入当前时间,左边返回一个时间. 当左边返回的返回小于当前时间戳减去 60 秒的时候,说明已经触发机制. 这时候禁止用户操作. RPOPLPUSH 这个命令是 O(1)的 正常情况不用担心机器同步时间的问题,大部分情况也不会超过 1 秒吧. 除非是对精度要求很高,可以用 Lua 脚本返回服务端的时间. |
|
21
huntcool001 2020-03-28 22:02:37 +08:00
@xuanbg
有. 如果要求 60 秒内访问 10 次. 你 key 60 秒过期一次. 那么我可以在 59 秒的节点访问十次,60 秒节点的时候你过期 key 了,数量清零. 61 秒的时候我又可以访问 10 次. 也就是说短短两秒的时间,我访问了 20 次. 这种情况要考虑到. 最坏情况就是访问到要求上限的两倍次数. |
 |
22
clayyj1210 2020-03-28 22:11:38 +08:00
@huntcool001 这个方案很不错啊。
|
|
23
yangbin9317 OP @huntcool001 感觉这个和方案 2 类似，缺点也都是每个用户都要创建长度为 10 的列表，我前面忘了写这个缺点了。之所以想用数组是想避免重复创建链表节点
|
|
24
xuanbg 2020-03-28 22:32:03 +08:00
@huntcool001 你想多了吧，这个 key 怎么来的？你第一次访问的时候生成的！所以不可能 59 秒来 10 次，下一秒还能来 10 次。无论你什么时候开始第一次访问，接下来的 60 秒内你只能再来 9 次。
|
|
25
Lax 2020-03-28 22:36:42 +08:00
@huntcool001 这个方法很不错，SCRIPT LOAD 进 redis 来然后 evalsha 执行更好，是原子操作，而且都是利用 redis 所在服务器的时间戳，还不用担心调用方出错破坏数据。
|
 |
26
labulaka521 2020-03-28 23:09:50 +08:00
令牌桶或者漏桶 我使用 golang 实现的 https://labulaka521.top/posts/3462205/
|
|
27
huntcool001 2020-03-29 00:04:05 +08:00
@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 以下.. |
|
28
huntcool001 2020-03-29 00:06:34 +08:00
忘了说,上面的说放到 hash 里,然后把里面的值进行位运算的话,要 evalsha 或者写 lua 脚本.
|
|
29
123444a 2020-03-29 02:13:29 +08:00 via Android
@huntcool001 2 千万用户秒杀？淘宝跪着叫你爸爸
|
 |
30
tt67wq 2020-03-29 08:57:14 +08:00
搜下令牌桶吧 一搜一大堆
|
|
31
yangbin9317 OP @huntcool001 非常感谢，我忘了 ziplist 这回事了
|
 |
32
RedisMasterNode 2020-03-29 10:27:28 +08:00 via Android 1
建议了解一下 redis-cell，现成的东西不要造轮子了
|
 |
33
HelloAmadeus 2020-03-29 11:50:27 +08:00
自己想的一般都不会很好， 直接用令牌桶或漏桶算法吧
|
 |
34
blessingsi 2020-03-29 13:09:35 +08:00
@huntcool001 是不是我理解的不太对。bit 位这种方式，每毫秒一个 bit 的话，这个字符串岂不是要非常非常长
|
 |
35
brucefu 2020-03-29 14:55:34 +08:00
不需要都用 redis 啊，内存很贵的，有规模的公司肯定要存用户的每次登陆记录的。
redis 中存每个用户的一个是否被禁止访问 flag，请求来了先 check 是否被禁止访问。 可以访问，就交给另一个线程、进程、服务去处理这个限流操作，持久化登录记录，然后计算是否应该被禁止访问，需要禁止更新 flag |
|
36
huntcool001 2020-03-29 15:12:15 +08:00 via Android
@blessingsi 你可以从每天的零点开始算起，节省一些
|
 |
37
limitsy 2020-03-29 16:11:10 +08:00
@yangbin9317 实现一个简单的滑动窗口呢？比方说。以每 10 秒进行计数。然后统计最近 60s 的请求数。其实就是把计数的粒度划细。不过个人认为。“例如五十九秒的时候请求 9 次，下一分钟一秒的时候再请求 9 次这种情况”这种极端例子感觉并不重要。因为在下一分钟一秒请求 9 次。意味着下一分钟的 59 秒时间内他都无法再进行请求。
|
|
38
huntcool001 2020-03-29 20:01:21 +08:00
@blessingsi 想了一下,你说的对,是我理解错了..
|
 |
39
ericgui 2020-03-30 08:17:28 +08:00
不仅要限制总数，还要限制每个人
不然的话，你想啊，你限定 1 分钟可以请求 1 万次，结果一个人就请求了 9000 次 那还得了 |
|
42
xuanbg 2020-07-03 06:33:27 +08:00
@huntcool001
@aliez1995 你觉得过了 59 秒计时已经快结束了，可实际上 key 的 60 秒计时刚开始呢，下一秒你什么也干不了。key 是你访问接口的特征字符串，只有在你访问接口的时候才会在 Redis 中存在 60 秒。也就是说，只要 Redis 里面有 key，你就只能访问 10 次。要想访问第 11 次，得等这个 key 自己消失才行。但你一旦进行第 11 次访问，这个 key 就又自动出现了，所以你接下去也就只能是 10 次。 |
 |
43
TeslaLyon 2020-10-26 18:02:54 +08:00
@labulaka521 站点不维护了？
|
 |
44
Evilk 2020-12-10 09:51:04 +08:00
最近正在做类似的东西
某个接口,需要限制每个用户 1 分钟内,只能访问 10 次 打算使用 redis-cell 模块来做,应用层直接调用 redis 命令,直接交给 redis 自身来做 现成的轮子,方便,高效 |
Select Language