设计实时排行榜

排行榜实时按分数给玩家排名:显示全球前 10、告诉我我的排名、显示我上下方的玩家——全都随分数变化即时更新,对数百万玩家。它看起来像一行 SQL 查询(ORDER BY score),而那正是陷阱。有趣的部分是:在规模上、在持续更新下高效计算排名,是朴素数据库做得极差的事——而单个专门数据结构(有序集合)做得漂亮。

⚡ 速览要点

SQL ORDER BY + COUNT 不扩展——计算一个玩家的排名意味数清他上方所有人,每查询 O(n) 扫描,重读下绝望。
Redis 有序集合是答案——跳表 + 哈希给出开箱即用的 O(log n) 分数更新、top-k 和排名查询。
核心操作 1:1 映射——ZADD/ZINCRBY 更新、ZREVRANGE 取 top-k、ZREVRANK 取玩家排名、ZRANGE 取邻居。
Redis 是热存储;DB 是真相来源——持久存分数,重启时重建有序集合。
分片打破精确全局排名——一旦集合跨节点,你无法便宜地得到精确跨分片排名;用近似。
基于时间的榜(每日/每周)只是带重置/过期的独立有序集合。

tldr

别用 SQL 算排名——数清一个玩家上方所有人是 O(n)。用 Redis 有序集合,它在跳表里按分数保持成员有序并支持 O(log n) 更新、top-k 和排名查询。用一个持久数据库作记录系统支撑它。单个有序集合处理数千万条目;超过这个你必须分片,这牺牲精确全局排名——所以切到分桶/近似排名。周期性榜只是额外的有序集合。

a sorted set, ordered by score

rank  member     score
  0    alice      9820      ◀ ZREVRANGE 0 2  → top 3
  1    bob        9650
  2    carol      9510
  ...
 41    you        7300      ◀ ZREVRANK "you" → 41
 42    dave       7295      ◀ ZREVRANGE 40 44 → 你周围的玩家
  ...
       跳表保持顺序;所有操作 O(log n)

第 1 步 — 澄清需求

功能:更新一个玩家的分数(设置或自增);取全球 top-k;取特定玩家的排名;取一个玩家紧邻的玩家("你是 #42,这是 #40–44")。非功能:更新和读应反映近实时排名、低延迟、高可用,并扩展到数百万玩家和高写量(每个游戏动作都能改分)。澄清分数是只增(更简单)还是能升降,以及排名是全局、按区域还是时间窗口——这些改变设计。

第 2 步 — 容量估算

比如 50M 玩家、10M 日活。若每个活跃玩家触发 ~10 分数更新/天,那是 ~100M 写/天(~1–2K 写/秒平均,峰值事件高得多)加重读(每个人刷榜)。一个有序集合条目小(成员 id + 分数),所以 50M 条目约几 GB——舒适地在单个大 Redis 节点的内存里,这是个重要的定容洞见:你常常根本不需要分片。

第 3 步 — API 设计

core API

POST /scores            {user_id, delta}     # 加分
GET  /leaderboard/top?limit=10                # top-k
GET  /rank/{user_id}                          # 这个玩家的排名 + 分数
GET  /leaderboard/around/{user_id}?range=5    # 邻居

第 4 步 — 为什么朴素数据库方法失败

在 SQL 存 (user_id, score) 并用 SELECT ... ORDER BY score DESC LIMIT 10 服务 top-k。有 score 上的索引,top-k 其实没问题。杀手是排名:"玩家 X 的位置是什么?"需要 SELECT COUNT(*) WHERE score > X.score——数清他们前面的每个玩家。那是每查询 O(n) 操作,随分数变化不断重算,在数百万玩家和频繁"给我看我的排名"请求下崩溃。排名是需要更好结构的操作。

操作	SQL(索引 score)	Redis 有序集合
更新分数	O(log n) 索引更新	O(log n) — ZADD/ZINCRBY
Top-k	带索引 O(k)	O(log n + k) — ZREVRANGE
玩家排名	O(n) COUNT 扫描 ✗	O(log n) — ZREVRANK ✓
邻居	难(需先有排名)	O(log n + range) — ZRANGE

第 5 步 — Redis 有序集合

Redis 有序集合(ZSET)存各带一个分数的成员,由跳表(skip list)(加一个成员到分数的哈希 map)保持有序。这恰好给出排行榜需要的操作,全在 O(log n):

Redis operations

ZINCRBY  board  50  "user42"     # 加 50 分(或 ZADD 设置)
ZREVRANGE board  0  9  WITHSCORES # top 10(最高优先)
ZREVRANK board  "user42"          # 玩家的 0 起始排名
ZREVRANGE board  40 44            # 排名 40..44 的玩家(邻居)
ZSCORE   board  "user42"          # 一个玩家的当前分数

每个排行榜查询直接映射到一个命令,跳表随分数变化保持一切有序——无扫描、无重算。

第 6 步 — 持久化与真相来源

Redis 是快、内存的服务层,但你不该把它当作数据的唯一副本。保留一个持久数据库(SQL 或 KV 存储)作分数的记录系统。每次更新,写到数据库并更新有序集合(write-through),或流式分数事件并应用到两者。若 Redis 重启或一个节点丢失,从数据库重建它的有序集合。Redis 持久化(RDB 快照 / AOF)帮助恢复速度,但持久 DB 是权威备份。

第 7 步 — Top-k、排名与邻居

有了有序集合,三个核心读平凡:top-k 是 ZREVRANGE 0 k-1;一个玩家的排名是 ZREVRANK(O(log n)——结构跟踪子树大小,所以它数前驱而不扫描);邻居是一个 ZREVRANK 找位置后跟一个对周围窗口的 ZREVRANGE。top-k 列表也极可缓存——相对它被查看的频率它变化慢,所以以短 TTL 缓存它,在大事件期间屏蔽 Redis 免受读尖峰。

第 8 步 — 扩展:一个节点不够时

单个 Redis 节点在几 GB 里持有数千万条目,所以对许多排行榜你从不分片。当你必须(内存或写吞吐限制)时,你分片有序集合跨节点——而这就是难的地方,因为排名本质是全局属性:

按分数范围分片(如节点 A:0–1000、节点 B:1001–5000…)。Top-k 和排名变成"问最高分片并加总计数",但分数范围倾斜且跨边界的玩家必须移动分片。
按用户(哈希)分片均匀分散写,但现在每个排名/top-k 查询都必须扇出到所有分片并合并——昂贵。

第 9 步 — 精确 vs 近似全局排名

跨分片,为任意玩家计算精确全局排名昂贵(你得问每个分片"你的有多少打败这个分数?")。在很大规模,标准动作是近似:

bucketed approximate rank

维护每分数桶的玩家计数:
   [9000-9999] → 1,203
   [8000-8999] → 4,560
   [7000-7999] → 12,800   ← 你的桶
   ...
approx_rank(you) = sum(更高桶的计数)
                 + 你在你桶内的位置
→ "前 ~3%" 而非 "排名 41,233"(便宜、足够好)

大多数产品只需 top-k 的精确排名(一个单一、便宜、不分片的"领先者排行榜")和给其他所有人的近似百分位("你在前 5%"),分桶便宜地交付这个。

第 10 步 — 基于时间和分段的排行榜

每日、每周或赛季榜就是按周期为键的独立有序集合(如 board:2023-W15),各带一个 TTL,使它在周期结束时自动过期;更新写到当前周期的集合(可能还有一个全时段集合)。同一模式给出按区域或按好友组的榜——只是更多有序集合,或对一组好友 ID 用 ZINTERSTORE 做"仅好友"视图。

第 11 步 — 关键取舍

有序集合 vs 数据库。有序集合让排名 O(log n) 而非 O(n);代价是在你 DB 旁运行并持久化一个内存存储。
单节点 vs 分片。一个节点让精确全局排名平凡;分片扩展更远但迫使扇出查询或近似。
精确 vs 近似排名。不分片时精确排名可行;在海量规模,分桶百分位便宜得多且在 top-k 外通常足够。
新鲜度 vs 缓存。缓存 top-k 在尖峰期间屏蔽 Redis,代价是几秒陈旧——几乎总可接受。

总结

排行榜是个单数据结构问题:一个 Redis 有序集合把昂贵部分(持续更新下的排名、邻居、top-k)变成朴素 SQL 方法无法匹敌的 O(log n) 操作。持久到一个持久存储作真相来源、缓存 top-k,并只在单个节点真的装不下集合时才动用分片——以及它强制的近似排名。

🎯 面试速答

为什么不就 SQL ORDER BY?Top-k 没问题,但一个玩家的排名需要 COUNT 他们上方所有人——每查询 O(n),在规模上崩溃。
为什么 Redis 有序集合?它的跳表给 O(log n) 分数更新、top-k(ZREVRANGE)和排名(ZREVRANK)——恰好是排行榜操作。
Redis 是真相来源吗?不——它是热服务层;一个持久 DB 持有权威分数,使你能在重启后重建集合。
分片时什么坏了?精确全局排名——它跨所有分片。用分数桶计数便宜地算近似排名/百分位。
每日/每周榜怎么工作?按周期为键、带 TTL 的独立有序集合;写到当前周期(可选还有一个全时段集合)。