Day 11 Medium Unique ID Snowflake UUIDv7 KSUID/ULID

唯一 ID 生成 — 时间、随机与索引的三角博弈Unique ID Generation: UUID, Snowflake, KSUID, ULID

问题场景 + 需求约束

设计一个全球聊天产品的消息 ID（参考 Discord / Slack / WhatsApp）。规模假设：3 亿 DAU、峰值 100w 消息/秒、消息按 channel 分片到上百个 Cassandra 节点。每条消息要分配一个 ID，决定它在 DB 中的物理位置、在客户端的排序、在 URL 里的样子。

关键需求：

全局唯一：跨数据中心，峰值 100w/s 不能冲突。
大致时间序：按 channel 拉历史消息，WHERE id < cursor 翻页要走索引。
紧凑：每条消息一个 ID，128-bit vs 64-bit 一年下来差几十 TB（带宽 + 存储 + 索引）。
无中心瓶颈：不能让一个 ID 服务挂掉就全站不能发消息。
不泄露业务量：自增 ID 让对手通过 id_today - id_yesterday 算出日活，是早期 Twitter 的隐私事故。
客户端可生成：离线发消息时本地先生成 ID，上线后服务端不重新分配，保证幂等。

高层架构

graph TD
    ZK["ZooKeeper / etcd
worker_id 分配"]
    NTP["NTP / PTP 时钟同步
检测回拨"]
    APP1["App 实例 #1
嵌入 ID lib
worker_id=42"]
    APP2["App 实例 #2
嵌入 ID lib
worker_id=43"]
    APPN["App 实例 #N
worker_id=...
(最多 2¹⁰=1024)"]
    CLIENT["移动客户端
UUIDv7 本地生成
离线消息"]
    CASS[("Cassandra
partition by channel
cluster by id DESC")]

    ZK -.分配.-> APP1 & APP2 & APPN
    NTP -.同步.-> APP1 & APP2 & APPN
    APP1 & APP2 & APPN --> CASS
    CLIENT -->|带 client_id| APP1

    classDef coord fill:#0e2030,stroke:#5eead4,color:#e8eef5
    classDef app fill:#1a2530,stroke:#64c8ff,color:#e8eef5
    classDef client fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef store fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class ZK,NTP coord
    class APP1,APP2,APPN app
    class CLIENT client
    class CASS store

ID 生成是 library 模式，没有独立服务可挂；ZK 只在启动时分配 worker_id，运行时无依赖

组件职责：ZooKeeper 启动时给每个 app 实例分一个 worker_id（10 bit = 1024 个槽），重启时归还。NTP 保证机器时钟不漂移（一般 < 10ms 误差），时钟回拨是 Snowflake 系命门。App 嵌入 ID lib 直接出 ID，无网络调用。客户端离线场景用 UUIDv7 本地生成，服务端原样接受（保证发送幂等）。

关键技术点

1. UUID 各版本：v4 随机 vs v7 时间序

原理：UUID 是 128-bit。v4 122 bit 全随机，冲突概率 ~2⁻¹²²，无需协调，但对 B-tree 索引是灾难——每次插入打在随机叶子页，page split + cache miss 暴增。v7（RFC 9562 2024 年定稿）前 48 bit 是毫秒级 Unix 时间戳，后 74 bit 随机/单调，字典序 = 时间序，新插入永远在 B-tree 右侧，page split 几乎为零。

Trade-off：

v4：✅ 无中心、客户端可生成；❌ Postgres / MySQL 主键用 v4 时，插入吞吐随表增大快速下降（buffer pool 装不下整个索引就崩）；占 16 字节存储，char(36) 形式 36 字节，是 BIGINT 的 2-4 倍。
v7：✅ 索引友好（B-tree 顺序插入）、保留 UUID 生态（128-bit、字符串 API 不变）、跨语言库就绪；❌ 时间戳暴露生成时间，私密场景慎用；时钟回拨需自己处理。
v1（MAC + 时间）：基本不用——泄露 MAC 地址、且时间戳排在低位，仍是随机插入。

# UUIDv7 极简生成 (Python，RFC 9562)
import os, time
def uuid7() -> bytes:
    ts_ms = int(time.time() * 1000)          # 48 bit
    rand_a = int.from_bytes(os.urandom(2), 'big') & 0x0FFF  # 12 bit
    rand_b = int.from_bytes(os.urandom(8), 'big') & ((1<<62)-1)  # 62 bit
    # 组装: ts(48) | ver=7(4) | rand_a(12) | var=10(2) | rand_b(62)
    n = (ts_ms << 80) | (0x7 << 76) | (rand_a << 64) | (0b10 << 62) | rand_b
    return n.to_bytes(16, 'big')

# Postgres 17+ 原生支持: gen_random_uuid() 仍是 v4, 但社区有 uuidv7() 扩展

现实案例：

Postgres 社区 benchmark：同表千万行插入，UUIDv4 比 UUIDv7 慢 3-10 倍（v7 顺序写、v4 随机写）；BRIN 索引在 v7 上能用，v4 上完全无效。
Stripe API 对象 ID：用 ch_/pi_ 前缀 + 16+ 字节随机，是 v4 风格（KV 存储不怕随机插入，且要求强抗猜测）。
OpenJDK：JEP 已支持 UUIDv7，标志 v7 正式进入主流。

2. Snowflake 类 ID：64-bit 三段式

原理：Twitter 2010 年开源 Snowflake，64 bit = 1 符号位 + 41 bit 毫秒时间戳（自定 epoch，可用 ~69 年）+ 10 bit worker_id（1024 台机器）+ 12 bit 序列号（同毫秒同机器最多 4096 个）。4096 × 1024 = 419 万 ID/ms = 41 亿/秒，远超任何单一系统需求。比 UUID 省一半空间，且天然大致时间序。

Trade-off：vs UUIDv7 / vs DB sequence

方案	位宽	峰值/秒	需要协调	致命问题
DB auto_increment	BIGINT 64	单实例 ~10w	无	单点、泄露业务量
UUIDv4	128	无上限	无	索引插入慢
Snowflake	64	41 亿	worker_id 分配 + 时钟	时钟回拨
UUIDv7	128	无上限	无	占空间 2 倍
DB segment（号段）	64	取决于段长	DB 一次拿 1000 个	重启浪费段

# Snowflake 核心 (Python 伪代码)
class Snowflake:
    EPOCH = 1672531200000  # 2023-01-01 自定起点
    def __init__(self, worker_id):
        assert 0 <= worker_id < 1024
        self.worker_id = worker_id
        self.seq = 0
        self.last_ts = -1
    def next_id(self):
        ts = int(time.time() * 1000)
        if ts < self.last_ts:
            raise ClockBackwardError(self.last_ts - ts)  # 见下一节
        if ts == self.last_ts:
            self.seq = (self.seq + 1) & 0xFFF
            if self.seq == 0:
                ts = self._wait_next_ms(self.last_ts)  # 等下一毫秒
        else:
            self.seq = 0
        self.last_ts = ts
        return ((ts - self.EPOCH) << 22) | (self.worker_id << 12) | self.seq

现实案例：

Twitter：原始版本，2010-09-21 上线，所有 tweet ID 从此非连续；2014 后切到内嵌库模式。
Discord：每个 message/user/channel 都是 Snowflake，bit 分配略调；前端从 ID 直接解出创建时间（不用查 DB）。
Instagram：41 bit 时间 + 13 bit shard_id + 10 bit seq，在 Postgres 内用 stored procedure 生成，不依赖外部服务——『把 Snowflake 写进数据库』的经典范式。
Sony Sonyflake：39 bit 10ms 精度时间戳 + 8 bit seq + 16 bit machine_id，换来 174 年寿命 + 65536 台机器，适合机器多但 QPS 不极端的场景。

3. 时钟回拨：Snowflake 的命门

原理：Snowflake 的唯一性完全依赖时间戳单调递增。NTP 一次回拨 100ms，机器在这 100ms 内生成的 ID 就可能和过去重复。leap second（闰秒）、虚拟机暂停恢复、运维误操作改时间，都触发过生产事故。

三种主流解法：

① 等待回到原时刻（最简单）：if ts < last_ts: sleep(last_ts - ts)。代价：回拨大时阻塞 ID 生成 = 阻塞写入，超过 5ms 就直接抛错让上层降级。Twitter 原版做法。
② 用『逻辑时间』代替系统时间：内存里维护 logical_ts = max(system_ts, last_ts + 1)，永不回退。代价：与真实时间逐渐漂移；适合短暂回拨。
③ 借 worker_id 做逃生（Sonyflake / Baidu UidGenerator）：检测到回拨直接换一个 worker_id 启动（ZK 还有空闲槽），旧 worker_id 等冷却。代价：worker_id 池要预留。
④ 关 NTP 的 step 模式，只允许 slew（运维方案）：NTP 用 -x 参数让时间『慢慢追』而不是『跳』，物理上消除回拨。生产标配，但仍需代码兜底。

# 处理回拨的鲁棒版本
def next_id(self):
    ts = now_ms()
    delta = self.last_ts - ts
    if delta > 0:
        if delta <= 5:          # 小回拨，等
            time.sleep(delta / 1000)
            ts = now_ms()
        elif delta <= 2000:     # 中回拨，用逻辑时钟
            ts = self.last_ts + 1
        else:                   # 大回拨，拒绝服务
            raise ClockBackwardError(delta)
    # ... 正常分配 seq

真实事故模式：VM 从 snapshot 恢复后时间倒退几小时；某次 NTP 配错指向有问题的源，全集群同时倒退 30 秒，生成的 ID 与历史 ID 重复，引发主键冲突写入失败——这种情况只能下线该实例 + 等到真实时间超过 last_ts。

4. ULID / KSUID / UUIDv7 三剑客对比

原理：三者都想解决『字典序 = 时间序 + 全分布式 + 无中心』。差别在 bit 数、编码、是否单调严格。

	UUIDv7	ULID	KSUID
位宽	128	128	160
时间精度	毫秒	毫秒	秒
随机位	74 bit	80 bit	128 bit
文本编码	hex+横线 (36 字符)	Crockford Base32 (26 字符)	Base62 (27 字符)
单调保证	同毫秒内可选	同毫秒严格单调（spec 要求）	无（秒级）
标准化	IETF RFC 9562	社区 spec（GitHub）	Segment 开源
典型场景	替换数据库 PK	面向用户的短 ID	事件流、日志

怎么选：

新项目 DB 主键：UUIDv7（标准化、生态、PK 友好）。
需要在 URL / UI 出现：ULID（26 个字符，Base32 无 I/L/O/U 不易看错）或 KSUID（27 字符 Base62）。
每秒只有几百到几千 ID：KSUID 简单够用，秒级时间戳无回拨敏感。
峰值 100w/s、严格单调：选 Snowflake（64 bit 省 50% 空间）或 ULID（spec 保证同毫秒递增）。

# 三种格式的字符串样例
UUIDv4:  6ba7b810-9dad-11d1-80b4-00c04fd430c8   ← 36 字符
UUIDv7:  018f1c2e-a31b-7c12-9a4b-3e1c2d4f5a6b   ← 36 字符, 前 48 bit 是时间
ULID:    01HXY8K5T4ZNQ9P2M3RVW6S0BC             ← 26 字符
KSUID:   2QqRwSdEf8VnT1bAaCpYlGmHkXjZ           ← 27 字符
Snowflake: 1773294523890106368                  ← 19 位十进制数字

现实案例：

Segment：KSUID 开源仓库声明在事件管道中产生数万亿个 KSUID；20 字节布局（4 字节时间戳 + 16 字节随机），秒级精度刚好够事件去重。
ULID：canonical spec 强制要求同毫秒内 ID 单调递增（实现要用 monotonic factory）；MongoDB ObjectID 是类似思路（12 字节 = 4 时间 + 5 random + 3 counter）。
Stripe：用带类型前缀的随机字符串（cus_, ch_），不属任何标准，但展示了『可读性 + 类型安全 + 抗猜测』的产品级 ID 设计。

扩展与优化

worker_id 不够用：10 bit = 1024 上限，容器化时代很快撞墙。Discord / Sonyflake 通过缩短时间戳精度（10ms 一格）省下 bit 给 worker_id。
多区部署：bit 拆分为 region(3) + dc(3) + worker(4)，让 ID 也能定位物理位置。Twitter 内部就是这样。
client_id 段：移动端离线生成 ID 时，用本地 UUIDv7 + 客户端 token 做幂等，服务端不重新分配。WhatsApp 用这种方案保证发送失败重试不重复。
从 UUIDv4 迁移到 UUIDv7：直接换生成函数，旧数据保留——v7 的版本号 4 bit 与 v4 不同，类型不冲突；索引性能会随新数据占比慢慢恢复。
监控信号：每秒生成数（是否接近 4096/ms/worker 上限）、时钟漂移、worker_id 冲突告警。

常见陷阱 + 面试问题

陷阱 1：把 UUIDv4 当 PK 用在大表。"UUID 反正全球唯一" 听起来安全，但 B-tree 插入性能崩塌往往要写到 5000 万行才发现，那时已经晚了。新项目直接 v7。

陷阱 2：以为 Snowflake 一定全局递增。它只是大致时间序——同毫秒内不同 worker 生成的 ID 大小由 worker_id 决定，不是真单调。代码不能依赖『新 ID 一定 > 旧 ID』。

陷阱 3：把 ID 当时间戳用。从 Snowflake 解出来的时间是生成时间，不是事件时间；客户端离线时事件时间和生成时间可能差几天。

陷阱 4：worker_id 被复用。机器漂移、容器调度让两个进程拿到同一个 worker_id → 必产生重复 ID。ZooKeeper 临时节点 + 心跳是标配。

陷阱 5：泄露业务量。自增 ID 让对手算出『今天发了多少条消息』。早期 Twitter 因此暴露增长数据。任何对外可见的 ID 都要至少加随机段。

面试可能追问：

峰值 1000w/s，64-bit Snowflake 够不够？bit 分配怎么改？
跨数据中心生成 ID 怎么避免冲突？datacenter_id 占几位？
UUIDv4 用作 MySQL 主键有什么问题？v7 怎么解？给出实测数字量级。
时钟回拨发生时，你设计的系统怎么响应？多大回拨需要熔断？
客户端能不能本地生成 ID？要满足什么前提？

深入资源

Twitter Engineering: Announcing Snowflake (2010) — 原始论证，看『为什么 ZooKeeper + 64 bit + 时间戳』
Instagram Engineering: Sharding & IDs at Instagram — 把 ID 生成做进 Postgres 的范式，工程极简主义
Discord: How Discord Stores Trillions of Messages — Snowflake ID 如何与 Cassandra 分片协同
RFC 9562: Universally Unique IDentifiers (UUIDs) — 2024 年新版，包含 v6/v7/v8 三种时间序变体
ULID spec & Segment KSUID — 两套 sortable ID 的 reference 实现

深入思考

1. UUIDv4 做 MySQL 主键插入性能崩，根本原因不是『随机』本身。到底慢在哪？为什么 UUIDv7 能解？

不是 CPU 慢、不是磁盘带宽不够，是 buffer pool 命中率崩。InnoDB 是聚簇索引——主键决定数据在磁盘上的物理位置。

顺序主键（自增 / UUIDv7）：新插入永远在 B-tree 最右叶子页，只要这一页在 buffer pool 里就 0 磁盘 IO，page split 几乎不发生。
随机主键（UUIDv4）：插入位置随机分布到全表的叶子页。表一旦超过 buffer pool（比如表 100GB、buffer pool 16GB），每次插入都大概率 miss → 必须先从磁盘读那一页再写 → 写放大 + IOPS 打满。
Page split 加剧：随机插入会频繁触发叶子页满了要分裂，分裂导致索引碎片化，b-tree 高度增加，进一步降低 buffer pool 利用率。

UUIDv7 怎么解：前 48 bit 是时间戳，近期生成的 ID 字典序都很接近，全部插入到 B-tree 右侧少数几个叶子页——这些页一直热，buffer pool 几乎永远命中。Percona / EnterpriseDB 的 benchmark 数据显示，亿级行的表 v7 比 v4 插入快 5-10 倍，写放大降一个数量级。

含义：用 v4 + 单独的 BIGINT 自增 PK + UUID 是 unique key，是历史上的折中方案；现在直接 v7 更干净。

2. Snowflake 的 12 bit 序列号支持 4096/ms = 410w/s。但生产中常见的『单进程 30w/s 就开始抛错』，为什么？

瓶颈不在 4096 上限，在『等下一毫秒』的实现。同毫秒内序列号用完（4096 个），代码要 sleep until next ms。但：

线程竞争：单 Snowflake 实例被多线程共享，last_ts + seq 要加锁 / CAS。30w/s 下锁争抢成瓶颈，远在 410w/s 之前。
系统调用开销：gettimeofday() 在 Linux 上虽快（vDSO），但每次 next_id 都调用，30w/s = 3μs/次，CPU 已经吃满。
burst 而非平均：实际流量是脉冲式，某一毫秒瞬间打满 4096 后阻塞，下一毫秒又空闲——平均看 30w/s，瞬时已饱和。

工程解法：

每个线程独立一个 Snowflake 实例（worker_id 进一步细分给线程），消除锁。
批量预生成：一次 next_batch(1000) 拿一段连续 ID 回客户端用，摊薄系统调用。
缓存时间戳：业务线程读上一次的 ts，单独一个 ticker 协程每毫秒更新，省 syscall。

Discord、Baidu UidGenerator、美团 Leaf 都在这个量级做过专门优化。

3. 系统里同时存在两种 ID（老的 BIGINT 自增 + 新的 Snowflake），如何无停机迁移？

这是『数据库主键演进』的经典难题。直接换主键 = 改表锁 + 改索引 + 改所有外键，停机几小时。无停机方案：

阶段 1：双写。新增 snowflake_id BIGINT UNIQUE 列，新写入两个 ID 都生成；老数据后台批量回填（按 PK 范围分批）。
阶段 2：双读。代码改为优先按 snowflake_id 读，按老 ID 读时内部转换。外部 API 接受两种 ID 格式（前缀区分或位数区分）。
阶段 3：迁移外键。把所有引用老 ID 的外键表，加 parent_snowflake_id 列、回填、切读、删老外键。这一步最痛苦，影响所有 JOIN。
阶段 4：下线老 ID。监控老 ID 的访问归零后，删列、改 PK。主键替换用 pt-online-schema-change / gh-ost 影子表方式做，避免锁表。

关键陷阱：

缓存里存的还是老 ID → 双写后要清相关 cache。
客户端 / 第三方系统持有老 ID → 给一个永久 redirect API（GET /v1/legacy_id/123 → snowflake）。
分析 / BI 系统按老 ID 做 JOIN → 数仓也要同步迁移。

整个过程通常 3-6 个月，关键是不要急于删老 ID——保留双写 1-2 个月观察。

4. 设计聊天系统时，发送方客户端在飞机上离线生成 ID 一周后上线发送，会发生什么？怎么处理？

核心问题：客户端本地生成的 UUIDv7 时间戳是一周前，到服务端时，按 ID 排序会把这条消息插入到一周前的位置，channel 历史里『过去突然冒出新消息』，UI 看不到。

解法分层：

双时间戳模型：消息 schema 同时存 client_id（客户端生成、用于幂等去重）+ server_ts（服务端收到的时间，决定排序）。排序按 server_ts，去重按 client_id。
消息体内 created_at：UI 显示『发送时间』用客户端的 created_at（让用户看到是『一周前写的』），但消息在 channel 列表的位置按 server_ts。WhatsApp、iMessage 都是这套。
幂等保证：服务端用 (channel_id, client_id) 做 upsert，客户端发 3 次同一条只成功一次。
冲突边界：极端情况两个客户端同时离线、同一 channel、同一毫秒生成相同 UUIDv7 概率仍 ~2⁻⁷⁴ ≈ 不可能。

更深的设计哲学：永远不要让一个字段同时承担『唯一标识』『时间排序』『因果排序』三件事——三者的时间语义不同（生成时间 / 接收时间 / 事件发生时间）。Slack 的 ts 字段是 server_ts、client_msg_id 是 UUID，分得很清楚。

5. 如果让你重新设计一个『面向用户可见』的 ID（出现在 URL、收据、support 工单），UUIDv7 / ULID / 自定义 Base62 怎么选？

用户可见 ID 的需求和后端主键完全不同，关键看 5 维：

抗猜测：URL 上的 order/123 可被遍历查别人订单。用户可见 ID 必须有足够随机位（>= 64 bit）。UUIDv7 后 74 bit 随机够用，但前 48 bit 时间戳暴露下单时间——金融场景不可接受。
抗输入错误：客户念给客服时 O/0、I/1 必须分清。Crockford Base32（ULID 用）专为此设计，去掉了 I L O U；Base62 没有这个保障。
长度：URL / 收据要短。UUIDv7 36 字符太长；ULID 26 字符可接受；Stripe 风格 cus_ + 14 随机字符是最佳折中。
类型可识别：用前缀（ord_, inv_）让支持人员一眼看出 ID 类型，避免把 invoice ID 当 order ID 查。这是Stripe 最被低估的工程决策。
是否暴露时间：B2B 场景可暴露（客户希望看到时间）；B2C 隐私场景不能。

推荐：Stripe 模式——{type_prefix}_{base62(随机)}，22-30 字符。后端主键用 UUIDv7 / Snowflake，对外永远不暴露后端 ID，加一层映射。代价是要存映射表（或者把 prefix + random 直接作为主键），但获得了 API 演进自由度。

反例：早期 Twitter URL 里的 tweet ID 是自增 + 后改 Snowflake，暴露了发推量；现在虽然换了 Snowflake 但仍能反推时间——产品发布时的时间戳设计要慎重。

← 回到 index