1.前言
为了在集群部署环境下生成一个唯一id,产生了对分布式id生成的需求
2.雪花算法
2.1 算法介绍
SnowFlake
是Twitter公司采用的一种算法,目的是在分布式系统中产生全局唯一且趋势递增的ID。
雪花算法
由64bit
组成的数据
- 符号标识占用
1bit
- 时间戳占用
41bit
- 机器id占用
10bit
- 序列号占用
12bit
,作为同一毫秒内可以产生的序列号,也就是同一毫秒内可以产生4096个序列号,对应的并发409.6w/s
2.2 算法实现逻辑
雪花算法逻辑实现步骤:
-
当前生成时间戳与上一次的时间戳作比较
-
时间戳不一致,直接将序列号值设置为0
-
时间戳一致,判断序列号值
- 序列号值大于4096,需要等到下一毫秒生成唯一id
- 序列号小于4096,直接将序列号进行 + 1操作
-
将时间戳左移22位
-
将机器id左移12位
-
时间戳移位后的结果与机器id移位后的结果进行
异或
运算 -
将上一步得到的结果与序列号进行
异或
运算得到唯一id
伪代码实现:
int sequence = -1;
if (now == last) {
if (sequence < 4096) {
sequence ++;
} else {
sleep 1毫秒;
now = 当前时间戳;
}
} else {
sequence = 0;
}
long id = now << 22 | workId << 12 | sequence
复制代码
2.3 算法实现分析
有了算法实现逻辑,下面通过示例对算法实现进行分析,加深对算法的理解
打开在线工具,将当前时间转换成毫秒时间戳,假设当前时间:2021-11-04 14:14:54,对应毫秒时间戳:1636006494000
机器id:3,序列号:123,依照算法逻辑生成如下流程图:
通过分析生成的唯一id:6861908581810188411,我们也可以通过java代码来验证分析结果是否正确
public static void main(String[] args) {
long time = 1636006494000L;
System.out.println(time << 22 | 3 << 12 | 123);
}
复制代码
运行程序,输出结果:6861908581810188411与分析得出的结果一致
近期评论