源碼解析之 Seata 項目中的分佈式 ID 生成算法

內容摘要：

    一、知識點背景

    二、算法原理

    三、相關源碼解析

    四、實踐運用

一、背景

Saga 作爲阿里開源的長事務解決方案，涉及到全局事務 id 的生成和串聯，需要保證事務 id 的穩定性和全局唯一性。

二、原理

twitter 開源的 snowflake 算法。

saga 實現的全局唯一的 id 生成算法也是來源於 snowflake。作爲最流行的分佈式 id 生成算法之一，其實在無數的開源代碼中都有看到過他的身影。比如 Sharding-jdbc，在操作分庫分表時，也使用了該算法來生成分佈式 id。

由上圖可以看出，雪花算法是由 4 個部分組合而成的：符號位 + 41 位時間戳 + 10 位機器碼 + 12 位序列號。

這麼組合的好處是什麼呢？這就要從分佈式 ID 的具體使用要求來看了：

snowflake 用時間戳 + 機器碼保證不同機器之間的 ID 互不相同；用時間戳 + 序列號的方式保證同一機器上的 ID 唯一。

我們從它的組合方式也能看出來, 該算法對唯一性的保障是強依賴機器時鐘的，一旦時鐘回撥，功能將異常。

snowflake 本身更強調的是無三方依賴，完全本地自主完成。當然，除了無依賴的策略之外，還有半依賴和純依賴的方式。一些業務場景 需要保證遞增 （至少是趨勢遞增），來做業務上的排序等判斷處理。這個就需要使用額外的一些組件來配合使用了，如 mysql 批量發號緩存策略。我們在最後一部分運用裏再說。

三、源碼解析

首先，需要定義 ID 組合方式所需的常量，如每段佔用位數等

/* 開始時間 (2020-05-03) */
private final long twepoch = 1607529600000L;
/* 機器碼所佔的bit位數 = 10位 */
private final long workerIdBits = 10L;
/* 最大支持的機器碼 = 1023，該式子相當與~(-1L << 10L) */ 
private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
/* 序列號所佔的bit位數 */
private final long sequenceBits = 12L;
/* 機器碼需要在序列號的左邊 */
private final long workerIdShift = sequenceBits;
/* 時間戳的起始位置在序列號和機器碼的左邊 */
private final long timestampLeftShift = sequenceBits + workerIdBits;
/* 序列號的最大支持數值 */
private final long sequenceMask = -1L ^ (-1L << sequenceBits);

然後，定義三個位段的含義字段

/* 機器碼 (0 ~ 1023) */
private long workerId;
/* 序列號 (0 ~ 4095) */
private long sequence = 0L;
/* 最後時間戳 */
private long lastTimestamp = -1L;

接下來，就是生產分佈式 ID 的核心

InetAddress address;
try {
    //獲取本機IP
    address = InetAddress.getLocalHost();
} catch (final UnknownHostException e) {
    throw new IllegalStateException("Cannot get LocalHost InetAddress, please check your network!",e);
}
byte[] ipAddressByteArray = address.getAddress();
//機器碼一共需要10位，所以取段倒數第二個段取最後2位 + 倒數第一段全部8位
return ((ipAddressByteArray[ipAddressByteArray.length - 2] & 0B11) << Byte.SIZE) + (ipAddressByteArray[ipAddressByteArray.length - 1] & 0xFF);
//當前時間戳
long timestamp = System.currentTimeMillis()
//如果當前時間戳 < 最後記錄時間戳 ，則可能發生時鐘回撥，異常中斷
if (timestamp < lastTimestamp) {
    throw new RuntimeException(String.format(
        "clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
}
//如果當前時間戳 == 最後記錄時間戳 
if (lastTimestamp == timestamp) {
    //計算下一個序列號,這裏&4095的作用是循環，因爲到4096會變成0
    sequence = (sequence + 1) & sequenceMask;
    //如果下一個序列號==0，則說明同一時間戳內序列號以用完，設置下一時間戳爲最後時間戳
    if (sequence == 0) {
        //該方法內部while循環直到當前時間>最後時間   
        timestamp = tilNextMillis(lastTimestamp);
    }
} else {
    sequence = 0L;
}
lastTimestamp = timestamp;
//時間戳和指定時間的差 左移 12+10 | 機器碼 左移12  | 序列號 
return ((timestamp - twepoch) << timestampLeftShift) | (workerId << workerIdShift) | sequence;

四、運用

因爲 saga 這裏生成的分佈式 ID 只是來保證用來串聯分佈式事務的 ID 的唯一性。所以，使用無依賴的策略就完全夠用。如果業務中有此類串聯業務的訴求，可以直接使用該方法。

然鵝 ，很大一部分業務場景，是需要分佈式 ID 符合特定業務要求的，比如增量消息，排序消息，涉及 B-tree 索引進行存儲時 ID 遞增保證效率等等。

美團的 Leaf-snowflake 方案，採用了半依賴的方式，採用依賴 zk 發號的方式實現：

(來源：https://tech.meituan.com/2017/04/21/mt-leaf.html)

阿里內部使用訂單號，因爲涉及到 LDC 邏輯單元部署，涉及到大促時的彈性部署，涉及到數據版本、業務標示等等要求，其實現方案要更嚴格一些，但原理，也是對 snowflake 進行了擴展，將原來的三個組成部分擴展成了多個組成部分，比如用固定位置固定長度的 bit 位來標示 LDC 路由值，用另外 N 位標示彈性，最後用 N 位來支持併發。因此，基本是全依賴的策略。

萬變不離其中，只要瞭解了內部實現邏輯，就可以結合自身業務做出適合的改造和優化。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/abMFfWYooSuet6v100iJdA

猜你喜歡