使用Snowflake算法生成分布式ID

使用 Snowflake 算法生成分布式 ID。Snowflake 算法是 Twitter 开源的一种简单而高效的分布式 ID 生成算法。它使用一个 64 位的整数来表示生成的 ID，其中包含以下几个部分：

时间戳：占用 42 位，精确到毫秒级别，可以使用当前时间减去一个起始时间戳来得到相对时间，然后将其转换为二进制表示。
工作机器 ID：占用 10 位，用于标识不同的工作机器。可以根据实际情况分配给每个工作机器一个唯一的 ID。
序列号：占用 12 位，用于解决在同一毫秒内产生多个 ID 的冲突问题。如果同一毫秒内生成的 ID 数量超过了序列号的范围，那么会等到下一毫秒再继续生成。

代码示例：

java
public class SnowflakeIdGenerator {
    // 起始的时间戳
    private static final long START_TIMESTAMP = 1630000000000L;

    // 每部分占用的位数
    private static final long WORKER_ID_BITS = 10L;
    private static final long SEQUENCE_BITS = 12L;

    // 每部分的最大值
    private static final long MAX_WORKER_ID = -1L ^ (-1L << WORKER_ID_BITS);
    private static final long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BITS);

    // 每部分向左的位移
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    private static final long TIMESTAMP_SHIFT = WORKER_ID_BITS + SEQUENCE_BITS;

    // 工作机器ID
    private 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("Worker ID超出范围");
        }
        this.workerId = workerId;
    }

    public synchronized long generateId() {
        long timestamp = getCurrentTimestamp();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("时间戳错误");
        }

        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQUENCE;
            if (sequence == 0) {
                // 当前毫秒内的序列号已经用完，等待下一毫秒
                timestamp = waitNextMillis(timestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - START_TIMESTAMP) << TIMESTAMP_SHIFT) |
                (workerId << WORKER_ID_SHIFT) |
                sequence;
    }

    private long getCurrentTimestamp() {
        return System.currentTimeMillis();
    }

    private long waitNextMillis(long currentTimestamp) {
        long timestamp = getCurrentTimestamp();
        while (timestamp <= currentTimestamp) {
            timestamp = getCurrentTimestamp();
        }
        return timestamp;
    }
}

public class Main {
    public static void main(String[] args) {
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1);
        long id = idGenerator.generateId();
        System.out.println("生成的ID：" + id);
    }
}

如何确保工作机器ID的唯一性？

可以自行配置或者使用zookeeper来确保保证。

使用zookeeper的顺序节点特性确保唯一性：

java
// 使用顺序节点来创建唯一的wordId。当多个客户端同时尝试创建节点时，ZooKeeper会为每个节点分配一个唯一的顺序号。
String wordIdPath = zooKeeper.create("/wordIds/wordId-", null, ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL);
String wordId = wordIdPath.replace("/wordIds/", ""); // 提取唯一的wordId

// 在上面的代码中，使用create方法创建了一个顺序节点，节点路径以"/wordIds/wordId-"开头，后面会自动附加一个唯一的顺序号。然后，可以提取出唯一的wordId。

如何避免时间回拨问题？

在雪花算法中实现时钟回拨检测可以通过以下步骤来实现：

记录上一次生成 ID 的时间戳：在每次生成雪花 ID 之前，记录上一次生成 ID 的时间戳。这可以通过全局变量、数据库或其他持久化存储方式来保存。
获取当前时间戳：在生成新的雪花 ID 之前，获取当前的系统时间戳。确保使用一个可靠的时间源，如网络时间协议（NTP）服务器或其他可靠的时间同步服务。
检测时钟回拨：将当前时间戳与上一次生成 ID 的时间戳进行比较。如果当前时间戳小于上一次生成 ID 的时间戳，说明发生了时钟回拨。
处理时钟回拨：当发现时钟回拨时，可以采取合适的处理方式来避免生成重复的 ID。以下是一些常见的处理方式：

1、等待补偿：等待一段时间，直到时钟回拨问题解决后再生成 ID。可以根据时钟回拨的量，等待足够的时间，确保时间超过上一次生成 ID 的时间戳，然后再生成 ID。

2、抛出异常或记录警告：在检测到时钟回拨时，可以抛出异常或记录警告，以通知系统管理员或相关人员。这样可以及时采取措施来调整时钟或处理时钟回拨问题。

3、调整时间戳：根据具体情况，可以调整当前时间戳，使其超过上一次生成 ID 的时间戳，以避免生成重复的 ID。这需要谨慎处理，确保调整后的时间戳不会导致其他问题。

时钟回拨检测是针对雪花算法的时间戳部分进行的。其他部分，如数据中心 ID 和工作机器 ID，在时钟回拨检测中通常不会受到影响。

java
public class SnowflakeIdGenerator {
    private static final long EPOCH = 1630000000000L; // 设置起始时间戳，根据实际情况调整
    private static final long WORKER_ID_BITS = 5L; // 机器ID所占位数
    private static final long DATA_CENTER_ID_BITS = 5L; // 数据中心ID所占位数
    private static final long SEQUENCE_BITS = 12L; // 序列号所占位数

    private static final long MAX_WORKER_ID = ~(-1L << WORKER_ID_BITS);
    private static final long MAX_DATA_CENTER_ID = ~(-1L << DATA_CENTER_ID_BITS);

    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    private static final long DATA_CENTER_ID_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;
    private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS + DATA_CENTER_ID_BITS;
    private static final long SEQUENCE_MASK = ~(-1L << SEQUENCE_BITS);

    private long workerId;
    private long dataCenterId;
    private long sequence = 0L;
    private long lastTimestamp = -1L;

    public SnowflakeIdGenerator(long workerId, long dataCenterId) {
        if (workerId > MAX_WORKER_ID || workerId < 0) {
            throw new IllegalArgumentException("Worker ID can't be greater than " + MAX_WORKER_ID + " or less than 0");
        }
        if (dataCenterId > MAX_DATA_CENTER_ID || dataCenterId < 0) {
            throw new IllegalArgumentException("Data Center ID can't be greater than " + MAX_DATA_CENTER_ID + " or less than 0");
        }
        this.workerId = workerId;
        this.dataCenterId = dataCenterId;
    }

    public synchronized long generateId() {
        long timestamp = System.currentTimeMillis();
        if (timestamp < lastTimestamp) {
            throw new RuntimeException("Clock moved backwards. Refusing to generate ID for " + (lastTimestamp - timestamp) + " milliseconds");
        }

        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & SEQUENCE_MASK;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }

        lastTimestamp = timestamp;

        return ((timestamp - EPOCH) << TIMESTAMP_LEFT_SHIFT) |
                (dataCenterId << DATA_CENTER_ID_SHIFT) |
                (workerId << WORKER_ID_SHIFT) |
                sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = System.currentTimeMillis();
        while (timestamp <= lastTimestamp) {
            timestamp = System.currentTimeMillis();
        }
        return timestamp;
    }
}

public class Main {
    public static void main(String[] args) {
        // 创建SnowflakeIdGenerator实例，传入workerId和dataCenterId
        SnowflakeIdGenerator idGenerator = new SnowflakeIdGenerator(1, 1);

        // 生成ID
        long id = idGenerator.generateId();
        System.out.println("Generated ID: " + id);
    }
}