当前位置：首页 > news >正文

雪花算法详解及源码分析

news 来源：原创 2024/9/29 10:21:22

雪花算法的简介：

雪花算法用来实现全局唯一ID的业务主键，解决分库分表之后主键的唯一性问题，所以就单从全局唯一性来说，其实有很多的解决方法，比如说UUID、数据库的全局表的自增ID

但是在实际的开发过程中，我们的id除了唯一性以外，还需要去满足有序递增，高性能，高可用，以及需要时间戳等这样一些特征，而雪花算法就是一个比较符合这个一类特征的全局唯一算法。

雪花算法结构的详解：

它是一个通过64个bit位组成的一个long类型的数字，可以将它分为四个部分，根据这四个部分的规则，生成对应的bit位的一个数据，然后组装在一起，形成一个全局的唯一id。

第一部分：是一个bit：这个是正负号，正常情况下为零，通常无意义

1）不用 1bit：是不用的

因为二进制里第一个bit位如果是1，那么都是复数，但是我们生成的id都是正数，所以第一个bit统一都是0

第二部分：是41个bit：表示的是时间戳

2）时间戳 41bit：表示的是时间戳，单位是毫秒

41bit表示的数字多达2^41-1，也就是可以标识2^41-1个毫秒值，换算成年表示就是69年的时间。

第三、四部分：是5+5个bit：表示的是机房id以及机器id、

3）+4）工作机器Id 10bit：记录工作机器的id，表示的是这个服务最多可以部署在2^10台机器上，也就是1024台机器。

但是10bit里5个bit代表机房id，5个bit代表机器id。意思就是最多代表2^个机房（32个机房），每个机房可以代表2^5和机器（32台机器），也可以根据实际情况确定

第五部分：是12个bit：表示的序号，就是某个机房中某个机器上这一毫秒内同时生成的id的序号，0000 0000 0000

12bit可以代表的最大正整数是2^12-1=4096，也就是说可以用这个12bit代表的数字来区分同一个毫秒内的4096个不同的id。

源码：

public class SnowFlakeUtil01 {// 起始时间戳 (可以自定义)private final long twepoch = 1288834974657L;// 机器ID所占的位数private final long workerIdBits = 5L;// 数据中心ID所占的位数private final long datacenterIdBits = 5L;// 支持的最大机器ID，结果是31 (这个移位算法可以计算最大值：-1L ^ (-1L << workerIdBits))private final long maxWorkerId = -1L ^ (-1L << workerIdBits);// 支持的最大数据中心ID，结果是31private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);// 序列在ID中占的位数private final long sequenceBits = 12L;// 机器ID左移位数private final long workerIdShift = sequenceBits;// 数据中心ID左移位数private final long datacenterIdShift = sequenceBits + workerIdBits;// 时间戳左移位数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;// 构造函数public SnowFlakeUtil01(long workerId, long datacenterId) {// 检查workerId是否在合法范围内if (workerId > maxWorkerId || workerId < 0) {throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));}// 检查datacenterId是否在合法范围内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;}/*** 获得下一个ID (该方法是线程安全的)* @return SnowflakeId*/public synchronized long nextId() {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) {// 如果毫秒相同，则从0递增生成序列号sequence = (sequence + 1) & sequenceMask;// 毫秒内序列溢出if (sequence == 0) {// 阻塞到下一个毫秒,获得新的时间戳timestamp = tilNextMillis(lastTimestamp);}}// 时间戳改变，毫秒内序列重置else {sequence = 0L;}// 上次生成ID的时间戳lastTimestamp = timestamp;// 移位并通过或运算拼到一起组成64位的IDreturn ((timestamp - twepoch) << timestampLeftShift) // 时间戳部分| (datacenterId << datacenterIdShift)       // 数据中心部分| (workerId << workerIdShift)               // 机器ID部分| sequence;                                 // 序列号部分}// 阻塞到下一个毫秒，直到获得新的时间戳protected long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}// 返回当前时间，以毫秒为单位protected long timeGen() {return System.currentTimeMillis();}//    public static void main(String[] args) {
//        SnowFlakeUtil snowFlakeUtil = new SnowFlakeUtil(0, 0);
//        for (int i = 0; i < 100; i++) {
//            long id = snowFlakeUtil.nextId();
//            System.out.println(id);
//        }
//    }
}