今天來分享下最近研究的分布式 ID 生成系統 —— Leaf ，一起來思考下這個分布式ID的設計吧
什麼是分布式ID？
ID 最大的特點是 唯一
而分布式 ID，就是指分布式系統下的 ID，它是 全局唯一 的。
為啥需要分布式ID呢？
這就和 唯一 息息相關了。
比如我們用 MySQL 存儲資料，一開始資料量不大，但是業務經過一段時間的發展，單表資料每日劇增，最終突破 1000w，2000w …… 系統開始變慢了，此時我們已經嘗試了優化索引， 讀寫分離 ，更新硬體，更新網絡 等操作，但是 單表瓶頸 還是來了，我們隻能去 分庫分表 了。
而問題也随着而來了，分庫分表後，如果還用 資料庫自增ID 的方式的話，那麼在使用者表中，就會出現 兩個不同的使用者有相同的ID 的情況，這個是不能接受的。
而 分布式ID全局唯一 的特點，正是我們所需要的。
分布式ID的生成方式
- UUID
- 資料庫自增ID （MySQL，Redis）
- 雪花算法
基本就上面幾種了，UUID 的最大缺點就是太長，36個字元長度，而且無序，不适合。
而其他兩種的缺點還有辦法補救，可能這也是 Leaf 提供這兩種生成 ID 方式的原因。
項目簡介
Leaf ，分布式 ID 生成系統，有兩種生成 ID 的方式：
- 号段模式
- Snowflake模式
号段模式
在 資料庫自增ID 的基礎上進行優化
- 增加一個 segement ，減少通路資料庫的次數。
- 雙 Buffer 優化，提前緩存下一個 Segement，降低網絡請求的耗時（降低系統的TP999名額）
來自美團技術團隊
biz_tag用來區分業務，max_id表示該biz_tag目前所被配置設定的ID号段的最大值，step表示每次配置設定的号段長度
沒優化前，每次都從 db 擷取，現在擷取的頻率和 step 字段相關。
雙 Buffer 優化思路
号段模式源碼解讀
SegmentService 構造方法
作用
- 配置 dataSource
- 設定 MyBatis
- 執行個體化 SegmentIDGenImpl
- 執行 init 方法
這段代碼我也忘了 哈哈，已經多久沒直接用 mybatis 了，還是重新去官網翻看的。
mybatis 官網例子
執行個體化 SegmentIDGenImpl 時，其中有兩個變量要留意下
- SEGMENT_DURATION，智能調節 step 的關鍵
- cache ，其中 SegmentBuffer 是雙 Buffer 的關鍵設計。
這裡先不展開，看看 init 方法先。
SegmentIDGenImpl init 方法
作用
- 執行 updateCacheFromDb 方法
- 開背景線程，每分鐘執行一次 updateCacheFromDb() 方法
顯然，核心在 updateCacheFromDb
updateCacheFromDb 方法
這裡就直接看源碼和我加的注釋
private void updateCacheFromDb() {
logger.info("update cache from db");
StopWatch sw = new Slf4JStopWatch();
try {
// 執行 SELECT biz_tag FROM leaf_alloc 語句，擷取所有的 業務字段。
List<String> dbTags = dao.getAllTags();
if (dbTags == null || dbTags.isEmpty()) {
return;
}
// 緩存中的 biz_tag
List<String> cacheTags = new ArrayList<String>(cache.keySet());
// 要插入的 db 中的 biz_tag
Set<String> insertTagsSet = new HashSet<>(dbTags);
// 要移除的緩存中的 biz_tag
Set<String> removeTagsSet = new HashSet<>(cacheTags);
// 緩存中有的話，不用再插入，從 insertTagsSet 中移除
for (int i = 0; i < cacheTags.size(); i++) {
String tmp = cacheTags.get(i);
if (insertTagsSet.contains(tmp)) {
insertTagsSet.remove(tmp);
}
}
// 為新增的 biz_tag 建立緩存 SegmentBuffer
for (String tag : insertTagsSet) {
SegmentBuffer buffer = new SegmentBuffer();
buffer.setKey(tag);
Segment segment = buffer.getCurrent();
segment.setValue(new AtomicLong(0));
segment.setMax(0);
segment.setStep(0);
cache.put(tag, buffer);
logger.info("Add tag {} from db to IdCache, SegmentBuffer {}", tag, buffer);
}
// db中存在的，從要移除的 removeTagsSet 移除。
for (int i = 0; i < dbTags.size(); i++) {
String tmp = dbTags.get(i);
if (removeTagsSet.contains(tmp)) {
removeTagsSet.remove(tmp);
}
}
// 從 cache 中移除不存在的 bit_tag。
for (String tag : removeTagsSet) {
cache.remove(tag);
logger.info("Remove tag {} from IdCache", tag);
}
} catch (Exception e) {
logger.warn("update cache from db exception", e);
} finally {
sw.stop("updateCacheFromDb");
}
}
執行完後，會出現這樣的 log
Add tag leaf-segment-test from db to IdCache, SegmentBuffer SegmentBuffer{key='leaf-segment-test', segments=[Segment(value:0,max:0,step:0), Segment(value:0,max:0,step:0)], currentPos=0, nextReady=false, initOk=false, threadRunning=false, step=0, minStep=0, updateTimestamp=0}
最後 init 方法結束後，會将 initOk 設定為 true。
項目啟動完畢後，我們就可以調用這個 API 了。
如圖，通路 LeafController 中的 Segment API，可以擷取到一個 id。
SegmentIDGenImpl get 方法
可以看到，init 不成功會報錯。
以及會直接從 cache 中查找這個 key(biz_tag) , 沒有的話會報錯。
拿到這個 SegmentBuffer 時，還得看看它 init 了 沒有，沒有的話用雙檢查鎖的方式去更新
先來看下一眼 SegmentBuffer 的結構
SegmentBuffer 類
⭐updateSegmentFromDb 方法
這裡就是更新緩存的方法了，主要是更新 Segment 的 value ， max，step 字段。
可以看到有三個 if 分支，下面展開說
分支一：初始化
第一次，buffer 還沒 init，如上圖，執行完後會更新 SegmentBuffer 的 step 和 minStep 字段。
分支二：第二次更新
這裡主要是更新這個 updateTimestamp ，它的作用看分支三
分支三：剩下的更新
這裡就比較有意思了，就是說如果這個号段在 15分鐘 内用完了，那麼它會擴大這個 step （不超過 10w），建立一個更大的 MaxId ，降低通路 DB 的頻率。
那麼，到這裡，我們完成了 updateSegmentFromDb 方法，更新了 Segment 的 value ， max，step 字段。
但是，我們不是每次 get 都走上面的流程，它還得走這個緩存方法
⭐getIdFromSegmentBuffer 方法
顯然，這是另一個重點。
如圖，在死循環中，先擷取讀鎖，拿到目前的号段 Segment，進行判斷
- 使用超過 10% 就開新線程去更新下一個号段
- 沒超過則将 value （AtomicLong 類型）+1 ，小于 maxId 則直接傳回。
這裡要重點留意 讀寫鎖的使用 ，比如 開新線程時，使用了這個 寫鎖 ，裡面的 nextReady 等變量使用了 volatile 修飾
這裡的核心就是切換 Segment。
至此，号段模式結束。
優缺點
資訊安全：如果ID是連續的，惡意使用者的扒取工作就非常容易做了，直接按照順序下載下傳指定URL即可；如果是訂單号就更危險了，競對可以直接知道我們一天的單量。是以在一些應用場景下，會需要ID無規則、不規則。—— 《Leaf——美團點評分布式ID生成系統》
美團
可以看到，這個号段模式的最大弊端就是 資訊不安全，是以在使用時得三思，能不能用到這些業務中去。
Snowflake模式
雪花算法，核心就是将 64bit 分段，用來表示時間，機器，序列号等。
41-bit的時間可以表示（1L<<41）/(1000L360024*365)=69年的時間，10-bit機器可以分别表示1024台機器。
12個自增序列号可以表示2^12個ID，理論上snowflake方案的QPS約為 2^12 * 1000 = 409.6w/s
這裡使用 Zookeeper 持久順序節點的特性自動對 snowflake 節點配置 wokerID，不用手動配置。
時鐘回撥問題
img
Snowflake模式源碼解讀
這部分源碼就不一一展開了，直接展示核心代碼
SnowflakeZookeeperHolder init 方法
這裡要注意調整這個 connectionTimeoutMs 和 sessionTimeoutMs ，不然兩種模式都啟動的話，這個 zk 的 session 可能會逾時，造成啟動失敗。
圖中流程
- 看看 zk 節點存不存在，不存在就建立
- 同時将 worker id 儲存到本地。
- 建立定時任務，更新 znode。
znode
worker Id
定時任務
SnowflakeIDGenImpl get 方法
這裡直接看代碼和注釋了
@Override
public synchronized Result get(String key) {
long timestamp = timeGen();
// 發生了回撥，此刻時間小于上次發号時間
if (timestamp < lastTimestamp) {
long offset = lastTimestamp - timestamp;
if (offset <= 5) {
try {
//時間偏差大小小于5ms，則等待兩倍時間
wait(offset << 1);
timestamp = timeGen();
//還是小于，抛異常并上報
if (timestamp < lastTimestamp) {
return new Result(-1, Status.EXCEPTION);
}
} catch (InterruptedException e) {
LOGGER.error("wait interrupted");
return new Result(-2, Status.EXCEPTION);
}
} else {
return new Result(-3, Status.EXCEPTION);
}
}
if (lastTimestamp == timestamp) {
// sequenceMask = ~(-1L << 12 ) = 4095 二進制即 12 個1
sequence = (sequence + 1) & sequenceMask;
if (sequence == 0) {
//seq 為0的時候表示是下一毫秒時間開始對seq做随機
sequence = RANDOM.nextInt(100);
timestamp = tilNextMillis(lastTimestamp);
}
} else {
//如果是新的ms開始
sequence = RANDOM.nextInt(100);
}
lastTimestamp = timestamp;
// timestampLeftShift = 22， workerIdShift = 12
long id = ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;
return new Result(id, Status.SUCCESS);
}
protected long tilNextMillis(long lastTimestamp) {
long timestamp = timeGen();
while (timestamp <= lastTimestamp) {
timestamp = timeGen();
}
return timestamp;
}
protected long timeGen() {
return System.currentTimeMillis();
}
API 效果
生成 ID
反解 ID
至此，這個 Snowflake 模式也了解完畢了。
總結
看完上面兩種模式，我覺得兩種模式都有它适用的場景，号段模式更适合對内使用（比如 使用者ID），而如果你這個 ID 會被使用者看到，暴露出去有其他風險（比如爬蟲惡意爬取等），那就得多斟酌了，。而訂單号 就更适合用 snowflake 模式。
分布式ID 的特點
- 全局唯一
- 趨勢遞增（有序一直很重要，粗略有序還是嚴格有序就看情況了）
- 可反解（可選）
- 資訊安全（可選）
參考資料
- Github 位址：https://github.com/Meituan-Dianping/Leaf/blob/master/README_CN.md
來源：https://mp.weixin.qq.com/s/BvLW3LTrTfW4-s3zPPRi6A