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