本文轉載自騰訊技術工程

引

在業務開發中，大量場景需要唯一ID來進行標識：用戶需要唯一身份標識；商品需要唯一標識；消息需要唯一標識；事件需要唯一標識…等等，都需要全局唯一ID，尤其是分布式場景下。

唯一ID有哪些特性或者說要求呢？按照我的分析有以下特性：

唯一性：生成的ID全局唯一，在特定范圍內沖突概率極小
有序性：生成的ID按某種規則有序，便于數據庫插入及排序
可用性：可保證高并發下的可用性
自主性：分布式環境下不依賴中心認證即可自行生成ID
安全性：不暴露系統和業務的信息

一般來說，常用的唯一ID生成方法有這些：

UUID：

基于時間戳&時鐘序列生成
基于名字空間/名字的散列值 (MD5/SHA1) 生成
基于隨機數生成

數據庫自增ID：

多臺機器不同初始值、同步長自增
批量緩存自增ID

雪花算法

時鐘回撥解決方案
本文便分別對這些算法進行講解及分析。

UUID

UUID全稱為：Universally Unique IDentifier（通用唯一識別碼），有的地方也稱作GUID（Globally Unique IDentifier），實際上GUID指微軟對于UUID標準的實現的實現。

UUID算法的目的是為了生成某種形式的全局唯一ID來標識系統中的任一元素，尤其在分布式環境下，該ID需要不依賴中心認證即可自動生成全局唯一ID。

其優勢有：

無需網絡，單機自行生成
速度快，QPS高（支持100ns級并發）
各語言均有相應實現庫供直接使用

而缺點為：

String存儲，占空間，DB查詢及索引效率低
無序，可讀性差
根據實現方式不同可能泄露信息

1.UUID的格式

UUID的標準形式為32個十六進制數組成的字符串，且分隔為五個部分，如：

467e8542-2275-4163-95d6-7adc205580a9

各部分的數字個數為：8-4-4-4-12

2.UUID版本

根據需要不同，標準提供了不同的UUID版本以供使用，分別對應于不同的UUID生成規則：

版本1 - 基于時間的UUID：主要依賴當前的時間戳及機器mac地址，因此可以保證全球唯一性
版本2 - 分布式安全的UUID：將版本1的時間戳前四位換為POSIX的UID或GID，很少使用
版本3 - 基于名字空間的UUID（MD5版）：基于指定的名字空間/名字生成MD5散列值得到，標準不推薦
版本4 - 基于隨機數的UUID：基于隨機數或偽隨機數生成，
版本5 - 基于名字空間的UUID（SHA1版）：將版本3的散列算法改為SHA1

3.UUID各版本優缺點

版本1 - 基于時間的UUID：

優點：能基本保證全球唯一性
缺點：使用了Mac地址，因此會暴露Mac地址和生成時間

版本2 - 分布式安全的UUID：

優點：能保證全球唯一性
缺點：很少使用，常用庫基本沒有實現

版本3 - 基于名字空間的UUID（MD5版）：

優點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復。
缺點：MD5碰撞問題，只用于向后兼容，后續不再使用

版本4 - 基于隨機數的UUID：

優點：實現簡單
缺點：重復幾率可計算

版本5 - 基于名字空間的UUID（SHA1版）：

優點：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復。
缺點：SHA1計算相對耗時

總得來說：

版本 1/2 適用于需要高度唯一性且無需重復的場景；
版本 3/5 適用于一定范圍內唯一且需要或可能會重復生成UUID的環境下；
版本 4 適用于對唯一性要求不太嚴格且追求簡單的場景。

4.UUID結構及生成規則

以版本1 - 基于時間的UUID為例先梳理UUID的結構：

UUID為32位的十六機制數，因此實際上是16-byte (128-bit)，各位分別為：

時間值：在基于時間的UUID中，時間值是一個60位的整型值，對應UTC的100ns時間間隔計數，因此其支持支持一臺機器每秒生成10M次。在UUID中，將這60位放置到了15~08這8-byte中（除了09位有4-bit的版本號內容）。

版本號：版本號即上文所說的五個版本，在五個版本的UUID中，都總是在該位置標識版本，占據 4-bit，分別以下列數字表示：

因此版本號這一位的取值只會是1,2,3,4,5

變體值：表明所依賴的標準（X表示可以是任意值）：

時鐘序列：在基于時間的UUID中，時鐘序列占據了07~06位的14-bit。不同于時間值，時鐘序列實際上是表示一種邏輯序列，用于標識事件發生的順序。在此，如果前一時鐘序列已知，則可以通過自增來實現時鐘序列值的改變；否則，通過（偽）隨機數來設置。主要用于避免因時間值向未來設置或節點值改變可能導致的UUID重復問題。

節點值：在基于時間的UUID中，節點值占據了05~00的48-bit，由機器的MAC地址構成。如果機器有多個MAC地址，則隨機選其中一個；如果機器沒有MAC地址，則采用（偽）隨機數。

了解了基于時間的UUID結構及生成規則后，再看看其他版本的UUID生成規則：

版本2 - 分布式安全的UUID：

將基于時間的UUID中時間戳前四位換為POSIX的UID或GID，其余保持一致。

版本3/5 - 基于名字空間的UUID (MD5/SHA1)：

將命名空間 (如DNS、URL、OID等) 及名字轉換為字節序列；
通過MD5/SHA1散列算法將上述字節序列轉換為16字節哈希值 (MD5散列不再推薦，SHA1散列的20位只使用其15~00位)；
將哈希值的 3~0 字節置于UUID的15~12位；
將哈希值的 5~4 字節置于UUID的11~10位；
將哈希值的 7~6 字節置于UUID的09~08位，并用相應版本號覆蓋第9位的高4位 (同版本1位置)；
將哈希值的 8 字節置于UUID的07位，并用相應變體值覆蓋其高2位 (同版本1位置)；
將哈希值的 9 字節置于UUID的06位 (原時鐘序列位置)；
將哈希值的 15~10 字節置于UUID的05~00位 (原節點值位置)。

版本4 - 基于隨機數的UUID：

生成16byte隨機值填充UUID。重復機率與隨機數產生器的質量有關。若要避免重復率提高，必須要使用基于密碼學上的假隨機數產生器來生成值才行；
將變體值及版本號填到相應位置。

5.多版本偽碼

// 版本 1 - 基于時間的UUID：gen_uuid { struct uuid uu;
 // 獲取時間戳 get_time(&clock_mid, &uu.time_low); uu.time_mid = (uint16_t) clock_mid; // 時間中間位 uu.time_hi_and_version = ((clock_mid >> 16) & 0x0FFF) | 0x1000; // 時間高位 & 版本號
 // 獲取時鐘序列。在libuuid中，嘗試取時鐘序列+1，取不到則隨機；在Python中直接使用隨機 get_clock(&uu.clock_seq);// 時鐘序列+1 或 隨機數 uu.clock_seq |= 0x8000;// 時鐘序列位 & 變體值
 // 節點值 char node_id[6]; get_node_id(node_id);// 根據mac地址等獲取節點id uu.node = node_id; return uu;}
// 版本4 - 基于隨機數的UUID：gen_uuid { struct uuid uu; uuid_t buf;
 random_get_bytes(buf, sizeof(buf));// 獲取隨機出來的uuid，如libuuid根據進程id、當日時間戳等進行srand隨機
 uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 變體值覆蓋 uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x4000;// 版本號覆蓋 return uu;}
// 版本5 - 基于名字空間的UUID（SHA1版）：gen_uuid(name) { struct uuid uu; uuid_t buf;
 sha_get_bytes(name, buf, sizeof(buf));// 獲取name的sha1散列出來的uuid
 uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 變體值覆蓋 uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x5000;// 版本號覆蓋 return uu;}

（左滑查看完整代碼）

數據庫自增ID

數據庫自增ID可能是大家最熟悉的一種唯一ID生成方式，其具有使用簡單，滿足基本需求，天然有序的優點，但也有缺陷：

并發性不好
數據庫寫壓力大
數據庫故障后不可使用
存在數量泄露風險

因此這里給出兩種優化方案。

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

如圖所示，可保證每臺數據庫生成的ID是不沖突的，但這種固定步長的方式也會帶來擴容的問題，很容易想到當擴容時會出現無ID初始值可分的窘境，解決方案有：

根據擴容考慮決定步長
增加其他位標記區分擴容

這其實都是在需求與方案間的權衡，根據需求來選擇最適合的方式。

2.批量生成一批ID

如果要使用單臺機器做ID生成，避免固定步長帶來的擴容問題，可以每次批量生成一批ID給不同的機器去慢慢消費，這樣數據庫的壓力也會減小到N分之一，且故障后可堅持一段時間。

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

雪花算法

定義一個64bit的數，對指定機器 & 同一時刻 & 某一并發序列，是唯一的，其極限QPS約為400w/s。其格式為：

將64 bit分為了四部分。其中時間戳有時間上限（69年）。機器id只有10位，能記錄1024臺機器，常用前幾位表示數據中心id，后幾位表示數據中心內的機器id。序列號用來對同一個毫秒之內的操作產生不同的ID，最多4095個。

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

由于雪花算法是強依賴于時間的，在分布式環境下，如果發生時鐘回撥，很可能會引起id沖突的問題。解決方案有：

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

方案對比

可以發現，常用的分布式唯一ID生成思路基本是利用一個長串數字或字符串，將其分割成多個部分，分別記錄時間信息、機器/名字信息、隨機信息、序列信息等。時間信息部分決定了該策略能使用的時長，機器/名字信息支持了分布式環境下的獨自生成唯一ID與識別能力，序列信息保證了事件的順序記錄以及同一時間單位下的并發數，而隨機信息則加大了ID整體的不可識別性。

實際上如果現有的方法依然不能滿足，我們完全可以依據自身業務和發展需求，來自行決定使用何種策略生成唯一ID。各種方案都有其優缺點，技術的使用沒有絕對的好壞之分，主要在于是否適合使用場景：