目录
一、概念
二、64bit结构图解
三、64bit结构解释
四、snokeFlake算法获取自增式Id
五、源码(Java版本)
一、概念
(1)开源ID:Twitter开源开源的分布式ID生成算法
(2)64 bit自增:使用一个64位的long型数字作为一个全局ID,且引入了时间戳概念,基本上保证自增的
(3)64位中,第一位是不用的,其中的41位作为毫秒数,10位(5+5)作为机房机器id,剩下的12位作为序列号
二、64bit结构图解
三、64bit结构解释
第一个部分，是 1 个 bit: 如果是 1，那么都是负数，但是我们生成的 id 都是正数，所以第一个 bit 统一都是 0。
第二个部分是 41 个 bit: 表示的是时间戳。41 bit 可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表示 69 年的时间。
第三个部分是 5 个 bit: 表示的是机房 id，10001。
第四个部分是 5 个 bit: 表示的是机器 id，11001。部署在 2^10 台机器上，也就是 1024 台机器。
第五个部分是 12 个 bit: 表示的序号，就是某个机房某台机器上这一毫秒内同时生成的 id 的序号，0000 0000 0000。记录同一个毫秒内产生的不同 id
四、snokeFlake算法获取自增式Id
(1)请求:某个微服务service需要生成一个全局唯一Id,那就可以给部署了snokeFlake算法的系统发送一个请求来生成唯一Id
(2)二进制生成:接着会用"二进制位运算"来生成一个64位的long型id,并且64位第一个bit无意义,算法系统当然知道当前的时间戳,自己的机房和机器
(3)毫秒内累加序号:最后在判断下这是这个毫秒下的第几个请求,给这次生成的Id的请求累加一个序号,作为最后的12个bit
(4)算法保证唯一:在同一毫秒下,同一个机房下的一台机器,生成一个唯一的id(12位=4096个), 如果一毫秒生成的Id数量超过了4095,就知会等待下一个毫秒在生成!但是估计没有请求能有这么频繁!
五、源码(Java版本)
import java.sql.Timestamp;
/**
* @author fong
* @date 2021/11/6 - 7:50:56
*/
public class SnokeFlake {
/*
机房 机器 序列号占的位数
*/
private final static long DATACENTER_BIT = 5;
private final static long MACHINE_BIT = 5;
private final static long SEQUENCE_BIT = 12;
// 起始时间戳, 固定值, 不能为new Date(),否则生成Id会重复
private final static long START_TIMESTAMP = 154231231412L;
// 机器标志相对序列号的偏移量 12位
private final static long MACHINE_LEFT = SEQUENCE_BIT;
// 机房标志相对机器的偏移量 17 = 12 + 5位
private final static long DATACENTER_LEFT = MACHINE_LEFT + MACHINE_BIT;
// 时间戳标志相对机器的偏移量 22 = 17 + 5位
private final static long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
// 用位运算计算出最大支持的数据中心数量 31
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
// 用位运算计算出最大支持的机器数量 31
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
// 用位运算计算出12位能存储的最大整数
/*
-1L异或运算复习
0 ^ 0 和 1 ^ 1 = 0
0 ^ 1 和 1 ^ 0 = 1
-1L = 1111 1111 (0000 0001的取反+1)
-1L << 12 = 1111 1111 0000 0000 0000
1111 1111 0000 0000 0000
^
1111 1111 1111 1111 1111
===============================
0000 0000 1111 1111 1111 换算成十进制为: 4095
*/
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/*
机房 机器 序列号 上一次请求保存的时间戳
*/
private static long datacenterId;
private static long machineId;
private static long sequence = 0L;// 自增序列号(相当于计数器)
private static long lastStamp = -1L;
/**
* 此处无参构造private,是为了避免以下两点问题
* (1)私有化避免了通过new方式进行调用, 解决了在for循环中通过new方式产生的id不一定唯一的问题
* 因为用于记录上一次时间戳lastStamp永远无法得到对比
* (2)没有给出有参构造在第一点的基础上考虑了分布式系统产生的唯一序列号应该总是"基于相同的参数"
*/
public SnokeFlake() {
}
/**
* 产出下一个Id
* @return
*/
public static synchronized long nextId() {
// 获取当前的时间戳
long curStamp = getCurrentStamp();
// 若当前时间戳 < 上次时间戳则抛出异常
if (curStamp < lastStamp) {
throw new RuntimeException("Clock moved backwords. Refusing to generate id");
}
// 1.同一毫秒内
if (curStamp == lastStamp) {
/*
复习&运算: 除了1 & 1 = 1, 其余情况都是0
例如sequence = 4095 MAX_SEQUENCE = 4095
4095: 0000 1111 1111 1111
^
4095 + 1: 0001 0000 0000 0000
===============================
0(重置0) 0000 0000 0000 0000
*/
// 1.1 相同毫秒内 id自增
sequence = (sequence + 1) & MAX_SEQUENCE;
// 1.2 同一毫秒内 序列数已经达到最大4095,等待下一个毫秒到来在生成
if (sequence == 0L) {
// 获取下一秒的时间戳并赋值给当前时间戳
curStamp = getNextMill();
}
// 2.不同毫秒,序列号重置为0
} else {
sequence = 0L;
}
// 3.当前时间戳存档, 用于下次生成id对比是否为同一毫秒内
lastStamp = curStamp;
// 4.或运算拼接返回id
return (curStamp - START_TIMESTAMP) << TIMESTAMP_LEFT // 时间戳部分
| datacenterId << DATACENTER_LEFT // 机房部分
| machineId << MACHINE_LEFT // 机器部分
| sequence; // 序列号部分
}
private static long getNextMill() {
long mill = getCurrentStamp();
// 循环获取当前时间戳, 直到拿到下一秒的时间戳
while (mill <= lastStamp) {
mill = getCurrentStamp();
}
return mill;
}
private static long getCurrentStamp() {
return System.currentTimeMillis();
}
}
