記一次“雪花算法”造成的生產(chǎn)事故的排查記錄
你好，我是悟空。
本文主要內(nèi)容如下：
前言
最近生產(chǎn)環(huán)境遇到一個問題：
現(xiàn)象：創(chuàng)建工單、訂單等地方，全都創(chuàng)建數(shù)據(jù)失敗。
初步排查：報錯信息為duplicate key，意思是保存數(shù)據(jù)的時候，報主鍵 id 重復(fù)，而這些 id 都是由雪花算法生成的，按道理來說，雪花算法生成的 ID 是唯一 ID，不應(yīng)該出現(xiàn)重復(fù)的 ID。
大家可以先猜猜是什么原因。
有的同學(xué)可能對雪花算法不熟悉，這里做個簡單的說明。（熟悉的同學(xué)可以跳到第二個段落）
一、雪花算法
snowflake（雪花算法）：Twitter 開源的分布式 id 生成算法，64 位的 long 型的 id，分為 4 部分：
snowflake 算法
- 1 bit：不用，統(tǒng)一為 0
- 41 bits：毫秒時間戳，可以表示 69 年的時間。
- 10 bits：5 bits 代表機房 id，5 個 bits 代表機器 id。最多代表 32 個機房，每個機房最多代表 32 臺機器。
- 12 bits：同一毫秒內(nèi)的 id，最多 4096 個不同 id，自增模式
優(yōu)點：
- 毫秒數(shù)在高位，自增序列在低位，整個ID都是趨勢遞增的。
- 不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。
- 可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。
缺點：
- 強依賴機器時鐘，如果機器上時鐘回撥（可以搜索2017 年閏秒 7:59:60找到相關(guān)問題），會導(dǎo)致發(fā)號重復(fù)或者服務(wù)會處于不可用狀態(tài)。
閏秒就是通過給“世界標(biāo)準(zhǔn)時間”加（或減）1秒，讓它更接近“太陽時”。例如，兩者相差超過0.9秒時，就在23點59分59秒與00點00分00秒之間，插入一個原本不存在的“23點59分60秒”，來將時間調(diào)慢一秒鐘。
看了上面的關(guān)于雪花算法的簡短介紹，想必大家能猜出個一二了。
雪花算法和時間是強關(guān)聯(lián)的，其中有 41 位是當(dāng)前時間的時間戳，那么會不會和時間有關(guān)？
二、排查
2.1 雪花算法有什么問題？
既然是雪花算法的問題，那我們就來看下雪花算法出了什么問題：
（1）What：雪花算法生成了重復(fù)的 ID，這些 ID 是什么樣的？
（2）Why：雪花算法為什么生成了重復(fù)的 key
第一個問題，我們可以通過報錯信息發(fā)現(xiàn)，這個重復(fù)的 ID 是 -1，這個就很奇怪了。一般雪花算法生成的唯一 ID 如下所示，我分別用二進制和十進制來表示：
找到項目中使用雪花算法的工具類，生成 ID 的時候有個判斷邏輯：
當(dāng)當(dāng)前時間?小于上次的生成時間?就會返回 -1，所以問題就出在這個邏輯上面。(有的雪花算法是直接拋異常)
由于每次 timestamp? 都是小于 lastTimeStamp，所以每次都返回了 -1，這也解釋了為什么生成了重復(fù)的 key。
2.2 時鐘回撥或跳躍
那么問題就聚焦?在為什么當(dāng)前時間?還會小于上次的生成時間。
下面有種場景可能發(fā)生這種情況：
首先假定當(dāng)前的北京時間是 9:00:00。另外上次生成 ID 的時候，服務(wù)器獲取的時間 lastTimestamp=10:00:00，而現(xiàn)在服務(wù)器獲取的當(dāng)前時間 timestamp=09:00:00，這就相當(dāng)于服務(wù)器之前是獲取了一個未來時間，現(xiàn)在突然跳躍到當(dāng)前時間。
而這種場景我們稱之為時鐘回撥或時鐘跳躍。
時鐘回撥：服務(wù)器時鐘可能會因為各種原因發(fā)生不準(zhǔn)，而網(wǎng)絡(luò)中會提供 NTP 服務(wù)來做時間校準(zhǔn)，因此在做校準(zhǔn)的時候，服務(wù)器時鐘就會發(fā)生時鐘的跳躍或者回撥問題。
2.3 時鐘同步
那么服務(wù)器為什么會發(fā)生時鐘回撥或跳躍呢？
我們猜測是不是服務(wù)器上的時鐘不同步后，又自動進行同步了，前后時間不一致。
首先我們的每臺服務(wù)器上都安裝了 ntpdate? 軟件，作為 NTP 客戶端，會每隔 10 分鐘?向 NTP 時間服務(wù)器同步一次時間。
如下圖所示，服務(wù)器 1 和 服務(wù)器 2 部署了應(yīng)用服務(wù)，每隔 10 分鐘向時間服務(wù)器?同步一次時間，來保證服務(wù)器 1 和服務(wù)器 2 的時間和時間服務(wù)器的時間一致。
每隔 10 分鐘同步的設(shè)置：
另外時間服務(wù)器會向 NTP Pool同步時間，NTP Pool 正在為世界各地成百上千萬的系統(tǒng)提供服務(wù)。它是絕大多數(shù)主流Linux發(fā)行版和許多網(wǎng)絡(luò)設(shè)備的默認“時間服務(wù)器”。（參考ntppool.org）
那問題就是 NTP 同步出了問題？？
2.4 時鐘不同步
我們到服務(wù)器上查看了下時間，確實和時鐘服務(wù)器不同步，早了幾分鐘。
當(dāng)我們執(zhí)行 NTP 同步的命令后，時鐘又同步了，也就是說時間回撥了。同步的命令如下：
在產(chǎn)生事故之前，我們重啟過服務(wù)器 1。我們推測服務(wù)器重啟后，服務(wù)器因網(wǎng)絡(luò)問題沒有正常同步。而在下一次定時同步操作到來之前的這個時間段，我們的后端服務(wù)已經(jīng)出現(xiàn)了因 ID 重復(fù)導(dǎo)致的大量異常問題。
這個 NTP 時鐘回撥的偶發(fā)現(xiàn)象并不常見，但時鐘回撥確實會帶了很多問題，比如潤秒 問題也會帶來 1s 時間的回撥。
為了預(yù)防這種情況的發(fā)生，網(wǎng)上也有一些開源解決方案。
三、解決方案
（1）方式一：使用美團 Leaf方案，基于雪花算法。
（2）方式二：使用百度 UidGenerator，基于雪花算法。
（3）方式三：用 Redis 生成自增的分布式 ID。弊端是 ID 容易被猜到，有安全風(fēng)險。
3.1 美團的 Leaf 方案
美團的開源項目 Leaf? 的方案：采用依賴 ZooKeeper 的數(shù)據(jù)存儲。如果時鐘回撥的時間超過最大容忍的毫秒數(shù)閾值，則程序報錯；如果在可容忍的范圍內(nèi)，Leaf 會等待時鐘同步到最后一次主鍵生成的時間后再繼續(xù)工作。
重點就是需要等待時鐘同步！
3.2 百度 UidGenerator 方案
百度UidGenerator方案不在每次獲取 ID 時都實時計算分布式 ID，而是利用 RingBuffer 數(shù)據(jù)結(jié)構(gòu)，通過緩存的方式預(yù)生成一批唯一 ID 列表，然后通過 incrementAndGet() 方法獲取下一次的時間，從而脫離了對服務(wù)器時間的依賴，也就不會有時鐘回撥的問題。
重點就是預(yù)生成一批 ID！
Github地址：
四、總結(jié)
本篇通過一次偶發(fā)的生產(chǎn)事故，引出了雪花算法的原理、雪花算法的不足、對應(yīng)的開源解決方案。
雪花算法因強依賴服務(wù)器的時鐘，如果時鐘產(chǎn)生了回撥，就會造成很多問題。
我們的系統(tǒng)雖然做了 NTP 時鐘同步，但也不是 100% 可靠，而且潤秒這種場景也是出現(xiàn)過很多次。鑒于此，美團和百度也有對應(yīng)的解決方案。
最后，我們的生產(chǎn)環(huán)境也是第一次遇到因 NTP 導(dǎo)致的時鐘回撥，而且系統(tǒng)中用到雪花算法的地方并不多，所以目前并沒有采取以上的替換方案。
雪花算法的代碼已經(jīng)上傳到 Gitlab：
參考資料：
https://time.geekbang.org/dailylesson/detail/100075739
https://blog.csdn.net/liangcsdn111/article/details/126103041
https://www.jianshu.com/p/291110ca60fc
