C- 開源一個新的雪花算法

用一種全新的雪花漂移算法,讓 ID 更短、生成速度更快。核心在於縮短 ID 長度的同時,還能擁有極高瞬時併發處理量(50W/0.1s),及強大的配置能力。

需求來源

1、作爲架構設計的你,想要解決數據庫主鍵唯一的問題,特別是在分佈式系統多數據庫的時候。

2、你希望這個主鍵是用最少的存儲空間,索引速度更快,Select、Insert 和 Update 更迅速。

3、你要考慮在分庫分表(合庫合表)的時候,主鍵值可直接使用,並能反映業務時序。

4、如果這樣的主鍵值太長,超過前端 JS Number 類型最大值,須把 Long 型轉換爲 String 型,你會覺得有點沮喪。

5、哪怕 Guid 能自增,但佔用空間大,這也不是你想要的。

6、你希望系統能運行 100 年以上。

傳統算法問題

  1. 生成的 ID 太長。

  2. 瞬時併發量不夠。

  3. 不能解決時間回撥問題。

  4. 不支持後補生成前序 ID。

  5. 依賴外部存儲系統。

新算法特點

  1. 整形數字,隨時間單調遞增(不一定連續),長度更短,用 50 年都不會超過 js Number 類型最大值。(默認配置 WorkerId 是 6bit,自增數是 6bit)

  2. 速度更快,是傳統雪花算法的 2-5 倍,0.1 秒可生成 50 萬個。(i7 筆記本,默認算法配置 6bit+6bit)

  3. 支持時間回撥處理。比如服務器時間回撥 1 秒,本算法能自動適應生成臨界時間的唯一 ID。

  4. 支持手工插入新 ID。當業務需要在歷史時間生成新 ID 時,用本算法的預留位能生成 5000 個每秒。

  5. 漂移時能外發通知事件。讓調用方確切知道算法漂移記錄,Log 併發調用量。

  6. 不依賴任何外部緩存和數據庫。(但 WorkerId 必須由外部指定)

性能數據

(參數:10 位自增序列,1000 次漂移最大值)

效果

1.js Number 類型最大數值:9007199254740992,本算法在保持併發性能(5W+/0.01s)和最大 64 個 WorkerId(6bit)的同時,能用 70 年纔到 js Number Max 值。

  1. 增加 WorkerId 位數到 8bit(256 節點)時,15 年達到 js Number Max 值。

  2. 極致性能:500W/1s。

  3. 所有測試數據均基於 8 代低壓 i7 計算。

“我” 是什麼

  1. 本算法是一個類庫,它基於 net standard2.0 基礎庫,不依賴任何第三方組件。

  2. 本算法不依賴任何外部數據系統(除了要被指定 WorkerId 之外)。

適用範圍

  1. 小型、中型、大型需要全局唯一 Id(不用 Guid)的項目。

  2. 分佈式項目。

  3. 不想將 Long 型轉 String 給前端用的項目。(若前端支持 bigint,則可不轉類型)

如何處理時間回撥

  1. 當發生系統時間回撥時,算法採用過去時序的預留序數生成新的 ID。

  2. 默認每秒生成 100 個(速度可調整)。

  3. 回撥生成的 ID 序號,默認靠前,也可以調整爲靠後。

  4. 允許時間回撥至本算法預設基數(參數可調)。

能用多久

  1. 在默認配置下,ID 可用 71000 年不重複。

  2. 在支持 1024 個工作節點時,ID 可用 4480 年不重複。

  3. 在支持 4096 個工作節點時,ID 可用 1120 年不重複。

  4. 以上所有工作節點,均擁有 50W/0.1s 瞬時處理速度。

★★集成建議★★

常規集成

  1. 用單例模式調用。外部集成方使用更多的實例並行調用本算法,不會增加 ID 產出效能,因爲本算法採用單線程模式生成 ID。

  2. 指定唯一的 WorkerId。必須由外部系統確保 WorkerId 的全局唯一性,並賦值給本算法入口方法。

  3. 異常處理。本算法內部會拋出所有 Exception,外部系統應該 catch 相關信息並做好應對處理,以免引發更大的系統崩潰。

  4. 認真理解 IdGeneratorOptions 的定義,這對集成和使用本算法有幫助。

  5. 訂閱 ID 異步通知。IIdGenerator.GenIdActionAsync 是一個可以向外部系統異步發送 ID 生成消息的事件,它包含的消息類型有 "漂移開始、漂移結束、時間回撥",具體參考 Yitter.IdGenTest 的 Program.cs 啓動代碼。不過訂閱 ID 異步通知會有細微的性能損失。

  6. 異步或同步調用。你可在外部系統的異步(async 標記)方法中調用本算法,同步調用同樣沒問題。

  7. 使用雪花漂移算法。雖然代碼裏包含了傳統雪花算法的定義,並且你可以在入口處指定(Method=2)來啓用傳統算法,但仍建議你使用雪花漂移算法(Method=1,默認的),畢竟它具有更好的伸縮力和更高的性能。

  8. 輕易不要修改核心算法。本算法內部參數較多,邏輯較爲複雜,在你尚未掌握核心邏輯時,請勿嘗試修改核心代碼且用於生產環境,除非通過大量細緻、科學的測試驗證。

大型分佈式集成

  1. 可擴大 WorkerIdBitLength 到最大 20,支持 1,048,576 個節點,且不影響上述併發性能(50W/0.1s)。[算法支持]

  2. 採用中心化 IdGenerator 集羣,生成可用 Id 列表,存入 Redis 隊列供節點消費。此時 64 箇中心化節點數足夠大型互聯網項目使用。[需集成方擴展實現]

  3. 以上 2 條二選一即可,採用方法 2 一般是因爲不想增加最終 ID 長度,但節點數超過 64 個。

  4. 任何加大 WorkerIdBitLength 或 SeqBitLength 的設置,都可能會增加 ID 的長度。

配置變更

配置變更指是系統運行一段時間後,再變更運行參數(IdGeneratorOptions 選項值),請注意:

  1. 最重要的一條原則是:StartTime 只能往前(比老值更小、距離現在更遠)賦值,原因是往後賦值極大可能產生相同的時間戳。[不推薦在系統運行之後調整 StartTime]

  2. 任何時候增加 WorkerIdBitLength 或 SeqBitLength,都是可以的,但是慎用 “減小” 的操作,因爲這可能導致在未來某天生成的 ID 與過去老配置時相同。[允許在系統運行之後增加任何一個 BitLength 值]

  3. 如果必須減小 WorkerIdBitLength 或 SeqBitLength 其中的一項,一定要滿足一個條件:新的兩個 BitLength 之和要大於 老的值之和。[不推薦在運行之後縮小任何一個 BitLength 值]

  4. 上述 3 條規則,並未在本算法內做邏輯控制,集成方應根據上述規則做好影響評估,確認無誤後,再實施配置變更。

關於默認配置

  1. 默認配置能很好應對常規併發不超過 1w 次 / 1s,突發請求不超過 10W 次 / 1s 的場景。

  2. 若要突發請求值滿足 50W 次 / 1s,可增加 SeqBitLength 至 8 或 9。

代碼示例

運行環境

1、.NET Standard 2.0+

引用 nuget 包

1<PackageReference Include="Yitter.IdGenerator" Version="1.0.2" />
2
3

調用示例

1// 全局初始化設置WorkerId,默認最大2^16-1。(初始化過程全局只需一次,且必須最先設置)
2var options = new IdGeneratorOptions(){ WorkerId = 1};
3IdHelper.SetIdGenerator(options);
4
5// 初始化以後,就可以在需要的地方調用方法生成ID。
6var newId = IdHelper.NextId();
7
8

如果基於 DI 框架集成,可以參考 IdHelper 去管理 IdGenerator 對象,必須使用單例模式。

options 說明

 1public class IdGeneratorOptions
 2{
 3    /// <summary>
 4    /// 雪花計算方法
 5    /// (1|2)
 6    /// </summary>
 7    public short Method { get; set; } = 1;
 8
 9    /// <summary>
10    /// 開始時間(UTC格式)
11    /// 不能超過當前系統時間
12    /// </summary>
13    public DateTime StartTime { get; set; } = DateTime.MinValue;
14
15    /// <summary>
16    /// 機器碼
17    /// 與 WorkerIdBitLength 有關係
18    /// </summary>
19    public ushort WorkerId { get; set; } = 0;
20
21    /// <summary>
22    /// 機器碼位長
23    /// 範圍:2-21(要求:序列數位長+機器碼位長不超過22)。
24    /// 建議範圍:6-12。
25    /// </summary>
26    public byte WorkerIdBitLength { get; set; } = 6;
27
28    /// <summary>
29    /// 序列數位長
30    /// 範圍:2-21(要求:序列數位長+機器碼位長不超過22)。
31    /// 建議範圍:6-14。
32    /// </summary>
33    public byte SeqBitLength { get; set; } = 6;
34
35    /// <summary>
36    /// 最大序列數(含)
37    /// (由SeqBitLength計算的最大值)
38    /// </summary>
39    public int MaxSeqNumber { get; set; } = 0;
40
41    /// <summary>
42    /// 最小序列數(含)
43    /// 默認11,不小於5,不大於MaxSeqNumber-2
44    /// </summary>
45    public ushort MinSeqNumber { get; set; } = 11;
46
47    /// <summary>
48    /// 最大漂移次數(含),
49    /// 默認2000,推薦範圍500-10000(與計算能力有關)
50    /// </summary>
51    public int TopOverCostCount { get; set; } = 2000;
52
53

生成的 ID

默認配置:

1WorkerId = 6 (最多64個工作節點)
2SeqBitLength = 6
3
4

ID 示例(基於默認配置):

1129053495681099        (本算法運行1年)
2387750301904971        (運行3年)
3646093214093387        (運行5年)
41292658282840139       (運行10年)
59007199254740992       (js Number 最大值)
6165399880288699493     (普通雪花算法生成的ID)
7
8

本算法生成的 ID 值,是 js Number 最大值的 1%-10%,是普通雪花算法值的千分之一,而計算能力卻超過普通雪花算法。

技術支持

**開源地址:**https://gitee.com/yitter/idgenerator

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