雪花算法&改造16位或者15位

Bertha 。 2024-03-22 15:32 76阅读 0赞

#### 文章目录 ####

*  一、默认版本-64bit
 *   *  代码原理
     *  范围：
     *  优点
     *  缺点
 *  二、修改版本一：32bit
 *  三、修改版本二：生成15位的id
 *   *  优点：
     *  代码

## 一、默认版本-64bit ##

雪花算法原理图：  
![b060547d6531373e4b4b98c6b7f1ea89.png][]  
使用1位作为符号位,确定为0, 表示正  
使用41位作为毫秒数  
使用10位作为机器的ID : 高5位是数据中心ID, 低5位是机器ID  
使用12位作为毫秒内的序列号，意味着每个节点每秒可以产生4096(212)个ID；该算法通过二进制的操作进行实现,单机每秒内理论上最多可以生成1000\*(2^12)，即409.6万个ID。

/**
 * 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===========================================
 /** 开始时间截 (2015-01-01) */
 private final long twepoch = 1420041600000L;
 
 /** 机器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)
 */
 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() {
 
 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 = (sequence + 1) & sequenceMask;
 //毫秒内序列溢出
 if (sequence == 0) {
 
 //阻塞到下一个毫秒,获得新的时间戳
 timestamp = tilNextMillis(lastTimestamp);
 }
 }
 //时间戳改变，毫秒内序列重置
 else {
 
 sequence = 0L;
 }
 
 //上次生成ID的时间截
 lastTimestamp = timestamp;
 
 //移位并通过或运算拼到一起组成64位的ID
 return ((timestamp - twepoch) << timestampLeftShift) //
 | (datacenterId << datacenterIdShift) //
 | (workerId << workerIdShift) //
 | sequence;
 }
 
 /**
 * 阻塞到下一个毫秒，直到获得新的时间戳
 * @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(Long.toBinaryString(id));
 System.out.println(id);
 }
 }
 }

### 代码原理 ###

其中有对三个部分都限制了最大值（MAX\_DATA\_CENTER\_NUM、MAX\_MACHINE\_NUM、MAX\_SEQUENCE），我们通过图解的方式来看下计算过程：  
![image.png][]  
![image.png][image.png 1]

![image.png][image.png 2]

### 范围： ###

![image.png][image.png 3]  
我们通过计算器，我们可以看出来，默认版本的雪花算法，最大数值长度：19位，最大值：`9223372036854775807`。

### 优点 ###

1.  按照时间自增排序，在多个分布式系统内不会产生id碰撞（数据中心+机器id区分）
2.  高性能：理论上QPS约为409.6w/s（1000\*2^12）
3.  不依赖于任何外部第三方系统
4.  灵活性高：可以根据自身业务情况调整分配bit位  
    
    
    ### 缺点 ###
5.  强依赖时钟：生成都是以时间自增，如果时间回拨，可能导致id重复
6.  返给前端时，需要将lang类型id转换成string类型，因为前端JavaScript的number类型最大接收16位长度数值，而雪花算法获得的id最大长度为19位。

美团对此缺点做了一些改进，具体可以参考：Leaf——美团点评分布式ID生成系统

## 二、修改版本一：32bit ##

![image.png][image.png 4]  
大致与64bit相同，唯一区别是**时间戳部分这里仅占用32bit**，因为保存的时间戳为：当前时间戳-雪花算法开始的时间戳，得出来的数据仅用10bit就可以保存，位数越少，对磁盘、数据索引等数据提高越明显

## 三、修改版本二：生成15位的id ##

在有些时候，我们的系统并发并没有很大，同时也不会部署`2^5`的数据中心和`2^5`的机器id。  
因为并发量用不到那么高，我们可以将12位序列位缩短。  
比如：不区分数据中心，机器id最多2^ 3=8 台，每毫秒最大并发为2^5=256。将64位版本的雪花算法改造一下：  
![image.png][image.png 5]  
这样的设计，只有41位用来存储时间戳，3位用来存储机器id，5位毫秒内的序列号。最前面的12位永远用不到。

### 优点： ###

这样的好处是：

*  可以和64版本的雪花算法一样，使用69年之久。
 *  最大值`562949953421311`，最长15位，传给前端时不用考虑类型转换问题。
 *  每毫秒内并发最大2^5=256，即每秒并发256000，足矣。

![image.png][image.png 6]

### 代码 ###

package com.bangcle.amp.bcl.base.utils;
 
 /**
 * TODO
 *
 * @author cheng.jin.peng
 * @version V1.0.0
 * @date 2023/5/11 11:17
 */
 
 public class SnowflakeIdWorker {
 
 /**
 * 开始时间截 (本次时间戳为：Thu Nov 04 2010 09:42:54 GMT+0800 (中国标准时间)----1288834974657L---1656543015264587776--19 )
 */
 private final long startTime = 1683803335498L;
 
 /** 机器id所占的位数 */
 private final long workerIdBits = 3L;
 
 /** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
 private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
 /** 序列在id中占的位数 */
 private final long sequenceBits = 5L;
 
 /** 机器ID向左移12位 */
 private final long workerIdShift = sequenceBits;
 
 /** 时间截向左移22位(10+12) */
 private final long timestampLeftShift = sequenceBits + workerIdBits;
 
 /** 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095) */
 private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
 /** 工作机器ID(0~1024) */
 private long workerId;
 
 /** 毫秒内序列(0~4095) */
 private long sequence = 0L;
 
 /** 上次生成ID的时间截 */
 private long lastTimestamp = -1L;
 
 //==============================Constructors=====================================
 /**
 * 构造函数
 * @param workerId 工作ID (0~1024)
 */
 public SnowflakeIdWorker(long workerId) {
 
 if (workerId > maxWorkerId || workerId < 0) {
 
 throw new IllegalArgumentException(String.format("workerId can't be greater than %d or less than 0", maxWorkerId));
 }
 this.workerId = workerId;
 }
 
 // ==============================Methods==========================================
 /**
 * 获得下一个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) {
 
 sequence = (sequence + 1) & sequenceMask;
 //毫秒内序列溢出
 if (sequence == 0) {
 
 //阻塞到下一个毫秒,获得新的时间戳
 timestamp = tilNextMillis(lastTimestamp);
 }
 }
 //时间戳改变，毫秒内序列重置
 else {
 
 sequence = 0L;
 }
 
 //上次生成ID的时间截
 lastTimestamp = timestamp;
 
 //移位并通过或运算拼到一起组成64位的ID
 return ((timestamp - startTime) << timestampLeftShift)
 | (workerId << workerIdShift)
 | sequence;
 }
 
 /**
 * 阻塞到下一个毫秒，直到获得新的时间戳
 * @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();
 }
 
 /**
 * 测试
 */
 public static void main(String[] args) {
 
 System.out.println("开始："+System.currentTimeMillis());
 
 SnowflakeIdWorker idWorker = new SnowflakeIdWorker(1);
 
 for (int i = 0; i < 50; i++) {
 
 try {
 
 Thread.sleep(1000);
 } catch (InterruptedException e) {
 
 throw new RuntimeException(e);
 }
 long id = idWorker.nextId();
 System.out.println(id+"长度="+String.valueOf(id).length());
 
 }
 
 System.out.println("结束："+System.currentTimeMillis());
 }
 }

[b060547d6531373e4b4b98c6b7f1ea89.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0aa8d3aa15d94bd6b22457ea677f7ea2.png
[image.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/fa0309cd0ea44874b79e4e90719a99f8.png
[image.png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/ef3033829b4c4297be2fe85f1ad2135d.png
[image.png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/cd959cf0a4544a6a8c6b93327d719ebe.png
[image.png 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/e3a48868496342729780a7e851f50b39.png
[image.png 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/862b73ad8d814cbb858eb2854d55e93d.png
[image.png 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/c22856c30d9a4ad395e80c0a9a393860.png
[image.png 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/18/0c8efd583bdf4015b55cf4b6e45c36de.png