雪花算法 Snowflake algorithm

1. 简介

雪花算法（Snowflake Algorithm）是一种分布式唯一 ID 生成算法，最初由 Twitter 提出，旨在解决大规模分布式系统中生成唯一标识符（ID）的需求。其生成的 ID 是 64 位的长整型，具有高性能和可扩展性。

2. 结构

生成的 ID 由以下几个部分组成：

雪花算法的 ID 结构示意图

0  -  41 bits  -  10 bits  -  12 bits
+----------------+----------+-----------+
|    timestamp   | machine  | sequence  |
|                | ID       | number    |
+----------------+----------+-----------+

在扩展的版本中工作机器 ID 可以扩展为数据中心 ID 和 机器 ID。

0  -  41 bits  -  5 bits  -  5 bits  -  12 bits
+----------------+----------+----------+-----------+
|    timestamp   | dataCenterID | machineID | sequence  |
|                |              |           | number    |
+----------------+----------+----------+-----------+

3. ID 生成示例

public class SnowflakeIdGenerator {
    private final long epoch = 1640995200000L; // 自定义起始时间
    private final long machineIdBits = 10L;
    private final long sequenceBits = 12L;

    private final long maxMachineId = ~(-1L << machineIdBits); // 最大机器 ID
    private final long sequenceMask = ~(-1L << sequenceBits); // 最大序列号

    private long lastTimestamp = -1L;
    private long machineId; // 工作机器 ID
    private long sequence = 0L; // 序列号

    public SnowflakeIdGenerator(long machineId) {
        if (machineId > maxMachineId || machineId < 0) {
            throw new IllegalArgumentException("Machine ID can't be greater than " + maxMachineId + " or less than 0");
        }
        this.machineId = machineId;
    }

    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();

        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Rejecting requests until " + lastTimestamp);
        }

        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask; // 同一毫秒内的序列号递增
        } else {
            sequence = 0L; // 不同毫秒重置序列号
        }

        lastTimestamp = timestamp;

        return ((timestamp - epoch) << (machineIdBits + sequenceBits)) | (machineId << sequenceBits) | sequence;
    }
}

• 获取当前时间戳：获取当前时间的毫秒数。
• 检查时间回拨：如果当前时间小于上次生成 ID 的时间，则抛出异常，避免生成重复 ID。
• 生成序列号：
  • 如果在同一毫秒内生成 ID，则序列号加 1；如果进入了新的毫秒，序列号重置为 0。
• 组合 ID：
  • 通过位运算，将时间戳、机器 ID 和序列号组合成一个 64 位的唯一 ID。

主要优点

• 高性能：可以在单机和分布式环境中高效生成 ID。
• 唯一性：确保生成的 ID 在全局范围内唯一。
• 可扩展性：通过增加工作机器 ID，可以支持更多的节点。

应用场景

• 雪花算法广泛应用于需要唯一标识符的场景，如数据库主键生成、消息系统 ID、订单 ID 等。