一、SnowFlake算法

       雪花算法(Snowflake)是twitter公司内部分布式项目采用的ID生成算法

1. Snowflake生成的是Long类型的ID，一个Long类型占8个字节，每个字节占8比特，也就是说一个Long类型占64个比特。
2. Snowflake ID组成结构：正数位(占1比特)+ 时间戳(占41比特)+ 机器ID(占5比特)+ 数据中心(占5比特)+ 自增值(占12比特)，总共64比特组成的一个Long类型。

• 第一位：占用1bit，Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。
• 时间戳：占用41bit，毫秒级的时间，不建议存当前时间戳，而是用(当前时间戳 - 固定开始时间戳)的差值，可以使产生的ID从更小的值开始;41位的时间戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年
• 工作机器id：占用10bit，最多可以容纳1024个节点（可以改造为5位工作中心+5位数据中心，具体如上图第二部分）
• 序列号：占用12bit，最多可以累加到4095。自增值支持同一毫秒内同一个节点可以生成4096个ID,这个值在同一毫秒同一节点上从0开始不断累加。(最大可以支持单节点差不多四百万的并发量)

SnowFlake可以保证：

所有生成的id按时间趋势递增
整个分布式系统内不会产生重复id（因为有datacenterId和workerId来做区分）
1
2

根据这个算法的逻辑，只需要将这个算法实现出来，封装为一个工具方法，那么各个业务应用可以直接使用该工具方法来获取分布式ID，只需保证每个业务应用有自己的工作机器id即可，而不需要单独去搭建一个获取分布式ID的应用。

二、代码实现

public class SnowFlake {
    // 因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。

    /**
     * 机器ID  2进制5位
     */
    private long workerId;

    /**
     * 机房ID 2进制5位
     */
    private long datacenterId;

    /**
     * 代表一毫秒内生成的多个id的最新序号  12位，范围从0到4095
     */
    private long sequence;

    /**
     * 设置一个时间初始值(这个用自己业务系统上线的时间)    2^41 - 1   差不多可以用69年
     */
    private long twepoch = 1585644268888L;

    /**
     * 5位的机器id
     */
    private long workerIdBits = 5L;

    /**
     * 5位的机房id
     */
    private long datacenterIdBits = 5L;

    /**
     * 每毫秒内产生的id数 2 的 12次方
     */
    private long sequenceBits = 12L;

    /**
     * 这个是二进制运算，就是5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
     */
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 这个是一个意思，就是5 bit最多只能有31个数字，机房id最多只能是32以内
     */
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /**
     * 机器ID向左移12位
     */
    private long workerIdShift = sequenceBits;

    /**
     * 机房ID向左移17位
     */
    private long datacenterIdShift = sequenceBits + workerIdBits;

    /**
     *时间戳向左移22位
     */
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 上次生成ID的时间截，记录产生时间毫秒数，判断是否是同1毫秒
     */
    private long lastTimestamp = -1L;

    /**
     * 构造函数
     * @param workerId
     * @param datacenterId
     * @param sequence
     */
    public SnowFlake(long workerId, long datacenterId, long sequence){

        // 检查机房id和机器id是否超过最大值，不能小于0
        if (workerId>maxWorkerId||workerId<0){
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
        }

        if (datacenterId>maxDatacenterId||datacenterId<0){
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
        }

        this.workerId=workerId;
        this.datacenterId=datacenterId;
        this.sequence=sequence;
    }

    /**
     * 这个是核心方法，通过调用nextId()方法，让当前这台机器上的snowflake算法程序生成一个全局唯一的id
     * @return
     */
    public synchronized long nextId(){
        // 获取当前的时间戳，单位是毫秒
        long timestamp=timeGen();

        //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常
        if (timestamp<lastTimestamp){
            System.err.printf("clock is moving backwards. Rejecting requests until %d.",lastTimestamp);
            throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",lastTimestamp-timestamp));
        }

        // 下面是说假设在同一个毫秒内，又发送了一个请求生成一个id
        // 这个时候就得把seqence序号给递增1，最多就是4096
        if (lastTimestamp == timestamp) {
            // 这个意思是说一个毫秒内最多只能有4096个数字，无论你传递多少进来，
            //这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            sequence = (sequence + 1) & sequenceMask;
            //当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }else{ // 时间戳改变，毫秒内序列重置
            sequence=0;
        }

        //上次生成ID的时间截
        lastTimestamp=timestamp;

        // 这儿就是最核心的二进制位运算操作，生成一个64bit的id
        // 先将当前时间戳左移，放到41 bit那儿；将机房id左移放到5 bit那儿；将机器id左移放到5 bit那儿；将序号放最后12 bit
        // 最后拼接起来成一个64 bit的二进制数字，转换成10进制就是个long型
        return ((timestamp-twepoch)<<timestampLeftShift)|
                (datacenterId<<datacenterIdShift)|
                (workerId<<workerIdShift)|sequence;
    }

    /**
     * 当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp=timeGen();
        while(timestamp<=lastTimestamp){
            timestamp=timeGen();
        }
        return timestamp;
    }

    /**
     * 获取当前时间戳
     * @return 当前时间(毫秒)
     */
    private long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * main 测试类
     * @param args
     */
    public static void main(String[] args) {
        SnowFlake worker=new SnowFlake(1,1,1);
        for (int i=0;i<22;i++){
            System.out.println(worker.nextId());
        }
    }
}
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

产生的唯一序列ID：
309845423537917952
309845423542112256
309845423542112257
309845423542112258
309845423542112259
309845423542112260
309845423542112261
309845423542112262
309845423542112263
309845423542112264
309845423542112265
309845423542112266
309845423542112267
309845423542112268
309845423542112269
309845423542112270
309845423542112271
309845423542112272
309845423542112273
309845423542112274
309845423542112275
309845423542112276
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

三、应用场景

1.数据库表主键：很多DBA在大型生产应用禁用auto_increment的ID，这时可以选snowflake替代。
2.TraceId：分布式系统追踪，希望用一个ID贯穿所有子系统来追踪分布式交互过程。也有系统产生一个Exception，我们需要对Exception编号等。
3. 摇一摇/抢红包ID：摇一摇的特点是活动促销的时候，短时间内访问特别大，需要一个高性能的ID生成器。

四、优缺点

优点：

1. ID在内存生成，不依赖于数据库，高性能高可用。
2. 每秒可生成几百万ID，容量大
3. 由于ID呈趋势递增，插入数据库后，使用索引的时候性能较高。

缺点：

1. 依赖于系统时钟的一致性，如果某台机器的系统时钟回拨，有可能造成ID冲突或者ID乱序。
2. 同一台机器的系统时间回拨过，那么有可能出现ID重复的情况

五、分布式生成ID方式

1. UUID
   UUID(Universally Unique Identifier)的标准型式包含32个16进制数字，以连字号分为五段，形式为8-4-4-4-12的36个字符。示例：5f26d8c0-6e09-43cf-9300-6fda1d11985c

• 优点：
  性能非常高，本地生成，没有网络消耗；实现了唯一性。
• 缺点：
  1.无序，无法预测它的生成顺序，不能生成递增有序数字。
  2.主键，ID作为主键时在特定环境中会存在一些问题。例如在做DB主键的场景下，UUID就非常不适用。MySQL官方有明确的建议主键要尽量越短越好。
  3.索引，B+树索引的分裂。分布式id作为主键，而主键包含索引，mysql的索引是通过B+树实现的，每一次新的UUID数据的插入，为了查询优化，都会对索引底层的B+树进行修改，又因为UUID是无序的，所以每一次UUID数据的插入会对主键底层的B+树进行很大的修改，这样会导致一些中间节点断裂，也会创造出很多不饱和的节点，这样大大降低了数据库的插入操作。

UUID只能保证全局唯一性，不满足后面的趋势递增，单调递增
1

2. 数据库主键自增
   在分布式里面，数据库的自增ID机制主要原理是：数据库自增ID和mysql数据库的replace into实现的。
   这里replace into跟insert功能类似，不同点在于：replace into首先尝试插入数据列表中，如果发现表中已经存在此行数据(根据主键或唯一索引判断)则先删除，再插入；否则则可以直接插入新数据。
   replace into的含义是插入一条记录，如果表中唯一索引的值遇到冲突，则替换老数据。

• 优点：
  实现了唯一性、趋势递增。
• 缺点（集群情况）：
  1.系统水平拓展比较困难，比如定义好了步长和机器台数之后，如果需要新添加机器怎么做？假设现在 只有一台机器发号是1，2，3，4，5(步长=1)，这时候需要扩容一台新机器：将第二台机器的初值设置的比第一台多很多。当扩容机器达到100台呢？就会出现初值设置会非常大。
  2.数据库压力还是很大，每次获取id都得读写一次数据库，非常影响性能，不符合分布式ID系统低延迟、高QPS的硬性要求。

我们每次插入的时候，发现都会把原来的数据给替换，并且ID也会增加
这就满足了：递增性、单调性、唯一性
在分布式情况下，并且并发量不多的情况，可以使用这种方案来解决，获得一个全局的唯一ID

3. Redis

• 单机版
  因为Redis是单线程的，天生就能够保证原子性，可以使用原子操作INCR和INCRBY来实现。

• 集群分布式
  Redis集群可以获取更高的吞吐量。
  注意：
  在Redis集群情况下，同样和MySQL一样需要设置不同的增长步长，同时key一定要设置有效期，可以使用Redis集群来获取更高的吞吐量。

• 假如一个集群有Redis，可以初始化每台Redis的值分别为1，2，3，4，5，然后步长都是5：
  各个Redis生成的ID为：
  A：1，6，11，16，21
  B：2，7，12，17，22
  C：3，8，13，18，23
  D：4，9，14，19，24
  E：5，10，15，20，25
  缺点：需要额外配置和维护Redis集群等工作才能获得id，比较麻烦。

4. 雪花算法

• 优点
  1.毫秒数在高维，自增序列在低位，整个ID都是趋势递增的
  2.不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的
  3.可以根据自身业务特性分配bit位，非常灵活
• 缺点
  1.依赖机器时钟，如果机器时钟回拨，会导致重复ID生成
  2.在单机上是递增的，但由于涉及到分布式环境，每台机器上的时钟不可能完全同步，有时候会出现不是全局递增的情况，此缺点可以认为无所谓，一般分布式ID只要求趋势递增，并不会严格要求递增，90%的需求只要求趋势递增。

其它补充：
为了解决时钟回拨问题，导致ID重复，后面有人专门提出了解决的方案

• UidGenerator - 百度开源的分布式唯一ID生成器
• Leaf - 美团点评分布式ID生成系统

参考：
参考一
参考二
参考三