雪花算法(snowflake)是Twitter提出的一種在分布式系統(tǒng)中生成唯一ID的算法。格式如下：
算法生成的是一個64位整型數(shù)字，由四部分組成：
首位始終填0。
接下來41位是從某個時間點開始計算的時間戳，單位為毫秒，可以不重復(fù)使用69年。
接下來10位是WorkerID，可以分配1024個節(jié)點。
最后12位是順序增長的序列號，每個節(jié)點每毫秒可以生成4096個ID。
算法本身本身比較簡單，優(yōu)勢在于：
不依賴于外部服務(wù)器，不需要額外的網(wǎng)絡(luò)通信，實現(xiàn)簡單
生成效率高
生成的ID總體有序增長
除首位外剩下三個部分的長度可以自由劃分
雖然算法本身比較簡單，但是有幾個地方值得把玩一下，下面一一道來。
為什么首位始終是0
雪花算法生成的是64位整數(shù)，對于一些應(yīng)用來說，比特占用情況是比較緊張的，為什么還要把首位始終設(shè)置為0不使用呢？這是因為Java中，所有整數(shù)都是有符號的。對于有符號數(shù)，首位為0表示正數(shù)，為1表示負(fù)數(shù)，所以需要把首位設(shè)置為0。當(dāng)然，如果你的應(yīng)用不需要考慮Java環(huán)境，這一位也可以正常使用。
三部分的位數(shù)如何劃分
對于請求量不大的業(yè)務(wù)，時間戳部分可以不用毫秒為單位。根據(jù)業(yè)務(wù)情況可以在毫秒到秒之間取舍，比如10毫秒或者秒。
對于進程多的業(yè)務(wù)，10位WorkerID字段很可能不夠用，需要從時間戳和序列號部分摳出一些比特來用。
WorkerID如何生成
本來以為這是一個很簡單的問題，但一些環(huán)境卻會使這個問題變復(fù)雜。
對于非云上業(yè)務(wù)，可以在本地配置文件中配置唯一的ServerID，進程啟動時讀取這個配置當(dāng)作WorkerID來使用。
對于Kubernetes上的業(yè)務(wù)，會復(fù)雜一些。因為Kubernetes上的業(yè)務(wù)沒有本地配置文件，需要想想其他的方案。
方案一：如果自己能控制Pod IP的分配方式，可以考慮使用IP的低16位或者若干位作為WokerID。前提是能夠確保這些位不會有重復(fù)。
方案二：使用MySQL或者Redis的自增長字段來分配WorkerID。每次進程啟動的時候，從MySQL或者Redis取一個增長的ID使用，因為只需要啟動的時候和MySQL通信一次，之后一直使用這個ID，所以生成的性能不會受影響。如果業(yè)務(wù)重啟不頻繁的話，可以考慮這個方案。如果頻繁的話，因為WorkerID的位數(shù)是有限的，比如10位是1024，16位是65536，也就是說只能重啟1024次或者65536次。MySQL中的自增長ID超過這個最大值的話，只能循環(huán)從0開始，如果上一次分配的使用這個ID的進程還健在，就重復(fù)了，從而會造成使用雪花生成的唯一ID重復(fù)。那怎么辦呢？
方案三：在MySQL中設(shè)置兩個字段，一個字段是未分配的ID列表，另一個字段是已分配的ID列表。
預(yù)先在未分配列表中填充1024（10位WorkerID）個數(shù)字。
進程啟動時從未分配ID列表中取一個ID，作為WorkerID，同時放到已分配ID列表中。
進程退出時，把ID從已分配列表刪除，添加到未分配列表中。
這個方案需要注意不同進程并發(fā)獲取ID造成的問題，可以考慮使用數(shù)據(jù)版本號等CAS方式來做到原子修改。
另外如果進程意外退出，那這個ID就不能回收到未分配列表中了。對于這個問題，如果池子中的ID足夠多，可以不用考慮，畢竟進程不可能天天崩潰，ID夠多的話足夠應(yīng)付很多年了。
方案四：MySQL中還是設(shè)置未分配ID列表和已分配ID列表，但使用租約機制，給已分配ID列表中每個ID添加一個時間戳表示這個ID的更新時間。進程啟動獲取這個ID后，需要定期到MySQL中更新這個ID的時間戳。如果進程意外退出，并且未分配ID列表中沒有了可用ID，從已分配列表中找一個租約已經(jīng)過期的ID使用。
方案五：增加ID分配服務(wù)器。但是這要考慮這個分配服務(wù)器的可用性問題，崩潰了怎么處理等。
系統(tǒng)時間回退怎么辦
如果系統(tǒng)開了NTP網(wǎng)絡(luò)對時協(xié)議的話，系統(tǒng)時間是有可能回退的，這會導(dǎo)致雪花算法生成的ID重復(fù)。所以一般系統(tǒng)會關(guān)閉NTP對時協(xié)議。但即使關(guān)閉了NTP對時協(xié)議，也可能遇到時間回退的情況，比如說閏秒。遇到這種情況，可以通過設(shè)置一到兩位時間回?fù)芪坏姆绞浇鉀Q，如下：
(圖來自https://juejin.im/post/6844904035380658190)
算法中記錄上一次生成的時間戳，發(fā)現(xiàn)有時間回退時，將時間回?fù)芪患?，繼續(xù)生成ID。這樣雖然時間戳字段的值可能和之前的一樣，但是回?fù)芪坏闹挡灰粯?，生成的ID是不會重復(fù)的。如果系統(tǒng)的時間超過了上一次的回退時間后可以把回?fù)芪粴w0。一位回?fù)芪豢梢栽试S系統(tǒng)時間回退一次，兩位回?fù)芪豢梢栽试S系統(tǒng)時間連續(xù)回退三次。一般設(shè)置一位回?fù)芪痪蛪蛴昧恕?/p>
參考
Resolve Leap Second Issues in Red Hat Enterprise Linux
How to find out if the linux kernel will insert a leap second at the end of the month
