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

圖片

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是根據(jù)虛擬機名稱生成，dataCenterId是根據(jù)mac地址生成，這2個東西部署在Docker環(huán)境中就很有可能重復。

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

概述

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

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

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

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

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

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

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

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

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

Seata的優(yōu)化方案

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

圖片

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

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

圖片

通過觀察Seata代碼，我們可以發(fā)現(xiàn)它只是簡單地調(diào)整了節(jié)點ID和時間戳的位置。那么這樣做的目的是什么呢？

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

這樣，時間戳和序列號在內(nèi)存中是連續(xù)存儲的，可以使用一個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類型轉(zhuǎn)化成二進制以后是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. 算法規(guī)定了節(jié)點ID最長為10位，2的10次方是1024，所以可以服務1024臺機器，體現(xiàn)在數(shù)字上的取值范圍是為[0,1023)；
2. 在原版雪花算法中，如果未指定節(jié)點ID，會截取本地IPv4地址的低10位作為節(jié)點ID，這樣在生成實踐中如果出現(xiàn)IP的第4個字節(jié)和第3個字節(jié)的低2位一樣就會重復。如：192.168.4.10 和 192.168.8.10
3. 新版算法generateWorkerIdBaseOnMac()是從從本機網(wǎng)卡的MAC地址截取低10位，最后通過(mac[4] & 0B11) << 8) | (mac[5] & 0xFF)保證其取值范圍最大值為1023，算法有點難懂，分步解釋：mac[4] 和mac[5] 是無符號8位整數(shù)的變量，其取值范圍是[0,255)(mac[4] & 0B11) 運算會保留 mac[4] 的最后兩位00,01,10,11，也就是取值范圍為 0 到 3。(mac[4] & 0B11) << 8。左移 8 位相當于乘以 256，所以結(jié)果的取值范圍是 0 到 3 * 256 = 0 到 768。(mac[5] & 0xFF) 最大值就是0xFF， 也就是取值范圍是 0 到 255所以最后結(jié)果的取值范圍是從 0 到 768 | 255 = 1023。
4. 計算出節(jié)點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雪花算法的實現(xiàn)邏輯，你覺得怎么樣呢？反正我只會直呼 ”臥槽，牛皮“~

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

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

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

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

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

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

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

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

Seata雪花算法的 “缺陷”

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

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

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

關于這個問題，官方已經(jīng)給出了結(jié)論：

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

現(xiàn)在讓我們來進一步優(yōu)化和解釋這個結(jié)論。

B+樹原理

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

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

圖片

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

圖片

頁分裂對IO操作不友好，需要創(chuàng)建新的數(shù)據(jù)頁，并復制和轉(zhuǎn)移舊數(shù)據(jù)頁中的部分記錄。因此，我們應該盡量避免頁分裂的發(fā)生。

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

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

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

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

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

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

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

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

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

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

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

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

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

圖片

假設此時出現(xiàn)了一個worker1-seq2的ID，由于數(shù)據(jù)頁已經(jīng)存滿，會觸發(fā)一次頁分裂，如下圖所示：

圖片

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

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

圖片

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

小結(jié)

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

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

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

DailyMart集成全局ID算法

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

圖片

同時，之前的文章中提到了在使用Mybatis-Plus時，由于沒有正確配置worker-id和datacenter-id參數(shù)，導致生成的ID可能會出現(xiàn)重復?；诖宋疫€在datasources公共模塊中替換了Mybatis-Plus的ID生成算法，直接使用Seata改進后的雪花算法。

以下為代碼具體實現(xiàn)：

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

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