分布式ID

分布式ID，也称为全局唯一ID，是在分布式系统中用于标识数据的唯一标识符。随着业务量的不断扩展，传统的UUID和数据库自增ID无法满足需求，需要进行分库分表，而分表后，每个表中的数据都会按自己的节奏进行自增，很有可能出现ID冲突。此时就需要一个单独的机制来负责生成唯一ID，生成出来的ID也可以叫做分布式ID，或全局ID。这个ID应满足全局唯一性、高性能和趋势递增等要求。

一、雪花算法起源

Snowflake中文的意思是“雪花”（因为在大自然中，不可能存在两片一模一样的雪花），所以被翻译成雪花算法。它最早是twitter内部使用的分布式环境下的唯一ID生成算法，在2014年开源。

二、雪花算法的原理

Snowflake产生的ID由 64 bit 的二进制数字组成，被分成了4个部分，每一部分存储的数据都有特定的含义：

> 第 0 位： 符号位（标识正负），始终为 0； 
> 第 1~41 位 ：一共 41 位，用来表示时间戳，单位是毫秒，可以支撑2 ^41 毫秒（约 69 年）2^41/1000*60*60*24*365 = 69年 
> 第 42~52 位 ：一共 10 位，工作机器id，一般用前 5 位表示机房ID，后 5 位表示机器ID，用于区分不同集群/机房的节点，10位的长度，可以表示1024个不同节点。 
> 第 53~64 位 ：一共12 位，用来表示序列号。 序列号为自增值，代表单台机器每毫秒能够产生的最大ID 数(2^12 =4096)，也就是说单台机器每毫秒最多可以生成 4096 个 唯一 ID，最大可以支持400w左右的并发量。

具体结构如下：

三、java实现雪花算法

package snow;/*** @author 杨树林* @version 1.0* @since 24/10/2023*/public class SnowFlake {// 机房(数据中心)IDprivate long datacenterId;// 机器IDprivate long workerId;// 同一时间的序列号private long sequence;// 开始时间戳private long twepoch = 1634393012000L;// 机房ID所占的位数： 5个bitprivate long datacenterIdBits = 5L;// 机器ID所占的位数：5个bitprivate long workerIdBits = 5L;// 最大机器ID：5bit最多只能有31个数字，就是说机器id最多只能是32以内// 最大:11111(2进制) --> 31(10进制)private long maxWorkerId = -1L ^ (-1L << workerIdBits);// 最大机房ID：5bit最多只能有31个数字，机房id最多只能是32以内// 最大:11111(2进制)--> 31(10进制)private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);// 同一时间的序列所占的位数:12个bit// 最大111111111111 = 4095  代表同一毫秒最多生成4096个private long sequenceBits = 12L;// workerId的偏移量12private long workerIdShift = sequenceBits;// datacenterId的偏移量12+5private long datacenterIdShift = sequenceBits + workerIdBits;// timestampLeft的偏移量12+5+5private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;// 序列号掩码 4095 (0b111111111111=0xfff=4095)// 用于序号的与运算，保证序号最大值在0-4095之间private long sequenceMask = -1L ^ (-1L << sequenceBits);// 最近一次时间戳private long lastTimestamp = -1L;// 按照机器ID和机房ID创建雪花算法对象public SnowFlake(long workerId, long datacenterId) {this(workerId, datacenterId, 0);}public SnowFlake(long workerId, long datacenterId, long sequence) {// 合法判断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));}System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);this.workerId = workerId;this.datacenterId = datacenterId;this.sequence = sequence;}// 获取下一个随机的IDpublic synchronized long nextId() {// 获取当前时间戳，单位毫秒long timestamp = timeGen();if (timestamp < lastTimestamp) {System.err.printf("clock is moving backwards.  Rejecting requests until %d.", 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;// sequence序列大于4095，导致溢出if (sequence == 0) {// 调用到下一个时间戳的方法timestamp = tilNextMillis(lastTimestamp);}} else {// 如果是当前时间的第一次获取，那么就置为0sequence = 0;}// 记录上一次的时间戳lastTimestamp = timestamp;// 偏移计算return ((timestamp - twepoch) << timestampLeftShift) |(datacenterId << datacenterIdShift) |(workerId << workerIdShift) |sequence;}// 计算时间戳private long tilNextMillis(long lastTimestamp) {// 获取最新时间戳long timestamp = timeGen();// 如果发现最新的时间戳小于或者等于序列号已经超4095的那个时间戳while (timestamp <= lastTimestamp) {// 不符合则继续timestamp = timeGen();}return timestamp;}// 获取当前时间戳private long timeGen() {return System.currentTimeMillis();}}

测试：

class test{public static void main(String[] args) {SnowFlake worker = new SnowFlake(1, 1);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}System.out.println();worker = new SnowFlake(1, 2);for (int i = 0; i < 100; i++) {System.out.println(worker.nextId());}}
}

四、常见问题

1.时钟回拨？
计算机在获取时间戳时，一般时不会获取到前一刻的时间的，如果获取到的时间戳属于之前的一个时间点，这种现象叫做时间回拨。一般是由于人为原因对系统时间修改，或者不同服务器之间的时间有一些偏差导致的
2.第一位为什么不使用?
在计算机的表示中，第一位是符号位，0表示整数，第一位如果是1则表示负数，我们用的ID默认就是正数，所以默认就是0，那么这一位默认就没有意义。
3.twepoch表示什么？
由于时间戳只能用69年，计算机默认计时是从1970年开始的，所以使用twepoch表示从项目开始的时间，用生成ID的时间减去twepoch作为时间戳，可以使用更久。

总结

Snowflake雪花算法的使用场景一般在于分布式架构下解决分布式ID唯一性、安全性、具有实际意义性的一个算法，在很多大型分布式架构中都是非常重要的解决ID唯一性算法。

• 第1位为符号位，固定为0；
• 接下来的41位为时间戳（毫秒级），记录了生成ID的时间；
• 然后是10位的机器ID，5位数据中心ID和5位工作机器ID，用于标识不同的机器；
• 最后是12位的序列号，用于表示在同一毫秒内生成的多个ID的顺序。