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

1. 為什么需要分布式 ID

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

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

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

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

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

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

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

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

3. 分布式 ID 生成方案

UUID

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

號段模式

Redis 實現(xiàn)

雪花算法（SnowFlake）

百度 Uidgenerator

美團(tuán) Leaf

滴滴 TinyID

3.1 UUID

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 號段模式

這種模式也是現(xiàn)在生成分布式 ID 的一種方法。實現(xiàn)思路是，會從數(shù)據(jù)庫獲取一個號段范圍，比如 [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'號段的布長',
biz_typeint(20)NOTNULLCOMMENT'業(yè)務(wù)類型',
versionint(20)NOTNULLCOMMENT'版本號',
PRIMARYKEY(`id`)
)

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

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

step ：代表號段的步長；

version ：版本號，就像 MVCC 一樣，可以理解為樂觀鎖。

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

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

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

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

3.4 Redis 實現(xiàn)

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

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

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

缺點 ：需要依賴 Redis 來實現(xiàn)，系統(tǒng)需要引入 Redis 組件。

3.5 雪花算法（SnowFlake）

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

第一部分：第一位占用 1 bit，始終是 0，是一個符號位，不使用；

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

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

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

優(yōu)缺點：

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

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

3.6 百度 Uidgenerator

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

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

UidGenerator 是 Java 實現(xiàn)的, 基于 Snowflake 算法的唯一 ID 生成器。UidGenerator 以組件形式工作在應(yīng)用項目中，支持自定義 workerId 位數(shù)和初始化策略，從而適用于 docker 等虛擬化環(huán)境下實例自動重啟、漂移等場景。在實現(xiàn)上, UidGenerator 通過借用未來時間來解決 sequence 天然存在的并發(fā)限制；采用 RingBuffer 來緩存已生成的 UID，并行化 UID 的生產(chǎn)和消費，同時對 CacheLine 補齊。避免了由 RingBuffer 帶來的硬件級「偽共享」問題. 最終單機 QPS 可達(dá) 600 萬。

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

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

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

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

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

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

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

3.7 美團(tuán) Leaf

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

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

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

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

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

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

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

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

>+-------------+--------------+------+-----+-------------------+-----------------------------+
|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)來的，引用官網(wǎng)技術(shù)博客介紹：

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

Leaf-snowflake 是按照下面幾個步驟啟動的：

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

如果有注冊過直接取回自己的 workerID（Zookeeper 順序節(jié)點生成的int類型ID號），啟動服務(wù)；

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

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

3.8 滴滴 Tinyid

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

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

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

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

審核編輯：劉清