分布式ID方案SnowFlake雪花算法分析
1、算法
SnowFlake算法生成的数据组成结构如下：
在java中用long类型标识，共64位（每部分用-分开）： 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00
- 1位标识，0表示正数。
- 41位时间戳，当前时间的毫秒减去开始时间的毫秒数。可用 (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。
- 5位数据中心标识，可支持(1L << 5) = 32个数据中心。
- 5位机器标识，每个数据中心可支持(1L << 5) = 32个机器标识。
- 12位序列号，每个节点每一毫秒支持(1L << 12) = 4096个序列号。
2、Java版本实现
/**
* 雪花算法<br>
* 在java中用long类型标识，共64位（每部分用-分开）：<br>
* 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 0000000000 00<br>
* 1位标识，0表示正数。<br>
* 41位时间戳，当前时间的毫秒减去开始时间的毫秒数。可用 (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年。<br>
* 5位数据中心标识，可支持(1L << 5) = 32个数据中心。<br>
* 5位机器标识，每个数据中心可支持(1L << 5) = 32个机器标识。<br>
* 12位序列号，每个节点每一毫秒支持(1L << 12) = 4096个序列号。<br>
*/
public class SnowflakeIdWorker {
/**
* 机器标识
*/
private long workerId;
/**
* 数据中心标识
*/
private long dataCenterId;
/**
* 序列号
*/
private long sequence;
/**
* 机器标识占用5位
*/
private long workerIdBits = 5L;
/**
* 数据中心标识占用5位
*/
private long dataCenterIdBits = 5L;
/**
* 12位序列号
*/
private long sequenceBits = 12L;
/**
* 12位序列号支持的最大正整数
* ....... 00001111 11111111
* 2^12-1 = 4095
*/
private long sequenceMask = ~(-1L << sequenceBits);
/**
* The Worker id shift.
* 12位
*/
private long workerIdShift = sequenceBits;
/**
* The Data center id shift.
* 12 + 5 = 17位
*/
private long dataCenterIdShift = sequenceBits + workerIdBits;
/**
* The Timestamp shift.
* 12 + 5 + 5 = 22位
*/
private long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
/**
* 开始时间戳毫秒
*/
private long startEpoch = 29055616000L;
/**
* The Last timestamp.
*/
private long lastTimestamp = -1L;
public SnowflakeIdWorker(long workerId, long dataCenterId, long sequence) {
// 检查workerId是否正常
/*
机器标识最多支持的最大正整数
-1的补码：
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
-1 左移 5 位，高位溢出，低位补0：
11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
取反：
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
转10进制：
16 + 8 + 4 + 2 + 1 = 31
*/
long maxWorkerId = ~(-1L << workerIdBits);
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("工作Id不能大于%d或小于0", maxWorkerId));
}
/*
数据中心最多支持的最大正整数31
*/
long maxDataCenterId = ~(-1L << dataCenterIdBits);
if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
throw new IllegalArgumentException(String.format("数据中心Id不能大于%d或小于0", maxDataCenterId));
}
this.workerId = workerId;
this.dataCenterId = dataCenterId;
this.sequence = sequence;
}
private synchronized long nextId() {
//获取当前时间毫秒数
long timestamp = timeGen();
//如果当前时间毫秒数小于上一次的时间戳
if (timestamp < lastTimestamp) {
System.err.printf("时钟发生回调，拒绝生成ID,直到： %d.", lastTimestamp);
throw new RuntimeException(String.format("时钟发生回调， 拒绝为 %d 毫秒生成ID。",
lastTimestamp - timestamp));
}
//当前时间毫秒数与上次时间戳相同，增加序列号
if (lastTimestamp == timestamp) {
//假设sequence=4095
//(4095 + 1) & 4095
//4096: ....... 00010000 00000000
//4095: ....... 00001111 11111111
// ....... 00000000 00000000
//最终sequence为0，即sequence发生溢出。
sequence = (sequence + 1) & sequenceMask;
//如果发生序列号为0，即当前毫秒数的序列号已经溢出，则借用下一毫秒的时间戳
if (sequence == 0) {
timestamp = tilNextMillis(lastTimestamp);
}
} else {
//当前毫秒数大于上次的时间戳，序列号为0
sequence = 0;
}
//更新
lastTimestamp = timestamp;
//生成ID算法，左移几位，则后面加几个0。
//1、当前时间的毫秒数-开始时间的毫秒数，结果左移22位
// 假设：timestamp - startEpoch = 1
// 二进制:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
// 左移22位:
// 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
//2、dataCenterId左移17位
// 假设：dataCenterId = 1
// 二进制:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
// 左移17位:
// 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000
//3、workerId左移12位
// 假设：workerId = 1
// 二进制:
// 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
// 左移12位:
// 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
//4、最后的所有结果按位`或`
//假设：sequence = 1
//00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000
//00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000
//00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000
//00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
//00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001
//结果： 0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001
return ((timestamp - startEpoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
/**
* 获取下一秒
*
* @param lastTimestamp the last timestamp
* @return the long
*/
private long tilNextMillis(long lastTimestamp) {
//获取当前毫秒数
long timestamp = timeGen();
//只要当前的毫秒数小于上次的时间戳，就一直循环，大于上次时间戳
while (timestamp <= lastTimestamp) {
//获取当前毫秒数
timestamp = timeGen();
}
return timestamp;
}
/**
* 获取当前毫秒数
*
* @return the long
*/
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowflakeIdWorker worker = new SnowflakeIdWorker(1, 1, 1);
for (int i = 0; i < 10000; i++) {
long id = worker.nextId();
System.out.println(id);
System.out.println(Long.toString(id).length());
System.out.println(Long.toBinaryString(id));
System.out.println(Long.toBinaryString(id).length());
}
}
}
3、难点
Tips: 左移几位，则后面加几个0。
3.1、计算机器标识最多支持的最大正整数
private long workerIdBits = 5L;
long maxWorkerId = ~(-1L << workerIdBits);
计算过程：
- -1的补码：<br> 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111
- -1 左移 5 位，高位溢出，低位补0：<br> 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000
- 取反：<br> 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111
- 转10进制：<br> 16 + 8 + 4 + 2 + 1 = 31
3.2、sequence溢出处理
sequence = (sequence + 1) & sequenceMask;
计算过程:<br> 假设sequence=4095：<br>
- (4095 + 1) & 4095
- 4096: ....... 00010000 00000000
- 4095: ....... 00001111 11111111
- 按位与 ....... 00000000 00000000
- 最终sequence为0，即sequence发生溢出。
3.3、ID计算
((timestamp - startEpoch) << timestampShift) |
(dataCenterId << dataCenterIdShift) |
(workerId << workerIdShift) |
sequence
计算过程：
- 当前时间的毫秒数-开始时间的毫秒数，结果左移22位
假设：timestamp - startEpoch = 1<br> 二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br> 左移22位: 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000<br>
- dataCenterId左移17位
假设：dataCenterId = 1<br> 二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br> 左移17位: 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000<br>
- workerId左移12位
假设：workerId = 1<br> 二进制: 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br> 左移12位: 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000<br>
- 最后的所有结果按位
或
假设：sequence = 1<br> 00000000 00000000 00000000 00000000 00000000 01000000 00000000 00000000<br> 00000000 00000000 00000000 00000000 00000000 00000010 00000000 00000000<br> 00000000 00000000 00000000 00000000 00000000 00000000 00010000 00000000<br> 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001<br>
00000000 00000000 00000000 00000000 00000000 01000010 00010000 00000001<br>
- 结果：
0 - 0000000 00000000 00000000 00000000 00000000 01 - 00001 - 00001 - 0000 00000001<br> 符合SnowFlake算法数据组成结构。
参考
理解分布式id生成算法SnowFlake Twitter雪花算法SnowFlake算法的java实现
