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

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

目前創(chuàng)新互聯(lián)公司已為超過(guò)千家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、綿陽(yáng)服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、溫嶺網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

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

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

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

什么是SnowFlakeID

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

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

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

0 - 0000000000 0000000000 0000000000 0000000000 0 - 0000000000 - 000000000000

第一段1位為未使用，永遠(yuǎn)固定為0

第二段41位為毫秒級(jí)時(shí)間(41位的長(zhǎng)度可以使用69年)

第三段10位為workerId(10位的長(zhǎng)度最多支持部署1024個(gè)節(jié)點(diǎn)）

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

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

算法的核心如下

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

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

SnowFlake有什么問(wèn)題

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

時(shí)鐘回?fù)?/strong>:最常見(jiàn)的問(wèn)題就是時(shí)鐘回?fù)軐?dǎo)致的ID重復(fù)問(wèn)題，在SnowFlake算法中并沒(méi)有什么有效的解法，僅是拋出異常。時(shí)鐘回?fù)苌婕皟煞N情況①實(shí)例停機(jī)→時(shí)鐘回?fù)堋鷮?shí)例重啟→計(jì)算ID ②實(shí)例運(yùn)行中→時(shí)鐘回?fù)堋?jì)算ID

手動(dòng)配置:另一個(gè)就是workerId（機(jī)器ID）是需要部署時(shí)手動(dòng)配置，而workerId又不能重復(fù)。幾臺(tái)實(shí)例還好，一旦實(shí)例達(dá)到一定量級(jí)，管理workerId將是一個(gè)復(fù)雜的操作。

如何優(yōu)化

時(shí)鐘回?fù)芨倪M(jìn)避免

ID生成器一旦不可用，可能造成所有數(shù)據(jù)庫(kù)相關(guān)新增業(yè)務(wù)都不可用，影響太大。所以時(shí)鐘回?fù)艿膯?wèn)題必須解決。

造成時(shí)鐘回?fù)艿脑蚨喾N多樣，可能是閏秒回?fù)埽赡苁荖TP同步，還可能是服務(wù)器時(shí)間手動(dòng)調(diào)整?？傊褪菚r(shí)間回到了過(guò)去。針對(duì)回退時(shí)間的多少可以進(jìn)行不同的策略改進(jìn)。一般有以下幾種方案：

1. 少量服務(wù)器部署ID生成器實(shí)例，關(guān)閉NTP服務(wù)器，嚴(yán)格管理服務(wù)器。這種方案不需要從代碼層面解決，完全人治。
2. 針對(duì)回退時(shí)間斷的情況，如閏秒回?fù)軆H回?fù)芰?s，可以在代碼層面通過(guò)判斷暫停一定時(shí)間內(nèi)的ID生成器使用。雖然少了幾秒鐘可用時(shí)間，但時(shí)鐘正常后，業(yè)務(wù)即可恢復(fù)正常。

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

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