数据结构|雪花算法(snowflake)实现分布式ID的生成
先分析一下:
文章图片
雪花算法简单描述:
一、 1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0,是符号位,始终为0,不可用。
二、41位的时间序列,精确到毫秒级,41位的长度可以使用69年。时间位还有一个很重要的作用是可以根据时间进行排序。注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截 - 开始时间截)
得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
三、10位的机器标识,10位的长度最多支持部署1024个节点。包括5位datacenterId和5位workerId
四、12位的计数序列号,序列号即一系列的自增id,可以支持同一节点同一毫秒生成多个ID序号,12位的计数序列号支持每个节点每毫秒产生4096个ID序号。
其中,10位器标识符一般是5位IDC+5位machine编号,唯一确定一台机器。
SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,
下面是代码实现:
public class SnowFlakeGenerator {// 起始的时间戳
private final static long START_STAMP = 1566886337L;
/**
* 可分配的位数
*/
private final static int REMAIN_BIT_NUM = 22;
/**
* idc编号
*/
private long idcId;
/**
* 机器编号
*/
private long machineId;
/**
* 当前序列号
*/
private long sequence = 0L;
/**
* 上次最新时间戳
*/
private long lastStamp = -1L;
//idc偏移量:一次计算出,避免重复计算
private int idcBitLeftOffset;
//机器id偏移量:一次计算出,避免重复计算
private int machineBitLeftOffset;
// 时间戳偏移量:一次计算出,避免重复计算
private int timestampBitLeftOffset;
// 最大序列值:一次计算出,避免重复计算
private int maxSequenceValue;
public static class Factory {
//每一部分占用位数的默认值
private final static int DEFAULT_MACHINE_BIT_NUM = 5;
//机器标识占用的位数
private final static int DEFAULT_IDC_BIT_NUM = 5;
//数据中心占用的位数private int machineBitNum;
private int idcBitNum;
public Factory() {
this.idcBitNum = DEFAULT_IDC_BIT_NUM;
this.machineBitNum = DEFAULT_MACHINE_BIT_NUM;
}public Factory(int machineBitNum, int idcBitNum) {
this.idcBitNum = idcBitNum;
this.machineBitNum = machineBitNum;
}public SnowFlakeGenerator create(long idcId, long machineId) {
return new SnowFlakeGenerator(this.idcBitNum, this.machineBitNum, idcId, machineId);
}
}private SnowFlakeGenerator(int idcBitNum, int machineBitNum, long idcId, long machineId) {
int sequenceBitNum = REMAIN_BIT_NUM - idcBitNum - machineBitNum;
if (idcBitNum <= 0 || machineBitNum <= 0 || sequenceBitNum <= 0) {
throw new IllegalArgumentException("error bit number");
}this.maxSequenceValue = https://www.it610.com/article/~(-1 << sequenceBitNum);
machineBitLeftOffset = sequenceBitNum;
idcBitLeftOffset=machineBitNum+sequenceBitNum;
timestampBitLeftOffset = idcBitNum + machineBitNum + sequenceBitNum;
this.idcId = idcId;
this.machineId = machineId;
}// 产生下一个ID
public long nextId() {
long currentStamp = getTimeMill();
if (currentStamp < lastStamp) {
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastStamp - currentStamp));
}//新的毫秒,序列从0开始,否则序列自增
if (currentStamp == lastStamp) {
sequence = (sequence + 1) & this.maxSequenceValue;
if (sequence == 0L) {
//Twitter源代码中的逻辑是循环,直到下一个毫秒
currentStamp = tilNextMillis();
//throw new IllegalStateException("sequence over flow");
}
} else {
sequence = 0L;
}lastStamp = currentStamp;
return (currentStamp - START_STAMP) << timestampBitLeftOffset | idcId << idcBitLeftOffset | machineId << machineBitLeftOffset | sequence;
}private long getTimeMill() {
return System.currentTimeMillis();
}private long tilNextMillis() {
long timestamp = getTimeMill();
while (timestamp <= lastStamp) {
timestamp = getTimeMill();
}
return timestamp;
}
}
【数据结构|雪花算法(snowflake)实现分布式ID的生成】
推荐阅读
- 画解算法(1.|画解算法:1. 两数之和)
- Guava|Guava RateLimiter与限流算法
- 错过(一)
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器(Swift)
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾(SVD在协同过滤推荐系统中的应用)