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

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

  •  
  •   qwerthhusn · 2020-09-09 17:27:57 +08:00 · 6129 次点击
    这是一个创建于 1518 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设系统有 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  
       2020-09-09 18:30:36 +08:00 via iPhone
    mysql 可以用内存数据库,等个最优解
    qwerthhusn
        2
    qwerthhusn  
    OP
       2020-09-09 18:32:38 +08:00
    @siweipancc 这东西要持久化的,内存数据库肯定不行
    siweipancc
        3
    siweipancc  
       2020-09-09 18:48:14 +08:00 via iPhone
    @qwerthhusn 可以晚点同步。我指的是开另一个内存中间表,在一个活动结算周期切换的时候再写入实体表
    netty
        4
    netty  
       2020-09-09 19:09:08 +08:00 via Android   ❤️ 1
    用 Redis 的 SortedSet 轻松搞定,key 排行榜名称,member 用户 ID,score 为用于排行的值
    ffLoveJava
        5
    ffLoveJava  
       2020-09-09 19:13:48 +08:00
    等一个大佬
    用户少的话无所谓。我想知道大佬对于超量用户量有什么解决方案?
    qwerthhusn
        6
    qwerthhusn  
    OP
       2020-09-09 19:14:13 +08:00
    @netty 这个道理都明白,但是数据库和 redis 的同步咋做呢?

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

    我能想到的就是定时全量刷新了,不知道这样弄合理不合理,全量刷新间隔时间也不好定
    qwerthhusn
        7
    qwerthhusn  
    OP
       2020-09-09 19:15:41 +08:00
    @ffLoveJava 期望来个大厂做过类似场景的的大佬,分享一下 Best Practice 呢。。
    smartwusir007
        8
    smartwusir007  
       2020-09-09 19:15:44 +08:00
    @netty 这样总用户排行有了,怎么做每个用户的好友排行呢
    xiaoliu926
        9
    xiaoliu926  
       2020-09-09 19:18:26 +08:00   ❤️ 1
    @smartwusir007 用户好友排行前端来实现就行了,只需要把用户好友数据丢给前端,前端自己排序
    qwerthhusn
        10
    qwerthhusn  
    OP
       2020-09-09 19:23:37 +08:00
    @smartwusir007 其实我突然一想,好友那个反而好弄一点,首先拿到好友 ID 列表,然后直接数据库或者 ZSCORE 读取好友们的 score 信息,直接应用排序。毕竟一个人的好友不会太多,
    optional
        11
    optional  
       2020-09-09 19:34:32 +08:00 via iPhone
    总排行榜和我的位置不是实时的,只要根据分数估算排行就行。
    limbo0
        12
    limbo0  
       2020-09-09 19:48:58 +08:00 via Android
    海量数据可以用图数据库,技术 janusgraph,保存关系和分数应该问题不大
    LostPrayers
        13
    LostPrayers  
       2020-09-09 19:49:18 +08:00
    简单实现就是 4L 说的 SortedSet,不能事务没有关系, 排行是通过 score 自动计算的, zrank 即可取到 index.
    好友 score 排行榜, 就取出所有好友 id 对应的 zrank 再排个序
    firefox12
        14
    firefox12  
       2020-09-09 20:04:46 +08:00
    总排行 定期算,拿出 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  
       2020-09-09 20:07:07 +08:00
    十分钟刷新一次排名可破
    kusya
        16
    kusya  
       2020-09-09 21:33:00 +08:00 via Android
    数据如果不要求实时性,可以按照 score 索引查询。数据太多还可以分表。
    hejw19970413
        17
    hejw19970413  
       2020-09-09 21:55:54 +08:00
    @Rheinmetal 支付宝几亿的用户,怎么处理?
    zhgg0
        18
    zhgg0  
       2020-09-09 22:17:20 +08:00
    可以利用桶排序,记录每个分数段的用户数量,根据当前用户的分数能直接算出大概排名。
    最高分数段的用户特殊处理,可以计算他们的准确排序。
    用户好友数一般不多,直接排就好了,可以把好友的分数缓存到当前用户里并且不用实时更新,只需要实时更新自己的分数就行了。
    如果分数跨度不大的话,假设分数只有 0 到 1000 这种,直接记录每个分数有多少用户,这种情况可以 O(1)算出每个人的准确排名。
    zxCoder
        19
    zxCoder  
       2020-09-09 22:38:39 +08:00
    收藏
    yeqizhang
        20
    yeqizhang  
       2020-09-09 22:53:50 +08:00 via Android
    赞同楼上有人说的把用户的好友 ID 去查出来排序就行了。总排名位置这东西实时性应该不高而且是个大概的位置
    proger
        21
    proger  
       2020-09-10 00:28:44 +08:00
    粗浅一点想的话,我感觉一群人分数打架,排出一个总排名表存在一个表内,每当有人分数达到表内到最低分数时,去做表内数据的替换。
    这样就变成用户主动去踢榜,可能会比较轻松点。
    显示的话,直接显示这个表给所有用户就好了,比较不会需要显示几千上万条数据给用户看,盲猜是百来条的样子。
    Olament
        22
    Olament  
       2020-09-10 03:13:32 +08:00
    一个大小为 N 的最小堆,每当有人的分数达到最小堆顶用户的分数时,弹出最小堆的一个元素,插入这个新用户到最小堆中
    Olament
        23
    Olament  
       2020-09-10 03:17:12 +08:00
    @Olament 看错题目了,尴尬
    cassyfar
        24
    cassyfar  
       2020-09-10 04:18:11 +08:00
    我个人以前做过推荐,每个商品有一个 score 。当时是线下计算,因为 score 变化不大,每一小时算一次就足够了。

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

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

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

    记得最早看见这个问题还是好久之前迅雷算积分有离线下载的时候,大体意思就是算某个迅雷用户的积分的排名
    limbo0
        42
    limbo0  
       2020-09-10 17:46:47 +08:00 via Android
    @wellsc 额,针对楼上说的数据量大的情况下算好友排名,更适合图数据库
    wellsc
        43
    wellsc  
       2020-09-11 10:26:27 +08:00
    @limbo0 还是那个问题,图数据库是用来解决高并发还是复杂业务场景的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1062 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 34ms · UTC 19:30 · PVG 03:30 · LAX 11:30 · JFK 14:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.