UUID的弊端以及雪花算法簡(jiǎn)析

一、問(wèn)題

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

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

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

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

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

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

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

①全局唯一

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

②趨勢(shì)遞增

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

③單調(diào)遞增

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

④信息安全

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

⑤含時(shí)間戳

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

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

①高可用

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

②低延遲

返回的速度要快

③高QPS（抵抗高訪問(wèn)）

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

二、一般通用方案

（一）UUID

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

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

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

索引， B+樹(shù)索引的分裂

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

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

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

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

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

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

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

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

（三）Redis生成全局id策略

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

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

可以使用Redis集群來(lái)獲取更高的吞吐量。

假如一個(gè)集群中有5臺(tái)Redis?？梢猿跏蓟颗_(tái)Redis的值分別是1,2,3,4,5，然后步長(zhǎng)都是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)不會(huì)產(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-序列號(hào)，序列號(hào)，用來(lái)記錄同毫秒內(nèi)產(chǎn)生的不同id。12位(bit) 可以表示的最大正整數(shù)是2^12-1=4059

（三）代碼

/**
*Twitter_Snowflake

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

*0-00000000000000000000000000000000000000000-00000-00000-000000000000

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

*41位時(shí)間截(毫秒級(jí))，注意，41位時(shí)間截不是存儲(chǔ)當(dāng)前時(shí)間的時(shí)間截，而是存儲(chǔ)時(shí)間截的差值（當(dāng)前時(shí)間截-開(kāi)始時(shí)間截)
*得到的值），這里的的開(kāi)始時(shí)間截，一般是我們的id生成器開(kāi)始使用的時(shí)間，由我們程序來(lái)指定的（如下下面程序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ù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時(shí)間截)產(chǎn)生4096個(gè)ID序號(hào)

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

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

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

/**數(shù)據(jù)標(biāo)識(shí)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ì)遞增的。不依賴數(shù)據(jù)庫(kù)等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的?？梢愿鶕?jù)自身業(yè)務(wù)特性分配bit位，非常靈活。

	缺點(diǎn):

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

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

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

	百度開(kāi)源的分布式唯一ID生成器UidGenerator

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

	





	審核編輯：劉清