前言

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

有很多業(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是一個長度為128位的標(biāo)志符，能夠在時間和空間上確保其唯一性。

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

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

UUID是基于時間戳、MAC地址、隨機數(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);
    }
}

運行結(jié)果：

22527933-d0a7-4c2b-a377-aeb438a31b02

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

缺點：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ù)代碼中，不需要做任何處理，這個ID的值，是由數(shù)據(jù)庫自動生成的，并且它會保證數(shù)據(jù)的唯一性。

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

缺點：只能保證單表的數(shù)據(jù)唯一性，如果跨表或者跨數(shù)據(jù)庫，ID可能會重復(fù)。ID是自增的，生成規(guī)則很容易被猜透，有安全風(fēng)險。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方案做一個優(yōu)化。

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

圖片

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

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

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

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

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

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

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

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

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

圖片

在生成ID的時候，一個請求只能寫入一個master實例。

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

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

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

缺點：跨多個master實例下生成的ID，可能不是遞增的。

5 Redis生成ID

除了使用數(shù)據(jù)庫之外，Redis其實也能產(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。

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

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

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

6 Zookeeper生成ID

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

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

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

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

7 雪花算法

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

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

圖片

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

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

10位的機器標(biāo)識，10位的長度最多支持部署1024個節(jié)點

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

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

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

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

8 Leaf

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

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

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

圖片

這個模式就是我們在第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個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。

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

圖片

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

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

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

圖片

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

9 Tinyid

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

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

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

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

圖片

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

如果號段還沒有加載，或者已經(jīng)用完了，則需要向db再申請一個新的可用號段，多臺server之間因為號段生成算法的原子性，而保證每臺server上的可用號段不重，從而使id生成不重。

但也帶來了這些問題：

• 當(dāng)id用完時需要訪問db加載新的號段，db更新也可能存在version沖突，此時id生成耗時明顯增加。
• db是一個單點，雖然db可以建設(shè)主從等高可用架構(gòu)，但始終是一個單點。
• 使用http方式獲取一個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中的號段在用到一定程度的時候，就會去異步加載下一個號段，保證內(nèi)存中始終有可用號段。
• 增加多db支持：每個DB都能生成唯一ID，提高了可用性。

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

10 UidGenerator

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

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

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

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

圖片

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

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

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

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

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

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

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

圖片

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

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

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