分布式系統(tǒng)中，有一些需要使用全局唯一 ID 的場景，這種時候為了防止 ID 沖突可以使用 36 位的 UUID，但是 UUID 有一些缺點，首先他相對比較長，另外 UUID 一般是無序的

有些時候我們希望能使用一種簡單些的 ID，并且希望 ID 能夠按照時間有序生成

什么是雪花算法

Snowflake 中文的意思是雪花，所以常被稱為雪花算法，是 Twitter 開源的分布式 ID 生成算法

Twitter 雪花算法生成后是一個 64bit 的 long 型的數(shù)值，組成部分引入了時間戳，基本保持了自增

SnowFlake 算法的優(yōu)點：

1. 高性能高可用：生成時不依賴于數(shù)據(jù)庫，完全在內(nèi)存中生成
2. 高吞吐：每秒鐘能生成數(shù)百萬的自增 ID
3. ID 自增：存入數(shù)據(jù)庫中，索引效率高

SnowFlake 算法的缺點：

依賴與系統(tǒng)時間的一致性，如果系統(tǒng)時間被回調(diào)，或者改變，可能會造成 ID 沖突或者重復(fù)

雪花算法組成

snowflake 結(jié)構(gòu)如下圖所示：

包含四個組成部分

不使用：1bit，最高位是符號位，0 表示正，1 表示負(fù)，固定為 0

時間戳：41bit，毫秒級的時間戳（41 位的長度可以使用 69 年）

標(biāo)識位：5bit 數(shù)據(jù)中心 ID，5bit 工作機(jī)器 ID，兩個標(biāo)識位組合起來最多可以支持部署 1024 個節(jié)點

序列號：12bit 遞增序列號，表示節(jié)點毫秒內(nèi)生成重復(fù)，通過序列號表示唯一，12bit 每毫秒可產(chǎn)生 4096 個 ID

通過序列號 1 毫秒可以產(chǎn)生 4096 個不重復(fù) ID，則 1 秒可以生成 4096 * 1000 = 409w ID

默認(rèn)的雪花算法是 64 bit，具體的長度可以自行配置。如果希望運(yùn)行更久，增加時間戳的位數(shù)；如果需要支持更多節(jié)點部署，增加標(biāo)識位長度；如果并發(fā)很高，增加序列號位數(shù)

總結(jié)：雪花算法并不是一成不變的，可以根據(jù)系統(tǒng)內(nèi)具體場景進(jìn)行定制

雪花算法適用場景

因為雪花算法有序自增，保障了 MySQL 中 B+ Tree 索引結(jié)構(gòu)插入高性能

所以，日常業(yè)務(wù)使用中，雪花算法更多是被應(yīng)用在數(shù)據(jù)庫的主鍵 ID 和業(yè)務(wù)關(guān)聯(lián)主鍵

雪花算法生成 ID 重復(fù)問題

假設(shè)：一個訂單微服務(wù)，通過雪花算法生成 ID，共部署三個節(jié)點，標(biāo)識位一致

此時有 200 并發(fā)，均勻散布三個節(jié)點，三個節(jié)點同一毫秒同一序列號下生成 ID，那么就會產(chǎn)生重復(fù) ID

通過上述假設(shè)場景，可以知道雪花算法生成 ID 沖突存在一定的前提條件

1. 服務(wù)通過集群的方式部署，其中部分機(jī)器標(biāo)識位一致
2. 業(yè)務(wù)存在一定的并發(fā)量，沒有并發(fā)量無法觸發(fā)重復(fù)問題
3. 生成 ID 的時機(jī)：同一毫秒下的序列號一致

標(biāo)識位如何定義

如果能保證標(biāo)識位不重復(fù)，那么雪花 ID 也不會重復(fù)

通過上面的案例，知道了 ID 重復(fù)的必要條件。如果要避免服務(wù)內(nèi)產(chǎn)生重復(fù)的 ID，那么就需要從標(biāo)識位上動文章

我們先看看開源框架中使用雪花算法，如何定義標(biāo)識位

Mybatis-Plus v3.4.2 雪花算法實現(xiàn)類 Sequence，提供了兩種構(gòu)造方法：無參構(gòu)造，自動生成 dataCenterId 和 workerId；有參構(gòu)造，創(chuàng)建 Sequence 時明確指定標(biāo)識位

Hutool v5.7.9 參照了 Mybatis-Plus dataCenterId 和 workerId 生成方案，提供了默認(rèn)實現(xiàn)

一起看下 Sequence 的創(chuàng)建默認(rèn)無參構(gòu)造，如何生成 dataCenterId 和 workerId

public static long getDataCenterId(long maxDatacenterId) {
    long id = 1L;
    final byte[] mac = NetUtil.getLocalHardwareAddress();
    if (null != mac) {
        id = ((0x000000FF & (long) mac[mac.length - 2])
                | (0x0000FF00 & (((long) mac[mac.length - 1]) << 8))) >> 6;
        id = id % (maxDatacenterId + 1);
    }

    return id;
}

入?yún)?maxDatacenterId 是一個固定值，代表數(shù)據(jù)中心 ID 最大值，默認(rèn)值 31

為什么最大值要是 31？因為 5bit 的二進(jìn)制最大是 11111，剛好是 31

獲取 dataCenterId 時存在兩種情況，一種是網(wǎng)絡(luò)接口為空，默認(rèn)取 1L；另一種不為空，通過 Mac 地址獲取 dataCenterId

可以得知，dataCenterId 的取值與 Mac 地址有關(guān)

接下來再看看 workerId

public static long getWorkerId(long datacenterId, long maxWorkerId) {
    final StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    try {
        mpid.append(RuntimeUtil.getPid());
    } catch (UtilException igonre) {
        //ignore
    }
    return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1);
}

入?yún)?maxWorkderId 也是一個固定值，代表工作機(jī)器 ID 最大值，默認(rèn)值 31；datacenterId 取自上述的 getDatacenterId 方法

name 變量值為 PID@IP，所以 name 需要根據(jù) @ 分割并獲取下標(biāo) 0，得到 PID

通過 MAC + PID 的 hashcode 獲取16個低位，進(jìn)行運(yùn)算，最終得到 workerId

分配標(biāo)識位

Mybatis-Plus 標(biāo)識位的獲取依賴 Mac 地址和進(jìn)程 PID，雖然能做到盡量不重復(fù)，但仍有小幾率

標(biāo)識位如何定義才能不重復(fù)？有兩種方案：預(yù)分配和動態(tài)分配

預(yù)分配

應(yīng)用上線前，統(tǒng)計當(dāng)前服務(wù)的節(jié)點數(shù)，人工去申請標(biāo)識位

這種方案，沒有代碼開發(fā)量，在服務(wù)節(jié)點固定或者項目少可以使用，但是解決不了服務(wù)節(jié)點動態(tài)擴(kuò)容性問題

動態(tài)分配

通過將標(biāo)識位存放在 Redis、Zookeeper、MySQL 等中間件，在服務(wù)啟動的時候去請求標(biāo)識位，請求后標(biāo)識位更新為下一個可用的

通過存放標(biāo)識位，延伸出一個問題：雪花算法的 ID 是 服務(wù)內(nèi)唯一還是全局唯一

以 Redis 舉例，如果要做服務(wù)內(nèi)唯一，存放標(biāo)識位的 Redis 節(jié)點使用自己項目內(nèi)的就可以；如果是全局唯一，所有使用雪花算法的應(yīng)用，要用同一個 Redis 節(jié)點

兩者的區(qū)別僅是 不同的服務(wù)間是否公用 Redis。如果沒有全局唯一的需求，最好使 ID 服務(wù)內(nèi)唯一，因為這樣可以避免單點問題

服務(wù)的節(jié)點數(shù)超過 1024，則需要做額外的擴(kuò)展；可以擴(kuò)展 10 bit 標(biāo)識位，或者選擇開源分布式 ID 框架

動態(tài)分配實現(xiàn)方案

Redis 存儲一個 Hash 結(jié)構(gòu) Key，包含兩個鍵值對：dataCenterId 和 workerId

在應(yīng)用啟動時，通過 Lua 腳本去 Redis 獲取標(biāo)識位。dataCenterId 和 workerId 的獲取與自增在 Lua 腳本中完成，調(diào)用返回后就是可用的標(biāo)示位

具體 Lua 腳本邏輯如下：

1. 第一個服務(wù)節(jié)點在獲取時，Redis 可能是沒有 snowflake_work_id_key 這個 Hash 的，應(yīng)該先判斷 Hash 是否存在，不存在初始化 Hash，dataCenterId、workerId 初始化為 0
2. 如果 Hash 已存在，判斷 dataCenterId、workerId 是否等于最大值 31，滿足條件初始化 dataCenterId、workerId 設(shè)置為 0 返回
3. dataCenterId 和 workerId 的排列組合一共是 1024，在進(jìn)行分配時，先分配 workerId
4. 判斷 workerId 是否 != 31，條件成立對 workerId 自增，并返回；如果 workerId = 31，自增 dataCenterId 并將 workerId 設(shè)置為 0

dataCenterId、workerId 是一直向下推進(jìn)的，總體形成一個環(huán)狀。通過 Lua 腳本的原子性，保證 1024 節(jié)點下的雪花算法生成不重復(fù)。如果標(biāo)識位等于 1024，則從頭開始繼續(xù)循環(huán)推進(jìn)

開源分布式 ID 框架

Leaf 和 Uid 都有實現(xiàn)雪花算法，Leaf 額外提供了號段模式生成 ID

美團(tuán) Leaf：https://github.com/Meituan-Dianping/Leaf

百度 Uid：https://github.com/baidu/uid-generator

雪花算法可以滿足大部分場景，如無必要，不建議引入開源方案增加系統(tǒng)復(fù)雜度

回顧總結(jié)

文章通過圖文并茂的方式幫助讀者梳理了一遍什么是雪花算法，以及如何解決雪花算法生成 ID 沖突的問題

關(guān)于雪環(huán)算法生成 ID 沖突問題，文中給了一種方案：分配標(biāo)示位；通過分配雪花算法的組成標(biāo)識位，來達(dá)到默認(rèn) 1024 節(jié)點下 ID 生成唯一

可以去看看  Hutool 或者 Mybatis-Plus 雪花算法的具體實現(xiàn)，幫助大家更好的理解

雪花算法不是萬能的，并不能適用于所有場景。如果 ID 要求全局唯一并且服務(wù)節(jié)點超出 1024 節(jié)點，可以選擇修改算法本身的組成，即擴(kuò)展標(biāo)識位，或者選擇開源方案：LEAF、UID

創(chuàng)作不易，文章看完有幫助，點關(guān)注支持一下，祝好