近兩年的技術(shù)面試，分布式系列是面試官經(jīng)常會(huì)問(wèn)到的一個(gè)高頻方向，比如：分布式事務(wù)、分布式鎖、分布式調(diào)度、分布式存儲(chǔ)、分布式ID等。

今天我們就來(lái)聊聊，這里面相對(duì)簡(jiǎn)單的分布式ID，首先說(shuō)下，我們?yōu)槭裁葱枰植际絀D？

當(dāng)系統(tǒng)數(shù)據(jù)量過(guò)大，已經(jīng)進(jìn)行分庫(kù)分表后，我們需要對(duì)分散在各個(gè)庫(kù)表中的數(shù)據(jù)記錄進(jìn)行唯一標(biāo)識(shí)，而分布式ID恰好用來(lái)解決這個(gè)問(wèn)題。

接下來(lái)，我們看看八大分布式ID的生成方案，以及各自的優(yōu)缺點(diǎn)是什么。

圖片

1、UUID

UUID是 Universally Unique Identifier 的縮寫(xiě)，翻譯成中文為“通用唯一識(shí)別碼”，由32個(gè)16進(jìn)制數(shù)字 + 4個(gè)“-”構(gòu)成，整體長(zhǎng)度為36，其可以保證唯一性，發(fā)生碰撞的概率極低。

UUID目前有5個(gè)版本，每個(gè)版本都有不同的生成方式。目前最常用的是版本4，通過(guò)隨機(jī)數(shù)的方式生成。

UUID的生成實(shí)現(xiàn)方式非常簡(jiǎn)單，可以通過(guò)java.util包，一行代碼即可實(shí)現(xiàn)。

import java.util.UUID;
 
public class Test {
    public static void main(String[] args) {
        System.out.println(“本次生成的UUID為” + UUID.randomUUID());
    }
}


//打印結(jié)果
//本次生成的UUID為：05cb2d06-1aca-4121-acb0-dfafce04dc46

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

（1）技術(shù)實(shí)現(xiàn)簡(jiǎn)單，一行代碼即可。（2）本地即可生成，出錯(cuò)率低。（3）ID生成性能高。

缺點(diǎn)：

（1）無(wú)序，影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）存儲(chǔ)成本高，就算去掉4個(gè)“-”，長(zhǎng)度也是32。（3）可讀性差。

2、數(shù)據(jù)庫(kù)自增ID

選擇一個(gè)數(shù)據(jù)庫(kù)作為中央數(shù)據(jù)庫(kù)，利用該庫(kù)中某表的自增主鍵機(jī)制生成分布式ID。

圖片

對(duì)應(yīng)SQL語(yǔ)句如下：

REPLACE INTO id_table (stub) values (’a‘) ;
SELECT LAST_INSERT_ID();

該SQL語(yǔ)句可以使 id_table 表中在保持一條數(shù)據(jù)記錄的情況下，主鍵ID持續(xù)遞增。

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

（1）單調(diào)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）可讀性高。

缺點(diǎn)：

（1）ID生成涉及到數(shù)據(jù)庫(kù)操作，性能不高。（2）需要額外引入中央數(shù)據(jù)庫(kù)，鏈路變長(zhǎng)導(dǎo)致出錯(cuò)概率增加。（3）開(kāi)發(fā)成本相對(duì)較高。（4）數(shù)據(jù)庫(kù)壓力大。

3、Redis自增命令

通過(guò)Redis的INCR自增命令來(lái)生成分布式ID。

圖片

如下所示：

127.0.0.1:6379> set distributed_id 1     // 將分布式ID初始化為1
OK
127.0.0.1:6379> incr distributed_id      // +1，并返回結(jié)果
(integer) 2

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

（1）單調(diào)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）ID生成性能高。（3）可讀性高。

缺點(diǎn)：

（1）需要額外引入Redis，鏈路變長(zhǎng)導(dǎo)致出錯(cuò)概率增加。（2）Redis宕機(jī)后，RDB + AOF數(shù)據(jù)恢復(fù)較慢，需要Plan B提升恢復(fù)速度。（3）開(kāi)發(fā)成本相對(duì)較高。

4、雪花算法

雪花算法（SnowFlake），是Twitter公司開(kāi)源的分布式ID生成算法，在本地引入hutool jar包即可實(shí)現(xiàn)。

雪花算法生成的分布式ID共64位，由4個(gè)部分組成。

圖片

• 第一部分：1位。固定為0，表示為正整數(shù)。二進(jìn)制中最高位是符號(hào)位，ID為正整數(shù)，所以固定為0。
• 第二部分：41位。表示精確到毫秒的時(shí)間戳，時(shí)間戳帶有自增屬性，可以使用69年。
• 第三部分：10位。表示10位的機(jī)器標(biāo)識(shí)，最多支持1024個(gè)節(jié)點(diǎn)。
• 第四部分：12 位。表示自增序列，可以支持同一節(jié)點(diǎn)同一毫秒生成最多4096個(gè)ID。

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

（1）技術(shù)實(shí)現(xiàn)簡(jiǎn)單，開(kāi)發(fā)成本低。（2）趨勢(shì)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（3）本地即可生成，出錯(cuò)率低。（4）ID生成性能高。

缺點(diǎn)：

（1）強(qiáng)依賴(lài)機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)?，?huì)導(dǎo)致ID重復(fù)。（2）可讀性差。

5、數(shù)據(jù)庫(kù)號(hào)段

數(shù)據(jù)庫(kù)號(hào)段，是在“數(shù)據(jù)庫(kù)自增ID”方案上做的優(yōu)化，實(shí)現(xiàn)方式如下：

（1）從中央數(shù)據(jù)庫(kù)中獲取出一批分布式ID，并緩存到分布式ID服務(wù)本地，業(yè)務(wù)系統(tǒng)獲取分布式ID的時(shí)候，可直接在這個(gè)批次內(nèi)遞增取值。（2）若該批次分布式ID的號(hào)段用完，則需要更新數(shù)據(jù)庫(kù)中的初始值，再次獲取新批次的分布式ID，并重新緩存到分布式ID服務(wù)本地，以供使用。

圖片

CREATE TABLE id_generator (
  id int(10) NOT NULL,
  max_id bigint(20) NOT NULL COMMENT '當(dāng)前最大id',
  step int(10) NOT NULL COMMENT '號(hào)段的長(zhǎng)度',
  biz_type int(10) NOT NULL COMMENT '業(yè)務(wù)類(lèi)型',
  version int(10) NOT NULL COMMENT '版本號(hào),是一個(gè)樂(lè)觀鎖，每次都更新version，保證并發(fā)時(shí)數(shù)據(jù)的正確性',
  PRIMARY KEY (`id`)
)

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

（1）趨勢(shì)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）ID生成性能高。（3）數(shù)據(jù)庫(kù)壓力小。（4）可讀性高。

缺點(diǎn)：

（1）開(kāi)發(fā)成本很高。（2）需要額外引入分布式ID服務(wù)和中央數(shù)據(jù)庫(kù)，鏈路變長(zhǎng)導(dǎo)致出錯(cuò)概率增加。

6、美團(tuán) Leaf

Leaf，是美團(tuán)技術(shù)團(tuán)隊(duì)實(shí)現(xiàn)的分布式ID生成方案，實(shí)現(xiàn)了數(shù)據(jù)庫(kù)號(hào)段模式（Leaf-segment）和雪花算法模式（Leaf-snowflake），我們這里著重說(shuō)Leaf-snowflake。

Leaf-snowflake方案完全沿用snowflake算法方案的bit位設(shè)計(jì)，即：以“1+41+10+12”的方式組裝ID號(hào)，改動(dòng)點(diǎn)為：將SnowFlake從本地jar包變成了獨(dú)立服務(wù)，并引入了Zookeeper來(lái)解決時(shí)鐘回?fù)軉?wèn)題。

圖片

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

（1）趨勢(shì)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）解決了原有的機(jī)器上時(shí)鐘回?fù)?，?huì)出現(xiàn)的ID重復(fù)問(wèn)題。（3）ID生成性能高。

缺點(diǎn)：

（1）第三方開(kāi)源軟件，有一定的熟悉和試錯(cuò)成本。（2）需要額外引入分布式ID服務(wù)和Zookeeper，鏈路變長(zhǎng)導(dǎo)致出錯(cuò)概率增加。（3）可讀性差。

7、滴滴 Tinyid

Tinyid，是滴滴技術(shù)團(tuán)隊(duì)實(shí)現(xiàn)的分布式ID生成算法，基于上文介紹的號(hào)段模式實(shí)現(xiàn)，在此基礎(chǔ)上支持?jǐn)?shù)據(jù)庫(kù)多主節(jié)點(diǎn)模式，還提供了tinyid-client客戶(hù)端的接入方式。

除此之外，Tinyid做的另一個(gè)優(yōu)化點(diǎn)是號(hào)段預(yù)加載。

舉個(gè)例子：當(dāng)前可用號(hào)段（1——1000）被加載到內(nèi)存，獲取id時(shí)會(huì)從1開(kāi)始遞增獲取，當(dāng)使用到20%（默認(rèn)）時(shí)，會(huì)異步加載下一可用號(hào)段（4001——5000）到內(nèi)存，此時(shí)內(nèi)存中可用號(hào)段為（201——1000）和（4001——5000）。

當(dāng)id遞增到1000時(shí)，當(dāng)前號(hào)段使用完畢，下一號(hào)段會(huì)替換為當(dāng)前號(hào)段，以此類(lèi)推。

圖片

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

（1）趨勢(shì)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）ID生成性能高。（3）數(shù)據(jù)庫(kù)壓力小。（4）可讀性高。

缺點(diǎn)：

（1）第三方開(kāi)源軟件，有一定的熟悉和試錯(cuò)成本。（2）需要額外引入分布式ID服務(wù)和中央數(shù)據(jù)庫(kù)，鏈路變長(zhǎng)導(dǎo)致出錯(cuò)概率增加。

8、百度 UidGenerator

UidGenerator是Java實(shí)現(xiàn)的，基于Snowflake算法的唯一ID生成器。

UidGenerator以組件形式工作在應(yīng)用項(xiàng)目中, 支持自定義workerId位數(shù)和初始化策略。

在實(shí)現(xiàn)上，UidGenerator通過(guò)借用未來(lái)時(shí)間，來(lái)解決sequence天然存在的并發(fā)限制，采用RingBuffer來(lái)緩存已生成的UID，并行化UID的生產(chǎn)和消費(fèi)，同時(shí)對(duì)CacheLine補(bǔ)齊，避免了由RingBuffer帶來(lái)的硬件級(jí)“偽共享”問(wèn)題，最終單機(jī)QPS可達(dá)600萬(wàn)。

圖片

• 第一部分：1位，符號(hào)標(biāo)識(shí)，即生成的UID為正數(shù)。
• 第二部分：28位，當(dāng)前時(shí)間，相對(duì)于時(shí)間基點(diǎn)"2016-05-20"的增量值，單位為秒，最多可支持約8.7年。
• 第三部分：22位，機(jī)器ID，最多可支持約420w次機(jī)器啟動(dòng)。
• 第四部分：13位，每秒下的并發(fā)序列，最多可支持每秒8192個(gè)并發(fā)。

我們從這里可以看到，相比較于SnowFlake，UidGenerator的時(shí)間bit變少了，而機(jī)器ID的bit變多了。

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

（1）趨勢(shì)遞增，不會(huì)影響數(shù)據(jù)庫(kù)的數(shù)據(jù)寫(xiě)入性能。（2）本地即可生成，出錯(cuò)率低。（3）ID生成性能極高。

缺點(diǎn)：

（1）第三方開(kāi)源軟件，有一定的熟悉和試錯(cuò)成本。（2）強(qiáng)依賴(lài)機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)?，?huì)導(dǎo)致ID重復(fù)。（3）可讀性差。

結(jié)語(yǔ)

這八大分布式ID生成方案，目前最常用的方案為雪花算法和數(shù)據(jù)庫(kù)號(hào)段方式。

當(dāng)然，最常用的未必是最適合你所負(fù)責(zé)的系統(tǒng)的，大家還是需要根據(jù)各自的特性來(lái)進(jìn)行選擇。