唯一ID生成演算法剖析，看看這篇就夠了

2019 年 10 月 31 日
筆記

本文轉載自騰訊技術工程

引

在業務開發中，大量場景需要唯一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。各種方案都有其優缺點，技術的使用沒有絕對的好壞之分，主要在於是否適合使用場景：

要求生成全局唯一且不會重複ID，不關心順序 —— 使用基於時間的UUID（如遊戲聊天室中不同用戶的身份ID）
要求生成唯一ID，具有名稱不可變性，可重複生成 —— 使用基於名稱哈希的UUID（如基於不可變資訊生成的用戶ID，若不小心刪除，仍可根據資訊重新生成同一ID）
要求生成有序且自然增長的ID —— 使用資料庫自增ID（如各業務操作流水ID，高並發下可參考優化方案）
要求生成數值型無序定長ID —— 使用雪花演算法（如對存儲空間、查詢效率、傳輸數據量等有較高要求的場景）

對於最初我們定義的唯一ID特性，各方案的對比如下：

從衝突率、QPS和演算法時間複雜度來比較的話：

參考

UUID演算法分析

關於UUID的二三事

UUID百度百科

UUID唯一資源命名空間的來龍去脈

UUID是如何保證唯一性的？

如果再有人問你分散式 ID，這篇文章丟給他

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

UidGenerator-百度

Leaf——美團點評分散式ID生成系統

分散式系統：Lamport 邏輯時鐘