雪花算法详解

我们知道java中一个long类型，长度为8个字节，一个字节有8位，所以一个long类型为64位。字节（byte）、位（bit）

在这张图中我们我们把64个bit分为5个区间。

1. 第一个bit在二进制码中是符号位，我们不做使用
2. 时间戳占用41个bit，41个bit可以代表 2⁴¹-1 个毫秒的值，换算成年(2⁴¹-1) / (1000 * 60 * 60 * 24 *365) = 69年
3. 数据中心id占用5个bit，2⁵=32 可以使用0~31这个范围的值。（分库分表情况下可以使用机房号或者机架号计算一个值）
4. 工作机器id占用5个bit，2⁵=32 可以使用0~31这个范围的值。（分库分表情况下可以使用机器号计算一个值）
5. 序列占用12个bit，2¹²=4096 可以使用0~4095这个范围的值。

一、计算时间戳的值

/*** 开始时间截 (2022-01-01)*/
private final long twepoch = 1640966460000L;/*** 返回以毫秒为单位的当前时间** @return 当前时间(毫秒)*/
private long timeGen() {return System.currentTimeMillis();
}
long timestamp = timeGen();timestamp - twepoch 就是将来需要填充到时间戳位置的数值

二、计算数据中心的id值

 /*** <p>* 数据标识id部分 使用网络接口来计算一个值* </p>*/protected static long getDatacenterId(long maxDatacenterId) {long id = 0L;try {//获取网络接口InetAddress ip = InetAddress.getLocalHost();NetworkInterface network = NetworkInterface.getByInetAddress(ip);if (network == null) {id = 1L;} else {byte[] mac = network.getHardwareAddress();if (null != mac) {id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;id = id % (maxDatacenterId + 1);}}} catch (Exception e) {}return id;}

三、计算工作机器id

    /*** <p>* 获取 maxWorkerId  使用数据标识id 和jvm进程的pid来获取一个值* </p>*/protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {StringBuilder mpid = new StringBuilder();mpid.append(datacenterId);//获取当前JVM进程的PIDString name = ManagementFactory.getRuntimeMXBean().getName();if (StringUtils.isNotEmpty(name)) {/** GET jvmPid*/mpid.append(name.split("@")[0]);}/** MAC + PID 的 hashcode 获取16个低位*/return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);}

四、序列值

序列值规则，在同一个时间戳内从0开始递增，下个一值在上一个值得基础上+1。如果当前时间戳大于之前的时间戳，那么序列值置为0。

//如果是同一时间生成的，则进行毫秒内序列if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;//毫秒内序列溢出if (sequence == 0) {//阻塞到下一个毫秒,获得新的时间戳timestamp = tilNextMillis(lastTimestamp);}}//时间戳改变，毫秒内序列重置else {// 不同毫秒内，序列号置为 1 - 3 随机数sequence = 0;}

五、系统时间不正常问题

系统时间被回退或者出现闰秒，我们的策略是等待五秒的范围，如果超出五秒则抛出异常。

 //如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if (timestamp < lastTimestamp) {//闰秒long offset = lastTimestamp - timestamp;if (offset <= 5) {try {wait(offset << 1);timestamp = timeGen();if (timestamp < lastTimestamp) {throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));}} catch (Exception e) {throw new RuntimeException(e);}} else {throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));}}

六、整体代码

public class SnowFlake {/*** 开始时间截 (2022-01-01)*/private final long twepoch = 1640966460000L;/*** 机器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;private static SnowFlake instance;private SnowFlake (){}public static synchronized SnowFlake getSnowFlake() {if (instance == null) {long datacenterId = Host.getDatacenterId(31);instance = new SnowFlake(Host.getMaxWorkerId(datacenterId,31), datacenterId);}return instance;}/*** 构造函数** @param workerId     工作ID (0~31)* @param datacenterId 数据中心ID (0~31)*/private SnowFlake(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;}/*** 获得下一个ID (该方法是线程安全的)** @return SnowflakeId*/public synchronized long nextId() {long timestamp = timeGen();//如果当前时间小于上一次ID生成的时间戳，说明系统时钟回退过这个时候应当抛出异常if (timestamp < lastTimestamp) {//闰秒long offset = lastTimestamp - timestamp;if (offset <= 5) {try {wait(offset << 1);timestamp = timeGen();if (timestamp < lastTimestamp) {throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));}} catch (Exception e) {throw new RuntimeException(e);}} else {throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", offset));}}//如果是同一时间生成的，则进行毫秒内序列if (lastTimestamp == timestamp) {sequence = (sequence + 1) & sequenceMask;//毫秒内序列溢出if (sequence == 0) {//阻塞到下一个毫秒,获得新的时间戳timestamp = tilNextMillis(lastTimestamp);}}//时间戳改变，毫秒内序列重置else {// 不同毫秒内，序列号置为 1 - 3 随机数sequence = 0;}//上次生成ID的时间截lastTimestamp = timestamp;//移位并通过或运算拼到一起组成64位的IDreturn ((timestamp - twepoch) << timestampLeftShift) //| (datacenterId << datacenterIdShift) //| (workerId << workerIdShift) //| sequence;}/*** 阻塞到下一个毫秒，直到获得新的时间戳** @param lastTimestamp 上次生成ID的时间截* @return 当前时间戳*/private long tilNextMillis(long lastTimestamp) {long timestamp = timeGen();while (timestamp <= lastTimestamp) {timestamp = timeGen();}return timestamp;}/*** 返回以毫秒为单位的当前时间** @return 当前时间(毫秒)*/private long timeGen() {return System.currentTimeMillis();}
}

public class Host {//获取数据中心id，我们使用hostName来计算数据中心idpublic static int getDataId(int max){try {return getHostId(Inet4Address.getLocalHost().getHostName(),max);} catch (UnknownHostException e) {return (int)(Math.random()*max);}}//获取工作机器id，我们使用hostAddress来计算机器idpublic static int getWorkId(int max){try {return getHostId(Inet4Address.getLocalHost().getHostAddress(),max);} catch (UnknownHostException e) {return (int)(Math.random()*max);}}//将字符串遍历每一个字节值相加和最大值取模 得到0~max的值private static int getHostId(String target,int max){byte[] bytes = target.getBytes();int sums = 0;for (int b:bytes) {sums+=b;}return sums%(max+1);}/*** <p>* 获取 maxWorkerId  使用数据标识id 和jvm进程的pid来获取一个值* </p>*/protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) {StringBuilder mpid = new StringBuilder();mpid.append(datacenterId);//获取当前JVM进程的PIDString name = ManagementFactory.getRuntimeMXBean().getName();if (StringUtils.isNotEmpty(name)) {/** GET jvmPid*/mpid.append(name.split("@")[0]);}/** MAC + PID 的 hashcode 获取16个低位*/return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);}/*** <p>* 数据标识id部分 使用网络接口来计算一个值* </p>*/protected static long getDatacenterId(long maxDatacenterId) {long id = 0L;try {//获取网络接口InetAddress ip = InetAddress.getLocalHost();NetworkInterface network = NetworkInterface.getByInetAddress(ip);if (network == null) {id = 1L;} else {byte[] mac = network.getHardwareAddress();if (null != mac) {id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6;id = id % (maxDatacenterId + 1);}}} catch (Exception e) {}return id;}}

public class SnowFlakeUtil {//通过雪花算法获取唯一值idpublic static long getIdBySnowFlake(){return SnowFlake.getSnowFlake().nextId();}
}