雪花算法(Snowflake algorithm)是一种生成全局唯一ID的算法，它能够保证在分布式系统中每个节点每秒钟生成不重复的ID。
雪花算法的核心思想是：使用64位的整数来生成ID，其中：
- 1位不用，因为二进制表示的时候最高位是符号位，1表示负数，所以正数的最高位是0，可以用于表示。
- 41位时间戳，单位是毫秒。可以容纳约69年的时间。
- 10位节点ID，可以容纳1024个节点。
- 12位序列号，可以在同毫秒内生成4096个ID。
以下是一个简单的Java实现：
public class SnowflakeIdGenerator {
private final long twepoch = 1577808548000L; // 假设自己的系统起始时间（毫秒）
private final long workerIdBits = 10L; // 节点ID的位数
private final long datacenterIdBits = 5L; // 数据中心ID的位数
private final long sequenceBits = 12L; // 序列号的位数
private final long workerIdShift = sequenceBits;
private final long datacenterIdShift = sequenceBits + workerIdBits;
private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private final long sequenceMask = -1L ^ (-1L << (int)sequenceBits);
private final long workerId;
private final long datacenterId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public SnowflakeIdGenerator(long workerId, long datacenterId) {
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException("workerId can't be greater than %d or less than 0");
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException("datacenterId can't be greater than %d or less than 0");
}
this.workerId = workerId;
this.datacenterId = datacenterId;
}
public synchronized long nextId() {
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return ((timestamp - twepoch) << (int)timestampLeftShift) |
(datacenterId << (int)datacenterIdShift) |
(workerId << (int)workerIdShift) |
sequence;
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {