一、問題

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

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

如在美團(tuán)點(diǎn)評的金融、支付、餐飲、酒店;

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

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

此時(shí)一個(gè)能夠生成全局唯一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)遞增

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

④信息安全

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

⑤含時(shí)間戳

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

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

①高可用

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

②低延遲

返回的速度要快

③高QPS（抵抗高訪問）

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

二、一般通用方案

（一）UUID

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

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

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

索引， B+樹索引的分裂

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

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

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

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

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

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

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

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

（三）Redis生成全局id策略

因?yàn)镽edis是單線的天生保證原子性，可以使用原子操作INCR和INCRBY來實(shí)現(xiàn)

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

可以使用Redis集群來獲取更高的吞吐量。

假如一個(gè)集群中有5臺Redis?？梢猿跏蓟颗_Redis的值分別是1,2,3,4,5，然后步長都是5。

各個(gè)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算法

特點(diǎn)：

① 能夠按照時(shí)間有序生成

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

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

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

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

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

工作進(jìn)程位最多為2^10，即1024個(gè)節(jié)點(diǎn)，包括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，負(fù)數(shù)是1，所以id一般是正數(shù)，最高位是0

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

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

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

*加起來剛好64位，為一個(gè)Long型。

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

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

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

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

	

	（四）優(yōu)缺點(diǎn)

	優(yōu)點(diǎn):

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

	缺點(diǎn):

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

	缺點(diǎn)的解決方案

	可以參照以下兩個(gè)來進(jìn)行機(jī)器時(shí)鐘的同步

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

	Leaf--美團(tuán)點(diǎn)評分布式ID生成系統(tǒng)

	





	審核編輯：劉清