一文讀懂分布式唯一ID生成

很多大的互聯(lián)網(wǎng)公司數(shù)據(jù)量很大，都采用分庫(kù)分表，那么分庫(kù)后就需要統(tǒng)一的唯一ID進(jìn)行存儲(chǔ)。這個(gè)ID可以是數(shù)字遞增的，也可以是UUID類型的。

如果是遞增的話，那么拆分了數(shù)據(jù)庫(kù)后，可以按照id的hash，均勻的分配到數(shù)據(jù)庫(kù)中，并且mysql數(shù)據(jù)庫(kù)如果將遞增的字段作為主鍵存儲(chǔ)的話會(huì)大大提高存儲(chǔ)速度。但是如果把訂單ID按照數(shù)字遞增的話，別人能夠很容易猜到你有多少訂單了，這種情況就可以需要一種非數(shù)字遞增的方式進(jìn)行ID的生成。

想到分布式ID的生成，大家可能想到采用Redis進(jìn)行生成ID，使用Redis的INCR命令去生成和獲取這個(gè)自增的ID，這個(gè)沒有問題，但是這個(gè)INCR的生成QPS速度為200400（官網(wǎng)發(fā)布的測(cè)試結(jié)果），也就是20W這樣子，如果QPS沒有超過這些的話，顯然使用Redis比較合適。

那么我們對(duì)于要達(dá)到高可用，高QPS，低延遲我們有沒有更好的想法呢。接下來(lái)一起看一下snowflake算法，由twitter公司開源的雪花算法。

snowflake一共64位：

• 1.第一位不用。

• 2. 41位是時(shí)間戳。 2^41以毫秒為單位的話，可得到69年，非常夠用了。

• 3. 10位位工作機(jī)器，可以有2^10=1024個(gè)工作節(jié)點(diǎn)，有的公司將其拆分為5位工作中心編碼，5位分給工作機(jī)器。

• 4. 最后12位用于生成遞增數(shù)據(jù)共4096個(gè)數(shù)。

如果用這個(gè)理論上的QPS上的QPS為409W/S。

這種方式的優(yōu)點(diǎn)為：

• 1. QPS非常高，性能也非常夠。高性能條件也滿足了。

• 2. 不需要依賴其他第三方的中間件，比如Redis。少了依賴，可用率提高了。

• 3. 可以根據(jù)自己定制進(jìn)行調(diào)節(jié)。也就是里邊的10位進(jìn)行自由分配。

缺點(diǎn)：

此種算法很依賴時(shí)鐘，假如時(shí)鐘進(jìn)行回?fù)芰耍瑢⒂锌赡苌上嗤腎D。

UUID是采用32位二進(jìn)制數(shù)據(jù)生成的，它生成的性能非常好，但是它是基于機(jī)器MAC地址生成的，而且不是分布式的，所以不是咱們討論的范疇。

　　下面咱們看一下一些大公司的分布式ID實(shí)現(xiàn)機(jī)制，通過生成創(chuàng)建一張表，采用8個(gè)Byte, 64位進(jìn)行存儲(chǔ)使用，用這張表記錄所產(chǎn)生ID的位置，比如ID從0開始，然后使用了1000個(gè)，那么數(shù)據(jù)庫(kù)里邊記錄里邊的最大值是一千，同時(shí)還有個(gè)步長(zhǎng)值，比如1000，那么獲取下一個(gè)值得時(shí)候最大值為2001，即最大的沒有使用的值。

具體的實(shí)現(xiàn)步驟如下：

• 1. 提供一個(gè)生成分布式ID的服務(wù)，這個(gè)ID的服務(wù)是讀取數(shù)據(jù)庫(kù)里邊的值和步長(zhǎng)值計(jì)算生成需要的值和范圍，然后服務(wù)消費(fèi)方拿到后進(jìn)行將號(hào)段存儲(chǔ)到緩存中使用。

• 2.當(dāng)給到服務(wù)調(diào)用方之后，數(shù)據(jù)庫(kù)立即更新數(shù)據(jù)。

這種情況下的優(yōu)點(diǎn)為：

• 1.? 容災(zāi)性能好，如果DB出現(xiàn)問題，因?yàn)閿?shù)據(jù)放到內(nèi)存中，還是可以支撐一段時(shí)間。

• 2. 8個(gè)Byte可以滿足業(yè)務(wù)生成ID使用。

• 3. 最大值可以自己定義，這樣有些遷移的業(yè)務(wù)還可以自己定義最大值繼續(xù)使用。

當(dāng)然缺點(diǎn)也存在：

• 1. 當(dāng)數(shù)據(jù)庫(kù)掛了整個(gè)系統(tǒng)將不能使用。

• 2. 號(hào)段遞增的，容易被其他人猜到。

• 3. 如果很多服務(wù)同時(shí)訪問獲取這個(gè)ID或者網(wǎng)絡(luò)波動(dòng)導(dǎo)致數(shù)據(jù)庫(kù)IO升高的時(shí)候，系統(tǒng)穩(wěn)定性會(huì)出現(xiàn)問題。

然后針對(duì)上述情況的解決方法是他們采用了雙緩存機(jī)制，即將號(hào)碼段讀取到內(nèi)存中之后開始使用，當(dāng)使用到了10%的時(shí)候重新啟動(dòng)一個(gè)新線程，然后當(dāng)一個(gè)緩存用完了之后去用另一塊緩存的數(shù)據(jù)。當(dāng)另一個(gè)緩存的數(shù)據(jù)達(dá)到10%的時(shí)候再重啟激動(dòng)一個(gè)新線程獲取，依次反復(fù)。

這樣做的好處是避免同時(shí)訪問大量數(shù)據(jù)庫(kù)，導(dǎo)致I/O增多。同時(shí)可以通過兩個(gè)緩存段解決了單一緩存導(dǎo)致很快用完的情況。當(dāng)然把這個(gè)號(hào)段設(shè)置成QPS大小的600倍，這樣數(shù)據(jù)庫(kù)掛了10-20分鐘內(nèi)還是可以繼續(xù)提供服務(wù)的。

以上一直提到了一個(gè)問題，就是ID遞增，咱們?nèi)绾谓鉀Q這個(gè)問題呢。就是采用snowflake，然后解決里邊的時(shí)鐘問題，有些公司采用ZK去比較當(dāng)前workerId也就是節(jié)點(diǎn)ID使用的時(shí)間是否有回?fù)埽绻谢負(fù)芫瓦M(jìn)行休眠固定時(shí)間，看是否能趕上時(shí)間，如果能趕上的話，繼續(xù)生成ID，如果一直沒有趕上達(dá)到某個(gè)值得話，那么就報(bào)錯(cuò)處理。因?yàn)橹虚g10位是表示不同的節(jié)點(diǎn)，那么不同的節(jié)點(diǎn)生成的ID就不會(huì)存在遞增的情況。

這些思路都是某公司已經(jīng)實(shí)現(xiàn)了的，如果有興趣繼續(xù)研究的話，那么在GITHUB上搜索下開源的Leaf可以直接拿著使用的。