雪花算法
雪花算法
文章转载自：雪花算法（snowflake）生成Id重复问题——唐江旭
前言
最近工作上遇到一个雪花算法生成Id重复导致数据库中表主键冲突，导致入库失败的问题，所以顺便学习了一下雪花算法，下面是学习的笔记以及讨论如果解决雪花算法在分布式部署中生成重复Id的问题。
基础概念
snowflake中文的意思是雪花，所以常被称为雪花算法
它是twitter用scala语言编写的一个用于简单规则运算就能高效生成唯一ID的算法，下面是源码地址：
网上还有各种其他语言的版本，思路基本上都是参考上述源码
特性
生成的ID不重复
生成性能高
基于时间戳，可以基本保证有序递增
设计原理
准备工作
bit与byte
bit(位)：电脑中存储的最小单位，可以存储二进制中的0或1
byte(字节)：一个byte由8个bit组成
如图：
而在java中，每个数据类型存储所占的字节数不一样，常用的如下：
int：4 个字节。
short：2 个字节。
long：8 个字节。
byte：1 个字节。
float：4 个字节。
double：8 个字节。
char：2 个字节。
而雪花算法生成的数字，我们定义为long，所以就是8个byte，64bit
假设我们定义 long a = 1L；则在计算机中的存储如下：
也就是可表示的范围为：-9223372036854775808（-2的63次方） ~ 9223372036854775807（2的63次方-1），考虑到生成的唯一值用于数据库主键，所以理论值为0~9223372036854775807（2的63次方-1），容量上肯定能满足业务方了
组成原理
雪花算法生成的Id由：1bit 不用 + 41bit时间戳+10bit工作机器id+12bit序列号，如下图：
不用： 1bit，因为最高位是符号位，0表示正，1表示负，所以这里固定为0
时间戳： 41bit，服务上线的时间毫秒级的时间戳（为当前时间-服务第一次上线时间），这里为 （2^41-1）/1000/60/60/24/365 = 49.7 年
工作机器id： 10bit，表示工作机器id，用于处理分布式部署id不重复问题，可支持 2^10 = 1024 个节点
序列号： 12bit，用于离散同一机器同一毫秒级别生成多条Id时，可允许同一毫秒生成 2^12 = 4096 个Id，则一秒就可生成 4096*1000 = 400w 个Id
说明：上面总体是64位，具体位数可自行配置，如想运行更久，需要增加时间戳位数；如想支持更多节点，可增加工作机器id位数；如想支持更高并发，增加序列号位数
Java版本的具体实现
public class SnowflakeIdWorker {
/** 开始时间截 (建议用服务第一次上线的时间，到毫秒级的时间戳) */
private final long twepoch = 687888001020L;
/** 机器id所占的位数 */
private final long workerIdBits = 10L;
/** 支持的最大机器id，结果是1023 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数) */
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)
* <<为左移，每左移动1位，则扩大1倍
* */
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~1023)
*/
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) {
//如果毫秒相同，则从0递增生成序列号
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;
}
/**
* 返回以毫秒为单位的当前时间，从1970-01-01 08:00:00算起
* @return 当前时间(毫秒)
*/
protected long timeGen() {
return System.currentTimeMillis();
}
}位运算可以看：计算机数据的表示
雪花算法生成Id重复问题
我们之前提到，同一机器同一毫秒级，我们能生成4096个不同序列，即不同Id，但是如果我们使用的是微服务架构，那不同机器人是否会可能生成相同Id呢？
其实我们之前有提到工作机器Id的作用，就是用于解决分布式Id重复的问题，这个workerId是通过构造方法传入的，如果我们用10位来存储这个值，那就是最多支持1024个节点
那么关键问题就回归到如何去把我们的服务器和workerId对应起来？如果不是容器化部署，部署是固定的机器，我们用机器的唯一名来做key，那我们可以对这些机器名和workerId建立一个对应关系，如果存在就用之前的workerId，不存在就往上累加比如我们用计算机名做key，这样机器如果不断累加，最多支持1024台服务器。
但是如果是容器化部署，需要支持动态增加节点，并且每次部署的机器不一定一样时，就会有问题，如果发现不同，就往上累加，经过多次发版，就可能会超过1023，这个时候生成雪花Id时，工作机器id左移12位后，当进行或运算时，时间戳的位置就会被影响，比如workerId=1024，我们拿之前的举例第1000ms，那它和第1001ms、workerId=0配置，可能生成重复的Id
优化方案：
- 在redis中存储一个当前workerId的最大值
- 每次生成workerId时，从redis中获取到当前workerId最大值，并+1作为当前workerId，并存入redis
- 如果workerId为1023，自增为1024，则重置0，作为当前workerId，并存入redis
上述逻辑，其实可以参考序列号的位运算，简化为：
workerId= (workerId+ 1) & (-1L ^ (-1L << workerIdBits))
其中：workerIdBits为机器人Id所占的位数
如果workerIdBits = 10，则为0增长到1023后，继续从0开始自增
上述方案是否一定没问题呢？其实是有的，如果自增1新分配的workerId还没释放掉，这个时候就会冲突了 比如我们第一个pod(workerId=0)一直没有重启过，但是第二个pod一直在重启，达到1024时回到0，则同时会有两个pod的workerId为0, 这两台pod上程序生成的Id就有可能重复。 我们算极端情况下，workerIdBits=10，即1024个节点的情况下，可以支持到两次发版中间第一个pod一直不重启，其余5个pod一直重启的极端情况下，也能支持204次。但是只要发一次版本，所有pod都会到最近redis中记录的最大workerId，像我们一周一个版本的情况，不会存在这个问题。
美团解决方案： Leaf：美团分布式ID生成服务开源
几个注意的点
- twepoch为开始的时间戳，建议为服务第一次上线的时间，虽然我们41bit的时间戳支持49.7年，但是其实是说的距离twepoch的时间，如果两者差值超过了49.7年，左右左移22位，就会导致部分有效数据丢失，生成的Id数据不能保证大致是递增的
- 雪花算法生成的id的组成位数，可以根据自己的实际需求可调整，如果需要支持更长，增加时间戳所占位数；如果想支持更多服务器或者更多次重启，增加工作机器人id所占位数；如果想支持同一时间更多并发，增加序列号所占位数
- 生成雪花算法的类，需要使用单例模式，并且需要保证线程安全