snowflake(Snowflake的使用方法以及示例分析)

雪花算法-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都不浪費

看完上述內容是否對您有幫助呢?如果還想對相關知識有進一步的了解或閱讀更多相關文章,請關注本站行業資訊頻道,感謝您對本站的支持。