📣讀完這篇文章里你能收獲到

• 圖文形式為你講解原生雪花算法的特征及原理
• 了解時(shí)間回?fù)艿母拍钜约翱赡芤鸢l(fā)此現(xiàn)象的操作
• 掌握時(shí)間回?fù)艿慕鉀Q方案—基于時(shí)鐘序列的雪花算法
• 關(guān)于雪花算法的常見問題解答

文章目錄

• 一、原生的雪花算法
• • 1. 簡(jiǎn)介
  • 2. 特征
  • 3. 原理
  • • 3.1 格式（64bit）
    • 3.2 字節(jié)分配
• 二、雪花算法的時(shí)間回?fù)軉栴}
• • 1. 問題描述
  • 2. 現(xiàn)象引發(fā)
  • 3. 常見的處理方式
  • • 3.1 直接拋出異常
    • 3.2 延遲等待
• 三、基于時(shí)鐘序列解決時(shí)間回?fù)艿姆桨?/li>
• • 1. 簡(jiǎn)介
  • 2. 設(shè)計(jì)思路
  • 3. 算法支持
  • 4. 關(guān)鍵實(shí)現(xiàn)代碼
• 四、關(guān)于雪花算法的常見問題解答
• • 1. 雪花算法支持的并發(fā)數(shù)最大多少？
  • 2. 雪花算法支持最多支持系統(tǒng)運(yùn)行多少年？
  • 3. 用了雪花Id，出現(xiàn)負(fù)閏秒為什么會(huì)導(dǎo)致系統(tǒng)大量拋異常？

一、原生的雪花算法

1. 簡(jiǎn)介

• 分布式 ID 生成算法用于在分布式系統(tǒng)中生成全局唯一的 ID 標(biāo)識(shí)
• Twitter 提出的雪花算法便是其中一種知名的算法，也是一種發(fā)號(hào)器方案
• 百度（uid-generator）、美團(tuán)（Leaf）及滴滴（Tinyid）等開源分布式ID都是基于雪花算法實(shí)現(xiàn)的，如果有人問你有關(guān)唯一 ID 生成的問題，你應(yīng)該立即想到雪花！
• 雪花是二進(jìn)制的 64位（只有 63 位用于填充有符號(hào)整數(shù)），最終數(shù)字一般以十進(jìn)制序列化

2. 特征

• 全局唯一性：雪花算法可以保證集群系統(tǒng)的ID全局唯一
• 趨勢(shì)遞增：由于強(qiáng)依賴時(shí)間戳，所以整體趨勢(shì)會(huì)隨著時(shí)間遞增
• 單調(diào)遞增（×）：不滿足單調(diào)遞增，在不考慮時(shí)間回?fù)艿那闆r下，雖然在單機(jī)中可以保持單調(diào)遞增，但在分布式集群中無法做到單調(diào)遞增，只能保證總體趨勢(shì)遞增
• 信息安全指的是ID生成不規(guī)則，無法猜測(cè)下一個(gè)

3. 原理

3.1 格式（64bit）

二進(jìn)制64位長(zhǎng)整型數(shù)字：1bit保留 + 41bit時(shí)間戳 + 10bit機(jī)器 + 12bit序列號(hào)

3.2 字節(jié)分配

• 1bit不用：因?yàn)槎M(jìn)制中最高位是符號(hào)位，1表示負(fù)數(shù)，0表示正數(shù)，生成的id一般都是用整數(shù)，所以最高位固定為0
• 41bit時(shí)間戳：這里采用的就是當(dāng)前系統(tǒng)的具體時(shí)間，單位為毫秒
• 10bit工作機(jī)器ID（workerId）：每臺(tái)機(jī)器分配一個(gè)id，這樣可以標(biāo)示不同的機(jī)器，但是上限為1024，標(biāo)示一個(gè)集群某個(gè)業(yè)務(wù)最多部署的機(jī)器個(gè)數(shù)上限
• 12bit序列號(hào)（自增域）：表示在某一毫秒下，這個(gè)自增域最大可以分配的bit個(gè)數(shù)，在當(dāng)前這種配置下，每一毫秒可以分配2^12 = 4096個(gè)數(shù)據(jù)

二、雪花算法的時(shí)間回?fù)軉栴}

1. 問題描述

簡(jiǎn)單說就是時(shí)間被調(diào)整回到了之前的時(shí)間，由于雪花算法重度依賴機(jī)器的當(dāng)前時(shí)間，所以一旦發(fā)生時(shí)間回?fù)?#xff0c;將有可能導(dǎo)致生成的 ID 可能與此前已經(jīng)生成的某個(gè) ID 重復(fù)（前提是剛好在同一毫秒生成 ID 時(shí)序列號(hào)也剛好一致），這就是雪花算法最經(jīng)常討論的問題——時(shí)間回?fù)?/p>

2. 現(xiàn)象引發(fā)

• 網(wǎng)絡(luò)時(shí)間校準(zhǔn)
• 人工設(shè)置
• 出現(xiàn)負(fù)閏秒（關(guān)于閏秒的介紹會(huì)在后面講到）

3. 常見的處理方式

3.1 直接拋出異常

在雪花算法原本的實(shí)現(xiàn)中，針對(duì)這種問題，算法本身只是返回錯(cuò)誤，由應(yīng)用另行決定處理邏輯，如果是在一個(gè)并發(fā)不高或者請(qǐng)求量不大的業(yè)務(wù)系統(tǒng)中，錯(cuò)誤等待或者重試的策略問題不大，但是如果是在一個(gè)高并發(fā)的系統(tǒng)中，這種策略顯得過于粗暴

3.2 延遲等待

將當(dāng)前線程阻塞3ms，之后再獲取時(shí)間，看時(shí)間是否比上一次請(qǐng)求的時(shí)間大，如果大了，說明恢復(fù)正常了，則不用管如果還小,說明真出問題了，則拋出異常，缺點(diǎn)仍然如3.1所描述

當(dāng)使用雪花算法出現(xiàn)時(shí)間回?fù)軙r(shí)，不想拋異常，又希望能繼續(xù)保持全局唯一性、趨勢(shì)遞增、信息安全，可以了解第四點(diǎn)，基于時(shí)間序列的方案

三、基于時(shí)鐘序列解決時(shí)間回?fù)艿姆桨?/h1>

1. 簡(jiǎn)介

我這里介紹的是一種基于修改擴(kuò)展位的思路，基于時(shí)鐘序列的雪花算法
二進(jìn)制64位長(zhǎng)整型數(shù)字：1bit保留 + 41bit時(shí)間戳 + 3位時(shí)鐘序列 + 7bit機(jī)器 + 12bit序列號(hào)

2. 設(shè)計(jì)思路

• 如上圖，將原本10位的機(jī)器碼拆分成3位時(shí)鐘序列及7位機(jī)器碼
• 發(fā)生時(shí)間回?fù)艿臅r(shí)候，時(shí)間已經(jīng)發(fā)生了變化，那么這時(shí)將時(shí)鐘序列新增1位，重新定義整個(gè)雪花Id
• 為了避免實(shí)例重啟引起時(shí)間序列丟失，因此時(shí)鐘序列最好通過DB/緩存等方式存儲(chǔ)起來

3. 算法支持

• 還是支持最長(zhǎng) 69 年多的運(yùn)行時(shí)間
• 分布式實(shí)例規(guī)模由2^{10（1024）降至2}7（128）
• 單實(shí)例每毫秒仍然支持 4096次請(qǐng)求
• 每個(gè)分布式實(shí)例支持最多 2^3（8） 次時(shí)間回?fù)?/li>

4. 關(guān)鍵實(shí)現(xiàn)代碼

.Net Demo 其他語言參考流程自行改造

/// <summary> /// 獲取下一個(gè)ID /// </summary> /// <returns></returns> public long NextId() {lock (_lock){//當(dāng)前系統(tǒng)時(shí)間戳var currentTimestamp = TimeGen();//出現(xiàn)時(shí)間回?fù)?當(dāng)前系統(tǒng)時(shí)間小于最后更新時(shí)間if (currentTimestamp < _lastTimestamp){// _clockSequence自增，和CLOCK_SEQUENCE_MASK相與一下，去掉高位_clockSequence = (_clockSequence + 1) & CLOCK_SEQUENCE_MASK;}// 如果上次生成時(shí)間和當(dāng)前時(shí)間相同，在同一毫秒內(nèi)if (_lastTimestamp == currentTimestamp){// sequence自增，和SEQUENCE_MASK相與一下，去掉高位_sequence = (_sequence + 1) & SEQUENCE_MASK;//判斷是否溢出,也就是每毫秒內(nèi)超過1024，當(dāng)為1024時(shí)，與sequenceMask相與，sequence就等于0if (_sequence == 0){//等待到下一毫秒currentTimestamp = TilNextMillis(_lastTimestamp);}}else{//如果和上次生成時(shí)間不同,重置sequence，就是下一毫秒開始，sequence計(jì)數(shù)重新從0開始累加,_sequence = 0;}_lastTimestamp = currentTimestamp;return ((currentTimestamp - TWEPOCH) << TIMESTAMP_LEFT_SHIFT) | _clockSequence << CLOCK_SEQUENCE_SHIFT | (WorkerId << WORKER_ID_SHIFT) | _sequence;} }

‘

四、關(guān)于雪花算法的常見問題解答

1. 雪花算法支持的并發(fā)數(shù)最大多少？

• 這個(gè)是由序列號(hào)的位數(shù)決定的，原生雪花算法序列號(hào)12位，也就是1毫秒最大可生成2^12（4096），相當(dāng)于1秒可生成 4096 * 1000 個(gè)ID，也就是QPS可以到 409.6 w/s

2. 雪花算法支持最多支持系統(tǒng)運(yùn)行多少年？

• 這個(gè)是由時(shí)間戳位數(shù)決定的，原生雪花算法時(shí)間戳占41位，也就是支持最大的時(shí)間戳為2^41（2199023255552），而1年的總毫秒數(shù)為3600 * 1000 * 24 * 365 = 31,536,000,000，因此2^41 / 1年的總毫秒數(shù)≈69.7年

• 其實(shí)衍生出另一個(gè)問題，41位能表示的最大的時(shí)間戳為2^41（2199023255552）對(duì)應(yīng)的時(shí)間應(yīng)該是2039-09-07 23:47:35，距離現(xiàn)在只有不到20年的時(shí)間，為什么算出來的是69年呢？

• 其實(shí)時(shí)間戳的算法是1970年1月1日到指點(diǎn)時(shí)間所經(jīng)過的毫秒或秒數(shù)，那咱們把開始時(shí)間從2021年開始，就可以延長(zhǎng)41位時(shí)間戳能表達(dá)的最大時(shí)間，所以這里實(shí)際指的是相對(duì)自定義開始時(shí)間的時(shí)間戳

3. 用了雪花Id，出現(xiàn)負(fù)閏秒為什么會(huì)導(dǎo)致系統(tǒng)大量拋異常？

• 閏秒是偶爾運(yùn)用于協(xié)調(diào)世界時(shí)（UTC）的調(diào)整，經(jīng)由增加或減少一秒，以消彌精確的時(shí)間（使用原子鐘測(cè)量）和不精確的觀測(cè)太陽時(shí)（稱為UT1)，之間的差異
• 這種做法已被證明具有破壞性，特別是在二十一世紀(jì)，尤其是在依賴精確時(shí)間戳或時(shí)間關(guān)鍵程序控制的服務(wù)中
• 而雪花算法嚴(yán)重依賴時(shí)間戳，當(dāng)出現(xiàn)負(fù)閏秒也就是時(shí)間減少一秒時(shí)（時(shí)間往前回?fù)?秒），雪花Id就可能出現(xiàn)重復(fù)，而原生的雪花算法出現(xiàn)時(shí)間回?fù)艿奶幚矸绞绞侵苯訏伄惓?/li>
• 2022年11月，在第27屆國(guó)際計(jì)量大會(huì)上，科學(xué)家和政府代表投票決定到2035年取消閏秒

總結(jié)

以上是生活随笔為你收集整理的『SnowFlake』雪花算法的详解及时间回拨解决方案的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。