首页 算法

# 介绍

雪花算法是 twitter 开源的由 64 位整数组成的分布式 id 。目的是在分布式系统中产生全局唯一且趋势递增的 ID 。

其核心思想就是：使用一个 64 bit 的 long 型的数字作为全局唯一 id 。在分布式系统中的应用十分广泛，且 ID 引入了时间戳，保持自增性且不重复。

# 雪花算法的结构

  • 标识： 没有实际意义。一般都是 0，都是正数。
  • 时间戳： 41 bit 可以表示的数字多达 2^41 - 1 ，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。
  • 机器 id: 这里标识的是机器的唯一标识，一般由两部分构成： 机房id+机器id 。一共 10 位，可以表示 1024 台机器。
  • 序列号：可以用这个 12 bit 代表的数字来区分同一个毫秒内的 4096 个不同的 id 。也就是同一毫秒内同一台机器所生成的最大 ID 数量为 4096

# 雪花算法的工作流程

以一个简单的雪花算法工作流程来说。假设有一个服务假设要生成一个全局唯一 id ，那么就可以发送一个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来生成唯一 id 。这个 SnowFlake 算法系统首先肯定是知道自己所在的机器号，（假设机器 id 为 10bit）接着 SnowFlake 算法系统接收到这个请求之后，首先就会用二进制位运算的方式生成一个 64 bit 的 long 型 id ， 64 个 bit 中的第一个 bit 是无意义的。接着用当前时间戳（单位到毫秒）占用 41 个 bit ，然后接着 10 个 bit 设置机器 id 。最后再判断一下，当前这台机房的这台机器上这一毫秒内，这是第几个请求，给这次生成 id 的请求累加一个序号，作为最后的 12 个 bit 。

# 雪花算法实现

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
194
195
196
197
198
199
200
201
202
203
package com.fxb.algorithm;

/**
 * 雪花算法生成器
 * <p>
 * 1.todo: 可以指定不同数据位数。
 * 2.todo: 单例
 *
 * @author fangjiaxiaobai
 * @date 2020-10-24 23:51
 * @since 1.0
 */
public class SnowFlakeGenerator {

    /**
     * 开始时间戳 (2015-01-01)
     */
    private final static long DEFAULT_TIMESTAMP = 1603556068000L;

    /**
     * 总位数
     */
    private final static long BITS_COUNT = 64L;
    /**
     * 机器id所占的位数,
     * 默认是5位。最多支持31台机器
     */
    private final static long DEFAULT_WORKER_ID_BITS = 5L;

    /**
     * 数据中心id所占的位数
     * 可以理解为机房。默认是5位。
     */
    private final static long DEFAULT_DATA_CENTER_ID_BITS = 5L;

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

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

    /**
     * 支持的数据中心数量
     */
    private final static long DEFAULT_MAX_DATA_CENTER_ID_BITS = ~(-1L << DEFAULT_DATA_CENTER_ID_BITS);

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

    /**
     * 时间戳向左移22位(5+5+12)
     */
    private final static long DEFAULT_TIMESTAMP_LEFT_SHIFT = DEFAULT_SEQUENCE_BITS + DEFAULT_WORKER_ID_BITS + DEFAULT_DATA_CENTER_ID_BITS;

    /**
     * 数据标识id向左移17位(12+5)
     */
    private final static long DEFAULT_DATA_CENTER_ID_SHIFT = DEFAULT_SEQUENCE_BITS + DEFAULT_WORKER_ID_BITS;

    /**
     * workId的位移
     */
    private final static long DEFAULT_WORKER_ID_SHIFT = DEFAULT_SEQUENCE_BITS;

    /**
     * 工作机器ID
     */
    private long workerId;

    /**
     * 数据中心ID
     */
    private long dataCenterId;

    /**
     * 支持的最大数据中心数
     */
    private long maxDataCenterId;

    /**
     * 支持的最大workerid数
     */
    private long maxWorkerId;

    /**
     * 序列号的位数
     */
    private Long sequenceBits;

    /**
     * 序列号的掩码
     * 即，2^sequenceBits
     */
    private Long sequenceMask;

    /**
     * 毫秒内序列
     */
    private long sequence = 0L;

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

    private long dataCenterIdShift;


    private long workerIdShift;
    /**
     * 时间戳的位数
     */
    private long timestampLeftShift;

    /**
     * 默认 每个数据中心可以容纳31台机器
     *
     * @param workerId     工作ID
     * @param dataCenterId 数据中心ID
     */
    public SnowFlakeGenerator(long workerId, long dataCenterId) {
        //...
    }

    /**
     * 根据自己的配置决定容纳的机器数
     *
     * @param workerId         工作机器的id
     * @param dataCenterId     数据中心的id
     * @param workerIdBits     工作机占的位数
     * @param dataCenterIdBits 数据中心占的位数
     */
    public SnowFlakeGenerator(long workerId, long dataCenterId, long workerIdBits, long dataCenterIdBits) {
      // ...
    }

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

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

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

        //上次生成ID的时间戳
        lastTimestamp = currentTimestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((currentTimestamp - DEFAULT_TIMESTAMP) << timestampLeftShift)
                | (dataCenterId << dataCenterIdShift)
                | (workerId << workerIdShift)
                | sequence;
    }

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

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

完整代码: http://dwz.date/cWmR

公众号中回复 【雪花算法】，可以直接获取源码文件。

# 最后

期望与你一起遇见更好的自己

期望与你一起遇见更好的自己