参考链接：
快速了解雪花算法详解及spring boot集成
SpringBoot快速开发（六）【雪花算法（snowflake）自增ID】
1.介绍#
SnowFlow算法是Twitter推出的分布式id生成算法，主要核心思想就是利用64bit的long类型的数字作为全局的id。在分布式系统中经常应用到，并且，在id中加入了时间戳的概念，基本上保持不重复，并且持续一种向上增加的方式。
在这64bit中，其中第一个bit是不用的，然后用其中的41个bit作为毫秒数，用10bit作为工作机器id,12bit作为序列号.具体如下图所示：
- 第一个部分：0,这个是个符号位，因为在二进制中第一个bit如果是1的话，那么都是负数，但是我们生成的这些id都是正数，所以第一个bit基本上都是0
- 第二个部分：41个bit,代表的是一个时间戳，41bit可以表示的数字多达$2^{41} $-1,也可以表示2^{41}-1
个毫秒值，基本上差不多是69年。
- 第三个部分：5个bit 表示的是机房id。
- 第四个部分：5个bit 表示的是机器id。
- 第五个部分：12个bit 表示的是机房id，表示的序号，就是某个机房某台机器上这一毫秒内同时生成的 id 的序号，0000 00000000，如果是同一毫秒，那么这个雪花值就会递增
简单来说，你的某个服务假设要生成一个全局唯一 id，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id。
这个算法可以保证说，一个机房的一台机器上，在同一毫秒内，生成了一个唯一的 id。可能一个毫秒内会生成多个 id，但是有最后 12 个 bit 的序号来区分开来。
下面我们就来简单看下这个算法的代码实现部分。
总之就是用一个64bit的数字中各个bit位置来设置不同的标志位
2.代码实现#
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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
/**
* id自增器（雪花算法）
*
* @author bin
* @date 2022/10/11
*/
public class SnowFlake {
private final static long twepoch = 12888349746579L;
// 机器标识位数
private final static long workerIdBits = 5L;
// 数据中心标识位数
private final static long datacenterIdBits = 5L;
// 毫秒内自增位数
private final static long sequenceBits = 12L;
// 机器ID偏左移12位
private final static long workerIdShift = sequenceBits;
// 数据中心ID左移17位
private final static long datacenterIdShift = sequenceBits + workerIdBits;
// 时间毫秒左移22位
private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
//sequence掩码，确保sequnce不会超出上限
private final static long sequenceMask = -1L ^ (-1L << sequenceBits);
//上次时间戳
private static long lastTimestamp = -1L;
//序列
private long sequence = 0L;
//服务器ID
private long workerId = 1L;
private static long workerMask = -1L ^ (-1L << workerIdBits);
//进程编码
private long processId = 1L;
private static long processMask = -1L ^ (-1L << datacenterIdBits);
private static SnowFlake snowFlake = null;
static{
snowFlake = new SnowFlake();
}
public static synchronized long nextId(){
return snowFlake.getNextId();
}
private SnowFlake() {
//获取机器编码
this.workerId=this.getMachineNum();
//获取进程编码
RuntimeMXBean runtimeMXBean = ManagementFactory.getRuntimeMXBean();
this.processId=Long.valueOf(runtimeMXBean.getName().split("@")[0]).longValue();
//避免编码超出最大值
this.workerId=workerId & workerMask;
this.processId=processId & processMask;
}
public synchronized long getNextId() {
//获取时间戳
long timestamp = timeGen();
//如果时间戳小于上次时间戳则报错
if (timestamp < lastTimestamp) {
try {
throw new Exception("Clock moved backwards. Refusing to generate id for " + (lastTimestamp - timestamp) + " milliseconds");
} catch (Exception e) {
e.printStackTrace();
}
}
//如果时间戳与上次时间戳相同
if (lastTimestamp == timestamp) {
// 当前毫秒内，则+1，与sequenceMask确保sequence不会超出上限
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
// 当前毫秒内计数满了，则等待下一秒
timestamp = tilNextMillis(lastTimestamp);
}
} else {
sequence = 0;
}
lastTimestamp = timestamp;
// ID偏移组合生成最终的ID，并返回ID
long nextId = ((timestamp - twepoch) << timestampLeftShift) | (processId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
return nextId;
}
/**
* 再次获取时间戳直到获取的时间戳与现有的不同
* @param lastTimestamp
* @return 下一个时间戳
*/
private long tilNextMillis(final long lastTimestamp) {
long timestamp = this.timeGen();
while (timestamp <= lastTimestamp) {
timestamp = this.timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
/**
* 获取机器编码
* @return
*/
private long getMachineNum(){
long machinePiece;
StringBuilder sb = new StringBuilder();
Enumeration<NetworkInterface> e = null;
try {
e = NetworkInterface.getNetworkInterfaces();
} catch (SocketException e1) {
e1.printStackTrace();
}
while (e.hasMoreElements()) {
NetworkInterface ni = e.nextElement();
sb.append(ni.toString());
}
machinePiece = sb.toString().hashCode();
return machinePiece;
}
}
|
使用
1
|
Long id = SnowFlake.nextId();
|
3.算法优缺点#
优点：
（1）高性能高可用：生成时不依赖于数据库，完全在内存中生成。
（2）容量大：每秒中能生成数百万的自增ID。
（3）ID自增：存入数据库中，索引效率高。
缺点：
（1）依赖与系统时间的一致性，如果系统时间被回调，或者改变，可能会造成id冲突或者重复(时钟重播造成的id重复问题)