前言

分布式ID，在我們?nèi)粘５拈_發(fā)中，其實(shí)使用的挺多的。

有很多業(yè)務(wù)場景在用，比如：

1. 分布式鏈路系統(tǒng)的trace_id
2. 單表中的主鍵
3. Redis中分布式鎖的key
4. 分庫分表后表的id

今天跟大家一起聊聊分布式ID的一些常見方案，希望對你會有所幫助。

圖片

1 UUID

UUID (Universally Unique IDentifier) 通用唯一識別碼 ，也稱為 GUID (Globally Unique IDentifier) 全球唯一標(biāo)識符。

UUID是一個(gè)長度為128位的標(biāo)志符，能夠在時(shí)間和空間上確保其唯一性。

UUID最初應(yīng)用于Apollo網(wǎng)絡(luò)計(jì)算系統(tǒng)，隨后在Open Software Foundation（OSF）的分布式計(jì)算環(huán)境（DCE）中得到應(yīng)用。

可讓分布式系統(tǒng)可以不借助中心節(jié)點(diǎn)，就可以生成唯一標(biāo)識， 比如唯一的ID進(jìn)行日志記錄。

UUID是基于時(shí)間戳、MAC地址、隨機(jī)數(shù)等多種因素生成，理論上全球范圍內(nèi)幾乎不可能重復(fù)。

在Java中可以通過UUID的randomUUID方法獲取唯一字符串：

import java.util.UUID;

/**
 * @author 蘇三
 * @date 2024/9/13 上午10:38
 */
public class UuidTest {
    public static void main(String[] args) {
        String uuid = UUID.randomUUID().toString();
        System.out.println(uuid);
    }
}

運(yùn)行結(jié)果：

22527933-d0a7-4c2b-a377-aeb438a31b02

優(yōu)點(diǎn)：UUID不借助中心節(jié)點(diǎn)，可以保持程序的獨(dú)立性，可以保證程序在不同的數(shù)據(jù)庫之間，做數(shù)據(jù)遷移，都不受影響。

缺點(diǎn)：UUID生成的字符串太長，通過索引查詢數(shù)據(jù)的效率比較低。此外，UUID生成的字符串，順序沒有保證，不是遞增的，不滿足工作中的有些業(yè)務(wù)場景。

在分布式日志系統(tǒng)或者分布式鏈路跟蹤系統(tǒng)中，可以使用UUID生成唯一標(biāo)識，用于串聯(lián)請求的日志。

2 數(shù)據(jù)庫自增ID

在很多數(shù)據(jù)庫中自增的主鍵ID，數(shù)據(jù)庫本身是能夠保證唯一的。

MySQL中的auto_increment。

Oracle中sequence。

我們在業(yè)務(wù)代碼中，不需要做任何處理，這個(gè)ID的值，是由數(shù)據(jù)庫自動生成的，并且它會保證數(shù)據(jù)的唯一性。

優(yōu)點(diǎn)：非常簡單，數(shù)據(jù)查詢效率非常高。

缺點(diǎn)：只能保證單表的數(shù)據(jù)唯一性，如果跨表或者跨數(shù)據(jù)庫，ID可能會重復(fù)。ID是自增的，生成規(guī)則很容易被猜透，有安全風(fēng)險(xiǎn)。ID是基于數(shù)據(jù)庫生成的，在高并發(fā)下，可能會有性能問題。

在一些老系統(tǒng)或者公司的內(nèi)部管理系統(tǒng)中，可能會用數(shù)據(jù)庫遞增ID作為分布式ID的方案，這些系統(tǒng)的用戶并發(fā)量一般比較小，數(shù)據(jù)量也不多。

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

在高并發(fā)的系統(tǒng)中，頻繁訪問數(shù)據(jù)庫，會影響系統(tǒng)的性能。

可以對數(shù)據(jù)庫自增ID方案做一個(gè)優(yōu)化。

一次生成一定步長的ID，比如：步長是1000，每次數(shù)據(jù)庫自增1000，ID值從100001變成了101001。

圖片

將100002~101001這個(gè)號段的1000個(gè)ID，緩存到服務(wù)器的內(nèi)存從。

當(dāng)有獲取分布式ID的請求過來時(shí)，先從服務(wù)器的內(nèi)存中獲取數(shù)據(jù)，如果能夠獲取到，則直接返回。

如果沒有獲取到，則說明緩存的號段的數(shù)據(jù)已經(jīng)被獲取完了。

這時(shí)需要重新從數(shù)據(jù)庫中獲取一次新號段的ID，緩存到服務(wù)器的內(nèi)存中，這樣下次又能直接從內(nèi)存中獲取ID了。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，對數(shù)據(jù)庫的依賴減弱了，可以提升系統(tǒng)的性能。

缺點(diǎn)：ID是自增的，生成規(guī)則很容易被猜透，有安全風(fēng)險(xiǎn)。如果數(shù)據(jù)庫是單節(jié)點(diǎn)的，有巖機(jī)的風(fēng)險(xiǎn)。

4 數(shù)據(jù)庫的多主模式

為了解決上面單節(jié)點(diǎn)巖機(jī)問題，我們可以使用數(shù)據(jù)庫的多主模式。

即有多個(gè)master數(shù)據(jù)庫實(shí)例。

圖片

在生成ID的時(shí)候，一個(gè)請求只能寫入一個(gè)master實(shí)例。

為了保證在不同的master實(shí)例下ID的唯一性，我們需要事先規(guī)定好每個(gè)master下的大的區(qū)間，比如：master1的數(shù)據(jù)是10開頭的，master2的數(shù)據(jù)是11開頭的，master3的數(shù)據(jù)是12開頭的。

然后每個(gè)master，還是按照數(shù)據(jù)庫號段模式來處理。

優(yōu)點(diǎn)：避免了數(shù)據(jù)庫號段模式的單節(jié)點(diǎn)巖機(jī)風(fēng)險(xiǎn)，提升了系統(tǒng)的穩(wěn)定性，由于結(jié)合使用了號段模式，系統(tǒng)性能也是OK的。

缺點(diǎn)：跨多個(gè)master實(shí)例下生成的ID，可能不是遞增的。

5 Redis生成ID

除了使用數(shù)據(jù)庫之外，Redis其實(shí)也能產(chǎn)生自增ID。

我們可以使用Redis中的incr命令：

redis> SET ID_VALUE 1000
OK

redis> INCR ID_VALUE
(integer) 1001

redis> GET ID_VALUE 
"1001"

給ID_VALUE設(shè)置了值是1000，然后使用INCR命令，可以每次都加1。

這個(gè)方案跟我們之前討論過的方案1（數(shù)據(jù)庫自增ID）的方案類似。

優(yōu)點(diǎn)：方案簡單，性能比方案1更好，避免了跨表或者跨數(shù)據(jù)庫，ID重復(fù)的問題。

缺點(diǎn)：ID是自增的，生成規(guī)則很容易被猜透，有安全風(fēng)險(xiǎn)。并且Redis可能也存在單節(jié)點(diǎn)，巖機(jī)的風(fēng)險(xiǎn)。

6 Zookeeper生成ID

Zookeeper主要通過其znode數(shù)據(jù)版本來生成序列號，可以生成32位和64位的數(shù)據(jù)版本號，客戶端可以使用這個(gè)版本號來作為唯一的序列號。

由于需要高度依賴Zookeeper，并且是同步調(diào)用API，如果在競爭較大的情況下，需要考慮使用分布式鎖。

因此，性能在高并發(fā)的分布式環(huán)境下，也不太理想。

很少人會使用Zookeeper來生成唯一ID。

7 雪花算法

Snowflake(雪花算法)是Twitter開源的分布式ID算法。

核心思想：使用一個(gè) 64 bit 的 long 型的數(shù)字作為全局唯一 id。

圖片

最高位是符號位，始終為0，不可用。

41位的時(shí)間序列，精確到毫秒級，41位的長度可以使用69年。時(shí)間位還有一個(gè)很重要的作用是可以根據(jù)時(shí)間進(jìn)行排序。

10位的機(jī)器標(biāo)識，10位的長度最多支持部署1024個(gè)節(jié)點(diǎn)

12位的計(jì)數(shù)序列號，序列號即一系列的自增id，可以支持同一節(jié)點(diǎn)同一毫秒生成多個(gè)ID序號，12位的計(jì)數(shù)序列號支持每個(gè)節(jié)點(diǎn)每毫秒產(chǎn)生4096個(gè)ID序號。

優(yōu)點(diǎn)：算法簡單，在內(nèi)存中進(jìn)行，效率高。高并發(fā)分布式環(huán)境下生成不重復(fù)ID，每秒可生成百萬個(gè)不重復(fù)ID?；跁r(shí)間戳，以及同一時(shí)間戳下序列號自增，基本保證ID有序遞增。并且不依賴第三方庫或者中間件，穩(wěn)定性更好。

缺點(diǎn)：依賴服務(wù)器時(shí)間，服務(wù)器時(shí)鐘回?fù)軙r(shí)可能會生成重復(fù)ID。

最近整理了一份10萬字的面試寶典，可以免費(fèi)送給大家，獲取方式加我微信：su_san_java，備注：面試。

8 Leaf

Leaf是美團(tuán)開源的分布式ID生成系統(tǒng)，它提供了兩種生成ID的方式：

• Leaf-segment號段模式
• Leaf-snowflake雪花算法

Leaf-segment號段模式，需要創(chuàng)建一張表：

圖片

這個(gè)模式就是我們在第3節(jié)講過的數(shù)據(jù)庫號段模式。

biz_tag用來區(qū)分業(yè)務(wù)，max_id表示該biz_tag目前所被分配的ID號段的最大值，step表示每次分配的號段長度。

原來獲取ID每次都需要寫數(shù)據(jù)庫，現(xiàn)在只需要把step設(shè)置得足夠大，比如1000。那么只有當(dāng)1000個(gè)號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。

Leaf-snowflake雪花算法，是在傳統(tǒng)雪花算法之上，加上Zookeeper，做了一點(diǎn)改造：

圖片

Leaf-snowflake服務(wù)需要從Zookeeper按順序的獲取workId，會緩存到本地。

如果Zookeeper出現(xiàn)異常，Leaf-snowflake服務(wù)會直接獲取本地的workId，它相當(dāng)于對Zookeeper是弱依賴的。

因?yàn)檫@種方案依賴時(shí)間，如果機(jī)器的時(shí)鐘發(fā)生了回?fù)?，那么就會有可能生成重?fù)的ID號，它內(nèi)部有一套機(jī)制解決機(jī)器時(shí)鐘回?fù)艿膯栴}：

圖片

如果你想知道美團(tuán)Leaf的更多細(xì)節(jié)，可以看看Github地址：https://github.com/Meituan-Dianping/Leaf

9 Tinyid

Tinyid是滴滴用Java開發(fā)的一款分布式id生成系統(tǒng)，基于數(shù)據(jù)庫號段算法實(shí)現(xiàn)。

Tinyid是在美團(tuán)的ID生成算法Leaf的基礎(chǔ)上擴(kuò)展而來，支持?jǐn)?shù)據(jù)庫多主節(jié)點(diǎn)模式，它提供了REST API和JavaClient兩種獲取方式，相對來說使用更方便。

但跟美團(tuán)Leaf不同的是，Tinyid只支持號段一種模式，并不支持Snowflake模式。

基于數(shù)據(jù)庫號段模式的簡單架構(gòu)方案：

圖片

ID生成系統(tǒng)向外提供http服務(wù)，請求經(jīng)過負(fù)載均衡router，能夠路由到其中一臺tinyid-server，這樣就能從事先加載好的號段中獲取一個(gè)ID了。

如果號段還沒有加載，或者已經(jīng)用完了，則需要向db再申請一個(gè)新的可用號段，多臺server之間因?yàn)樘柖紊伤惴ǖ脑有?，而保證每臺server上的可用號段不重，從而使id生成不重。

但也帶來了這些問題：

• 當(dāng)id用完時(shí)需要訪問db加載新的號段，db更新也可能存在version沖突，此時(shí)id生成耗時(shí)明顯增加。
• db是一個(gè)單點(diǎn)，雖然db可以建設(shè)主從等高可用架構(gòu)，但始終是一個(gè)單點(diǎn)。
• 使用http方式獲取一個(gè)id，存在網(wǎng)絡(luò)開銷，性能和可用性都不太好。

為了解決這些這些問題：增加了tinyid-client本地生成ID、使用雙號段緩存、增加多 db 支持提高服務(wù)的穩(wěn)定性。

最終的架構(gòu)方案如下：

圖片

Tinyid方案主要做了下面這些優(yōu)化：

• 增加tinyid-client：tinyid-client向tinyid-server發(fā)送請求來獲取可用號段，之后在本地構(gòu)建雙號段、id生成，如此id生成則變成純本地操作，性能大大提升。
• 使用雙號段緩存：為了避免在獲取新號段的情況下，程序獲取唯一ID的速度比較慢。Tinyid中的號段在用到一定程度的時(shí)候，就會去異步加載下一個(gè)號段，保證內(nèi)存中始終有可用號段。
• 增加多db支持：每個(gè)DB都能生成唯一ID，提高了可用性。

如果你想知道滴滴Tinyid的更多細(xì)節(jié)，可以看看Github地址：https://github.com/didi/tinyid

10 UidGenerator

百度 UID-Generator 使用 Java 語言，基于雪花算法實(shí)現(xiàn)。

UidGenerator以組件形式工作在應(yīng)用項(xiàng)目中, 支持自定義workerId位數(shù)和初始化策略, 從而適用于docker等虛擬化環(huán)境下實(shí)例自動重啟、漂移等場景。

在實(shí)現(xiàn)上, UidGenerator通過借用未來時(shí)間來解決sequence天然存在的并發(fā)限制。

采用RingBuffer來緩存已生成的UID, 并行化UID的生產(chǎn)和消費(fèi), 同時(shí)對CacheLine補(bǔ)齊，避免了由RingBuffer帶來的硬件級「偽共享」問題. 最終單機(jī)QPS可達(dá)600萬。

圖片

Snowflake算法描述：指定機(jī)器 & 同一時(shí)刻 & 某一并發(fā)序列，是唯一的。據(jù)此可生成一個(gè)64 bits的唯一ID（long）。默認(rèn)采用上圖字節(jié)分配方式：

• sign(1bit)：固定1bit符號標(biāo)識，即生成的UID為正數(shù)。
• delta seconds (28 bits) ：當(dāng)前時(shí)間，相對于時(shí)間基點(diǎn)"2016-05-20"的增量值，單位：秒，最多可支持約8.7年
• worker id (22 bits)：機(jī)器id，最多可支持約420w次機(jī)器啟動。內(nèi)置實(shí)現(xiàn)為在啟動時(shí)由數(shù)據(jù)庫分配，默認(rèn)分配策略為用后即棄，后續(xù)可提供復(fù)用策略。
• sequence (13 bits)：每秒下的并發(fā)序列，13 bits可支持每秒8192個(gè)并發(fā)。

sequence決定了UidGenerator的并發(fā)能力，13 bits的 sequence 可支持 8192/s 的并發(fā)，但現(xiàn)實(shí)中很有可能不夠用，從而誕生了 CachedUidGenerator。

CachedUidGenerator 使用 RingBuffer 緩存生成的id。RingBuffer是個(gè)環(huán)形數(shù)組，默認(rèn)大小為 8192 個(gè)（可以通過boostPower參數(shù)設(shè)置大?。?/p>

RingBuffer環(huán)形數(shù)組，數(shù)組每個(gè)元素成為一個(gè) slot。

Tail 指針、Cursor 指針用于環(huán)形數(shù)組上讀寫 slot：

• Tail指針：表示 Producer 生產(chǎn)的最大序號(此序號從 0 開始，持續(xù)遞增)。Tail 不能超過 Cursor，即生產(chǎn)者不能覆蓋未消費(fèi)的 slot。當(dāng) Tail 已趕上 curosr，此時(shí)可通過 rejectedPutBufferHandler 指定 PutRejectPolicy。
• Cursor指針：表示 Consumer 消費(fèi)到的最小序號(序號序列與 Producer 序列相同)。Cursor 不能超過 Tail，即不能消費(fèi)未生產(chǎn)的 slot。當(dāng) Cursor 已趕上 tail，此時(shí)可通過 rejectedTakeBufferHandler 指定 TakeRejectPolicy。

圖片

RingBuffer填充觸發(fā)機(jī)制:

• 程序啟動時(shí)，將RingBuffer填充滿。
• 在調(diào)用getUID()方法獲取id時(shí)，如果檢測到RingBuffer中的剩余id個(gè)數(shù)小于總個(gè)數(shù)的50%，將RingBuffer填充滿。
• 定時(shí)填充（可配置是否使用以及定時(shí)任務(wù)的周期）。

如果你想知道百度uid-generator的更多細(xì)節(jié)，可以看看Github地址：https://github.com/baidu/uid-generator