分布式Snowflake雪花算法

主键ID生成方式比较

  • UUID(缺点:太长、没法排序、使数据库性能降低)
  • Redis(缺点:必须依赖Redis)
  • Oracle序列号(缺点:用Oracle才能使用)
  • Snowflake雪花算法(优点:生成有顺序的id,提高数据库的性能)

Snowflake雪花算法解析

雪花算法snowflake的结构如下(每部分用-分开):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

  • 第一位为未使用,接下来的41位为毫秒级时间(41位的长度可以使用69年)
  • 然后是5位datacenterId和5位workerId(10位的长度最多支持部署1024个节点)
  • 最后12位是毫秒内的计数(12位的计数顺序号支持每个节点每毫秒产生4096个ID序号)

一共加起来刚好64位,为一个Long型(转换成字符串长度为18)

Snowflake算法核心把时间戳,工作机器id,序列号组合在一起

整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由datacenter和机器ID作区分),并且效率较高,经测试,snowflake每秒能够产生26万ID左右,完全满足需要。

分布式Snowflake雪花算法代码

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
123
124
125
126
127
128
129
130
131
132
public class SnowFlakeGenerator {
public static class Factory {
/**
* 每一部分占用位数的默认值
*/
private final static int DEFAULT_MACHINE_BIT_NUM = 5; //机器标识占用的位数
private final static int DEFAULT_IDC_BIT_NUM = 5;//数据中心占用的位数

private int machineBitNum;
private int idcBitNum;

public Factory() {
this.idcBitNum = DEFAULT_IDC_BIT_NUM;
this.machineBitNum = DEFAULT_MACHINE_BIT_NUM;
}

public Factory(int machineBitNum, int idcBitNum) {
this.idcBitNum = idcBitNum;
this.machineBitNum = machineBitNum;
}

public SnowFlakeGenerator create(long idcId, long machineId) {
return new SnowFlakeGenerator(this.idcBitNum, this.machineBitNum, idcId, machineId);
}
}

/**
* 起始的时间戳
* 作者写代码时的时间戳
*/
private final static long START_STAMP = 1508143349995L;

/**
* 可分配的位数
*/
private final static int REMAIN_BIT_NUM = 22;

/**
* idc编号
*/
private long idcId;

/**
* 机器编号
*/
private long machineId;

/**
* 当前序列号
*/
private long sequence = 0L;

/**
* 上次最新时间戳
*/
private long lastStamp = -1L;

/**
* idc偏移量:一次计算出,避免重复计算
*/
private int idcBitLeftOffset;

/**
* 机器id偏移量:一次计算出,避免重复计算
*/
private int machineBitLeftOffset;

/**
* 时间戳偏移量:一次计算出,避免重复计算
*/
private int timestampBitLeftOffset;

/**
* 最大序列值:一次计算出,避免重复计算
*/
private int maxSequenceValue;

private SnowFlakeGenerator(int idcBitNum, int machineBitNum, long idcId, long machineId) {
int sequenceBitNum = REMAIN_BIT_NUM - idcBitNum - machineBitNum;

if (idcBitNum <= 0 || machineBitNum <= 0 || sequenceBitNum <= 0) {
throw new IllegalArgumentException("error bit number");
}

this.maxSequenceValue = ~(-1 << sequenceBitNum);

machineBitLeftOffset = sequenceBitNum;
idcBitLeftOffset = idcBitNum + sequenceBitNum;
timestampBitLeftOffset = idcBitNum + machineBitNum + sequenceBitNum;

this.idcId = idcId;
this.machineId = machineId;
}

/**
* 产生下一个ID
*/
public synchronized long nextId() {
long currentStamp = getTimeMill();
if (currentStamp < lastStamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
}

//新的毫秒,序列从0开始,否则序列自增
if (currentStamp == lastStamp) {
sequence = (sequence + 1) & this.maxSequenceValue;
if (sequence == 0L) {
//Twitter源代码中的逻辑是循环,直到下一个毫秒
lastStamp = tilNextMillis();
//throw new IllegalStateException("sequence over flow");
}
} else {
sequence = 0L;
}

lastStamp = currentStamp;

return (currentStamp - START_STAMP) << timestampBitLeftOffset | idcId << idcBitLeftOffset | machineId << machineBitLeftOffset | sequence;
}

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

private long tilNextMillis() {
long timestamp = getTimeMill();
while (timestamp <= lastStamp) {
timestamp = getTimeMill();
}
return timestamp;
}
}