分布式唯一 ID 生成方案，有點(diǎn)全！

一、前言

分布式系統(tǒng)中我們會(huì)對(duì)一些數(shù)據(jù)量大的業(yè)務(wù)進(jìn)行分拆，如：用戶表，訂單表。因?yàn)閿?shù)據(jù)量巨大一張表無(wú)法承接，就會(huì)對(duì)其進(jìn)行分庫(kù)分表。

但一旦涉及到分庫(kù)分表，就會(huì)引申出分布式系統(tǒng)中唯一主鍵ID的生成問(wèn)題，永不遷移數(shù)據(jù)和避免熱點(diǎn)的文章中要求需要唯一ID的特性：

• 整個(gè)系統(tǒng)ID唯一
• ID是數(shù)字類型，而且是趨勢(shì)遞增的
• ID簡(jiǎn)短，查詢效率快

什么是遞增？ 如：第一次生成的ID為12，下一次生成的ID是13，再下一次生成的ID是14。這個(gè)就是生成ID遞增。

什么是趨勢(shì)遞增？ 如：在一段時(shí)間內(nèi)，生成的ID是遞增的趨勢(shì)。如：再一段時(shí)間內(nèi)生成的ID在【0，1000】之間，過(guò)段時(shí)間生成的ID在【1000，2000】之間。但在【0-1000】區(qū)間內(nèi)的時(shí)候，ID生成有可能第一次是12，第二次是10，第三次是14。

那有什么方案呢？往下看！

二、分布式ID的幾種生成方案

2.1、UUID

這個(gè)方案是小伙伴們第一個(gè)能過(guò)考慮到的方案

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

• 代碼實(shí)現(xiàn)簡(jiǎn)單。
• 本機(jī)生成，沒(méi)有性能問(wèn)題
• 因?yàn)槭侨蛭ㄒ坏腎D，所以遷移數(shù)據(jù)容易

缺點(diǎn)：

• 每次生成的ID是無(wú)序的，無(wú)法保證趨勢(shì)遞增
• UUID的字符串存儲(chǔ)，查詢效率慢
• 存儲(chǔ)空間大
• ID本事無(wú)業(yè)務(wù)含義，不可讀

應(yīng)用場(chǎng)景：

• 類似生成token令牌的場(chǎng)景

• 不適用一些要求有趨勢(shì)遞增的ID場(chǎng)景

  
  

這個(gè)方案就是利用了MySQL的主鍵自增auto_increment，默認(rèn)每次ID加1。

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

• 數(shù)字化，id遞增
• 查詢效率高
• 具有一定的業(yè)務(wù)可讀

缺點(diǎn)：

• 存在單點(diǎn)問(wèn)題，如果mysql掛了，就沒(méi)法生成iD了
• 數(shù)據(jù)庫(kù)壓力大，高并發(fā)抗不住

2.3、MySQL多實(shí)例主鍵自增

這個(gè)方案就是解決mysql的單點(diǎn)問(wèn)題，在auto_increment基本上面，設(shè)置step步長(zhǎng)

每臺(tái)的初始值分別為1,2,3...N，步長(zhǎng)為N（這個(gè)案例步長(zhǎng)為4）

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

• 解決了單點(diǎn)問(wèn)題

缺點(diǎn)：

• 一旦把步長(zhǎng)定好后，就無(wú)法擴(kuò)容；而且單個(gè)數(shù)據(jù)庫(kù)的壓力大，數(shù)據(jù)庫(kù)自身性能無(wú)法滿足高并發(fā)

應(yīng)用場(chǎng)景：

• 數(shù)據(jù)不需要擴(kuò)容的場(chǎng)景

2.4、雪花snowflake算法

這個(gè)算法網(wǎng)上介紹了很多。雪花算法生成64位的二進(jìn)制正整數(shù)，然后轉(zhuǎn)換成10進(jìn)制的數(shù)。64位二進(jìn)制數(shù)由如下部分組成：

• 1位標(biāo)識(shí)符：始終是0
• 41位時(shí)間戳：41位時(shí)間截不是存儲(chǔ)當(dāng)前時(shí)間的時(shí)間截，而是存儲(chǔ)時(shí)間截的差值（當(dāng)前時(shí)間截 - 開始時(shí)間截 )得到的值，這里的的開始時(shí)間截，一般是我們的id生成器開始使用的時(shí)間，由我們程序來(lái)指定的
• 10位機(jī)器標(biāo)識(shí)碼：可以部署在1024個(gè)節(jié)點(diǎn)，如果機(jī)器分機(jī)房（IDC）部署，這10位可以由 5位機(jī)房ID + 5位機(jī)器ID 組成
• 12位序列：毫秒內(nèi)的計(jì)數(shù)，12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時(shí)間截)產(chǎn)生4096個(gè)ID序號(hào)

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

• 此方案每秒能夠產(chǎn)生409.6萬(wàn)個(gè)ID，性能快
• 時(shí)間戳在高位，自增序列在低位，整個(gè)ID是趨勢(shì)遞增的，按照時(shí)間有序遞增
• 靈活度高，可以根據(jù)業(yè)務(wù)需求，調(diào)整bit位的劃分，滿足不同的需求

缺點(diǎn)：

• 依賴機(jī)器的時(shí)鐘，如果服務(wù)器時(shí)鐘回?fù)埽瑫?huì)導(dǎo)致重復(fù)ID生成

在分布式場(chǎng)景中，服務(wù)器時(shí)鐘回?fù)軙?huì)經(jīng)常遇到，一般存在10ms之間的回?fù)?；小伙伴們就說(shuō)這點(diǎn)10ms，很短可以不考慮吧。但此算法就是建立在毫秒級(jí)別的生成方案，一旦回?fù)?，就很有可能存在重?fù)ID。

2.5、Redis生成方案

利用redis的incr原子性操作自增，一般算法為：

年份 + 當(dāng)天距當(dāng)年第多少天 + 天數(shù) + 小時(shí) + redis自增

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

• 有序遞增，可讀性強(qiáng)

缺點(diǎn)：

• 占用帶寬，每次要向redis進(jìn)行請(qǐng)求

整體測(cè)試了這個(gè)性能如下：

需求：同時(shí)10萬(wàn)個(gè)請(qǐng)求獲取ID1、并發(fā)執(zhí)行完耗時(shí)：9s左右
2、單任務(wù)平均耗時(shí)：74ms
3、單線程最小耗時(shí)：不到1ms
4、單線程最大耗時(shí)：4.1s

性能還可以，如果對(duì)性能要求不是太高的話，這個(gè)方案基本符合要求。

但不完全符合希望id從 1 開始趨勢(shì)遞增。（當(dāng)然算法可以調(diào)整為 就一個(gè) redis自增，不需要什么年份，多少天等）。

2.6、小結(jié)

以上介紹了常見的幾種分布式ID生成方案。一線大廠的分布式ID方案絕沒(méi)有這個(gè)簡(jiǎn)單，他們對(duì)高并發(fā)，高可用的要求很高。

如Redis方案中，每次都要去Redis去請(qǐng)求，有網(wǎng)絡(luò)請(qǐng)求耗時(shí)，并發(fā)強(qiáng)依賴了Redis。這個(gè)設(shè)計(jì)是有風(fēng)險(xiǎn)的，一旦Redis掛了，整個(gè)系統(tǒng)不可用。

而且一線大廠也會(huì)考慮到ID安全性的問(wèn)題，如：Redis方案中，用戶是可以預(yù)測(cè)下一個(gè)ID號(hào)是多少，因?yàn)樗惴ㄊ沁f增的。

這樣的話競(jìng)爭(zhēng)對(duì)手第一天中午12點(diǎn)下個(gè)訂單，就可以看到平臺(tái)的訂單ID是多少，第二天中午12點(diǎn)再下一單，又平臺(tái)訂單ID到多少。這樣就可以猜到平臺(tái)1天能產(chǎn)生多少訂單了，這個(gè)是絕對(duì)不允許的，公司絕密啊。

三、一線大廠是如何設(shè)計(jì)的呢?

一線大廠的設(shè)計(jì)思路其實(shí)和小伙伴們思路差不多，只是多想了1～2層，設(shè)計(jì)上面多了1～2個(gè)環(huán)節(jié)。

3.1、改造數(shù)據(jù)庫(kù)主鍵自增

上述我們介紹了利用數(shù)據(jù)庫(kù)的自增主鍵的特性，可以實(shí)現(xiàn)分布式ID；這個(gè)ID比較簡(jiǎn)短明了，適合做userId，正好符合如何永不遷移數(shù)據(jù)和避免熱點(diǎn)? 根據(jù)服務(wù)器指標(biāo)分配數(shù)據(jù)量(揭秘篇)文章中的ID的需求。但這個(gè)方案有嚴(yán)重的問(wèn)題：

• 一旦步長(zhǎng)定下來(lái)，不容易擴(kuò)容
• 數(shù)據(jù)庫(kù)壓力山大

小伙伴們看看怎么優(yōu)化這個(gè)方案。先看數(shù)據(jù)庫(kù)壓力大，為什么壓力大？是因?yàn)槲覀兠看潍@取ID的時(shí)候，都要去數(shù)據(jù)庫(kù)請(qǐng)求一次。那我們可以不可以不要每次去??？

思路我們可以請(qǐng)求數(shù)據(jù)庫(kù)得到ID的時(shí)候，可設(shè)計(jì)成獲得的ID是一個(gè)ID區(qū)間段。

我們看上圖，有張ID規(guī)則表：

1、id表示為主鍵，無(wú)業(yè)務(wù)含義。

2、biz_tag為了表示業(yè)務(wù)，因?yàn)檎w系統(tǒng)中會(huì)有很多業(yè)務(wù)需要生成ID，這樣可以共用一張表維護(hù)

3、max_id表示現(xiàn)在整體系統(tǒng)中已經(jīng)分配的最大ID

4、desc描述

5、update_time表示每次取的ID時(shí)間

我們?cè)賮?lái)看看整體流程：

1、【用戶服務(wù)】在注冊(cè)一個(gè)用戶時(shí)，需要一個(gè)用戶ID；會(huì)請(qǐng)求【生成ID服務(wù)(是獨(dú)立的應(yīng)用)】的接口

2、【生成ID服務(wù)】會(huì)去查詢數(shù)據(jù)庫(kù)，找到user_tag的id，現(xiàn)在的max_id為0，step=1000

3、【生成ID服務(wù)】把max_id和step返回給【用戶服務(wù)】；并且把max_id更新為max_id = max_id + step，即更新為1000

4、【用戶服務(wù)】獲得max_id=0，step=1000；

5、 這個(gè)用戶服務(wù)可以用ID=【max_id + 1，max_id+step】區(qū)間的ID，即為【1，1000】

6、【用戶服務(wù)】會(huì)把這個(gè)區(qū)間保存到j(luò)vm中

7、【用戶服務(wù)】需要用到ID的時(shí)候，在區(qū)間【1，1000】中依次獲取id，可采用AtomicLong中的getAndIncrement方法。

8、如果把區(qū)間的值用完了，再去請(qǐng)求【生產(chǎn)ID服務(wù)】接口，獲取到max_id為1000，即可以用【max_id + 1，max_id+step】區(qū)間的ID，即為【1001，2000】

這個(gè)方案就非常完美的解決了數(shù)據(jù)庫(kù)自增的問(wèn)題，而且可以自行定義max_id的起點(diǎn)，和step步長(zhǎng)，非常方便擴(kuò)容。

而且也解決了數(shù)據(jù)庫(kù)壓力的問(wèn)題，因?yàn)樵谝欢螀^(qū)間內(nèi)，是在jvm內(nèi)存中獲取的，而不需要每次請(qǐng)求數(shù)據(jù)庫(kù)。即使數(shù)據(jù)庫(kù)宕機(jī)了，系統(tǒng)也不受影響，ID還能維持一段時(shí)間。

3.2、競(jìng)爭(zhēng)問(wèn)題

以上方案中，如果是多個(gè)用戶服務(wù)，同時(shí)獲取ID，同時(shí)去請(qǐng)求【ID服務(wù)】，在獲取max_id的時(shí)候會(huì)存在并發(fā)問(wèn)題。

如用戶服務(wù)A，取到的max_id=1000 ;用戶服務(wù)B取到的也是max_id=1000，那就出現(xiàn)了問(wèn)題，Id重復(fù)了。那怎么解決？

其實(shí)方案很多，加分布式鎖，保證同一時(shí)刻只有一個(gè)用戶服務(wù)獲取max_id。當(dāng)然也可以用數(shù)據(jù)庫(kù)自身的鎖去解決。

利用事務(wù)方式加行鎖，上面的語(yǔ)句，在沒(méi)有執(zhí)行完之前，是不允許第二個(gè)用戶服務(wù)請(qǐng)求過(guò)來(lái)的，第二個(gè)請(qǐng)求只能阻塞。

3.3、突發(fā)阻塞問(wèn)題

上圖中，多個(gè)用戶服務(wù)獲取到了各自的ID區(qū)間，在高并發(fā)場(chǎng)景下，ID用的很快，如果3個(gè)用戶服務(wù)在某一時(shí)刻都用完了，同時(shí)去請(qǐng)求【ID服務(wù)】。因?yàn)樯厦嫣岬降母?jìng)爭(zhēng)問(wèn)題，所有只有一個(gè)用戶服務(wù)去操作數(shù)據(jù)庫(kù)，其他二個(gè)會(huì)被阻塞。

小伙伴就會(huì)問(wèn)，有這么巧嗎？同時(shí)ID用完。我們這里舉的是3個(gè)用戶服務(wù)，感覺概率不大；如果是100個(gè)用戶服務(wù)呢？概率是不是一下子大了。

出現(xiàn)的現(xiàn)象就是一會(huì)兒突然系統(tǒng)耗時(shí)變長(zhǎng)，一會(huì)兒好了，就是這個(gè)原因?qū)е碌?，怎么去解決？

3.4、雙buffer方案

在一般的系統(tǒng)設(shè)計(jì)中，雙buffer會(huì)經(jīng)常看到，怎么去解決上面的問(wèn)題也可以采用雙buffer方案。

在設(shè)計(jì)的時(shí)候，采用雙buffer方案，上圖的流程：

1、當(dāng)前獲取ID在buffer1中，每次獲取ID在buffer1中獲取

2、當(dāng)buffer1中的Id已經(jīng)使用到了100，也就是達(dá)到區(qū)間的10%

3、達(dá)到了10%，先判斷buffer2中有沒(méi)有去獲取過(guò)，如果沒(méi)有就立即發(fā)起請(qǐng)求獲取ID線程，此線程把獲取到的ID，設(shè)置到buffer2中。

4、如果buffer1用完了，會(huì)自動(dòng)切換到buffer2

5、buffer2用到10%了，也會(huì)啟動(dòng)線程再次獲取，設(shè)置到buffer1中

6、依次往返

雙buffer的方案，小伙伴們有沒(méi)有感覺很酷，這樣就達(dá)到了業(yè)務(wù)場(chǎng)景用的ID，都是在jvm內(nèi)存中獲得的，從此不需要到數(shù)據(jù)庫(kù)中獲取了。允許數(shù)據(jù)庫(kù)宕機(jī)時(shí)間更長(zhǎng)了。

因?yàn)闀?huì)有一個(gè)線程，會(huì)觀察什么時(shí)候去自動(dòng)獲取。兩個(gè)buffer之間自行切換使用。就解決了突發(fā)阻塞的問(wèn)題。

四、總結(jié)

此方案是某團(tuán)使用的分布式ID算法，小伙伴們?nèi)绻肓私飧?，可以去網(wǎng)上搜下，這里應(yīng)該介紹了比較詳細(xì)了。

當(dāng)然此方案美團(tuán)還做了一些別的優(yōu)化，監(jiān)控ID使用頻率，自動(dòng)設(shè)置步長(zhǎng)step，從而達(dá)到對(duì)ID節(jié)省使用。

來(lái)源：toutiao.com/i6682672464708764174