雪花id生成算法_雪花算法生成id

什么是雪花算法

雪花算法的本质为生成一个64位长度的具有自增性的分布式全局唯一id。在64bits中，会对不同段的位进行划分。可分为：

1. 符号段
2. 时间戳段
3. 机器码段(data center + worker)
4. 自增序列号段

位段详解

1. 第一位 : 符号位，正数为0。
2. [2, 42] : 41位时间戳位，表明id的生成时间点(完整时间戳: 起始时间戳 + 41位时间戳)。41位最多能表示的时间为： (2^41-1) / (1000 * 60 * 60 * 24 * 365) 约等为69.73年。
3. [43, 47] : 5位data center id。data center id + worker id 共10位，最多能表示1024个机器。不同机器保证机器码段的位值不同即可。
4. [48, 52] : 5位worker id。data center id + worker id 共10位，最多能表示1024个机器。不同机器保证机器码段的位值不同即可。
5. [53, 64] : 12位自增序列号，用于区分同一毫秒内生成的id。序列号范围: [0, 2^12-1]，最多有2^12个，即4096个。

优点

1. 算法简单，基于内存，生成效率高
2. 支持分布式环境下的多节点服务（机器码段），秒内可生成百万个唯一id
3. 基于时间戳 与 同时间戳下自增序列号，生成的id具有自增性
4. 具有业务定制性，根据业务的不同可以对不同段的位数进行变更。比如业务持续时长不会那么久，就可以将时间戳段减少位数，补充给自增序列段，使每一毫秒能生成更多的id。

问题

依赖服务器时间。若服务器时钟回拨，可能会导致生成的id重复。可在代码中新增lastTimeMillis字段，在获取nextId时根据系统当前时间进行判断解决。
但若不进行持久化处理，服务重启后发生时钟回拨依旧会出现重复问题。

实际应用

1. mybatis plus：使用雪花算法生成id：@TableId(value = “id”, type = IdType.ID_WORKER)。id字段若不指定类型，默认使用雪花算法生成id
2. Hutool工具包：IdUtil.createSnowflake(workerId, datacenterId);

具体实现

/**
 * Created by QQ.Cong on 2022-07-22 / 9:48
 *
 * @author: CongQingquan
 * @Description: Snowflake util
 */
public class SnowflakeUtils {

    // ============================== Basic field ==============================//

    // Datacenter id
    private long datacenterId;

    // Worker id
    private long workerId;

    // Increment sequence
    private long sequence;

    // ============================== Bits ==============================//

    // Bits of datacenter id
    private long datacenterIdBits;

    // Bits of worker id
    private long workerIdBits;

    // Bits of sequence
    private long sequenceBits;

    // ============================== Largest ==============================//

    // Largest datacenter id
    private long largestDatacenterId;

    // Largest worker id
    private long largestWorkerId;

    // Largest sequence
    private long largestSequence;

    // ============================== Shift ==============================//

    // Left shift num of worker id
    private long workerIdShift;

    // Left shift num of datacenter id
    private long datacenterIdShift;

    // Left shift num of timestamp
    private long timestampShift;

    // ============================== Other ==============================//

    // Epoch
    private long epoch;

    // The timestamp that last get snowflake id
    private long lastTimestamp;

    // ============================== End ==============================//

    public SnowflakeUtils(long dataCenterId, long workerId) {
        // Default epoch: 2022-07-22 00:00:00
        this(1658419200000L, -1L, dataCenterId, workerId, 5L, 5L, 5L);
    }

    public SnowflakeUtils(long epoch, long lastTimestamp, long datacenterId, long workerId,
        long datacenterIdBits, long workerIdBits, long sequenceBits) {
        this.epoch = epoch;
        this.lastTimestamp = lastTimestamp;
        this.datacenterId = datacenterId;
        this.workerId = workerId;
        this.sequence = 0L;
        this.datacenterIdBits = datacenterIdBits;
        this.workerIdBits = workerIdBits;
        this.sequenceBits = sequenceBits;
        this.largestDatacenterId = ~(-1L << datacenterIdBits);
        this.largestWorkerId = ~(-1L << workerIdBits);
        this.largestSequence = ~(-1L << sequenceBits);
        if (datacenterId > largestDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(
                String.format("The datacenter id param can't be greater than %s or less than 0",
                    largestDatacenterId));
        }
        if (workerId > largestWorkerId || workerId < 0) {
            throw new IllegalArgumentException(
                String.format("The worker id param can't be greater than %s or less than 0",
                    largestWorkerId));
        }
        this.workerIdShift = sequenceBits;
        this.datacenterIdShift = workerIdShift + workerIdBits;
        this.timestampShift = datacenterIdShift + datacenterIdBits;
    }

    /**
     * Get snowflake id
     * @return
     */
    public synchronized long nextId() {
        long timestamp = System.currentTimeMillis();
        // 若时钟回退
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                "System clock moved backward, cannot to generate snowflake id");
        }
        // 若当前毫秒内多次生成雪花id
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & largestSequence;
            // 序列溢出
            if (sequence == 0) {
                timestamp = waitUntilNextMilli(timestamp);
            }
        }
        // 若当前毫秒内首次生成雪花id
        else {
            sequence = 0L;
        }
        // 更新获取雪花id的时间戳
        lastTimestamp = timestamp;
        // 生成雪花id (通过位或运算符进行拼接)
        return ((timestamp - epoch) << timestampShift) // 时间戳段
            | (datacenterId << datacenterIdShift) // 机器码段
            | (workerId << workerIdShift) // 机器码段
            | sequence; // 自增序列段
    }

    /**
     * Wait until next millisecond
     * @param lastTimestamp
     * @return
     */
    private long waitUntilNextMilli(long lastTimestamp) {
        long currentTimeMillis;
        do {
            currentTimeMillis = System.currentTimeMillis();
        }
        while (currentTimeMillis <= lastTimestamp);
        return currentTimeMillis;
    }

    /**
     * Get util instance
     * @param dataCenterId
     * @param workerId
     * @return
     */
    public static SnowflakeUtils getInstance(long dataCenterId, long workerId) {
        return new SnowflakeUtils(dataCenterId, workerId);
    }
}
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