在復雜的分布式系統(tǒng)中，常常需要一個全局唯一的 ID來標識數(shù)據(jù)，消息或者請求，比如：訂單號，消息的唯一標識，接口的冪等ID等等。今天，我們一起來聊聊幾種常見的分布式ID 生成方式。

一、分布式ID具備什么條件？

分布式 ID，通常建議具備以下 4個條件：

1. 全局唯一

全局唯一，是指在支撐的業(yè)務范圍內(nèi)能保持全局唯一，這里的全局范圍可大可小，大到成千上萬個部門的集團，小到某個團隊內(nèi)的幾個系統(tǒng)， 所以在設計分布式 ID的時候，一定要清晰地定位受眾范圍。

2. 數(shù)量夠用

分布式ID，一定要保證數(shù)量夠用，通常需要根據(jù)公司具體業(yè)務來評估，在一定時間范圍內(nèi)會消耗多個ID， 比如，用于訂單號，需要預估每年會產(chǎn)生多少訂單，消耗多少個訂單號，需要支撐幾年的業(yè)務使用。

3. 安全性

分布式 ID應該是安全的，防止惡意用戶預測或推斷出其他ID，如果業(yè)務對于這種預測不敏感可以忽略。比如，用于接口冪等使用，只要唯一就 ok。

4. 有序性

通常建議分布式 ID具備有序性，方便業(yè)務排序使用。

二、生成算法

1. UUID

UUID，是 Universally Unique Identifier，通用唯一識別碼的縮寫，共128-bit（2^128個），通常表示成 32個十六進制數(shù)字，并且以“-”分隔成五組（8bit-4bit-4bit-4bit-12bit）， 比如：62f77d2d-aefe-41ba-b0f8-4c4c39ab670e。

UUID有 5種常見的生成方式，這里總結了構成，用途和特點：

(1) 基于時間戳和 MAC地址

• 構成：基于當前時間戳、時鐘序列和機器的MAC地址。
• 用途：可以確?？缈臻g（不同機器）和時間的唯一性。
• 特點：可能會暴露生成 UUID的機器地址和時間。

Java示例代碼，需要依賴 java-uuid-generator 工具：

import com.fasterxml.uuid.Generators;
public static void generateUUID() {
  UUID uuid = Generators.timeBasedGenerator().generate();
  System.out.println(uuid); // 比如：de02864c-eda8-11ee-a793-dd2f40a50976
}

(2) DCE安全的UUID

• 構成：與方法1類似，但將一部分空間用于包含 POSIX的 UID或 GID。
• 用途：用于DCE（分布式計算環(huán)境）的安全性。
• 特點：并不常用，和方法1相似，但提供了額外的用戶或組識別信息。

(3) 基于名字的MD5散列

• 構成：使用名字空間（Namespace）和特定名字生成 MD5散列。java.util.UUID 提供了這種方式，需要傳入key，使用比較少。
• 用途：為相同名字生成相同的 UUID，但不同名字空間下的相同名字將生成不同的 UUID。
• 特點：相同輸入產(chǎn)生相同輸出，但由于 MD5容易被破解，不安全，因此現(xiàn)在使用較少。

Java代碼示例：

import java.util.UUID;
public static void generateUUID() {
  String key = "xxxxx"; // 自己指定的key
  UUID uuid3 = UUID.nameUUIDFromBytes(key.getBytes()).toString();
  System.out.println(uuid); // 比如：ea416ed0-759d-36a8-9e58-f63a59077499
}

(4) 隨機生成

• 構成：使用隨機數(shù)或偽隨機數(shù)生成，java.util.UUID 是基于這種方式，使用比較多。
• 用途：不需要基于時間或名字，僅需要快速生成UUID。
• 特點：簡單，沒有時間順序，不具備可預測性。

Java代碼示例：

import java.util.UUID;
public static void main(String[] args) {
  String uuid = UUID.randomUUID().toString();
  System.out.println(uuid); //比如：ea416ed0-759d-36a8-9e58-f63a59077499
}

(5) 基于名字的 SHA-1散列

• 構成：與方法3類似，使用 SHA-1散列算法代替 MD5。
• 用途：給相同名字生成相同的UUID，通常用于避免 MD5弱點的場景。
• 特點：比方法3的 MD5更安全，但SHA-1目前也已被認為不夠安全，比較少使用。

Java代碼示例：

import java.security.MessageDigest;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.util.UUID;

public static UUID generateUUID(String namespace, String name) {
    try {
        MessageDigest sha1 = MessageDigest.getInstance("SHA-1");
        sha1.update(namespace.getBytes());
        byte[] result = sha1.digest(name.getBytes());

        // Set the version to 5
        result[6] &= 0x0f; // clear version
        result[6] |= 0x50; // set to version 5

        // Set the variant to 2
        result[8] &= 0x3f; // clear variant
        result[8] |= 0x80; // set to IETF variant

        ByteBuffer buffer = ByteBuffer.wrap(result);
        buffer.order(ByteOrder.BIG_ENDIAN);
        returnnew UUID(buffer.getLong(), buffer.getLong());
    } catch (Exception e) {
        thrownew RuntimeException("Unable to generate Version 5 UUID", e);
    }
}
// 使用namespace和name生成Version 5 UUID
UUID uuid5 = generateType5UUID("namespace", "name"); // 比如：c717c842-f1d0-5079-a123-4a86d058c64f

到此，我們對 UUID有了一個全面的認識，最后，總結下 UUID的優(yōu)缺點以及一些使用建議：

優(yōu)點：

• 生成方式簡單，各種語言都有成熟的類庫
• 本地生成，性能高，不依賴網(wǎng)絡
• 隨機機行強，不容被預測

缺點：

• 無序，不利于排序，用于 MySQL主鍵時對索引不夠友好
• 32位，字符串太長，存儲需要消耗更多的空間
• 具體生成 UUID算法的缺點

使用建議：

• 日常工作為了使用更美觀，一般會把 UUID中的 “-”去掉
• 如果對 UUID的缺點沒有任何要求，完全可以采用這種方式來生成分布式 ID，比如，作為接口的冪等ID
• UUID有重復的概率，但是幾乎可以忽略不計

2. ULID

ULID 是 Universally Unique Lexicographically Sortable Identifier的縮寫，它是一種全局唯一、按字典序可排序的標識符。

ULID 由 48-bit的時間戳 + 80-bit 的隨機數(shù)組成，時間戳表示自 1970 年 1 月 1 日 UTC 起的毫秒數(shù)，可以支持大約 280 年的時間范圍。

下面借助三方庫 Sulky ULID 演示如何使用 Java 生成 ULID：

import de.huxhorn.sulky.ulid.ULID;
public class ULIDTest {
    public static void main(String[] args) {
        ULID ulid = new ULID();
        String id = ulid.nextULID();
        System.out.println("ULID: " + id); // 01HTBBBDYK0YMQ8X1Z50QGDH9E
    }
}

最后總結下 ULID 的優(yōu)缺點：

優(yōu)點：

• 可排序：ULID  由 48-bit 時間戳開頭，可以按照生成時間進行排序
• 高性能：由于 ULID 使用時間戳和隨機數(shù)，生成速度較快。

缺點：

•  ULID 依賴于時間戳，極端情況可能會出現(xiàn)時間回撥導致 ID沖突

3. 基于 Redis

在 Redis中，可以通過 INCR 和 INCRBY 這樣的自增原子命令，來實現(xiàn)有序的分布式ID：

下面總結下 Redis的優(yōu)缺點：

優(yōu)點：

• 高性能
• 生成的 ID有序

缺點：

• 需要增加 Redis的成本
• 強依賴 Redis，因此需要保證 Redis服務的穩(wěn)定性
• 生成的ID 有序，對于敏感業(yè)務，ID容易被預測

4. 基于MySQL

通過 MySQL數(shù)據(jù)表的主鍵（int 或 bigint）自增來生成分布式 ID，因此，首先來看看 int 和 bigint 類型支持的數(shù)據(jù)范圍。

int（或 integer）：

• 無符號的范圍是 0 到 4294967295（42億多）
• 有符號的范圍是 -2147483648 到 2147483647

bigint：

• 無符號的范圍是 0 到 18446744073709551615
• 有符號的范圍是 -9223372036854775808 到 9223372036854775807

假如每天消耗 1億個，使用總年數(shù)：18446744073709551615 / 100,000,000 / 365 ≈ 505061753 年。

假如每天消耗 1萬億個，使用總年數(shù)：18446744073709551615 / 100,000,000,000,0 / 365 ≈ 50506 年（5萬年）。

使用 MySQL的 bigint，就算業(yè)務體量每天消耗一萬億個 ID，也需要 5萬年才能消耗完，絕對夠用。

接下來分析 2種常見生成方式：

(1) MySQL乞丐版

首先，創(chuàng)建一張 distributed_ids表，用于記錄已經(jīng)生成的 ID（如果 ID不想從 1開始，可以在創(chuàng)建表時給主鍵 ID設置一個起始值），表設計如下：

CREATE TABLE`distributed_ids` (
`id`BIGINT(20) NOTNULL AUTO_INCREMENT,
`created_at`TIMESTAMPNOTNULLDEFAULTCURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;
-- 或者
CREATETABLE`distributed_ids` (
`id`BIGINT(20) NOTNULL AUTO_INCREMENT,
`created_at`TIMESTAMPNOTNULLDEFAULTCURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1000000; -- 1000000可以設置成具體的

接著，我們需要包裝一個 ID生成的服務對外提供給業(yè)務使用，整體架構思路圖如下：

下面為對外提供服務核心步驟的 java偽代碼：

@Controller
public class IdGeneratorController {
    @GetMapping("/generateId")
    public Long generateId() {
        Long id = null;
        synchronized (this) {
             // generate id;  sql: UPDATE distributed_ids SET id = id + 1(step);
            // select max id;  sql: SELECT id FROM distributed_ids ORDER BY id desc limit 1;
        }
        return id;
    }
}

到此，一個簡單的 ID生成系統(tǒng)就完成了，總結下該方案的優(yōu)缺點：

優(yōu)點：

• 實現(xiàn)簡單，維護成本低
• ID單調(diào)遞增
• 可以用較少的成本實現(xiàn)體量較小的業(yè)務需求

缺點：

• 每次獲取 ID時候需要進行兩次 DB操作
• 強依賴于 DB，DB性能以及穩(wěn)定性直接影響 ID生成系統(tǒng)的穩(wěn)定性，而且這里有 DB單節(jié)點的風險

對于缺點中單臺 MySQL存在性能問題，我們自然會想到增加一臺 MySQL，一臺使用奇數(shù)自增（1,3,5,7,2n-1），一臺使用偶數(shù)自增(2,4,6,8,2n)，這樣是不是就可以分攤壓力了？如果 2臺 MySQL還不夠用，那我們可以使用 N臺，每臺的初始值依次為 1, 2, 3 … N-1，步長是N（機器的數(shù)量），整個架構思路圖如下：

仔細觀察上述架構圖可以發(fā)現(xiàn)，對于 MySQL節(jié)點選擇其實本質(zhì)上是一個 Hash算法，因此，該方案存在 Hash算法典型的缺點：水平擴容困難，擴容時，需要涉及到大量的數(shù)據(jù)遷移。

那么，有沒有一個更優(yōu)的設計方案，既能減少對 DB的操作，又能避免 DB的性能瓶頸？

(2) MySQL號段版

號段版是指每次獲取一批 ID（比如 1000，10000），而不是一個 ID，然后在內(nèi)存中去分發(fā)號段內(nèi)的號碼。對此，表結構該如何設計呢？

這里我們引入了號段最大值（max_id） 和步長（step）兩個概念，max_id是指表中末次獲取號段時的最大 ID號，step是指每次獲取多少個 ID。比如，初始值是 1，第一次獲取 1000個ID，那 max_id=1000， step=1000，第二獲取 1000個ID，那么 max_id=2000， step=1000，表結構設計如下：

-- 號段 + 步長step
CREATETABLE`distributed_ids` (
`max_id`BIGINT(20) NOTNULL AUTO_INCREMENT,
`step`INT(11) NOTNULL,
`created_at`TIMESTAMPNOTNULLDEFAULTCURRENT_TIMESTAMP,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT 1; -- 1可以設置成具體的起始值

整體架構思路圖：

對于這個方案中的 step設置多大比較合理，一般會參考流量高峰期的是QPS/TPS， 假設高峰期的 QPS是 1000（1s會消耗 1000個ID）， 如果想取用一次號段持續(xù)使用 10分鐘，那么 step=1000 * 60 * 10，即 step是 QPS的 600倍，以此類推， 也可以參考以往業(yè)務流量分布，確認峰值一般會維持多長時間，根據(jù)這個時間來設定一個合理的 step，這樣就可以避免業(yè)務高峰期頻繁去操作 DB獲取號段。

總結下方案的優(yōu)缺點：

優(yōu)點：

• 一次批量獲取 ID，大大降低了對 MySQL的壓力，比如QPS是 1萬，如果 step設置為1000， 那么對 MySQL的壓力就從 10000降到 10
• step可以更具業(yè)務壓力靈活調(diào)整，可以將此參數(shù)設置為配置變量

缺點

• DB不可用導致整個ID生成系統(tǒng)不可用
• ID規(guī)律性太強，很容易識別語義，比如，用于訂單號時，可以根據(jù)某一個訂單號輕易地猜測出其他訂單號

對于缺點1，可以采用高可用容災方案：主從（一主多從） + 多活（2 地 3活），當主節(jié)點掛了，需要將從節(jié)點切換成主節(jié)點，當機房A 出現(xiàn)問題， 可以切換到機房B，這樣充分保證了服務的高可用，思路看起來簡單，但實施起來比較困難，特別是主從切換的時候，如何保證數(shù)據(jù)一致性是一個比較大的挑戰(zhàn)。

對于缺點2，可以采用雪花算法等方案來生成隨機且遞增的 ID，在下文的三方工具里有很好的實現(xiàn)。

整個高可用容災方案如下圖：

5. 雪花算法

Snowflake，雪花算法是由 Twitter開源的分布式 ID生成算法，整個ID包含 64-bit，對應 Java的 Long類型，如下圖：

為了更好地說明，本文將 64-bit 分成A, B, C, D 4部分：

• A部分，占用 1-bit，代表符號位，其值始終是0
• B部分，占用 41-bit，代表時間戳，可表示 2^41 個數(shù)，每個數(shù)代表毫秒，雪花算法可用的時間年限大概是 69年。
• C部分，占用 10-bit，代表機器數(shù)或者 IDC（數(shù)據(jù)中心）+ 機器數(shù)，如果是機器數(shù)，即 2^10 = 1024 臺機器，如果是 IDC+機器數(shù)， 一般 5-bit 用于 IDC（最大 32個IDC）C，5-bit用于工作機器（最大 32臺機器），這里可以根據(jù)自身業(yè)務靈活調(diào)整。
• D部分，占用 12-bit，代表自增序列，可表示 2^12 = 4096個數(shù)。

基于上述的劃分可以看出，每豪秒能產(chǎn)生 1024 * 4096個有序不重復的ID。

最后，總結下雪花算法的優(yōu)缺點：

優(yōu)點：

• 本地生成，不依賴數(shù)據(jù)庫等第三方系統(tǒng)，穩(wěn)定性高
• ID是趨勢遞增，對于敏感業(yè)務，不具備可預測性
• 可以根據(jù)自身業(yè)務特性靈活分配 bit位

缺點：

• 強依賴機器時鐘，如果時鐘回撥，可能會導致 ID重復

6. 三方工具

(1) 美團的 Leaf

Leaf是美團開源的分布式 ID生成工具，它包含 Leaf-segment 和 Leaf-snowflake兩種方案， Leaf-segment是基于 MySQL數(shù)據(jù)庫，它是針對上述 MySQL方案的更優(yōu)秀設計，Leaf-snowflake 是基于雪花算法，并且解決雪花算法中時鐘回撥的問題。

詳情參考官方文檔：https://tech.meituan.com/2017/04/21/mt-leaf.html

(2) 滴滴的TinyID

Tinyid是用Java開發(fā)的一款分布式id生成系統(tǒng)，基于數(shù)據(jù)庫號段算法實現(xiàn)，Tinyid擴展了leaf-segment算法，支持了多db(master)，同時提供了java-client(sdk)使id生成本地化，獲得了更好的性能與可用性。

詳情參考官方文檔：https://github.com/didi/tinyid/wiki

(3) 百度-UidGenerator

UidGenerator 百度開源的一款用 Java語言實現(xiàn)，基于 Snowflake算法的唯一ID生成器。包含 DefaultUidGenerator 和 CachedUidGenerator 2種實現(xiàn)方式：

• DefaultUidGenerator 是基于時間戳和機器位還有序列號的生成方式，和雪花算法很相似，對于時鐘回撥也只是拋異常處理。僅有一些不同，如以秒為為單位而不再是毫秒和支持Docker等虛擬化環(huán)境。
• CachedUidGenerator 是使用 RingBuffer 緩存生成的id。數(shù)組每個元素成為一個slot。RingBuffer容量，默認為Snowflake算法中sequence最大值（2^13 = 8192）?？赏ㄟ^ boostPower 配置進行擴容，以提高 RingBuffer 讀寫吞吐量。

詳情參考官方文檔：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

三、總結

本文分析了幾種常見的分布式 ID生成方式，具體選用哪種可以根據(jù)自身業(yè)務而定：

• UUID簡單高效，但是無序，如果作為 MySQL的ID主鍵，對于索引不太友好
• ULID 很好的解決了UUID無序的問題，極端情況下存在時間回撥導致ID重復的風險
• 基于 Redis生成的 ID有序，性能高，需要引入和維護 Redis
• MySQL 乞丐版，實現(xiàn)簡單，但是不適合大流量的場景
• MySQL 號段版，適合大流量的場景，但是，當 MySQL主節(jié)點故障時，主從切換需要保持數(shù)據(jù)的一致性
• 雪花算法，有序且不易預測，算法很優(yōu)秀，不過需要解決時鐘回撥的問題
• 三方工具，經(jīng)過生產(chǎn)環(huán)境的考驗，是很不錯的方式，如果不想重復造輪子，優(yōu)先推薦該方式