分布式SnowFlakeID（雪花ID）原理和改進優(yōu)化

最近在研究分布式框架的組件和整體設(shè)計思路。所有的問題，一旦涉及分布式難度就呈幾何倍數(shù)的提升。包括最常見的ID生成也是，單機情況下，使用數(shù)據(jù)庫自增ID、UUID都是簡單易行的選擇

但在分布式環(huán)境下，就需要考慮同業(yè)務(wù)部署多套以后，ID重復(fù)的問題。使用數(shù)據(jù)庫則數(shù)據(jù)庫容易成為瓶頸，使用UUID又沒有順序，數(shù)據(jù)庫集成又會遇到遞增步長等問題。最后，數(shù)據(jù)庫（也可使用redis）號段生成器和snowFlake就成為了目前分布式ID生成器的主流

我所知大部分互聯(lián)網(wǎng)公司的分布式ID生成器，其實都是一個網(wǎng)絡(luò)服務(wù)或集群，單獨部署。其他應(yīng)用程序通過網(wǎng)絡(luò)去獲取分布式的全局唯一ID。使用網(wǎng)絡(luò)服務(wù)的方式，好處顯而易見，就是方便集中管理，只要生成器設(shè)計的沒問題，基本ID就能保證整體趨勢是遞增的。壞處就是獲取效率被明顯降低了

另外針對我司來說，由于項目的性質(zhì)，采用分布式ID生成器，對開發(fā)和上線部署及其后期的運維都會帶來一定的麻煩。畢竟上線后，項目的管理權(quán)就不在我們手上了，所以為了保證分布式ID生成器的穩(wěn)定性，盡量不采取分布式ID生成中心的策略。于是，留給我的選擇就只剩下了SnowFlakeID（雪花ID）了。

什么是SnowFlakeID

SnowFlake是twitter公司內(nèi)部分布式項目采用的ID生成算法，開源后廣受國內(nèi)大廠的好評。由這種算法生成的ID，我們就叫做SnowFlakeID

SnowFlakeID的最大的特性就是天然去中心化，通過時間戳、工作機器編號兩個變量進行配置后，通過SnowFlake算法會生成唯一的遞增ID。在任何機器上，只要保證工作機器編號不同，就可以確保生成的ID唯一，且整體趨勢是遞增的

Snowflake的結(jié)構(gòu)如下(每部分用-分開):

0 - 0000000000 0000000000 0000000000 0000000000 0 - 0000000000 - 000000000000

第一段1位為未使用，永遠固定為0

第二段41位為毫秒級時間(41位的長度可以使用69年)

第三段10位為workerId(10位的長度最多支持部署1024個節(jié)點）

第三段12位為毫秒內(nèi)的計數(shù)（12位的計數(shù)順序號支持每個節(jié)點每毫秒產(chǎn)生4096個ID序號）

如果按照1024的滿節(jié)點（1個節(jié)點就是1個部署的服務(wù)）計算，每毫秒可生成的ID序號有1024*4096=4194304個，足以滿足現(xiàn)在絕大多數(shù)的業(yè)務(wù)情況

算法的核心如下

 ((當(dāng)前時間 - 服務(wù)時間) << timestampLeftShift) 
        | (機器ID << workerIdShift) 
        | sequence;

服務(wù)時間指的是服務(wù)的開發(fā)時間，即第一個正式ID產(chǎn)生的時間。由于SnowFlakeID最長可用69年（因為只有41個bit，41個bit的最大值換算成年就是69年）。所以服務(wù)時間越貼近上線時間，則該算法可用時間越長。
其中sequence為遞增序列，當(dāng)前時間戳和上一ID生成時間戳一致時，sequence就遞增1，直到4096為止。

SnowFlake有什么問題

SnowFlake很好，分布式、去中心化、無第三方依賴。但它并不是完美的，由于SnowFlake強依賴時間戳，所以時間的變動會造成SnowFlake的算法產(chǎn)生錯誤。

時鐘回?fù)?/strong>:最常見的問題就是時鐘回?fù)軐?dǎo)致的ID重復(fù)問題，在SnowFlake算法中并沒有什么有效的解法，僅是拋出異常。時鐘回?fù)苌婕皟煞N情況①實例停機→時鐘回?fù)堋鷮嵗貑ⅰ嬎鉏D ②實例運行中→時鐘回?fù)堋嬎鉏D

if (refusedSeconds <= 5) {
    try {
    //時間偏差大小小于5ms，則等待兩倍時間
        wait(refusedSeconds << 1);//wait
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    currentSecond = getCurrentSecond();
}else {//時鐘回?fù)茌^大
    //用其他策略修復(fù)時鐘問題
}

 List<Long> uidList = uidProvider.provide(lastSecond.incrementAndGet());