京東二面：為什么需要分布式ID？你項目中是怎么做的？

下午好，我是 Guide哥！

今天分享一道朋友去京東面試遇到的面試題：“為什么要分布式ID？你項目中是怎么做的？”。

這篇文章我會說說自己的看法，詳細介紹一下分布式ID相關(guān)的內(nèi)容包括分布式 ID 的基本要求以及分布式 ID 常見的解決方案。

這篇文章全程都是大白話的形式，希望能夠為你帶來幫助！

原創(chuàng)不易，若有幫助，點贊/分享就是對我最大的鼓勵！

個人能力有限。如果文章有任何需要補充/完善/修改的地方，歡迎在評論區(qū)指出，共同進步！

分布式 ID

何為 ID？

日常開發(fā)中，我們需要對系統(tǒng)中的各種數(shù)據(jù)使用 ID 唯一表示，比如用戶 ID 對應(yīng)且僅對應(yīng)一個人，商品 ID 對應(yīng)且僅對應(yīng)一件商品，訂單 ID 對應(yīng)且僅對應(yīng)一個訂單。

我們現(xiàn)實生活中也有各種 ID，比如身份證 ID 對應(yīng)且僅對應(yīng)一個人、地址 ID 對應(yīng)且僅對應(yīng)

簡單來說，ID 就是數(shù)據(jù)的唯一標(biāo)識。

何為分布式 ID？

分布式 ID 是分布式系統(tǒng)下的 ID。分布式 ID 不存在與現(xiàn)實生活中，屬于計算機系統(tǒng)中的一個概念。

我簡單舉一個分庫分表的例子。

我司的一個項目，使用的是單機 MySQL 。但是，沒想到的是，項目上線一個月之后，隨著使用人數(shù)越來越多，整個系統(tǒng)的數(shù)據(jù)量將越來越大。

單機 MySQL 已經(jīng)沒辦法支撐了，需要進行分庫分表（推薦 Sharding-JDBC）。

在分庫之后， 數(shù)據(jù)遍布在不同服務(wù)器上的數(shù)據(jù)庫，數(shù)據(jù)庫的自增主鍵已經(jīng)沒辦法滿足生成的主鍵唯一了。我們?nèi)绾螢椴煌臄?shù)據(jù)節(jié)點生成全局唯一主鍵呢？

這個時候就需要生成分布式 ID了。

分布式 ID 需要滿足哪些要求?

分布式 ID 作為分布式系統(tǒng)中必不可少的一環(huán)，很多地方都要用到分布式 ID。

一個最基本的分布式 ID 需要滿足下面這些要求：

• 全局唯一 ：ID 的全局唯一性肯定是首先要滿足的！
• 高性能 ：分布式 ID 的生成速度要快，對本地資源消耗要小。
• 高可用 ：生成分布式 ID 的服務(wù)要保證可用性無限接近于 100%。
• 方便易用 ：拿來即用，使用方便，快速接入！

除了這些之外，一個比較好的分布式 ID 還應(yīng)保證：

• 安全 ：ID 中不包含敏感信息。
• 有序遞增 ：如果要把 ID 存放在數(shù)據(jù)庫的話，ID 的有序性可以提升數(shù)據(jù)庫寫入速度。并且，很多時候 ，我們還很有可能會直接通過 ID 來進行排序。
• 有具體的業(yè)務(wù)含義 ：生成的 ID 如果能有具體的業(yè)務(wù)含義，可以讓定位問題以及開發(fā)更透明化（通過 ID 就能確定是哪個業(yè)務(wù)）。
• 獨立部署 ：也就是分布式系統(tǒng)單獨有一個發(fā)號器服務(wù)，專門用來生成分布式 ID。這樣就生成 ID 的服務(wù)可以和業(yè)務(wù)相關(guān)的服務(wù)解耦。不過，這樣同樣帶來了網(wǎng)絡(luò)調(diào)用消耗增加的問題?？偟膩碚f，如果需要用到分布式 ID 的場景比較多的話，獨立部署的發(fā)號器服務(wù)還是很有必要的。

分布式 ID 常見解決方案

數(shù)據(jù)庫

數(shù)據(jù)庫主鍵自增

這種方式就比較簡單直白了，就是通過關(guān)系型數(shù)據(jù)庫的自增主鍵產(chǎn)生來唯一的 ID。

以 MySQL 舉例，我們通過下面的方式即可。

1.創(chuàng)建一個數(shù)據(jù)庫表。

CREATE TABLE `sequence_id` (
  `id` bigint(20) unsigned NOT NULL AUTO_INCREMENT,
  `stub` char(10) NOT NULL DEFAULT '',
  PRIMARY KEY (`id`),
  UNIQUE KEY `stub` (`stub`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

stub 字段無意義，只是為了占位，便于我們插入或者修改數(shù)據(jù)。并且，給 stub 字段創(chuàng)建了唯一索引，保證其唯一性。

2.通過 replace into 來插入數(shù)據(jù)。

BEGIN;
REPLACE INTO sequence_id (stub) VALUES ('stub');
SELECT LAST_INSERT_ID();
COMMIT;

插入數(shù)據(jù)這里，我們沒有使用 insert into 而是使用 replace into 來插入數(shù)據(jù)，具體步驟是這樣的：

1)第一步：嘗試把數(shù)據(jù)插入到表中。

2)第二步：如果主鍵或唯一索引字段出現(xiàn)重復(fù)數(shù)據(jù)錯誤而插入失敗時，先從表中刪除含有重復(fù)關(guān)鍵字值的沖突行，然后再次嘗試把數(shù)據(jù)插入到表中。

這種方式的優(yōu)缺點也比較明顯：

• 優(yōu)點 ：實現(xiàn)起來比較簡單、ID 有序遞增、存儲消耗空間小
• 缺點 ：支持的并發(fā)量不大、存在數(shù)據(jù)庫單點問題（可以使用數(shù)據(jù)庫集群解決，不過增加了復(fù)雜度）、ID 沒有具體業(yè)務(wù)含義、安全問題（比如根據(jù)訂單 ID 的遞增規(guī)律就能推算出每天的訂單量，商業(yè)機密?。。?、每次獲取 ID 都要訪問一次數(shù)據(jù)庫（增加了對數(shù)據(jù)庫的壓力，獲取速度也慢）

數(shù)據(jù)庫號段模式

數(shù)據(jù)庫主鍵自增這種模式，每次獲取 ID 都要訪問一次數(shù)據(jù)庫，ID 需求比較大的時候，肯定是不行的。

如果我們可以批量獲取，然后存在在內(nèi)存里面，需要用到的時候，直接從內(nèi)存里面拿就舒服了！這也就是我們說的 基于數(shù)據(jù)庫的號段模式來生成分布式 ID。

數(shù)據(jù)庫的號段模式也是目前比較主流的一種分布式 ID 生成方式。像滴滴開源的Tinyid^[1] 就是基于這種方式來做的。不過，TinyId 使用了雙號段緩存、增加多 db 支持等方式來進一步優(yōu)化。

以 MySQL 舉例，我們通過下面的方式即可。

1.創(chuàng)建一個數(shù)據(jù)庫表。

CREATE TABLE `sequence_id_generator` (
  `id` int(10) NOT NULL,
  `current_max_id` bigint(20) NOT NULL COMMENT '當(dāng)前最大id',
  `step` int(10) NOT NULL COMMENT '號段的長度',
  `version` int(20) NOT NULL COMMENT '版本號',
  `biz_type`    int(20) NOT NULL COMMENT '業(yè)務(wù)類型',
   PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

current_max_id 字段和step字段主要用于獲取批量 ID，獲取的批量 id 為：current_max_id ~ current_max_id+step。

version 字段主要用于解決并發(fā)問題（樂觀鎖）,biz_type 主要用于表示業(yè)余類型。

2.先插入一行數(shù)據(jù)。

INSERT INTO `sequence_id_generator` (`id`, `current_max_id`, `step`, `version`, `biz_type`)
VALUES
 (1, 0, 100, 0, 101);

3.通過 SELECT 獲取指定業(yè)務(wù)下的批量唯一 ID

SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101

結(jié)果：

id current_max_id step version biz_type
1 0 100 1 101

4.不夠用的話，更新之后重新 SELECT 即可。

UPDATE sequence_id_generator SET current_max_id = 0+100, version=version+1 WHERE version = 0  AND `biz_type` = 101
SELECT `current_max_id`, `step`,`version` FROM `sequence_id_generator` where `biz_type` = 101

結(jié)果：

id current_max_id step version biz_type
1 100 100 1 101

相比于數(shù)據(jù)庫主鍵自增的方式，數(shù)據(jù)庫的號段模式對于數(shù)據(jù)庫的訪問次數(shù)更少，數(shù)據(jù)庫壓力更小。

另外，為了避免單點問題，你可以從使用主從模式來提高可用性。

數(shù)據(jù)庫號段模式的優(yōu)缺點:

• 優(yōu)點 ：ID 有序遞增、存儲消耗空間小
• 缺點 ：存在數(shù)據(jù)庫單點問題（可以使用數(shù)據(jù)庫集群解決，不過增加了復(fù)雜度）、ID 沒有具體業(yè)務(wù)含義、安全問題（比如根據(jù)訂單 ID 的遞增規(guī)律就能推算出每天的訂單量，商業(yè)機密?。。?/section>

NoSQL

一般情況下，NoSQL 方案使用 Redis 多一些。我們通過 Redis 的 incr 命令即可實現(xiàn)對 id 原子順序遞增。

127.0.0.1:6379> set sequence_id_biz_type 1
OK
127.0.0.1:6379> incr sequence_id_biz_type
(integer) 2
127.0.0.1:6379> get sequence_id_biz_type
"2"

為了提高可用性和并發(fā)，我們可以使用 Redis Cluser。Redis Cluser 是 Redis 官方提供的 Redis 集群解決方案（3.0+版本）。

除了 Redis Cluser 之外，你也可以使用開源的 Redis 集群方案Codis^[2] （大規(guī)模集群比如上百個節(jié)點的時候比較推薦）。

除了高可用和并發(fā)之外，我們知道 Redis 基于內(nèi)存，我們需要持久化數(shù)據(jù)，避免重啟機器或者機器故障后數(shù)據(jù)丟失。Redis 支持兩種不同的持久化方式：快照（snapshotting，RDB）、只追加文件（append-only file, AOF）。并且，Redis 4.0 開始支持 RDB 和 AOF 的混合持久化（默認(rèn)關(guān)閉，可以通過配置項 aof-use-rdb-preamble 開啟）。

關(guān)于 Redis 持久化，我這里就不過多介紹。不了解這部分內(nèi)容的小伙伴，可以看看 JavaGuide 對于 Redis 知識點的總結(jié)^[3]。

Redis 方案的優(yōu)缺點：

• 優(yōu)點 ：性能不錯并且生成的 ID 是有序遞增的
• 缺點 ：和數(shù)據(jù)庫主鍵自增方案的缺點類似

除了 Redis 之外，MongoDB ObjectId 經(jīng)常也會被拿來當(dāng)做分布式 ID 的解決方案。

MongoDB ObjectId 一共需要 12 個字節(jié)存儲：

• 0~3：時間戳
• 3~6：代表機器 ID
• 7~8：機器進程 ID
• 9~11 ：自增值

MongoDB 方案的優(yōu)缺點：

• 優(yōu)點 ：性能不錯并且生成的 ID 是有序遞增的
• 缺點 ：需要解決重復(fù) ID 問題（當(dāng)機器時間不對的情況下，可能導(dǎo)致會產(chǎn)生重復(fù) ID） 、有安全性問題（ID 生成有規(guī)律性）

算法

UUID

UUID 是 Universally Unique Identifier（通用唯一標(biāo)識符） 的縮寫。UUID 包含 32 個 16 進制數(shù)字（8-4-4-4-12）。

JDK 就提供了現(xiàn)成的生成 UUID 的方法，一行代碼就行了。

//輸出示例：cb4a9ede-fa5e-4585-b9bb-d60bce986eaa
UUID.randomUUID()

RFC 4122^[4] 中關(guān)于 UUID 的示例是這樣的：

我們這里重點關(guān)注一下這個 Version(版本)，不同的版本對應(yīng)的 UUID 的生成規(guī)則是不同的。

5 種不同的 Version(版本)值分別對應(yīng)的含義（參考維基百科對于 UUID 的介紹^[5]）：

• 版本 1 : UUID 是根據(jù)時間和節(jié)點 ID（通常是 MAC 地址）生成；
• 版本 2 : UUID 是根據(jù)標(biāo)識符（通常是組或用戶 ID）、時間和節(jié)點 ID 生成；
• 版本 3、版本 5 : 版本 5 - 確定性 UUID 通過散列（hashing）名字空間（namespace）標(biāo)識符和名稱生成；
• 版本 4 : UUID 使用隨機性^[6]或偽隨機性^[7]生成。

下面是 Version 1 版本下生成的 UUID 的示例：

JDK 中通過 UUID 的 randomUUID() 方法生成的 UUID 的版本默認(rèn)為 4。

UUID uuid = UUID.randomUUID();
int version = uuid.version();// 4

另外，Variant(變體)也有 4 種不同的值，這種值分別對應(yīng)不同的含義。這里就不介紹了，貌似平時也不怎么需要關(guān)注。

需要用到的時候，去看看維基百科對于 UUID 的 Variant(變體) 相關(guān)的介紹即可。

從上面的介紹中可以看出，UUID 可以保證唯一性，因為其生成規(guī)則包括 MAC 地址、時間戳、名字空間（Namespace）、隨機或偽隨機數(shù)、時序等元素，計算機基于這些規(guī)則生成的 UUID 是肯定不會重復(fù)的。

雖然，UUID 可以做到全局唯一性，但是，我們一般很少會使用它。

比如使用 UUID 作為 MySQL 數(shù)據(jù)庫主鍵的時候就非常不合適：

• 數(shù)據(jù)庫主鍵要盡量越短越好，而 UUID 的消耗的存儲空間比較大（32 個字符串，128 位）。
• UUID 是無順序的，InnoDB 引擎下，數(shù)據(jù)庫主鍵的無序性會嚴(yán)重影響數(shù)據(jù)庫性能。

最后，我們再簡單分析一下 UUID 的優(yōu)缺點 （面試的時候可能會被問到的哦?。?:

• 優(yōu)點 ：生成速度比較快、簡單易用
• 缺點 ：存儲消耗空間大（32 個字符串，128 位） 、 不安全（基于 MAC 地址生成 UUID 的算法會造成 MAC 地址泄露)、無序（非自增）、沒有具體業(yè)務(wù)含義、需要解決重復(fù) ID 問題（當(dāng)機器時間不對的情況下，可能導(dǎo)致會產(chǎn)生重復(fù) ID）

Snowflake(雪花算法)

Snowflake 是 Twitter 開源的分布式 ID 生成算法。Snowflake 由 64 bit 的二進制數(shù)字組成，這 64bit 的二進制被分成了幾部分，每一部分存儲的數(shù)據(jù)都有特定的含義：

• 第 0 位：符號位（標(biāo)識正負(fù)），始終為 0，沒有用，不用管。
• 第 1~41 位 ：一共 41 位，用來表示時間戳，單位是毫秒，可以支撐 2 ^41 毫秒（約 69 年）
• 第 42~52 位 ：一共 10 位，一般來說，前 5 位表示機房 ID，后 5 位表示機器 ID（實際項目中可以根據(jù)實際情況調(diào)整）。這樣就可以區(qū)分不同集群/機房的節(jié)點。
• 第 53~64 位 ：一共 12 位，用來表示序列號。序列號為自增值，代表單臺機器每毫秒能夠產(chǎn)生的最大 ID 數(shù)(2^12 = 4096),也就是說單臺機器每毫秒最多可以生成 4096 個 唯一 ID。

如果你想要使用 Snowflake 算法的話，一般不需要你自己再造輪子。有很多基于 Snowflake 算法的開源實現(xiàn)比如美團 的 Leaf、百度的 UidGenerator，并且這些開源實現(xiàn)對原有的 Snowflake 算法進行了優(yōu)化。

另外，在實際項目中，我們一般也會對 Snowflake 算法進行改造，最常見的就是在 Snowflake 算法生成的 ID 中加入業(yè)務(wù)類型信息。

我們再來看看 Snowflake 算法的優(yōu)缺點 ：

• 優(yōu)點 ：生成速度比較快、生成的 ID 有序遞增、比較靈活（可以對 Snowflake 算法進行簡單的改造比如加入業(yè)務(wù) ID）
• 缺點 ：需要解決重復(fù) ID 問題（依賴時間，當(dāng)機器時間不對的情況下，可能導(dǎo)致會產(chǎn)生重復(fù) ID）。

開源框架

UidGenerator(百度)

UidGenerator^[8] 是百度開源的一款基于 Snowflake(雪花算法)的唯一 ID 生成器。

不過，UidGenerator 對 Snowflake(雪花算法)進行了改進，生成的唯一 ID 組成如下。

可以看出，和原始 Snowflake(雪花算法)生成的唯一 ID 的組成不太一樣。并且，上面這些參數(shù)我們都可以自定義。

UidGenerator 官方文檔中的介紹如下：

自 18 年后，UidGenerator 就基本沒有再維護了，我這里也不過多介紹。想要進一步了解的朋友，可以看看 UidGenerator 的官方介紹^[9]。

Leaf(美團)

Leaf^[10] 是美團開源的一個分布式 ID 解決方案 。這個項目的名字 Leaf（樹葉） 起源于德國哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話：“There are no two identical leaves in the world”（世界上沒有兩片相同的樹葉） 。這名字起得真心挺不錯的，有點文藝青年那味了！

Leaf 提供了 號段模式 和 Snowflake(雪花算法) 這兩種模式來生成分布式 ID。并且，它支持雙號段，還解決了雪花 ID 系統(tǒng)時鐘回?fù)軉栴}。不過，時鐘問題的解決需要弱依賴于 Zookeeper 。

Leaf 的誕生主要是為了解決美團各個業(yè)務(wù)線生成分布式 ID 的方法多種多樣以及不可靠的問題。

Leaf 對原有的號段模式進行改進，比如它這里增加了雙號段避免獲取 DB 在獲取號段的時候阻塞請求獲取 ID 的線程。簡單來說，就是我一個號段還沒用完之前，我自己就主動提前去獲取下一個號段（圖片來自于美團官方文章：《Leaf——美團點評分布式 ID 生成系統(tǒng)》^[11]）。

根據(jù)項目 README 介紹，在 4C8G VM 基礎(chǔ)上，通過公司 RPC 方式調(diào)用，QPS 壓測結(jié)果近 5w/s，TP999 1ms。

Tinyid(滴滴)

Tinyid^[12] 是滴滴開源的一款基于數(shù)據(jù)庫號段模式的唯一 ID 生成器。

數(shù)據(jù)庫號段模式的原理我們在上面已經(jīng)介紹過了。Tinyid 有哪些亮點呢？

為了搞清楚這個問題，我們先來看看基于數(shù)據(jù)庫號段模式的簡單架構(gòu)方案。（圖片來自于 Tinyid 的官方 wiki:《Tinyid 原理介紹》^[13]）

在這種架構(gòu)模式下，我們通過 HTTP 請求向發(fā)號器服務(wù)申請唯一 ID。負(fù)載均衡 router 會把我們的請求送往其中的一臺 tinyid-server。

這種方案有什么問題呢？在我看來（Tinyid 官方 wiki 也有介紹到），主要由下面這 2 個問題：

• 獲取新號段的情況下，程序獲取唯一 ID 的速度比較慢。
• 需要保證 DB 高可用，這個是比較麻煩且耗費資源的。

除此之外，HTTP 調(diào)用也存在網(wǎng)絡(luò)開銷。

Tinyid 的原理比較簡單，其架構(gòu)如下圖所示：

相比于基于數(shù)據(jù)庫號段模式的簡單架構(gòu)方案，Tinyid 方案主要做了下面這些優(yōu)化：

• 雙號段緩存 ：為了避免在獲取新號段的情況下，程序獲取唯一 ID 的速度比較慢。Tinyid 中的號段在用到一定程度的時候，就會去異步加載下一個號段，保證內(nèi)存中始終有可用號段。
• 增加多 db 支持 ：支持多個 DB，并且，每個 DB 都能生成唯一 ID，提高了可用性。
• 增加 tinyid-client ：純本地操作，無 HTTP 請求消耗，性能和可用性都有很大提升。

Tinyid 的優(yōu)缺點這里就不分析了，結(jié)合數(shù)據(jù)庫號段模式的優(yōu)缺點和 Tinyid 的原理就能知道。

分布式 ID 生成方案總結(jié)

這篇文章中，我基本上已經(jīng)把最常見的分布式 ID 生成方案都總結(jié)了一波。

除了上面介紹的方式之外，像 ZooKeeper 這類中間件也可以幫助我們生成唯一 ID。沒有銀彈，一定要結(jié)合實際項目來選擇最適合自己的方案。

參考資料