引

在業(yè)務(wù)開發(fā)中，大量場景需要唯一ID來進(jìn)行標(biāo)識(shí)：用戶需要唯一身份標(biāo)識(shí)；商品需要唯一標(biāo)識(shí)；消息需要唯一標(biāo)識(shí)；事件需要唯一標(biāo)識(shí)...等等，都需要全局唯一ID，尤其是分布式場景下。

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

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

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

• UUID：
  • 基于時(shí)間戳&時(shí)鐘序列生成
  • 基于名字空間/名字的散列值（MD5/SHA1）生成
  • 基于隨機(jī)數(shù)生成
• 數(shù)據(jù)庫自增ID：
  • 多臺(tái)機(jī)器不同初始值、同步長自增
  • 批量緩存自增ID
• 雪花算法
  • 時(shí)鐘回?fù)芙鉀Q方案

本文便分別對這些算法進(jìn)行講解及分析。

UUID

UUID全稱為：Universally Unique IDentifier（通用唯一識(shí)別碼），有的地方也稱作GUID（Globally Unique IDentifier），實(shí)際上GUID指微軟對于UUID標(biāo)準(zhǔn)的實(shí)現(xiàn)的實(shí)現(xiàn)。

UUID算法的目的是為了生成某種形式的全局唯一ID來標(biāo)識(shí)系統(tǒng)中的任一元素，尤其在分布式環(huán)境下，該ID需要不依賴中心認(rèn)證即可自動(dòng)生成全局唯一ID。

其優(yōu)勢有：

• 無需網(wǎng)絡(luò)，單機(jī)自行生成
• 速度快，QPS高（支持100ns級(jí)并發(fā)）
• 各語言均有相應(yīng)實(shí)現(xiàn)庫供直接使用

而缺點(diǎn)為：

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

1.UUID的格式

UUID的標(biāo)準(zhǔn)形式為32個(gè)十六進(jìn)制數(shù)組成的字符串，且分隔為五個(gè)部分，如：

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

各部分的數(shù)字個(gè)數(shù)為：8-4-4-4-12

2.UUID版本

根據(jù)需要不同，標(biāo)準(zhǔn)提供了不同的UUID版本以供使用，分別對應(yīng)于不同的UUID生成規(guī)則：

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

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

• 版本1 - 基于時(shí)間的UUID：
  • 優(yōu)點(diǎn)：能基本保證全球唯一性
  • 缺點(diǎn)：使用了Mac地址，因此會(huì)暴露Mac地址和生成時(shí)間
• 版本2 - 分布式安全的UUID：
  • 優(yōu)點(diǎn)：能保證全球唯一性
  • 缺點(diǎn)：很少使用，常用庫基本沒有實(shí)現(xiàn)
• 版本3 - 基于名字空間的UUID（MD5版）：
  • 優(yōu)點(diǎn)：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復(fù)。
  • 缺點(diǎn)：MD5碰撞問題，只用于向后兼容，后續(xù)不再使用
• 版本4 - 基于隨機(jī)數(shù)的UUID：
  • 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單
  • 缺點(diǎn)：重復(fù)幾率可計(jì)算
• 版本5 - 基于名字空間的UUID（SHA1版）：
  • 優(yōu)點(diǎn)：不同名字空間或名字下的UUID是唯一的；相同名字空間及名字下得到的UUID保持重復(fù)。
  • 缺點(diǎn)：SHA1計(jì)算相對耗時(shí)

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

4.UUID結(jié)構(gòu)及生成規(guī)則

以版本1 - 基于時(shí)間的UUID為例先梳理UUID的結(jié)構(gòu)：

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

時(shí)間值：在基于時(shí)間的UUID中，時(shí)間值是一個(gè)60位的整型值，對應(yīng)UTC的100ns時(shí)間間隔計(jì)數(shù)，因此其支持支持一臺(tái)機(jī)器每秒生成10M次。在UUID中，將這60位放置到了15~08這8-byte中（除了09位有4-bit的版本號(hào)內(nèi)容）。

版本號(hào)：版本號(hào)即上文所說的五個(gè)版本，在五個(gè)版本的UUID中，都總是在該位置標(biāo)識(shí)版本，占據(jù) 4-bit，分別以下列數(shù)字表示：

因此版本號(hào)這一位的取值只會(huì)是1,2,3,4,5

變體值：表明所依賴的標(biāo)準(zhǔn)（X表示可以是任意值）：

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

節(jié)點(diǎn)值：在基于時(shí)間的UUID中，節(jié)點(diǎn)值占據(jù)了05~00的48-bit，由機(jī)器的MAC地址構(gòu)成。如果機(jī)器有多個(gè)MAC地址，則隨機(jī)選其中一個(gè)；如果機(jī)器沒有MAC地址，則采用（偽）隨機(jī)數(shù)。

了解了基于時(shí)間的UUID結(jié)構(gòu)及生成規(guī)則后，再看看其他版本的UUID生成規(guī)則：

• 版本2 - 分布式安全的UUID：
  將基于時(shí)間的UUID中時(shí)間戳前四位換為POSIX的UID或GID，其余保持一致。
• 版本3/5 - 基于名字空間的UUID（MD5/SHA1）：
  1. 將命名空間（如DNS、URL、OID等）及名字轉(zhuǎn)換為字節(jié)序列；
  2. 通過MD5/SHA1散列算法將上述字節(jié)序列轉(zhuǎn)換為16字節(jié)哈希值（MD5散列不再推薦，SHA1散列的20位只使用其15~00位）；
  3. 將哈希值的 3~0 字節(jié)置于UUID的15~12位；
  4. 將哈希值的 5~4 字節(jié)置于UUID的11~10位；
  5. 將哈希值的 7~6 字節(jié)置于UUID的09~08位，并用相應(yīng)版本號(hào)覆蓋第9位的高4位（同版本1位置）；
  6. 將哈希值的 8 字節(jié)置于UUID的07位，并用相應(yīng)變體值覆蓋其高2位（同版本1位置）；
  7. 將哈希值的 9 字節(jié)置于UUID的06位（原時(shí)鐘序列位置）；
  8. 將哈希值的 15~10 字節(jié)置于UUID的05~00位（原節(jié)點(diǎn)值位置）。
• 版本4 - 基于隨機(jī)數(shù)的UUID：
  1. 生成16byte隨機(jī)值填充UUID。重復(fù)機(jī)率與隨機(jī)數(shù)產(chǎn)生器的質(zhì)量有關(guān)。若要避免重復(fù)率提高，必須要使用基于密碼學(xué)上的假隨機(jī)數(shù)產(chǎn)生器來生成值才行；
  2. 將變體值及版本號(hào)填到相應(yīng)位置。

5.多版本偽碼

// 版本 1 - 基于時(shí)間的UUID：
gen_uuid() {
    struct uuid uu;

    // 獲取時(shí)間戳
    get_time(&clock_mid, &uu.time_low);
    uu.time_mid = (uint16_t) clock_mid; // 時(shí)間中間位
    uu.time_hi_and_version = ((clock_mid >> 16) & 0x0FFF) | 0x1000; // 時(shí)間高位 & 版本號(hào)

    // 獲取時(shí)鐘序列。在libuuid中，嘗試取時(shí)鐘序列+1，取不到則隨機(jī)；在python中直接使用隨機(jī)
    get_clock(&uu.clock_seq);// 時(shí)鐘序列+1 或 隨機(jī)數(shù)
    uu.clock_seq |= 0x8000;// 時(shí)鐘序列位 & 變體值

    // 節(jié)點(diǎn)值
    char node_id[6];
    get_node_id(node_id);// 根據(jù)mac地址等獲取節(jié)點(diǎn)id
    uu.node = node_id;
    return uu;
}

// 版本4 - 基于隨機(jī)數(shù)的UUID：
gen_uuid() {
    struct uuid uu;
    uuid_t buf;

    random_get_bytes(buf, sizeof(buf));// 獲取隨機(jī)出來的uuid，如libuuid根據(jù)進(jìn)程id、當(dāng)日時(shí)間戳等進(jìn)行srand隨機(jī)

    uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;// 變體值覆蓋
    uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF) | 0x4000;// 版本號(hào)覆蓋
    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;// 版本號(hào)覆蓋
    return uu;
}

數(shù)據(jù)庫自增ID

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

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

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

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

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

• 根據(jù)擴(kuò)容考慮決定步長
• 增加其他位標(biāo)記區(qū)分?jǐn)U容

這其實(shí)都是在需求與方案間的權(quán)衡，根據(jù)需求來選擇最適合的方式。

2.批量生成一批ID

如果要使用單臺(tái)機(jī)器做ID生成，避免固定步長帶來的擴(kuò)容問題，可以每次批量生成一批ID給不同的機(jī)器去慢慢消費(fèi)，這樣數(shù)據(jù)庫的壓力也會(huì)減小到N分之一，且故障后可堅(jiān)持一段時(shí)間。

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

雪花算法

定義一個(gè)64bit的數(shù)，對指定機(jī)器 & 同一時(shí)刻 & 某一并發(fā)序列，是唯一的，其極限QPS約為400w/s。其格式為：

將64 bit分為了四部分。其中時(shí)間戳有時(shí)間上限（69年）。機(jī)器id只有10位，能記錄1024臺(tái)機(jī)器，常用前幾位表示數(shù)據(jù)中心id，后幾位表示數(shù)據(jù)中心內(nèi)的機(jī)器id。序列號(hào)用來對同一個(gè)毫秒之內(nèi)的操作產(chǎn)生不同的ID，最多4095個(gè)。

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

由于雪花算法是強(qiáng)依賴于時(shí)間的，在分布式環(huán)境下，如果發(fā)生時(shí)鐘回?fù)?/strong>，很可能會(huì)引起id沖突的問題。解決方案有：