緣起

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

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

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

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

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

常見方案

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

• 單機自行生成，不依賴其他服務，來保證全局唯一性。
• 應用集群，應用服務的業(yè)務場景內(nèi)保證全局唯一 ID。
• 獨立服務提供通用的生產(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。重復機率與隨機數(shù)產(chǎn)生器的質(zhì)量有關。
• 版本5 - 基于名字空間的 UUID（SHA1版）：將版本 3 的散列算法改為 SHA1。

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

UUID 的優(yōu)勢：

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

UUID 的劣勢：

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

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

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

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

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

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

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

TDDL Sequence

這里通過介紹我司 TDDL Sequence 的方案來解釋 “批量發(fā)號” 的思想。其實依然是自增初始值結(jié)合自增步長的思路，但核心思路是通過應用層來代理 ID 的自增。只是在數(shù)據(jù)庫中記錄當前場景的 ID 最大值，通過在應用側(cè)設置了自增步長，每次通過數(shù)據(jù)庫拿到當前場景的 ID 起始值，就在本地得到了一個“號段”，此時更新數(shù)據(jù)庫記錄當前最新的 ID 最大值，之后這個 “號段” 維護在內(nèi)存中，ID 自增通過在內(nèi)存中自增后直接返回，當這個 “號段” 消耗殆盡后，再重復之前的操作，得到一個新的號段。
舉個例子，當前場景下，應用配置的自增步長為 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í)行的，是否會存在多臺機器申請到同一 “號段” 導致出現(xiàn)重復 ID 呢？這個部分是通過在請求數(shù)據(jù)庫階段的樂觀鎖實現(xiàn)的，因為當前機器確定使用這個號段前，會更新數(shù)據(jù)庫當前最大 ID 值，通過樂觀鎖機制，如果拿老的最大 ID 值更新沒有成功，意味著需要再去嘗試取下一個 “號段”，直到成功更新數(shù)據(jù)庫記錄為止。這個過程的時序如下：

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

Leaf-segment

美團 Leaf-segment 的思路其實幾乎和 TDDL Sequence 非常類似，不再額外說明。不過針對號段消耗殆盡后會同步請求數(shù)據(jù)庫，對性能 TP999 指標有一定影響，故其設計了 “雙 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)但一個應用的機器數(shù)量不可能超過 1024 臺，那么可以將原來的 10 位機器位拿出兩位來表示單元，8 位去標識機器。這個通常根據(jù)自己業(yè)務的實際情況可以靈活調(diào)整。
類雪花算法由于依賴本地時間，會有一個知名的時間回撥問題：

時間回撥問題

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

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

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

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

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

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

Leaf-snowflake

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

//發(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 生成器改良成了僅在應用啟動是記錄當前的時間戳，之后的生產(chǎn)就不再依賴，時間戳位的更新改成了依賴序列號位的溢出，每次當序列號位溢出（即已達到 4096）后將時間戳位進位。

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

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

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

總結(jié)

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

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

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

最新評論