分布式雪花算法獲取id
點擊上方藍色字體，選擇“標(biāo)星公眾號”
優(yōu)質(zhì)文章，第一時間送達
? 作者?|??MXC肖某某?
來源 |? urlify.cn/zEB7Vn
正文
實現(xiàn)全局唯一ID
一、采用主鍵自增
最常見的方式。利用數(shù)據(jù)庫，全數(shù)據(jù)庫唯一。
優(yōu)點：
1）簡單，代碼方便，性能可以接受。
2）數(shù)字ID天然排序，對分頁或者需要排序的結(jié)果很有幫助。
缺點：
1）不同數(shù)據(jù)庫語法和實現(xiàn)不同，數(shù)據(jù)庫遷移的時候或多數(shù)據(jù)庫版本支持的時候需要處理。
2）在單個數(shù)據(jù)庫或讀寫分離或一主多從的情況下，只有一個主庫可以生成。有單點故障的風(fēng)險。
3）在性能達不到要求的情況下，比較難于擴展。
4）如果遇見多個系統(tǒng)需要合并或者涉及到數(shù)據(jù)遷移會相當(dāng)痛苦。
5）分表分庫的時候會有麻煩。
二、UUID
常見的方式。可以利用數(shù)據(jù)庫也可以利用程序生成，一般來說全球唯一。
優(yōu)點：
1）簡單，代碼方便。
2）生成ID性能非常好，基本不會有性能問題。
3）全球唯一，在遇見數(shù)據(jù)遷移，系統(tǒng)數(shù)據(jù)合并，或者數(shù)據(jù)庫變更等情況下，可以從容應(yīng)對。
缺點：
1）沒有排序，無法保證趨勢遞增。
2）UUID往往是使用字符串存儲，查詢的效率比較低。
3）存儲空間比較大，如果是海量數(shù)據(jù)庫，就需要考慮存儲量的問題。
4）傳輸數(shù)據(jù)量大
5）插入數(shù)據(jù)慢，因為mysql采用的B+tree的結(jié)構(gòu)來存儲索引，假如是數(shù)據(jù)庫自帶的那種主鍵自增，節(jié)點滿了，會裂變出新的節(jié)點，新節(jié)點滿了，再去裂變新的節(jié)點，這樣利用率和效率都很高。而UUID是無序的，會造成中間節(jié)點的分裂，也會造成不飽和的節(jié)點，插入的效率自然就比較低下了。
三、Redis生成ID
當(dāng)使用數(shù)據(jù)庫來生成ID性能不夠要求的時候，我們可以嘗試使用Redis來生成ID。這主要依賴于Redis是單線程的，所以也可以用生成全局唯一的ID。可以用Redis的原子操作 INCR和INCRBY來實現(xiàn)。可以使用Redis集群來獲取更高的吞吐量。假如一個集群中有5臺Redis。可以初始化每臺Redis的值分別是1,2,3,4,5，然后步長都是5。各個Redis生成的ID為：
A：1,6,11,16,21
B：2,7,12,17,22
C：3,8,13,18,23
D：4,9,14,19,24
E：5,10,15,20,25
這個，隨便負載到哪個機確定好，未來很難做修改。但是3-5臺服務(wù)器基本能夠滿足器上，都可以獲得不同的ID。但是步長和初始值一定需要事先需要了。使用Redis集群也可以方式單點故障的問題。另外，比較適合使用Redis來生成每天從0開始的流水號。比如訂單號=日期+當(dāng)日自增長號。可以每天在Redis中生成一個Key，使用INCR進行累加。
優(yōu)點：
1）不依賴于數(shù)據(jù)庫，靈活方便，且性能優(yōu)于數(shù)據(jù)庫。
2）數(shù)字ID天然排序，對分頁或者需要排序的結(jié)果很有幫助。
缺點：
1）如果系統(tǒng)中沒有Redis，還需要引入新的組件，增加系統(tǒng)復(fù)雜度。
2）需要編碼和配置的工作量比較大。
四、雪花算法 (snowflake，Java版)
SnowFlake算法生成id的結(jié)果是一個64bit大小的整數(shù)，它的結(jié)構(gòu)如下圖：
??
1位，不用。二進制中最高位為1的都是負數(shù)，但是我們生成的id一般都使用整數(shù)，所以這個最高位固定是0
41位，用來記錄時間戳（毫秒）。
41位可以表示$2^{41}-1$個數(shù)字，
如果只用來表示正整數(shù)（計算機中正數(shù)包含0），可以表示的數(shù)值范圍是：0 至 $2^{41}-1$，減1是因為可表示的數(shù)值范圍是從0開始算的，而不是1。
也就是說41位可以表示$2^{41}-1$個毫秒的值，轉(zhuǎn)化成單位年則是$(2^{41}-1) / (1000 * 60 * 60 * 24 * 365) = 69$年
10位，用來記錄工作機器id。
可以部署在$2^{10} = 1024$個節(jié)點，包括5位datacenterId和5位workerId
5位（bit）可以表示的最大正整數(shù)是$2^{5}-1 = 31$，即可以用0、1、2、3、....31這32個數(shù)字，來表示不同的datecenterId或workerId
12位，序列號，用來記錄同毫秒內(nèi)產(chǎn)生的不同id。
12位（bit）可以表示的最大正整數(shù)是$2^{12}-1 = 4095$，即可以用0、1、2、3、....4094這4095個數(shù)字，來表示同一機器同一時間截（毫秒)內(nèi)產(chǎn)生的4095個ID序號
由于在Java中64bit的整數(shù)是long類型，所以在Java中SnowFlake算法生成的id就是long(18位)來存儲的。
優(yōu)點：
1)所有生成的id按時間趨勢遞增
2)整個分布式系統(tǒng)內(nèi)不會產(chǎn)生重復(fù)id（因為有datacenterId和workerId來做區(qū)分）
3)不依賴于其他系統(tǒng)，可直接編寫
缺點：
1）時鐘回撥:最常見的問題就是時鐘回撥導(dǎo)致的ID重復(fù)問題，在SnowFlake算法中并沒有什么有效的解法，僅是拋出異常。時鐘回撥涉及兩種情況①實例停機→時鐘回撥→實例重啟→計算ID ②實例運行中→時鐘回撥→計算ID
2）手動配置:另一個就是workerId（機器ID）是需要部署時手動配置，而workerId又不能重復(fù)。幾臺實例還好，一旦實例達到一定量級，管理workerId將是一個復(fù)雜的操作。
美團的Leaf和百度的UidGenerator有相應(yīng)的解決方案
以下是Twitter官方原版的，用Scala寫的：
/**?Copyright?2010-2012?Twitter,?Inc.*/
package?com.twitter.service.snowflake
import?com.twitter.ostrich.stats.Stats
import?com.twitter.service.snowflake.gen._
import?java.util.Random
import?com.twitter.logging.Logger
/**
?*?An?object?that?generates?IDs.
?*?This?is?broken?into?a?separate?class?in?case
?*?we?ever?want?to?support?multiple?worker?threads
?*?per?process
?*/
class?IdWorker(val?workerId:?Long,?val?datacenterId:?Long,?private?val?reporter:?Reporter,?var?sequence:?Long?=?0L)
extends?Snowflake.Iface?{
??private[this]?def?genCounter(agent:?String)?=?{
????Stats.incr("ids_generated")
????Stats.incr("ids_generated_%s".format(agent))
??}
??private[this]?val?exceptionCounter?=?Stats.getCounter("exceptions")
??private[this]?val?log?=?Logger.get
??private[this]?val?rand?=?new?Random
??val?twepoch?=?1288834974657L
??private[this]?val?workerIdBits?=?5L
??private[this]?val?datacenterIdBits?=?5L
??private[this]?val?maxWorkerId?=?-1L?^?(-1L?<??private[this]?val?maxDatacenterId?=?-1L?^?(-1L?<??private[this]?val?sequenceBits?=?12L
??private[this]?val?workerIdShift?=?sequenceBits
??private[this]?val?datacenterIdShift?=?sequenceBits?+?workerIdBits
??private[this]?val?timestampLeftShift?=?sequenceBits?+?workerIdBits?+?datacenterIdBits
??private[this]?val?sequenceMask?=?-1L?^?(-1L?<
??private[this]?var?lastTimestamp?=?-1L
??//?sanity?check?for?workerId
??if?(workerId?>?maxWorkerId?||?workerId?????exceptionCounter.incr(1)
????throw?new?IllegalArgumentException("worker?Id?can't?be?greater?than?%d?or?less?than?0".format(maxWorkerId))
??}
??if?(datacenterId?>?maxDatacenterId?||?datacenterId?????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)
??def?get_id(useragent:?String):?Long?=?{
????if?(!validUseragent(useragent))?{
??????exceptionCounter.incr(1)
??????throw?new?InvalidUserAgentError
????}
????val?id?=?nextId()
????genCounter(useragent)
????reporter.report(new?AuditLogEntry(id,?useragent,?rand.nextLong))
????id
??}
??def?get_worker_id():?Long?=?workerId
??def?get_datacenter_id():?Long?=?datacenterId
??def?get_timestamp()?=?System.currentTimeMillis
??protected[snowflake]?def?nextId():?Long?=?synchronized?{
????var?timestamp?=?timeGen()
????if?(timestamp???????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))
????}
????if?(lastTimestamp?==?timestamp)?{
??????sequence?=?(sequence?+?1)?&?sequenceMask
??????if?(sequence?==?0)?{
????????timestamp?=?tilNextMillis(lastTimestamp)
??????}
????}?else?{
??????sequence?=?0
????}
????lastTimestamp?=?timestamp
????((timestamp?-?twepoch)?<??????(datacenterId?<??????(workerId?<??????sequence
??}
??protected?def?tilNextMillis(lastTimestamp:?Long):?Long?=?{
????var?timestamp?=?timeGen()
????while?(timestamp?<=?lastTimestamp)?{
??????timestamp?=?timeGen()
????}
????timestamp
??}
??protected?def?timeGen():?Long?=?System.currentTimeMillis()
??val?AgentParser?=?"""([a-zA-Z][a-zA-Z\-0-9]*)""".r
??def?validUseragent(useragent:?String):?Boolean?=?useragent?match?{
????case?AgentParser(_)?=>?true
????case?_?=>?false
??}
}
使用java:
public?class?SnowflakeIdWorker?{
????/**
?????*?開始時間截?(2015-01-01)
?????*/
????private?final?long?twepoch?=?1420041600000L;
????/**
?????*?機器id所占的位數(shù)
?????*/
????private?final?long?workerIdBits?=?5L;
????/**
?????*?數(shù)據(jù)標(biāo)識id所占的位數(shù)
?????*/
????private?final?long?datacenterIdBits?=?5L;
????/**
?????*?支持的最大機器id，結(jié)果是31?(這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù))
?????*/
????private?final?long?maxWorkerId?=?-1L?^?(-1L?<????/**
?????*?支持的最大數(shù)據(jù)標(biāo)識id，結(jié)果是31
?????*/
????private?final?long?maxDatacenterId?=?-1L?^?(-1L?<????/**
?????*?序列在id中占的位數(shù)
?????*/
????private?final?long?sequenceBits?=?12L;
????/**
?????*?機器ID向左移12位
?????*/
????private?final?long?workerIdShift?=?sequenceBits;
????/**
?????*?數(shù)據(jù)標(biāo)識id向左移17位(12+5)
?????*/
????private?final?long?datacenterIdShift?=?sequenceBits?+?workerIdBits;
????/**
?????*?時間截向左移22位(5+5+12)
?????*/
????private?final?long?timestampLeftShift?=?sequenceBits?+?workerIdBits?+?datacenterIdBits;
????/**
?????*?生成序列的掩碼，這里為4095?(0b111111111111=0xfff=4095)
?????*/
????private?final?long?sequenceMask?=?-1L?^?(-1L?<????/**
?????*?工作機器ID(0~31)
?????*/
????private?long?workerId;
????/**
?????*?數(shù)據(jù)中心ID(0~31)
?????*/
????private?long?datacenterId;
????/**
?????*?毫秒內(nèi)序列(0~4095)
?????*/
????private?long?sequence?=?0L;
????/**
?????*?上次生成ID的時間截
?????*/
????private?long?lastTimestamp?=?-1L;
????/**
?????*?構(gòu)造函數(shù)
?????*?@param?workerId?????工作ID?(0~31)
?????*?@param?datacenterId?數(shù)據(jù)中心ID?(0~31)
?????*/
????public?SnowflakeIdWorker(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;
????}
????/**
?????*?獲得下一個ID?(該方法是線程安全的)
?????*?@return?SnowflakeId
?????*/
????public?synchronized?long?nextId()?{
????????long?timestamp?=?timeGen();
????????//?如果當(dāng)前時間小于上一次ID生成的時間戳，說明系統(tǒng)時鐘回退過這個時候應(yīng)當(dāng)拋出異常
????????if?(timestamp?????????????throw?new?RuntimeException(
????????????????????String.format("Clock?moved?backwards.??Refusing?to?generate?id?for?%d?milliseconds",?lastTimestamp?-?timestamp));
????????}
????????//?如果是同一時間生成的，則進行毫秒內(nèi)序列
????????if?(lastTimestamp?==?timestamp)?{
????????????sequence?=?(sequence?+?1)?&?sequenceMask;
????????????//?毫秒內(nèi)序列溢出
????????????if?(sequence?==?0)?{
????????????????//阻塞到下一個毫秒,獲得新的時間戳
????????????????timestamp?=?tilNextMillis(lastTimestamp);
????????????}
????????}
????????//?時間戳改變，毫秒內(nèi)序列重置
????????else?{
????????????sequence?=?0L;
????????}
????????//?上次生成ID的時間截
????????lastTimestamp?=?timestamp;
????????//?移位并通過或運算拼到一起組成64位的ID
????????return?((timestamp?-?twepoch)?<????????????????|?(datacenterId?<????????????????|?(workerId?<????????????????|?sequence;
????}
????/**
?????*?阻塞到下一個毫秒，直到獲得新的時間戳
?????*?@param?lastTimestamp?上次生成ID的時間截
?????*?@return?當(dāng)前時間戳
?????*/
????protected?long?tilNextMillis(long?lastTimestamp)?{
????????long?timestamp?=?timeGen();
????????while?(timestamp?<=?lastTimestamp)?{
????????????timestamp?=?timeGen();
????????}
????????return?timestamp;
????}
????/**
?????*?返回以毫秒為單位的當(dāng)前時間
?????*?@return?當(dāng)前時間(毫秒)
?????*/
????protected?long?timeGen()?{
????????return?System.currentTimeMillis();
????}
????public?static?void?main(String[]?args)?throws?InterruptedException?{
????????SnowflakeIdWorker?idWorker?=?new?SnowflakeIdWorker(0,?0);
????????for?(int?i?=?0;?i?????????????long?id?=?idWorker.nextId();
????????????Thread.sleep(1);
????????????System.out.println(id);
????????}
????}
}
粉絲福利：實戰(zhàn)springboot+CAS單點登錄系統(tǒng)視頻教程免費領(lǐng)取
???
?長按上方微信二維碼?2 秒 即可獲取資料
感謝點贊支持下哈?