分布式id之雪花算法

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与分析得出的结果一致