在業務開發中，大量場景需要唯一ID來進行辨別：使用者需要唯一身份辨別、商品需要唯一辨別、消息需要唯一辨別、事件需要唯一辨別等，都需要全局唯一ID，尤其是複雜的分布式業務場景中全局唯一ID更為重要。
那麼，分布式唯一ID有哪些特性或要求呢？
① 唯一性：生成的ID全局唯一，在特定範圍内沖突機率極小。
② 有序性：生成的ID按某種規則有序，便于資料庫插入及排序。
③ 可用性：可保證高并發下的可用性, 確定任何時候都能正确的生成ID。
④ 自主性：分布式環境下不依賴中心認證即可自行生成ID。
⑤ 安全性：不暴露系統和業務的資訊, 如：訂單數,使用者數等。
分布式唯一ID有哪些生成方法呢？
總的來說，大概有三大類方法，分别是：資料庫自增ID、UUID生成、snowflake雪花算法。
下面分别說下這三大類及其優化方案：
一、資料庫自增ID
核心思想：使用資料庫的id自增政策(如: Mysql的auto_increment)。
優點：
① 簡單，天然有序。
缺點：
① 并發性不好。
② 資料庫寫壓力大。
③ 資料庫故障後不可使用。
④ 存在數量洩露風險。
針對以上缺點，有以下幾種優化方案：
資料庫水準拆分，設定不同的初始值和相同的自增步長
核心思想：将資料庫進行水準拆分，每個資料庫設定不同的初始值和相同的自增步長。
如圖所示，可保證每台資料庫生成的ID是不沖突的，但這種固定步長的方式也會帶來擴容的問題，很容易想到當擴容時會出現無ID初始值可分的窘境，解決方案有：
① 根據擴容考慮決定步長。
② 增加其他位标記區分擴容。
這其實都是在需求與方案間的權衡，根據需求來選擇最适合的方式。
2. 批量緩存自增ID
核心思想：如果使用單台機器做ID生成，可以避免固定步長帶來的擴容問題(方案1的缺點)。
具體做法是：每次批量生成一批ID給不同的機器去慢慢消費，這樣資料庫的壓力也會減小到N分之一，且故障後可堅持一段時間。
如圖所示，但這種做法的缺點是伺服器重新開機、單點故障會造成ID不連續。
還是那句話，沒有最好的方案，隻有最适合的方案。
3. Redis生成ID
核心思想：Redis的所有指令操作都是單線程的，本身提供像 incr 和 increby 這樣的自增原子指令，是以能保證生成的 ID 肯定是唯一有序的。
優點：
① 不依賴于資料庫，靈活友善，且性能優于資料庫。
② 數字ID天然排序，對分頁或者需要排序的結果很有幫助。
缺點：
① 如果系統中沒有Redis，還需要引入新的元件，增加系統複雜度。
② 需要編碼和配置的工作量比較大。
優化方案：
考慮到單節點的性能瓶頸，可以使用 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
優點：
① 本地生成，沒有網絡消耗，生成簡單，沒有高可用風險。
缺點：
① 不易于存儲：UUID太長，16位元組128位，通常以36長度的字元串表示，很多場景不适用。
② 資訊不安全：基于MAC位址生成UUID的算法可能會造成MAC位址洩露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
③ 無序查詢效率低：由于生成的UUID是無序不可讀的字元串，是以其查詢效率低。
◆ 到目前為止業界一共有5種方式生成UUID：
①版本1 - 基于時間的UUID(date-time & MAC address)：
規則：主要依賴目前的時間戳及機器mac位址，是以可以保證全球唯一性。
優點：能基本保證全球唯一性。
缺點：使用了Mac位址，是以會暴露Mac位址和生成時間。
②版本2 - 分布式安全的UUID(date-time & group/user id)：
規則：将版本1的時間戳前四位換為POSIX的UID或GID，很少使用。
優點：能保證全球唯一性。
缺點：很少使用，常用庫基本沒有實作。
③版本3 - 基于名字空間的UUID-MD5版(MD5 hash & namespace)：
規則：基于指定的名字空間/名字生成MD5散列值得到，标準不推薦。
優點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重複。
缺點：MD5碰撞問題，隻用于向後相容，後續不再使用。
④版本4 - 基于随機數的UUID(pseudo-random number)：
規則：基于随機數或僞随機數生成。
優點：實作簡單。
缺點：重複幾率可計算。機率也與随機數産生器的品質有關。若要避免重複機率提高，必須要使用基于密碼學上的強僞随機數産生器來生成值才行。
⑤版本5 - 基于名字空間的UUID-SHA1版(SHA-1 hash & namespace)：
規則：将版本3的雜湊演算法改為SHA1。
優點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重複。
缺點：SHA1計算相對耗時。
總得來說：
①版本 1/2 适用于需要高度唯一性且無需重複的場景。
②版本 3/5 适用于一定範圍内唯一且需要或可能會重複生成UUID的環境下。
③版本 4 适用于對唯一性要求不太嚴格且追求簡單的場景。
相關僞代碼如下：
三、雪花算法
核心思想：把64-bit分别劃分成多段，分開來标示機器、時間、某一并發序列等，進而使每台機器及同一機器生成的ID都是互不相同。
PS：這種結構是雪花算法提出者Twitter的分法，但實際上這種算法使用可以很靈活，根據自身業務的并發情況、機器分布、使用年限等，可以自由地重新決定各部分的位數，進而增加或減少某部分的量級。比如：百度的UidGenerator、美團的Leaf等，都是基于雪花算法做一些适合自身業務的變化。
下面介紹雪花算法的幾種不同優化方案：
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個節點(即1 << 10 = 1024)。超過這個數量，生成的ID就有可能會沖突。
④12位序列：毫秒内的計數，12位的計數順序号支援每個節點每毫秒(同一機器，同一時間截)産生4096個ID序号(即1 << 12 = 4096)。
PS：全部結構辨別(1+41+10+12=64)加起來剛好64位，剛好湊成一個Long型。
優點：
①整體上按照時間按時間趨勢遞增，後續插入索引樹的時候性能較好。
②整個分布式系統内不會産生ID碰撞(由資料中心辨別ID、機器辨別ID作區分)
③本地生成，且不依賴資料庫(或第三方元件)，沒有網絡消耗，是以效率高(每秒能夠産生26萬ID左右)。
缺點：
①由于雪花算法是強依賴于時間的，在分布式環境下，如果發生時鐘回撥，很可能會引起ID重複、ID亂序、服務會處于不可用狀态等問題。
解決方案有：
a. 将ID生成交給少量伺服器，并關閉時鐘同步。
b. 直接報錯，交給上層業務處理。
c. 如果回撥時間較短，在耗時要求内，比如5ms，那麼等待回撥時長後再進行生成。
d. 如果回撥時間很長，那麼無法等待，可以勻出少量位(1~2位)作為回撥位，一旦時鐘回撥，将回撥位加1，可得到不一樣的ID，2位回撥位允許标記3次時鐘回撥，基本夠使用。如果超出了，可以再選擇抛出異常。
Twitter_SnowFlake的源代碼(JAVA版)：
核心運算邏輯(右移運算&位運算)： (timestamp << 22) | (datacenterId << 17) | (workerId << 12) | sequence;
2. Mongo的ObjectId算法
核心思想是：使用12位元組(24bit)的BSON 類型字元串作為ID，并将所占的24bit 劃分成多段。
其結構如下：
說明：
①4位元組(8位)timeStamp：UNIX時間戳(精确到秒)。
②3位元組(6位)machine：所在主機的唯一辨別符(一般是機器主機名的散列值)。
③2位元組(4位)pid：同一台機器不同的程序産生objectid的程序辨別符 。
④3位元組(6位)increment：由一個随機數開始的計數器生成的自動增加的值，用來確定在同一秒内産生的objectid也不會發現沖突，允許256^3(16777216)條記錄的唯一性。
如：ObjectID(為了友善檢視，每部分使用“-”分隔)格式為：5dba76a3-d2c366-7f99-57dfb0
①timeStamp：5dba76a3(對應十進制為：1572501155)。
②machine：d2c366(對應十進制為：13812582)。
③pid：7f99(對應十進制為：32665)。
④increment：57dfb0(對應十進制為：5758896)。
優點：
①本地生成，沒有網絡消耗，生成簡單，沒有高可用風險。
②所生成的ID包含時間資訊，可以提取時間資訊。
缺點：
①不易于存儲：12位元組24位長度的字元串表示，很多場景不适用。
◆ 新版ObjectId中“機器辨別碼+程序号” 改為用随機數作為機器辨別和程序号的值
mark：從 MongoDB 3.4 開始(最早釋出于 2016 年 12 月)，ObjectId 的設計被修改了，中間 5 位元組的值由原先的 “機器辨別碼+程序号” 改為用随機數作為機器辨別和程序号的值。
那問題來了，為什麼不繼續使用“機器辨別+程序号”呢？
問題就在于，在這個實體機鮮見，虛拟機、雲主機、容器橫行的時代，機器辨別和程序号不太可靠。
①機器辨別碼：
ObjectId 的機器辨別碼是取系統 hostname 哈希值的前幾位。那麼問題來了，準備了幾台虛拟機，hostname 都是預設的 localhost，誰都想着這玩意兒能有什麼用，還得刻意給不同機器起不同的 hostname？ 此外，hostname 在容器、雲主機裡一般預設就是随機數，也不會檢查同一叢集裡是否有hostname 重名。
②程序号：
這個問題就更大了，要知道，容器内的程序擁有自己獨立的程序空間，在這個空間裡隻用它自己這一個程序(以及它的子程序)，是以它的程序号永遠都是 1。也就是說，如果某個服務(既可以是 mongo 執行個體也可以是 mongo 用戶端)是使用容器部署的，無論部署多少個執行個體，在這個服務上生成的 ObjectId，第八第九個位元組恒為 0000 0001，相當于說這兩個位元組廢了。
綜上，與其使用一個固定值來“區分不同程序執行個體”，且這個固定值還是人類随意設定或随機生成的 hostname 加上一個可能恒為 1 的程序号，倒不如每次都随機生成一個新值。
可見，這是平台層面的架構變動影響了應用層面的設計方案，随着雲、容器的繼續發展，這樣的故事還會繼續上演。
1)舊版：使用主機名的散列值作用machine、使用程序辨別符作為pid
Java版代碼：
2)新版：使用随機數作為machine、pid的值
Java版代碼：
3. 百度UidGenerator算法
UidGenerator是百度開源的分布式ID生成器，是基于snowflake算法的實作，看起來感覺還行，但是需要借助資料庫，配置起來比較複雜。
具體可以參考官網說明：https://github.com/baidu/uid-...
4. 美團Leaf算法
Leaf 是美團開源的分布式ID生成器，能保證全局唯一性、趨勢遞增、單調遞增、資訊安全，裡面也提到了幾種分布式方案的對比，但也需要依賴關系資料庫、Zookeeper等中間件。
具體可以參考官網說明： https://tech.meituan.com/2017...
小結
這篇文章和大家分享了全局id生成服務的幾種常用方案，同時對比了各自的優缺點和适用場景。在實際工作中，大家可以結合自身業務和系統架構體系進行合理選型。