分析与改造SnowFlake算法
背景
公司原本订单ID的生成是基于Java Random与Hash算法的单机UID生成策略，但是后端系统的生成环境是基于SLB，Nginx与Java多进程的分布式环境，导致出现了UID 碰撞,产生线上问题。现准备基于Twitter的SnowFlake，将UID生成独立出来做一个统一的全局ID生成服务。
SnowFlake概述
SnowFlake算法用来生成64位的ID，刚好可以用long整型存储，能够用于分布式系统中生产唯一的ID， 并且生成的ID有大致的顺序。 生成的64位ID可以分成5个部分：
0 - 41位时间戳 - 5位数据中心标识 - 5位机器标识 - 12位序列号
5位数据中心标识跟5位机器标识这样的分配仅仅是当前实现中分配的，可以按其它的分配比例分配，如10位机器标识，不需要数据中心标识…
- 1位标识部分，在java中由于long的最高位是符号位，正数是0，负数是1，一般生成的ID为正数，所以为0
- 41位时间戳部分，这个是毫秒级的时间，一般实现上不会存储当前的时间戳，而是时间戳的差值（当前时间-固定的开始时间），这样可以使产生的ID从更小值开始；41位的时间戳可以使用69年，41位可以表示241−1个毫秒的值，转化成单位年则是(241−1)/(1000∗60∗60∗24∗365)=69年
- 10位节点部分，Twitter实现中使用前5位作为数据中心标识，后5位作为机器标识，可以部署1024个节点(5位可支持2^5 = 0~31整型,
32*32=1024节点)； - 12位序列号部分，支持同一毫秒内同一个节点可以生成4096个ID(2^12=4096)；
简单实现
结构
0 - 41位时间戳 - 10位机器标识 - 12位序列号
集群环境下机器标识获取
-
IP后三位
启动系统的时候获取IP地址(或者截取IP后三位)作为机器标识(0~255)。缺陷：会浪费256~1024位的机器标识
-
Redis Set
①在服务启动时通过Redis setnx <key:机器标识 value:ip地址>,for 1024对机器标识进行获取，如果Key不存在则设置当前IP地址，并使用key作为当前服务的机器标识。
②在服务运行过程中使用ScheduleThreadPool或者DeamonThread为当前服务的Redis Key续时,避免其他服务获取到相同的机器标识
其他
1. 服务鉴权|IP白名单
2. 服务限流
代码
- Java 实现
/**
* @Author : lhr
* @Date : 12:03 2018/9/14
* <p>
* 基于Twitter SnowFlake算法 UID生成类
* 0 - 41位时间戳 - 10位机器标识 - 12位序列号
* 41位时间戳：时间戳的差值（当前时间-固定的开始时间START_STMP）
* 10位机器标识:固定值,取IP地址后八位
* 12位序列号：同一毫秒内同一个节点可以生成4096个ID
* <p>
* 0 - 000000000 0000000000 0000000000 0000000000 0 - 000000000 - 0000000000 00
*/
public class SnowFlakeUidGenerate {
/**
* 起始时间戳 2018-09-10 00:00:00
*/
private final static long START_STMP = 1536508800000L;
private static ReentrantLock reentrantLock = new ReentrantLock();
/**
* 每一部分占用的位数
* SEQUENCE_BIT:序列号占用的位数
* MACHINE_BIT:机器标识占用的位数(0-1024)
*/
private final static long SEQUENCE_BIT = 12;
private final static long MACHINE_BIT = 10;
/**
* 每一部分占用的最大值
* MAX_SEQUENCE_NUM:序列号最大值
* MAX_MACHINE_NUM:机器标识最大值
*/
private final static long MAX_SEQUENCE_NUM = -1L ^ (-1L << SEQUENCE_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
/**
* 每一部分向左移动
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long TIMESTMP_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private static long machineId = 0L;
private static long sequence = 0L;
private static long lastStmp = -1L;
/**
* 产生下一个Id
*
* @return
*/
public static long nextId() {
reentrantLock.lock();
try {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
String msg = String.format("SnowFlakeUidGenerate: 机器时钟发生错误,无法生成UID " +
"machineId:{} ; currStmp:{} ; lastStmp:{}", machineId, currStmp, lastStmp);
throw new RuntimeException(msg);
}
if (currStmp == lastStmp) {
//相同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE_NUM;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内，序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
return ((currStmp - START_STMP) << TIMESTMP_LEFT)
| machineId << MACHINE_LEFT
| sequence;
} finally {
reentrantLock.unlock();
}
}
private static long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}
private static long getNewstmp() {
return System.currentTimeMillis();
}
public static void initMachineId(long currentMachineId) {
if (currentMachineId > MAX_MACHINE_NUM || currentMachineId < 0) {
String msg = String.format("SnowFlakeUidGenerate 机器标识不正确 machineId:{}", machineId);
throw new RuntimeException(msg);
}
machineId = currentMachineId;
}
public static long getMachineId() {
return machineId;
}
}
- 核心操作
((currStmp - START_STMP) << TIMESTMP_LEFT)
使用当前时间戳减去开始时间戳得到时间戳数值,时间戳数值左移22位进行bit位对齐
0 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00]00 0000 0000 0000 0000 0000
| machineId << MACHINE_LEFT
10位的机器ID左移12位进行bit位对其,并于上述二进制数值进行|或操作,进行bit位对齐
0 000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00 [00 0000 0000] 0000 0000 0000
|
0 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00]00 0000 0000 0000 0000 0000
=
0 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00][00 0000 0000] 0000 0000 0000
| sequence
12位的序列号与上述二进制数值进行|或操作,进行bit位对齐 得到
0 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00][00 0000 0000][0000 0000 0000]
SnowFlake改造
固定长度UID改造
Snowflake生成的ID长度不是固定的，和设置的起始时间有关系。多数订单号需要一个统一长度的订单ID。可以在64位数前面使用01达到确定位数，对机器ID与序列号进行取舍。(对于机房小的小型公司可以采用缩减机器ID的方式，对于并发性不高的业务可以采用缩减序列号的方式，减小毫秒级别UID的生成数量)
/**
* @Author : lhr
* @Date : 14:06 2019/7/30
* <p>
* 基于Twitter SnowFlake算法改造 UserId生成类 生成固定长度为19的ID
* 01 - 41位时间戳 - 10位机器标识 - 11位序列号
* 41位时间戳：时间戳的差值（当前时间-固定的开始时间START_STMP）
* 10位机器标识:固定值,取IP地址后八位
* 11位序列号：同一毫秒内同一个节点可以生成2048个ID
* <p>
* 01 - 000000000 0000000000 0000000000 0000000000 0 - 000000000 - 0000000000 0
*/
public class SnowFlakeUserIdGenerate {
/**
* 起始时间戳 2018-09-10 00:00:00
*/
private final static long START_STMP = 1536508800000L;
private static ReentrantLock reentrantLock = new ReentrantLock();
/**
* 有效bit位
*/
private static final long bitNum = 62;
/**
* 每一部分占用的位数
* SEQUENCE_BIT:序列号占用的位数
* MACHINE_BIT:机器标识占用的位数(0-1024)
*/
private final static long SEQUENCE_BIT = 11;
private final static long MACHINE_BIT = 10;
/**
* 每一部分占用的最大值
* MAX_SEQUENCE_NUM:序列号最大值
* MAX_MACHINE_NUM:机器标识最大值
*/
private final static long MAX_SEQUENCE_NUM = -1L ^ (-1L << SEQUENCE_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
/**
* 每一部分向左移动
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long TIMESTMP_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private static long machineId = 0L;
private static long sequence = 0L;
private static long lastStmp = -1L;
/**
* 产生下一个Id
*
* @return
*/
public static long nextId() {
reentrantLock.lock();
try {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
String msg = String.format("SnowFlakeUserIdGenerate: 机器时钟发生错误,无法生成UID " +
"machineId:{} ; currStmp:{} ; lastStmp:{}", machineId, currStmp, lastStmp);
throw new RuntimeException(msg);
}
if (currStmp == lastStmp) {
//相同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE_NUM;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内，序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
return ((currStmp - START_STMP) << TIMESTMP_LEFT)
| machineId << MACHINE_LEFT
| sequence
| 1L << bitNum;
} finally {
reentrantLock.unlock();
}
}
private static long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}
private static long getNewstmp() {
return System.currentTimeMillis();
}
public static void initMachineId(long currentMachineId) {
if (currentMachineId > MAX_MACHINE_NUM || currentMachineId < 0) {
String msg = String.format("SnowFlakeUserIdGenerate 机器标识不正确 machineId:{}", machineId);
throw new RuntimeException(msg);
}
machineId = currentMachineId;
}
public static long getMachineId() {
return machineId;
}
}
- 核心操作
| 1L << bitNum;
1左移62个有效bit位，并与原来生成的uid进行|或操作,使得生成的UID bit位1和2为01，达到确定生成十进制数为19位的目的
00 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00][00 0000 0000][0000 0000 000]
|
01 000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00 00 0000 0000 0000 0000 000
=
01 [000 0000 0000 0000 0000 0000 0000 0000 0000 0000 00][00 0000 0000][0000 0000 000]