V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
yangbin9317
V2EX  ›  Redis

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

  •  
  •   yangbin9317 · 2020-03-28 19:33:02 +08:00 · 10127 次点击
    这是一个创建于 1678 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求:

    这是昨天面试中遇到的一个问题,当用户 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 限制用户行为频率?

    44 条回复    2020-12-10 09:51:04 +08:00
    RihcardLu
        1
    RihcardLu  
       2020-03-28 19:42:52 +08:00
    一种不太严密的算法,记录第一次请求次数和时间,每次访问后次数+1, 当达到 y 次时,和第一次请求时间做比较,小于 X,置 0
    yangbin9317
        2
    yangbin9317  
    OP
       2020-03-28 19:44:25 +08:00
    @RihcardLu #1 嗯,很简单但不能做到任意窗口内小于 y
    Livid
        3
    Livid  
    MOD
       2020-03-28 19:45:34 +08:00   ❤️ 1
    目前 V2EX 的做法的大概思路:

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

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

    count = client.incr(redis_key)

    if count >= y:
    Livid
        4
    Livid  
    MOD
       2020-03-28 19:49:32 +08:00
    这个也基本上也就是 Redis 本身推荐的实现方式:

    https://redis.io/commands/incr
    jugelizi
        5
    jugelizi  
       2020-03-28 19:51:41 +08:00
    令牌桶算法
    yangbin9317
        6
    yangbin9317  
    OP
       2020-03-28 20:20:10 +08:00
    @Livid #4 谢谢 Livid,但是文档中的方法不能避免例如五十九秒的时候请求 9 次,下一分钟一秒的时候再请求 9 次这种情况。
    Livid
        7
    Livid  
    MOD
       2020-03-28 20:23:19 +08:00
    @yangbin9317 这种情况的问题是?单位时间内的总数(也可以理解为是服务器能够接受的请求次数)是限制住了的。
    Mohanson
        8
    Mohanson  
       2020-03-28 20:43:10 +08:00
    123444a
        9
    123444a  
       2020-03-28 20:43:35 +08:00 via Android
    y 不一样做法不同,如果单用户 QPS 等于 10 万,2 万用户,那么你要几万台 codis 集群
    123444a
        10
    123444a  
       2020-03-28 20:45:10 +08:00 via Android
    高 QPS 分布式一般使用预分配 token
    123444a
        11
    123444a  
       2020-03-28 20:46:05 +08:00 via Android
    脱离需求谈设计等于耍流氓
    Lax
        12
    Lax  
       2020-03-28 21:02:40 +08:00   ❤️ 2
    @yangbin9317
    大部分生产环境用这种算法足够了。
    在对齐的时间片上满足频率要求,不对齐的时间片上最多是频率限制的 2 倍,业务系统应该能满足这种波动。况且这是单个客户端的频率超出,对总体影响会比较小。
    yangbin9317
        13
    yangbin9317  
    OP
       2020-03-28 21:10:35 +08:00 via iPhone
    @Lax 谢谢,但这是一个面试题,应该不能改需求,所以想搞清楚我的方法哪里还能优化
    yangbin9317
        14
    yangbin9317  
    OP
       2020-03-28 21:11:10 +08:00 via iPhone
    @123444a 我错了,我一直在小公司工作没见过大场面
    yangbin9317
        15
    yangbin9317  
    OP
       2020-03-28 21:11:56 +08:00 via iPhone
    @Livid 谢谢 Livid,这种方法在现实世界很好用,事实上我在日常开发中也是这么做的。
    gosansam
        16
    gosansam  
       2020-03-28 21:18:03 +08:00
    推荐滑动窗口
    xuanbg
        17
    xuanbg  
       2020-03-28 21:21:26 +08:00
    咦,这不是简单生成一个 key 保存一下访问次数作为 value,并且设置一下 key 的过期时间就行了吗?如果没有 key 就写入一个 key,有 key 存在并且 value 超过次数就拦截掉,没有超过次数就对 value 进行累加。难道这样有问题?
    watzds
        18
    watzds  
       2020-03-28 21:22:38 +08:00 via Android
    @yangbin9317 其实面试官没你想的这么多
    skadi
        19
    skadi  
       2020-03-28 21:53:46 +08:00
    incr + ttl ?
    huntcool001
        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 脚本返回服务端的时间.
    huntcool001
        21
    huntcool001  
       2020-03-28 22:02:37 +08:00
    @xuanbg

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

    也就是说短短两秒的时间,我访问了 20 次. 这种情况要考虑到. 最坏情况就是访问到要求上限的两倍次数.
    clayyj1210
        22
    clayyj1210  
       2020-03-28 22:11:38 +08:00
    @huntcool001 这个方案很不错啊。
    yangbin9317
        23
    yangbin9317  
    OP
       2020-03-28 22:24:38 +08:00 via iPhone
    @huntcool001 感觉这个和方案 2 类似,缺点也都是每个用户都要创建长度为 10 的列表,我前面忘了写这个缺点了。之所以想用数组是想避免重复创建链表节点
    xuanbg
        24
    xuanbg  
       2020-03-28 22:32:03 +08:00
    @huntcool001 你想多了吧,这个 key 怎么来的?你第一次访问的时候生成的!所以不可能 59 秒来 10 次,下一秒还能来 10 次。无论你什么时候开始第一次访问,接下来的 60 秒内你只能再来 9 次。
    Lax
        25
    Lax  
       2020-03-28 22:36:42 +08:00
    @huntcool001 这个方法很不错,SCRIPT LOAD 进 redis 来然后 evalsha 执行更好,是原子操作,而且都是利用 redis 所在服务器的时间戳,还不用担心调用方出错破坏数据。
    labulaka521
        26
    labulaka521  
       2020-03-28 23:09:50 +08:00
    令牌桶或者漏桶 我使用 golang 实现的 https://labulaka521.top/posts/3462205/
    huntcool001
        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 以下..
    huntcool001
        28
    huntcool001  
       2020-03-29 00:06:34 +08:00
    忘了说,上面的说放到 hash 里,然后把里面的值进行位运算的话,要 evalsha 或者写 lua 脚本.
    123444a
        29
    123444a  
       2020-03-29 02:13:29 +08:00 via Android
    @huntcool001 2 千万用户秒杀?淘宝跪着叫你爸爸
    tt67wq
        30
    tt67wq  
       2020-03-29 08:57:14 +08:00
    搜下令牌桶吧 一搜一大堆
    yangbin9317
        31
    yangbin9317  
    OP
       2020-03-29 09:37:49 +08:00 via iPhone
    @huntcool001 非常感谢,我忘了 ziplist 这回事了
    RedisMasterNode
        32
    RedisMasterNode  
       2020-03-29 10:27:28 +08:00 via Android   ❤️ 1
    建议了解一下 redis-cell,现成的东西不要造轮子了
    HelloAmadeus
        33
    HelloAmadeus  
       2020-03-29 11:50:27 +08:00
    自己想的一般都不会很好, 直接用令牌桶或漏桶算法吧
    blessingsi
        34
    blessingsi  
       2020-03-29 13:09:35 +08:00
    @huntcool001 是不是我理解的不太对。bit 位这种方式,每毫秒一个 bit 的话,这个字符串岂不是要非常非常长
    brucefu
        35
    brucefu  
       2020-03-29 14:55:34 +08:00
    不需要都用 redis 啊,内存很贵的,有规模的公司肯定要存用户的每次登陆记录的。
    redis 中存每个用户的一个是否被禁止访问 flag,请求来了先 check 是否被禁止访问。
    可以访问,就交给另一个线程、进程、服务去处理这个限流操作,持久化登录记录,然后计算是否应该被禁止访问,需要禁止更新 flag
    huntcool001
        36
    huntcool001  
       2020-03-29 15:12:15 +08:00 via Android
    @blessingsi 你可以从每天的零点开始算起,节省一些
    limitsy
        37
    limitsy  
       2020-03-29 16:11:10 +08:00
    @yangbin9317 实现一个简单的滑动窗口呢?比方说。以每 10 秒进行计数。然后统计最近 60s 的请求数。其实就是把计数的粒度划细。不过个人认为。“例如五十九秒的时候请求 9 次,下一分钟一秒的时候再请求 9 次这种情况”这种极端例子感觉并不重要。因为在下一分钟一秒请求 9 次。意味着下一分钟的 59 秒时间内他都无法再进行请求。
    huntcool001
        38
    huntcool001  
       2020-03-29 20:01:21 +08:00
    @blessingsi 想了一下,你说的对,是我理解错了..
    ericgui
        39
    ericgui  
       2020-03-30 08:17:28 +08:00
    不仅要限制总数,还要限制每个人

    不然的话,你想啊,你限定 1 分钟可以请求 1 万次,结果一个人就请求了 9000 次
    那还得了
    123444a
        40
    123444a  
       2020-03-31 08:13:54 +08:00 via Android
    @ericgui 禁止用户访问的原文,含义就是限流到人
    aliez1995
        41
    aliez1995  
       2020-07-03 00:00:48 +08:00 via iPhone
    @xuanbg 先访问一次,等待到第 59 秒访问 9 次,下一秒就可以再来十次了
    xuanbg
        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 次。
    TeslaLyon
        43
    TeslaLyon  
       2020-10-26 18:02:54 +08:00
    @labulaka521 站点不维护了?
    Evilk
        44
    Evilk  
       2020-12-10 09:51:04 +08:00
    最近正在做类似的东西
    某个接口,需要限制每个用户 1 分钟内,只能访问 10 次
    打算使用 redis-cell 模块来做,应用层直接调用 redis 命令,直接交给 redis 自身来做
    现成的轮子,方便,高效
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1332 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 23:40 · PVG 07:40 · LAX 16:40 · JFK 19:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.