雪花算法-Snowflake

Snowflake,雪花算法是由Twitter开源的分布式ID生成算法,以划分命名空间的方式将 64-bit位分割成多个部分,每个部分代表不同的含义。而 Java中64bit的整数是Long类型,所以在 Java 中 SnowFlake 算法生成的 ID 就是 long 来存储的。

• 第1位占用1bit,其值始终是0,可看做是符号位不使用。

• 第2位开始的41位是时间戳,41-bit位可表示2^41个数,每个数代表毫秒,那么雪花算法可用的时间年限是(1L<<41)/(1000L360024*365)=69 年的时间。

• 中间的10-bit位可表示机器数,即2^10 = 1024台机器,但是一般情况下我们不会部署这么台机器。如果我们对IDC(互联网数据中心)有需求,还可以将 10-bit 分 5-bit 给 IDC,分5-bit给工作机器。这样就可以表示32个IDC,每个IDC下可以有32台机器,具体的划分可以根据自身需求定义。

• 最后12-bit位是自增序列,可表示2^12 = 4096个数。

这样的划分之后相当于在一毫秒一个数据中心的一台机器上可产生4096个有序的不重复的ID。但是我们 IDC 和机器数肯定不止一个,所以毫秒内能生成的有序ID数是翻倍的。

Snowflake 的Twitter官方原版是用Scala写的,对Scala语言有研究的同学可以去阅读下,以下是 Java 版本的写法。

packagecom.xxx.util;/***Twitter_Snowflake<br>*SnowFlake的结构如下(每部分用-分开):<br>*0-00000000000000000000000000000000000000000-00000-00000-000000000000<br>*1位标识,由于long基本类型在Java中是带符号的,最高位是符号位,正数是0,负数是1,所以id一般是正数,最高位是0<br>*41位时间截(毫秒级),注意,41位时间截不是存储当前时间的时间截,而是存储时间截的差值(当前时间截-开始时间截)*得到的值),这里的的开始时间截,一般是我们的id生成器开始使用的时间,由我们程序来指定的(如下下面程序IdWorker类的startTime属性)。41位的时间截,可以使用69年,年T=(1L<<41)/(1000L*60*60*24*365)=69<br>*10位的数据机器位,可以部署在1024个节点,包括5位datacenterId和5位workerId<br>*12位序列,毫秒内的计数,12位的计数顺序号支持每个节点每毫秒(同一机器,同一时间截)产生4096个ID序号<br>*加起来刚好64位,为一个Long型。<br>*SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。**@authorwsh*@version1.0*@sinceJDK1.8*@date2019/7/31*/publicclassSnowflakeDistributeId{//==============================Fields===========================================/***开始时间截(2015-01-01)*/privatefinallongtwepoch=1420041600000L;/***机器id所占的位数*/privatefinallongworkerIdBits=5L;/***数据标识id所占的位数*/privatefinallongdatacenterIdBits=5L;/***支持的最大机器id,结果是31(这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)*/privatefinallongmaxWorkerId=-1L^(-1L<<workerIdBits);/***支持的最大数据标识id,结果是31*/privatefinallongmaxDatacenterId=-1L^(-1L<<datacenterIdBits);/***序列在id中占的位数*/privatefinallongsequenceBits=12L;/***机器ID向左移12位*/privatefinallongworkerIdShift=sequenceBits;/***数据标识id向左移17位(12+5)*/privatefinallongdatacenterIdShift=sequenceBits+workerIdBits;/***时间截向左移22位(5+5+12)*/privatefinallongtimestampLeftShift=sequenceBits+workerIdBits+datacenterIdBits;/***生成序列的掩码,这里为4095(0b111111111111=0xfff=4095)*/privatefinallongsequenceMask=-1L^(-1L<<sequenceBits);/***工作机器ID(0~31)*/privatelongworkerId;/***数据中心ID(0~31)*/privatelongdatacenterId;/***毫秒内序列(0~4095)*/privatelongsequence=0L;/***上次生成ID的时间截*/privatelonglastTimestamp=-1L;//==============================Constructors=====================================/***构造函数**@paramworkerId工作ID(0~31)*@paramdatacenterId数据中心ID(0~31)*/publicSnowflakeDistributeId(longworkerId,longdatacenterId){if(workerId>maxWorkerId||workerId<0){thrownewIllegalArgumentException(String.format("workerIdcan'tbegreaterthan%dorlessthan0",maxWorkerId));}if(datacenterId>maxDatacenterId||datacenterId<0){thrownewIllegalArgumentException(String.format("datacenterIdcan'tbegreaterthan%dorlessthan0",maxDatacenterId));}this.workerId=workerId;this.datacenterId=datacenterId;}//==============================Methods==========================================/***获得下一个ID(该方法是线程安全的)**@returnSnowflakeId*/publicsynchronizedlongnextId(){longtimestamp=timeGen();//如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过这个时候应当抛出异常if(timestamp<lastTimestamp){thrownewRuntimeException(String.format("Clockmovedbackwards.Refusingtogenerateidfor%dmilliseconds",lastTimestamp-timestamp));}//如果是同一时间生成的,则进行毫秒内序列if(lastTimestamp==timestamp){sequence=(sequence+1)&sequenceMask;//毫秒内序列溢出if(sequence==0){//阻塞到下一个毫秒,获得新的时间戳timestamp=tilNextMillis(lastTimestamp);}}//时间戳改变,毫秒内序列重置else{sequence=0L;}//上次生成ID的时间截lastTimestamp=timestamp;//移位并通过或运算拼到一起组成64位的IDreturn((timestamp-twepoch)<<timestampLeftShift)//|(datacenterId<<datacenterIdShift)//|(workerId<<workerIdShift)//|sequence;}/***阻塞到下一个毫秒,直到获得新的时间戳**@paramlastTimestamp上次生成ID的时间截*@return当前时间戳*/protectedlongtilNextMillis(longlastTimestamp){longtimestamp=timeGen();while(timestamp<=lastTimestamp){timestamp=timeGen();}returntimestamp;}/***返回以毫秒为单位的当前时间**@return当前时间(毫秒)*/protectedlongtimeGen(){returnSystem.currentTimeMillis();}}

测试的代码如下

publicstaticvoidmain(String[]args){SnowflakeDistributeIdidWorker=newSnowflakeDistributeId(0,0);for(inti=0;i<1000;i++){longid=idWorker.nextId();//System.out.println(Long.toBinaryString(id));System.out.println(id);}}

雪花算法提供了一个很好的设计思想,雪花算法生成的ID是趋势递增,不依赖数据库等第三方系统,以服务的方式部署,稳定性更高,生成ID的性能也是非常高的,而且可以根据自身业务特性分配bit位,非常灵活。

但是雪花算法强依赖机器时钟,如果机器上时钟回拨,会导致发号重复或者服务会处于不可用状态。如果恰巧回退前生成过一些ID,而时间回退后,生成的ID就有可能重复。官方对于此并没有给出解决方案,而是简单的抛错处理,这样会造成在时间被追回之前的这段时间服务不可用。

雪花算法(Snowflake) - 改进版

• 时间戳:高位取从2018年1月1日到现在的毫秒数,假设系统至少运行10年,那至少需要10年365天24小时3600秒1000毫秒=320*10^9,差不多预留39bit给毫秒数

• 业务线:8bit

• 机器:自动生成,预留10bit

• 毫秒内序号:每秒的单机高峰并发量小于10W,即平均每毫秒的单机高峰并发量小于100,差不多预留7bit给每毫秒内序列号。

代码如下:

SnowflakeIdGenerator.java

packagecom.wsh.common.util;importcom.wsh.common.exception.IdsException;importjava.net.InetAddress;importjava.net.InterfaceAddress;importjava.net.NetworkInterface;importjava.net.SocketException;importjava.util.List;importjava.util.Random;/***Snowflake算法改进版**@authorwsh*@version1.0*@date2019/7/31*@sinceJDK1.8*/publicclassSnowflakeIdGenerator{/***业务线标识id所占的位数**/privatefinallongserviceIdBits=8L;/***业务线标识支持的最大数据标识id(这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)*/privatefinallongmaxServiceId=-1L^(-1L<<serviceIdBits);privatefinallongserviceId;/***机器id所占的位数**/privatefinallongworkerIdBits=10L;/***支持的最大机器id*/privatefinallongmaxWorkerId=-1L^(-1L<<workerIdBits);privatefinallongworkerId;/***序列在id中占的位数**/privatefinallongsequenceBits=7L;privatefinallongsequenceMask=-1L^(-1L<<sequenceBits);/***开始时间戳(2018年1月1日)**/privatefinallongtwepoch=1514736000000L;/***最后一次的时间戳**/privatevolatilelonglastTimestamp=-1L;/***毫秒内序列**/privatevolatilelongsequence=0L;/***随机生成器**/privatestaticvolatileRandomrandom=newRandom();/***机器id左移位数**/privatefinallongworkerIdShift=sequenceBits;/***业务线id左移位数**/privatefinallongserviceIdShift=workerIdBits+sequenceBits;/***时间戳左移位数**/privatefinallongtimestampLeftShift=serviceIdBits+workerIdBits+sequenceBits;publicSnowflakeIdGenerator(longserviceId){if((serviceId>maxServiceId)||(serviceId<0)){thrownewIllegalArgumentException(String.format("serviceIdcan'tbegreaterthan%dorlessthan0",maxServiceId));}workerId=getWorkerId();if((workerId>maxWorkerId)||(workerId<0)){thrownewIllegalArgumentException(String.format("workerIdcan'tbegreaterthan%dorlessthan0",maxWorkerId));}this.serviceId=serviceId;}publicsynchronizedlongnextId()throwsIdsException{longtimestamp=System.currentTimeMillis();if(timestamp<lastTimestamp){thrownewIdsException("Clockmovedbackwards.Refusingtogenerateidfor"+(lastTimestamp-timestamp)+"milliseconds.");}//如果是同一时间生成的,则进行毫秒内序列if(lastTimestamp==timestamp){sequence=(sequence+1)&sequenceMask;if(sequence==0){timestamp=tilNextMillis(lastTimestamp);}}else{//跨毫秒时,序列号总是归0,会导致序列号为0的ID比较多,导致生成的ID取模后不均匀,所以采用10以内的随机数sequence=random.nextInt(10)&sequenceMask;}//上次生成ID的时间截(设置最后时间戳)lastTimestamp=timestamp;//移位并通过或运算拼到一起组成64位的IDreturn((timestamp-twepoch)<<timestampLeftShift)//时间戳|(serviceId<<serviceIdShift)//业务线|(workerId<<workerIdShift)//机器|sequence;//序号}/***等待下一个毫秒的到来,保证返回的毫秒数在参数lastTimestamp之后*不停获得时间,直到大于最后时间*/privatelongtilNextMillis(finallonglastTimestamp){longtimestamp=System.currentTimeMillis();while(timestamp<=lastTimestamp){timestamp=System.currentTimeMillis();}returntimestamp;}/***根据机器的MAC地址获取工作进程Id,也可以使用机器IP获取工作进程Id,取最后两个段,一共10个bit*极端情况下,MAC地址后两个段一样,产品的工作进程Id会一样;再极端情况下,并发不大时,刚好跨毫秒,又刚好随机出来的sequence一样的话,产品的Id会重复**@return*@throwsIdsException*/protectedlonggetWorkerId()throwsIdsException{try{java.util.Enumeration<NetworkInterface>en=NetworkInterface.getNetworkInterfaces();while(en.hasMoreElements()){NetworkInterfaceiface=en.nextElement();List<InterfaceAddress>addrs=iface.getInterfaceAddresses();for(InterfaceAddressaddr:addrs){InetAddressip=addr.getAddress();NetworkInterfacenetwork=NetworkInterface.getByInetAddress(ip);if(network==null){continue;}byte[]mac=network.getHardwareAddress();if(mac==null){continue;}longid=((0x000000FF&(long)mac[mac.length-1])|(0x0000FF00&(((long)mac[mac.length-2])<<8)))>>11;if(id>maxWorkerId){returnnewRandom(maxWorkerId).nextInt();}returnid;}}returnnewRandom(maxWorkerId).nextInt();}catch(SocketExceptione){thrownewIdsException(e);}}/***获取序号**@paramid*@return*/publicstaticLonggetSequence(Longid){Stringstr=Long.toBinaryString(id);intsize=str.length();StringsequenceBinary=str.substring(size-7,size);returnLong.parseLong(sequenceBinary,2);}/***获取机器**@paramid*@return*/publicstaticLonggetWorker(Longid){Stringstr=Long.toBinaryString(id);intsize=str.length();StringsequenceBinary=str.substring(size-7-10,size-7);returnLong.parseLong(sequenceBinary,2);}/***获取业务线**@paramid*@return*/publicstaticLonggetService(Longid){Stringstr=Long.toBinaryString(id);intsize=str.length();StringsequenceBinary=str.substring(size-7-10-8,size-7-10);returnLong.parseLong(sequenceBinary,2);}}

IdsGen.java

packagecom.wsh.common.util;/***ID生成器**@authorwsh*@version1.0*@date2019/7/31*@sinceJDK1.8*/publicenumIdsGen{/***基础公共*/BASIC(0),/***业务服务*/BUSSINESS(1),/***其它*/OTHER(255);privateSnowflakeIdGeneratorsnowflakeIdGenerator;IdsGen(finalintservice){snowflakeIdGenerator=newSnowflakeIdGenerator(service);}publiclonggetIdGen(){returnsnowflakeIdGenerator.nextId();}publicStringgetIdGenStr(){returnString.valueOf(snowflakeIdGenerator.nextId());}}

Test.java

packagecom.wsh.common.util;/***@authorwsh*@version1.0*@date2019/7/31*@sinceJDK1.8*/publicclassTest{publicstaticvoidmain(String[]args){longt=System.currentTimeMillis();for(inti=0;i<10000;i++){System.out.println(IdsGen.BASIC.getIdGenStr());}longt1=System.currentTimeMillis();System.out.println("耗时-->"+(t1-t));}}

缺点:

1. 极端情况下,获取的workerId可能会重复,请看getWorkerId的注释,后续可以改造为读取配置文件,如果配置文件读取不到再自动生成

2. 无法避免时间回拨,比如润秒

3. 无法保证每个ID都不浪费

看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注本站行业资讯频道,感谢您对本站的支持。