📚 课程目录第3章雪花算法（Snowflake）

3. 雪花算法（Snowflake）：算法原理与 Python 实现

聊到分布式唯一 ID，绕不开 Snowflake。我记得第一次接触它，是在一个电商订单系统里——每天要生成上亿个订单号，还得保证全局唯一、趋势递增。UUID 虽然简单，但太长了，还不适合做数据库索引。嗯，Snowflake 正好解决了这个问题。

3.1 算法核心：64 位结构

说白了，Snowflake 把 64 位拆成四个部分。我习惯用这张图来理解它：

3.2 时间戳：核心驱动力

时间戳部分占了 41 位。这里有个细节：它不是用 Unix 时间戳，而是从一个自定义纪元开始算。比如我把起始时间设为 2020-01-01 00:00:00，那么实际存的是相对毫秒数。

为什么要这样？因为 41 位的无符号整数最大能表示 2^41 - 1 = 2199023255551 毫秒。你算算看：

2199023255551 ms ÷ (1000 * 60 * 60 * 24 * 365) ≈ 69.7 年

如果从 2020 年开始，约能用到 2089 年。我在项目中习惯把起始时间设得离业务启动近一点，这样能多用几年。

小技巧： 用 time.time() * 1000 - CUSTOM_EPOCH 算差值，记得转 int 并取绝对值。

3.3 机器 ID：分布式节点标识

10 bit 的机器 ID 怎么分？我亲眼见过两种做法：

手动配置： 启动时从环境变量或配置文件读取，简单可靠。
自动注册： 用 ZooKeeper 或 Redis 分配，节点挂掉后释放。

我个人倾向于手动配置，原因很简单——避免外部依赖。尤其在我们早期做物联网平台时，设备节点数量不大，手动配 0~1023 完全够用。如果你有数据中心概念，还可以拆成 5 bit 数据中心 ID + 5 bit 机器 ID。

避坑： 我曾经遇到过两台服务器配了相同机器 ID，结果在同一毫秒内生成重复 ID，排查了半天。务必确保机器 ID 全局唯一，最好用分布式协调工具来保证。

3.4 序列号：同一毫秒的并发保障

12 bit 序列号，范围 0~4095。当同一毫秒内生成了 4096 个 ID 时，就必须等下一毫秒。我通常这样处理：

如果当前毫秒跟上次相同，序列号自增。
如果序列号超过 4095，忙等待到下一毫秒。
如果当前毫秒小于上次（时钟回拨），抛异常或直接阻塞。

你看，核心逻辑就这几行。但有个坑：时钟回拨。我记忆中遇到过两次：一次是运维手动调了 NTP，导致时间瞬间跳回 500 毫秒。好在我们的实现里加了「容忍回拨 100 毫秒以内等待」的逻辑，否则订单 ID 就乱套了。

3.5 Python 实现：完整示例

下面是我在多个项目里实际用过的版本，去掉了冗余依赖，只保留核心：

import time
import threading

class Snowflake:
    CUSTOM_EPOCH = 1577836800000  # 2020-01-01 00:00:00 UTC 毫秒
    MACHINE_ID_BITS = 10
    SEQUENCE_BITS = 12
    MAX_MACHINE_ID = -1 ^ (-1 << MACHINE_ID_BITS)  # 1023
    MAX_SEQUENCE = -1 ^ (-1 << SEQUENCE_BITS)      # 4095
    MACHINE_SHIFT = SEQUENCE_BITS                  # 12
    TIMESTAMP_SHIFT = SEQUENCE_BITS + MACHINE_ID_BITS  # 22

    def __init__(self, machine_id):
        if machine_id < 0 or machine_id > self.MAX_MACHINE_ID:
            raise ValueError(f"Machine ID must be 0 ~ {self.MAX_MACHINE_ID}")
        self.machine_id = machine_id
        self.last_timestamp = -1
        self.sequence = 0
        self.lock = threading.Lock()

    def _wait_next_millis(self, last_ts):
        """阻塞直到下一个毫秒"""
        ts = self._gen_timestamp()
        while ts <= last_ts:
            ts = self._gen_timestamp()
        return ts

    def _gen_timestamp(self):
        return int(time.time() * 1000) - self.CUSTOM_EPOCH

    def next_id(self):
        with self.lock:
            timestamp = self._gen_timestamp()
            if timestamp < self.last_timestamp:
                # 时钟回拨 —— 我建议直接抛异常
                raise RuntimeError(
                    f"Clock moved backwards: {self.last_timestamp - timestamp} ms"
                )
            if timestamp == self.last_timestamp:
                self.sequence = (self.sequence + 1) & self.MAX_SEQUENCE
                if self.sequence == 0:
                    timestamp = self._wait_next_millis(timestamp)
            else:
                self.sequence = 0
            self.last_timestamp = timestamp
            return (
                (timestamp << self.TIMESTAMP_SHIFT)
                | (self.machine_id << self.MACHINE_SHIFT)
                | self.sequence
            )

# 使用示例
snow = Snowflake(machine_id=1)
print(snow.next_id())  # 输出 64 位整数，例如 1288834974657

关键说明：

用 threading.Lock 保证线程安全，多线程环境下也能正常生成。
_wait_next_millis 采用忙等待，实际项目中可以加个短暂 sleep 降低 CPU 开销。
时钟回拨处理：我选择直接抛异常，因为超过 100ms 的回拨大概率是人为故障，不应该默默容忍。

3.6 性能对比：UUID vs Snowflake

我整理了一个简单表格，帮你直观感受差异：

特性	UUID（版本 4）	Snowflake
长度	128 bit（36 字符）	64 bit（19 位数字）
顺序性	无序	趋势递增
生成性能	约 10 万/秒	百万级/秒（受锁影响）
时钟依赖	无	依赖系统时钟
DB 索引友好	差（随机 B+ 树分裂）	好（有序写入）

你看，Snowflake 在有序性和索引性能上明显占优。缺点就是怕时钟回拨——嗯，这也是你设计系统时必须考虑的风险。

3.7 时钟回拨兜底策略

我记得有一次线上排查：某个节点突然生成不了 ID，日志里全是「Clock moved backwards」。后来发现是 NTP 同步导致时间微调。之后我调整了方案：

小回拨（< 100ms）： 阻塞等待恢复，然后继续。
大回拨（>= 100ms）： 直接抛异常，人工介入。

如果你觉得抛异常太暴力，也可以考虑用 备用序列号池 或 切换到其他算法（比如美团 Leaf）。但我觉得，对于大部分场景，上面这个 Python 实现已经够用了。

生产建议： 机器 ID 通过环境变量注入 MACHINE_ID，方便容器化部署时指定。别忘了在部署脚本里做唯一性校验。

3.8 本章总结

Snowflake 的巧妙之处，就在于用 64 位分片，把时间、机器、并发三个维度整合成一个趋势递增的整数。你只要记住：时间戳决定范围，机器 ID 决定节点，序列号决定并发。每一部分单独可控，组合起来就是分布式 ID 的标准答案之一。