分布式下使用雪花算法生成全局ID及解决时钟回拨问题

简介

雪花算法是 64 位 的二进制，一共包含了四部分：

• 1位是符号位，也就是最高位，始终是0，没有任何意义，因为要是唯一计算机二进制补码中就是负数，0才是正数
• 41位是时间戳，具体到毫秒，41位的二进制可以使用69年，因为时间理论上永恒递增，所以根据这个排序是可以的
• 10位是机器标识，可以全部用作机器ID，也可以用来标识机房ID + 机器ID，10位最多可以表示1024台机器
• 12位是计数序列号，也就是同一台机器上同一时间，理论上还可以同时生成不同的ID，12位的序列号能够区分出4096个ID

原版的java雪花算法

package com.yy.geturl.util;
/**
 * Twitter_Snowflake

 * SnowFlake的结构如下(每部分用-分开):

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

 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0

 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69

 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId

 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号

 * 加起来刚好64位，为一个Long型。

 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */

/**
 * @author code
 * @Date 2022/9/19 15:04
 * Description 雪花算法
 * Version 1.0
 */
public class SnowflakeIdWorker {

    // ==============================Fields===========================================
    /** 开始时间截 (2015-01-01) */
    private final long twepoch = 1420041600000L;

    /** 机器id所占的位数 */
    private final long workerIdBits = 5L;

    /** 数据标识id所占的位数 */
    private final long datacenterIdBits = 5L;

    /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大数据标识id，结果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** 序列在id中占的位数 */
    private final long sequenceBits = 12L;

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

    /** 数据标识id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 时间截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

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

    /** 工作机器ID(0~31) */
    private long workerId;

    /** 数据中心ID(0~31) */
    private long datacenterId;

    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;

    /** 上次生成ID的时间截 */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================
    /**
     * 构造函数
     * @param workerId 工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeIdWorker(long workerId, long datacenterId) {
        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;
    }

    // ==============================Methods==========================================
    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();

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

        //如果是同一时间生成的，则进行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

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

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    //==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);

        for (int i = 0; i < 10; i++) {
            long id = idWorker.nextId();
            System.out.println(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
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

解决了时钟回拨问题

改进后的雪花算法

package com.yy.geturl.util;

import java.io.IOException;

/**
 * @author code
 * @Date 2022/9/19 15:32
 * Description 优化
 * Version 1.0
 */
public class SnowflakeIdWorkerUtil {

    /** 因为二进制里第一个 bit 为如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0 */
    /** 机器ID  2进制5位  32位减掉1位 31个 */
    private long workerId;
    /** 机房ID 2进制5位  32位减掉1位 31个 */
    private long datacenterId;
    /** 代表一毫秒内生成的多个id的最新序号  12位 4096 -1 = 4095 个 */
    private long sequence;
    /** 设置一个时间初始值    2^41 - 1   差不多可以用69年 */
    private long twepoch = 1420041600000L;
     /** 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);

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 记录产生时间毫秒数，判断是否是同1毫秒 */
    private long lastTimestamp = -1L;
    public long getWorkerId(){
        return workerId;
    }
    public long getDatacenterId() {
        return datacenterId;
    }
    public long getTimestamp() {
        return System.currentTimeMillis();
    }

    /** 是否发生了时钟回拨 */
    private boolean isBackwordsFlag = false;
    /** 是否是第一次发生时钟回拨, 用于设置时钟回拨时间点 */
    private boolean isFirstBackwordsFlag = true;
    /** 记录时钟回拨发生时间点, 用于判断回拨后的时间达到回拨时间点时, 跳过 已经用过的 时钟回拨发生时间点 之后的时间 到 未来时间的当前时间点 */
    private long backBaseTimestamp = -1L;

    public SnowflakeIdWorkerUtil() {
    }

    public SnowflakeIdWorkerUtil(long workerId, long datacenterId, long sequence) {

        // 检查机房id和机器id是否超过31 不能小于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;
    }


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

        if (isBackwordsFlag) {
            //当回拨时间再次叨叨回拨时间点时, 跳过回拨这段时间里已经使用了的未来时间
            if (timestamp >= backBaseTimestamp && timestamp < lastTimestamp) {
                //直接将当前时间设置为最新的未来时间
                timestamp = lastTimestamp;
            } else if(timestamp > lastTimestamp) {
                //当前时间已经大于上次时间, 重置时钟回拨标志
                isBackwordsFlag = false;
                isFirstBackwordsFlag = true;
                System.out.println("时间已恢复正常-->" + timestamp);
            } else {
                // timestamp == lastTimestamp 等于的情况在后面
            }
        }
        // 判断是否小于上次时间戳，如果小于的话，就抛出异常
        if (timestamp < lastTimestamp) {

            System.err.printf("lastTimestamp=%d, timestamp=%d, l-t=%d \n", lastTimestamp, timestamp, lastTimestamp - timestamp);
//            throw new RuntimeException(
//                    String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
//                            lastTimestamp - timestamp));
            //这里不再抛出异常, 改为记录时钟回拨发生时间点
            //发生时钟回拨后, 当前时间 timestamp 就变成了 过去的时间
            //此时将 timestamp 设置为 上一次时间, 即相对于当前时间的未来时间
            timestamp = lastTimestamp;
            isBackwordsFlag = true;

            //记录时钟回拨发生的时间点, 后续需要跳过已经使用的未来时间段
            if (isFirstBackwordsFlag) {
                backBaseTimestamp = timestamp;
                isFirstBackwordsFlag = false;
                System.out.println("时钟回拨已发生-->" + backBaseTimestamp);
            }
            //--20220813--2---------------------------------------
        }

        // 下面是说假设在同一个毫秒内，又发送了一个请求生成一个id
        // 这个时候就得把seqence序号给递增1，最多就是4096
        if (timestamp == lastTimestamp) {

            // 这个意思是说一个毫秒内最多只能有4096个数字，无论你传递多少进来，
            //这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            sequence = (sequence + 1) & sequenceMask;
            //当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
            if (sequence == 0) {
                //这里也不能阻塞了, 因为阻塞方法中需要用到当前时间, 改为将此时代表未来的时间 加 1
                if (isBackwordsFlag) {
                    lastTimestamp++;
                } else {
                    timestamp = tilNextMillis(lastTimestamp);
                }
            }

        } else {
            //sequence = 0;
            //每毫秒的序列号都从0开始的话，会导致没有竞争情况返回的都是偶数。解决方法是用时间戳&1，这样就会随机得到1或者0。
            sequence = timestamp & 1;
        }
        // 这儿记录一下最近一次生成id的时间戳，单位是毫秒
        if(isBackwordsFlag) {
            //什么都不做
        } else {
            lastTimestamp = timestamp;
        }
        // 这儿就是最核心的二进制位运算操作，生成一个64bit的id
        // 先将当前时间戳左移，放到41 bit那儿；将机房id左移放到5 bit那儿；将机器id左移放到5 bit那儿；将序号放最后12 bit
        // 最后拼接起来成一个64 bit的二进制数字，转换成10进制就是个long型
        long sn = ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) | sequence;

        if (isBackwordsFlag) {
            System.out.printf("sn=%d\n", sn);
        }
        return sn;
    }

    /**
     * 当某一毫秒的时间，产生的id数 超过4095，系统会进入等待，直到下一毫秒，系统继续产生ID
     * @param lastTimestamp
     * @return
     */
    private long tilNextMillis(long lastTimestamp) {

        long timestamp = timeGen();

        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
    /** 获取当前时间戳 */
    private long timeGen(){
        return System.currentTimeMillis();
    }

    /**
     *  main 测试类
     * @param args
     */
    public static void main(String[] args) {
        SnowflakeIdWorkerUtil snowflakeIdWorkerUtil = new SnowflakeIdWorkerUtil(1, 1, 1);
        int count = 10;
        for (int i = 0; i < count; i++) {
            //实际测试发现遍历太快输出日志过多导致卡顿, 增加睡眠时间, 或输出到文件
            System.out.println(snowflakeIdWorkerUtil.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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193