一、問題

為什么需要分布式全局唯一ID以及分布式ID的業(yè)務(wù)需求

在復(fù)雜分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)和消息進行唯一標(biāo)識

如在美團點評的金融、支付、餐飲、酒店;

貓眼電影等產(chǎn)品的系統(tǒng)中數(shù)據(jù)日漸增長，對數(shù)據(jù)分庫分表后需要有一個唯一ID來標(biāo)識一條數(shù)據(jù)或消息;

特別一點的如訂單、騎手、優(yōu)惠券也都需要有唯一ID做標(biāo)識。

此時一個能夠生成全局唯一ID的系統(tǒng)是非常必要的

ID生成規(guī)則部分硬性要求

①全局唯一

即不能出現(xiàn)重復(fù)ID號

②趨勢遞增

在Mysql的InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用的是BTree的數(shù)據(jù)結(jié)構(gòu)作為存儲索引數(shù)據(jù)，在主鍵的選擇上我們應(yīng)該盡量使用有序的主鍵保證寫入性能

③單調(diào)遞增

保證下一個ID一定大于上一個ID，如事務(wù)版本號、排序等特殊要求

④信息安全

如果ID是連續(xù)的，惡意用戶的扒取工作就非常容易做了，直接按照順序下載指定URL即可:如果是訂單號就更危險了，競對可以直接知道我們一天的單量。所以在一些應(yīng)用場景下，需要ID無規(guī)則不規(guī)則，讓競爭對手不好猜

⑤含時間戳

在開發(fā)中能快速了解這個分布式id生成的時間

ID號生成系統(tǒng)的可用性要求

①高可用

發(fā)一個獲取分布式ID的請求，服務(wù)器要保證99.999%的情況下能給我返回一個分布式ID

②低延遲

返回的速度要快

③高QPS（抵抗高訪問）

比如一秒內(nèi)10萬個，需要服務(wù)器能抵抗住并且生成10萬個分布式ID

二、一般通用方案

（一）UUID

jdk自帶，生成36位字符，形式為8-4-4-4-12，包含4個連號－，對于單體式僅需滿足唯一的話可以使用

好處：性能高，本地生成，無網(wǎng)絡(luò)消耗

壞處：無序且字符串長，存入數(shù)據(jù)庫會增大數(shù)據(jù)庫壓力，入數(shù)據(jù)庫性能差。mysql官方推薦主鍵越短越好

索引， B+樹索引的分裂

既然分布式id是主鍵，然后主鍵是包含索引的，然后mysql的索引是通過b+樹來實現(xiàn)的，每一次新的UUID數(shù)據(jù)的插入，為了查詢的優(yōu)化，都會對索引底層的b+樹進行修改，因為UUID數(shù)據(jù)是無序的。

所以每一次UUID數(shù)據(jù)的插入都會對主鍵地的b+樹進行很大的修改，這一點很不好。插入完全無序，不但會導(dǎo)致一些中間節(jié)點產(chǎn)生分裂，也會白白創(chuàng)造出很多不飽和的節(jié)點，這樣大大降低了數(shù)據(jù)庫插入的性能

（二）數(shù)據(jù)庫自增主鍵

數(shù)據(jù)庫自增主鍵實現(xiàn)原理：數(shù)據(jù)庫自增id和replace into實現(xiàn)的

REPLACE INTO的含義是插入一條記錄，如果表中唯一索引的值遇到?jīng)_突，則替換老數(shù)據(jù)

那數(shù)據(jù)庫自增ID機制適合作分布式ID嗎? 答案是不太適合

系統(tǒng)水平擴展比較困難，比如定義好了步長和機器臺數(shù)之后，如果要添加機器該怎么做? 假設(shè)現(xiàn)在只有一臺機器發(fā)號是1,2.3.4.5(步長是1)，這個時候需要擴容機器一臺?？梢赃@樣做，把第二臺機器的初始值設(shè)置得比第一臺超過很多，貌似還好，現(xiàn)在想象一下如果我們線上有100臺機器，這個時候要擴容該怎么做? 簡直是噩夢。所以系統(tǒng)水平擴展方案復(fù)雜難以實現(xiàn)。

數(shù)據(jù)庫壓力還是很大，每次獲取ID都得讀寫一次數(shù)據(jù)庫，非常影響性能，不符合分布式ID里面的延遲低和要高QPS的規(guī)則(在高并發(fā)下，如果都去數(shù)據(jù)庫里面獲取id，那是非常影響性能的)

（三）Redis生成全局id策略

因為Redis是單線的天生保證原子性，可以使用原子操作INCR和INCRBY來實現(xiàn)

注意:在Redis集群情況下，同樣和MySQL一樣需要設(shè)置不同的增長步長，同時key一定要設(shè)置有效期

可以使用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

三、snowflake

（一）概述

Twitter的分布式自增ID算法

特點：

① 能夠按照時間有序生成

②Snowflake算法生成id的結(jié)果是一個64bit大小的整數(shù)，為一個Long型，轉(zhuǎn)化為字符串最多19位

③分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由datacenter和workerld作區(qū)分) 并且效率較高。

（二）結(jié)構(gòu)

bit表示＋-，id一般為正，所以固定為0

時間戳位范圍為0-2^41次方，大概是可以使用69年（從1970算起）

工作進程位最多為2^10，即1024個節(jié)點，包括5位datacenter和5位workerld作區(qū)分

12bit-序列號，序列號，用來記錄同毫秒內(nèi)產(chǎn)生的不同id。12位(bit) 可以表示的最大正整數(shù)是2^12-1=4059

（三）代碼

/**
*Twitter_Snowflake

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

*0-00000000000000000000000000000000000000000-00000-00000-000000000000

*1位標(biāo)識，由于long基本類型在Java中是帶符號的，最高位是符號位，正數(shù)是0，負數(shù)是1，所以id一般是正數(shù)，最高位是0

*41位時間截(毫秒級)，注意，41位時間截不是存儲當(dāng)前時間的時間截，而是存儲時間截的差值（當(dāng)前時間截-開始時間截)
*得到的值），這里的的開始時間截，一般是我們的id生成器開始使用的時間，由我們程序來指定的（如下下面程序IdWorker類的startTime屬性）。41位的時間截，可以使用69年，年T =(1L << 41)?/?(1000L * 60?* 60?* 24 * 365)?= 69

*10位的數(shù)據(jù)機器位，可以部署在1024個節(jié)點，包括5位datacenterId和5位workerId

*12位序列，毫秒內(nèi)的計數(shù)，12位的計數(shù)順序號支持每個節(jié)點每毫秒(同一機器，同一時間截)產(chǎn)生4096個ID序號

*加起來剛好64位，為一個Long型。

* SnowFlake的優(yōu)點是，整體上按照時間自增排序，并且整個分布式系統(tǒng)內(nèi)不會產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機器ID作區(qū)分)，并且效率較高，經(jīng)測試，SnowFlake每秒能夠產(chǎn)生26萬ID左右。
*/
publicclassSnowflakeIdWorker{
//==============================Fields===========================================
/**開始時間截(2020-08-28)*/
privatefinallongtwepoch=1598598185157L;

/**機器id所占的位數(shù)*/
privatefinallongworkerIdBits=5L;

/**數(shù)據(jù)標(biāo)識id所占的位數(shù)*/
privatefinallongdatacenterIdBits=5L;

/**支持的最大機器id，結(jié)果是31(這個移位算法可以很快的計算出幾位二進制數(shù)所能表示的最大十進制數(shù))*/
privatefinallongmaxWorkerId=-1L^(-1L<maxWorkerId||workerIdmaxDatacenterId||datacenterId

	

	（四）優(yōu)缺點

	優(yōu)點:

	毫秒數(shù)在高位，自增序列在低位，整個ID都是趨勢遞增的。不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的?？梢愿鶕?jù)自身業(yè)務(wù)特性分配bit位，非常靈活。

	缺點:

	依賴機器時鐘，如果機器時鐘回撥，會導(dǎo)致重復(fù)ID生成在單機上是遞增的，但是由于設(shè)計到分布式環(huán)境，每臺機器上的時鐘不可能完全同步，有時候會出現(xiàn)不是全局遞增的情況(此缺點可以認為無所謂，一般分布式ID只要求趨勢遞增，并不會亞格要求遞增，90%的需求都只要求趨勢遞增)

	缺點的解決方案

	可以參照以下兩個來進行機器時鐘的同步

	百度開源的分布式唯一ID生成器UidGenerator

	Leaf--美團點評分布式ID生成系統(tǒng)

	





	審核編輯：劉清