引在業(yè)務開發(fā)中，大量場景需要唯一ID來進行標識：用戶需要唯一身份標識；商品需要唯一標識；消息需要唯一標識；事件需要唯一標識…等等，都需要全局唯一ID，尤其是分布式場景下。唯一ID有哪些特性或者說要求呢？按照我的分析有以下特性：

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

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

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

數(shù)據庫自增ID：

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

雪花算法

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

UUIDUUID全稱為：Universally Unique IDentifier(通用唯一識別碼)，有的地方也稱作GUID(Globally Unique IDentifier)，實際上GUID指微軟對于UUID標準的實現(xiàn)的實現(xiàn)。UUID算法的目的是為了生成某種形式的全局唯一ID來標識系統(tǒng)中的任一元素，尤其在分布式環(huán)境下，該ID需要不依賴中心認證即可自動生成全局唯一ID。其優(yōu)勢有：

• 無需網絡，單機自行生成
• 速度快，QPS高(支持100ns級并發(fā))
• 各語言均有相應實現(xiàn)庫供直接使用

而缺點為：

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

1.UUID的格式

UUID的標準形式為32個十六進制數(shù)組成的字符串，且分隔為五個部分，如：467e8542-2275-4163-95d6-7adc205580a9各部分的數(shù)字個數(shù)為：8-4-4-4-12

2.UUID版本

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

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

3.UUID各版本優(yōu)缺點

版本1 - 基于時間的UUID：

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

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

• 優(yōu)點：能保證全球唯一性
• 缺點：很少使用，常用庫基本沒有實現(xiàn)

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

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

版本4 - 基于隨機數(shù)的UUID：

• 優(yōu)點：實現(xiàn)簡單
• 缺點：重復幾率可計算

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

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

總得來說：

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

4.UUID結構及生成規(guī)則

以版本1 - 基于時間的UUID為例先梳理UUID的結構：UUID為32位的十六機制數(shù)，因此實際上是16-byte (128-bit)，各位分別為：時間值：在基于時間的UUID中，時間值是一個60位的整型值，對應UTC的100ns時間間隔計數(shù)，因此其支持支持一臺機器每秒生成10M次。在UUID中，將這60位放置到了15~08這8-byte中(除了09位有4-bit的版本號內容)。版本號：版本號即上文所說的五個版本，在五個版本的UUID中，都總是在該位置標識版本，占據 4-bit，分別以下列數(shù)字表示：因此版本號這一位的取值只會是1,2,3,4,5變體值：表明所依賴的標準(X表示可以是任意值)：時鐘序列：在基于時間的UUID中，時鐘序列占據了07~06位的14-bit。不同于時間值，時鐘序列實際上是表示一種邏輯序列，用于標識事件發(fā)生的順序。在此，如果前一時鐘序列已知，則可以通過自增來實現(xiàn)時鐘序列值的改變；否則，通過(偽)隨機數(shù)來設置。主要用于避免因時間值向未來設置或節(jié)點值改變可能導致的UUID重復問題。節(jié)點值：在基于時間的UUID中，節(jié)點值占據了05~00的48-bit，由機器的MAC地址構成。如果機器有多個MAC地址，則隨機選其中一個；如果機器沒有MAC地址，則采用(偽)隨機數(shù)。了解了基于時間的UUID結構及生成規(guī)則后，再看看其他版本的UUID生成規(guī)則：

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

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

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

將命名空間 (如DNS、URL、OID等) 及名字轉換為字節(jié)序列；

通過MD5/SHA1散列算法將上述字節(jié)序列轉換為16字節(jié)哈希值 (MD5散列不再推薦，SHA1散列的20位只使用其15~00位)；

將哈希值的 3~0 字節(jié)置于UUID的15~12位；

將哈希值的 5~4 字節(jié)置于UUID的11~10位；

將哈希值的 7~6 字節(jié)置于UUID的09~08位，并用相應版本號覆蓋第9位的高4位 (同版本1位置)；

將哈希值的 8 字節(jié)置于UUID的07位，并用相應變體值覆蓋其高2位 (同版本1位置)；

將哈希值的 9 字節(jié)置于UUID的06位 (原時鐘序列位置)；

將哈希值的 15~10 字節(jié)置于UUID的05~00位 (原節(jié)點值位置)。

• 版本4 - 基于隨機數(shù)的UUID：

生成16byte隨機值填充UUID。重復機率與隨機數(shù)產生器的質量有關。若要避免重復率提高，必須要使用基于密碼學上的假隨機數(shù)產生器來生成值才行；

將變體值及版本號填到相應位置。

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 或 隨機數(shù) uu.clock_seq |= 0x8000;// 時鐘序列位 & 變體值 // 節(jié)點值 char node_id[6]; get_node_id(node_id);// 根據mac地址等獲取節(jié)點id uu.node = node_id; return uu;}// 版本4 - 基于隨機數(shù)的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;}

(左滑查看完整代碼)

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

• 并發(fā)性不好
• 數(shù)據庫寫壓力大
• 數(shù)據庫故障后不可使用
• 存在數(shù)量泄露風險

因此這里給出兩種優(yōu)化方案。

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

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

• 根據擴容考慮決定步長
• 增加其他位標記區(qū)分擴容

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

2.批量生成一批ID

如果要使用單臺機器做ID生成，避免固定步長帶來的擴容問題，可以每次批量生成一批ID給不同的機器去慢慢消費，這樣數(shù)據庫的壓力也會減小到N分之一，且故障后可堅持一段時間。如圖所示，但這種做法的缺點是服務器重啟、單點故障會造成ID不連續(xù)。還是那句話，沒有最好的方案，只有最適合的方案。雪花算法定義一個64bit的數(shù)，對指定機器 & 同一時刻 & 某一并發(fā)序列，是唯一的，其極限QPS約為400w/s。其格式為：將64 bit分為了四部分。其中時間戳有時間上限(69年)。機器id只有10位，能記錄1024臺機器，常用前幾位表示數(shù)據中心id，后幾位表示數(shù)據中心內的機器id。序列號用來對同一個毫秒之內的操作產生不同的ID，最多4095個。這種結構是雪花算法提出者Twitter的分法，但實際上這種算法使用可以很靈活，根據自身業(yè)務的并發(fā)情況、機器分布、使用年限等，可以自由地重新決定各部分的位數(shù)，從而增加或減少某部分的量級。比如百度的UidGenerator、美團的Leaf等，都是基于雪花算法做一些適合自身業(yè)務的變化。由于雪花算法是強依賴于時間的，在分布式環(huán)境下，如果發(fā)生時鐘回撥，很可能會引起id沖突的問題。解決方案有：

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

方案對比可以發(fā)現(xiàn)，常用的分布式唯一ID生成思路基本是利用一個長串數(shù)字或字符串，將其分割成多個部分，分別記錄時間信息、機器/名字信息、隨機信息、序列信息等。時間信息部分決定了該策略能使用的時長，機器/名字信息支持了分布式環(huán)境下的獨自生成唯一ID與識別能力，序列信息保證了事件的順序記錄以及同一時間單位下的并發(fā)數(shù)，而隨機信息則加大了ID整體的不可識別性。實際上如果現(xiàn)有的方法依然不能滿足，我們完全可以依據自身業(yè)務和發(fā)展需求，來自行決定使用何種策略生成唯一ID。各種方案都有其優(yōu)缺點，技術的使用沒有絕對的好壞之分，主要在于是否適合使用場景：

• 要求生成全局唯一且不會重復ID，不關心順序 —— 使用基于時間的UUID(如游戲聊天室中不同用戶的身份ID)
• 要求生成唯一ID，具有名稱不可變性，可重復生成 —— 使用基于名稱哈希的UUID(如基于不可變信息生成的用戶ID，若不小心刪除，仍可根據信息重新生成同一ID)
• 要求生成有序且自然增長的ID —— 使用數(shù)據庫自增ID(如各業(yè)務操作流水ID，高并發(fā)下可參考優(yōu)化方案)
• 要求生成數(shù)值型無序定長ID —— 使用雪花算法(如對存儲空間、查詢效率、傳輸數(shù)據量等有較高要求的場景)

對于最初我們定義的唯一ID特性，各方案的對比如下：從沖突率、QPS和算法時間復雜度來比較的話：參考UUID算法分析關于UUID的二三事UUID百度百科UUID唯一資源命名空間的來龍去脈UUID是如何保證唯一性的？如果再有人問你分布式 ID，這篇文章丟給他分布式唯一ID的幾種生成方案UidGenerator-百度Leaf——美團點評分布式ID生成系統(tǒng)分布式系統(tǒng)：Lamport 邏輯時鐘

總結

以上是生活随笔為你收集整理的node 生成随机头像_唯一ID生成算法剖析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。