常見分布式全局唯一ID生成策略及算法的對(duì)比
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
? 作者?|??長(zhǎng)河
來(lái)源 |? urlify.cn/bMzqUj
66套java從入門到精通實(shí)戰(zhàn)課程分享
簡(jiǎn)單分析一下需求 [1]
全局唯一
趨勢(shì)有序
常見生成策略的優(yōu)缺點(diǎn)對(duì)比 [2]
此方法使用數(shù)據(jù)庫(kù)原有的功能，所以相對(duì)簡(jiǎn)單
能夠保證唯一性
能夠保證遞增性
id 之間的步長(zhǎng)是固定且可自定義的
可用性難以保證：數(shù)據(jù)庫(kù)常見架構(gòu)是 一主多從 + 讀寫分離，生成自增ID是寫請(qǐng)求?主庫(kù)掛了就玩不轉(zhuǎn)了
擴(kuò)展性差，性能有上限：因?yàn)閷懭胧菃吸c(diǎn)，數(shù)據(jù)庫(kù)主庫(kù)的寫性能決定ID的生成性能上限，并且?難以擴(kuò)展
冗余主庫(kù)，避免寫入單點(diǎn)
數(shù)據(jù)水平切分，保證各主庫(kù)生成的ID不重復(fù)
如上圖所述，由1個(gè)寫庫(kù)變成3個(gè)寫庫(kù)，每個(gè)寫庫(kù)設(shè)置不同的 auto_increment 初始值，以及相同的增長(zhǎng)步長(zhǎng)，以保證每個(gè)數(shù)據(jù)庫(kù)生成的ID是不同的（上圖中DB 01生成0,3,6,9…，DB 02生成1,4,7,10，DB 03生成2,5,8,11…）
喪失了ID生成的“絕對(duì)遞增性”：先訪問DB 01生成0,3，再訪問DB 02生成1，可能導(dǎo)致在非常短的時(shí)間內(nèi)，ID生成不是絕對(duì)遞增的（這個(gè)問題不大，目標(biāo)是趨勢(shì)遞增，不是絕對(duì)遞增
數(shù)據(jù)庫(kù)的寫壓力依然很大，每次生成ID都要訪問數(shù)據(jù)庫(kù)
保證了ID生成的絕對(duì)遞增有序
大大的降低了數(shù)據(jù)庫(kù)的壓力，ID生成可以做到每秒生成幾萬(wàn)幾十萬(wàn)個(gè)
服務(wù)仍然是單點(diǎn)
如果服務(wù)掛了，服務(wù)重啟起來(lái)之后，繼續(xù)生成ID可能會(huì)不連續(xù)，中間出現(xiàn)空洞（服務(wù)內(nèi)存是保存著0,1,2,3,4，數(shù)據(jù)庫(kù)中max-id是4，分配到3時(shí)，服務(wù)重啟了，下次會(huì)從5開始分配，3和4就成了空洞，不過這個(gè)問題也不大）
雖然每秒可以生成幾萬(wàn)幾十萬(wàn)個(gè)ID，但畢竟還是有性能上限，無(wú)法進(jìn)行水平擴(kuò)展
本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
擴(kuò)展性好，基本可以認(rèn)為沒有性能上限
無(wú)法保證趨勢(shì)遞增
uuid過長(zhǎng)，往往用字符串表示，作為主鍵建立索引查詢效率低，常見優(yōu)化方案為“轉(zhuǎn)化為兩個(gè)uint64整數(shù)存儲(chǔ)”或者“折半存儲(chǔ)”（折半后不能保證唯一性）
本地生成ID，不需要進(jìn)行遠(yuǎn)程調(diào)用，時(shí)延低
生成的ID趨勢(shì)遞增
生成的ID是整數(shù)，建立索引后查詢效率高
如果并發(fā)量超過1000，會(huì)生成重復(fù)的ID
依賴于數(shù)據(jù)庫(kù)，靈活方便，且性能優(yōu)于數(shù)據(jù)庫(kù)。
數(shù)字ID天然排序，對(duì)分頁(yè)或者需要排序的結(jié)果很有幫助。
如果系統(tǒng)中沒有Redis，還需要引入新的組件，增加系統(tǒng)復(fù)雜度。
需要編碼和配置的工作量比較大。
41 bit 作為毫秒數(shù) -?41位的長(zhǎng)度可以使用69年
10 bit 作為機(jī)器編號(hào) （5個(gè)bit是數(shù)據(jù)中心，5個(gè)bit的機(jī)器ID） -?10位的長(zhǎng)度最多支持部署1024個(gè)節(jié)點(diǎn)
算法單機(jī)每秒內(nèi)理論上最多可以生成1000*(2^12)，也就是400W的ID，完全能滿足業(yè)務(wù)的需求。
package?com;
?
public?class?SnowflakeIdGenerator?{
????//================================================Algorithm's?Parameter=============================================
????//?系統(tǒng)開始時(shí)間截?(UTC?2017-06-28?00:00:00)
????private?final?long?startTime?=?1498608000000L;
????//?機(jī)器id所占的位數(shù)
????private?final?long?workerIdBits?=?5L;
????//?數(shù)據(jù)標(biāo)識(shí)id所占的位數(shù)
????private?final?long?dataCenterIdBits?=?5L;
????//?支持的最大機(jī)器id(十進(jìn)制)，結(jié)果是31?(這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù))
????//?-1L?左移?5位?(worker?id?所占位數(shù))?即?5位二進(jìn)制所能獲得的最大十進(jìn)制數(shù)?-?31
????private?final?long?maxWorkerId?=?-1L?^?(-1L?<????//?支持的最大數(shù)據(jù)標(biāo)識(shí)id?-?31
????private?final?long?maxDataCenterId?=?-1L?^?(-1L?<????//?序列在id中占的位數(shù)
????private?final?long?sequenceBits?=?12L;
????//?機(jī)器ID?左移位數(shù)?-?12?(即末?sequence?所占用的位數(shù))
????private?final?long?workerIdMoveBits?=?sequenceBits;
????//?數(shù)據(jù)標(biāo)識(shí)id?左移位數(shù)?-?17(12+5)
????private?final?long?dataCenterIdMoveBits?=?sequenceBits?+?workerIdBits;
????//?時(shí)間截向?左移位數(shù)?-?22(5+5+12)
????private?final?long?timestampMoveBits?=?sequenceBits?+?workerIdBits?+?dataCenterIdBits;
????//?生成序列的掩碼(12位所對(duì)應(yīng)的最大整數(shù)值)，這里為4095?(0b111111111111=0xfff=4095)
????private?final?long?sequenceMask?=?-1L?^?(-1L?<????//=================================================Works's?Parameter================================================
????/**
?????*?工作機(jī)器ID(0~31)
?????*/
????private?long?workerId;
????/**
?????*?數(shù)據(jù)中心ID(0~31)
?????*/
????private?long?dataCenterId;
????/**
?????*?毫秒內(nèi)序列(0~4095)
?????*/
????private?long?sequence?=?0L;
????/**
?????*?上次生成ID的時(shí)間截
?????*/
????private?long?lastTimestamp?=?-1L;
????//===============================================Constructors=======================================================
????/**
?????*?構(gòu)造函數(shù)
?????*
?????*?@param?workerId?????工作ID?(0~31)
?????*?@param?dataCenterId?數(shù)據(jù)中心ID?(0~31)
?????*/
????public?SnowflakeIdGenerator(long?workerId,?long?dataCenterId)?{
????????if?(workerId?>?maxWorkerId?||?workerId?????????????throw?new?IllegalArgumentException(String.format("Worker?Id?can't?be?greater?than?%d?or?less?than?0",?maxWorkerId));
????????}
????????if?(dataCenterId?>?maxDataCenterId?||?dataCenterId?????????????throw?new?IllegalArgumentException(String.format("DataCenter?Id?can't?be?greater?than?%d?or?less?than?0",?maxDataCenterId));
????????}
????????this.workerId?=?workerId;
????????this.dataCenterId?=?dataCenterId;
????}
????//?==================================================Methods========================================================
????//?線程安全的獲得下一個(gè)?ID?的方法
????public?synchronized?long?nextId()?{
????????long?timestamp?=?currentTime();
????????//如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳:?說(shuō)明系統(tǒng)時(shí)鐘回退過?-?這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
????????if?(timestamp?????????????throw?new?RuntimeException(
????????????????????String.format("Clock?moved?backwards.??Refusing?to?generate?id?for?%d?milliseconds",?lastTimestamp?-?timestamp));
????????}
????????//如果是同一時(shí)間生成的，則進(jìn)行毫秒內(nèi)序列
????????if?(lastTimestamp?==?timestamp)?{
????????????sequence?=?(sequence?+?1)?&?sequenceMask;
????????????//毫秒內(nèi)序列溢出?即?序列?>?4095
????????????if?(sequence?==?0)?{
????????????????//阻塞到下一個(gè)毫秒,獲得新的時(shí)間戳
????????????????timestamp?=?blockTillNextMillis(lastTimestamp);
????????????}
????????}
????????//時(shí)間戳改變，毫秒內(nèi)序列重置
????????else?{
????????????sequence?=?0L;
????????}
????????//上次生成ID的時(shí)間截
????????lastTimestamp?=?timestamp;
????????//移位并通過或運(yùn)算拼到一起組成64位的ID
????????return?((timestamp?-?startTime)?<????????????????|?(dataCenterId?<????????????????|?(workerId?<????????????????|?sequence;
????}
????//?阻塞到下一個(gè)毫秒?即?直到獲得新的時(shí)間戳
????protected?long?blockTillNextMillis(long?lastTimestamp)?{
????????long?timestamp?=?currentTime();
????????while?(timestamp?<=?lastTimestamp)?{
????????????timestamp?=?currentTime();
????????}
????????return?timestamp;
????}
????//?獲得以毫秒為單位的當(dāng)前時(shí)間
????protected?long?currentTime()?{
????????return?System.currentTimeMillis();
????}
????//====================================================Test?Case=====================================================
????public?static?void?main(String[]?args)?{
????????SnowflakeIdGenerator?idWorker?=?new?SnowflakeIdGenerator(0,?0);
????????for?(int?i?=?0;?i?????????????long?id?=?idWorker.nextId();
????????????//System.out.println(Long.toBinaryString(id));
????????????System.out.println(id);
????????}
????}
粉絲福利：Java從入門到入土學(xué)習(xí)路線圖
???
?長(zhǎng)按上方微信二維碼?2 秒
感謝點(diǎn)贊支持下哈?