Interview

Game Ranking Board — System Design

Requirements Analysis

Functional Requirements

Top-N 排行榜：展示全服 Top 10（可扩展到 Top 100），以及具体玩家的当前排名。
邻接排名：显示目标玩家前后各 4 名的排名和分数，方便玩家感知周围竞争。
分数更新：玩家赢得对局后分数即时变化，排名实时反映。
多时间窗口：每月开始新的锦标赛（新榜单），历史榜单可查询。

Non-Functional Requirements

实时性：分数变化必须即时反映在排名中，不允许仅呈现批量历史结果。
高并发：5M DAU（平均），25M MAU，每人每天约 10 场对局。
高可用：99.9%+，排行榜不可用不能阻塞游戏主流程。
低延迟：Top 10 查询 < 50ms，排名更新秒级可见。

Scale Estimation

指标	平均	峰值 (5x)
新增用户/秒	~50	~250
分数更新 QPS	~500	~2,500
Top-10 查询 QPS	~50	~250

估算依据：5M DAU / ~100K 秒 ≈ 50 请求/秒，峰值按 5x 计算。读操作（查询排名）远多于写操作（分数更新）。

Constraints and Assumptions

计分规则：每赢一局 +1 分，分数单调递增（简化设计；分数下降场景同样适用）。
范围：所有玩家参与排名，非仅头部玩家。
时间窗口：每月开始新锦标赛，榜单按月轮替。
并列处理：相同分数获相同排名；必要时按最先到达该分数的时间戳打破并列。
安全约束：分数提交必须由游戏服务器完成，客户端不可直接调排行服务 — 防止中间人攻击篡改分数。
客户端不可信：用户通过代理可直接修改请求参数，因此分数更新的权威来源必须是服务端。

Core Challenges

实时排名计算的规模挑战
- 传统 SQL 方案：SELECT ... ORDER BY score DESC 需要对百万级行全表扫描，单次排名查询耗时数十秒，不可接受。
- 即使加 LIMIT + INDEX 优化 Top-N 查询，获取任意用户的排名仍需全表扫描。
- 核心选型：Redis Sorted Set，底层基于跳表（skiplist），插入、更新、排名查询均为 O(log N)。
为什么 SQL 数据库不适合排行榜
- 排行榜是典型的持续变化的大数据集场景。SQL 排序在大规模、高频更新下性能急剧下降。
- 高频写入使缓存失效频繁，读操作几乎无法利用缓存。
- 结论：SQL 仅用于持久化点历史（审计与灾备），实时排名由 Redis 承担。
Redis Sorted Set 内部原理
- 两种数据结构组合：哈希表（user_id → score 映射）+ 跳表（score → user_id 排序）。
- 跳表在有序链表基础上增加多级索引，每级索引跳过下级约一半节点。
- 对于 25M 数据量，跳表只需遍历约 log₂(25M) ≈ 25 个节点即可定位，远优于 O(N) 遍历。
存储评估
- 每个条目：24 字符 user_id（24 bytes）+ 2 字节整数 score = 26 bytes。
- 25M MAU × 26 bytes ≈ 650 MB。加上跳表和哈希表开销约翻倍 → 1.3 GB。
- 单台现代 Redis 服务器（例如 16 GB 内存）完全足够承载全量数据。
多时间窗口的处理
- 每月创建独立的 Sorted Set key（如 leaderboard:2026-05），历史数据自然隔离。
- 月初新 key 自动创建，旧 key 可归档或保留查询。
并列排名与打破平局
- 相同分数的玩家获得相同 ZREVRANK 值。
- 如需打破平局（先达到该分数的排前面），维护一个独立的 Redis Hash 存储 user_id → 最近获胜时间戳，查询时辅助排序。

Architecture Design

API Design

以下 API 全部由游戏服务器调用，客户端不直接访问排行服务：

端点	方法	说明
`/v1/scores`	POST	游戏服务器验证对局后调用，更新胜者分数
`/v1/scores`	GET	返回 Top 10 玩家（user_id, name, rank, score）
`/v1/scores/{:user_id}`	GET	返回特定玩家的排名和分数

POST 请求体（仅由服务器发送）：

{
  "user_id": "mary1934",
  "points": 1
}

Data Flow

Client ──▶ Game Service ──▶ Leaderboard Service ──▶ Redis (sorted set)
                │                                        │
                │ (验证对局合法性)                         │
                │                                        ▼
                │                               MySQL (point 历史记录)
                ▼
          Leaderboard Service ◀── Client (查询排名)

分数提交流程：

玩家赢得对局 → Game Service 验证合法性
Game Service → Leaderboard Service 更新分数（ZINCRBY）
Leaderboard Service → MySQL 写入对局记录（异步，用于审计与灾备）

排名查询流程：

客户端直接请求 Leaderboard Service
Leaderboard Service → Redis ZREVRANGE（Top 10）或 ZREVRANK（个人排名）
→ MySQL 查询用户详情（显示名等）组装结果返回

Why No Message Queue

ByteByteGo 的原设计明确不使用 Kafka：当前需求仅涉及分数更新和排名查询，不需要多消费者（如通知、分析）。引入队列会增加不必要的延迟和运维复杂度。如果未来需要多玩家实时通知或回合制游戏，再引入消息队列。

Detailed Design

Data Model — Redis Sorted Set

Key 设计：

leaderboard:2026-05        # 当月榜单（每月轮替）
leaderboard:2026-04        # 上月榜单（保留可查）

核心 Redis 命令：

命令	复杂度	用途
`ZINCRBY leaderboard:2026-05 1 'mary1934'`	O(log N)	分数 +1（不存在则自动创建）
`ZREVRANGE leaderboard:2026-05 0 9 WITHSCORES`	O(log N + M)	获取 Top 10（降序）
`ZREVRANK leaderboard:2026-05 'mary1934'`	O(log N)	获取玩家排名
`ZREVRANGE leaderboard:2026-05 357 365`	O(log N + M)	获取排名 358~366 的玩家（4 above + 4 below）

Auxiliary Data Storage — MySQL

-- 用户表
CREATE TABLE user (
    user_id    VARCHAR(64) PRIMARY KEY,
    user_name  VARCHAR(128) NOT NULL
);

-- 对局记录表（审计 & 灾备恢复）
CREATE TABLE point (
    id         BIGINT AUTO_INCREMENT PRIMARY KEY,
    user_id    VARCHAR(64) NOT NULL,
    score      INT NOT NULL,
    created_at TIMESTAMPTZ DEFAULT NOW()
);
CREATE INDEX idx_point_user_time ON point (user_id, created_at DESC);

point 表记录每次得分事件，可用于：

播放历史查询
Redis 集群大规模故障后重建排行榜（离线脚本重放所有 ZINCRBY）

User Detail Cache (Optional)

Top 10 玩家查询最频繁，其用户详情（显示名等）可使用 Redis Hash 缓存：

HSET user:mary1934 name "Mary" avatar "https://..."

查询 Top 10 时，先 ZREVRANGE 获取 user_id 列表，再批量 HMGET 获取用户详情，避免每次请求都查 MySQL。

Scalability Design

Single Node to Sharding (500M DAU)

当 DAU 从 5M 扩展到 500M（100x）：

存储从 1.3 GB → 65 GB
QPS 从 2,500 → 250,000

单台 Redis 无法承载，需要分片。

Approach 1: Fixed Partitioning (by Score Range, Recommended)

将分数范围切分到不同分片：

Shard 1: scores 1-100
Shard 2: scores 101-200
...
Shard N: scores 901-1000

应用层维护一个二级缓存（user_id → 当前分数），用于路由到正确分片。

Top 10 查询：只查最高分分片（如 901-1000） — Top 玩家天然集中在这里。

用户排名计算：分片内本地排名 + 所有高分分片玩家总数（通过 INFO KEYSPACE O(1) 获取）。

跨分片迁移：玩家分数跨越分片边界时，从旧分片删除并插入新分片。

Approach 2: Hash Partitioning (Redis Cluster)

通过 CRC16(key) % 16384 自动分布到 16384 个槽位。

缺点：

Top 10 需要 scatter-gather：查询所有分片本地的 Top 10，在应用层合并重排
延迟取决于最慢的分片 — 分片越多延迟越可能被拖高
用户排名计算不直观

结论：固定分区更适合排行榜场景。

DynamoDB Alternative

如果不用 Redis，DynamoDB 需要 写分片（write sharding） 解决热分区问题：

分区键 = game#{year-month}#p{user_id % N}，排序键 = score

N 的选择：分区越多每分区负载越低，但 scatter-gather 复杂度越高，需压测权衡。
Top 10 查询：scatter-gather 从所有分区取各自 Top 10，应用层合并。
用户排名：无法精确计算，替代方案是 cron 任务分析每分区分数分布，返回百分位排名（如”Top 20%”），在大规模场景下可能更有意义。

Cloud Deployment (Serverless)

推荐使用 AWS Lambda + API Gateway：

API	Lambda Function
GET /v1/scores	LeaderboardFetchTop10
GET /v1/scores/{:user_id}	LeaderboardFetchPlayerRank
POST /v1/scores	LeaderboardUpdateScore

优势：自动扩缩，无需管理服务器。Lambda → Redis（ElastiCache）→ MySQL（RDS）。

Disaster Recovery

当 Redis 集群发生大规模故障时：

从 MySQL point 表读取全部对局记录
离线脚本按用户聚合分数并重放 ZINCRBY
重建完整的排行榜 Sorted Set

MySQL 是排行榜数据的持久化源（source of truth），Redis 是实时查询层。

Performance Optimization

Redis 写密集型部署：为故障恢复预留双倍内存（快照生成需要额外空间）。
生产部署前使用 redis-benchmark 验证目标硬件上的性能。
Top 10 结果加本地缓存（可选），但写入频繁时缓存命中率有限，收益需实测验证。

References

ByteByteGo — Real-time Gaming Leaderboard