面試官：為什麽需要分布式ID？你計畫中是怎麽做的？

今天分享一位讀者去京東面試遇到的面試題：「為什麽要分布式 ID？你計畫中是怎麽做的？」。

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

內容概覽：

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

分布式 ID 介紹

什麽是 ID？

日常開發中，我們需要對系統中的各種數據使用 ID 唯一表示，比如使用者 ID 對應且僅對應一個人，商品 ID 對應且僅對應一件商品，訂單 ID 對應且僅對應一個訂單。

我們現實生活中也有各種 ID，比如身份證 ID 對應且僅對應一個人、地址 ID 對應且僅對應

簡單來說， ID 就是數據的唯一標識 。

什麽是分布式 ID？

分布式 ID 是分布式系統下的 ID。分布式 ID 不存在與現實生活中，屬於電腦系統中的一個概念。

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

我司的一個計畫，使用的是單機 MySQL 。但是，沒想到的是，計畫上線一個月之後，隨著使用人數越來越多，整個系統的數據量將越來越大。單機 MySQL 已經沒辦法支撐了，需要進行分庫分表（推薦 Sharding-JDBC）。

在分庫之後， 數據遍布在不同伺服器上的資料庫，資料庫的自增主鍵已經沒辦法滿足生成的主鍵唯一了。 我們如何為不同的數據節點生成全域唯一主鍵呢？

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

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

分布式 ID 作為分布式系統中必不可少的一環，很多地方都要用到分布式 ID。

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

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

分布式 ID 常見解決方案

資料庫

資料庫主鍵自增

這種方式就比較簡單直白了，就是透過關系型資料庫的自增主鍵產生來唯一的 ID。

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

1.建立一個資料庫表。

CREATETABLE`sequence_id` (
`id`bigint(20) unsignedNOTNULL AUTO_INCREMENT,
`stub`char(10) NOTNULLDEFAULT'',
PRIMARY KEY (`id`),
UNIQUEKEY`stub` (`stub`)
) ENGINE=InnoDBDEFAULTCHARSET=utf8mb4;


stub 欄位無意義，只是為了占位，便於我們插入或者修改數據。並且，給 stub 欄位建立了唯一索引，保證其唯一性。

2.透過 replace into 來插入數據。

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


插入數據這裏，我們沒有使用 insert into 而是使用 replace into 來插入數據，具體步驟是這樣的：

這種方式的優缺點也比較明顯：

資料庫號段模式

資料庫主鍵自增這種模式，每次獲取 ID 都要存取一次資料庫，ID 需求比較大的時候，肯定是不行的。

如果我們可以批次獲取，然後存在在記憶體裏面，需要用到的時候，直接從記憶體裏面拿就舒服了！這也就是我們說的 基於資料庫的號段模式來生成分布式 ID。

資料庫的號段模式也是目前比較主流的一種分布式 ID 生成方式。像滴滴開源的 Tinyid ^[1] 就是基於這種方式來做的。不過，TinyId 使用了雙號段緩存、增加多 db 支持等方式來進一步最佳化。

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

1. 建立一個資料庫表。

CREATETABLE`sequence_id_generator` (
`id`int(10) NOTNULL,
`current_max_id`bigint(20) NOTNULLCOMMENT'當前最大id',
`step`int(10) NOTNULLCOMMENT'號段的長度',
`version`int(20) NOTNULLCOMMENT'版本號',
`biz_type`int(20) NOTNULLCOMMENT'業務型別',
PRIMARY KEY (`id`)
) ENGINE=InnoDBDEFAULTCHARSET=utf8mb4;


current_max_id 欄位和 step 欄位主要用於獲取批次 ID，獲取的批次 id 為： current_max_id ~ current_max_id+step 。

version 欄位主要用於解決並行問題（樂觀鎖）, biz_type 主要用於表示業務型別。

2. 先插入一行數據。

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


3. 透過 SELECT 獲取指定業務下的批次唯一 ID

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


結果：

id current_max_id step version biz_type
1 0 100 0 101


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

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


結果：

id current_max_id step version biz_type
1 100 100 1 101


相比於資料庫主鍵自增的方式， 資料庫的號段模式對於資料庫的存取次數更少，資料庫壓力更小。

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

資料庫號段模式的優缺點:

NoSQL

一般情況下，NoSQL 方案使用 Redis 多一些。我們透過 Redis 的 incr 命令即可實作對 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"


為了提高可用性和並行，我們可以使用 Redis Cluster。Redis Cluster 是 Redis 官方提供的 Redis 集群解決方案（3.0+版本）。

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

除了高可用和並行之外，我們知道 Redis 基於記憶體，我們需要持久化數據，避免重新開機機器或者機器故障後數據遺失。Redis 支持兩種不同的持久化方式： 快照（snapshotting，RDB） 、 只追加檔（append-only file, AOF） 。並且，Redis 4.0 開始支持 RDB 和 AOF 的混合持久化 （預設關閉，可以透過配置項 aof-use-rdb-preamble 開啟）。

關於 Redis 持久化，我這裏就不過多介紹。不了解這部份內容的小夥伴，可以看看 Redis 持久化機制詳解 ^[3] 這篇文章。

Redis 方案的優缺點：

除了 Redis 之外，MongoDB ObjectId 經常也會被拿來當做分布式 ID 的解決方案。

MongoDB ObjectId 一共需要 12 個字節儲存：

MongoDB 方案的優缺點：

演算法

UUID

UUID 是 Universally Unique Identifier（通用唯一識別元） 的縮寫。UUID 包含 32 個 16 進制數位（8-4-4-4-12）。

JDK 就提供了現成的生成 UUID 的方法，一行程式碼就行了。

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


RFC 4122 ^[4] 中關於 UUID 的範例是這樣的：

我們這裏重點關註一下這個 Version(版本)，不同的版本對應的 UUID 的生成規則是不同的。

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

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

JDK 中透過 UUID 的 randomUUID() 方法生成的 UUID 的版本預設為 4。

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


另外，Variant(變體)也有 4 種不同的值，這種值分別對應不同的含義。這裏就不介紹了，貌似平時也不怎麽需要關註。

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

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

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

比如使用 UUID 作為 MySQL 資料庫主鍵的時候就非常不合適：

最後，我們再簡單分析一下 UUID 的優缺點 （面試的時候可能會被問到的哦！） :

Snowflake(雪花演算法)

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

在實際計畫中，我們一般也會對 Snowflake 演算法進行改造，最常見的就是在 Snowflake 演算法生成的 ID 中加入業務型別資訊。

我們再來看看 Snowflake 演算法的優缺點：

如果你想要使用 Snowflake 演算法的話，一般不需要你自己再造輪子。有很多基於 Snowflake 演算法的開源實作比如美團 的 Leaf、百度的 UidGenerator（後面會提到），並且這些開源實作對原有的 Snowflake 演算法進行了最佳化，效能更優秀，還解決了 Snowflake 演算法的時間回撥問題和依賴機器 ID 的問題。

並且，Seata 還提出了「改良版雪花演算法」，針對原版雪花演算法進行了一定的最佳化改良，解決了時間回撥問題，大幅提高的 QPS。具體介紹和改進原理，可以參考下面這兩篇文章：

開源框架

UidGenerator(百度)

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

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

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

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

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

Leaf(美團)

Leaf ^[12] 是美團開源的一個分布式 ID 解決方案 。這個計畫的名字 Leaf（樹葉） 起源於德國哲學家、數學家萊布尼茲的一句話：「There are no two identical leaves in the world」（世界上沒有兩片相同的樹葉） 。這名字起得真心挺不錯的，有點文藝青年那味了！

Leaf 提供了 號段模式 和 Snowflake(雪花演算法) 這兩種模式來生成分布式 ID。並且，它支持雙號段，還解決了雪花 ID 系統時鐘回撥問題。不過，時鐘問題的解決需要弱依賴於 Zookeeper（使用 Zookeeper 作為註冊中心，透過在特定路徑下讀取和建立子節點來管理 workId） 。

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

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

根據計畫 README 介紹，在 4C8G VM 基礎上，透過公司 RPC 方式呼叫，QPS 壓測結果近 5w/s，TP999 1ms。

Tinyid(滴滴)

Tinyid ^[14] 是滴滴開源的一款基於資料庫號段模式的唯一 ID 生成器。

資料庫號段模式的原理我們在上面已經介紹過了。 Tinyid 有哪些亮點呢？

為了搞清楚這個問題，我們先來看看基於資料庫號段模式的簡單架構方案。（圖片來自於 Tinyid 的官方 wiki: 【Tinyid 原理介紹】 ^[15] ）

在這種架構模式下，我們透過 HTTP 請求向發號器服務申請唯一 ID。負載均衡 router 會把我們的請求送往其中的一台 tinyid-server。

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

除此之外，HTTP 呼叫也存在網路開銷。

Tinyid 的原理比較簡單，其架構如下圖所示：

相比於基於資料庫號段模式的簡單架構方案，Tinyid 方案主要做了下面這些最佳化：

Tinyid 的優缺點這裏就不分析了，結合資料庫號段模式的優缺點和 Tinyid 的原理就能知道。

IdGenerator(個人)

和 UidGenerator、Leaf 一樣， IdGenerator ^[16] 也是一款基於 Snowflake(雪花演算法)的唯一 ID 生成器。

IdGenerator 有如下特點：

IdGenerator 生成的唯一 ID 組成如下：

Java 語言使用範例：https://github.com/yitter/idgenerator/tree/master/Java。

總結

透過這篇文章，我基本上已經把最常見的分布式 ID 生成方案都總結了一波。

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

不過，本文主要介紹的是分布式 ID 的理論知識。在實際的面試中，面試官可能會結合具體的業務場景來考察你對分布式 ID 的設計，你可以參考這篇文章： 分布式 ID 設計指南 ^[17] （對於實際工作中分布式 ID 的設計也非常有幫助）。

參考資料

[1]

Tinyid: https://github.com/didi/tinyid/wiki/tinyid原理介绍

如喜歡本文，請點選右上角，把文章分享到朋友圈
如有想了解學習的技術點，請留言給若飛安排分享

因公眾號更改推播規則，請點「在看」並加「星標」 第一時間獲取精彩技術分享

·END·

相關閱讀：

作者：JavaGuide

來源：JavaGuide

版權申明：內容來源網路，僅供學習研究，版權歸原創者所有。如有侵權煩請告知，我們會立即刪除並表示歉意。謝謝!