雪花算法、梨花算法、薄雾算法等在分布式中全局唯⼀ID的⽣成和使⽤及其特性雪花算法、梨花算法、薄雾算法等在分布式中全局唯⼀ID的⽣成和使⽤及其特性。
互联⽹快速发展的今天，分布式应⽤系统已经见怪不怪，在分布式系统中，我们需要各种各样的ID，既然是ID那么必然是要保证全局唯⼀，除此之外，不同当业务还需要不同的特性，⽐如像并发巨⼤的业务要求ID⽣成效率⾼，吞吐⼤；⽐如某些银⾏类业务，需要按每⽇⽇期制定交易流⽔号等等。针对每个公司，随着服务化演进，单个服务越来越多，数据库分的越来越细，有的时候⼀个业务需要分成好⼏个库，这时候⾃增主键或者序列之类的主键id⽣成⽅式已经不再满⾜需求，分布式系统中需要的是⼀个全局唯⼀的id⽣成规则。既然号称在全局分布式系统中唯⼀，那么主键的⽣成规则必然要复杂⼀些。
雪花算法（SnowFlake）
SnowFlake 算法，是 Twitter 开源的分布式 id ⽣成算法。其核⼼思想就是：使⽤⼀个 64 bit 的 long 型的数字作为全局唯⼀ id。在分布式系统中的应⽤⼗分⼴泛，且ID 引⼊了时间戳，基本上保持递增的。这 64 个 bit 中，其中 1 个 bit 是不⽤的，然后⽤其中的 41 bit 作为毫秒数，⽤ 10 bit 作为⼯作机器 id，12 bit 作为序列号。举个例⼦，⽐如下⾯那个 64 bit 的 long 型数字：
0｜1020000000000000000000000000000000000000000｜10001 11001｜100000000001
第⼀个部分，是 1 个 bit：0，这个是⽆意义的。
第⼆个部分是 41 个 bit：表⽰的是时间戳。
第三个部分是 5 个 bit：表⽰的是机房 id，10001。
第四个部分是 5 个 bit：表⽰的是机器 id，11001。
第五个部分是 12 个 bit：表⽰的序号，就是某个机房某台机器上这⼀毫秒内同时⽣成的 id 的序号，0000 00000000。
化工与制药类①1 bit：是不⽤的，为啥呢？
因为⼆进制⾥第⼀个 bit 为如果是 1，那么都是负数，但是我们⽣成的 id 都是正数，所以第⼀个 bit 统⼀都是 0。
②41 bit：表⽰的是时间戳，单位是毫秒。
41 bit 可以表⽰的数字多达 2^41 - 1，也就是可以标识 2 ^ 41 - 1 个毫秒值，换算成年就是表⽰ 69 年的时间。
③10 bit：记录⼯作机器 id，代表的是这个服务最多可以部署在 2^10 台机器上，也就是 1024 台机器。
但是 10 bit ⾥ 5 个 bit 代表机房 id，5 个 bit 代表机器 id。意思就是最多代表 2 ^ 5 个机房（32 个机房），每个机房⾥可以代表 2 ^ 5个机器（32 台机器），也可以根据⾃⼰公司的实际情况确定。
④12 bit：这个是⽤来记录同⼀个毫秒内产⽣的不同 id。
12 bit 可以代表的最⼤正整数是 2 ^ 12 - 1 = 4096，也就是说可以⽤这个 12 bit 代表的数字来区分同⼀个毫秒内的 4096 个不同的id。
简单来说，你的某个服务假设要⽣成⼀个全局唯⼀ id，那么就可以发送⼀个请求给部署了 SnowFlake 算法的系统，由这个 SnowFlake 算法系统来⽣成唯⼀ id。
这个 SnowFlake 算法系统⾸先肯定是知道⾃⼰所在的机房和机器的，⽐如机房 id = 17，机器 id = 12。
接着 SnowFlake 算法系统接收到这个请求之后，⾸先就会⽤⼆进制位运算的⽅式⽣成⼀个 64 bit 的 long 型 id，64 个 bit 中的第⼀个
bit 是⽆意义的。
接着 41 个 bit，就可以⽤当前时间戳（单位到毫秒），然后接着 5 个 bit 设置上这个机房 id，还有 5 个 bit 设置上机器 id。
最后再判断⼀下，当前这台机房的这台机器上这⼀毫秒内，这是第⼏个请求，给这次⽣成 id 的请求累加⼀个序号，作为最后的 12 个 bit。
最终⼀个 64 个 bit 的 id 就出来了，这个算法可以保证说，⼀个机房的⼀台机器上，在同⼀毫秒内，⽣成了⼀个唯⼀的 id。可能⼀个毫秒内会⽣成多个 id，但是有最后 12 个 bit 的序号来区分开来。
下⾯我们简单看看这个 SnowFlake 算法的⼀个代码实现，这就是个⽰例，总之就是⽤⼀个 64 bit 的数字中各个 bit 位来设置不同的标志位，区分每⼀个 id。
public class IdWorker {
//因为⼆进制⾥第⼀个 bit 为如果是 1，那么都是负数，但是我们⽣成的 id 都是正数，所以第⼀个 bit 统⼀都是 0。//机器ID 2进制5位 32位减掉1位 31个
private long workerId;
//机房ID 2进制5位 32位减掉1位 31个
private long datacenterId;
//代表⼀毫秒内⽣成的多个id的最新序号 12位 4096 -1 = 4095 个
private long sequence;
//设置⼀个时间初始值 2^41 - 1 差不多可以⽤69年
private long twepoch =1585644268888L;
//5位的机器id
private long workerIdBits =5L;
//5位的机房id
private long datacenterIdBits =5L;
//每毫秒内产⽣的id数 2 的 12次⽅
private long sequenceBits =12L;
// 这个是⼆进制运算，就是5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
private long maxWorkerId =-1L ^(-1L << workerIdBits);
/
/ 这个是⼀个意思，就是5 bit最多只能有31个数字，机房id最多只能是32以内
private long maxDatacenterId =-1L ^(-1L << datacenterIdBits);
private long workerIdShift = sequenceBits;
private long datacenterIdShift = sequenceBits + workerIdBits;
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
private long sequenceMask =-1L ^(-1L << sequenceBits);
//记录产⽣时间毫秒数，判断是否是同1毫秒
private long lastTimestamp =-1L;
public long getWorkerId(){
return workerId;
}
public long getDatacenterId(){
return datacenterId;
}
public long getTimestamp(){
return System.currentTimeMillis();
}
public IdWorker(long workerId,long datacenterId,long sequence){
// 检查机房id和机器id是否超过31 不能⼩于0
if(workerId > maxWorkerId || workerId <0){
throw new IllegalArgumentException(
String.format("worker Id can't be greater than %d or less than 0",maxWorkerId));
}
if(datacenterId > maxDatacenterId || datacenterId <0){
throw new IllegalArgumentException(
String.format("datacenter Id can't be greater than %d or less than 0",maxDatacenterId));
}
学习科学发展观this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
// 这个是核⼼⽅法，通过调⽤nextId()⽅法，让当前这台机器上的snowflake算法程序⽣成⼀个全局唯⼀的id public synchronized long nextId(){
// 这⼉就是获取当前时间戳，单位是毫秒
long timestamp =timeGen();
if(timestamp < lastTimestamp){
"clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(
String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
// 下⾯是说假设在同⼀个毫秒内，⼜发送了⼀个请求⽣成⼀个id
// 这个时候就得把seqence序号给递增1，最多就是4096
if(lastTimestamp == timestamp){
天涯明月刀职业选择/
/ 这个意思是说⼀个毫秒内最多只能有4096个数字，⽆论你传递多少进来，
//这个位运算保证始终就是在4096这个范围内，避免你⾃⼰传递个sequence超过了4096这个范围
sequence =(sequence +1)& sequenceMask;
//当某⼀毫秒的时间，产⽣的id数超过4095，系统会进⼊等待，直到下⼀毫秒，系统继续产⽣ID
if(sequence ==0){
timestamp =tilNextMillis(lastTimestamp);
}
}else{
sequence =0;
}
// 这⼉记录⼀下最近⼀次⽣成id的时间戳，单位是毫秒
lastTimestamp = timestamp;
// 这⼉就是最核⼼的⼆进制位运算操作，⽣成⼀个64bit的id
// 先将当前时间戳左移，放到41 bit那⼉；将机房id左移放到5 bit那⼉；将机器id左移放到5 bit那⼉；将序号放最后12 bit // 最后拼接起来成⼀个64 bit的⼆进制数字，转换成10进制就是个long型
return((timestamp - twepoch)<< timestampLeftShift)|
(datacenterId << datacenterIdShift)|
(workerId << workerIdShift)| sequence;
}
/**
* 当某⼀毫秒的时间，产⽣的id数超过4095，系统会进⼊等待，直到下⼀毫秒，系统继续产⽣ID
* @param lastTimestamp
* @return
*/
private long tilNextMillis(long lastTimestamp){
long timestamp =timeGen();
while(timestamp <= lastTimestamp){
timestamp =timeGen();
}
return timestamp;
}
//获取当前时间戳
private long timeGen(){
return System.currentTimeMillis();
}
/**
* main 测试类
* @param args
*/
public static void main(String[] args){
System.out.println(1&4596);
System.out.println(2&4596);
System.out.println(6&4596);
System.out.println(6&4596);
System.out.println(6&4596);
祝国庆节快乐
System.out.println(6&4596);
IdWorker worker =new IdWorker(1,1,1);
for(int i =0; i <22; i++){
System.out.Id());
}
}
SnowFlake算法的优点：
（1）⾼性能⾼可⽤：⽣成时不依赖于数据库，完全在内存中⽣成。
（2）容量⼤：每秒中能⽣成数百万的⾃增ID。
（3）ID⾃增：存⼊数据库中，索引效率⾼。
SnowFlake算法的缺点：
依赖与系统时间的⼀致性，如果系统时间被回调，或者改变，可能会造成id冲突或者重复。
实际中我们的机房并没有那么多，我们可以改进改算法，将10bit的机器id优化，成业务表或者和我们系统相关的业务。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 =~(-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;
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论