一、雪花算法介绍

雪花算法（Snowflake Algorithm）是由 Twitter 公司开发的一种分布式 ID 生成算法，用于在分布式系统环境中高效地生成全局唯一 ID。这个算法生成的 ID 是一个 64 位的整数，结构如下：

  • 符号位（1 bit）：最高位是符号位，始终为 0，表示这是一个正整数。
  • 时间戳（41 bits）：接下来的 41 位是毫秒级时间戳，从一个自定义的起始时间点（通常是某个特定的时间，比如 2020-01-01 00:00:00）开始计算的偏移量。这可以确保不同机器上的 ID 在时间上是有序的，并且能够支持大约 69 年的时间跨度。
  • 机器标识（10 bits）：再接下来的 10 位是机器标识，可以用来区分不同的工作机器。这部分可以进一步划分为数据中心 ID 和机器 ID，例如用 5 位表示数据中心，用 5 位表示同一数据中心内的机器 ID。
  • 序列号（12 bits）：最后的 12 位是序列号，在同一个毫秒内，同一台机器上产生的不同 ID 会通过原子递增的方式分配不同的序列号。这使得即使在同一毫秒内也可以生成多个唯一的 ID。

这种设计的优点在于它可以在分布式的环境下快速生成不重复的 ID，并且这些 ID 在整体上有一定的顺序性，这对于某些数据库索引是有利的。此外，由于使用了时间戳，所以生成的 ID 也隐含了时间信息，有助于调试和故障排查。

1、优点

  • 全局唯一：雪花算法生成的ID是全局唯一的，可以用于分布式系统中的数据分片和数据合并，避免了 ID 冲突的问题。
  • 时间有序：雪花算法生成的 ID 中包含了时间戳信息，可以根据 ID 的大小推算出生成的时间，方便进行数据排序和查询。
  • 高性能：雪花算法生成 ID 的速度很快，可以满足高并发的场景需求。
  • 可扩展性：雪花算法的 数据结构相对简单，易于扩展和修改。

2、缺点

  • 依赖于系统时钟：雪花算法生成 ID 的过程中依赖于系统时钟，如果系统时钟发生回拨，可能会导致生成的 ID 出现重复。
  • 长度固定：雪花算法生成的 ID 长度固定为 64 位，可能会导致存储和传输成本较高。
  • 不支持分布式计算：雪花算法生成 ID 的过程是单线程的，不能支持分布式计算。

二、源码

这里的源码看的是 hutool 中封装的雪花算法。

其中有几个重要的属性：

1
2
3
4
5
6
7
8
9
private long sequence = 0L;

private long lastTimestamp = -1L;

private final long randomSequenceLimit;

private final long timeOffset;

private final long epoch;
  • epoch 表示初始化时间点。雪花算法是基于时间的，64 bit 位中有 41 位来记录毫秒值，该值表示的是生成 ID 的时间点与 epoch 属性的差值，41 位毫秒值，2 ^ 41 = 2,199,023,255,552，换算成年份大约 69 年左右，所以这个时间需要自定义一下，尽量靠近系统初次上线前的时间。因为是差值，后续如果修改这个 epoch 默认开始时间，会造成生成 ID 重复。
  • sequence 为自增序号
  • lastTimestamp 为最后一次生成 ID 的时间
  • randomSequenceLimit 用于限制生成 ID 的随机范围
  • timeOffset 允许的时钟回拨毫秒数

1、机器标识如何生成

有 10 位需要用来作为机器标识，10 个 bit 位，最多可以区分 1024 个 Java 进程实例。在这 10 位又分为数据中心 ID 和机器 ID。

根据机器的 MAC 地址来生成 dataCenter Id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * <p>获取数据中心 ID
 *
 * <p>数据中心 ID 依赖于本地网卡 MAC 地址
 * <p>保证在不同机器上面的 datacenter id 不同
 *
 * @param maxDatacenterId 最大的中心 ID
 * @return 数据中心 ID
 */
public static long getDataCenterId(long maxDatacenterId) {
    Assert.isTrue(maxDatacenterId > 0, "maxDatacenterId must be > 0");

    if (maxDatacenterId == Long.MAX_VALUE) {
        maxDatacenterId -= 1;
    }
    long id = 1L;
    byte[] mac = null;
    try {
        // 获取 mac 地址的二进制数组
        mac = NetUtil.getLocalHardwareAddress();
    } catch (UtilException ignore) {
        // ignore
    }
    if (mac != null) {
        // 下面这行代码最后向右移动 6 位，前面的计算结果为 16 位，向右移动 6 位，还剩 10 位
        id = ((0x000000FF & (long) mac[mac.length - 2]) | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
        // 之后对这 10 位的整数，取余
        id = id % (maxDatacenterId + 1);
    }
    return id;
}

根据 Java 进程的 PID 来生成 worker ID

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * <p>获取机器 ID，使用进程 ID 配合数据中心 ID 生成
 *
 * <p>机器依赖于本进程 ID 或进程名的 Hash 值。
 * <p>保证在同一个机器上面的不同 Java 实例进程的 work id 不同
 *
 * <p>此算法来自于mybatis-plus#Sequence
 *
 * @param datacenterId 数据中心ID
 * @param maxWorkerId  最大的机器节点ID
 */
public static long getWorkerId(long datacenterId, long maxWorkerId) {
    final StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    try {
        mpid.append(RuntimeUtil.getPid());
    } catch (UtilException igonre) {
        //ignore
    }
    // MAC + PID 的 hashcode 获取16个低位
    return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}

可以根据实际需要修改这 10 位中，dataCenter Id 和 worker Id 所占用的位数

程序启动时，使用常量类来存储当前 Java 进程实例的 dataCenter Id 和 Worker Id

1
2
3
4
5
6
7
8
9
10
11
12
13
public class IdConstants {

    /**
     * <p>默认的数据中心 ID
     */
    public static final long DEFAULT_DATACENTER_ID = IdUtils.getDataCenterId(Snowflake.MAX_DATA_CENTER_ID);

    /**
     * <p>默认的 Worker ID
     */
    public static final long DEFAULT_WORKER_ID = IdUtils.getWorkerId(DEFAULT_DATACENTER_ID, Snowflake.MAX_WORKER_ID);

}

2、ID 生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public synchronized long nextId() {
    long timestamp = genTime();
    // 如果获取到的当前时间小于上一次生成 ID 的时间
    if (timestamp < this.lastTimestamp) {
        // 如果差值小于 允许的时钟回拨毫秒数（默认 2 秒）
        if (this.lastTimestamp - timestamp < timeOffset) {
            // 容忍指定的回拨，避免 NTP 校时造成的异常
            timestamp = lastTimestamp;
        } else {
            // 如果服务器时间有问题(时钟后退) 报错。
            throw new IllegalStateException(StrUtil.format("Clock moved backwards. Refusing to generate id for {} ms", lastTimestamp - timestamp));
        }
    }

    // 如果获取到的当前时间等于上一次生成 ID 的时间
    if (timestamp == this.lastTimestamp) {
        final long sequence = (this.sequence + 1) & SEQUENCE_MASK;
        // sequence 为 0，因为 timestamp == this.lastTimestamp 表示当前毫秒已经生成过 ID 了，此 0 不可能为第一次生成时的 0
        // 只可能是 sequence 为 4096 时，序号 4096（二进制 1000000000000）与 4095（二进制 11111111111）按位与运算计算结果完成后的 0
        // 此时生成的需要已经超过了 4095，超过了 12 bit 位的序号位数限制
        if (sequence == 0) {
            // 时间重新赋值，知道 timestamp 大于 lastTimestamp 最后生成序号时间为止
            timestamp = this.tilNextMillis(lastTimestamp);
        }
        this.sequence = sequence;
    } else {
        // issue#I51EJY
        // 当在低频模式下时，序号始终为 0，导致生成 ID 始终为偶数
        // randomSequenceLimit 用于限定一个随机上限，在不同毫秒下生成序号时，给定一个随机数，避免偶数问题。
        // 默认构造器中，randomSequenceLimit 属性赋值为 0，表示不需要随机数
        if (randomSequenceLimit > 1) {
            sequence = RandomUtil.randomLong(randomSequenceLimit);
        } else {
            sequence = 0L;
        }
    }

    // 最后一次生成 ID 时间重新赋值
    lastTimestamp = timestamp;

    // 组装 ID
    return ((timestamp - epoch) << TIMESTAMP_LEFT_SHIFT)
            | (dataCenterId << DATA_CENTER_ID_SHIFT)
            | (workerId << WORKER_ID_SHIFT)
            | sequence;
}

该方法用于生成新的 ID，在生成 ID 的时间是否与上一次生成时间处于同一毫秒时，需要执行的逻辑不一样，并且会限制同一毫秒，同一 Java 进程中生成的 ID 数量为 4096 个 ID，如果超过这个数量，将会等待到下一毫秒去生成。

另外，该实现中还处理了正在低调用量时，每一毫秒生成的 ID 很少，生成的 ID 序号都为 0，导致生成的 ID 都为偶数的问题。

3、根据 ID 获取各个组成部分

3.1 根据 ID 获取 worker ID

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 根据 Snowflake 的 ID，获取机器 id
 *
 * @param id snowflake算法生成的id
 * @return 所属机器的id
 */
public long getWorkerId(long id) {
    // id >> WORKER_ID_SHIFT，将 id 中用来存储 work id 的部分移动到最低位
    // -1L 的二进制表示为 1111111111111111111111111111111111111111111111111111111111111111
    // -1L 左移 work id 会保存的长度，按位左移，低位补 0，1111111111111111111111111111111111111111111111111111111111100000
    // ~ 按位非，各个位置上 1 变成 0， 0 变成 1， 结果为 0000000000000000000000000000000000000000000000000000000000011111
    // 之后使用 按位与 操作符，只有位上都为 1 时，结果为 1，否则为 0，计算得出 work id
    return id >> WORKER_ID_SHIFT & ~(-1L << WORKER_ID_BITS);
}

3.2 根据 ID 获取 dataCenter ID

1
2
3
4
5
6
7
8
9
/**
 * 根据 Snowflake 的 ID，获取数据中心 id
 *
 * @param id snowflake算法生成的id
 * @return 所属数据中心
 */
public long getDataCenterId(long id) {
    return id >> DATA_CENTER_ID_SHIFT & ~(-1L << DATA_CENTER_ID_BITS);
}

3.3 根据 ID 获取生成时间

1
2
3
4
5
6
7
8
9
/**
 * 根据 Snowflake 的 ID，获取生成时间
 *
 * @param id snowflake 算法生成的 id
 * @return 生成的时间
 */
public long getGenerateDateTime(long id) {
    return (id >> TIMESTAMP_LEFT_SHIFT & ~(-1L << 41L)) + epoch;
}

4、IdUtils

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class IdUtils {

    private static final LocalDateTime LOCAL_DATE_TIME = LocalDateTime.of(2024, 12, 2, 12, 25, 43);

    public static Snowflake getSnowflake() {
        return Singleton.get(Snowflake.class);
    }

    /**
     * 获取单例的 Twitter 的 Snowflake 算法生成器对象
     *
     * @param workerId 终端ID
     */
    public static Snowflake getSnowflake(long workerId) {
        return Singleton.get(Snowflake.class, workerId);
    }

    /**
     * 获取单例的 Twitter 的 Snowflake 算法生成器对象
     *
     * @param workerId     终端ID
     * @param datacenterId 数据中心ID
     */
    public static Snowflake getSnowflake(long workerId, long datacenterId) {
        return Singleton.get(Snowflake.class, workerId, datacenterId);
    }

    /**
     * 获取单例的 Twitter 的 Snowflake 算法生成器对象
     *
     * @param epochDate        初始化时间起点（null 表示默认起始日期）,后期修改会导致 id 重复,如果要修改连 workerId dataCenterId，慎用
     * @param workerId         工作机器节点 id
     * @param dataCenterId     数据中心 id
     * @param isUseSystemClock 是否使用{@link SystemClock} 获取当前时间戳
     */
    public static Snowflake getSnowflake(LocalDateTime epochDate, long workerId, long dataCenterId, boolean isUseSystemClock) {
        return Singleton.get(Snowflake.class, epochDate, workerId, dataCenterId, isUseSystemClock);
    }

    /**
     * 简单获取 Snowflake 的 nextId
     *
     * @return nextId
     */
    public static long nextId() {
        return getSnowflake(LOCAL_DATE_TIME, IdConstants.DEFAULT_WORKER_ID, IdConstants.DEFAULT_DATACENTER_ID, true).nextId();
    }

    /**
     * 简单获取 Snowflake 的 nextId
     *
     * @return nextIdStr
     */
    public static String nextIdStr() {
        return getSnowflake(LOCAL_DATE_TIME, IdConstants.DEFAULT_WORKER_ID, IdConstants.DEFAULT_DATACENTER_ID, true).nextIdStr();
    }

}

需要向数据库中插入数据时，使用 IdUtils.nextId 或 IdUtils.nextIdStr 方法来生成 ID，方法中使用了自定义的计算差值开始时间。

三、其他问题

1、为什么不用数据库自增主键

之前有一个项目，使用的是主主复制，北中心和南中心使用各自的数据库，数据在北中心和南中心之间进行主主复制，当时创建序列时，还要特意在首位区分开南中心和北中心，比如，南中心以 1 开头，北中心以 2 开头。

雪花 ID 是有顺序的，对于索引来说，有序会使查询效率更高，而使用 UUID 是无序的，比较不适合作为主键。

2、关于 System.currentTimeMillis() 性能

柠檬夕桐/sequence - 码云 - 开源中国

3、雪花算法时钟回拨问题

雪花算法依赖系统时钟，雪花算法生成 ID 的组成部分中的时间戳是计算的生成 ID 的时间到设定好的起始时间的差值，当时钟回拨发生时，再次生成时这个计算的差值可能会再次出现，就有可能会生成重复的 ID，这将会破坏系统一致性和稳定性。

另外就算不产生重复的 ID，但是发生时钟回拨后，新生成的 ID 可能比回拨前已经生成的 ID 小，即全局递增性质被破坏。如果有业务依赖 ID 的递增性质，可能会发生问题。

出现时钟回拨的原因：

  • NTP 时间同步异常。NTP（网络时间协议）在同步时间时可能会导致时间回拨。
  • 手动调整时间。
  • 虚拟环境出现问题。比如虚拟机挂起后恢复时，系统时钟可能回拨。

解决时钟回拨问题，有如下几个常见方法：

  • 直接抛出异常。
  • 延迟等待。
  • 切换机器。在分布式系统中，会部署多机器多实例，当某个节点发生回拨时，可以切换到其他正常的节点来生成 ID。雪花 ID 中有 10 位是机器标识，通过操作使雪花 ID 的机器标识为之前一直未使用的机器标识。
  • 追赶时钟。
  • 使用备用时间戳。记录最后一次生成 ID 的时间，当发生时钟回拨后，判断生成时间是否小于记录的最后一次生成 ID 的时间，如果小于则使用最后记录的时间来生成 ID。

相关链接

柠檬夕桐/sequence - 码云 - 开源中国

百度 UidGenerator 和美团 Leaf | 死磕 Java

百度 UidGenerator | 死磕 Java

OB tags

#Java #后端