最近公司在搞什么领域负责人,其实就是每个人负责某几个模块,也就是owner的意思,公司的snowflake服务是我负责,借此机会研究下雪花算法
1.1 雪花算法结构
snowflake生成的结果是一个64bit大小的整数,使用long存储,它的结构如下图:
其中
[1]、1位,不用,二进制中的最高位是符号位,1表示负数,0表示正数,由于我们生成的雪花算法都是正整数,所以这里是0
[2]、41位,这里的时间戳是表示的是从起始时间算起,到生成id时间所经历的时间戳,也就是(当前时间戳-起始时间戳(固定))
这里一共是41位,范围就是(0~ 2^41-1),这么大的毫秒数转化成时间就是大约69年
[3]、10位,这里的10位代表工作机器id,一共可以部署在(2^10=1024)台机器上面,10位又可以分为前面五位是数据中心id(0~31),后面五位是机器id(0-31)
[4]、共12位,序列位,一共可用(0 ~ 2^12-1)共4096个数字
1.2 雪花算法作用
雪花算法可以保证:
- 生成的所有的id都是随着时间递增
- 分布式系统内不会产生重复的id(因为有机器位做区分)
1.3 雪花算法代码实现
package snowflake;
import java.util.HashSet;
import java.util.Set;
/**
* @author Smith 2020/12/26
*/
public class SnowFlakeService {
//起始时间戳( 2020-12-26 00:00:00 )
private static final long START_STAMP = 1608912000000L;
//序列号占用位数
private static final long SEQUENCE_BIT = 12;
//机器标识占用位数
private static final long MACHINE_BIT = 5;
//数据中心占用位数
private static final long DATACENTER_BIT = 5;
//序列号最大值
private static final long MAX_SEQUENCE = -1L ^ (-1L << 12); // 4095
/**
* 偏移量
**/
private static final long MACHINE_LEFT = SEQUENCE_BIT;
private static final long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
private static final long TIMESTAMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
private static long dataCenterId; //0, 数据中心(0-31)
private static long machineId; //0, 机器标识(0-31)
private static long sequence; //序列号 range(0 ~ 4095)
private static long lastStamp; //上一次时间戳
public static synchronized long getNextId() {
long currentStamp = System.currentTimeMillis();
if (currentStamp < lastStamp) {
throw new IllegalArgumentException("时间被回退,不能继续产生id");
}
if (currentStamp == lastStamp) {
//相同毫秒内,序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
if (sequence == 0L) {
//序列号已经到最大值
System.out.println("序列号已经到达最大值");
//使用下一个时间戳
currentStamp = getNextStamp();
}
} else {
//不同毫秒,序列号重置
sequence = 0L;
}
lastStamp = currentStamp;//当前时间戳存档,用于判断下次产生id时间戳是否相同
return (currentStamp - START_STAMP) << TIMESTAMP_LEFT
| dataCenterId << DATACENTER_LEFT
| machineId << MACHINE_LEFT
| sequence;
}
/**
* 阻塞直至获得下一个时间戳
*
* @return
*/
public static long getNextStamp() {
long newStamp = getCurrentStamp();
while (newStamp <= lastStamp) {
newStamp = getCurrentStamp();
}
return newStamp;
}
/**
* 获取当前时间戳
*
* @return
*/
public static long getCurrentStamp() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
Set<Long> set = new HashSet<Long>();
long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
Long id = SnowFlakeService.getNextId();
set.add(id);
}
System.out.println("总耗时 : " + (System.currentTimeMillis() - start));
System.out.println(set.size());
}
}
运行结果:
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
序列号已经到达最大值
总耗时 : 34
100000
因为序列号是每秒最多可以生成4096个id,所以在序列号到达最大值的时候,程序会阻塞直到下一个毫秒时间戳,然后继续生成id,从运行结果来看,在34ms内生成了100000个不同的id,还是比较可观的。
1.4 雪花算法的弊端
- snowflake不依赖数据库也不依赖内存,随时可以生成id,这也是为什么它如此受欢迎,但是因为它在设计时通过时间戳来避免对内存和数据库的依赖,所以它依赖于服务器的时间。 试想,如果服务器的时间发生了错乱或者回拨,这就直接影响了生成的id,有很大可能生成重复的id,且一定会打破递增属性,这也是他的一个致命缺点(不支持服务器时间回拨)
- 每毫秒生成id的上限受到限制,由于时间戳位是41位的毫秒级时间戳,所以从当前起始到41bit 耗尽,只能坚持70年
- 程序获取操作系统时间会耗费较多时间 那么如何解决这些问题呢(后面在研究): 百度开源了UIDGenerator 算法 美团团队根据业务场景提出了基于号段思想的 Leaf-Segment 方案和基于 Snowflake 的 Leaf-Snowflake 方案