緣起

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

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

對(duì)于全局唯一 ID 來(lái)說(shuō)，通常具備以下特點(diǎn)：

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

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

常見(jiàn)方案

通常來(lái)說(shuō)全局唯一 ID 的生成方案也分幾類(lèi)：

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

下面來(lái)具體介紹業(yè)界常見(jiàn)的一些方案：

UUID

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

UUID 一共有 5 個(gè)版本：

• 版本1 - 基于時(shí)間的 UUID：主要依賴當(dāng)前的時(shí)間戳及機(jī)器 mac 地址，因此可以保證全球唯一性。
• 版本2 - 分布式安全的 UUID：將版本1的時(shí)間戳前四位換為 POSIX 的 UID 或 GID，很少使用。
• 版本3 - 基于名字空間的 UUID（MD5 版）：基于指定的名字空間/名字生成 MD5 散列值得到，標(biāo)準(zhǔn)不推薦。
• 版本4 - 基于隨機(jī)數(shù)的 UUID：基于偽隨機(jī)數(shù)，生成 16byte 隨機(jī)值填充 UUID。重復(fù)機(jī)率與隨機(jī)數(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)勢(shì)：

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

UUID 的劣勢(shì)：

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

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

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

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

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

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

但其實(shí)這些缺陷并非無(wú)法解決，有一個(gè) “批量發(fā)號(hào)” 思想的解決方案：

TDDL Sequence

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

另外也不需要擔(dān)心因?yàn)閼?yīng)用重啟導(dǎo)致內(nèi)存中維護(hù)號(hào)段丟失的問(wèn)題，因?yàn)閱?dòng)后一定會(huì)申請(qǐng)一個(gè)新號(hào)段，只是可能會(huì)存在一些 ID 的浪費(fèi)，但這個(gè)問(wèn)題通常可以忽略。

Leaf-segment

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

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

類(lèi)雪花算法

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

時(shí)間回?fù)軉?wèn)題

所謂時(shí)間回?fù)?，即?dāng)前得到的本地時(shí)間小于了之前獲取的本地時(shí)間，感覺(jué)時(shí)針被“回?fù)?rdquo;了。那么什么情況下可能出現(xiàn)時(shí)間回?fù)軉?wèn)題呢？

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

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

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

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

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

Leaf-snowflake

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

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

Seata UUID

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

這樣的改變相當(dāng)于即解決了時(shí)鐘回?fù)軉?wèn)題，也突破了 4096/ms 的生產(chǎn)性能瓶頸，相當(dāng)于有 53 位參與遞增。

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

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

總結(jié)

如果場(chǎng)景簡(jiǎn)單，直接使用 UUID 即可。如果僅是因?yàn)閿?shù)據(jù)量比較大，需要分庫(kù)分表，那么類(lèi)似 TDDL Sequence 的方案也完全足夠。除此之外，需要具體問(wèn)題具體分析：

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

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

最新評(píng)論