雪花算法

雪花算法雪花算法SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数

欢迎大家来到IT世界,在知识的湖畔探索吧!

雪花算法

SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛,且ID 引入了时间戳,基本上保持自增的。本文主要是是实现了单机版本的算法,使用多台计算机构成分布式的ID生成服务也是可以的,预留了相关的方法参数。

应用范围

1、在jdk中自带的uuid算法可以来生成唯一性的32位字符串【拼接上‘-’之后,是36位,如:’4211210a-ba56-41b4-b055-6262411970a4’】,uuid算法得到的id是无序的,而且是字符串,数据表记录多时,查询效率不高

2、基于数据库的sequnce【通过表也可以模拟sequence】来生成,在分布式系统中更新记录不方便,只能操作主表的更新。

3、雪花算法在分布式系统中可以较好地使用。

原理

把64位进行拆分,分为如下几个部份

第1部份只占1位,而且必需为0,因为最高位0表示正数。

第2部份是时间戳,占41位【为什么是41位,后面会介绍】,最多可以表示2^41,大约是69年

第3部份是产生的机器号,占10位【也可以是其它位数,不一定非得是10位,官方约定是10位】,最多可以表示2^10,相当于1024台机器,这部分可以划成两个维度,如下:

3.1 拿5位出来做为机房号,最多可以表示 2^5个机房号,也就是最多32个机房编号

3.2 拿5位出来做为机器号,最多可以表示 2^5台电脑,也就是最多32台电脑编号

第4部份是时间戳,占12位,相当于在同一个毫秒内,可以最大支持2^12,也就是4096个序号【普通的计算机根本达不到】

代码实现

public class IdGenerator {

//定义属性 [机器码10位,如何分配成 机房码和电脑码,做为属性,这里默认都是5]

private final long dataCenterBits = 5L; //机房码的位数

private final long computerBits = 5L; //电脑码的位数

//最后的序列码,默认从0开始

private long sequence = 0L;

//记录执行的最后时间,以毫秒为单位,默认初始化为-1L

private long lastTimeStamp = -1L;

//因为要做二进制运算,我们需要定义如下属性来记录每个部份所在的位置的偏移量

private final long sequenceBits = 12; //序号占用12位

private final long computerIdShift = sequenceBits; //电脑码的偏移量

private final long dataCenterIdShift = computerIdShift + computerBits; //机房码的偏移量

private final long timeStampShift = dataCenterIdShift + dataCenterBits; //时间戳的偏移量

//根据机房码的位数,来计算出机房码最大值

private final long MAX_DATA_CENTER = -1L ^ (-1L << dataCenterBits); //相当于 11111, 也就是 31

private final long MAX_COMPUTER = -1L ^ (-1L << computerBits); //同上

private final long SEQUENCE_MASK = -1L ^ (-1L << sequenceBits); // 为防止序列号溢出而准备的掩码,相当于 11111111 111

//定义属性

private long computerId; //电脑的id 【在分布式系统中,记录这个雪花号是由哪一台电脑生成的】

private long dataCenterId; //机房的id 【在分布式系统中,记录这个雪花号是由哪一个中心机房里的电脑生成的】

//构造

public IdGenerator(long computerId, long dataCenterId) {

//对参数的有效性进行判断,由于机房码和电脑码都是5位,所以,它们的值最大都不能超过31

if(computerId > MAX_COMPUTER || computerId < 0) {

throw new IllegalArgumentException(String.format(“电脑编号不能大于 %d 或者小于 %d \n”,MAX_COMPUTER,0));

}

if(dataCenterId > MAX_DATA_CENTER || dataCenterId < 0) {

throw new IllegalArgumentException(String.format(“机房编号不能大于 %d 或者小于 %d\n”,MAX_DATA_CENTER, 0));

}

//赋值

this.computerId = computerId;

this.dataCenterId = dataCenterId;

}

/***************

* 核心方法,利用雪花算法来获取一个唯一性的ID

* @return

*/

public synchronized long nextId() {

//1.获取当前的系统时间

long currTime = getCurrentTime();

//2. 判断是否在同一个时间内的请求

if(currTime == lastTimeStamp) {

//2.1 sequence 要增1, 但要预防sequence超过 最大值4095,所以要 与 SEQUENCE_MASK 按位求与

sequence = (sequence + 1) & SEQUENCE_MASK;

//2.2 进一步判断,如果在同一个毫秒内,sequence达到了4096【1 0000 0000 0000】,则lastTime时间戳必需跳入下一个时间,因为同一个毫秒内

//sequence只能产生4096个【0-4095】,当超过时,必需跳入下一个毫秒

// 【此情况极少出现,但不可不防,这意味着1个毫秒内,JVM要执行此方法达到4096次,我这个电脑执行远达不到。】

if(sequence == 0) {

currTime = unitNextTime();

}

} else {

//如果不是与lastTime一样,则表示进入了下一个毫秒,则sequence重新计数

sequence = 0L;

}

//3. 把当前时间赋值给 lastTime, 以便下一次判断是否处在同一个毫秒内

lastTimeStamp = currTime;

//4. 依次把各个部门求出来并通过逻辑或 拼接起来

return (this.lastTimeStamp << timeStampShift) | //把当前系统时间 左移22位

(this.dataCenterId << dataCenterIdShift) | //把机房编号 左移17位

(this.computerId << computerIdShift) | //把计算机号编号左移 12位

this.sequence; //最后的序列号占12位,无需移动

}

/******

* 等待毫秒数进入下一个时间

* @return

*/

private long unitNextTime() {

//1.再次获取系统时间

long timestamp = getCurrentTime();

//2. 判断 lastTime与currentTime是否一样

while(timestamp <= lastTimeStamp) {

//2.1 继续获取系统时间,直到上面的条件不成立为止

timestamp = getCurrentTime();

}

//3. 返回

return timestamp;

}

/*****

* 用来获取当前的系统时间,以毫秒为单位

* @return

*/

private long getCurrentTime() {

return System.currentTimeMillis();

}

}

测试类

public class UseIdGenerator {

/****

* 主方法

* @param args

*/

public static void main(String[] args) {

//这里两个参数都是1,表示1号机房和1号电脑【在分布式系统中,每个电脑知道自己所在的机房和编号】

IdGenerator ig = new IdGenerator(1,1);

//循环生成

long result = -1;

for(int i = 0;i<100000;i++) {

result = ig.nextId();

System.out.println(result+” , “+Long.toBinaryString(result));

}

}

}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/37992.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信