V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Sponsored by
ShowMeBug
[福利] V2EXer 专属!在线代码笔面试 20 场
ShowMeBug,专业的在线代码面试平台,助力你快速识别神队友,高效面试不加班。

为了感谢 V2EX 小伙伴们的支持,特地大家提供了福利:ShowMeBug 在线笔面试场次 20 场,限时活动,快邀请你的小伙伴来薅羊毛吧!
Promoted by ShowMeBug
CandyMuj
V2EX  ›  Java

使用 Java +mysql+redis 实现一个简易的类似随机的数据获取算法,有哪些比较好的方案?目前我都有点怀疑需求是不是有问题了。

  •  
  •   CandyMuj · 102 天前 · 2630 次点击
    这是一个创建于 102 天前的主题,其中的信息可能已经有所发展或是发生改变。

    说明

      公司的小项目,没有打算使用搜索引擎或大数据相关的技术。

    首先说一下产品的需求:

      目前有个视频列表查询,需实现每次启动 app 获取的第一页数据不同即可(如果不做处理,使用 mysql 每次获取数据的顺序都是一定的,则每个用户每次启动 app 获取的第一页数据都是一样的);还需要保证在用户没有获取完所有的视频前不再获取之前已经获取过的视频。即以每个用户为单位,看过的视频不能再被查出来,除非数据库的数据都被这个用户获取过一遍。产品不允许有重复的视频在用户没有看完所有视频前再被查询出来,无论数据量是大还是小。

    举例说明

    假设

    ​ 数据库总数据:10 条
    ​ id 为自增:1-10
    ​ 每页查询:4 条
    ​ 默认排序为 id 顺序自增

    当前方案

    • 启动 app 查询第一页数据的 id:1 2 3 4
    • redis 记录当前用户查询的最后一条数据的 id:userId:4 (最后一条记录 id )
    • 重启 app 查询第一页数据的 id: 此时就限制数据 id > 4 即 5,6,7,8
    • redis 记录当前用户查询的最后一条数据的 id:userId:8
    • 重启 app 查询第一页数据的 id: 此时就限制数据 id > 8 即 8,9,10 还差一条才满足一页,因此从 1 开始取,最终返回的数据为 8,9,10,1
    • redis 记录当前用户查询的最后一条数据的 id:userId:1
    • ...

    如果保证每次返回的数据 id 是顺序自增的那么是没问题的,如果是倒序自增,也没问题,每次重启 app 取数据的时候 id>? 变为 id<? 即可。

    遇到的问题

    有一个特殊情况,管理员可以设置精选视频,可以把一些视频进行置顶,那么获取的数据就不是顺序或倒序自增的了,顺序就会乱。

    而且还存在增删操作。

    • 顺序 id 为:1 2 3 4 5 6 7 8 9 10
    • 后台设置精选后的顺序变为:7 1 9 2 3 5 4 10 6 8
    • 如果再按照当前方案,就会出现问题:
      • 启动 app 查询第一页数据的 id:7 1 9 2
      • redis 记录当前用户查询的最后一条数据的 id:userId:2
      • 重启 app 查询第一页数据的 id:此时就限制数据 id > 4
        •   那么数据库的筛选后的排序及数据结果为:7 9 5 10 6 8
          
        •   返回的数据就变成了:7 9 5 10
          
      • redis 记录当前用户查询的最后一条数据的 id:userId:10
      • 重启 app 查询第一页数据 id:此时就限制数据 id > 10
        •   那么数据库的筛选后的排序及数据结果为:7 1 9 2 (因为>10 的数据没有,就从头开始取)
          
      • redis 记录当前用户查询的最后一条数据的 id:userId:2
      • ...

    问题也就出现了,第二次启动 app 查询的第一页数据 id7 和 9 这两条数据就和上一次启动 app 查询的数据重复了;并且 3 4 6 8 这些数据永远不会被查询出来。问题就是这样,未实现产品需求。 (数据没有全部查询过一遍,距上一次查询就出现了重复数据)

    这种情况和数据量的大小没有较大关系(如果把自增的最大的一个 id 推荐到了第一页的最后一条,那么就永远只能查到前四条数据)。

    还需要考虑管理员设置精选或者进行增删后的数据的实时性问题。设置精选和增删操作如果频繁有哪些影响。

    产品提供的一个方案

    将每个用户看过的视频进行记录,然后在查询的时候进行剔除,如果数据不够一页就从头开始获取一次;这种方式就必不会出现未看完就重复的问题,但是有严重的性能问题。

    • 顺序 id 为:1 2 3 4 5 6 7 8 9 10
    • 第一次数据 id:1 2 3 4
    • redis 记录当前用户已看数据 id:userid:1,2,3,4
    • 第二次数据 id: not in(1,2,3,4) 查出 5,6,7,8
    • redis 记录当前用户已看数据 id:userid:1,2,3,4,5,6,7,8
    • 第三次数据 id:not in(1,2,3,4,5,6,7,8) 查出 9 10 1 2 (数据不够从头开始获取)
    • ...

    逻辑是没问题的,但是数据量少还好,如果数据量很大那么性能影响很严重。

    小声 bb,产品告诉我,同时满足需求和性能不就是开发应该干的事嘛,我很想说想要性能和需求同时满足也得看需求是否合理吧。

    如果有 10w 用户并且有 10w 数据,在最极端的情况下,假设这 10w 用户有 99999 条数据都看过了,那么 redis 就会存储 10w*99999 的数据量,并且在查询 mysql 的时候语句就变成 not in(99999 个 id),想想就恐怖,如果数据量更大呢?

    但产品认为不要考虑这么多我们系统最多只有几千条数据,用户量可能会很多,但即使这样数据量也比较大 10w*几千 ,并且也没有这样设计系统的,不合理。


      不局限于目前已有的这些方案或技术栈(使用除 java+mysql+redis 以外的技术也可),只要能实现这个需求的目的就可以:以用户为单位,数据在没有全部查询过一次的情况下,不能出现重复数据。期间需考虑管理员可以在任意时刻,或很频繁的进行精选和增删操作。

      各位有没有什么好的想法,以及使用 java+mysql+redis 的技术栈能否实现,若不能实现,是否有其他实现方式?

      再提一句,这个产品实际上是个 Android 开发。

      帮忙出出主意吧,先谢谢各位了,最近已经被折磨的焦头烂额了!

    第 1 条附言  ·  100 天前
    有些想法确实给了我不少灵感,甚至我从未朝那方面想过或者未接触过,提供的这些想法即使这一次不会全都用到,但对我还是很有帮助的,指不定哪天就有需求了,那时就可以直接用,而不用费尽心思再琢磨!


    依然欢迎大家在贴内继续提出更多五花八门的想法!我会虚心学习的!但后续可能会较少回复,每次回复帖子就排在站内最前面了,不想过多占用站内资源。

    因此未一一回复,在此统一表示感谢!!! ^^
    51 条回复    2021-01-12 15:43:41 +08:00
    awanganddong
        1
    awanganddong   102 天前
    将视频列表整个加载到 redis 内存中,
    然后用户已浏览记录也放入内存中,求这两者之间的差集。
    然后对差集进行排序。

    这里边时间与空间复杂度没考虑。
    zxCoder
        2
    zxCoder   102 天前
    问题描述没看懂

    直接按你原来的方案然后存下标不行吗

    1 2 3 4 5 6 7 8 9 10
    7 1 9 2 3 5 4 10 6 8
    ylrshui
        3
    ylrshui   102 天前 via iPhone
    笨方法:为每个用户维护一个未查询列表
    MoYi123
        4
    MoYi123   102 天前
    我用 pg 尝试过类似的功能,用 hll 存用户看过的视频,和你的需求应该差不多 https://github.com/mmooyyii/mmooyyii/blob/master/docs/database/tiplist1.md
    lpts007
        5
    lpts007   102 天前 via Android
    上次在 V 站看到的,用户 id 哈希后 mod 视频数量,每次顺着取,记录下每个用户当前值。完事。
    zieglar
        6
    zieglar   102 天前
    redis 的 sdiff 命令,比较 set 返回差异值
    renmu123
        7
    renmu123   102 天前 via Android
    我提供一个非技术的方法。
    遇到这种事就直接怼回去,就说以现在技术水平做不到这件事,如果硬要做可能会产生性能问题。如果产品还在强硬,就把两人的聊天记录都整理好保存到项目软件中(以防之后出现问题倒打一耙),然后公开艾特你的老大和他以及他的老大说明其中问题,如果觉得没问题,那你就按他说的做。这样基本能保证之后就算出问题你也不用背锅,如果你的老大够给力会直接帮你怼回去。
    CandyMuj
        8
    CandyMuj   102 天前
    @renmu123 多谢,也是挺有用的一个办法,所有类似的事都可以这么处理的,做可以,出了问题我不负责,而且我之前也明确说过会出问题。遇到这种事是需要保存一些证据,尽量让自己少担责。如果遇到通情达理或者懂点技术的上级可能没问题。
    如果遇到不懂技术或者也不通情的上级,然后产品或上级给你来一句:“这不就是你该做的事吗?做不了两全其美,那就是你技术有问题。” 这就把我整蒙了啊。
    CandyMuj
        9
    CandyMuj   102 天前
    @MoYi123 谢谢
    CandyMuj
        10
    CandyMuj   102 天前
    @MoYi123 是挺类似的,学习了
    yzbythesea
        11
    yzbythesea   102 天前
    可以在手机端处理。App 缓存客户的视频列表然后在本地保存一个 bloom filter 记录客户看过的视频。到时候直接选择不在 bloom filter 里的视频 ID 然后向后台发送请求。
    CandyMuj
        12
    CandyMuj   102 天前
    @awanganddong 数据全都加载到 redis,如果只是记录 id 的话,那么在用 Sql 进行查询的时候可能不太方便的,而且数据还会存在频繁的增删操作,应该还是得以 mysql 为核心的。
    yzbythesea
        13
    yzbythesea   102 天前
    另外就是增加 redis 台数,反正你这个是可以很轻松地横向扩展的。我觉得钱到位,产品说得这个方案是推荐做法,也没有任何性能担忧。
    CandyMuj
        14
    CandyMuj   102 天前
    说一下和另一个同行进行讨论后的一个大致可行方案吧,使用最笨的办法,单独使用一张表记录用户观看过的视频(就类似一个观看记录的功能);建立好索引,即使数据量很大速度也不会太慢;
    主要问题就是在用户看完所有视频后需要清除之前已看的数据重新记录,在删除的时候需要重建索引,为了不影响用户正常使用,可以使用队列或者 redis 发布订阅来进行异步的删除,这样数据就存在延迟,就可能出现我一边在插入一边在删除的情况,查询也存在问题(本应该从头开始查,但此时还没有删除之前的观看记录,因此实际查询的时候还会剔除之前已观看的)。
    解决这个的办法就是在往队列插入删除任务的时候同时记录需要删除的历史观看记录的最大 id,在删除的时候就通过 userid=? and historyId <= ?,如果数据量大可以进一步优化,进行分批删除。
    还有个问题就是管理员如果修改了精选视频的排序,是否需要用户实时展示最新的排列顺序,即是否也要清空观看记录的问题或者其他的处理方式(例如,只清除所有用户历史记录中管理员新设置精选的视频 id,让这些视频可以被用户再次查询,此时就不考虑重复问题,因为设置精选就是为了增加曝光量)。如果不考虑这一点的话就不用管了
    rrfeng
        15
    rrfeng   102 天前 via Android
    先实现:根据上次访问的 lastid 分页

    再实现:精选的 lastid

    拼在一起即可。
    CandyMuj
        16
    CandyMuj   102 天前
    @zieglar 谢谢,和一楼的方法类似 需要数据在 redis 才好操作,因此筛选出 id 后使用 sql 操作存在性能问题,应该以 msyql 为核心
    CandyMuj
        17
    CandyMuj   102 天前
    @rrfeng 谢谢,最开始就是这个,主要问题就在于这个数据的顺序会变,如果顺序不变就没问题 可以看看 14 楼的方案
    CandyMuj
        18
    CandyMuj   102 天前
    不一一回复了,感谢所有回复的朋友,好的方案我会学习一下的,谢谢啦! ^^
    CandyMuj
        19
    CandyMuj   102 天前
    @rrfeng 不过维护两个 lastid 这个想法挺不错的,是一个好的想法,谢谢。
    CandyMuj
        20
    CandyMuj   102 天前
    @ylrshui 笨方法有时反而是最有效的方法,只要优化的好也能成为好的方法,哈哈哈!
    CandyMuj
        21
    CandyMuj   102 天前
    @yzbythesea 这种方式用 sql 查询的时候会用到 in(id1,id2,ids...),这样的话不走索引的,或者有什么方法可以替代 in 么?而且这种操作一般都不会在 app 端做处理的。
    CandyMuj
        22
    CandyMuj   102 天前
    @CandyMuj 还有一点,记录历史记录的时候是每次查询都记录视频 id,但是查询由于是分页的,在查询的时候需要加一个限制 historyId <= 第一页查询时的最大历史记录 id,不然就会出现下面的问题
    有数据 id:1 2 3 4 5 6 7 8 9 10
    首次查询不剔除数据
    第一页:limit 0,2 => 1 2 3 4
    记录看过的:1 2 3 4
    第二页查询:
    此时就剔除 1234:5 6 7 8 9 10
    查询:limit 2,2 => 7 8

    就会导致有些数据是被直接跳过了
    CandyMuj
        23
    CandyMuj   102 天前
    @CandyMuj 还有一点,记录历史记录的时候是每次查询都记录视频 id,但是查询由于是分页的,在查询的时候需要加一个限制 historyId <= 第一页查询时的最大历史记录 id,不然就会出现下面的问题
    有数据 id:1 2 3 4 5 6 7 8 9 10
    首次查询不剔除数据
    第一页:limit 0,2 => 1 2
    记录看过的:1 2
    第二页查询:
    此时就剔除 1234:3 4 5 6 7 8 9 10
    查询:limit 2,2 => 5 6

    就会导致有些数据是被直接跳过了
    zieglar
        24
    zieglar   102 天前
    @CandyMuj 其实都使用 redis 操作是可行的,首先维护好 redis 里对应的影片列表,在排序、新增、修改以后都同步到这个列表里,然后每个用户两个列表,一个是已看,一个是未看,初始数据时影片列表同步到未看,然后用 spop 来获取未看列表数据输出为 A 列表,然后把看 A 列表数据同步到已看列表里,后面的操作是当影片列表发生变化时,影片列表和已看进行 sdiff,把差异值覆盖到未看去,这样每次从未看拿到的数据符合影片列表的最新排序,且根据 A 列表数据也可以对从数据库的记录进行排序,并不觉得这样根据 ID 来搜索 mysql 的数据会早层什么性能问题
    YouLMAO
        25
    YouLMAO   102 天前 via Android
    标题写随机,内文没有,骗子
    xyjincan
        26
    xyjincan   102 天前 via Android
    头一次见这么详细的说明帖子,管理员操作信息直接维护在列表数据库,用户已读数据单独建表,
    hma
        27
    hma   102 天前 via iPhone
    @CandyMuj #17 可以把精选列表独立出来。再记录精选的已阅列表。
    yzbythesea
        28
    yzbythesea   102 天前
    @CandyMuj 直接用 redis 存用户看不过没有? App 端还真有类似做法。
    lldld
        29
    lldld   102 天前
    还是需要对每个用户存储其看过的视频, 但是每个 id 都记不合适.

    大部分情况下, 给用户展示的视频是按 id 排序的, 少部分是随机的(精选).

    记录的 id 也分两种形式, 比如 [1, 30], [40, 48], {51, 72, 99} 表示看过 1~30, 40~48, 以及 51, 72, 99.

    那么当下要推荐给用户的视频, 应该是优先推荐精选, 然后就是以缩短上面的记录为原则.

    比如今天的精选是 {200, 210, 22}, 然后首页需要 5 个视频, 那么再补上 49, 50 比较好.
    sql 就是 select id in [200, 210, 22, 49, 50]

    这样新的记录变成 [1, 30], [40, 51], {72, 99, 200, 210}
    CandyMuj
        30
    CandyMuj   102 天前 via Android
    @YouLMAO 我说了这是一个类似随机的方案,因为直接采取随机的话,会出现重复的数据,不满足需求。如果想实现随机+不重复 你可以在取数据的时候进行随机获取并踢除已看视频,如果数据不足一页就一次查询多页,查询多页需要注意一个问题,看第 23 楼
    CandyMuj
        31
    CandyMuj   102 天前 via Android
    @yzbythesea #28 我没有这样处理过 😂
    CandyMuj
        32
    CandyMuj   102 天前 via Android
    @zieglar #24 这样确实也可以,谢谢你的思路。
    如果把数据全部维护到 Redis,个人不太喜欢这样的处理方式。
    处理方式挺不错的,如果后续有其他需求可以用到这个思路!
    CandyMuj
        33
    CandyMuj   102 天前 via Android
    @yzbythesea #28 关于用户一般就是存个 token,缓存一些用户数据,直接用 Redis 当用户表就没玩过了 😂
    CandyMuj
        34
    CandyMuj   102 天前 via Android
    @hma 后续会考虑这方面的优化,谢谢!
    CandyMuj
        35
    CandyMuj   102 天前 via Android
    @xyjincan #26 最开始就是打算的这个方案,可能我当时技术欠缺或者没想到如何优化性能,然后就不打算采取这个方案。现在有了性能优化方案以及整个查询逻辑的细节处理方法,就可以用啦。

    问题不描述清楚,我光解释就要解释半天。😂
    CandyMuj
        36
    CandyMuj   102 天前 via Android
    @lldld 感谢,好的想法,学习到了! ^^
    CandyMuj
        37
    CandyMuj   102 天前 via Android
    @lldld #29 暂时先记录所有吧,先出一个可以用的,然后再优化吧,这种不记录全部 id 的想法很棒!
    CandyMuj
        38
    CandyMuj   102 天前 via Android
    @YouLMAO #25 并且,我这是一篇求助帖,而不是教程帖。
    zxyroy
        39
    zxyroy   102 天前
    我突然有个想法,既然没有要求每个用户顺序不能一样,不如直接生成一个乱序列表,每个用户都按这个乱序列表返回,新视频就攒 10 个再乱序追加到最后。每当有用户 load 完其中一个列表就再创建一个。每个用户一定要 load 完一个列表才能进入下一个。
    kkkkkrua
        40
    kkkkkrua   102 天前
    给个 sort 列,专门用来排序,好像就可以解决你 id 乱序的问题吧
    qingluo
        41
    qingluo   102 天前
    redis 有一个 hyberloglog 的数据结构 可以做做参考
    Nillouise
        42
    Nillouise   101 天前
    没详细看题目,但我考虑过类似的问题,即信息流推荐,因为信息的内容是实时更新的,所以什么生成固定序列,其实不是个好办法,无法处理这种情况,也无法处理不同信息有权值的情况。

    网上我看到有文章说,记录最多用户看过的 10000 个信息,然后直接过滤这 10000 个信息即可。
    pushback
        43
    pushback   101 天前
    order by RAND()
    MySQL 无所不能
    simonlu9
        44
    simonlu9   101 天前
    自己用 redis 有序集合存吧,优先推荐那些就把权重提高一点,我是用 es 做的,可以满足很多需求
    thinkmore
        45
    thinkmore   101 天前
    我有一个想法。把所有数据分配到一个环中。

    然后给每个用户随机分配一个在环中的起始点。

    当有精品视频时,就将这些排序好的重新构成环即可

    @CandyMuj
    OldCarMan
        46
    OldCarMan   101 天前
    不知道,你说的不重复是什么样的时间频率,如果是每一天保证不重复(或者隔多长时间保证不重复)并且只靠 mysql 实现的话,加一个用户浏览记录表,然后每次查询加上一个 not in 之类的,最后加个定时任务,定时删除该频率内产生的这些记录数据。
    auh
        47
    auh   101 天前
    依赖 mysql 是没办法实现这种乱序操作的,必然带来 msyql 的压力。
    视频记录必须 load 到 redis 。

    分页,这种分页,本质上不是分页。而是单纯的下一批。
    每页 10 个。就读取 redis 集合存储的 Vid10 个。

    如果视频没有时效性,直接顺序读取 redis 列表就行。只为每个用户记录一个游标,因为对用户来说,用户感知不到随机性。兼容竞选列表也很简单。单独处理精选列表逻辑。合并两个结果集,保证一页总共 10 个就行了。

    如果视频具备特殊属性。不仅是时效性。可能就需要,为每个用户记录已读列表了。
    这个时候,优化的话,如果可以,对视频列表进行分片,用户读完一片之后,不需要再关心之前的片了。已读列表就很小了。
    如果分片不了,相当于用户面向的是整张视频表的随机。这种必须完整记录。但是,现在可以考虑针对用户分组。不同组群的用户共享一个已读列表。每个用户只持有游标。内存就又少了。

    ok 。不废话了。具体情况,具体分析。因为你遇到的可能比你描述的复杂的多。
    fkname
        48
    fkname   100 天前
    1.建议客户端做随机操作,这样可以大大减少服务端的计算
    2.如果用新表存储已读记录,可以做逻辑删除,这样不会有重建索引的问题。当然插入时需要修改为 insertOrUpdate 方式
    CandyMuj
        49
    CandyMuj   100 天前 via Android
    @fkname #48 感谢,是个很好的办法!
    CandyMuj
        50
    CandyMuj   100 天前 via Android
    @auh 谢谢
    CandyMuj
        51
    CandyMuj   100 天前 via Android
    @auh #47 万分感激,我还一直在分页这里面琢磨。。。 实际上这里就是分批次拿数据,都不应该叫做分页了!
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2975 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 05:16 · PVG 13:16 · LAX 22:16 · JFK 01:16
    ♥ Do have faith in what you're doing.