為什么需要分布式ID？求一種分布式ID生成方案

1. 為什么需要分布式 ID

對(duì)于單體系統(tǒng)來(lái)說(shuō)，主鍵 ID 常用主鍵自動(dòng)的方式進(jìn)行設(shè)置。這種 ID 生成方法在單體項(xiàng)目是可行的，但是對(duì)于分布式系統(tǒng)，分庫(kù)分表之后就不適應(yīng)了。比如訂單表數(shù)據(jù)量太大了，分成了多個(gè)庫(kù)，如果還采用數(shù)據(jù)庫(kù)主鍵自增的方式，就會(huì)出現(xiàn)在不同庫(kù) id 一致的情況，雖然是不符合業(yè)務(wù)的。

基于 Spring Boot + MyBatis Plus + Vue & Element 實(shí)現(xiàn)的后臺(tái)管理系統(tǒng) + 用戶小程序，支持 RBAC 動(dòng)態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

2. 業(yè)務(wù)系統(tǒng)對(duì)分布式 ID 有什么要求

全局唯一性 ：ID 是作為唯一的標(biāo)識(shí)，不能出現(xiàn)重復(fù)；

趨勢(shì)遞增 ：互聯(lián)網(wǎng)比較喜歡 MySQL 數(shù)據(jù)庫(kù)，而 MySQL 數(shù)據(jù)庫(kù)默認(rèn)使用 InnoDB 存儲(chǔ)引擎，其使用的是聚集索引，使用有序的主鍵 ID 有利于保證寫入的效率；

單調(diào)遞增 ：保證下一個(gè) ID 大于上一個(gè) ID，這種情況可以保證事務(wù)版本號(hào)，排序等特殊需求實(shí)現(xiàn)；

信息安全 ：前面說(shuō)了 ID 要遞增，但是最好不要連續(xù)。如果 ID 是連續(xù)的，容易被惡意爬取數(shù)據(jù)，指定一系列連續(xù)的，所以 ID 遞增但是不規(guī)則是最好的。

基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實(shí)現(xiàn)的后臺(tái)管理系統(tǒng) + 用戶小程序，支持 RBAC 動(dòng)態(tài)權(quán)限、多租戶、數(shù)據(jù)權(quán)限、工作流、三方登錄、支付、短信、商城等功能

3. 分布式 ID 生成方案

UUID

數(shù)據(jù)庫(kù)自增

號(hào)段模式

Redis 實(shí)現(xiàn)

雪花算法（SnowFlake）

百度 Uidgenerator

美團(tuán) Leaf

滴滴 TinyID

3.1 UUID

UUID （Universally Unique Identifier），通用唯一識(shí)別碼的縮寫。

UUID 的標(biāo)準(zhǔn)型式包含 32 個(gè) 16 進(jìn)制數(shù)字，以連字號(hào)分為五段，形式為 8-4-4-4-12 的 36 個(gè)字符，示例 863e254b-ae34-4371-87da-204b71d46a7b。

UUID 理論上的總數(shù)為 1632=2128，約等于 3.4 x 10^38。

優(yōu)點(diǎn) ：性能非常高，本地生成的，不依賴于網(wǎng)絡(luò)；

缺點(diǎn) ：不易存儲(chǔ)。16 字節(jié) 128 位，36 位長(zhǎng)度的字符串信息不安全，基于 MAC 地址生成 UUID 算法可能會(huì)造成 MAC 地址泄露，暴露使用者的位置。UUID 的無(wú)序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，影響性能。

3.2 數(shù)據(jù)庫(kù)自增

在分布式環(huán)境也可以使用 MySQL 自增實(shí)現(xiàn)分布式 ID 的生成。如果分庫(kù)分表了，當(dāng)然不是簡(jiǎn)單地設(shè)置好 auto_increment_increment 和 auto_increment_offset 就行。在分布式系統(tǒng)中，我們可以多部署幾臺(tái)機(jī)器，每臺(tái)機(jī)器設(shè)置不同的初始值，且步長(zhǎng)和機(jī)器數(shù)相等。

比如有兩臺(tái)機(jī)器，設(shè)置步長(zhǎng) step 為 2。Server1 的初始值為 1（1, 3, 5, 7, 9, 11…），Server2 的初始值為 2（2, 4, 6, 8, 10…）。

這是 Flickr 團(tuán)隊(duì)在 2010 年撰文介紹的一種主鍵生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。

假設(shè)有 N 臺(tái)機(jī)器，step 就要設(shè)置為 N，如下圖進(jìn)行設(shè)置：

這種方案看起來(lái)是可行的。但是如果要擴(kuò)容，步長(zhǎng) step 等要重新設(shè)置。假如只有一臺(tái)機(jī)器，步長(zhǎng)就是 1，比如 1,2,3,4,5,6。這時(shí)候如果要進(jìn)行擴(kuò)容，就要重新設(shè)置。機(jī)器 2 可以挑一個(gè)偶數(shù)的數(shù)字，這個(gè)數(shù)字在擴(kuò)容時(shí)間內(nèi)，數(shù)據(jù)庫(kù)自增達(dá)不到這個(gè)數(shù)的，然后步長(zhǎng)就是 2。機(jī)器 1 要重新設(shè)置 step 為 2，然后還是以一個(gè)奇數(shù)開始進(jìn)行自增。這個(gè)過(guò)程看起來(lái)不是很雜，但是如果機(jī)器很多的話，那就要花很多時(shí)間去維護(hù)重新設(shè)置。

這種實(shí)現(xiàn)的缺陷：

ID 沒(méi)有了單調(diào)遞增的特性，只能趨勢(shì)遞增。有些業(yè)務(wù)場(chǎng)景可能不符合；

數(shù)據(jù)庫(kù)壓力還是比較大，每次獲取 ID 都需要讀取數(shù)據(jù)庫(kù)，只能通過(guò)多臺(tái)機(jī)器提高穩(wěn)定性和性能。

3.3 號(hào)段模式

這種模式也是現(xiàn)在生成分布式 ID 的一種方法。實(shí)現(xiàn)思路是，會(huì)從數(shù)據(jù)庫(kù)獲取一個(gè)號(hào)段范圍，比如 [1,1000]，生成 1 到 1000 的自增 ID 加載到內(nèi)存中。

建表結(jié)構(gòu)如下：

CREATETABLEid_generator(
idint(10)NOTNULL,
max_idbigint(20)NOTNULLCOMMENT'當(dāng)前最大id',
stepint(20)NOTNULLCOMMENT'號(hào)段的布長(zhǎng)',
biz_typeint(20)NOTNULLCOMMENT'業(yè)務(wù)類型',
versionint(20)NOTNULLCOMMENT'版本號(hào)',
PRIMARYKEY(`id`)
)

biz_type ：不同業(yè)務(wù)類型；

max_id ：當(dāng)前最大的 id；

step ：代表號(hào)段的步長(zhǎng)；

version ：版本號(hào)，就像 MVCC 一樣，可以理解為樂(lè)觀鎖。

等 ID 都用完了，再去數(shù)據(jù)庫(kù)獲取，然后更改最大值：

updateid_generatorsetmax_id=#{max_id+step},version=version+1whereversion=#{version}andbiz_type=XXX

優(yōu)點(diǎn) ：有比較成熟的方案，像百度 Uidgenerator，美團(tuán) Leaf；

缺點(diǎn) ：依賴于數(shù)據(jù)庫(kù)實(shí)現(xiàn)。

3.4 Redis 實(shí)現(xiàn)

Redis 分布式 ID 實(shí)現(xiàn)主要是通過(guò)提供像 INCR 和 INCRBY 這樣的自增原子命令。由于 Redis 單線程的特點(diǎn)，可以保證 ID 的唯一性和有序性。

這種實(shí)現(xiàn)方式，如果并發(fā)請(qǐng)求量上來(lái)后，就需要集群。不過(guò)集群后，又要和傳統(tǒng)數(shù)據(jù)庫(kù)一樣，設(shè)置分段和步長(zhǎng)。

優(yōu)點(diǎn) ：Redis 性能相對(duì)比較好，而且可以保證唯一性和有序性；

缺點(diǎn) ：需要依賴 Redis 來(lái)實(shí)現(xiàn)，系統(tǒng)需要引入 Redis 組件。

3.5 雪花算法（SnowFlake）

雪花算法（Snowflake）是由 Twitter 開源的分布式 ID 生成算法，以劃分命名空間的方式將 64-bit 位分割成多個(gè)部分，每個(gè)部分代表不同的含義。在 Java 中 Long 類型是 64 位的，所以 Java 程序中一般使用 Long 類型存儲(chǔ)。

第一部分：第一位占用 1 bit，始終是 0，是一個(gè)符號(hào)位，不使用；

第二部分：第 2 位開始的 41 位是時(shí)間戳。41-bit 位可表示 241 個(gè)數(shù)，每個(gè)數(shù)代表毫秒，那么雪花算法可用的時(shí)間年限是 (241)/(1000606024365)=69 年的時(shí)間；

第三部分：10-bit 位可表示機(jī)器數(shù)，即 2^10 = 1024 臺(tái)機(jī)器。通常不會(huì)部署這么多臺(tái)機(jī)器；

第四部分：12-bit 位是自增序列，可表示 2^12 = 4096 個(gè)數(shù)。覺(jué)得一毫秒個(gè)數(shù)不夠用也可以調(diào)大點(diǎn)。

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

優(yōu)點(diǎn) ：雪花算法生成的 ID 是趨勢(shì)遞增，不依賴數(shù)據(jù)庫(kù)等第三方系統(tǒng)。生成 ID 的效率非常高，穩(wěn)定性好，可以根據(jù)自身業(yè)務(wù)特性分配 bit 位，比較靈活；

缺點(diǎn) ：雪花算法強(qiáng)依賴于機(jī)器時(shí)鐘 。如果機(jī)器上時(shí)鐘回?fù)?，?huì)導(dǎo)致發(fā)號(hào)重復(fù)或者服務(wù)會(huì)處于不可用狀態(tài)。如果恰巧回退前生成過(guò)一些 ID，而時(shí)間回退后，生成的 ID 就有可能重復(fù)。

3.6 百度 Uidgenerator

百度 UidGenerator 是百度開源基于 Java 語(yǔ)言實(shí)現(xiàn)的唯一 ID 生成器，是在雪花算法 Snowflake 的基礎(chǔ)上做了一些改進(jìn)。

引用官網(wǎng)的解釋：

UidGenerator 是 Java 實(shí)現(xiàn)的, 基于 Snowflake 算法的唯一 ID 生成器。UidGenerator 以組件形式工作在應(yīng)用項(xiàng)目中，支持自定義 workerId 位數(shù)和初始化策略，從而適用于 docker 等虛擬化環(huán)境下實(shí)例自動(dòng)重啟、漂移等場(chǎng)景。在實(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í)「?jìng)喂蚕怼箚?wèn)題. 最終單機(jī) QPS 可達(dá) 600 萬(wàn)。

Snowflake 算法描述：指定機(jī)器 & 同一時(shí)刻 & 某一并發(fā)序列，是唯一的。據(jù)此可生成一個(gè) 64 bits 的唯一 ID（long）。默認(rèn)采用上圖字節(jié)分配方式：

sign(1bit)：固定 1bit 符號(hào)標(biāo)識(shí)，即生成的 UID 為正數(shù)；

delta seconds (28 bits)：當(dāng)前時(shí)間，相對(duì)于時(shí)間基點(diǎn)"2016-05-20"的增量值，單位：秒，最多可支持約8.7年；

worker id (22 bits)：機(jī)器 id，最多可支持約 420 萬(wàn)次機(jī)器啟動(dòng)。內(nèi)置實(shí)現(xiàn)為在啟動(dòng)時(shí)由數(shù)據(jù)庫(kù)分配，默認(rèn)分配策略為用后即棄，后續(xù)可提供復(fù)用策略；

sequence (13 bits)：每秒下的并發(fā)序列，13 bits 可支持每秒 8192 個(gè)并發(fā)。

詳細(xì)介紹可參考官網(wǎng)說(shuō)明：

ttps://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

3.7 美團(tuán) Leaf

Leaf 這個(gè)名字是來(lái)自德國(guó)哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話：There are no two identical leaves in the world “世界上沒(méi)有兩片相同的樹葉”

Leaf 提供兩種生成的 ID 的方式：號(hào)段模式（Leaf-segment）和 Snowflake 模式（Leaf-snowflake）。你可以同時(shí)開啟兩種方式，也可以指定開啟某種方式，默認(rèn)兩種方式為關(guān)閉狀態(tài)。

Leafsegment 數(shù)據(jù)庫(kù)方案

其實(shí)就是前面介紹的號(hào)段模式的改進(jìn)，可以引用美團(tuán)技術(shù)博客的介紹：

第一種 Leaf-segment 方案，在使用數(shù)據(jù)庫(kù)的方案上，做了如下改變：

原方案每次獲取 ID 都得讀寫一次數(shù)據(jù)庫(kù)，造成數(shù)據(jù)庫(kù)壓力大。改為利用 proxy server 批量獲取 ，每次獲取一個(gè) segment（step 決定大小）號(hào)段的值。用完之后再去數(shù)據(jù)庫(kù)獲取新的號(hào)段，可以大大減輕數(shù)據(jù)庫(kù)的壓力；

各個(gè)業(yè)務(wù)不同的發(fā)號(hào)需求用 biz_tag 字段來(lái)區(qū)分，每個(gè) biz-tag 的 ID 獲取相互隔離，互不影響。如果以后有性能需求需要對(duì)數(shù)據(jù)庫(kù)擴(kuò)容，不需要上述描述的復(fù)雜的擴(kuò)容操作，只需要對(duì) biz_tag 分庫(kù)分表就行。

表結(jié)構(gòu)設(shè)計(jì)：

>+-------------+--------------+------+-----+-------------------+-----------------------------+
|Field|Type|Null|Key|Default|Extra|
+-------------+--------------+------+-----+-------------------+-----------------------------+
|biz_tag|varchar(128)|NO|PRI|||
|max_id|bigint(20)|NO||1||
|step|int(11)|NO||NULL||
|desc|varchar(256)|YES||NULL||
|update_time|timestamp|NO||CURRENT_TIMESTAMP|onupdateCURRENT_TIMESTAMP|
+-------------+--------------+------+-----+-------------------+-----------------------------+

Leafsnowflake 方案

Leafsnowflake 是在雪花算法上改進(jìn)來(lái)的，引用官網(wǎng)技術(shù)博客介紹：

Leaf-snowflake 方案完全沿用 Snowflake 方案的 bit 位設(shè)計(jì)，即是“1+41+10+12”的方式組裝 ID 號(hào)。對(duì)于 workerID 的分配，當(dāng)服務(wù)集群數(shù)量較小的情況下，完全可以手動(dòng)配置。Leaf 服務(wù)規(guī)模較大，手動(dòng)配置成本太高。所以使用 Zookeeper 持久順序節(jié)點(diǎn)的特性自動(dòng)對(duì) Snowflake 節(jié)點(diǎn)配置 wokerID。

Leaf-snowflake 是按照下面幾個(gè)步驟啟動(dòng)的：

啟動(dòng) Leaf-snowflake 服務(wù)，連接 Zookeeper，在 leaf_forever 父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊(cè)過(guò)（是否有該順序子節(jié)點(diǎn)）；

如果有注冊(cè)過(guò)直接取回自己的 workerID（Zookeeper 順序節(jié)點(diǎn)生成的int類型ID號(hào)），啟動(dòng)服務(wù)；

如果沒(méi)有注冊(cè)過(guò)，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)。創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的 workerID 號(hào)，啟動(dòng)服務(wù)。

這種方案解決了前面提到的雪花算法的缺陷。官網(wǎng)沒(méi)解釋，不過(guò) Leafsnowflake 對(duì)其進(jìn)行改進(jìn)，官網(wǎng)的流程圖。

3.8 滴滴 Tinyid

Tinyid 是用 Java 開發(fā)的一款分布式 ID 生成系統(tǒng)，基于數(shù)據(jù)庫(kù)號(hào)段算法實(shí)現(xiàn)。Tinyid 擴(kuò)展了 leaf-segment 算法，支持了多數(shù)據(jù)庫(kù)和 tinyid-client。

Tinyid 也是基于號(hào)段算法實(shí)現(xiàn)，系統(tǒng)實(shí)現(xiàn)圖如下：

優(yōu)點(diǎn) ：方便集成，有成熟的方案和實(shí)現(xiàn)；

缺點(diǎn) ：依賴 DB 穩(wěn)定性，需要采用集群主從備份的方式提高 DB 可用性。

審核編輯：劉清