Skip to content

Latest commit

 

History

History
126 lines (111 loc) · 5.22 KB

排行榜系统设计.org

File metadata and controls

126 lines (111 loc) · 5.22 KB
Raw

排行榜系统设计

知识点

  • 性能优化
  • 热点分析
  • 数据分片
  • 数据结构/缓存设计

需求

设计一个排行榜系统 可以查询出 每天/月/年/总榜 每个用户获得的奖励(贝壳)排行榜 以及当前用户在排行榜上的名次

设计要求

  • 可以查询每个用户当前的排名
  • 排行榜更新时效性保证分钟级别更新
  • top N (N < 1000) 要做到实时更新

性能要求

  • 千万量级用户, 峰值 QPS > 1万
  • 读写延迟低于100ms
  • 高可用(服务实例/存储实例宕机场景分析)

sql 设计

CREATE TABLE board_bucket_$id (
    uid int(11) comment '用户id',
    score int(11) conmment '得分',
    PRIMARY KEY (`uid`),
    KEY`score_idx` (`score`)
) ENGINE=InnoDB COMMENT='排名分表';

CREATE TABLE board (
    uid int(11) comment '用户id',
    score int(11) comment '得分',  /* 冗余数据 */
    bucket_id int(11) comment '桶id',
    PRIMARY KEY (`uid`)
) ENGINE=InnoDB COMMENT='排名总表';

redis 设计

分片 redis zset

  • zset key1：pre + bucket_id
  • field: uid
  • score: score

各个分片的长度

  • hash key2: key
  • field: bucket_id
  • value: len

各个分片长度缓存（热 key)

  • string key3: key
  • value: map{bucket_id: len}
  • expire: 30s

内存缓存

每个桶的 min_score, max_score

代码逻辑

查询用户排名

  1. 根据 uid 从表 board 获取用户 bucket_id
  2. 从 key1 获取用户在该分片的排名 rank
  3. 从 key3 获取各个分片的长度
  4. 计算最终排名：所有小于 bucket_id 的各个分片的长度之和 + rank

加分（并发模式下需要对该用户加分布式锁。加锁LK -> 步骤1 -> 步骤2 -> 解锁LK -> 步骤3)

  1. 更新 board 表中的用户分数
  2. 查询 board 表中用户当前桶，根据 score 来查询用户应该划分的桶
    • 在同一个桶中, 那么只需要更新当前桶中分数（board_bucket_$id 桶中的分数和 redis zset 分片的分数）
    • 如果跨桶
      • 在新桶中插入该用户分数（board_bucket_$id 桶中的分数和 redis zset 分片的分数）
      • 更新 board 表中用户的 bucket_id
      • 删除旧桶该用户数据（board_bucket_$id 桶中的分数和 redis zset 分片的分数）
  3. 更新 redis key2 各个分片长度

rebalance/load 逻辑

  1. 遍历 board 的每一条记录，对每一条记录，执行步骤2
  2. 查询该用户当前桶、和应该划分的桶
    • rebalance: 在同一个桶中，跳过; load: 如果在同一个桶中，在桶中插入该用户
    • 如果跨桶
      • 加锁 LK
      • 查询该用户当前桶、和应该划分的桶，如果跨桶，继续下一步；否则遍历下一条记录
      • 在新桶中插入该用户分数（board_bucket_$id 桶中的分数和 redis zset 分片的分数）
      • 更新 board 表中用户的 bucket_id
      • 删除旧桶该用户数据（board_bucket_$id 桶中的分数和 redis zset 分片的分数）
      • 解锁 LK
    • 更新 redis key2 各个分片长度
  3. zcard 获取每个分片长度，redis key2 设置各个分片长度

优化

redis 更新时可以使用 pipeline

kafka 消费者一次性获取 1000 条加分任务，merge 之后再执行加分操作

表 board 是大表，可以提前分库分表

考虑到通用性，可以在两张表中新增榜单名字段

可靠性

db 宕机

redis 宕机

设计要点

  • 直接查询排名涉及到全局排序,如何设计存储来规避这个问题.
    • 采用分桶策略, 根据排行榜数据分布分桶, 或者根据用户数据量分桶. 这块可以开放来回答, 言之有理即可
  • 关于内存缓存
    • 需要缓存各个 bucket 的大小, 以及 score 区间. 便于查询加速
  • 用户数据更新
    • 可以考虑多种方案(MQ, 合并写, 定期 rebalance 等, 根据场景选择)
  • redis 或者 DB 宕机如何处理
    • 如果 DB 宕机, 需要保存写请求到 MQ,等待恢复后重放
    • 如果 redis 宕机, 系统降级 rank 的查询
      • 根据线性插值法估算排名(这块可以有很多近似估计法, 根据情况要求候选人回答)
      • rank = (max_score - user_score) * bucket_size / (max_score - min_score)
  • Top N 热点数据如何缓存, 如何保证强一致性
    • 针对 Top 可以设立单独的缓存或者存储, 用户数据更新如果进入 Top N 的范围, 需要重建缓存, 这块需要单独讲清楚

评分标准

P7 技术专家

  • 对于整个系统需要解决的问题, 有比较清晰的认识. 能够想到分桶或者其他类分治的方法.
  • 对于热点查询(Top N)能想到缓存的方案, 以及强一致性的方法, 思路不能有模糊的地方
  • 在可靠性上, 对于 db 宕机, 以及峰值写入, 并发查询的场景需要能给出正确思路
  • 对于降级以及容灾方案, 需要讲清楚流程
  • 分桶设计以及数据更新流程上, 需要讲清楚每一步的细节.
  • 需要考虑服务通用性设计, 而不是针对单一的场景

P6 资深工程师

  • 需要考虑到分桶的设计, 如果没想到分桶设计, 也需要提供近似估计的一些方案(全局近似估计)
  • 对于热点数据, 需要考虑查询效率的问题
  • 数据库以及缓存的结构设计需要讲清楚原因
  • 能给出一些性能以及稳定性相关的优化方案(结合具体场景)