在復(fù)雜的分布式系統(tǒng)中，常常需要一個(gè)全局唯一的 ID來(lái)標(biāo)識(shí)數(shù)據(jù)，消息或者請(qǐng)求，比如：訂單號(hào)，消息的唯一標(biāo)識(shí)，接口的冪等ID等等。今天，我們一起來(lái)聊聊幾種常見(jiàn)的分布式ID 生成方式。

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

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

1. 全局唯一

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

2. 數(shù)量夠用

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

3. 安全性

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

4. 有序性

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

二、生成算法

1. UUID

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

UUID有 5種常見(jiàn)的生成方式，這里總結(jié)了構(gòu)成，用途和特點(diǎn)：

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

• 構(gòu)成：基于當(dāng)前時(shí)間戳、時(shí)鐘序列和機(jī)器的MAC地址。
• 用途：可以確?？缈臻g（不同機(jī)器）和時(shí)間的唯一性。
• 特點(diǎn)：可能會(huì)暴露生成 UUID的機(jī)器地址和時(shí)間。

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

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

(3) 基于名字的MD5散列

• 構(gòu)成：使用名字空間（Namespace）和特定名字生成 MD5散列。java.util.UUID 提供了這種方式，需要傳入key，使用比較少。
• 用途：為相同名字生成相同的 UUID，但不同名字空間下的相同名字將生成不同的 UUID。
• 特點(diǎn)：相同輸入產(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) 隨機(jī)生成

• 構(gòu)成：使用隨機(jī)數(shù)或偽隨機(jī)數(shù)生成，java.util.UUID 是基于這種方式，使用比較多。
• 用途：不需要基于時(shí)間或名字，僅需要快速生成UUID。
• 特點(diǎn)：簡(jiǎn)單，沒(méi)有時(shí)間順序，不具備可預(yù)測(cè)性。

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散列

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

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

到此，我們對(duì) UUID有了一個(gè)全面的認(rèn)識(shí)，最后，總結(jié)下 UUID的優(yōu)缺點(diǎn)以及一些使用建議：

優(yōu)點(diǎn)：

• 生成方式簡(jiǎn)單，各種語(yǔ)言都有成熟的類庫(kù)
• 本地生成，性能高，不依賴網(wǎng)絡(luò)
• 隨機(jī)機(jī)行強(qiáng)，不容被預(yù)測(cè)

缺點(diǎn)：

• 無(wú)序，不利于排序，用于 MySQL主鍵時(shí)對(duì)索引不夠友好
• 32位，字符串太長(zhǎng)，存儲(chǔ)需要消耗更多的空間
• 具體生成 UUID算法的缺點(diǎn)

使用建議：

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

2. ULID

ULID 是 Universally Unique Lexicographically Sortable Identifier的縮寫(xiě)，它是一種全局唯一、按字典序可排序的標(biāo)識(shí)符。

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

下面借助三方庫(kù) 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
    }
}

最后總結(jié)下 ULID 的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

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

缺點(diǎn)：

•  ULID 依賴于時(shí)間戳，極端情況可能會(huì)出現(xiàn)時(shí)間回?fù)軐?dǎo)致 ID沖突

3. 基于 Redis

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

下面總結(jié)下 Redis的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

• 高性能
• 生成的 ID有序

缺點(diǎn)：

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

4. 基于MySQL

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

int（或 integer）：

• 無(wú)符號(hào)的范圍是 0 到 4294967295（42億多）
• 有符號(hào)的范圍是 -2147483648 到 2147483647

bigint：

• 無(wú)符號(hào)的范圍是 0 到 18446744073709551615
• 有符號(hào)的范圍是 -9223372036854775808 到 9223372036854775807

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

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

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

接下來(lái)分析 2種常見(jiàn)生成方式：

(1) MySQL乞丐版

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

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可以設(shè)置成具體的

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

下面為對(duì)外提供服務(wù)核心步驟的 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;
    }
}

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

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

對(duì)于缺點(diǎn)中單臺(tái) MySQL存在性能問(wèn)題，我們自然會(huì)想到增加一臺(tái) MySQL，一臺(tái)使用奇數(shù)自增（1,3,5,7,2n-1），一臺(tái)使用偶數(shù)自增(2,4,6,8,2n)，這樣是不是就可以分?jǐn)倝毫α耍咳绻?2臺(tái) MySQL還不夠用，那我們可以使用 N臺(tái)，每臺(tái)的初始值依次為 1, 2, 3 … N-1，步長(zhǎng)是N（機(jī)器的數(shù)量），整個(gè)架構(gòu)思路圖如下：

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

那么，有沒(méi)有一個(gè)更優(yōu)的設(shè)計(jì)方案，既能減少對(duì) DB的操作，又能避免 DB的性能瓶頸？

(2) MySQL號(hào)段版

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

這里我們引入了號(hào)段最大值（max_id） 和步長(zhǎng)（step）兩個(gè)概念，max_id是指表中末次獲取號(hào)段時(shí)的最大 ID號(hào)，step是指每次獲取多少個(gè) ID。比如，初始值是 1，第一次獲取 1000個(gè)ID，那 max_id=1000， step=1000，第二獲取 1000個(gè)ID，那么 max_id=2000， step=1000，表結(jié)構(gòu)設(shè)計(jì)如下：

-- 號(hào)段 + 步長(zhǎng)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可以設(shè)置成具體的起始值

整體架構(gòu)思路圖：

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

總結(jié)下方案的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

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

缺點(diǎn)

• DB不可用導(dǎo)致整個(gè)ID生成系統(tǒng)不可用
• ID規(guī)律性太強(qiáng)，很容易識(shí)別語(yǔ)義，比如，用于訂單號(hào)時(shí)，可以根據(jù)某一個(gè)訂單號(hào)輕易地猜測(cè)出其他訂單號(hào)

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

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

整個(gè)高可用容災(zāi)方案如下圖：

5. 雪花算法

Snowflake，雪花算法是由 Twitter開(kāi)源的分布式 ID生成算法，整個(gè)ID包含 64-bit，對(duì)應(yīng) Java的 Long類型，如下圖：

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

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

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

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

優(yōu)點(diǎn)：

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

缺點(diǎn)：

• 強(qiáng)依賴機(jī)器時(shí)鐘，如果時(shí)鐘回?fù)埽赡軙?huì)導(dǎo)致 ID重復(fù)

6. 三方工具

(1) 美團(tuán)的 Leaf

Leaf是美團(tuán)開(kāi)源的分布式 ID生成工具，它包含 Leaf-segment 和 Leaf-snowflake兩種方案， Leaf-segment是基于 MySQL數(shù)據(jù)庫(kù)，它是針對(duì)上述 MySQL方案的更優(yōu)秀設(shè)計(jì)，Leaf-snowflake 是基于雪花算法，并且解決雪花算法中時(shí)鐘回?fù)艿膯?wèn)題。

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

(2) 滴滴的TinyID

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

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

(3) 百度-UidGenerator

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

• DefaultUidGenerator 是基于時(shí)間戳和機(jī)器位還有序列號(hào)的生成方式，和雪花算法很相似，對(duì)于時(shí)鐘回?fù)芤仓皇菕伄惓Ｌ幚?。僅有一些不同，如以秒為為單位而不再是毫秒和支持Docker等虛擬化環(huán)境。
• CachedUidGenerator 是使用 RingBuffer 緩存生成的id。數(shù)組每個(gè)元素成為一個(gè)slot。RingBuffer容量，默認(rèn)為Snowflake算法中sequence最大值（2^13 = 8192）?？赏ㄟ^(guò) boostPower 配置進(jìn)行擴(kuò)容，以提高 RingBuffer 讀寫(xiě)吞吐量。

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

三、總結(jié)

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

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