緣起

在分布式微服務(wù)系統(tǒng)架構(gòu)下，有非常多的情況我們需要生成一個全局唯一的 ID 來做標識，比如：

• 需要分庫分表的情況下，分庫或分表會導(dǎo)致表本事的自增鍵不具備唯一性。
• 較長的業(yè)務(wù)鏈路涉及到多個微服務(wù)之間的調(diào)用，需要一個唯一 ID 來標識比如訂單 ID、消息 ID、優(yōu)惠券 ID、分布式事務(wù)全局事務(wù) ID。

對于全局唯一 ID 來說，通常具備以下特點：

• 全局唯一性：ID 不會重復(fù)，這個是全局唯一 ID 最基本的特性
• 趨勢遞增：考慮到類似 MySQL 數(shù)據(jù)存儲是基于 B+ 樹的聚簇索引，非趨勢遞增會導(dǎo)致寫入性能受到影響。
• 單調(diào)遞增：保證上一個 ID 的大小一定小于下一個 ID，對于某些有排序需求的場景有一定的必要性，比如 IM 消息觸達到端，或者就是單純的有需要基于 ID 進行排序的需求。
• 信息安全：如果 ID 可以被簡單的枚舉出來，那么有潛在的數(shù)據(jù)安全問題。并且如果是訂單號的場景，通過訂單號的簡單相減就預(yù)估出當天的訂單量的話，會導(dǎo)致商業(yè)數(shù)據(jù)泄漏。

可以發(fā)現(xiàn) 1 是我們必須去保證的，2 盡可能保證，3 和 4 一定程度上是互斥的，無法通過一個方案來實現(xiàn)。并且在這個基礎(chǔ)上，全局唯一 ID 的生成需要做到高性能（TP999 的響應(yīng)耗時要盡可能?。┮约案叻€(wěn)定性（可用性 5 個 9）。

常見方案

通常來說全局唯一 ID 的生成方案也分幾類：

• 單機自行生成，不依賴其他服務(wù)，來保證全局唯一性。
• 應(yīng)用集群，應(yīng)用服務(wù)的業(yè)務(wù)場景內(nèi)保證全局唯一 ID。
• 獨立服務(wù)提供通用的生產(chǎn)全局唯一 ID 的能力。

下面來具體介紹業(yè)界常見的一些方案：

UUID

UUID 是通用唯一識別碼（Universally Unique Identifier）的縮寫，開放軟件基金會（OSF）規(guī)范定義了包括網(wǎng)卡MAC地址、時間戳、名字空間（Namespace）、隨機或偽隨機數(shù)、時序等元素。利用這些元素來生成 UUID。

UUID 一共有 5 個版本：

• 版本1 - 基于時間的 UUID：主要依賴當前的時間戳及機器 mac 地址，因此可以保證全球唯一性。
• 版本2 - 分布式安全的 UUID：將版本1的時間戳前四位換為 POSIX 的 UID 或 GID，很少使用。
• 版本3 - 基于名字空間的 UUID（MD5 版）：基于指定的名字空間/名字生成 MD5 散列值得到，標準不推薦。
• 版本4 - 基于隨機數(shù)的 UUID：基于偽隨機數(shù)，生成 16byte 隨機值填充 UUID。重復(fù)機率與隨機數(shù)產(chǎn)生器的質(zhì)量有關(guān)。
• 版本5 - 基于名字空間的 UUID（SHA1版）：將版本 3 的散列算法改為 SHA1。

大家多數(shù)情況下使用的是 v4 版本，Node.js 的 uuid 包支持所有版本的 uuid 生成。Java 的 UUID.randomUUID() 是基于 v4 版本，UUID.nameUUIDFromBytes() 是基于 v3 版本。

UUID 的優(yōu)勢：

• 本地生成，不依賴外部服務(wù)，生成的性能也還不錯。

UUID 的劣勢：

• v1 版本存在信息安全問題，直接將 mac 地址暴露出去，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
• v3、v5 都是在命名空間 + 名稱輸入的情況下可以輸出統(tǒng)一的 UUID，不適合用于唯一 ID 生成。
• v4 版本如果基于偽隨機數(shù)，理論上會存在出現(xiàn)重復(fù)的概率。
• 通常在數(shù)據(jù)庫中存儲為字符串，相比整型會花費更多存儲空間。
• 字符串無法保證有序，在 MySQL 基于 B+ 樹的聚簇索引結(jié)構(gòu)下，寫入性能不佳。

在一些簡單場景下，對于性能的要求不嚴格，并且系統(tǒng)并發(fā)不高的情況下，使用 UUID 可能是最簡單、最低成本的方案。

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

數(shù)據(jù)庫主鍵自增這個是大家都非常熟悉的功能，在分庫分表的場景下，依賴單表主鍵自增顯然沒法保證唯一性。但也并不是完全不能利用，比如一個統(tǒng)一的 ID 生成服務(wù)，背后建若干張 sequence 表專門用于 ID 的生成，每臺機器對應(yīng)不同的 sequence 表，并且每個 sequence 表設(shè)置不同的自增初始值和統(tǒng)一的自增步長，比如 2 臺機器的情況下，一臺自增初始值為 1，一臺自增初始值為 2，自增步長都為 2，就相當于每臺機器返回的是一個等差數(shù)列，且每臺機器返回的等差數(shù)列之間不會重復(fù)。

這種方案滿足的是趨勢遞增，但不是絕對的單調(diào)遞增，同時也有明顯的缺陷：

• 擴展性較差，如果服務(wù)需要擴容，自增起始值和自增步長都需要整體重新設(shè)置。
• 強依賴數(shù)據(jù)庫，數(shù)據(jù)庫掛了整個服務(wù)不可用，且數(shù)據(jù)庫的 IO 性能會成為整個服務(wù)的瓶頸。

但其實這些缺陷并非無法解決，有一個 “批量發(fā)號” 思想的解決方案：

TDDL Sequence

這里通過介紹我司 TDDL Sequence 的方案來解釋 “批量發(fā)號” 的思想。其實依然是自增初始值結(jié)合自增步長的思路，但核心思路是通過應(yīng)用層來代理 ID 的自增。只是在數(shù)據(jù)庫中記錄當前場景的 ID 最大值，通過在應(yīng)用側(cè)設(shè)置了自增步長，每次通過數(shù)據(jù)庫拿到當前場景的 ID 起始值，就在本地得到了一個“號段”，此時更新數(shù)據(jù)庫記錄當前最新的 ID 最大值，之后這個 “號段” 維護在內(nèi)存中，ID 自增通過在內(nèi)存中自增后直接返回，當這個 “號段” 消耗殆盡后，再重復(fù)之前的操作，得到一個新的號段。
舉個例子，當前場景下，應(yīng)用配置的自增步長為 1000，且當前數(shù)據(jù)庫中 ID 最大值為 1000，那么第一次請求數(shù)據(jù)庫，會將當前場景的 ID 最大值更新到 2000，并得到號段 [1000, 2000)，在這個區(qū)間內(nèi)的自增 ID 全部通過內(nèi)存生成，當生成到 2000 的時候，再次請求數(shù)據(jù)庫，將當前場景的 ID 最大值更新為 3000，并在內(nèi)存中維護號段 [2000, 3000)。

CREATE TABLE `sequence` (
  `id` BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
  `name` VARCHAR(64) NOT NULL,
  `value` BIGINT NOT NULL,
  `gmt_create` TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
  `gmt_modified` TIMESTAMP NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `uk_unique_name` (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

但如果自增是在內(nèi)存中執(zhí)行的，是否會存在多臺機器申請到同一 “號段” 導(dǎo)致出現(xiàn)重復(fù) ID 呢？這個部分是通過在請求數(shù)據(jù)庫階段的樂觀鎖實現(xiàn)的，因為當前機器確定使用這個號段前，會更新數(shù)據(jù)庫當前最大 ID 值，通過樂觀鎖機制，如果拿老的最大 ID 值更新沒有成功，意味著需要再去嘗試取下一個 “號段”，直到成功更新數(shù)據(jù)庫記錄為止。這個過程的時序如下：

另外也不需要擔心因為應(yīng)用重啟導(dǎo)致內(nèi)存中維護號段丟失的問題，因為啟動后一定會申請一個新號段，只是可能會存在一些 ID 的浪費，但這個問題通?？梢院雎?。

Leaf-segment

美團 Leaf-segment 的思路其實幾乎和 TDDL Sequence 非常類似，不再額外說明。不過針對號段消耗殆盡后會同步請求數(shù)據(jù)庫，對性能 TP999 指標有一定影響，故其設(shè)計了 “雙 Buffer優(yōu)化” 方案，本質(zhì)上就是在監(jiān)控號段已經(jīng)消耗到比如 20% 的情況下，就會提前通過異步的方式拉取下一個號段，避免號段消耗殆盡后的數(shù)據(jù)庫 IO 對性能 TP999 指標的影響。

滴滴也曾開源了 tinyid，其生成 ID 的思想和上述方案幾乎一致，就不再贅述。

類雪花算法

雪花算法是 Twitter 工程師提出的生成全局唯一 ID 的方案，它使用固定的 64 位二進制表示一個 ID，最后可以通過長整型的數(shù)據(jù)類型存儲這個 ID。第一位為保留位，固定為 0，后面 41 位是 時間戳位，表示當前時間戳，那么算一下最多可以表示 （1L<<41）/(1000L*3600*24*365)=69 年的時間，再后面 10 位是 機器標識位，可以分別表示 1024 臺機器。最后的 12 位為 序列號位，或者是自增序列位，可以表示 4096 個 ID，理論上 snowflake 方案的 QPS 約為 409.6w/s，這種分配方式可以保證在任何一個 IDC 的任何一臺機器在任意毫秒內(nèi)生成的 ID 都是不同的。
之所以標題叫 “類雪花算法”，原因是位數(shù)的分配，實際是可以自己調(diào)整的。比如單元化架構(gòu)，多地分別有不同的機房，或者一個集群的機器數(shù)量超過了 1024 臺，那么都可以根據(jù)實際情況去調(diào)整，比如需要單元化架構(gòu)但一個應(yīng)用的機器數(shù)量不可能超過 1024 臺，那么可以將原來的 10 位機器位拿出兩位來表示單元，8 位去標識機器。這個通常根據(jù)自己業(yè)務(wù)的實際情況可以靈活調(diào)整。
類雪花算法由于依賴本地時間，會有一個知名的時間回撥問題：

時間回撥問題

所謂時間回撥，即當前得到的本地時間小于了之前獲取的本地時間，感覺時針被“回撥”了。那么什么情況下可能出現(xiàn)時間回撥問題呢？

• 人工設(shè)置
• NTP 網(wǎng)絡(luò)時間同步

人工設(shè)置的情況不多做解釋，一般也很少發(fā)生。NTP 網(wǎng)絡(luò)時間同步是一個時間同步協(xié)議，C/S 架構(gòu)，服務(wù)器通過從權(quán)威設(shè)施（原子鐘、GPS）獲取到當前時間后，同時考慮傳輸時間差進行時間校準后得到當前的準確時間。首先我們?nèi)粘＜矣玫臅r鐘，包括機器上的時鐘通常是石英材質(zhì)，石英材質(zhì)的時鐘精度雖然可以滿足家用，但實際存在誤差，也就意味著通過網(wǎng)絡(luò)時間同步后的時間可能會出現(xiàn)回撥現(xiàn)象。
這里不得不提到閏秒問題，什么是閏秒？

為確定時間，世界上有兩種常用的時間計量系統(tǒng)：基于地球自轉(zhuǎn)的世界時（UT）和基于原子振蕩周期的國際原子時（TAI）。由于兩種測量方法不同，隨著時間推移，兩個計時系統(tǒng)結(jié)果會出現(xiàn)差異，因此有了協(xié)調(diào)世界時的概念。 協(xié)調(diào)世界時以國際原子時秒長為基礎(chǔ)，在時刻上盡量接近世界時。1972年的國際計量大會決定，當國際原子時與世界時的時刻相差達到0.9秒時，協(xié)調(diào)世界時就增加或減少 1 秒，以盡量接近世界時，這個修正被稱作閏秒。

簡單表達，就是地球自轉(zhuǎn)速率本身不是一個穩(wěn)定的值，為了磨平誤差，世界時可能會出現(xiàn)減少 1 秒的情況，而網(wǎng)絡(luò)時間同步又會去同步世界時，于是便發(fā)生了時間回撥問題。
過去已經(jīng)有幾個知名的因為閏秒導(dǎo)致的故障：2012 年實施閏秒時，引發(fā)了 Reddit 的大規(guī)模故障，以及 Mozilla、LinkedIn、Yelp 和航空預(yù)訂服務(wù) Amadeus 的相關(guān)問題。2017 年，Cloudflare 的一個閏秒故障使這家網(wǎng)絡(luò)基礎(chǔ)設(shè)施公司的一部分客戶的服務(wù)器離線。
總之時間回撥問題無法避免，對于強依賴本地時間的計算，都需要考慮時間回撥問題的處理。

閏秒將在 2035 年被取消，喜大普奔。

Leaf-snowflake

美團的 Leaf-snowflake 是基于雪花算法的 ID 生成方案，通過獨立的集群服務(wù)對外提供能力，其機器標識位依賴 Zookeeper 生成，機器本地會備份一份結(jié)果用于 Zookeeper 的災(zāi)備。
首先記錄上一次生成 ID 的時間戳，如果本次的時間戳還小于上次的，那么說明發(fā)生時間回撥，如果時間偏差較小，則等待這個時間差過去，再進行生成，否則拋出異常拒絕服務(wù)，并且將當前機器剔除。

//發(fā)生了回撥，此刻時間小于上次發(fā)號時間
if (timestamp < lastTimestamp) {
    long offset = lastTimestamp - timestamp;
    if (offset <= 5) {
        try {
            //時間偏差大小小于5ms，則等待兩倍時間
            wait(offset << 1);//wait
            timestamp = timeGen();
            if (timestamp < lastTimestamp) {
                //還是小于，拋異常并上報
                throwClockBackwardsEx(timestamp);
            }    
        } catch (InterruptedException e) {  
            throw  e;
        }
    } else {
        //throw
        throwClockBackwardsEx(timestamp);
    }
}
//分配ID       

Seata UUID

Seata 的 UUID 生成器是基于雪花算法改良的，針對上述的時間回撥問題進行了解決，同時也進一步突破了原來雪花算法的性能瓶頸。
時間回撥問題本質(zhì)是每次生成 ID 都會依賴本地時間，Seata UUID 生成器改良成了僅在應(yīng)用啟動是記錄當前的時間戳，之后的生產(chǎn)就不再依賴，時間戳位的更新改成了依賴序列號位的溢出，每次當序列號位溢出（即已達到 4096）后將時間戳位進位。

這樣的改變相當于即解決了時鐘回撥問題，也突破了 4096/ms 的生產(chǎn)性能瓶頸，相當于有 53 位參與遞增。

那么這樣的改變是否有問題？因為在并發(fā)較高的情況下，會出現(xiàn) 超前消費，消費速率超過 4096/ms 的情況下，時間戳位的進位速度以及超過了當前時間戳的值，那么這個時候應(yīng)用重啟再拿當前的時間戳作為初始值，是否就會出現(xiàn)大量重復(fù) ID 的情況呢？沒錯，理論可能，但這個問題實際被 Seata 忽略了，原因是如果真的持續(xù)是這樣的 QPS，瓶頸不就不再 UUID 生成器了，Seata 服務(wù)本身就撐不住。

當然由于每次生成的 ID 對本地時間不再是強依賴了，那么意味著這個 ID 在有限范圍內(nèi)是可被枚舉的，不過由于是用在分布式事務(wù)的場景下，這個問題可以忽略。

總結(jié)

如果場景簡單，直接使用 UUID 即可。如果僅是因為數(shù)據(jù)量比較大，需要分庫分表，那么類似 TDDL Sequence 的方案也完全足夠。除此之外，需要具體問題具體分析：

• 如果唯一 ID 要落庫，且可預(yù)見的會無限增長（比如是一個通用服務(wù)），需要一個定長 ID 來保證數(shù)據(jù)庫字段長度的確定性，傾向于考慮類雪花算法的方案。
• 如果判斷服務(wù)需要承載的并發(fā)較高，則最好不要考慮 UUID 的方案。
• 如果業(yè)務(wù)場景強依賴 ID 進行排序的，必須要求 ID 單調(diào)遞增，則選擇類雪花算法的方案。

到此這篇關(guān)于Java幾種分布式全局唯一ID生成方案的文章就介紹到這了,更多相關(guān)Java分布式全局唯一ID生成方案內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論