[[423697]]

分布式系統(tǒng)中，有一些需要使用全局唯一 ID 的場景，這種時(shí)候?yàn)榱朔乐?ID 沖突可以使用 36 位的 UUID，但是 UUID 有一些缺點(diǎn)，首先他相對(duì)比較長，另外 UUID 一般是無序的

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

什么是雪花算法

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

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

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

高性能高可用：生成時(shí)不依賴于數(shù)據(jù)庫，完全在內(nèi)存中生成

高吞吐：每秒鐘能生成數(shù)百萬的自增 ID

ID 自增：存入數(shù)據(jù)庫中，索引效率高

SnowFlake 算法的缺點(diǎn)：

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

雪花算法組成

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

包含四個(gè)組成部分

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

時(shí)間戳：41bit，毫秒級(jí)的時(shí)間戳(41 位的長度可以使用 69 年)

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

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

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

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

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

雪花算法適用場景

因?yàn)檠┗ㄋ惴ㄓ行蜃栽觯Ｕ狭?MySQL 中 B+ Tree 索引結(jié)構(gòu)插入高性能

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

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

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

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

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

服務(wù)通過集群的方式部署，其中部分機(jī)器標(biāo)識(shí)位一致

業(yè)務(wù)存在一定的并發(fā)量，沒有并發(fā)量無法觸發(fā)重復(fù)問題

生成 ID 的時(shí)機(jī)：同一毫秒下的序列號(hào)一致

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

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

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

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

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

Hutool v5.7.9 參照了 Mybatis-Plus dataCenterId 和 workerId 生成方案，提供了默認(rèn)實(shí)現(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 是一個(gè)固定值，代表數(shù)據(jù)中心 ID 最大值，默認(rèn)值 31

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

獲取 dataCenterId 時(shí)存在兩種情況，一種是網(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 也是一個(gè)固定值，代表工作機(jī)器 ID 最大值，默認(rèn)值 31;datacenterId 取自上述的 getDatacenterId 方法

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

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

分配標(biāo)識(shí)位

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

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

預(yù)分配

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

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

動(dòng)態(tài)分配

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

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

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

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

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

動(dòng)態(tài)分配實(shí)現(xiàn)方案

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

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

具體 Lua 腳本邏輯如下：

第一個(gè)服務(wù)節(jié)點(diǎn)在獲取時(shí)，Redis 可能是沒有 snowflake_work_id_key 這個(gè) Hash 的，應(yīng)該先判斷 Hash 是否存在，不存在初始化 Hash，dataCenterId、workerId 初始化為 0

如果 Hash 已存在，判斷 dataCenterId、workerId 是否等于最大值 31，滿足條件初始化 dataCenterId、workerId 設(shè)置為 0 返回

dataCenterId 和 workerId 的排列組合一共是 1024，在進(jìn)行分配時(shí)，先分配 workerId

判斷 workerId 是否 != 31，條件成立對(duì) workerId 自增，并返回;如果 workerId = 31，自增 dataCenterId 并將 workerId 設(shè)置為 0

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

開源分布式 ID 框架

Leaf 和 Uid 都有實(shí)現(xiàn)雪花算法，Leaf 額外提供了號(hào)段模式生成 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)識(shí)位，來達(dá)到默認(rèn) 1024 節(jié)點(diǎn)下 ID 生成唯一

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

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