雪花算法（SnowFlake）

雪花算法（SnowFlake）

Twitter雪花算法

雪花算法原理是生成一个的64位比特位的long类型的唯一id

  • 最高1位固定值0，使生成的id为正整数
  • 41位存储毫秒级时间戳，2^41/(1000606024365)=69，大概可以使用69年
  • 10位存储机器码，包括5位datacenterId和5位workerId，最多可以部署2^10=1024台机器
  • 12位存储序列号，时间戳同一毫秒时，通过这个递增的序列号来区分，即对于同一台机器，一毫秒时间戳可以生成2^12=4096个不重复id

可以将雪花算法作为一个单独的服务进行部署，然后需要全局唯一 id 的系统，请求雪花算法服务获取 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
154
155
156
157
/**
 * 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左右。
 */
public class SnowflakeIdWorker {
    // ==============================Fields===========================================
    /** 开始时间截 (2020-08-28) */
    private final long twepoch = 1598598185157L;

    /** 机器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) 此方法是判断传入的机房号和机器号是否超过了最大值，即31，或者小于0
     */
    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() {
        // 1.获取当前的系统时间
        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 要增1, 但要预防sequence超过 最大值4095，所以要 与 SEQUENCE_MASK 按位求与
            // 即如果此时sequence等于4095，加1后为4096，再和4095按位与后，结果为0
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        // 上次生成ID的时间截
        // 把当前时间赋值给 lastTime, 以便下一次判断是否处在同一个毫秒内
        lastTimestamp = timestamp;

        // 移位并通过或运算拼到一起组成64位的ID
        long id = ((timestamp - twepoch) << timestampLeftShift) // 时间戳减去默认时间 再左移22位 与运算
                | (datacenterId << datacenterIdShift) // 机房号 左移17位 与运算
                | (workerId << workerIdShift) // 机器号 左移12位 与运算
                | sequence; // 序列号无需左移 直接进行与运算
        return id;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * 
     * @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 < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(id);
        }
    }
}

SnowFlake 雪花算法详解与实现 - 掘金

snowflake算法(雪花算法)_LQJ灬的博客-CSDN博客

分布式唯一 ID 生成方案浅谈

分布式自增ID算法——雪花算法 - 简书

雪花算法改（增加数据信息）

根据实际项目的需要，修改SnowFlake的结构

0 - 0000000000 0000000000 0000000000 00000 - 0 - 0 - 0 - 0000000000 0000000000 00000

  • 1位标识

  • 36位时间截(毫秒级)

  • 3位数据机器位

  • 4位毫秒内序列

  • 20位信息序列，存储数据的信息，信息以首字母的形式存储，每5位表示一个字母，0表示空，1-26表示a-z；该信息序列可以表示4个字母，存储部分数据，方便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
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
import java.util.Date;
import java.text.SimpleDateFormat;

/**
 * SnowFlake的结构如下(每部分用-分开):
 * 0 - 0000000000 0000000000 0000000000 000000 - 0 - 00 - 0000 - 0000000000
 * 0000000000
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0
 * 36位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。35位的时间截，可以使用1年，年T
 * = (1L << 36) / (1000L * 60 * 60 * 24 * 365) = 2
 * 3位的数据机器位，可以部署在4个节点，包括1位datacenterId和1位workerId
 * 4位毫秒内序列，毫秒内的计数，1位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生2个ID序号
 * 20位信息序列，存储数据信息，信息以首字母的形式存储，每5位表示一个字母，0表示空，1~26表示a~z
 * 加起来刚好64位，为一个Long型。
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class MySnowflakeIdWorker {
    // ==============================Fields===========================================
    /** 开始时间截 (2023-06-16) */
    private final long startTimestamp = 1686904669147L;

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

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

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

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

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

    /** 信息在id中占的位数 */
    private final long infoBits = 20L;

    /* 时间戳在id中占的位数 */
    private final long timestampBits = 64 - 1 - workerIdBits - datacenterIdBits - sequenceBits - infoBits;

    /** 序列向左移25位 */
    private final long sequenceShift = infoBits;

    /** 机器ID向左移26位(25+1) */
    private final long workerIdShift = infoBits + sequenceBits;

    /** 数据中心id向左移27位(25+1+1) */
    private final long datacenterIdShift = infoBits + sequenceBits + workerIdBits;

    /** 时间截向左移28位(25+1+1+1) */
    private final long timestampShift = infoBits + sequenceBits + workerIdBits + datacenterIdBits;

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

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

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

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

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

    // ==============================Constructors=====================================
    /**
     * 构造函数
     * 此方法是判断传入的机房号和机器号是否超过了最大值，即31，或者小于0
     * 
     * @param workerId     工作ID (0~1)
     * @param datacenterId 数据中心ID (0~1)
     */
    public MySnowflakeIdWorker(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 (该方法是线程安全的)
     * 
     * @param data
     * @return SnowflakeId
     */
    public synchronized long nextId(String data) {
        // 1.获取当前的系统时间
        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 要增1, 但要预防sequence超过 最大值4095，所以要 与 SEQUENCE_MASK 按位求与
            // 即如果此时sequence等于4095，加1后为4096，再和4095按位与后，结果为0
            sequence = (sequence + 1) & sequenceMask;
            // 毫秒内序列溢出
            if (sequence == 0) {
                // 阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        // 上次生成ID的时间截
        // 把当前时间赋值给 lastTime, 以便下一次判断是否处在同一个毫秒内
        lastTimestamp = timestamp;

        // 根据数据生成信息序列
        long info = infoGen(data);

        // 移位并通过或运算拼到一起组成64位的ID
        long id = ((timestamp - startTimestamp) << timestampShift) // 时间戳减去默认时间 再左移28位 或运算
                | (datacenterId << datacenterIdShift) // 机房号 左移27位 或运算
                | (workerId << workerIdShift) // 机器号 左移26位 或运算
                | (sequence << sequenceShift) // 序列号 左移25位 或运算
                | (info); // 信息号 无需左移 直接进行或运算
        return id;
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * 
     * @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();
    }

    /**
     * 根据数据生成信息序列
     * 
     * @param data
     * @return 信息序列
     */
    protected long infoGen(String data) {
        String s = PinYinUtil.getDataHeadChar(data);
        long info = string2long(s);
        return info;
    }

    /**
     * 将字符串转换为long，每个字符对应5位
     * 
     * @param str
     * @return 信息序列
     */
    protected long string2long(String str) {
        char[] cs = str.toCharArray();
        long lo = 0;
        for (int i = 0; i < cs.length; i++) {
            lo = lo << 5;
            if (cs[i] != ' ') {
                lo += cs[i] - 'a' + 1;
            }
        }
        return lo;
    }

    protected void idDecoder(long id) {
        long timestampFilter = (-1L ^ (-1L << timestampBits) << timestampShift);
        long datacenterIdFilter = (-1L ^ (-1L << datacenterIdBits) << datacenterIdShift);
        long workerIdFilter = (-1L ^ (-1L << workerIdBits) << workerIdShift);
        long sequenceFilter = (-1L ^ (-1L << sequenceBits) << sequenceShift);
        long infoFilter = -1L ^ (-1L << infoBits);
        long ts = ((id & timestampFilter) >> timestampShift) + startTimestamp;
        long did = (id & datacenterIdFilter) >> datacenterIdShift;
        long wid = (id & workerIdFilter) >> workerIdShift;
        long seq = (id & sequenceFilter) >> sequenceShift;
        long info = id & infoFilter;
        System.out.println("time: " + new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date(ts)));
        System.out.println("datacenter id: " + did);
        System.out.println("worker id: " + wid);
        System.out.println("sequence: " + seq);
        System.out.println("data: " + PinYinUtil.getDataFromLong(info));
    }

    // ==============================Test=============================================
    /** 测试 */
    public static void main(String[] args) {
        MySnowflakeIdWorker idWorker = new MySnowflakeIdWorker(0, 0);
        long l = idWorker.nextId("你好谢谢");
        System.out.println(l);
        System.out.println(Long.toBinaryString(l));
        idWorker.idDecoder(l);
    }
}
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
import net.sourceforge.pinyin4j.PinyinHelper;

public class PinYinUtil {

    private static int dataWord = 4;

    /* 去掉字符串中的其他符号，值保留英文和中文 */
    public static String string2AllTrim(String value) {
        if (isNull(value)) {
            return "";
        }
        return value.replaceAll("[^a-zA-Z\u4e00-\u9fa5]", "");
    }

    /* 判断字符串是否为空 */
    public static boolean isNull(Object strData) {
        if (strData == null || String.valueOf(strData).trim().equals("")) {
            return true;
        }
        return false;
    }

    /* 提取每个汉字的首字母(小写) */
    public static String getPinYinHeadChar(String str) {
        if (isNull(str)) {
            return "";
        }
        String convert = "";
        for (int j = 0; j < str.length(); j++) {
            char word = str.charAt(j);
            // 提取汉字的首字母
            String[] pinyinArray = PinyinHelper.toHanyuPinyinStringArray(word);
            if (pinyinArray != null) {
                convert += pinyinArray[0].charAt(0);
            } else {
                convert += word;
            }
        }

        convert = string2AllTrim(convert);
        return convert.toLowerCase();
    }

    /* 获取数据的首字母，长度为4，多则删除少则空格填补 */
    public static String getDataHeadChar(String str) {
        String s = PinYinUtil.getPinYinHeadChar(str);
        if (s.length() < dataWord) {
            for (int i = 0; i < dataWord - s.length(); i++) {
                s += " ";
            }
        } else if (s.length() > dataWord) {
            s = s.substring(0, dataWord);
        }
        return s;
    }

    /* 将long信息序列转换为字母字符串 */
    public static String long2InfoString(long lo) {
        long filter = -1L ^ (-1L << 5);
        StringBuffer info = new StringBuffer();
        while (lo != 0) {
            int n = (int) (lo & filter);
            if (n == 0) {
                char c = ' ';
                info.append(c);
            } else {
                char c = (char) ('a' + n - 1);
                info.append(c);
            }
            lo = lo >> 5;
        }
        return info.reverse().toString();
    }

    public static String getDataFromLong(long lo) {
        String data = long2InfoString(lo);
        return data;
    }

    /* 测试 */
    public static void main(String[] args) {
        System.out.println(PinYinUtil.getDataHeadChar("你好谢谢"));
    }

}

java获取汉字的首字母_java获取中文首字母_可乐丿不加冰的博客-CSDN博客

开发
#代码
雪花算法（SnowFlake）
https://wangaaayu.github.io/blog/posts/75e39d48/
作者
WangAaayu
发布于
2023年6月14日
更新于
2023年6月17日
许可协议