分布式雪花算法是分布式ID的实现，也是目前大厂的主流方式，所以掌握好雪花算法很重要，下面我来给大家详解分布式雪花算法@mikechen
雪花算法简介
雪花算法是一种用于生成全局唯一ID的分布式算法，主要解决在分布式系统中产生唯一标识符的问题，它由Twitter设计。
我们都知道，在大自然不存在两片完全一样的雪花。
如下图所示：
所以，用雪花算法来表示唯一性就很正常了，这就是为什么叫雪花算法的由来。
雪花算法特质
雪花算法，需要具备如下4大特征：
1.唯一性
雪花算法生成的ID，在分布式系统中是唯一的，这是必须满足的第一条件，不唯一就没有意义了。
比如：可以通过时间戳、数据中心ID、机器ID、序列号等等，来确保同一时间的唯一性。
2.有序性
生成的ID具有一定的有序性，这有助于在数据库索引等场景下提高性能。
3.分布式
雪花算法，适用于分布式系统，需要确保在大规模的分布式系统中，生成的ID不会发生冲突。
4.高性能
生成ID的效率很高，原因很简单，因为生成ID是在同一时间，不同的分布式服务器生成，所以，需要每秒的高性能。
如果你同时满足了上面我提到的几点，这就是一个比较好的分布式ID算法。
雪花算法原理
雪花算法，构造如下图所示：
各部分解释如下：
1.符号位
1位，标识正负。
由于是生成正整数，所以为0，所以，第一位基本不用，不用Care。
2.时间戳
41位，记录了生成ID的时间戳，使用的是毫秒级时间戳。
可以用69年来表示，从算法开始运行的时刻开始计算，也就是说这个时间戳可以使用69年不重复，大概可以使用 69 年。
注意：雪花算法中，41位时间戳的使用需要注意时钟同步、回拨等问题。
3.10位机器id
用于标识分布式环境中的，数据中心和机器，防止在不同的节点上产生相同的ID。
这里的10位机器id，会包含：5位datacenterId(数据中ID)、5位workerId(机器ID)。
5位，用于标识数据中心， 5位，用于标识机器。
4.序列号
序列号，是用来记录同毫秒内产生的不同id，用12位表示。
也就是说，表示在同一毫秒内生成的ID序号，支持每台机器每毫秒产生4096个ID。
理论上，雪花算法方案的QPS约为：409.6w/s，可以基本保证唯一性，速度也还可以。
所以，雪花算法算法是不错的分布式ID生成方法，这也是目前大厂主流的方法。
雪花算法代码实现
public class SnowflakeIdWorker {
/** 开始时间截 (这个用自己业务系统上线的时间) */
private final long twepoch = 1575365018000L;
/** 机器id所占的位数 */
private final long workerIdBits = 10L;
/** 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/** 序列在id中占的位数 */
private final long sequenceBits = 12L;
/** 机器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 - twepoch) << 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();
}
}
雪花算法总结
总之，雪花算法是一种简单而有效的分布式唯一ID生成算法，通过时间戳和节点信息的组合，确保在分布式环境中生成的ID是唯一的。
雪花算法的优点包括唯一性、有序性和简单高效，但需要注意：其对系统时钟的依赖。
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》