理解Snowflake算法的實(shí)現(xiàn)原理
前提
Snowflake (雪花)是 Twitter 開(kāi)源的高性能 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)來(lái)運(yùn)行。
而 2010 年發(fā)布的初版 Snowflake 源碼是使用 Scala 語(yǔ)言編寫的，歸檔于 scala_28 分支。換言之， 大家目前使用的 Snowflake 算法原版或者改良版已經(jīng)是十年前(當(dāng)前是 2020 年)的產(chǎn)物，不得不說(shuō)這個(gè)算法確實(shí)比較厲害 。 scala_28 分支中有介紹該算法的動(dòng)機(jī)和要求，這里簡(jiǎn)單摘錄一下：
動(dòng)機(jī)：
- Cassandra 中沒(méi)有生成順序 ID 的工具， Twitter 由使用 MySQL 轉(zhuǎn)向使用 Cassandra 的時(shí)候需要一種新的方式來(lái)生成 ID (印證了架構(gòu)不是設(shè)計(jì)出來(lái)，而是基于業(yè)務(wù)場(chǎng)景迭代出來(lái))。
要求：
- 高性能：每秒每個(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方案簡(jiǎ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è)可以理解為原來(lái)的機(jī)器 ID )和 5 bit 的 Data Center ID (數(shù)據(jù)中心 ID )，詳情見(jiàn) IdWorker.scala ：
也就是說(shuō)，支持配置最多 32 個(gè)機(jī)器 ID 和最多 32 個(gè)數(shù)據(jù)中心 ID ：
由于算法是 Scala 語(yǔ)言編寫，是依賴于 JVM 的語(yǔ)言，返回的 ID 值為 Long 類型，也就是 64 bit 的整數(shù)，原來(lái)的算法生成序列中只使用了 63 bit 的長(zhǎng)度，要返回的是無(wú)符號(hào)數(shù)，所以在高位補(bǔ)一個(gè) 0 (占用 1 bit )，那么加起來(lái)整個(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í)間來(lái)源于系統(tǒng)時(shí)間戳，所以必須保證系統(tǒng)時(shí)間是向前遞進(jìn)，不能發(fā)生 時(shí)鐘回?fù)? (通說(shuō)來(lái)說(shuō)就是不能在同一個(gè)時(shí)刻產(chǎn)生多個(gè)相同的時(shí)間戳或者產(chǎn)生了過(guò)去的時(shí)間戳)。一旦發(fā)生時(shí)鐘回?fù)埽?Snowflake 會(huì)拒絕生成下一個(gè) ID 。
位運(yùn)算知識(shí)補(bǔ)充
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 沒(méi)有二義性。
簡(jiǎn)單來(lái)看就是這樣：
- * [+ 11] 原碼 = [0000 1011] 補(bǔ)碼 = [0000 1011]
- * [- 11] 原碼 = [1000 1011] 補(bǔ)碼 = [1111 0101]
- * [- 11]的補(bǔ)碼計(jì)算過(guò)程：
- 原碼 1000 1011
- 除了最高位其他位取反 1111 0100
- 加1 1111 0101 （補(bǔ)碼）
使用原碼、反碼在計(jì)算的時(shí)候得到的不一定是準(zhǔn)確的值，而使用補(bǔ)碼的時(shí)候計(jì)算結(jié)果才是正確的，記住這個(gè)結(jié)論即可，這里不在舉例。由于 Snowflake 的 ID 生成方案中，除了最高位，其他四個(gè)部分都是無(wú)符號(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é)果和原來(lái)的值一致。
- 兩數(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)左移
帶符號(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ù)超過(guò)了該類型的最大位數(shù)，那么編譯器會(huì)對(duì)移動(dòng)的位數(shù)取模，例如 int 移位 33 位，實(shí)際上只移動(dòng)了 33 % 2 = 1 位。
推演過(guò)程如下(假設(shè) n = 2 )：
- * [+ 11] 原碼 = [0000 1011] 補(bǔ)碼 = [0000 1011]
- * [- 11] 原碼 = [1000 1011] 補(bǔ)碼 = [1111 0101]
- * [+ 11 << 2]的計(jì)算過(guò)程
- 補(bǔ)碼 0000 1011
- 左移2位 0000 1011
- 舍高補(bǔ)低 0010 1100
- 十進(jìn)制數(shù) 2^2 + 2^3 + 2^5 = 44
- * [- 11 << 2]的計(jì)算過(guò)程
- 補(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ì)算過(guò)程如下：
- * [-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ì)算過(guò)程：
- * [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ì)超過(guò) N ，這是利用了按位與中的"取指定位"的特性。
Snowflake算法實(shí)現(xiàn)源碼分析
Snowflake 雖然用 Scala 語(yǔ)言編寫，語(yǔ)法其實(shí)和 Java 差不多，當(dāng)成 Java 代碼這樣閱讀就行，下面閱讀代碼的時(shí)候會(huì)跳過(guò)一些日志記錄和度量統(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)?，說(shuō)明1毫秒內(nèi)并發(fā)生成的ID數(shù)量超過(guò)了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í)間戳小，說(shuō)明時(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ì)算出來(lái)的序列號(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算法改良
Snowflake 算法有幾個(gè)比較大的問(wèn)題：
- 低并發(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è)問(wèn)題美團(tuán)開(kāi)源的 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)單說(shuō)就是確保 Woker ID 和 Data Center ID 的組合全局唯一 )，否則在高并發(fā)的場(chǎng)景下，在系統(tǒng)時(shí)鐘一致的情況下，很容易在多個(gè)節(jié)點(diǎn)產(chǎn)生相同的 ID 值，所以一般的部署架構(gòu)如下：
管理這兩個(gè) ID 的方式有很多種，或者像 Leaf 這樣的開(kāi)源框架引入分布式緩存進(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í)現(xiàn)簡(jiǎn)化版Snowflake
如果完全不考慮性能的話，也不考慮時(shí)鐘回?fù)堋⑿蛄刑?hào)生成等等問(wèn)題，其實(shí)可以把 Snowflake 的位運(yùn)算和異常處理部分全部去掉，使用 Long.toBinaryString() 方法結(jié)合字符串按照 Snowflake 算法思路拼接出 64 bit 的二進(jìn)制數(shù)，再通過(guò) 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ù)?nbsp;
- 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
通過(guò)字符串拼接的寫法雖然運(yùn)行效率低，但是可讀性會(huì)比較高，工程化處理后的代碼可以在實(shí)例化時(shí)候直接指定 Worker ID 和 Data Center ID 等值，并且這個(gè)簡(jiǎn)易的 Snowflake 實(shí)現(xiàn)沒(méi)有第三方庫(kù)依賴，拷貝下來(lái)可以直接運(yùn)行。上面的方法使用字符串拼接看起來(lái)比較低端，其實(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
- }
- }
這樣看起來(lái)整個(gè)算法都變得簡(jiǎn)單，不過(guò)這里涉及到指數(shù)運(yùn)算和加法運(yùn)算，效率會(huì)比較低。
小結(jié)
Snowflake 算法是以高性能為核心目標(biāo)的算法，基于這一點(diǎn)目的巧妙地大量使用位運(yùn)算，這篇文章已經(jīng)把 Snowflake 中應(yīng)用到的位運(yùn)算和具體源碼實(shí)現(xiàn)徹底分析清楚。最后，基于 Twitter 官方的 Snowflake 算法源碼，修訂出了一版 Java 實(shí)現(xiàn)版本，并且應(yīng)用前面提到的改良方式，修復(fù)了低并發(fā)場(chǎng)景下只產(chǎn)生偶數(shù)的問(wèn)題， 并且已經(jīng)應(yīng)用于生產(chǎn)環(huán)境一段時(shí)間 ，代碼倉(cāng)庫(kù)如下(代碼沒(méi)有任何第三方庫(kù)依賴，拷貝出來(lái)就直接可用)：
Github ： https://github.com/zjcscut/framework-mesh/tree/master/java-snowflake
