C- 開源一個新的雪花算法
用一種全新的雪花漂移算法,讓 ID 更短、生成速度更快。核心在於縮短 ID 長度的同時,還能擁有極高瞬時併發處理量(50W/0.1s),及強大的配置能力。
需求來源
1、作爲架構設計的你,想要解決數據庫主鍵唯一的問題,特別是在分佈式系統多數據庫的時候。
2、你希望這個主鍵是用最少的存儲空間,索引速度更快,Select、Insert 和 Update 更迅速。
3、你要考慮在分庫分表(合庫合表)的時候,主鍵值可直接使用,並能反映業務時序。
4、如果這樣的主鍵值太長,超過前端 JS Number 類型最大值,須把 Long 型轉換爲 String 型,你會覺得有點沮喪。
5、哪怕 Guid 能自增,但佔用空間大,這也不是你想要的。
6、你希望系統能運行 100 年以上。
傳統算法問題
-
生成的 ID 太長。
-
瞬時併發量不夠。
-
不能解決時間回撥問題。
-
不支持後補生成前序 ID。
-
依賴外部存儲系統。
新算法特點
-
整形數字,隨時間單調遞增(不一定連續),長度更短,用 50 年都不會超過 js Number 類型最大值。(默認配置 WorkerId 是 6bit,自增數是 6bit)
-
速度更快,是傳統雪花算法的 2-5 倍,0.1 秒可生成 50 萬個。(i7 筆記本,默認算法配置 6bit+6bit)
-
支持時間回撥處理。比如服務器時間回撥 1 秒,本算法能自動適應生成臨界時間的唯一 ID。
-
支持手工插入新 ID。當業務需要在歷史時間生成新 ID 時,用本算法的預留位能生成 5000 個每秒。
-
漂移時能外發通知事件。讓調用方確切知道算法漂移記錄,Log 併發調用量。
-
不依賴任何外部緩存和數據庫。(但 WorkerId 必須由外部指定)
性能數據
(參數:10 位自增序列,1000 次漂移最大值)
效果
1.js Number 類型最大數值:9007199254740992,本算法在保持併發性能(5W+/0.01s)和最大 64 個 WorkerId(6bit)的同時,能用 70 年纔到 js Number Max 值。
-
增加 WorkerId 位數到 8bit(256 節點)時,15 年達到 js Number Max 值。
-
極致性能:500W/1s。
-
所有測試數據均基於 8 代低壓 i7 計算。
“我” 是什麼
-
本算法是一個類庫,它基於 net standard2.0 基礎庫,不依賴任何第三方組件。
-
本算法不依賴任何外部數據系統(除了要被指定 WorkerId 之外)。
適用範圍
-
小型、中型、大型需要全局唯一 Id(不用 Guid)的項目。
-
分佈式項目。
-
不想將 Long 型轉 String 給前端用的項目。(若前端支持 bigint,則可不轉類型)
如何處理時間回撥
-
當發生系統時間回撥時,算法採用過去時序的預留序數生成新的 ID。
-
默認每秒生成 100 個(速度可調整)。
-
回撥生成的 ID 序號,默認靠前,也可以調整爲靠後。
-
允許時間回撥至本算法預設基數(參數可調)。
能用多久
-
在默認配置下,ID 可用 71000 年不重複。
-
在支持 1024 個工作節點時,ID 可用 4480 年不重複。
-
在支持 4096 個工作節點時,ID 可用 1120 年不重複。
-
以上所有工作節點,均擁有 50W/0.1s 瞬時處理速度。
★★集成建議★★
常規集成
-
用單例模式調用。外部集成方使用更多的實例並行調用本算法,不會增加 ID 產出效能,因爲本算法採用單線程模式生成 ID。
-
指定唯一的 WorkerId。必須由外部系統確保 WorkerId 的全局唯一性,並賦值給本算法入口方法。
-
異常處理。本算法內部會拋出所有 Exception,外部系統應該 catch 相關信息並做好應對處理,以免引發更大的系統崩潰。
-
認真理解 IdGeneratorOptions 的定義,這對集成和使用本算法有幫助。
-
訂閱 ID 異步通知。IIdGenerator.GenIdActionAsync 是一個可以向外部系統異步發送 ID 生成消息的事件,它包含的消息類型有 "漂移開始、漂移結束、時間回撥",具體參考 Yitter.IdGenTest 的 Program.cs 啓動代碼。不過訂閱 ID 異步通知會有細微的性能損失。
-
異步或同步調用。你可在外部系統的異步(async 標記)方法中調用本算法,同步調用同樣沒問題。
-
使用雪花漂移算法。雖然代碼裏包含了傳統雪花算法的定義,並且你可以在入口處指定(Method=2)來啓用傳統算法,但仍建議你使用雪花漂移算法(Method=1,默認的),畢竟它具有更好的伸縮力和更高的性能。
-
輕易不要修改核心算法。本算法內部參數較多,邏輯較爲複雜,在你尚未掌握核心邏輯時,請勿嘗試修改核心代碼且用於生產環境,除非通過大量細緻、科學的測試驗證。
大型分佈式集成
-
可擴大 WorkerIdBitLength 到最大 20,支持 1,048,576 個節點,且不影響上述併發性能(50W/0.1s)。[算法支持]
-
採用中心化 IdGenerator 集羣,生成可用 Id 列表,存入 Redis 隊列供節點消費。此時 64 箇中心化節點數足夠大型互聯網項目使用。[需集成方擴展實現]
-
以上 2 條二選一即可,採用方法 2 一般是因爲不想增加最終 ID 長度,但節點數超過 64 個。
-
任何加大 WorkerIdBitLength 或 SeqBitLength 的設置,都可能會增加 ID 的長度。
配置變更
配置變更指是系統運行一段時間後,再變更運行參數(IdGeneratorOptions 選項值),請注意:
-
最重要的一條原則是:StartTime 只能往前(比老值更小、距離現在更遠)賦值,原因是往後賦值極大可能產生相同的時間戳。[不推薦在系統運行之後調整 StartTime]
-
任何時候增加 WorkerIdBitLength 或 SeqBitLength,都是可以的,但是慎用 “減小” 的操作,因爲這可能導致在未來某天生成的 ID 與過去老配置時相同。[允許在系統運行之後增加任何一個 BitLength 值]
-
如果必須減小 WorkerIdBitLength 或 SeqBitLength 其中的一項,一定要滿足一個條件:新的兩個 BitLength 之和要大於 老的值之和。[不推薦在運行之後縮小任何一個 BitLength 值]
-
上述 3 條規則,並未在本算法內做邏輯控制,集成方應根據上述規則做好影響評估,確認無誤後,再實施配置變更。
關於默認配置
-
默認配置能很好應對常規併發不超過 1w 次 / 1s,突發請求不超過 10W 次 / 1s 的場景。
-
若要突發請求值滿足 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