大家好，我是樹哥。

之前我們有聊過「如何設計一個分布式 ID 發號器」，其中有講過 4 種解決方案，分別是：

• UUID
• 類雪花算法
• 數據庫自增主鍵
• Redis 原子自增

美團以第 2、3 種解決方案為基礎，開發出了分布式 ID 生成方案 Leaf，并將其開源。我們可以在 GitHub 上獲取到該項目的源碼，以及相關的文檔說明，項目地址：Meituan-Dianping/Leaf: Distributed ID Generate Service。

今天我們就來學習一下 Leaf 的設計思路，看看大廠是如何設計大型中間件的，這有利于進一步提升我們自己的系統設計能力。

數據庫自增主鍵

在「如何設計一個分布式 ID 發號器？」文章里，我們說到可以基于數據庫自增主鍵設計發號器。但我們也提到其存在如下兩個問題：

• 只能依賴堆機器提高性能。當請求再次增多時，我們只能無限堆機器，這貌似是一種物理防御一樣。
• 水平擴展困難。當我們需要增加一臺機器時，其處理過程非常麻煩。首先，我們需要先把新增的服務器部署好，設置新的步長，起始值要設置一個不可能達到的值。當把新增的服務器部署好之后，再一臺臺處理舊的服務器，這個過程真的非常痛苦，可以說是人肉運維了。

簡單地說，就是基于數據庫主鍵自增的方式，其發號效率受限于單臺物理機器。在低 QPS 的情況下還可以支持，但在高 QPS 的時候就支持不了了。即使可以通過設計步長的方式來堆機器，但是其運維成本也非常高。

在這樣的業務背景下，美團開源的 Leaf 做了進一步優化，在數據庫與業務服務之間加入了中間層。之前業務系統直接去請求數據庫，現在業務系統不直接請求數據庫，而是去請求 Leaf 中間層，之后由 Leaf 中間層去數據庫取數據。

Leaf 中間層每次去數據庫獲取 ID 的時候，一次性獲取一批 ID 號碼段，而不是只獲取一個 ID。 整個服務的具體處理流程如下所示。

Leaf Segment 處理流程 - 圖片來自美團技術團隊博客

如上圖所示，綠色的業務系統請求 Leaf 發號服務的時候，帶上業務編碼標記。隨后 Leaf 發號服務根據業務編號類型返回下一個唯一 ID。Leaf 發號服務每次向數據庫獲取 1000 個 ID，數據庫往表中插入一條數據，表示這 1000 個 ID 分給了某個業務。

通過這種方式，原本業務系統獲取 1000 個 ID 需要進行 1000 次數據請求，現在可能只需要 1 次就夠了，極大地提高了運行效率。 此外，業務系統獲取 ID 的時候都是從內存獲取，不需要請求第三方，極大的提高了響應速度。

上述方式雖然解決了數據庫層的壓力問題，但也存在一些問題，例如：在 ID 號碼段發完時，這時候需要去進行數據庫請求，這次請求的耗時就會突增，系統監控上就會出現耗時尖刺。

為了解決這個問題，美團 Leaf 采用了「雙 Buffer + 預加載」的策略，即在內存中維護兩個 ID 段，并在上一個 ID 段使用達到 10% 的時候去預加載。這其實有點像我們 App 上加載瀑布流的預加載，思路是一樣的。其設計思路如下圖所示。

雙 Buffer + 預加載 - 圖片來自美團技術團隊博客

通過預加載的方式，Leaf 解決了尖刺的問題，并且提供了一定程度的數據庫宕機高可用。 如果數據庫宕機，Leaf 服務還可以提供一段時間的服務，只要其在短時間內可以恢復。

按照官方博客種的說法，這套方案再上線半年之后又遇到了問題 —— 發號 ID 段是固定的，但流量不是固定的，如果流量增加 10 倍，就會發現維持的時間很短，這樣仍然有可能導致數據庫壓力較大。

為了解決這個問題，其采用了動態號碼段的思路，即：根據上次號碼段的長度及分發耗時，計算出下次應發的號碼段長度。對于號碼長度的計算規則如下：

• T < 15min，nextStep = step * 2
• 15min < T < 30min，nextStep = step
• T > 30min，nextStep = step / 2

簡單地說，如果耗時低于 15 分鐘，那么下次應發的號碼段長度變為原有的 2 倍。如果在 15 - 30 分鐘之間，那么就保持應發號碼段長度不變。如果耗時大于 30 分鐘， 那么下次應發號碼段長度減半。

這種設計思路，其實有點像 Hotspot 虛擬機獲取鎖時的自適應自旋，或許我們可以稱它為：自適應長度。

即使 Leaf 做了如此多的優化，但在更惡劣的環境下，仍然可能發生系統不可以的情況，例如：

• 數據庫主庫突然宕機，短時間內無法恢復，此時系統不可用。
• 業務流量突增幾十倍，即使有批量分發，但數據庫單機無法支撐如此高的寫請求。
• 等等。

在上面這些場景下，系統仍然無法保證高可用。究其根本，這是因為 Leaf 對數據庫是強依賴的，因此需要從數據庫層面去做高可用保障。

按照 Leaf 官方博客的思路，Leaf 目前使用了半同步的方式同步數據，并且實現了主從切換。 這就解決了主庫宕機的問題，進一步提升了高可用程度。

MySQL 半同步有點類似于 Kafka 的副本同步，需要有一個 slave 收到 binlog 之后，才能提交事務，從而保證了一定程度上的一致性，降低了號碼段重發的風險。

但由于半同步方式，并無法保證數據強一致性，因此極端情況下還是可能會有號碼段重發的風險，只是較低罷了。如果需要保證完全的強一致性，那么需要考慮使用 MySQL 的 Group Replication 特性。但由于美團內部的數據庫強一致性特性還在迭代中，因此 Leaf 也未實現數據強一致性。

類雪花算法

在「如何設計一個分布式 ID 發號器？」文章里，我們說到雪花算法是一個非常好的分布式 ID 生成算法。但其存在一個缺陷 —— 存在時鐘回撥的問題。美團開源的 Leaf 也實現了基于雪花算法的分布式 ID 生成功能，并且解決了時鐘回撥的問題。

美團 Leaf 引入了 zookeeper 來解決時鐘回撥問題，其大致思路為：每個 Leaf 運行時定時向 zk 上報時間戳。每次 Leaf 服務啟動時，先校驗本機時間與上次發 ID 的時間，再校驗與 zk 上所有節點的平均時間戳。如果任何一個階段有異常，那么就啟動失敗報警。

這個解決方案還是比較好理解的，就是對比上次發 ID 的時間，還有其他機器的平均時間。除了時間回撥的問題，當機器數量變多的時候，雪花算法中的 workerId 也不是很好維護。

因此，Leaf 也用 zookeeper 作為中間件，以每個服務器的 IP + Port 作為 key 去注冊一個節點，獲取一個 int 類型的節點作為 workerId。

總結

美團開源的 Leaf 提供了兩種 ID 生成方式：

• 號碼段模式。基于數據庫自增組件，ID 從低位趨勢增長，能夠忍受 MySQL 短時間不可用。
• 類雪花算法模式。基于雪花算法，解決了時間回撥以及海量機器的 workId 維護問題。

對于號碼段模式而言，其在傳統的自增 ID 基礎上，增加了 Proxy 模式，提出號碼段模式。接著，又采用「雙 Buffer + 預加載」的方式解決尖刺的問題。再之，為了解決流量暴增的問題，采用了自適應號碼段長度的優化思路。最后，在數據庫高可用上，使用 MySQL 半同步復制 + 主從切換，從一定程度上保障了高可用。

對于類雪花算法模式而言，其引入了 zookeeper 作為海量機器的 workerId 生成方法。其次，還通過「本地存儲時間戳 + 定時上報時間戳」的方式，解決了時間戳的問題。

好了，這就是今天分享的全部內容了。