雪花算法

在分布式系统中，为了避免多个节点生成相同的唯一标识符id，我们通常使用一种全局唯一ID生成策略，而Snowflake Algorithm就是广泛使用的解决方案之一。

雪花算法简介

雪花算法生成的 ID 是一个 64 位的二进制整数，具有以下组成部分：

代码实现

package com.can.springbootmessage;

public class SnowflakeIdGenerator {
    // 起始时间戳，Long是64位，所以这里的Statt_Timestamp实际上有64位
    private static final long START_TIMESTAMP = 157286400000L;

    // 每部分占用的位数，符号位默认1位且位0，时间戳
    private static final long WORKER_ID_BITS = 5L;    // 机器ID所占位数
    private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);    // 最大支持机器ID数量：31
    // 序列号占用的位数为 12 位，同一毫秒内可以生成 2^12 = 4096 个序列号。
    private static final long SEQUENCE_BITS = 12L;

    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;

    // 当前机器的唯一标识（0-31）。
    private final long workerId;
    private long sequence = 0L;
    // 上一次生成 ID 时的时间戳，用于判断是否跨毫秒。
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId) {
        if(workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException(String.format("Worker ID cantnot be greater than %d or less than 0", MAX_WORKER_ID));
        }
        this.workerId = workerId;
    }

    // 获取当前的系统时间戳（以毫秒为单位）。
    private long timeGen() {
        return System.currentTimeMillis();
    }

    // 生成下一个唯一的 ID，synchronized 关键字确保多线程环境下的线程安全。
    public synchronized long nextId() {
        long timestamp = timeGen();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate id");
        }
        // 如果当前时间戳等于上一次生成 ID 的时间戳，说明是在同一毫秒内生成 ID。
        if (timestamp == lastTimestamp) {
            // 序列号递增。通过 & 运算保证序列号不超过 4095 (2^12 - 1)。如果sequence递增到4096，通过这个 & 操作，sequence就变成0了
            sequence = (sequence + 1) & (1 << SEQUENCE_BITS - 1);
            if (sequence == 0) {
                // 如果该毫秒内，sequence增加到4096，循环等到下一毫秒生成新的 ID
                timestamp = tilNextMillis(lastTimestamp);

            } else {
                // 如果当前时间戳大于上一次生成 ID 的时间戳，说明是新的一毫秒，序列号重置为 0。
                sequence = 0L;
            }
        }
        // 更新 lastTimestamp 为当前时间戳，以便后续生成 ID 时使用。
        lastTimestamp = timestamp;
        // 生成 ID 并返回。通过位移和或操作将时间戳、机器 ID 和序列号合并成一个 64 位的 long 值。
        return ((timestamp - START_TIMESTAMP) << TIMESTAMP_LEFT_SHIFT)  // 时间戳部分
                | (workerId << WORKER_ID_SHIFT)  // 机器 ID 部分
                | sequence;  // 序列号部分
    }

    // 如果当前时间戳与上一次生成 ID 的时间戳相同，并且序列号已用尽，等待到下一毫秒。
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        // 循环，直到获取到比 lastTimestamp 大的时间戳。
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    
    public static void main(String[] args) {
        // example usage
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1);
        for (int i = 0; i < 10; i++) {
            long id = idGenerator.nextId();
            System.out.println("Generated ID:" + id);
        }
    }
}

1. 参数初始化：
   • START_TIMESTAMP 是一个时间戳的起点，通常定义为系统的某个固定时间，所有生成的 ID 的时间戳都基于这个时间差来计算。
   • SEQUENCE_BITS + WORKER_ID_BITS 分别表示序列号 和 机器 ID 占用的位数，设计成 12 位和 5 位，这些位数的设计可以根据系统规模调整。
   • 您可以根据自己的需求和分布式环境的规模来调整 WORKER_ID_BITS 的长度，以适应不同的场景，这里只设置了5位的机器ID
2. ID 生成逻辑：
   • 生成使用了 41 位的时间戳、5 位的机器中心 ID，以及 12 位的序列号。
   • 生成新的 ID 时，如果时间戳不变，序列号递增；如果时间戳变了，序列号清零。
   • 一毫秒内的序列号已经用完（4096 个 ID），会等待到下一毫秒再继续生成。
3. 时钟回拨检测：
   • 当系统时间出现回退（即当前时间小于上次生成 ID 时的时间），为了避免生成重复 ID，直接抛出异常。

总结

1. 雪花算法算法是用来生成全局唯一ID。
2. 核心是64位二进制数，基于时间戳的算法，
   1. 1位默认位0，41位时间用于时间戳，10位用于机器ID，12位用于序列号。
   2. 机器ID，用于标识不同的机器(节点)。10位可以将其分数据中心ID(5位)和机器ID(5位）,共支持1024台机器同时生成ID
   3. 序列号用来区分在同一台机器、同一时间戳下生成的多个ID，最大支持同一毫秒生成4096个唯一ID。
3. 生成新的ID时：
   1. 如果时间戳不变，序列号增加；
   2. 如果时间戳改变，序列号清零；
   3. 一毫秒内的序列号如果用完(4096个ID)，会等待到下一毫秒再继续生成(进入循环，直到时间戳更新)