大家好，我是飄渺。昨天小伙伴使用Mybaits-Plus開發的項目線上（集群、K8S）出現了主鍵重復問題，其報錯如下：

圖片

Mybatis-Plus啟動時會通過com.baomidou.mybatisplus.core.toolkit.Sequence類的getMaxWorkerId()和getDatacenterId()方法來初始化workerId和dataCenterId()。

protected long getMaxWorkerId(long datacenterId, long maxWorkerId) {
    StringBuilder mpid = new StringBuilder();
    mpid.append(datacenterId);
    String name = ManagementFactory.getRuntimeMXBean().getName();
    if (StringUtils.isNotBlank(name)) {
        mpid.append(name.split("@")[0]);
    }

    return (long)(mpid.toString().hashCode() & '\uffff') % (maxWorkerId + 1L);
}

protected long getDatacenterId(long maxDatacenterId) {
    ...省略部分代碼...
    byte[] mac = network.getHardwareAddress();
    if (null != mac) {
        id = (255L & (long)mac[mac.length - 2] | 65280L & (long)mac[mac.length - 1] << 8) >> 6;
        id %= maxDatacenterId + 1L;
    }  

    return id;
}

通過代碼可知，workerID是根據虛擬機名稱生成，dataCenterId是根據mac地址生成，這2個東西部署在Docker環境中就很有可能重復。

本文不去探討怎么解決這個問題，而是給你推薦另外一個經過優化后的雪花算法，可以非常方便集成在你項目中并替換掉Mybatis-Plus的ID生成邏輯。

概述

在軟件開發過程中，我們經常會遇到需要生成全局唯一流水號的場景，例如各種流水號和分庫分表的分布式主鍵ID。特別是在使用MySQL數據庫時，除了要求流水號具有“全局唯一”性外，還需要具備“遞增趨勢”，以減少MySQL的數據頁分裂，從而降低數據庫IO壓力并提升服務器性能。

因此，在項目中通常需要引入一種算法，能夠生成滿足“全局唯一”、“遞增趨勢”和“高性能”要求的數據。

關于全局分布式ID的生成，網上有很多相關文章。其中最常見的方法是借助第三方開源組件實現，如百度開源的Uidgenerator、滴滴開源的TinyID、美團開源的Leaf以及雪花算法SnowFlake等。然而，大部分開源組件都需要依賴數據庫或Redis中間件來實現，對于非特大型項目來說可能過于繁重。因此，我更傾向于在項目中使用雪花算法SnowFlake來生成全局唯一ID。

標準版雪花算法網上已經有很多解讀文章了，此處就不再贅述了。

然而，標準版的雪花算法存在 時鐘敏感 問題。由于ID生成與當前操作系統時間戳綁定（利用了時間的單調遞增性），當操作系統的時鐘出現回撥時，生成的ID可能會重復（盡管通常不會人為地回撥時鐘，但服務器可能會出現偶發的“時鐘漂移”現象）。

如果要要解決這個問題，我們可以在獲取 ID 時記錄當前的時間戳。然后在下一次獲取 ID 時，比較當前時間戳和上次記錄的時間戳。如果發現當前時間戳小于上次記錄的時間戳，說明出現了時鐘回撥現象，此時可以拒絕服務并等待時間戳追上記錄值。

因此，在項目中我們不能直接使用標準版的雪花算法，而需要尋找一個改良后的方案。

這里我推薦大家使用開源分布式事務處理組件Seata的改良方案，它完美的解決了雪花算法時鐘敏感的問題，并且代碼簡潔，可以非常方便集成在你項目中。

下面讓我們來分析一下Seata改進后的方案。

Seata的優化方案

在原版雪花算法中，分布式ID的格式是這樣的。

圖片

雪花算法主要是利用時間的單調遞增特性，并且與操作系統的時間戳時刻綁定，一旦出現時間“回退”，則打破了時間  “單調遞增”這個前提，所以可能會出現重復。

而在改良后的Seata方案中，其ID格式是這樣的。

圖片

通過觀察Seata代碼，我們可以發現它只是簡單地調整了節點ID和時間戳的位置。那么這樣做的目的是什么呢？

答案是通過這種方式解除了算法與操作系統時間戳的強綁定關系。生成器僅在初始化時獲取系統時間戳作為初始時間戳，之后不再與系統時間戳同步。生成器的遞增僅由序列號的遞增驅動。例如，當序列號的當前值達到4095時，下一個請求到來時，序列號將溢出12位空間并重新歸零，同時溢出的進位將加到時間戳上，使時間戳+1。因此，時間戳和序列號實際上可以視為一個整體。

這樣，時間戳和序列號在內存中是連續存儲的，可以使用一個AtomicLong來同時保存它們。下面是相關核心代碼的示例：

/**
 * timestamp and sequence mix in one Long
 * highest 11 bit: not used
 * middle  41 bit: timestamp
 * lowest  12 bit: sequence
 */
private AtomicLong timestampAndSequence;

/**
 * The number of bits occupied by sequence
 */
private final int sequenceBits = 12;

/**
 * init first timestamp and sequence immediately
 */
private void initTimestampAndSequence() {
  long timestamp = getNewestTimestamp();
  long timestampWithSequence = timestamp << sequenceBits;
  this.timestampAndSequence = new AtomicLong(timestampWithSequence);
}

代碼解釋：

1. 在初始化方法中，獲取當前時間戳getNewestTimestamp()以后將其左移12位，留出了序列號的位置。

2. 而Long類型轉化成二進制以后是64位，前11位不使用，中間的41位代表時間戳，后面的12位代表序列號。

最高11位在初始化時就直接確定好，之后不再變化，核心代碼如下：

/**
 * init workerId
 * @param workerId if null, then auto generate one
 */
private void initWorkerId(Long workerId) {
  if (workerId == null) {
    workerId = generateWorkerId();
  }
  if (workerId > maxWorkerId || workerId < 0) {
    String message = String.format("worker Id can't be greater than %d or less than 0", maxWorkerId);
    throw new IllegalArgumentException(message);
  }
  this.workerId = workerId << (timestampBits + sequenceBits);
}

/**
 * auto generate workerId, try using mac first, if failed, then randomly generate one
 * @return workerId
 */
private long generateWorkerId() {
  try {
    return generateWorkerIdBaseOnMac();
  } catch (Exception e) {
    return generateRandomWorkerId();
  }
}


/**
 * use lowest 10 bit of available MAC as workerId
 * @return workerId
 * @throws Exception when there is no available mac found
 */
private long generateWorkerIdBaseOnMac() throws Exception {
  Enumeration<NetworkInterface> all = NetworkInterface.getNetworkInterfaces();
  while (all.hasMoreElements()) {
    NetworkInterface networkInterface = all.nextElement();
    boolean loopBack = networkInterface.isLoopback();
    boolean isVirtual = networkInterface.isVirtual();
    if (loopBack || isVirtual) {
      continue;
    }
    byte[] mac = networkInterface.getHardwareAddress();
    return ((mac[4] & 0B11) << 8) | (mac[5] & 0xFF);
  }
  throw new RuntimeException("no available mac found");
}

代碼解讀：

1. 算法規定了節點ID最長為10位，2的10次方是1024，所以可以服務1024臺機器，體現在數字上的取值范圍是為[0,1023)；
2. 在原版雪花算法中，如果未指定節點ID，會截取本地IPv4地址的低10位作為節點ID，這樣在生成實踐中如果出現IP的第4個字節和第3個字節的低2位一樣就會重復。如：192.168.4.10 和 192.168.8.10
3. 新版算法generateWorkerIdBaseOnMac()是從從本機網卡的MAC地址截取低10位，最后通過(mac[4] & 0B11) << 8) | (mac[5] & 0xFF)保證其取值范圍最大值為1023，算法有點難懂，分步解釋：mac[4] 和mac[5] 是無符號8位整數的變量，其取值范圍是[0,255)(mac[4] & 0B11) 運算會保留 mac[4] 的最后兩位00,01,10,11，也就是取值范圍為 0 到 3。(mac[4] & 0B11) << 8。左移 8 位相當于乘以 256，所以結果的取值范圍是 0 到 3 * 256 = 0 到 768。(mac[5] & 0xFF) 最大值就是0xFF， 也就是取值范圍是 0 到 255所以最后結果的取值范圍是從 0 到 768 | 255 = 1023。
4. 計算出節點ID以后，將其左移，this.workerId = workerId << (timestampBits + sequenceBits)，這樣就完成了算法ID的組裝。

最后看看生成ID的算法

private final int timestampBits = 41;
private final int sequenceBits = 12;
private final long timestampAndSequenceMask = ~(-1L << (timestampBits + sequenceBits));
public long nextId() {
   // 獲得遞增后的時間戳和序列號
   long next = timestampAndSequence.incrementAndGet();
   // 截取低53位
   long timestampWithSequence = next & timestampAndSequenceMask;
   // 跟先前保存好的高11位進行一個或的位運算
   return workerId | timestampWithSequence;
}

看完Seata雪花算法的實現邏輯，你覺得怎么樣呢？反正我只會直呼 ”臥槽，牛皮“~

通過對Seata改良算法代碼的解讀，可以知道，算法生成器僅在啟動時獲取了一次系統時鐘，可以說是弱依賴于操作系統時鐘，這樣在運行期間，生成器不再受時鐘回撥的影響。

同時由于序列號有12位，最大取值范圍是[0,4095]。

如果在當前毫秒下序列號生成到了 4096 ，這個時候序列號回重新歸0，同時讓時間戳+1，也就是 "借用"下一個時間戳的序列號空間，這種超前消費會不會導致生成器內的時間戳大大超前于系統的時間戳，從而導致重啟時ID重復呢？

理論上有，實際上并不會。因為要達到這個效果，也就意味著生成器的QPS得持續穩定在4096/ms，約400W/s之上，這得什么場景才能有這樣的流量呢？(12306在2020年春運期間高峰QPS約為170W/s，2020年雙11淘寶TPS為58.3W/s) 就算有了，瓶頸一定不在生成器這里。

通過對Seata改良算法代碼的解讀，我們可以了解到算法生成器僅在啟動時獲取一次系統時鐘，因此它在運行期間對操作系統時鐘的依賴相對較弱。這意味著生成器不會受到時鐘回撥的影響。

此外，根據序列號的位數為12位，其取值范圍為[0, 4095]。

如果在當前毫秒內序列號生成到了4096，這時序列號會重新歸0，并且時間戳會增加1，即"借用"下一個時間戳的序列號空間。這種超前消費是否會導致生成器內部的時間戳大大超前于系統的時間戳，從而導致在重啟時出現重復的ID呢？

理論上來說，這種情況是有可能發生的。然而，在實際情況下并不會出現這種問題。因為要達到這種效果，也就意味著生成器的每秒請求數(QPS)需要持續穩定在4096次以上，相當于每秒處理約400萬個請求。這樣高的流量場景是非常罕見的，而且即使存在這樣的流量，天塌下來有高個子頂著，一定會是其他組件先出問題。

Seata雪花算法的 “缺陷”

經過觀察，我們可以發現一個問題：Seata改良版的算法在單節點內部確實是單調遞增的，但是在多實例部署時，它不再保證全局單調遞增。這是因為節點ID在生成的ID中占據了高位，因此節點ID較大的生成的ID一定大于節點ID較小的生成的ID，與它們的生成時間先后順序無關。

相比之下，原版雪花算法將時間戳放在高位，并且始終追隨系統時鐘，可以確保早期生成的ID小于后期生成的ID。只有當兩個節點恰好在同一時間戳生成ID時，兩個ID的大小才由節點ID決定。

從這個角度來看，新版算法是否存在問題呢？

關于這個問題，官方已經給出了結論：

新版算法的確不具備全局的單調遞增性，但這不影響我們的初衷(減少數據庫的頁分裂)。這個結論看起來有點違反直覺，但可以被證明。

現在讓我們來進一步優化和解釋這個結論。

B+樹原理

在證明之前我們需要先回顧一下數據庫頁分裂的相關知識（基于B+數索引的MySQL InnoDB引擎）。

在B+樹索引中，主鍵索引的葉子節點除了保存鍵的值之外，還保存了數據行的完整記錄。葉子節點之間以雙向鏈表的形式連接在一起。葉子節點在物理存儲上被組織為數據頁，每個數據頁最多可以存儲N條行記錄。

圖片

B+樹的特性要求左邊的節點的鍵值小于右邊節點的鍵值。如果現在要插入一條ID為25的記錄，會發生什么呢？（假設每個數據頁只能容納4條記錄）答案是會導致頁分裂，如下圖所示：

圖片

頁分裂對IO操作不友好，需要創建新的數據頁，并復制和轉移舊數據頁中的部分記錄。因此，我們應該盡量避免頁分裂的發生。

如果你想直觀地了解B+樹節點分裂的過程，建議訪問以下網站：

B+ Tree Visualization -> https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

理想的情況下，主鍵ID最好是順序遞增的(例如把主鍵設置為auto_increment)，這樣就只會在當前數據頁放滿了的時候，才需要新建下一頁，雙向鏈表永遠是順序尾部增長的，不會有中間的節點發生分裂的情況。

最糟糕的情況下，主鍵ID是隨機無序生成的(例如java中一個UUID字符串)，這種情況下，新插入的記錄會隨機分配到任何一個數據頁，如果該頁已滿，就會觸發頁分裂。

如果主鍵ID由標準版雪花算法生成，最好的情況下，是每個時間戳內只有一個節點在生成ID，這時候算法的效果等同于理想情況的順序遞增，即跟auto_increment無差。最壞的情況下，是每個時間戳內所有節點都在生成ID，這時候算法的效果接近于無序(但仍比UUID的完全無序要好得多，因為workerId只有10位決定了最多只有1024個節點)。實際生產中，算法的效果取決于業務流量，并發度越低，算法越接近理想情況。

在理想情況下，主鍵ID最好是按順序遞增的（例如使用auto_increment設置主鍵），這樣只有在當前數據頁已滿時才需要創建下一頁，雙向鏈表的增長總是在尾部進行的，不會導致中間節點的分裂。

在最糟糕的情況下，主鍵ID是隨機無序生成的（例如在Java中使用UUID字符串），這種情況下，新插入的記錄會被隨機分配到任意一個數據頁，如果該頁已滿，則觸發頁分裂。

這也是為什么不推薦使用UUID作為主鍵ID的原因，UUID會導致頻繁出現頁裂變，影響數據庫性能。

如果主鍵ID由標準版雪花算法生成，最理想的情況是每個時間戳內只有一個節點生成ID，這種情況下算法的效果與理想情況的順序遞增相同，即與auto_increment沒有區別。最糟糕的情況是每個時間戳內的所有節點都在生成ID，這種情況下算法的效果接近于無序（但仍比完全無序的UUID要好得多，因為workerId只有10位，限制了節點數量最多為1024個）。在實際生產環境中，算法的效果取決于業務流量，較低的并發度會使算法接近理想情況。

那么，Seata改良版的雪花算法又是如何呢？

Seata 改良算法會導致頻繁頁裂變嗎？

新版算法從全局角度來看，生成的ID是無序的。然而，對于每個節點而言，它所生成的ID序列是嚴格單調遞增的。由于節點ID是有限的，因此最多可以劃分出1024個子序列，每個子序列都是單調遞增的。

對于數據庫而言，在初始階段接收到的ID可能是無序的，來自各個子序列的ID會混合在一起。假設節點ID的值是遞增的，初始階段的效果如下圖所示：

圖片

假設此時出現了一個worker1-seq2的ID，由于數據頁已經存滿，會觸發一次頁分裂，如下圖所示：

圖片

然而，分裂之后發生了一件有趣的事情。對于worker1而言，后續的seq3、seq4由于可以直接放入數據頁，不會再觸發頁分裂。而seq5只需要像順序遞增一樣，在新建的頁中進行鏈接。值得注意的是，由于worker1的后續ID都比worker2的ID小，它們不會被分配到worker2及其之后的節點，因此不會導致后續節點的頁分裂。同樣地，由于是單調遞增，它們也不會被分配到worker1當前節點的前面，因此不會導致前面節點的頁分裂。

在這里，我們稱具有這種性質的子序列達到了穩態，意味著該子序列已經"穩定"下來，其后續增長只會發生在子序列的尾部，而不會引起其他節點的頁分裂。同樣的情況也可以推廣到其他子序列上。無論初始階段數據庫接收到的ID有多么混亂，在有限次頁分裂之后，雙向鏈表總能達到這樣一個穩定的終態：

圖片

到達終態后，后續的ID只會在該ID所屬的子序列上進行順序增長，而不會造成頁分裂。該狀態下的順序增長與auto_increment的順序增長的區別是，前者有1024個增長位點(各個子序列的尾部)，后者只有尾部一個。

小結

綜上所述，改進版的雪花算法雖然不具備全局單調遞增的特性，但在同一節點下能夠保持單調遞增。此外，經過幾次數據頁分裂后，它會達到一個穩定狀態，不會頻繁觸發數據庫的頁分裂。同時，該算法仍然滿足高性能和全局唯一的要求。因此，完全可以將改進版的雪花算法引入到項目中使用。

然而，需要注意的是，在實際業務系統中，最好將此算法應用于那些需要長期保存數據的場景，而對于需要頻繁刪除的表則不太適用。

這是因為該算法利用前期的頁分裂，逐漸將不同子序列分離，從而實現算法的收斂到穩定狀態。如果頻繁刪除數據，會觸發數據庫的頁合并操作，這會阻礙數據的收斂。在極端情況下，剛剛分離的數據可能會立即發生頁合并，導致數據無法保持穩定狀態。因此，在使用改進版的雪花算法時需要謹慎考慮業務需求和數據操作的頻率。

DailyMart集成全局ID算法

DailyMart項目中涉及到多個場景需要使用全局唯一ID，因此我已經將Seata改進版的雪花算法通過自定義Starter的方式集成到了項目中。使用時只需要調用IdUtils.nextId()方法即可獲取全局唯一ID，你可以參考源代碼進行具體實現。

圖片

同時，之前的文章中提到了在使用Mybatis-Plus時，由于沒有正確配置worker-id和datacenter-id參數，導致生成的ID可能會出現重復。基于此我還在datasources公共模塊中替換了Mybatis-Plus的ID生成算法，直接使用Seata改進后的雪花算法。

以下為代碼具體實現：

public class CustomIdGenerator implements IdentifierGenerator {
    
    @Override
    public Number nextId(Object entity) {
        return IdUtils.nextId();
    }
    
}

/**
 * 替換Mybatis-plus的算法生成器
 */
@Bean
public IdentifierGenerator identifierGenerator() {
  return new CustomIdGenerator();
}