专业书籍精读 · System Design Interview 卷一 · 第 7 章
System Design Interview Vol 1 · Ch 7 · Alex Xu · 2020
你下的每一单、发的每一条消息，系统都得给它一个编号——不能重、最好还能一眼看出谁先谁后。一台机器的时候，这事儿简单到不用想：数据库自己「从 1 开始往上加」就行。这一章讲的是：当后台变成几百台机器，这个「往上加 1」为什么会塌，以及怎么重新做一个。
把它想成一家连锁店的取号机。只有一家店时，取号机从 1 数上去，从不出错。开到 32 家分店以后，麻烦来了：每家店都从 1 开始数，全国就会冒出 32 个「3 号」——顾客拿着号来取货，店员不知道该给谁。
一、让所有分店都打电话回总部要号。号是不重了，可每发一个号都要打一次电话，慢；更糟的是总部一停电，全国 32 家店都发不出号。
二、每家店自己抽一串超长的随机乱码。确实撞不上，但这串码又长又看不出先后——你没法从两个编号里读出「哪单先下的」。
三、各店跳着数：1 号店数 1、33、65……，2 号店数 2、34、66……。听着挺妙，可一旦新开一家店或关掉一家，全国的数法都得重排一遍。
Twitter 想出的办法，是不再向任何人要号，而是用三样「本来就唯一」的东西现场拼一个：前一段写现在是几点几分几秒几毫秒，中间一段写我是哪家分店，最后一段写这一毫秒里我这家店发的第几个。
三段一拼，谁也不用问谁：不同毫秒，第一段就不一样；同一毫秒不同店，第二段不一样；同店同毫秒，第三段不一样。而且因为时间放在最前面，编号从小到大排，差不多就是从早到晚排——「有序」是白送的。这台「取号机」每家店每毫秒能发 4096 个号，够全国用 69 年。
这套编号的正确性，整个押在「每台机器的钟走得准」上：万一某台机器的时间被往回拨了一下，它就会把刚才那一毫秒重过一遍、把已经发过的号再发一次。
分布式编号的难点从来不是「别重复」——随便抽个长随机数就不会重。难的是又要不重、又要短、又要看得出先后，还不许机器之间互相打招呼。答案是把编号切成「时间 + 我是谁 + 这一刻的第几个」三段，用时间换掉了商量。
想进到具体机制、记号和示意图？ → 切到精读版
你以为分布式唯一 ID 难在「别重复」，其实不重复是四个约束里最容易的一个——一个足够长的随机数就够了。真正难的是让不重复、够短（塞进 64 位）、按时间大致有序、生成时不和任何机器商量这四件事同时成立。本章把四条路摆上桌逐一淘汰，最后落到 Twitter 的 Snowflake：把 64 位当预算，切成「时间戳 + 机器号 + 序列号」三段——有序性由「时间戳占最高位」白送，唯一性由「同机同毫秒序列号不重」保证，代价是整套正确性押在机器时钟上。
9.2×10¹⁸；「怎么花这 64 个 0/1」就是本章的核心设计题。09c93e62-50b4-468d-bf8a-c07e1040bfb2。卷一 Part II 案例章的第 4 道题。上承 Ch5 一致性哈希与 Ch6 键值存储——那两章回答「这条数据放哪台机器」，这一章回答「这条数据叫什么名字」，三章共用同一条主线：怎么在没有中心协调的前提下把事办了。下启 Ch8 短网址，那一章要把这里生成的 ID 用 base62 再编一次码。现实对应：订单号、消息 ID、Feed 条目 ID、日志 trace ID——凡是分库分表之后还想要一个全局主键的地方。
本章在需求澄清阶段敲定了五条：唯一、纯数字、能塞进 64 位、按日期有序、每秒 1 万个。这五条把答案空间收得极窄，也正是它们让最顺手的两个方案当场出局。
为什么 auto_increment 不成立？因为那个计数器是某一个数据库实例的私有状态。分库分表之后，两个库都从 1 开始数，第 10001 号订单会有两个。不解决会怎样：主键冲突 → 后写的那单覆盖先写的那单，两个用户的订单指向同一行数据，而且这种错误不会报警、只会静默地丢数据。
那直接上 UUID 呢？撞车概率确实可以忽略——v4 的 122 个随机位，要生成大约 10¹⁸ 个才有 50% 的机会碰一次。但它违反了另外三条需求：128 位不是 64 位、带横杠不是纯数字、随机值完全无序。最后这条代价最贵：随机主键没有时间局部性，每插一行都往 B-tree 的随机位置捅一刀，页分裂和随机 I/O 全都来了——这不是理论洁癖，是实测能差出一个数量级的写入吞吐（见 §「落到真实系统」里 RFC 9562 的原话）。
① 多主复制（multi-master replication）自增。让 k 台数据库都开自增，但把步长设成 k、起点错开：1 号库数 1、4、7……，2 号库数 2、5、8……。机制成立，唯一性也成立。死穴在伸缩：加一台机器就要把所有库的步长和起点重排一遍；而且跨机房时，ID 的数值大小和真实时间顺序完全对不上。本质上它还是把数据库当发号器用，写入天花板没变。
② UUID。各机器独立生成、零协调、零单点，是本章唯一「完全不需要通信」的方案，思路上最接近正确答案。但它把「够短」和「有序」两条需求整个牺牲掉了。
③ 票据服务器（ticket server）。Flickr 的做法：单独一台 MySQL 什么业务都不干，专门跑一列 auto_increment，谁要号谁来取。ID 又短又严格递增，实现只要几十行。死穴是单点：它一停，全站发不出 ID；做成两台主备，「两台之间怎么不撞」的老问题又回来了。而且每发一个 ID 就是一次网络往返，毫秒级的延迟直接加在每一次下单上。
④ Snowflake。不问任何人，靠三样本来就唯一的东西现场拼一个：现在的时刻、我是谁、我这一刻发到第几个。
逐段看，每一段都在回答一个具体问题。符号位恒为 0——Java 之类语言的 long 是有符号的，最高位一置就成了负数，主键变负号很多系统都受不了。41 位毫秒时间戳不从 Unix 纪元 1970 年算起，而是从自定义纪元算起（Twitter 用 1288834974657，即 2010-11-04）——把服务上线之前那四十年的位数全省下来，2⁴¹ 毫秒才够撑 69.7 年。5+5 位机器号给出 32 个数据中心 × 每个 32 台 = 1024 台上限，且在启动时静态分配、运行期不许变——中途改号就可能和别人撞。12 位序列号在同一台机器的同一毫秒内自增，4096 个封顶，跨到下一毫秒清零；真撞满了就自旋等下一毫秒。
关键洞察只有一句：时间戳在最高位，所以按数值大小排序就约等于按生成时间排序——「有序」这条需求是白送的，不花任何一次网络通信。但要说准：它只是大致有序（k-sorted）。两台机器在同一毫秒发的号，谁大谁小由机器号决定，和真实先后毫无关系；Twitter 在自己的 README 里承诺的也正是「1 秒内 k-sorted」。
这是本章最值得带走的一层：1 / 41 / 10 / 12 不是标准答案，是一张预算表。时间位换服务寿命，机器位换集群规模，序列位换单机峰值——三者相加恒等于 63，多给谁就得从另外两个身上扣。
算一笔具体的账：12 位序列意味着单机理论上限 4096 × 1000 = 409.6 万 个/秒，而本章白纸黑字的需求只有 1 万个/秒——差了 400 倍。也就是说，照搬 12 位序列的人，等于白扔了 8 位预算；那 8 位挪去时间戳，寿命能从 69 年变成一万多年；挪去机器号，集群上限能从 1024 台变成 26 万台。面试里能算出这笔账，比背出位布局有说服力得多。
票据服务器并非只能被淘汰——它的死穴是「每发一个 ID 都要一次网络往返」，而这个死穴可以单独治。号段（segment）模式把零售改成批发：应用一次向数据库申请一整段 [8001, 9000]，把段号记在本地内存里，之后 999 个 ID 全在进程内自增发出，段用完了再来领下一段。
代价要诚实写：实例重启会丢掉没用完的那半段，ID 序列出现空洞；多个实例并发领段之后，ID 只在实例内有序、跨实例乱序——「有序」这条需求打了折。
Snowflake 的唯一性证明只有一句话：「同一台机器在同一毫秒内序列号不重复，不同毫秒时间戳不同。」这句话只在时钟单调递增时成立。而 NTP 校正、闰秒、虚拟机时钟漂移、有人手工改时间，都会把本地时钟往回拨——一旦回拨，这台机器就会把刚过去的那一毫秒重过一遍，序列号也从 0 重来，于是发出和历史上一模一样的 ID。
工程上有三种处理，取向截然不同：① 检测到回拨就拒绝发号、直接抛异常（宁可服务不可用，也不发错号）；② 回拨幅度很小（几毫秒）就自旋等待，等真实时间追上再继续；③ 把「本机用过的最大时间戳」持久化到外部（美团 Leaf 用 ZooKeeper 记录），重启后不敢往回走。请注意第 ① 条背后的取向：Snowflake 在时钟出问题时选择牺牲可用性来保正确性——这和 Ch6 那个无主键值存储「先写下去再慢慢收敛」的取向正好相反。
表 1 · 五种发号方案：什么场景该选什么
| 方案 | 机制一句话 | 形态 | 时间有序 | 要不要协调 | 主要代价 |
|---|---|---|---|---|---|
| 多主自增 | k 台库都自增，步长设成 k、起点错开 | 64 位数字 | 否（跨库乱序） | 不用（但要静态配好） | 加减机器要全盘重排；写入天花板还在数据库 |
| UUID v4 | 各机器抽 122 个随机位 | 128 位、带横杠 | 否 | 完全不用 | 长一倍、非数字；随机主键破坏索引局部性 |
| 票据服务器 | 单独一台 MySQL 专跑 auto_increment | 64 位数字 | 严格递增 | 每个 ID 一次往返 | 单点 + 毫秒级延迟压在每次下单上 |
| 号段模式 | 一次领 1000 个，本地内存慢慢发 | 64 位数字 | 实例内有序 | 每 1000 个一次往返 | 重启丢半段（ID 空洞）；跨实例乱序 |
| Snowflake | 时间戳 + 机器号 + 序列号现场拼 | 64 位数字 | k-sorted 大致有序 | 发号时零协调（协调挪到启动分配机器号） | 正确性押在时钟上；机器号要人管；69 年寿命 |
表 2 · 同样 63 位，三家公司分出三种预算（均取自各自公开仓库的默认配置）
| 实现 | 时间位 | 机器位 | 序列位 | 服务寿命 | 集群上限 | 单机峰值 |
|---|---|---|---|---|---|---|
| Twitter Snowflake | 41（毫秒） | 10 | 12 | ≈ 69 年 | 1024 台 | 409.6 万/秒 |
| Sony Sonyflake | 39（每格 10 ms） | 16 | 8 | ≈ 174 年 | 65536 台 | 2.56 万/秒 |
| Baidu UidGenerator | 28（秒） | 22 | 13 | ≈ 8.5 年 | 419 万节点 | 8192/秒 |
三家拿同样的 64 位，按各自业务把预算重分了一遍：Sony 要更多机器、更长寿命，就把单机峰值砍到 1/160；百度做容器化，机器号一给就是 22 位（容器来去频繁、号要够撒），代价是寿命只有 8.5 年、必须定期换纪元。这张表本身就是本章的答案：位分配是设计参数，不是常数。
Snowflake 是「无协调设计」最短、最好讲的一道样板题——它示范了一种通用手法：当你需要全局唯一但不想全局通信时，就把「全局唯一」拆成几个各自天然唯一的本地事实，再拼起来。这个手法在幂等键、分布式追踪的 trace ID、对象存储的对象名上到处可见。
今天真实系统里到处是它的影子：Discord 的所有对象 ID 都是 snowflake（42 位时间戳 + 5 位 worker + 5 位进程 + 12 位自增，纪元定在 2015 年），MongoDB 的 ObjectId 是同一思路的 12 字节版（4 字节秒级时间戳 + 5 字节进程随机值 + 3 字节自增计数器）。更值得注意的是标准化那一步：UUIDv7 在 2024 年被写进 RFC 9562，把「时间戳放最高位」从工程土办法变成了行业标准，PostgreSQL 18 已内置 uuidv7()——代价仍然是 128 位而不是 64 位。
2¹⁶ 而非 2¹⁰，代价是每 10 ms 只能发 256 个——直接印证「位分配是可调预算」。sony/sonyflake ↗uuidv7()，省掉整套自建发号服务与机器号管理，代价是 128 位而不是 64 位。「一定要自建 Snowflake」已经不是默认答案了。① 真正的题面不是「别重复」，而是不重复 + 够短（64 位）+ 按时间有序 + 零协调四条同时成立；四条互相打架，所以答案必然是取舍。
② auto_increment 死在「计数器是单个数据库实例的私有状态」；UUID 活下来但违反了另外三条，尤其随机主键破坏 B-tree 索引局部性。
③ 票据服务器（Flickr）短且严格递增，死在单点 + 每个 ID 一次网络往返；号段模式把往返频率降到 1/1000 救回一半，代价是重启丢段、跨实例乱序。
④ Snowflake = 1 符号位 + 41 毫秒时间戳 + 5 数据中心 + 5 机器 + 12 序列：69 年寿命、1024 台、每机每毫秒 4096 个。
⑤ 有序性的全部来源是时间戳占最高位，不花任何通信；但只是 k-sorted 大致有序，不是严格单调。
⑥ 位分配是预算不是常数：时间位换寿命、机器位换规模、序列位换峰值，三者抢 63 位。Sony（39/16/8，174 年）与百度（28/22/13，419 万节点）就是两种不同的分法。
⑦ 最大的软肋是时钟回拨：NTP 把表往回拨一下，机器就重放同一毫秒 + 归零的序列号，发出完全相同的 ID。对策是拒绝发号 / 自旋等待 / 外部记录最大时间戳——第一种等于用可用性换正确性。
⑧ 协调没消失，只是从「每次发号」挪到了「每次启动分配机器号」；容器化之后这笔账变贵了，这是最常被忽略的一项。
⑨ 通用手法：把全局唯一拆成几个天然唯一的本地事实再拼起来。UUIDv7 进 RFC 9562（2024）、PostgreSQL 18 内置 uuidv7()，说明这条直觉已经成了标准。