雪花算法，什么情況下發(fā)生 ID 沖突？
分布式系統(tǒng)中，有一些需要使用全局唯一 ID 的場景，這種時候為了防止 ID 沖突可以使用 36 位的 UUID，但是 UUID 有一些缺點，首先他相對比較長，另外 UUID 一般是無序的
有些時候我們希望能使用一種簡單些的 ID，并且希望 ID 能夠按照時間有序生成
什么是雪花算法
Snowflake 中文的意思是雪花，所以常被稱為雪花算法，是 Twitter 開源的分布式 ID 生成算法
Twitter 雪花算法生成后是一個 64bit 的 long 型的數(shù)值，組成部分引入了時間戳，基本保持了自增
SnowFlake 算法的優(yōu)點：
高性能高可用：生成時不依賴于數(shù)據(jù)庫，完全在內(nèi)存中生成
高吞吐：每秒鐘能生成數(shù)百萬的自增 ID
ID 自增：存入數(shù)據(jù)庫中，索引效率高
SnowFlake 算法的缺點：
依賴與系統(tǒng)時間的一致性，如果系統(tǒng)時間被回調(diào)，或者改變，可能會造成 ID 沖突或者重復
雪花算法組成
snowflake 結(jié)構(gòu)如下圖所示：
包含四個組成部分
不使用：1bit，最高位是符號位，0 表示正，1 表示負，固定為 0
時間戳：41bit，毫秒級的時間戳(41 位的長度可以使用 69 年)
標識位：5bit 數(shù)據(jù)中心 ID，5bit 工作機器 ID，兩個標識位組合起來最多可以支持部署 1024 個節(jié)點
序列號：12bit 遞增序列號，表示節(jié)點毫秒內(nèi)生成重復，通過序列號表示唯一，12bit 每毫秒可產(chǎn)生 4096 個 ID
通過序列號 1 毫秒可以產(chǎn)生 4096 個不重復 ID，則 1 秒可以生成 4096 * 1000 = 409w ID
默認的雪花算法是 64 bit，具體的長度可以自行配置。如果希望運行更久，增加時間戳的位數(shù);如果需要支持更多節(jié)點部署，增加標識位長度;如果并發(fā)很高，增加序列號位數(shù)
總結(jié)：雪花算法并不是一成不變的，可以根據(jù)系統(tǒng)內(nèi)具體場景進行定制
雪花算法適用場景
因為雪花算法有序自增，保障了 MySQL 中 B+ Tree 索引結(jié)構(gòu)插入高性能
所以，日常業(yè)務(wù)使用中，雪花算法更多是被應用在數(shù)據(jù)庫的主鍵 ID 和業(yè)務(wù)關(guān)聯(lián)主鍵
雪花算法生成 ID 重復問題
假設(shè)：一個訂單微服務(wù)，通過雪花算法生成 ID，共部署三個節(jié)點，標識位一致
此時有 200 并發(fā)，均勻散布三個節(jié)點，三個節(jié)點同一毫秒同一序列號下生成 ID，那么就會產(chǎn)生重復 ID
通過上述假設(shè)場景，可以知道雪花算法生成 ID 沖突存在一定的前提條件
服務(wù)通過集群的方式部署，其中部分機器標識位一致
業(yè)務(wù)存在一定的并發(fā)量，沒有并發(fā)量無法觸發(fā)重復問題
生成 ID 的時機：同一毫秒下的序列號一致
標識位如何定義
如果能保證標識位不重復，那么雪花 ID 也不會重復
通過上面的案例，知道了 ID 重復的必要條件。如果要避免服務(wù)內(nèi)產(chǎn)生重復的 ID，那么就需要從標識位上動文章
我們先看看開源框架中使用雪花算法，如何定義標識位
Mybatis-Plus v3.4.2 雪花算法實現(xiàn)類 Sequence，提供了兩種構(gòu)造方法：無參構(gòu)造，自動生成 dataCenterId 和 workerId;有參構(gòu)造，創(chuàng)建 Sequence 時明確指定標識位
Hutool v5.7.9 參照了 Mybatis-Plus dataCenterId 和 workerId 生成方案，提供了默認實現(xiàn)
一起看下 Sequence 的創(chuàng)建默認無參構(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 最大值，默認值 31
為什么最大值要是 31?因為 5bit 的二進制最大是 11111，剛好是 31
獲取 dataCenterId 時存在兩種情況，一種是網(wǎng)絡(luò)接口為空，默認取 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 也是一個固定值，代表工作機器 ID 最大值，默認值 31;datacenterId 取自上述的 getDatacenterId 方法
name 變量值為 PID@IP，所以 name 需要根據(jù) @ 分割并獲取下標 0，得到 PID
通過 MAC + PID 的 hashcode 獲取16個低位，進行運算，最終得到 workerId
分配標識位
Mybatis-Plus 標識位的獲取依賴 Mac 地址和進程 PID，雖然能做到盡量不重復，但仍有小幾率
標識位如何定義才能不重復?有兩種方案：預分配和動態(tài)分配
預分配
應用上線前，統(tǒng)計當前服務(wù)的節(jié)點數(shù)，人工去申請標識位
這種方案，沒有代碼開發(fā)量，在服務(wù)節(jié)點固定或者項目少可以使用，但是解決不了服務(wù)節(jié)點動態(tài)擴容性問題
動態(tài)分配
通過將標識位存放在 Redis、Zookeeper、MySQL 等中間件，在服務(wù)啟動的時候去請求標識位，請求后標識位更新為下一個可用的
通過存放標識位，延伸出一個問題：雪花算法的 ID 是 服務(wù)內(nèi)唯一還是全局唯一
以 Redis 舉例，如果要做服務(wù)內(nèi)唯一，存放標識位的 Redis 節(jié)點使用自己項目內(nèi)的就可以;如果是全局唯一，所有使用雪花算法的應用，要用同一個 Redis 節(jié)點
兩者的區(qū)別僅是 不同的服務(wù)間是否公用 Redis。如果沒有全局唯一的需求，最好使 ID 服務(wù)內(nèi)唯一，因為這樣可以避免單點問題
服務(wù)的節(jié)點數(shù)超過 1024，則需要做額外的擴展;可以擴展 10 bit 標識位，或者選擇開源分布式 ID 框架
動態(tài)分配實現(xiàn)方案
Redis 存儲一個 Hash 結(jié)構(gòu) Key，包含兩個鍵值對：dataCenterId 和 workerId
在應用啟動時，通過 Lua 腳本去 Redis 獲取標識位。dataCenterId 和 workerId 的獲取與自增在 Lua 腳本中完成，調(diào)用返回后就是可用的標示位
具體 Lua 腳本邏輯如下：
第一個服務(wù)節(jié)點在獲取時，Redis 可能是沒有 snowflake_work_id_key 這個 Hash 的，應該先判斷 Hash 是否存在，不存在初始化 Hash，dataCenterId、workerId 初始化為 0
如果 Hash 已存在，判斷 dataCenterId、workerId 是否等于最大值 31，滿足條件初始化 dataCenterId、workerId 設(shè)置為 0 返回
dataCenterId 和 workerId 的排列組合一共是 1024，在進行分配時，先分配 workerId
判斷 workerId 是否 != 31，條件成立對 workerId 自增，并返回;如果 workerId = 31，自增 dataCenterId 并將 workerId 設(shè)置為 0
dataCenterId、workerId 是一直向下推進的，總體形成一個環(huán)狀。通過 Lua 腳本的原子性，保證 1024 節(jié)點下的雪花算法生成不重復。如果標識位等于 1024，則從頭開始繼續(xù)循環(huán)推進
開源分布式 ID 框架
Leaf 和 Uid 都有實現(xiàn)雪花算法，Leaf 額外提供了號段模式生成 ID
美團 Leaf：https://github.com/Meituan-Dianping/Leaf
百度 Uid：https://github.com/baidu/uid-generator
雪花算法可以滿足大部分場景，如無必要，不建議引入開源方案增加系統(tǒng)復雜度
回顧總結(jié)
文章通過圖文并茂的方式幫助讀者梳理了一遍什么是雪花算法，以及如何解決雪花算法生成 ID 沖突的問題
關(guān)于雪環(huán)算法生成 ID 沖突問題，文中給了一種方案：分配標示位;通過分配雪花算法的組成標識位，來達到默認 1024 節(jié)點下 ID 生成唯一
可以去看看 Hutool 或者 Mybatis-Plus 雪花算法的具體實現(xiàn)，幫助大家更好的理解
雪花算法不是萬能的，并不能適用于所有場景。如果 ID 要求全局唯一并且服務(wù)節(jié)點超出 1024 節(jié)點，可以選擇修改算法本身的組成，即擴展標識位，或者選擇開源方案：LEAF、UID
