为数百万玩家设计一个实时排行榜

Question

为数百万玩家设计一个实时排行榜

IT Interview Practice · Accepted Answer

**使用以分数为键的 Redis sorted set（ZSET）：排名和 top-N 成为 O(log N) 的内置操作，因此你绝不会在每次请求时对数百万行排序。**ZSET 会自动按分数保持成员有序；这正是排行榜的本质。

## 架构

```text
Game svc ──ZADD score──▶ Redis ZSET (sorted by score) ──ZREVRANGE 0 99──▶ Top-100 API
                              │
                              ├─ ZREVRANK user ─▶ "your rank" (around-me: rank±5)
                              └─ AOF/RDB + async ─▶ Postgres (durable source of truth)
```

## 工作原理

- **ZADD** 以 O(log N) upsert 一个玩家的分数。Redis 通过**跳表（skip list）**维护顺序，因此无需重新排序。
- **Top-N**：`ZREVRANGE board 0 99 WITHSCORES` 以 O(log N + 100) 返回前 100 名。
- **你的排名**：`ZREVRANK board user` 给出从 0 起算的位置；**我附近（around-me）**是 `ZREVRANGE rank-5 rank+5`——你附近玩家的切片。
- **持久性**：Redis 是内存型的。启用 **AOF**（append-only file）以便重放，并异步地把分数镜像到 **Postgres** 作为真正的记录系统（system of record），使 Redis 丢失是可恢复的。

## 面向数百万用户的分片

一个 ZSET 容纳数千万成员没有问题（受内存限制，100 万条约 100MB）。超过这个规模，或为了全球规模，**按分数范围分片**（0–1k、1k–10k…），使每个 shard 是一个连续区间——全局 top-N 只读取最高的那个 shard。避免按用户哈希分片：跨随机 shard 重新组合排名代价高昂。

## 面试视角

面试官希望看到你**求助于正确的数据结构**，而不是在 SQL 上 `ORDER BY score LIMIT 100`（它在每次命中时重新排序，并在写负载下崩溃）。好的回答会指出 ZSET；出色的回答会涵盖**"我附近"查询、并列（ties）、持久化和分片策略**。一个经典陷阱：忘记 Redis 是易失的，并把它当作真实来源——一次重启会清空排行榜，除非存在 AOF/RDB 或 DB 镜像。

## 权衡与故障

- **并列（Ties）。**相同分数会按成员的字典序排列，看起来是随机的。把一个决胜项编码进分数（例如 `score * 1e13 - timestamp`），使更早达成者排名更高。
- **热点键。**单个全局 ZSET 是一个 shard 上的一个键——一个写热点。缓冲/批量执行 `ZADD`，或使用时间分桶的排行榜（每日/每周）来分散负载。
- **一致性。**读取可能比异步 DB 镜像滞后数秒——对排行榜没问题，但不适合发奖；在颁奖前从 Postgres 对账。
- **内存成本。**数百万成员会消耗真实的 RAM；用 TTL 让赛季性排行榜过期。
- **何时不该用：**一个每分钟刷新一次、几千人的排行榜，作为缓存的 SQL 查询就足够了——当写入持续不断且排名必须即时时，Redis ZSET 才大放异彩。

架构

工作原理

面向数百万用户的分片

面试视角

权衡与故障

相关问题