您好,登錄后才能下訂單哦!
這篇文章主要講解了“Snowflake算法的實(shí)現(xiàn)原理”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“Snowflake算法的實(shí)現(xiàn)原理”吧!
Snowflake
(雪花)是Twitter
開源的高性能ID
生成算法(服務(wù))。
上圖是Snowflake
的Github
倉(cāng)庫(kù),master
分支中的REAEMDE
文件中提示:初始版本于2010
年發(fā)布,基于Apache Thrift
,早于Finagle
(這里的Finagle
是Twitter
上用于RPC
服務(wù)的構(gòu)建模塊)發(fā)布,而Twitter
內(nèi)部使用的Snowflake
是一個(gè)完全重寫的程序,在很大程度上依靠Twitter
上的現(xiàn)有基礎(chǔ)架構(gòu)來運(yùn)行。
而2010
年發(fā)布的初版Snowflake
源碼是使用Scala
語言編寫的,歸檔于scala_28
分支。換言之,大家目前使用的Snowflake
算法原版或者改良版已經(jīng)是十年前(當(dāng)前是2020
年)的產(chǎn)物,不得不說這個(gè)算法確實(shí)比較厲害。scala_28
分支中有介紹該算法的動(dòng)機(jī)和要求,這里簡(jiǎn)單摘錄一下:
動(dòng)機(jī):
Cassandra
中沒有生成順序ID
的工具,Twitter
由使用MySQL
轉(zhuǎn)向使用Cassandra
的時(shí)候需要一種新的方式來生成ID
(印證了架構(gòu)不是設(shè)計(jì)出來,而是基于業(yè)務(wù)場(chǎng)景迭代出來)。
要求:
高性能:每秒每個(gè)進(jìn)程至少產(chǎn)生10K
個(gè)ID
,加上網(wǎng)絡(luò)延遲響應(yīng)速度要在2ms
內(nèi)。
順序性:具備按照時(shí)間的自增趨勢(shì),可以直接排序。
緊湊性:保持生成的ID
的長(zhǎng)度在64 bit
或更短。
高可用:ID
生成方案需要和存儲(chǔ)服務(wù)一樣高可用。
下面就Snowflake
的源碼分析一下他的實(shí)現(xiàn)原理。
Snowflake
在初版設(shè)計(jì)方案是:
時(shí)間:41 bit
長(zhǎng)度,使用毫秒級(jí)別精度,帶有一個(gè)自定義epoch
,那么可以使用大概69
年。
可配置的機(jī)器ID
:10 bit
長(zhǎng)度,可以滿足1024
個(gè)機(jī)器使用。
序列號(hào):12 bit
長(zhǎng)度,可以在4096
個(gè)數(shù)字中隨機(jī)取值,從而避免單個(gè)機(jī)器在1 ms
內(nèi)生成重復(fù)的序列號(hào)。
但是在實(shí)際源碼實(shí)現(xiàn)中,Snowflake
把10 bit
的可配置的機(jī)器ID
拆分為5 bit
的Worker ID
(這個(gè)可以理解為原來的機(jī)器ID
)和5 bit
的Data Center ID
(數(shù)據(jù)中心ID
),詳情見IdWorker.scala
:
也就是說,支持配置最多32
個(gè)機(jī)器ID
和最多32
個(gè)數(shù)據(jù)中心ID
:
由于算法是Scala
語言編寫,是依賴于JVM
的語言,返回的ID
值為Long
類型,也就是64 bit
的整數(shù),原來的算法生成序列中只使用了63 bit
的長(zhǎng)度,要返回的是無符號(hào)數(shù),所以在高位補(bǔ)一個(gè)0
(占用1 bit
),那么加起來整個(gè)ID
的長(zhǎng)度就是64 bit
:
其中:
41 bit
毫秒級(jí)別時(shí)間戳的取值范圍是:[0, 2^41 - 1]
=> 0 ~ 2199023255551
,一共2199023255552
個(gè)數(shù)字。
5 bit
機(jī)器ID
的取值范圍是:[0, 2^5 - 1]
=> 0 ~ 31
,一共32
個(gè)數(shù)字。
5 bit
數(shù)據(jù)中心ID
的取值范圍是:[0, 2^5 - 1]
=> 0 ~ 31
,一共32
個(gè)數(shù)字。
12 bit
序列號(hào)的取值范圍是:[0, 2^12 - 1]
=> 0 ~ 4095
,一共4096
個(gè)數(shù)字。
那么理論上可以生成2199023255552 * 32 * 32 * 4096
個(gè)完全不同的ID
值。
Snowflake
算法還有一個(gè)明顯的特征:依賴于系統(tǒng)時(shí)鐘。41 bit
長(zhǎng)度毫秒級(jí)別的時(shí)間來源于系統(tǒng)時(shí)間戳,所以必須保證系統(tǒng)時(shí)間是向前遞進(jìn),不能發(fā)生時(shí)鐘回?fù)?/strong>(通說來說就是不能在同一個(gè)時(shí)刻產(chǎn)生多個(gè)相同的時(shí)間戳或者產(chǎn)生了過去的時(shí)間戳)。一旦發(fā)生時(shí)鐘回?fù)埽?code>Snowflake會(huì)拒絕生成下一個(gè)ID
。
Snowflake
算法中使用了大量的位運(yùn)算。由于整數(shù)的補(bǔ)碼才是在計(jì)算機(jī)中的存儲(chǔ)形式,Java
或者Scala
中的整型都使用補(bǔ)碼表示,這里稍微提一下原碼和補(bǔ)碼的知識(shí)。
原碼用于閱讀,補(bǔ)碼用于計(jì)算。
正數(shù)的補(bǔ)碼與其原碼相同。
負(fù)數(shù)的補(bǔ)碼是除最高位其他所有位取反,然后加1
(反碼加1
),而負(fù)數(shù)的補(bǔ)碼還原為原碼也是使用這個(gè)方式。
+0
的原碼是0000 0000
,而-0
的原碼是1000 0000
,補(bǔ)碼只有一個(gè)0
值,用0000 0000
表示,這一點(diǎn)很重要,補(bǔ)碼的0
沒有二義性。
簡(jiǎn)單來看就是這樣:
* [+ 11] 原碼 = [0000 1011] 補(bǔ)碼 = [0000 1011] * [- 11] 原碼 = [1000 1011] 補(bǔ)碼 = [1111 0101] * [- 11]的補(bǔ)碼計(jì)算過程: 原碼 1000 1011 除了最高位其他位取反 1111 0100 加1 1111 0101 (補(bǔ)碼)
使用原碼、反碼在計(jì)算的時(shí)候得到的不一定是準(zhǔn)確的值,而使用補(bǔ)碼的時(shí)候計(jì)算結(jié)果才是正確的,記住這個(gè)結(jié)論即可,這里不在舉例。由于Snowflake
的ID
生成方案中,除了最高位,其他四個(gè)部分都是無符號(hào)整數(shù),所以四個(gè)部分的整數(shù)使用補(bǔ)碼進(jìn)行位運(yùn)算的效率會(huì)比較高,也只有這樣才能滿足Snowflake高性能設(shè)計(jì)的初衷。Snowflake
算法中使用了幾種位運(yùn)算:異或(^
)、按位與(&
)、按位或(|
)和帶符號(hào)左移(<<
)。
異或的運(yùn)算規(guī)則是:0^0=0
0^1=1
1^0=1
1^1=0
,也就是位不同則結(jié)果為1,位相同則結(jié)果為0。主要作用是:
特定位翻轉(zhuǎn),也就是一個(gè)數(shù)和N
個(gè)位都為1
的數(shù)進(jìn)行異或操作,這對(duì)應(yīng)的N
個(gè)位都會(huì)翻轉(zhuǎn),例如0100 & 1111
,結(jié)果就是1011
。
與0
項(xiàng)異或,則結(jié)果和原來的值一致。
兩數(shù)的值交互:a=a^b
b=b^a
a=a^b
,這三個(gè)操作完成之后,a
和b
的值完成交換。
這里推演一下最后一條:
* [+ 11] 原碼 = [0000 1011] 補(bǔ)碼 = [0000 1011] a * [- 11] 原碼 = [1000 1011] 補(bǔ)碼 = [1111 0101] b a=a^b 0000 1011 1111 0101 ---------^ 1111 1110 b=b^a 1111 0101 ---------^ 0000 1011 (十進(jìn)制數(shù):11) b a=a^b 1111 1110 ---------^ 1111 0101 (十進(jìn)制數(shù):-11) a
按位與的運(yùn)算規(guī)則是:0&0=0
0&1=0
1&0=0
1&1=1
,只有對(duì)應(yīng)的位都為1的時(shí)候計(jì)算結(jié)果才是1,其他情況的計(jì)算結(jié)果都是0。主要作用是:
清零,如果想把一個(gè)數(shù)清零,那么和所有位為0
的數(shù)進(jìn)行按位與即可。
取一個(gè)數(shù)中的指定位,例如要取X
中的低4
位,只需要和zzzz...1111
進(jìn)行按位與即可,例如取1111 0110
的低4
位,則11110110 & 00001111
即可得到00000110
。
按位與的運(yùn)算規(guī)則是:0|0=0
0|1=1
1|0=1
1|1=1
,只要有其中一個(gè)位存在1則計(jì)算結(jié)果是1,只有兩個(gè)位同時(shí)為0的情況下計(jì)算結(jié)果才是0。主要作用是:
對(duì)一個(gè)數(shù)的部分位賦值為1
,只需要和對(duì)應(yīng)位全為0
的數(shù)做按位或操作就行,例如1011 0000
如果低4
位想全部賦值為1
,那么10110000 | 00001111
即可得到1011 1111
。
帶符號(hào)左移的運(yùn)算符是<<
,一般格式是:M << n
。作用如下:
M
的二進(jìn)制數(shù)(補(bǔ)碼)向左移動(dòng)n
位。
左邊(高位)移出部分直接舍棄,右邊(低位)移入部分全部補(bǔ)0
。
移位結(jié)果:相當(dāng)于M
的值乘以2
的n
次方,并且0、正、負(fù)數(shù)通用。
移動(dòng)的位數(shù)超過了該類型的最大位數(shù),那么編譯器會(huì)對(duì)移動(dòng)的位數(shù)取模,例如int
移位33
位,實(shí)際上只移動(dòng)了33 % 2 = 1
位。
推演過程如下(假設(shè)n = 2
):
* [+ 11] 原碼 = [0000 1011] 補(bǔ)碼 = [0000 1011] * [- 11] 原碼 = [1000 1011] 補(bǔ)碼 = [1111 0101] * [+ 11 << 2]的計(jì)算過程 補(bǔ)碼 0000 1011 左移2位 0000 1011 舍高補(bǔ)低 0010 1100 十進(jìn)制數(shù) 2^2 + 2^3 + 2^5 = 44 * [- 11 << 2]的計(jì)算過程 補(bǔ)碼 1111 0101 左移2位 1111 0101 舍高補(bǔ)低 1101 0100 原碼 1010 1100 (補(bǔ)碼除最高位其他所有位取反再加1) 十進(jìn)制數(shù) - (2^2 + 2^3 + 2^5) = -44
可以寫個(gè)main
方法驗(yàn)證一下:
public static void main(String[] args) { System.out.println(-11 << 2); // -44 System.out.println(11 << 2); // 44 }
利用上面提到的三個(gè)位運(yùn)算符,相互組合可以實(shí)現(xiàn)一些高效的計(jì)算方案。
計(jì)算n個(gè)bit能表示的最大數(shù)值:
Snowflake
算法中有這樣的代碼:
// 機(jī)器ID的位長(zhǎng)度 private val workerIdBits = 5L; // 最大機(jī)器ID -> 31 private val maxWorkerId = -1L ^ (-1L << workerIdBits);
這里的算子是-1L ^ (-1L << 5L)
,整理運(yùn)算符的順序,再使用64 bit
的二進(jìn)制數(shù)推演計(jì)算過程如下:
* [-1] 的補(bǔ)碼 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 左移5位 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11100000 [-1] 的補(bǔ)碼 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 異或 ----------------------------------------------------------------------- ^ 結(jié)果的補(bǔ)碼 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00011111 (十進(jìn)制數(shù) 2^0 + 2^1 + 2^2 + 2^3 + 2^4 = 31)
這樣就能計(jì)算出5 bit
能表示的最大數(shù)值n
,n
為整數(shù)并且0 <= n <= 31
,即0、1、2、3...31
。Worker ID
和Data Center ID
部分的最大值就是使用這種組合運(yùn)算得出的。
用固定位的最大值作為Mask避免溢出:
Snowflake
算法中有這樣的代碼:
var sequence = 0L ...... private val sequenceBits = 12L // 這里得到的是sequence的最大值4095 private val sequenceMask = -1L ^ (-1L << sequenceBits) ...... sequence = (sequence + 1) & sequenceMask
最后這個(gè)算子其實(shí)就是sequence = (sequence + 1) & 4095
,假設(shè)sequence
當(dāng)前值為4095
,推演一下計(jì)算過程:
* [4095] 的補(bǔ)碼 00000000 00000000 00000000 00000000 00000000 00000000 00000111 11111111 [sequence + 1] 的補(bǔ)碼 00000000 00000000 00000000 00000000 00000000 00000000 00001000 00000000 按位與 ----------------------------------------------------------------------- & 計(jì)算結(jié)果 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 (十進(jìn)制數(shù):0)
可以編寫一個(gè)main
方法驗(yàn)證一下:
public static void main(String[] args) { int mask = 4095; System.out.println(0 & mask); // 0 System.out.println(1 & mask); // 1 System.out.println(2 & mask); // 2 System.out.println(4095 & mask); // 4095 System.out.println(4096 & mask); // 0 System.out.println(4097 & mask); // 1 }
也就是x = (x + 1) & (-1L ^ (-1L << N))
能保證最終得到的x
值不會(huì)超過N
,這是利用了按位與中的"取指定位"的特性。
Snowflake
雖然用Scala
語言編寫,語法其實(shí)和Java
差不多,當(dāng)成Java
代碼這樣閱讀就行,下面閱讀代碼的時(shí)候會(huì)跳過一些日志記錄和度量統(tǒng)計(jì)的邏輯。先看IdWorker.scala
的屬性值:
// 定義基準(zhǔn)紀(jì)元值,這個(gè)值是北京時(shí)間2010-11-04 09:42:54,估計(jì)就是2010年初版提交代碼時(shí)候定義的一個(gè)時(shí)間戳 val twepoch = 1288834974657L // 初始化序列號(hào)為0 var sequence = 0L //TODO after 2.8 make this a constructor param with a default of 0 // 機(jī)器ID的最大位長(zhǎng)度為5 private val workerIdBits = 5L // 數(shù)據(jù)中心ID的最大位長(zhǎng)度為5 private val datacenterIdBits = 5L // 最大的機(jī)器ID值,十進(jìn)制數(shù)為為31 private val maxWorkerId = -1L ^ (-1L << workerIdBits) // 最大的數(shù)據(jù)中心ID值,十進(jìn)制數(shù)為為31 private val maxDatacenterId = -1L ^ (-1L << datacenterIdBits) // 序列號(hào)的最大位長(zhǎng)度為12 private val sequenceBits = 12L // 機(jī)器ID需要左移的位數(shù)12 private val workerIdShift = sequenceBits // 數(shù)據(jù)中心ID需要左移的位數(shù) = 12 + 5 private val datacenterIdShift = sequenceBits + workerIdBits // 時(shí)間戳需要左移的位數(shù) = 12 + 5 + 5 private val timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits // 序列號(hào)的掩碼,十進(jìn)制數(shù)為4095 private val sequenceMask = -1L ^ (-1L << sequenceBits) // 初始化上一個(gè)時(shí)間戳快照值為-1 private var lastTimestamp = -1L // 下面的代碼塊為參數(shù)校驗(yàn)和初始化日志打印,這里不做分析 if (workerId > maxWorkerId || workerId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("worker Id can't be greater than %d or less than 0".format(maxWorkerId)) } if (datacenterId > maxDatacenterId || datacenterId < 0) { exceptionCounter.incr(1) throw new IllegalArgumentException("datacenter Id can't be greater than %d or less than 0".format(maxDatacenterId)) } log.info("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId)
接著看算法的核心代碼邏輯:
// 同步方法,其實(shí)就是protected synchronized long nextId(){ ...... } protected[snowflake] def nextId(): Long = synchronized { // 獲取系統(tǒng)時(shí)間戳(毫秒) var timestamp = timeGen() // 高并發(fā)場(chǎng)景,同一毫秒內(nèi)生成多個(gè)ID if (lastTimestamp == timestamp) { // 確保sequence + 1之后不會(huì)溢出,最大值為4095,其實(shí)也就是保證1毫秒內(nèi)最多生成4096個(gè)ID值 sequence = (sequence + 1) & sequenceMask // 如果sequence溢出則變?yōu)?,說明1毫秒內(nèi)并發(fā)生成的ID數(shù)量超過了4096個(gè),這個(gè)時(shí)候同1毫秒的第4097個(gè)生成的ID必須等待下一毫秒 if (sequence == 0) { // 死循環(huán)等待下一個(gè)毫秒值,直到比lastTimestamp大 timestamp = tilNextMillis(lastTimestamp) } } else { // 低并發(fā)場(chǎng)景,不同毫秒中生成ID // 不同毫秒的情況下,由于外層方法保證了timestamp大于或者小于lastTimestamp,而小于的情況是發(fā)生了時(shí)鐘回?fù)?,下面?huì)拋出異常,所以不用考慮 // 也就是只需要考慮一種情況:timestamp > lastTimestamp,也就是當(dāng)前生成的ID所在的毫秒數(shù)比上一個(gè)ID大 // 所以如果時(shí)間戳部分增大,可以確定整數(shù)值一定變大,所以序列號(hào)其實(shí)可以不用計(jì)算,這里直接賦值為0 sequence = 0 } // 獲取到的時(shí)間戳比上一個(gè)保存的時(shí)間戳小,說明時(shí)鐘回?fù)?,這種情況下直接拋出異常,拒絕生成ID // 個(gè)人認(rèn)為,這個(gè)方法應(yīng)該可以提前到var timestamp = timeGen()這段代碼之后 if (timestamp < lastTimestamp) { exceptionCounter.incr(1) log.error("clock is moving backwards. Rejecting requests until %d.", lastTimestamp); throw new InvalidSystemClock("Clock moved backwards. Refusing to generate id for %d milliseconds".format(lastTimestamp - timestamp)); } // lastTimestamp保存當(dāng)前時(shí)間戳,作為方法下次被調(diào)用的上一個(gè)時(shí)間戳的快照 lastTimestamp = timestamp // 度量統(tǒng)計(jì),生成的ID計(jì)數(shù)器加1 genCounter.incr() // X = (系統(tǒng)時(shí)間戳 - 自定義的紀(jì)元值) 然后左移22位 // Y = (數(shù)據(jù)中心ID左移17位) // Z = (機(jī)器ID左移12位) // 最后ID = X | Y | Z | 計(jì)算出來的序列號(hào)sequence ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence } // 輔助方法:獲取系統(tǒng)當(dāng)前的時(shí)間戳(毫秒) protected def timeGen(): Long = System.currentTimeMillis() // 輔助方法:獲取系統(tǒng)當(dāng)前的時(shí)間戳(毫秒),用死循環(huán)保證比傳入的lastTimestamp大,也就是獲取下一個(gè)比lastTimestamp大的毫秒數(shù) protected def tilNextMillis(lastTimestamp: Long): Long = { var timestamp = timeGen() while (timestamp <= lastTimestamp) { timestamp = timeGen() } timestamp }
最后一段邏輯的位操作比較多,但是如果熟練使用位運(yùn)算操作符,其實(shí)邏輯并不復(fù)雜,這里可以畫個(gè)圖推演一下:
四個(gè)部分的整數(shù)完成左移之后,由于空缺的低位都會(huì)補(bǔ)充了0
,基于按位或的特性,所有低位只要存在1
,那么對(duì)應(yīng)的位就會(huì)填充為1
,由于四個(gè)部分的位不會(huì)越界分配,所以這里的本質(zhì)就是:四個(gè)部分左移完畢后最終的數(shù)字進(jìn)行加法計(jì)算。
Snowflake
算法有幾個(gè)比較大的問題:
低并發(fā)場(chǎng)景會(huì)產(chǎn)生連續(xù)偶數(shù),原因是低并發(fā)場(chǎng)景系統(tǒng)時(shí)鐘總是走到下一個(gè)毫秒值,導(dǎo)致序列號(hào)重置為0
。
依賴系統(tǒng)時(shí)鐘,時(shí)鐘回?fù)軙?huì)拒絕生成新的ID
(直接拋出異常)。
Woker ID
和Data Center ID
的管理比較麻煩,特別是同一個(gè)服務(wù)的不同集群節(jié)點(diǎn)需要保證每個(gè)節(jié)點(diǎn)的Woker ID
和Data Center ID
組合唯一。
這三個(gè)問題美團(tuán)開源的Leaf
提供了解決思路,下圖截取自com.sankuai.inf.leaf.snowflake.SnowflakeIDGenImpl
:
對(duì)應(yīng)的解決思路是(不進(jìn)行深入的源碼分析,有興趣可以閱讀以下Leaf
的源碼):
序列號(hào)生成添加隨機(jī)源,會(huì)稍微減少同一個(gè)毫秒內(nèi)能產(chǎn)生的最大ID
數(shù)量。
時(shí)鐘回?fù)軇t進(jìn)行一定期限的等待。
使用Zookeeper
緩存和管理Woker ID
和Data Center ID
。
Woker ID
和Data Center ID
的配置是極其重要的,對(duì)于同一個(gè)服務(wù)(例如支付服務(wù))集群的多個(gè)節(jié)點(diǎn),必須配置不同的機(jī)器ID
和數(shù)據(jù)中心ID
或者同樣的數(shù)據(jù)中心ID
和不同的機(jī)器ID
(簡(jiǎn)單說就是確保Woker ID
和Data Center ID
的組合全局唯一),否則在高并發(fā)的場(chǎng)景下,在系統(tǒng)時(shí)鐘一致的情況下,很容易在多個(gè)節(jié)點(diǎn)產(chǎn)生相同的ID
值,所以一般的部署架構(gòu)如下:
管理這兩個(gè)ID
的方式有很多種,或者像Leaf
這樣的開源框架引入分布式緩存進(jìn)行管理,再如筆者所在的創(chuàng)業(yè)小團(tuán)隊(duì)生產(chǎn)服務(wù)比較少,直接把Woker ID
和Data Center ID
硬編碼在服務(wù)啟動(dòng)腳本中,然后把所有服務(wù)使用的Woker ID
和Data Center ID
統(tǒng)一登記在團(tuán)隊(duì)內(nèi)部知識(shí)庫(kù)中。
如果完全不考慮性能的話,也不考慮時(shí)鐘回?fù)?、序列?hào)生成等等問題,其實(shí)可以把Snowflake
的位運(yùn)算和異常處理部分全部去掉,使用Long.toBinaryString()
方法結(jié)合字符串按照Snowflake
算法思路拼接出64 bit
的二進(jìn)制數(shù),再通過Long.parseLong()
方法轉(zhuǎn)化為Long
類型。編寫一個(gè)main
方法如下:
public class Main { private static final String HIGH = "0"; /** * 2020-08-01 00:00:00 */ private static final long EPOCH = 1596211200000L; public static void main(String[] args) { long workerId = 1L; long dataCenterId = 1L; long seq = 4095; String timestampString = leftPadding(Long.toBinaryString(System.currentTimeMillis() - EPOCH), 41); String workerIdString = leftPadding(Long.toBinaryString(workerId), 5); String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5); String seqString = leftPadding(Long.toBinaryString(seq), 12); String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString; long num = Long.parseLong(value, 2); System.out.println(num); // 某個(gè)時(shí)刻輸出為3125927076831231 } private static String leftPadding(String value, int maxLength) { int diff = maxLength - value.length(); StringBuilder builder = new StringBuilder(); for (int i = 0; i < diff; i++) { builder.append("0"); } builder.append(value); return builder.toString(); } }
然后把代碼規(guī)范一下,編寫出一個(gè)簡(jiǎn)版Snowflake
算法實(shí)現(xiàn)的工程化代碼:
// 主鍵生成器接口 public interface PrimaryKeyGenerator { long generate(); } // 簡(jiǎn)易Snowflake實(shí)現(xiàn) public class SimpleSnowflake implements PrimaryKeyGenerator { private static final String HIGH = "0"; private static final long MAX_WORKER_ID = 31; private static final long MIN_WORKER_ID = 0; private static final long MAX_DC_ID = 31; private static final long MIN_DC_ID = 0; private static final long MAX_SEQUENCE = 4095; /** * 機(jī)器ID */ private final long workerId; /** * 數(shù)據(jù)中心ID */ private final long dataCenterId; /** * 基準(zhǔn)紀(jì)元值 */ private final long epoch; private long sequence = 0L; private long lastTimestamp = -1L; public SimpleSnowflake(long workerId, long dataCenterId, long epoch) { this.workerId = workerId; this.dataCenterId = dataCenterId; this.epoch = epoch; checkArgs(); } private void checkArgs() { if (!(MIN_WORKER_ID <= workerId && workerId <= MAX_WORKER_ID)) { throw new IllegalArgumentException("Worker id must be in [0,31]"); } if (!(MIN_DC_ID <= dataCenterId && dataCenterId <= MAX_DC_ID)) { throw new IllegalArgumentException("Data center id must be in [0,31]"); } } @Override public synchronized long generate() { long timestamp = System.currentTimeMillis(); // 時(shí)鐘回?fù)? if (timestamp < lastTimestamp) { throw new IllegalStateException("Clock moved backwards"); } // 同一毫秒內(nèi)并發(fā) if (lastTimestamp == timestamp) { sequence = sequence + 1; if (sequence == MAX_SEQUENCE) { timestamp = untilNextMillis(lastTimestamp); sequence = 0L; } } else { // 下一毫秒重置sequence為0 sequence = 0L; } lastTimestamp = timestamp; // 41位時(shí)間戳字符串,不夠位數(shù)左邊補(bǔ)"0" String timestampString = leftPadding(Long.toBinaryString(timestamp - epoch), 41); // 5位機(jī)器ID字符串,不夠位數(shù)左邊補(bǔ)"0" String workerIdString = leftPadding(Long.toBinaryString(workerId), 5); // 5位數(shù)據(jù)中心ID字符串,不夠位數(shù)左邊補(bǔ)"0" String dataCenterIdString = leftPadding(Long.toBinaryString(dataCenterId), 5); // 12位序列號(hào)字符串,不夠位數(shù)左邊補(bǔ)"0" String seqString = leftPadding(Long.toBinaryString(sequence), 12); String value = HIGH + timestampString + workerIdString + dataCenterIdString + seqString; return Long.parseLong(value, 2); } private long untilNextMillis(long lastTimestamp) { long timestamp; do { timestamp = System.currentTimeMillis(); } while (timestamp <= lastTimestamp); return timestamp; } private static String leftPadding(String value, int maxLength) { int diff = maxLength - value.length(); StringBuilder builder = new StringBuilder(); for (int i = 0; i < diff; i++) { builder.append("0"); } builder.append(value); return builder.toString(); } public static void main(String[] args) { long epoch = LocalDateTime.of(1970, 1, 1, 0, 0, 0, 0) .toInstant(ZoneOffset.of("+8")).toEpochMilli(); PrimaryKeyGenerator generator = new SimpleSnowflake(1L, 1L, epoch); for (int i = 0; i < 5; i++) { System.out.println(String.format("第%s個(gè)生成的ID: %d", i + 1, generator.generate())); } } } // 某個(gè)時(shí)刻輸出如下 第1個(gè)生成的ID: 6698247966366502912 第2個(gè)生成的ID: 6698248027448152064 第3個(gè)生成的ID: 6698248032162549760 第4個(gè)生成的ID: 6698248033076908032 第5個(gè)生成的ID: 6698248033827688448
通過字符串拼接的寫法雖然運(yùn)行效率低,但是可讀性會(huì)比較高,工程化處理后的代碼可以在實(shí)例化時(shí)候直接指定Worker ID
和Data Center ID
等值,并且這個(gè)簡(jiǎn)易的Snowflake
實(shí)現(xiàn)沒有第三方庫(kù)依賴,拷貝下來可以直接運(yùn)行。上面的方法使用字符串拼接看起來比較低端,其實(shí)最后那部分的按位或,可以完全轉(zhuǎn)化為加法:
public class Main { /** * 2020-08-01 00:00:00 */ private static final long EPOCH = 1596211200000L; public static void main(String[] args) { long workerId = 1L; long dataCenterId = 1L; long seq = 4095; long timestampDiff = System.currentTimeMillis() - EPOCH; long num = (long) (timestampDiff * Math.pow(2, 22)) + (long) (dataCenterId * Math.pow(2, 17)) + (long) (workerId * Math.pow(2, 12)) + seq; System.out.println(num); // 某個(gè)時(shí)刻輸出為3248473482862591 } }
這樣看起來整個(gè)算法都變得簡(jiǎn)單,不過這里涉及到指數(shù)運(yùn)算和加法運(yùn)算,效率會(huì)比較低。
感謝各位的閱讀,以上就是“Snowflake算法的實(shí)現(xiàn)原理”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對(duì)Snowflake算法的實(shí)現(xiàn)原理這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。