分布式唯一ID的幾種生成方案

作者：稻哥說編程
鏈接：https://www.jianshu.com/p/4ba1c5e8c185

在業(yè)務開發(fā)中，大量場景需要唯一ID來進行標識：用戶需要唯一身份標識、商品需要唯一標識、消息需要唯一標識、事件需要唯一標識等，都需要全局唯一ID，尤其是復雜的分布式業(yè)務場景中全局唯一ID更為重要。

那么，分布式唯一ID有哪些特性或要求呢？ ① 唯一性：生成的ID全局唯一，在特定范圍內沖突概率極小。
② 有序性：生成的ID按某種規(guī)則有序，便于數據庫插入及排序。
③ 可用性：可保證高并發(fā)下的可用性, 確保任何時候都能正確的生成ID。
④ 自主性：分布式環(huán)境下不依賴中心認證即可自行生成ID。
⑤ 安全性：不暴露系統(tǒng)和業(yè)務的信息, 如：訂單數,用戶數等。

分布式唯一ID有哪些生成方法呢？ 總的來說，大概有三大類方法，分別是：數據庫自增ID、UUID生成、snowflake雪花算法。

一、數據庫自增ID

核心思想：使用數據庫的id自增策略（如: Mysql的auto_increment）。

優(yōu)點：
① 簡單，天然有序。

缺點：
① 并發(fā)性不好。
② 數據庫寫壓力大。
③ 數據庫故障后不可使用。
④ 存在數量泄露風險。

針對以上缺點，有以下幾種優(yōu)化方案：

1. 數據庫水平拆分，設置不同的初始值和相同的自增步長

核心思想：將數據庫進行水平拆分，每個數據庫設置不同的初始值和相同的自增步長。

如圖所示，可保證每臺數據庫生成的ID是不沖突的，但這種固定步長的方式也會帶來擴容的問題，很容易想到當擴容時會出現無ID初始值可分的窘境。解決方案有：
① 根據擴容考慮決定步長。
② 增加其他位標記區(qū)分擴容。
這其實都是在需求與方案間的權衡，根據需求來選擇最適合的方式。

2. 批量緩存自增ID

核心思想：如果使用單臺機器做ID生成，可以避免固定步長帶來的擴容問題（方案1的缺點）。

具體做法是：每次批量生成一批ID給不同的機器去慢慢消費，這樣數據庫的壓力也會減小到N分之一，且故障后可堅持一段時間。

如圖所示，但這種做法的缺點是服務器重啟、單點故障會造成ID不連續(xù)。
還是那句話，沒有最好的方案，只有最適合的方案。

3. Redis生成ID

核心思想：Redis的所有命令操作都是單線程的，本身提供像 incr 和 increby 這樣的自增原子命令，所以能保證生成的 ID 肯定是唯一有序的。

優(yōu)點：
① 不依賴于數據庫，靈活方便，且性能優(yōu)于數據庫。
② 數字ID天然排序，對分頁或者需要排序的結果很有幫助。

缺點：
① 如果系統(tǒng)中沒有Redis，還需要引入新的組件，增加系統(tǒng)復雜度。
② 需要編碼和配置的工作量比較大。

優(yōu)化方案：
考慮到單節(jié)點的性能瓶頸，可以使用 Redis 集群來獲取更高的吞吐量，并利用上面的方案（①數據庫水平拆分，設置不同的初始值和相同的步長；②批量緩存自增ID）來配置集群。

PS：比較適合使用 Redis 來生成每天從0開始的流水號。比如：“訂單號=日期+當日自增長號”，則可以每天在Redis中生成一個Key，使用INCR進行累加。

二、UUID生成

核心思想：結合機器的網卡（基于名字空間/名字的散列值MD5/SHA1）、當地時間（基于時間戳&時鐘序列）、一個隨記數來生成UUID。

其結構如下：
aaaaaaaa-bbbb-cccc-dddd-eeeeeeeeeeee（即包含32個16進制數字，以連字號-分為五段，最終形成“8-4-4-4-12”的36個字符的字符串，即32個英數字母+4個連字號）。
例如：550e8400-e29b-41d4-a716-446655440000

優(yōu)點：
① 本地生成，沒有網絡消耗，生成簡單，沒有高可用風險。

缺點：
① 不易于存儲：UUID太長，16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用。
② 信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
③ 無序查詢效率低：由于生成的UUID是無序不可讀的字符串，所以其查詢效率低。

◆ 到目前為止業(yè)界一共有5種方式生成UUID：

①版本1 - 基于時間的UUID（date-time & MAC address）：
規(guī)則：主要依賴當前的時間戳及機器mac地址，因此可以保證全球唯一性。
優(yōu)點：能基本保證全球唯一性。
缺點：使用了Mac地址，因此會暴露Mac地址和生成時間。

②版本2 - 分布式安全的UUID（date-time & group/user id）：
規(guī)則：將版本1的時間戳前四位換為POSIX的UID或GID，很少使用。
優(yōu)點：能保證全球唯一性。
缺點：很少使用，常用庫基本沒有實現。

③版本3 - 基于名字空間的UUID-MD5版（MD5 hash & namespace）：
規(guī)則：基于指定的名字空間/名字生成MD5散列值得到，標準不推薦。
優(yōu)點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復。
缺點：MD5碰撞問題，只用于向后兼容，后續(xù)不再使用。

④版本4 - 基于隨機數的UUID（pseudo-random number）：
規(guī)則：基于隨機數或偽隨機數生成。
優(yōu)點：實現簡單。
缺點：重復幾率可計算。機率也與隨機數產生器的質量有關。若要避免重復機率提高，必須要使用基于密碼學上的強偽隨機數產生器來生成值才行。

⑤版本5 - 基于名字空間的UUID-SHA1版（SHA-1 hash & namespace）：
規(guī)則：將版本3的散列算法改為SHA1。
優(yōu)點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復。
缺點：SHA1計算相對耗時。

總得來說：
①版本 1/2 適用于需要高度唯一性且無需重復的場景。
②版本 3/5 適用于一定范圍內唯一且需要或可能會重復生成UUID的環(huán)境下。
③版本 4 適用于對唯一性要求不太嚴格且追求簡單的場景。

相關偽代碼如下：

三、雪花算法

核心思想：把64-bit分別劃分成多段，分開來標示機器、時間、某一并發(fā)序列等，從而使每臺機器及同一機器生成的ID都是互不相同。

PS：這種結構是雪花算法提出者Twitter的分法，但實際上這種算法使用可以很靈活，根據自身業(yè)務的并發(fā)情況、機器分布、使用年限等，可以自由地重新決定各部分的位數，從而增加或減少某部分的量級。比如：百度的UidGenerator、美團的Leaf等，都是基于雪花算法做一些適合自身業(yè)務的變化。

下面介紹雪花算法的幾種不同優(yōu)化方案：

1. Twitter的snowflake算法

核心思想是：采用bigint（64bit）作為id生成類型，并將所占的64bit 劃分成多段。

其結構如下：

說明：
①1位標識：由于long基本類型在Java中是帶符號的，最高位是符號位，正數是0，負數是1，所以id一般是正數，最高位是0。

②41位時間截(毫秒級）：需要注意的是，41位時間截不是存儲當前時間的時間截，而是存儲時間截的差值（當前時間截 - 開始時間截）得到的值，這里的開始時間截，一般是指我們的id生成器開始使用的時間截，由我們的程序來指定。41位的毫秒時間截，可以使用69年（即T =（1L << 41）/（1000 * 60 * 60 * 24 * 365）= 69）。

③10位的數據機器位：包括5位數據中心標識Id（datacenterId）、5位機器標識Id(workerId)，最多可以部署1024個節(jié)點（即1 << 10 = 1024）。超過這個數量，生成的ID就有可能會沖突。

④12位序列：毫秒內的計數，12位的計數順序號支持每個節(jié)點每毫秒（同一機器，同一時間截）產生4096個ID序號（即1 << 12 = 4096）。

PS：全部結構標識（1+41+10+12=64）加起來剛好64位，剛好湊成一個Long型。

優(yōu)點：
①整體上按照時間按時間趨勢遞增，后續(xù)插入索引樹的時候性能較好。
②整個分布式系統(tǒng)內不會產生ID碰撞（由數據中心標識ID、機器標識ID作區(qū)分）。
③本地生成，且不依賴數據庫（或第三方組件），沒有網絡消耗，所以效率高（每秒能夠產生26萬ID左右）。

缺點：
①由于雪花算法是強依賴于時間的，在分布式環(huán)境下，如果發(fā)生時鐘回撥，很可能會引起ID重復、ID亂序、服務會處于不可用狀態(tài)等問題。

解決方案有：

a. 將ID生成交給少量服務器，并關閉時鐘同步。
b. 直接報錯，交給上層業(yè)務處理。
c. 如果回撥時間較短，在耗時要求內，比如5ms，那么等待回撥時長后再進行生成。
d. 如果回撥時間很長，那么無法等待，可以勻出少量位（1~2位）作為回撥位，一旦時鐘回撥，將回撥位加1，可得到不一樣的ID，2位回撥位允許標記3次時鐘回撥，基本夠使用。如果超出了，可以再選擇拋出異常。

2. Mongo的ObjectId算法

核心思想是：使用12字節(jié)（24bit）的BSON 類型字符串作為ID，并將所占的24bit 劃分成多段。

說明：
①4字節(jié)（8位）timeStamp：UNIX時間戳（精確到秒)。
②3字節(jié)（6位）machine：所在主機的唯一標識符（一般是機器主機名的散列值）。
③2字節(jié)（4位）pid：同一臺機器不同的進程產生objectid的進程標識符 。
④3字節(jié)（6位）increment：由一個隨機數開始的計數器生成的自動增加的值，用來確保在同一秒內產生的objectid也不會發(fā)現沖突，允許256^3（16777216）條記錄的唯一性。

如：ObjectID（為了方便查看，每部分使用“-”分隔）格式為：5dba76a3-d2c366-7f99-57dfb0
①timeStamp：5dba76a3（對應十進制為：1572501155）。
②machine：d2c366（對應十進制為：13812582）。
③pid：7f99（對應十進制為：32665）。
④increment：57dfb0（對應十進制為：5758896）。

優(yōu)點：
①本地生成，沒有網絡消耗，生成簡單，沒有高可用風險。
②所生成的ID包含時間信息，可以提取時間信息。

缺點：
①不易于存儲：12字節(jié)24位長度的字符串表示，很多場景不適用。

◆ 新版ObjectId中“機器標識碼+進程號” 改為用隨機數作為機器標識和進程號的值

mark：從 MongoDB 3.4 開始（最早發(fā)布于 2016 年 12 月），ObjectId 的設計被修改了，中間 5 字節(jié)的值由原先的 “機器標識碼+進程號” 改為用隨機數作為機器標識和進程號的值。

那問題來了，為什么不繼續(xù)使用“機器標識+進程號”呢？

問題就在于，在這個物理機鮮見，虛擬機、云主機、容器橫行的時代，機器標識和進程號不太可靠。

①機器標識碼：
ObjectId 的機器標識碼是取系統(tǒng) hostname 哈希值的前幾位。那么問題來了，準備了幾臺虛擬機，hostname 都是默認的 localhost，誰都想著這玩意兒能有什么用，還得刻意給不同機器起不同的 hostname？此外，hostname 在容器、云主機里一般默認就是隨機數，也不會檢查同一集群里是否有hostname 重名。

②進程號：
這個問題就更大了，要知道，容器內的進程擁有自己獨立的進程空間，在這個空間里只用它自己這一個進程（以及它的子進程），所以它的進程號永遠都是 1。也就是說，如果某個服務（既可以是 mongo 實例也可以是 mongo 客戶端）是使用容器部署的，無論部署多少個實例，在這個服務上生成的 ObjectId，第八第九個字節(jié)恒為 0000 0001，相當于說這兩個字節(jié)廢了。

綜上，與其使用一個固定值來“區(qū)分不同進程實例”，且這個固定值還是人類隨意設置或隨機生成的 hostname 加上一個可能恒為 1 的進程號，倒不如每次都隨機生成一個新值。

可見，這是平臺層面的架構變動影響了應用層面的設計方案，隨著云、容器的繼續(xù)發(fā)展，這樣的故事還會繼續(xù)上演。

**1）舊版：使用主機名的散列值作用machine、使用進程標識符作為pid **

2）新版：使用隨機數作為machine、pid的值

3. 百度UidGenerator算法 UidGenerator是百度開源的分布式ID生成器，是基于snowflake算法的實現，看起來感覺還行，但是需要借助數據庫，配置起來比較復雜。
具體可以參考官網說明：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

4. 美團Leaf算法 Leaf 是美團開源的分布式ID生成器，能保證全局唯一性、趨勢遞增、單調遞增、信息安全，里面也提到了幾種分布式方案的對比，但也需要依賴關系數據庫、Zookeeper等中間件。
具體可以參考官網說明：https://tech.meituan.com/2017/04/21/mt-leaf.html

小結：這篇文章和大家分享了全局id生成服務的幾種常用方案，同時對比了各自的優(yōu)缺點和適用場景。在實際工作中，大家可以結合自身業(yè)務和系統(tǒng)架構體系進行合理選型。

源代碼請移步到博主的CSDN博客（猿碼之家） ：https://blog.csdn.net/liudao51/article/details/103007892