专业书籍精读 · System Design Interview 卷二 · 第 10 章
System Design Interview Vol 2 · Ch 10 · Alex Xu & Sahn Lam · 2022
手游里的周榜、健身 App 里的步数榜、直播间的打赏榜——它们看起来只是「把人按分数排一排」。这一章就是从头造一个这样的榜：几百万人同时在玩，分数每秒都在变，还要立刻告诉每个人「你排第几」。
听起来必须动用一大堆机器，可这一章最先做的事是拿计算器算一遍。算完发现：五百万活跃玩家的月榜，数据只有几百 MB，忙的时候每秒也就两三千次改动——一台机器就装得下、也忙得过来。
这才是整章真正的教学点：先算账，再谈架构。很多「必须上分布式」的直觉，一算就散了。
用普通数据库存一张分数表，「取前十名」很容易——按分数排个序，拿最上面十行。
难的是另一个问题：「我排第几？」数据库没有「第几」这个概念，它只能老老实实数：比我分高的人有多少个？如果你排在两千万人的中游，它就得数一千万个人，才能回你一句「第 1000 万名」。每个人都这么问一次，机器直接跪。
① 排名要能「跳着数」。把所有人按分数排成一队，只在最底下一层挨个连起来，再往上搭几层「快车道」——高层一步就跨过一大段人。关键在于：每一步都顺手记下「我这一跳跨过了几个人」。于是要算排名，只需沿着快车道跳几步，把跨过的人数加起来，而不用一个一个点名。几千万人也只要十几步。
② 一个榜就是一样东西，切不开。如果人多到一台机器放不下，直觉是拆成几台。可「排第几」问的是全场的名次——一旦把人随机分到几台机器上，每台只知道自己这几个人的顺序，谁也答不出全场第几，只能挨个问一遍再拼。
③ 所以只能按分数段来分。不是随机分人，而是按分数划段：900 分以上的放一台，800～899 的放另一台。这样「你排第几」= 比你那段高的几台机器各有多少人（一个数就够）+ 你在自己这段里排第几。代价是分数一旦挤进同一段，那台机器就被压垮。
④ 别对所有人都较真。前十名必须一分不差，但第 800 万名和第 801 万名的区别，其实没人关心。给中间的大多数人一句「你在前 12%」，比精确到个位便宜得多，而且他们更看得懂。
这套榜为了快，住在内存里——机器一重启就可能丢掉最近几秒到几分钟的分数，所以真账还得另外记一份在硬盘上，随时能把榜重建出来。
排行榜的难点从来不是「排序」，而是「我排第几」——那是个必须看全场才能回答的问题。解法是给排好的队伍加几层快车道，并在每一跳上记下跨过了多少人，于是排名能跳着数出来。真要拆成多台机器时，只能按分数段拆、不能按人随机拆，否则全场名次就散了。而对绝大多数人，一句「你在前 12%」比精确名次划算得多。
想进到具体机制、记号和示意图？ → 切到精读版
这一章表面是「给游戏做个排行榜」，真正教的是两件事。第一件反直觉：先算账，再谈架构——500 万日活听起来非分布式不可，算完发现峰值只有约 2,500 QPS、数据只有几百 MB，一台 Redis 就够了。第二件是全章的灵魂矛盾：排名是一个全局量，而分片是一次局部化，两者天生互斥。于是这一章所有的设计——跳表节点上的跨度、按分数分桶、近似百分位——都是在同一个问题上讨价还价：怎么在不看全部数据的前提下，说出「你排第几」。
ZADD（写）、ZINCRBY（加分）、ZREVRANGE（取前 N）、ZREVRANK（查名次）。O(log n)，即「数据翻一百万倍，步数只多二十步」。16384 个槽之一，槽再分配给节点。同一个键永远整个落在一个节点上。卷二第 10 章。上承 Ch9「对象存储」——那一章是自己造一个存储组件，这一章回到「用现成组件搭系统」，但把卷一 Ch2「粗略估算」那门手艺用到了极致：全章最重要的决定，是在算完账之后做出的。现实对应物是手游周榜月榜、Strava 之类健身 App 的排名、电商实时销量榜、直播打赏榜，以及一切「实时名次」类需求。
需求很小，但每一条都咬人：① 显示前十名；② 显示某个用户的确切名次；③ 显示某个用户上下各四名；④ 分数一变，榜要实时反映。前两条看着像同一件事，其实差着一个数量级的代价——这正是整章的发动机。
书里的规模假设与算法值得原样记住（这是面试里能当场复述的那种算账）：
10^5 秒，摊平就是每秒约 50 人开始一局；按峰值 5 倍算，250 人/秒。24 字节 + 分数 2 字节 = 26 字节，25M × 26B ≈ 650MB。结论是这一章最该记住的一句：2,500 QPS 和几百 MB，一台 Redis 实例绰绰有余（单实例执行简单命令的能力在每秒十万次量级）。这里有个诚实的修正：650MB 只是裸数据，有序集合的跳表节点和哈希表条目都要带指针，实际内存通常是裸数据的数倍——但即便如此，仍是单机量级。算账的价值不在于算得多准，而在于它能告诉你「不必做什么」。
那难点在哪？在需求②。关系数据库里，SELECT COUNT(*) FROM scores WHERE score > ? 就算走索引，也要真的把上面那些行数一遍。一个排在 2500 万人中游的玩家，一次查询要扫一千万条索引项。「排第几」不是排序问题，是计数问题——而计数天然是 O(n) 的。整章的所有机巧，都在把这个 O(n) 压下来。
Redis 的有序集合同时维护两套索引：一张哈希表（成员 → 分数，按人查分是 O(1)），和一条跳表（按分数有序，负责取范围和查名次）。
跳表的直觉是地铁：底层是站站停的慢车（所有节点串成有序链表），上面叠几层快车，每层跳过的站越来越多。查一个位置时先坐最快的车冲过去、坐过头就退回下一层，O(log n) 步到站——两千五百万人也只要二十多步。
但光是跳表还答不出名次。真正的机关是：每条指针上额外记一个「跨度」——这一跳跨过了几个节点。于是 ZREVRANK 不需要数人头，只要沿路把跨度加起来。名次从「数 n 个人」变成「加 log n 个数」，这一章的核心难题在这里被一笔勾销。
顺带两个实现细节值得知道：同分时按成员名的字典序排（所以并列名次的顺序是确定的、但和先来后到无关）；底层链表带反向指针，因此从高分往低分遍历（ZREVRANGE）和正向一样快。
算完账我们知道单机够用。但书里仍然把「如果不够呢」推到底——因为这一推，才暴露出排行榜和普通业务数据的本质差别。
先说一个常被误解的事实：Redis Cluster 不会替你分排行榜。它按键名哈希到 16384 个槽，而整个排行榜只有一个键——它整个躺在某一个节点上，扩集群一点忙也帮不上。要分片，只能在应用层把一个榜切成多个键。切法只有两种：
按用户哈希切（把玩家随机分到 N 个榜）：写入分布完美均匀，但名次彻底失效——每片只知道自家人的顺序。要算全局名次，得问遍所有分片再归并；要取全局前十，也得各取前十再合并。分片数越多越贵，还受最慢那片拖累。
按分数分桶切（900+ 一片、800–899 一片……）：这才是能用的那条路。全局名次 = 比我这桶高的所有桶的人数之和（每桶一个计数，ZCARD 级别的便宜操作）+ 我在本桶内的名次。取前十也只需从最高的那个桶取。代价同样诚实：分布会漂移——游戏平衡性一改、赛季一过，大家的分数就挤到某几个桶里，那几片成了热点，而且桶的边界很难在线重划。
这个对比值得记成一条通则：分片键必须和查询的「作用域」对齐。普通业务查的是「某个用户的数据」，按用户分片天经地义；而排名查的是「全场」，于是必须按分数——也就是被查询的那个维度——来分。
就算分片做对了，「给每个人算确切名次」在几千万人的规模上仍然是笔冤枉钱。书里给的出路是放宽需求：前十名必须精确（那是产品的门面），某个玩家上下各四名也不贵（先 ZREVRANK 拿到自己的位置，再 ZREVRANGE 取相邻那一小段，一次范围读就够）。
真正贵的是「第 812 万名」这种中段精确值——而它恰恰对用户没有意义。替代方案是近似百分位：按分数把人分成若干桶、只维护每桶人数，回答「你在前 12%」。代价从「实时维护全局名次」降到「定期刷新几十个计数」，而答案反而更好懂。
面试里这一步比任何技术选型都值钱：能主动指出「需求②对中段用户可以降级」，说明你在设计系统，而不是在实现需求文档。
还剩两个容易被跳过、但一跳过就出事的问题。
客户端能不能直接写 Redis？不能。一是分数必须由服务端判定，客户端报分等于把作弊权交出去；二是把 Redis 凭证发到几百万台手机上，等于没有凭证。所以路径必须是：客户端 → 游戏服务（校验、判定得分）→ 排行榜。
Redis 能不能当真相源？不能。它是内存结构，靠快照和追加日志落盘：追加日志按每秒刷盘时，最坏可能丢掉数十秒的写；只用快照则可能丢掉几分钟。所以分数要同时写进一个持久的账本（关系数据库，或经由 Kafka 之类的日志同时喂给排行榜和数据仓库），Redis 里的榜被定义成「可以随时从账本重建的派生视图」。这样「Redis 集群崩了」就从事故降级成一次重建。
顺带两个设计细节：榜里只放用户 ID 和分数（那条 26 字节才成立），昵称头像另去数据库取并缓存；月榜用带月份的键名（形如 rank:2026-09），月底整个键一删就完成赛季重置。
表 1 · 三种实现方式：差别不在快慢，在「我排第几」贵不贵
| 方案 | 好在哪 | 代价（诚实说） | 什么时候选它 |
|---|---|---|---|
| 关系数据库 | 零新组件；取前十走索引即可；天然持久、可做账本 | 查名次是计数，O(n)：中段玩家一次要扫上千万条索引项；实时更新还会让索引持续抖动 | 玩家数万级、或名次只需离线日更 |
| Redis 有序集合 （书里的选择） | 写与查名次均 O(log n)；一个命令搞定加分；单实例即可扛住本章全部流量 | 不是真相源（要另配持久账本）；内存按 GB 计费；单个榜是单键，无法靠集群横向扩 | 实时榜的默认答案——先用它，别提前分片 |
| NoSQL（如 DynamoDB） | 持久化与弹性容量由托管服务负责；天然多副本 | 名次要自己造：全榜同一分区键会撞热分区，拆成 N 个分区后取前十又变成扇出归并 | 已重度依赖该托管栈、且能接受近似名次 |
表 2 · 真到了必须分片那天：两种切法
| 切法 | 什么变好 | 什么变贵（诚实说） | 适用判据 |
|---|---|---|---|
| 按用户哈希 | 写入分布绝对均匀；扩缩容简单；Redis Cluster 开箱即用 | 名次彻底失效：每次查名次 / 取前十都要扇出全部分片再归并 | 只要「个人历史分数」、不要全局名次时 |
| 按分数分桶 | 名次 = 高分桶计数之和 + 桶内名次；取前十只问最高那桶 | 分布漂移即热点：赛季或平衡性一变，人挤进某几个桶；边界难以在线重划 | 必须保留精确全局名次时唯一可行的切法 |
| 不切（先别分片） | 零复杂度；本章算完的规模下完全够用 | 单节点上限压在头顶：内存和单线程吞吐都有天花板，要提前想好越界那天的路 | 算完账发现够用时——也就是绝大多数情况 |
表 3 · 名次的精确度：把需求分层，是最便宜的优化
| 需求 | 怎么做 | 代价（诚实说） |
|---|---|---|
| 前十名 | 一次 ZREVRANGE 0 9，或只问最高分那个桶 | 几乎免费——但必须绝对精确，这是产品的门面 |
| 自己上下各四名 | 先取自己名次，再读相邻的一小段范围 | 一次定位 + 一次短范围读，仍然便宜 |
| 中段玩家的确切名次 | 严格维护全局名次 | 最贵的一项，且没人关心：第 812 万名和第 813 万名对用户毫无差别 |
| 「你在前 12%」 | 按分数分桶只维护每桶计数，定期刷新 | 答案是近似的、有刷新延迟；换来的是成本掉一个数量级，而且用户更看得懂 |
这一章的迁移价值远超游戏：任何「实时名次 / 实时 Top N」都是同一道题——热搜榜、电商实时销量、直播打赏、风控里的异常分数排序。判据也永远是同一条：先问这个「第几」到底要多精确、给谁看，再决定要不要为它买一套分布式。
src/t_zset.c · github.com/redis/redisredis.conf 注释 · github.com/redis/redisN 个分区键再扇出归并，正是为了绕开这一点。出处：Elhemali 等，《Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service》，USENIX ATC 2022。该来源域名被本次运行的出口代理拦截，故只留文字出处。650MB 当成真实内存。那只是裸数据；跳表节点与哈希表条目的指针开销会让实际占用是它的数倍。容量规划照裸数据买内存，是会出事的。① 这一章真正的教学点是顺序：先算账，再谈架构。算完发现 500 万 DAU 只需一台 Redis。
② 记住这串算式：5M DAU ÷ 10^5 秒 ≈ 50 人/秒，峰值 ×5；人均 10 局 → 约 500 QPS，峰值 2,500 QPS；月榜 25M × 26B ≈ 650MB。
③ 难的不是排序，是「我排第几」——关系数据库只能数，是 O(n)。
④ 有序集合 = 哈希表（按人查分 O(1)）+ 跳表（按分排序）；名次靠指针上的跨度累加得出，O(n) 计数变成 O(log n) 加法。
⑤ 排名是全局量，分片是局部化——这是全章的灵魂矛盾。
⑥ Redis Cluster 按键分 16384 个槽，而一个榜只有一个键：它不会替你分排行榜。
⑦ 按用户哈希分片毁掉名次；按分数分桶才留得住名次，代价是分布漂移带来的热点桶。
⑧ 通则：分片键必须和查询的作用域对齐——查全场，就按被查的那个维度分。
⑨ 把需求分层最省钱：前十名必须精确，自己上下四名很便宜，中段用户给近似百分位就够。
⑩ 两条红线：客户端不许直连（分数必须服务端判定）；内存榜不是账本，要能从持久账本随时重建。