SWE · System / Product Design

Meta 游戏排行榜:全局、好友、本人排名与滚动分页

设计全局前十、好友榜、本人周围排名和滚动分页,解释精确排名、有序索引、热点与一致性取舍。

题目重点:设计全局前十、好友榜、本人周围排名和滚动分页,解释精确排名、有序索引、热点与一致性取舍。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练以每个赛季每位用户一个权威分数为例;分数高者在前,同分按稳定userId排序,排名定义为排序中的位置,避免dense rank与ordinal混用。
  • 好友榜按访问者当前可见好友集合过滤;权限变更应即时生效。题目未指定重置或反作弊合同,作为扩展处理。
  • 先问更新频率、用户数、好友上限、是否允许最终一致以及滚动是否要求稳定快照。示例容量为假设:1亿用户、10万次分数更新/秒、100万次读/秒。

解题路线

  1. 用score-event(userId,season,eventId,revision,score)确定重复与乱序规则;权威存储拒绝旧revision,榜单按该版本更新,避免重试多加分。API分别提供global top、user rank、neighbors、friend top和cursor page。
  2. 中等规模单榜可用有序集合(score,userId)实现update/rank/range。若用浮点score编码userId,必须验证精度;更稳的是支持复合排序键的索引。user→score映射让排名与好友筛选可直接查询。
  3. 好友少时批量读分数再排序,查询O(F log F);好友大或查询高频可缓存可见好友榜,好友关系/权限/分数变化触发失效。全局附近±5直接rank范围查询,不能从好友榜推断全局名次。
  4. 单分片撑不住时按分数区间分区,维护区间人数和区间内有序索引。精确rank=前面区间人数之和+本区间rank;跨区间改分需事务或事件版本,否则一人可能被重复或漏计。TopK聚合各分区候选,热点高分段需自适应切分。
  5. 滚动用最后的(score,userId)及榜单epoch为cursor。实时变化会使跨页重复/遗漏;若业务要求稳定视图,固定物化快照或MVCC版本,并设置保留期。API明确旧cursor过期的返回和重启方式。

手动走一遍

A=100、B=100、C=90,同分userId A<B,则排序A/B/C。B的全局rank=2,若好友只有C,则好友榜仍是C第1而不是全局第3的同一含义。第一页[A,B]的cursor必须含100与B;仅含score=100会漏掉同分玩家。

规模与取舍

单个有序索引更新/定位rank为O(log N),范围K条O(log N+K);好友榜O(F)批量取分加O(F log F)排序。每玩家24字节基础字段的1亿条约2.4GB,尚未计索引、对象、复制和日志,实际需要量测。跨分片精确rank的成本来自计数一致性,不只是网络并行。

易错点与追问

容易失分的边界

  • 用offset分页会随榜单变化跳过或重复记录;cursor只解决排序定位,稳定快照仍需版本。
  • 客户端提交任意分数会破坏榜单可信度;评分服务鉴权,客户端事件须验证,异常账号过滤后排名口径要一致。
  • Redis有序集合不能自动解决跨分片精确rank、权限和故障恢复。缓存榜单不是权威计分账本。

继续深挖

  • 强一致写确认后本人立即看到新rank,应读同版本或走权威路径;其他玩家可采用有界延迟副本。
  • 全球地区榜和赛季榜是否共享分数?定义维度和更新扇出,避免给每个好友同步写一份巨大榜。
  • 若分区边界移动,如何通过新旧epoch双写/回填/对账再切换,保证cursor和计数不混版本?
✓已复制微信号!