现在我们来分析一下 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake,完整代码如下:
/**
* twitter的snowflake算法 -- java实现
*
* @author beyond
* @date 2016/11/26
*/
public class SnowFlake {
/**
* 起始的时间戳
*/
private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATACENTER_BIT = 5;//数据中心占用的位数
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
/**
* 每一部分向左的位移
*/
private final static long MACHINE_LEFT = SEQUENCE_BIT;
private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
private long datacenterId; //数据中心
private long machineId; //机器标识
private long sequence = 0L; //序列号
private long lastStmp = -1L;//上一次时间戳
public SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException(
"datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException(
"machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}
/**
* 产生下一个ID
*
* @return
*/
public synchronized long nextId() {
long currStmp = getNewstmp();
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
if (currStmp == lastStmp) {
//相同毫秒内,序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列数已经达到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内,序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
| datacenterId << DATACENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //序列号部分
}
private long getNextMill() {
long mill = getNewstmp();
while (mill <= lastStmp) {
mill = getNewstmp();
}
return mill;
}
private long getNewstmp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(2, 3);
for (int i = 0; i < (1 << 12); i++) {
System.out.println(snowFlake.nextId());
}
}
}
在详细分析之前,我们先来回顾一下 Snowflake 算法的 ID 构成图:
首位不用,默认为 0。41bit(第2-42位)时间戳,是相对时间戳,通过当前时间戳减去一个固定的历史时间戳生成。在 SnowFlake 类定义了一个 long 类型的静态变量 START_STMP,它的值为 1480166465631L:
/**
* 起始的时间戳:Sat Nov 26 2016 21:21:05 GMT+0800 (中国标准时间)
*/
private final static long START_STMP = 1480166465631L;
接着继续定义三个 long 类型的静态变量,来表示序列号和工作机器 ID 的占用位数:
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位数
private final static long MACHINE_BIT = 5; //机器标识占用的位数
private final static long DATACENTER_BIT = 5;//数据中心占用的位数
此外还定义了每一部分的最大值,具体如下:
/**
* 每一部分的最大值
*/
private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT); // 31
private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT); // 31
private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT); // 4095
SnowFlake 类的构造函数,该构造函数含有 datacenterId 和 machineId 两个参数,它们分别表示数据中心 id 和机器标识:
private long datacenterId; //数据中心
private long machineId; //机器标识
public SnowFlake(long datacenterId, long machineId) {
if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
throw new IllegalArgumentException(
"datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
}
if (machineId > MAX_MACHINE_NUM || machineId < 0) {
throw new IllegalArgumentException(
"machineId can't be greater than MAX_MACHINE_NUM or less than 0");
}
this.datacenterId = datacenterId;
this.machineId = machineId;
}
在 SnowFlake 类的实现中,在创建完 SnowFlake 对象之后,可以通过调用 nextId 方法来获取 ID。有的小伙伴可能对位运算不太清楚,这里先简单介绍一下 nextId 方法中,所用到的位运算知识。
按位与运算符(&)
参加运算的两个数据,按二进制位进行 “与” 运算,它的运算规则:
0&0=0; 0&1=0; 1&0=0; 1&1=1;
即两位同时为 1,结果才为 1,否则为 0。
按位或运算(|) 参加运算的两个对象,按二进制位进行 “或” 运算,它的运算规则:
0|0=0; 0|1=1; 1|0=1; 1|1=1;
即仅当两位都为 0 时,结果才为 0。
左移运算符 <<
将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补 0)。若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以 2。
在了解完位运算的相关知识后,我们再来看一下 nextId 方法的具体实现:
/**
* 产生下一个ID
*
* @return
*/
public synchronized long nextId() {
// 获取当前的毫秒数:System.currentTimeMillis(),该方法产生一个当前的毫秒,这个毫秒
// 其实就是自1970年1月1日0时起的毫秒数。
long currStmp = getNewstmp();
// private long lastTimeStamp = -1L; 表示上一次时间戳
// 检测是否出现时钟回拨
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards. Refusing to generate id");
}
// 相同毫秒内,序列号自增
if (currStmp == lastStmp) {
// private long sequence = 0L; 序列号
// MAX_SEQUENCE = 4095 111111111111
// MAX_SEQUENCE + 1 = 4096 1000000000000
sequence = (sequence + 1) & MAX_SEQUENCE;
// 同一毫秒的序列数已经达到最大
if (sequence == 0L) {
// 阻塞到下一个毫秒,获得新的时间戳
currStmp = getNextMill();
}
} else {
//不同毫秒内,序列号置为0
sequence = 0L;
}
lastStmp = currStmp;
// MACHINE_LEFT = SEQUENCE_BIT; -> 12
// DATA_CENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT; -> 17
// TIMESTAMP_LEFT = DATA_CENTER_LEFT + DATA_CENTER_BIT; -> 22
return (currStmp - START_STMP) << TIMESTMP_LEFT //时间戳部分
| datacenterId << DATACENTER_LEFT //数据中心部分
| machineId << MACHINE_LEFT //机器标识部分
| sequence; //序列号部分
}
现在我们来看一下使用方式:
public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(2, 3);
for (int i = 0; i < (1 << 12); i++) {
System.out.println(snowFlake.nextId());
}
}
现在我们已经可以利用 SnowFlake 对象生成唯一 ID 了,那这个唯一 ID 有什么用呢?这里举一个简单的应用场景,即基于 SnowFlake 的短网址生成器,其主要思路是使用 SnowFlake 算法生成一个整数,然后对该整数进行 62 进制编码最终生成一个短地址 URL。对短网址生成器感兴趣的小伙伴,可以参考 徐刘根 大佬在码云上分享的工具类。
最后我们来简单总结一下,本文主要介绍了什么是 Snowflake(雪花)算法、Snowflake 算法 ID 构成图及其优缺点,最后详细分析了 Github 上 beyondfengyu 大佬基于 Java 实现的 SnowFlake。在实际项目中,建议大家选用基于 Snowflake 算法成熟的开源项目,如百度的 UidGenerator 或美团的 Leaf。
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。