大家好，我是樹哥。

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

• UUID
• 類雪花算法
• 數(shù)據(jù)庫自增主鍵
• Redis 原子自增

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

今天我們就來學(xué)習(xí)一下 Leaf 的設(shè)計思路，看看大廠是如何設(shè)計大型中間件的，這有利于進一步提升我們自己的系統(tǒng)設(shè)計能力。

數(shù)據(jù)庫自增主鍵

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

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

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

在這樣的業(yè)務(wù)背景下，美團開源的 Leaf 做了進一步優(yōu)化，在數(shù)據(jù)庫與業(yè)務(wù)服務(wù)之間加入了中間層。之前業(yè)務(wù)系統(tǒng)直接去請求數(shù)據(jù)庫，現(xiàn)在業(yè)務(wù)系統(tǒng)不直接請求數(shù)據(jù)庫，而是去請求 Leaf 中間層，之后由 Leaf 中間層去數(shù)據(jù)庫取數(shù)據(jù)。

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

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

如上圖所示，綠色的業(yè)務(wù)系統(tǒng)請求 Leaf 發(fā)號服務(wù)的時候，帶上業(yè)務(wù)編碼標(biāo)記。隨后 Leaf 發(fā)號服務(wù)根據(jù)業(yè)務(wù)編號類型返回下一個唯一 ID。Leaf 發(fā)號服務(wù)每次向數(shù)據(jù)庫獲取 1000 個 ID，數(shù)據(jù)庫往表中插入一條數(shù)據(jù)，表示這 1000 個 ID 分給了某個業(yè)務(wù)。

通過這種方式，原本業(yè)務(wù)系統(tǒng)獲取 1000 個 ID 需要進行 1000 次數(shù)據(jù)請求，現(xiàn)在可能只需要 1 次就夠了，極大地提高了運行效率。 此外，業(yè)務(wù)系統(tǒng)獲取 ID 的時候都是從內(nèi)存獲取，不需要請求第三方，極大的提高了響應(yīng)速度。

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

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

雙 Buffer + 預(yù)加載 - 圖片來自美團技術(shù)團隊博客

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

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

為了解決這個問題，其采用了動態(tài)號碼段的思路，即：根據(jù)上次號碼段的長度及分發(fā)耗時，計算出下次應(yīng)發(fā)的號碼段長度。對于號碼長度的計算規(guī)則如下：

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

簡單地說，如果耗時低于 15 分鐘，那么下次應(yīng)發(fā)的號碼段長度變?yōu)樵械?2 倍。如果在 15 - 30 分鐘之間，那么就保持應(yīng)發(fā)號碼段長度不變。如果耗時大于 30 分鐘， 那么下次應(yīng)發(fā)號碼段長度減半。

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

即使 Leaf 做了如此多的優(yōu)化，但在更惡劣的環(huán)境下，仍然可能發(fā)生系統(tǒng)不可以的情況，例如：

• 數(shù)據(jù)庫主庫突然宕機，短時間內(nèi)無法恢復(fù)，此時系統(tǒng)不可用。
• 業(yè)務(wù)流量突增幾十倍，即使有批量分發(fā)，但數(shù)據(jù)庫單機無法支撐如此高的寫請求。
• 等等。

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

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

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

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

類雪花算法

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

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

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

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

總結(jié)

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

• 號碼段模式。基于數(shù)據(jù)庫自增組件，ID 從低位趨勢增長，能夠忍受 MySQL 短時間不可用。
• 類雪花算法模式?；谘┗ㄋ惴ǎ鉀Q了時間回撥以及海量機器的 workId 維護問題。

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

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

好了，這就是今天分享的全部內(nèi)容了。