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

请教大佬,类似蚂蚁森林的能量排行,后端应该怎么设计?

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

    假设系统有 N 万个用户,每个用户都有一个 score 。这个 score 经常发生变化。

    需要完成以下功能:

    1. 整个平台,score 最高的 N 个用户的信息
    2. 我的好友 score 排行榜
    3. 我的 score 在整个平台处于的位置

    现在没有太好的思路,现在想的是

    • score 加索引,但是对于经常变化的这个列加索引会不会导致更新速度大幅减慢?
    • redis 加个 zset,但是这样的话如何能保证跟 MySQL 里面的数据保持一致呢?

    假设数据存在 MySQL 里面的

    create table user (
        id bigint not null primary key,
        name varchar(255) not null,
        score int not null
    );
    
    create table user_relation (
       user1_id bigint not null,
       user2_id bigint not null,
       primary key(user1_id, user2_id)
    );
    
    43 条回复    2020-09-11 10:26:27 +08:00
    siweipancc
        1
    siweipancc   170 天前 via iPhone
    mysql 可以用内存数据库,等个最优解
    qwerthhusn
        2
    qwerthhusn   170 天前
    @siweipancc 这东西要持久化的,内存数据库肯定不行
    siweipancc
        3
    siweipancc   170 天前 via iPhone
    @qwerthhusn 可以晚点同步。我指的是开另一个内存中间表,在一个活动结算周期切换的时候再写入实体表
    netty
        4
    netty   170 天前 via Android   ❤️ 1
    用 Redis 的 SortedSet 轻松搞定,key 排行榜名称,member 用户 ID,score 为用于排行的值
    ffLoveJava
        5
    ffLoveJava   170 天前
    等一个大佬
    用户少的话无所谓。我想知道大佬对于超量用户量有什么解决方案?
    qwerthhusn
        6
    qwerthhusn   170 天前
    @netty 这个道理都明白,但是数据库和 redis 的同步咋做呢?

    首先 redis 不能事务,可能就存在 redis 与真实数据不一致的地方。

    我能想到的就是定时全量刷新了,不知道这样弄合理不合理,全量刷新间隔时间也不好定
    qwerthhusn
        7
    qwerthhusn   170 天前
    @ffLoveJava 期望来个大厂做过类似场景的的大佬,分享一下 Best Practice 呢。。
    smartwusir007
        8
    smartwusir007   170 天前
    @netty 这样总用户排行有了,怎么做每个用户的好友排行呢
    xiaoliu926
        9
    xiaoliu926   170 天前   ❤️ 1
    @smartwusir007 用户好友排行前端来实现就行了,只需要把用户好友数据丢给前端,前端自己排序
    qwerthhusn
        10
    qwerthhusn   170 天前
    @smartwusir007 其实我突然一想,好友那个反而好弄一点,首先拿到好友 ID 列表,然后直接数据库或者 ZSCORE 读取好友们的 score 信息,直接应用排序。毕竟一个人的好友不会太多,
    optional
        11
    optional   170 天前 via iPhone
    总排行榜和我的位置不是实时的,只要根据分数估算排行就行。
    limbo0
        12
    limbo0   170 天前 via Android
    海量数据可以用图数据库,技术 janusgraph,保存关系和分数应该问题不大
    LostPrayers
        13
    LostPrayers   170 天前
    简单实现就是 4L 说的 SortedSet,不能事务没有关系, 排行是通过 score 自动计算的, zrank 即可取到 index.
    好友 score 排行榜, 就取出所有好友 id 对应的 zrank 再排个序
    firefox12
        14
    firefox12   170 天前
    总排行 定期算,拿出 1 个数组 ,长度为 n, 比如 0-10000 最多 10000 点, 然后统计的时候 把你的分数-> index, 在 index 上加 1
    最终结果 就是 0 分的 100 代表 100 人 0 分,1 分 200 代表 200 人 1 分。
    从 n->0 开始 统计, 把结果写在数组里, 比如 n 里面 10 个人,n-1 里面 100 人, 那么 n 就是 10, n-1 就是 110, 这个 x
    的值,就是 n 到 x+1 的和,这个数组的坐标里的值就是 你的排名。

    最后拿你的分数 直接在这张表里查 你就知道 你多少名了。
    Rheinmetal
        15
    Rheinmetal   170 天前
    十分钟刷新一次排名可破
    kusya
        16
    kusya   170 天前 via Android
    数据如果不要求实时性,可以按照 score 索引查询。数据太多还可以分表。
    hejw19970413
        17
    hejw19970413   170 天前
    @Rheinmetal 支付宝几亿的用户,怎么处理?
    zhgg0
        18
    zhgg0   170 天前
    可以利用桶排序,记录每个分数段的用户数量,根据当前用户的分数能直接算出大概排名。
    最高分数段的用户特殊处理,可以计算他们的准确排序。
    用户好友数一般不多,直接排就好了,可以把好友的分数缓存到当前用户里并且不用实时更新,只需要实时更新自己的分数就行了。
    如果分数跨度不大的话,假设分数只有 0 到 1000 这种,直接记录每个分数有多少用户,这种情况可以 O(1)算出每个人的准确排名。
    zxCoder
        19
    zxCoder   170 天前
    收藏
    yeqizhang
        20
    yeqizhang   170 天前 via Android
    赞同楼上有人说的把用户的好友 ID 去查出来排序就行了。总排名位置这东西实时性应该不高而且是个大概的位置
    proger
        21
    proger   169 天前
    粗浅一点想的话,我感觉一群人分数打架,排出一个总排名表存在一个表内,每当有人分数达到表内到最低分数时,去做表内数据的替换。
    这样就变成用户主动去踢榜,可能会比较轻松点。
    显示的话,直接显示这个表给所有用户就好了,比较不会需要显示几千上万条数据给用户看,盲猜是百来条的样子。
    Olament
        22
    Olament   169 天前
    一个大小为 N 的最小堆,每当有人的分数达到最小堆顶用户的分数时,弹出最小堆的一个元素,插入这个新用户到最小堆中
    Olament
        23
    Olament   169 天前
    @Olament 看错题目了,尴尬
    cassyfar
        24
    cassyfar   169 天前
    我个人以前做过推荐,每个商品有一个 score 。当时是线下计算,因为 score 变化不大,每一小时算一次就足够了。

    如果 score 变化大而且你需要特别精确的话,可以参考这个:
    https://aws.amazon.com/blogs/database/building-a-real-time-gaming-leaderboard-with-amazon-elasticache-for-redis/
    xuanbg
        25
    xuanbg   169 天前
    凡是排行,统统 Redis 。用一个 ZSet 就行了
    SeanLari
        26
    SeanLari   169 天前
    这个东西,和游戏的技能使用技能冷却一个意思吧?也就是时间轮?(我不懂我瞎说的
    SmiteChow
        27
    SmiteChow   169 天前
    分数和用户绑定存 mysql,榜单存 redis,定时打榜即可
    zdt3476
        28
    zdt3476   169 天前
    第 1 点和第三点,redis zset 轻松搞定。至于同步问题也不用担心。更新 mysql 数据的时候同步更新 redis 数据就行了。排行榜这东西本来就不会要求很高的一致性,而且你说的才 N 万用户,那就更不会有问题了。 至于第二点,返回好友列表的 score 给前端,让前端排序。
    zdt3476
        29
    zdt3476   169 天前
    @zdt3476 或者干脆你查到好友列表的 score 自己排好序再给前端也是一样的。
    promise2mm
        30
    promise2mm   169 天前
    Redis: 好友排行应该一个 Zset 管够,全部用户的话,考虑数量问题,我的想法是先来个 hash,存 n 个分段的 Zset 的索引 key

    比如:key1 -> 1~100 分:Zset1
    key2 -> 101~200 分:Zset2
    keyN -> X~Y 分:ZsetN

    当然,按场景可以调整或者冗余分组的策略,比如按城市(如果需要城市排名的话)
    wellsc
        31
    wellsc   169 天前 via Android
    @limbo0 海量数据和图数据库有啥关系...不是业务复杂才用图数据库么
    qiyuey
        32
    qiyuey   169 天前
    推、拉的区别,这种一般拉就行
    Citrullus
        33
    Citrullus   169 天前
    等一个最优解决方案
    676529483
        34
    676529483   169 天前
    1:大顶堆,每隔一段时间同步下就行
    2:因为查询频率不会太高,觉得直接查数据库+缓存就行了
    3:跳表,或者直接把 1 的堆分多个,只用找出大概位置就行,比如 5k+
    在更新内存数据结构的同时,同步更新数据库
    以上瞎说,期待大厂兄弟
    ershisi
        35
    ershisi   169 天前
    @optional 同意这个说法。
    sdushn
        36
    sdushn   169 天前
    @xiaoliu926 我想到的也是这样,前端做这个更合适,之前遇到一个类似场景,后端推来所有好友数据,前端根据某个字段排序,毕竟这个场景下,可以接受实时性比较差,如果要实时性强的话可能要考虑其他方案了
    pepesii
        37
    pepesii   169 天前
    @limbo0 #12 我感觉也是图数据库呢,蚂蚁金服用的是自研的数据库应该是 ocean base,好像有个 gae base
    kiwier
        38
    kiwier   169 天前
    @yeqizhang 对,总排名这玩意没人要求实时刷新排名,基本都是各一小时或者几个小时再更新排名
    kiwier
        39
    kiwier   169 天前
    @sdushn 好友数据在 app 里本地就存储了,新加或删减好友再同步数据库里
    wangyzj
        40
    wangyzj   169 天前
    redis zset
    yangyaofei
        41
    yangyaofei   169 天前
    同意 #14 楼的思路 但是这个其实是存储 n * 10^4 区间中的个数,就可以接近实时的了,然后每次直接算每个区间的计数之和和对应的小区间的排名就好了.

    记得最早看见这个问题还是好久之前迅雷算积分有离线下载的时候,大体意思就是算某个迅雷用户的积分的排名
    limbo0
        42
    limbo0   169 天前 via Android
    @wellsc 额,针对楼上说的数据量大的情况下算好友排名,更适合图数据库
    wellsc
        43
    wellsc   168 天前
    @limbo0 还是那个问题,图数据库是用来解决高并发还是复杂业务场景的
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2584 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 15:36 · PVG 23:36 · LAX 07:36 · JFK 10:36
    ♥ Do have faith in what you're doing.