前面文章在談論分布式唯一ID生成的時候，有提到雪花算法，這一次，我們詳細點講解，只講它。
SnowFlake算法
據國家大氣研究中心的查爾斯·奈特稱，一般的雪花大約由10^19個水分子組成。在雪花形成過程中，會形成不同的結構分支，所以說大自然中不存在兩片完全一樣的雪花，每一片雪花都擁有自己漂亮獨特的形狀。雪花算法表示生成的id如雪花般獨一無二。
snowflake是Twitter開源的分布式ID生成算法，結果是一個long型的ID。其核心思想是：使用41bit作為毫秒數，10bit作為機器的ID（5個bit是數據中心，5個bit的機器ID），12bit作為毫秒內的流水號（意味著每個節點在每毫秒可以產生 4096 個 ID），最后還有一個符號位，永遠是0。
核心思想：分布式，唯一。
算法具體介紹
雪花算法是 64 位 的二進制，一共包含了四部分：
- 1位是符號位，也就是最高位，始終是0，沒有任何意義，因為要是唯一計算機二進制補碼中就是負數，0才是正數。
- 41位是時間戳，具體到毫秒，41位的二進制可以使用69年，因為時間理論上永恒遞增，所以根據這個排序是可以的。
- 10位是機器標識，可以全部用作機器ID，也可以用來標識機房ID + 機器ID，10位最多可以表示1024臺機器。
- 12位是計數序列號，也就是同一臺機器上同一時間，理論上還可以同時生成不同的ID，12位的序列號能夠區分出4096個ID。
優化
由于41位是時間戳，我們的時間計算是從1970年開始的，只能使用69年，為了不浪費，其實我們可以用時間的相對值，也就是以項目開始的時間為基準時間，往后可以使用69年。獲取唯一ID的服務，對處理速度要求比較高，所以我們全部使用位運算以及位移操作，獲取當前時間可以使用System.currentTimeMillis()。
時間回撥問題
在獲取時間的時候，可能會出現時間回撥的問題，什么是時間回撥問題呢？就是服務器上的時間突然倒退到之前的時間。
- 人為原因，把系統環境的時間改了。
- 有時候不同的機器上需要同步時間，可能不同機器之間存在誤差，那么可能會出現時間回撥問題。
解決方案
- 回撥時間小的時候，不生成 ID，循環等待到時間點到達。
- 上面的方案只適合時鐘回撥較小的，如果間隔過大，阻塞等待，肯定是不可取的，因此要么超過一定大小的回撥直接報錯，拒絕服務，或者有一種方案是利用拓展位，回撥之后在拓展位上加1就可以了，這樣ID依然可以保持唯一。但是這個要求我們提前預留出位數，要么從機器id中，要么從序列號中，騰出一定的位，在時間回撥的時候，這個位置 +1。
由于時間回撥導致的生產重復的ID的問題，其實百度和美團都有自己的解決方案了，有興趣可以去看看，下面不是它們官網文檔的信息：
- 百度UIDGenerator：https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md
- UidGenerator是JAVA實現的, 基于Snowflake算法的唯一ID生成器。UidGenerator以組件形式工作在應用項目中, 支持自定義workerId位數和初始化策略, 從而適用于Docker等虛擬化環境下實例自動重啟、漂移等場景。 在實現上, UidGenerator通過借用未來時間來解決sequence天然存在的并發限制; 采用RingBuffer來緩存已生成的UID, 并行化UID的生產和消費, 同時對CacheLine補齊，避免了由RingBuffer帶來的硬件級「偽共享」問題. 最終單機QPS可達600萬。
- 美團Leaf:https://tech.meituan.com/2019/03/07/open-source-project-leaf.html
- leaf-segment 方案
- 優化：雙buffer + 預分配
- 容災：MySQL DB 一主兩從，異地機房，半同步方式
- 缺點：如果用segment號段式方案：id是遞增，可計算的，不適用于訂單ID生成場景，比如競對在兩天中午12點分別下單，通過訂單id號相減就能大致計算出公司一天的訂單量，這個是不能忍受的。
- leaf-snowflake方案
- 使用Zookeeper持久順序節點的特性自動對snowflake節點配置workerID
- 1.啟動Leaf-snowflake服務，連接Zookeeper，在leaf_forever父節點下檢查自己是否已經注冊過（是否有該順序子節點）。
- 2.如果有注冊過直接取回自己的workerID（zk順序節點生成的int類型ID號），啟動服務。
- 3.如果沒有注冊過，就在該父節點下面創建一個持久順序節點，創建成功后取回順序號當做自己的workerID號，啟動服務。
- 緩存workerID，減少第三方組件的依賴
- 由于強依賴時鐘，對時間的要求比較敏感，在機器工作時NTP同步也會造成秒級別的回退，建議可以直接關閉NTP同步。要么在時鐘回撥的時候直接不提供服務直接返回ERROR_CODE，等時鐘追上即可。或者做一層重試，然后上報報警系統，更或者是發現有時鐘回撥之后自動摘除本身節點并報警
- 使用Zookeeper持久順序節點的特性自動對snowflake節點配置workerID
- leaf-segment 方案
代碼展示
public class SnowFlake {
// 數據中心(機房) id
private long datacenterId;
// 機器ID
private long workerId;
// 同一時間的序列
private long sequence;
public SnowFlake(long workerId, long datacenterId) {
this(workerId, datacenterId, 0);
}
public SnowFlake(long workerId, long datacenterId, long sequence) {
// 合法判斷
if (workerId > maxWorkerId || workerId < 0) {
throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
}
if (datacenterId > maxDatacenterId || datacenterId < 0) {
throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
}
System.out.printf("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);
this.workerId = workerId;
this.datacenterId = datacenterId;
this.sequence = sequence;
}
// 開始時間戳（2021-10-16 22:03:32）
private long twepoch = 1634393012000L;
// 機房號，的ID所占的位數 5個bit 最大:11111(2進制)--> 31(10進制)
private long datacenterIdBits = 5L;
// 機器ID所占的位數 5個bit 最大:11111(2進制)--> 31(10進制)
private long workerIdBits = 5L;
// 5 bit最多只能有31個數字，就是說機器id最多只能是32以內
private long maxWorkerId = -1L ^ (-1L << workerIdBits);
// 5 bit最多只能有31個數字，機房id最多只能是32以內
private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
// 同一時間的序列所占的位數 12個bit 111111111111 = 4095 最多就是同一毫秒生成4096個
private long sequenceBits = 12L;
// workerId的偏移量
private long workerIdShift = sequenceBits;
// datacenterId的偏移量
private long datacenterIdShift = sequenceBits + workerIdBits;
// timestampLeft的偏移量
private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
// 序列號掩碼 4095 (0b111111111111=0xfff=4095)
// 用于序號的與運算，保證序號最大值在0-4095之間
private long sequenceMask = -1L ^ (-1L << sequenceBits);
// 最近一次時間戳
private long lastTimestamp = -1L;
// 獲取機器ID
public long getWorkerId() {
return workerId;
}
// 獲取機房ID
public long getDatacenterId() {
return datacenterId;
}
// 獲取最新一次獲取的時間戳
public long getLastTimestamp() {
return lastTimestamp;
}
// 獲取下一個隨機的ID
public synchronized long nextId() {
// 獲取當前時間戳，單位毫秒
long timestamp = timeGen();
if (timestamp < lastTimestamp) {
System.err.printf("clock is moving backwards. Rejecting requests until %d.", lastTimestamp);
throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds",
lastTimestamp - timestamp));
}
// 去重
if (lastTimestamp == timestamp) {
sequence = (sequence + 1) & sequenceMask;
// sequence序列大于4095
if (sequence == 0) {
// 調用到下一個時間戳的方法
timestamp = tilNextMillis(lastTimestamp);
}
} else {
// 如果是當前時間的第一次獲取，那么就置為0
sequence = 0;
}
// 記錄上一次的時間戳
lastTimestamp = timestamp;
// 偏移計算
return ((timestamp - twepoch) << timestampLeftShift) |
(datacenterId << datacenterIdShift) |
(workerId << workerIdShift) |
sequence;
}
private long tilNextMillis(long lastTimestamp) {
// 獲取最新時間戳
long timestamp = timeGen();
// 如果發現最新的時間戳小于或者等于序列號已經超4095的那個時間戳
while (timestamp <= lastTimestamp) {
// 不符合則繼續
timestamp = timeGen();
}
return timestamp;
}
private long timeGen() {
return System.currentTimeMillis();
}
public static void main(String[] args) {
SnowFlake worker = new SnowFlake(1, 1);
long timer = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
worker.nextId();
}
System.out.println(System.currentTimeMillis());
System.out.println(System.currentTimeMillis() - timer);
}
}
問題分析
1. 第一位為什么不使用?
在計算機的表示中，第一位是符號位，0表示整數，第一位如果是1則表示負數，我們用的ID默認就是正數，所以默認就是0，那么這一位默認就沒有意義。
2.機器位怎么用？
機器位或者機房位，一共10 bit，如果全部表示機器，那么可以表示1024臺機器，如果拆分，5 bit 表示機房，5bit表示機房里面的機器，那么可以有32個機房，每個機房可以用32臺機器。
3. twepoch表示什么？
由于時間戳只能用69年，我們的計時又是從1970年開始的，所以這個twepoch表示從項目開始的時間，用生成ID的時間減去twepoch作為時間戳，可以使用更久。
4. -1L ^ (-1L << x) 表示什么？
表示 x 位二進制可以表示多少個數值，假設x為3：
在計算機中，第一位是符號位，負數的反碼是除了符號位，1變0，0變1, 而補碼則是反碼+1：
-1L 原碼：1000 0001
-1L 反碼：1111 1110
-1L 補碼：1111 1111
從上面的結果可以知道，-1L其實在二進制里面其實就是全部為1,那么 -1L 左移動 3位，其實得到 1111 1000，也就是最后3位是0，再與-1L異或計算之后，其實得到的，就是后面3位全是1。-1L ^ (-1L << x) 表示的其實就是x位全是1的值，也就是x位的二進制能表示的最大數值。
5.時間戳比較
在獲取時間戳小于上一次獲取的時間戳的時候，不能生成ID，而是繼續循環，直到生成可用的ID，這里沒有使用拓展位防止時鐘回撥。
6.前端直接使用發生精度丟失
如果前端直接使用服務端生成的long 類型 id，會發生精度丟失的問題，因為 JS 中Number是16位的（指的是十進制的數字），而雪花算法計算出來最長的數字是19位的，這個時候需要用 String 作為中間轉換，輸出到前端即可。
秦懷の觀點
雪花算法其實是依賴于時間的一致性的，如果時間回撥，就可能有問題，一般使用拓展位解決。而只能使用69年這個時間限制，其實可以根據自己的需要，把時間戳的位數設置得更多一點，比如42位可以用139年，但是很多公司首先得活下來。當然雪花算法也不是銀彈，它也有缺點，在單機上遞增，而多臺機器只是大致遞增趨勢，并不是嚴格遞增的。
沒有最好的設計方案，只有合適和不合適的方案。
原文：
https://www.cnblogs.com/Damaer/p/15559201.html
