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

使用 redis 如何维护一个动态的区间和?

  •  
  •   111qqz · 2022-03-17 10:31:06 +08:00 · 2738 次点击
    这是一个创建于 742 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求是这样: 有一个队列,队列中的元素是不断变化的,想知道这个队列中所有元素的和。

    队列元素的增加: 当一个请求到来时,就往队列中添加元素。 可能同时到来上百个请求

    队列元素的删除: 按照时间删除,当请求到来超过一定时间后,自动删除。

    说白了就是想维护一个时间窗口,并查询窗口中元素之和。

    我目前想过的两种做法:

    1. 利用 redis 的 key 过期时间进行。 但是 key 过期的时候,无法直接反应到 sum 上。 每次请求 sum 都要把队列中的元素累加一遍,可能不太合理?

    2. 队列中存储元素的时间戳,定时(比如 100ms )来根据元素的时间戳进行逐个删除,删除的同时维护区间和。 删除到第一个在时间窗口中的元素为止。 (队列从右边加入元素,从左边删除元素)

    第一次使用 redis ,想问问各位大佬这个操作要如何进行比较合理?

    26 条回复    2022-03-31 20:15:47 +08:00
    sunny352787
        1
    sunny352787  
       2022-03-17 10:35:36 +08:00
    你是想做...访问限流?
    111qqz
        2
    111qqz  
    OP
       2022-03-17 10:38:13 +08:00
    @sunny352787 #1 类似吧,在做一个智能算力的项目,会根据区间和的大小来动态分配算力。
    sunny352787
        3
    sunny352787  
       2022-03-17 10:42:36 +08:00   ❤️ 1
    @111qqz google 一下“redis 限流”,解决方案很多
    hidemyself
        4
    hidemyself  
       2022-03-17 10:45:59 +08:00   ❤️ 1
    sored set ,zremrangeByScore ?
    hidemyself
        5
    hidemyself  
       2022-03-17 10:46:27 +08:00
    @hidemyself sored->sorted
    edward1987
        6
    edward1987  
       2022-03-17 10:53:57 +08:00   ❤️ 1
    方案 2 挺好的
    111qqz
        7
    111qqz  
    OP
       2022-03-17 10:55:13 +08:00
    @hidemyself #4 感谢回复,用 sorted set 的话的确可以一下子把过期的元素全部删掉,但是 sum 的维护还是要把删掉的元素列表拿出来逐个进行,是吧?
    111qqz
        8
    111qqz  
    OP
       2022-03-17 10:58:57 +08:00
    @sunny352787 #3 感谢老哥提供的关键字,我去搜了下,看到了这个 https://segmentfault.com/a/1190000040570911 其中"计数器"这个方案和我想要的比较类似。 但是差别是,计数器只需要知道一个集合中元素的个数就可以了,我需要知道集合中元素之和。 这个好像要通过写 lua 脚本(?) 之类实现,听说会比较影响性能
    MoYi123
        9
    MoYi123  
       2022-03-17 11:00:33 +08:00   ❤️ 1
    就用方案 2 吧.

    看你的量比较大. 如果流量比较稳定, 可以不需要定时器, 只在查询和插入之前清空过期数据,
    不过这样也有可能某次删除了大量数据导致单次请求很慢的问题.
    删除的时候可以写个 lua, 性能好点.
    111qqz
        10
    111qqz  
    OP
       2022-03-17 11:15:02 +08:00
    @MoYi123 #9 @edward1987 感谢回复。 如果使用方案 2 的话,我这里用一个 list 是合理的吗? 不太了解 redis 的线程安全问题。 我这里是假定了队列中的元素是会按照时间戳严格单调排列,也就是更新的元素一定在旧的元素的右边。 这个假定是可以保证的嘛?
    godleon
        11
    godleon  
       2022-03-17 11:17:22 +08:00
    滑动窗口算法( Sliding Window Algorithm )
    sunny352787
        12
    sunny352787  
       2022-03-17 11:18:57 +08:00   ❤️ 1
    @111qqz redis 本身你可以认为是单线程处理所以不用考虑线程安全问题,使用 lua 的话其实比你用命令方式访问性能还高些,相当于打包处理,放心的用吧,就你的这个需求来看,用 lua 很合适
    xhinliang
        13
    xhinliang  
       2022-03-17 11:27:30 +08:00   ❤️ 1
    Sorted Set 吧。
    定期删除 zremrangebyscore
    获取元素之和 zrangebyscore 然后自己代码里加就行了
    111qqz
        14
    111qqz  
    OP
       2022-03-17 11:29:57 +08:00
    @sunny352787 #12 好的,感谢,我去研究研究😁
    111qqz
        15
    111qqz  
    OP
       2022-03-17 11:30:55 +08:00
    @xhinliang #13 感谢,我也看看这个方案
    111qqz
        16
    111qqz  
    OP
       2022-03-17 11:31:25 +08:00
    @godleon #11 感谢回复,虽然和我问的没什么关系😅
    111qqz
        18
    111qqz  
    OP
       2022-03-17 11:35:37 +08:00
    @rimutuyuan #17 感谢老哥授人以渔,我之后读一读
    edward1987
        19
    edward1987  
       2022-03-17 11:41:40 +08:00
    @111qqz #10 这个不能保证,因为时间戳是你程序生成的。 但是误差也就影响个几毫秒,对你业务没影响。
    111qqz
        20
    111qqz  
    OP
       2022-03-17 11:42:33 +08:00
    @edward1987 #19 好的,明白了。 那确实应该没有影响
    git00ll
        21
    git00ll  
       2022-03-17 14:37:37 +08:00   ❤️ 1
    第二种方式没问题,resilience4j 中就有与这种做法类似的做法
    111qqz
        22
    111qqz  
    OP
       2022-03-17 18:12:48 +08:00
    @git00ll #21 感谢解答
    moqimoqide
        23
    moqimoqide  
       2022-03-18 00:07:00 +08:00 via iPhone   ❤️ 1
    如果 redis 的版本大于 5 ,建议使用 流 这种数据结构。

    XADD 命令还提供了 MAXLEN 选项,让用户可以在添加新元素的同时删除旧元素,以此来限制流的长度:

    ​​​​​​​​​​XADD stream [MAXLEN len] id field value
    ricky077
        24
    ricky077  
       2022-03-18 00:53:53 +08:00
    刚好我们也有这样一个物联网项目,数据量挺大,需要查固定周期内的数据来求和,感谢楼上老哥些的方法
    111qqz
        25
    111qqz  
    OP
       2022-03-19 13:17:52 +08:00
    @moqimoqide #23 感谢,不过看了下和我的需要不太一样。 我窗口中元素个数其实并不会固定,在请求高峰期和低峰期会差非常多。
    111qqz
        26
    111qqz  
    OP
       2022-03-31 20:15:47 +08:00
    调研到了这个 https://redis.io/docs/stack/timeseries/
    感觉蛮合适
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5512 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 37ms · UTC 08:18 · PVG 16:18 · LAX 01:18 · JFK 04:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.