雪花算法

发表于 更新于 分类于 阅读次数：

分布式 ID 生成方案。

雪花算法的核心思想是将一个64位的ID分成多个部分，每个部分代表不同的含义。

2023-05-04_16-02-04

具体分为四个部分：

  • 第一部分，占用 1 个 bit，其值永远是 0 ，因为 ID 永远都是正数 0 表示正数。
  • 第二部分是时间戳，占用 41 个 bit ，单位为毫秒，最大可以容纳约 69 年的时间，这里的时间戳不会从 1970 年开始计算，我们可以其从任意时间开始计算。
  • 第三部分是工作机器的 ID ，占用 10 个 bit，高五位为数据中心 ID，低五位为工作节点 ID 最多可以容纳 1024 个节点。
  • 第四部分为序列号，占用 12 个 bit，用来记录同毫秒内产生的不同 ID 。每个节点每毫秒从 0 开始累加，最多可以累加到 4095，同一毫秒最多可以产生 4096 个 ID。

实现逻辑如下：

  1. 首先实例化我们的节点对象，实例化参数分别为集群中统一使用的时间和节点的 ID 值。
  2. 因为存在并发的情况，所以生成 ID 的操作必须使用锁。
  3. 生成 ID 时，比对当前时间和记录的时间是否一致，如果一致则序列号+1。如果序列号满了则等待下一毫秒。如果不一致则序列号保持为 0。
  4. 记录新的时间戳。
  5. 拼接三段二进制的数据，使用位移和或运算拼接。
  6. 返回生成的 ID。

使用 Java 语言简单实现该算法。

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
package com.example.demo.snowflake;

public class Snowflake {

    // 基准时间戳
    private long baseTimestamp = 0L;
    // 上次记录的时间戳偏移量
    private long lastTimestamp = 0L;
    // 工作机器ID
    private long workerID = 0L;
    // 序列号
    private long sequence = 0L;

    // 序列号最大值
    private static final long MAX_SEQUENCE = 4096L;
    // 序列号位数
    private static final long SEQUENCE_BITS = 12L;
    // 工作机器ID位数
    private static final long WORKER_ID_BITS = 10L;
    // 工作机器ID最大值
    private static final long MAX_WORKER_ID = 1024L;
    // 工作机器ID左移位数
    private static final long WORKER_ID_SHIFT = SEQUENCE_BITS;
    // 时间戳左移位数
    private static final long TIMESTAMP_LEFT_SHIFT = SEQUENCE_BITS + WORKER_ID_BITS;

    public Snowflake(long baseTimestamp, long workerID) {
        if (System.currentTimeMillis() < baseTimestamp) {
            throw new RuntimeException("Base timestamp must be in the past");
        }

        if (workerID < 0 || workerID > MAX_WORKER_ID) {
            throw new RuntimeException("Worker ID must be between 0 and " + MAX_WORKER_ID);
        }

        this.baseTimestamp = baseTimestamp;
        this.workerID = workerID;
    }

    public synchronized long generateID() {
        // 获取当前时间戳(毫秒)
        long now = System.currentTimeMillis();
        // 计算时间戳偏移量
        long timestamp = now - this.baseTimestamp;

        // 处理时钟回拨
        if (timestamp <= this.lastTimestamp)
            waitUntilClockCatchUp(this.lastTimestamp);

        // 如果当前偏移量等于上次记录的偏移量,则说明在同一个毫秒内请求
        // 如果当前毫秒内请求次数超过4096次,则等待1毫秒
        // 否则,序列号加1
        if (timestamp == this.lastTimestamp) {
            // 这里是对序列号位进行递增并使用取模运算保证序列号不会超过4096
            this.sequence = (this.sequence + 1) & MAX_SEQUENCE;
            // 如果超出了最大值,则等待1毫秒
            if (this.sequence == 0) {
                // 获取下一毫秒
                try {
                    Thread.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                    throw new RuntimeException(e);
                }
                now = System.currentTimeMillis();
                timestamp = now - this.baseTimestamp;
            }
        } else {
            this.sequence = 0L;
        }
        // 记录当前时间戳
        this.lastTimestamp = timestamp;
        // 返回序列号
        return (timestamp << TIMESTAMP_LEFT_SHIFT) | (this.workerID << WORKER_ID_SHIFT) | this.sequence;
    }

    private void waitUntilClockCatchUp(long lastTimestamp) {
        long currentTimestamp;
        while ((currentTimestamp = System.currentTimeMillis() - this.baseTimestamp) <= lastTimestamp) {
            long sleepTime = lastTimestamp - currentTimestamp + 1;
            try {
                Thread.sleep(sleepTime); // 等待1毫秒
            } catch (InterruptedException e) {
                // 处理中断异常
                e.printStackTrace();
                throw new RuntimeException(e);
            }
        }
    }
}