写在前面
最近学习也有点陷入迷茫状态，不知道学些什么，也不知道写点什么。那就想起什么就写点啥，就当是重新学习。
今天要来讲的是分布式系统中常用的一种算法，雪花算法。
正文
什么是雪花算法
雪花算法(snowflake)，它是Twitter公司使用的在分布式系统中生成唯一ID的一个算法，在2014年开源。
雪花算法是在高并发环境下生成为ID的算法，它能保证分布式环境下ID不重复，且基本有序递增，并且不依赖与其他的第三方库。
雪花算法的原理
雪花算法的原理十分简单，它生成的ID由64bit组成，其中包括：
- 1bit的标志位，由于二进制中最高为1的都是负数，并且生成的id一般都是整数，所以这一位通常为0.
- 41bit的时间戳，可以存储69年的时间，一般来说起始时间戳为系统上线的时间戳。
- 10bit的机器id，可以部署1024个节点。
- 12bit序列号，用来表示同一时间戳下生成的不同id，在同一个时间戳下可以表示4095个序列号。
因为刚好是64bit，所以在Java中刚好由long类型来存储。倒不如说是这个算法可能一开始就想好使用long类型来存储。
代码实现
当然最重要的还是如何生成ID啦，那生成的算法网上有很多，我就依照可能大家看的最多的代码，来讲讲自己的理解。
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
| public class SnowFlake {
private final long startTimestamp = 1602172800L;
private final long workerIdBits = 10L;
private final long maxWorkerId = ~(-1L << workerIdBits);
private final long sequenceBits = 12L;
private final long sequenceMask = ~(-1L << sequenceBits);
private final long workerIdShift = sequenceBits;
private final long timestampLeftShift = sequenceBits + workerIdBits;
private long workerId;
private long sequence = 0L;
private long lastTimestamp = -1L;
public SnowFlake(long workerId) {
if (workerId < 0 || workerId > maxWorkerId){
throw new RuntimeException("机器id不正确");
}
this.workerId = workerId;
}
public synchronized long nextId(){
long timestamp = System.currentTimeMillis();
if (timestamp < lastTimestamp){
throw new RuntimeException("系统时间被回退");
}
if (lastTimestamp == timestamp){
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0){
timestamp = getNextMillis(lastTimestamp);
}
}
else{
sequence = 0L;
}
lastTimestamp = timestamp;
return ((timestamp - startTimestamp) << timestampLeftShift)
| (workerId << workerIdShift)
| sequence;
}
private long getNextMillis(long lastTimestamp){
long timestamp = System.currentTimeMillis();
while (timestamp <= lastTimestamp){
timestamp = System.currentTimeMillis();
}
return timestamp;
}
}
|
在代码中都有相应的注释。其中需要理解的可能是生成最大值的位运算，比如maxWorkerId = ~(-1L << workerIdBits);。
首先负数在计算机中是使用补码进行表示，补码是负数绝对值的原码，取反码再加一。-1的绝对值是1，1的原码就是最后一位是1，取反码，就是0变1,1变0，再加1，就得到了全是1的二进制。
然后左移workerIdBits位，也就是12位，然后再取反，就得到了最大值，即1023。
那其实取最大值有两种写法，一种是maxWorkerId = -1L ^ (-1L << workerIdBits);还有一种就是上面的写法，一种是异或一种是取反，得到的结果都是相同的。我个人也不确定哪种比较好，idea中提示我使用取反操作，那就当取反操作可能更好一些。当然这只是idea的建议，真正要区分的话还得看两种方法的底层速度比较，我对位运算不熟悉，希望有大佬能比较一下。
后续一些思考
那雪花算法并不算难，通常情况下我们可以对雪花算法进行魔改。比如我可能不需要用到1024个节点啊，那么就把workIdBit减少，然后时间戳增加或者序列号增加。
又或者我这个系统可能用不到69年，那就可以适当减少时间戳比特位。
那还有就是workid的问题，即workid该怎么决定？那我们可以通过JVM传参，即-D选项，那如果是通过容器化部署的话，可能没办法传入不同参数，那可以通过某些规则来计算workid，比如可以通过该台机器的ip地址或者mac地址来计算workid，但是需要保证workid不重复，否则即使在并发不高的情况下，id也可能重复，至于实现，这里便不再展开，感兴趣的可以自己写写。
