雪花算法(snowflake)
1、 背景
分布式系统中，有一些需要使用全局唯一ID的场景，这种时候为了防止ID冲突可以使用36位的UUID，但是UUID有一些缺点，首先他相对比较长，另外UUID一般是无序的。
有些时候我们希望能使用一种简单一些的ID，并且希望ID能够按照时间有序生成。
而twitter的snowflake解决了这种需求，最初Twitter把存储系统从MySQL迁移到Cassandra，因为Cassandra没有顺序ID生成机制，为了满足Twitter每秒上万条消息的请求，每条消息都必须分配一条唯一的id，这些id还需要一些大致的顺序（方便客户端排序），并且在分布式系统中不同机器产生的id必须不同，所以twitter开发了这样一套全局唯一ID生成服务。
2、Snowflake算法核心
- SnowFlake的结构如下(每部分用-分开): 把时间戳，工作机器id，序列号组合在一起。
文章图片
*41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截) 后得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69
10位的数据机器位，可以部署在1024个节点，包括10位workerId
12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
加起来刚好64位，为一个Long型。
public class SnowFlakeGenerator { 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 final static long START_STAMP = 1553153540626L;
/**
* 可分配的位数
*/
private final static int REMAIN_BIT_NUM = 12;
/**
* 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;
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 = idcBitNum + sequenceBitNum;
timestampBitLeftOffset = idcBitNum + machineBitNum + sequenceBitNum;
this.idcId = idcId;
this.machineId = machineId;
} /**
* 产生下一个ID
*/
public synchronized 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源代码中的逻辑是循环，直到下一个毫秒
lastStamp = 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;
} public static void main(String[] args) {
SnowFlakeGenerator snowFlakeGenerator = new SnowFlakeGenerator.Factory().create(1, 1);
long start = System.currentTimeMillis();
for (long i = 0;
i < 100000;
i++) {
System.out.println(snowFlakeGenerator.nextId());
}
System.out.println(System.currentTimeMillis() - start);
}
}
【雪花算法(snowflake)】
/**
* Twitter的分布式自增ID雪花算法snowflake
*
*
*/
public class SnowFlake { /**
* 起始的时间戳
*/
private final static long START_STMP = 1553153540626L;
/**
* 每一部分占用的位数
*/
private final static long SEQUENCE_BIT = 2;
// 序列号占用的位数
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 = getNowMill();
if (currStmp < lastStmp) {
throw new RuntimeException("Clock moved backwards.Refusing to generate id");
}if (currStmp == lastStmp) {
// 相同毫秒内，序列号自增
sequence = (sequence + 1) & 3;
// 同一毫秒的序列数已经达到最大
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 = getNowMill();
while (mill <= lastStmp) {
mill = getNowMill();
}
return mill;
} private long getNowMill() {
return System.currentTimeMillis();
} public static void main(String[] args) {
SnowFlake snowFlake = new SnowFlake(1, 1);
long start = System.currentTimeMillis();
for (int i = 0;
i < 100000;
i++) {
System.out.println(snowFlake.nextId());
}System.out.println(System.currentTimeMillis() - start);
}
}推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 错过（一）
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）