摘要：是美團(tuán)基礎(chǔ)研發(fā)平臺(tái)推出的一個(gè)分布式生成服務(wù)，名字取自德國(guó)哲學(xué)家數(shù)學(xué)家萊布尼茨的一句話(huà)具備高可靠低延遲全局唯一等特點(diǎn)。目前已經(jīng)廣泛應(yīng)用于美團(tuán)金融美團(tuán)外賣(mài)美團(tuán)酒旅等多個(gè)部門(mén)。具體的技術(shù)細(xì)節(jié)，可參考此前美團(tuán)技術(shù)博客的一篇文章美團(tuán)分布式生成服務(wù)。

Leaf是美團(tuán)基礎(chǔ)研發(fā)平臺(tái)推出的一個(gè)分布式ID生成服務(wù)，名字取自德國(guó)哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話(huà)：“There are no two identical leaves in the world.”Leaf具備高可靠、低延遲、全局唯一等特點(diǎn)。目前已經(jīng)廣泛應(yīng)用于美團(tuán)金融、美團(tuán)外賣(mài)、美團(tuán)酒旅等多個(gè)部門(mén)。具體的技術(shù)細(xì)節(jié)，可參考此前美團(tuán)技術(shù)博客的一篇文章：《Leaf美團(tuán)分布式ID生成服務(wù)》。近日，Leaf項(xiàng)目已經(jīng)在Github上開(kāi)源：https://github.com/Meituan-Dianping/Leaf，希望能和更多的技術(shù)同行一起交流、共建。

Leaf在設(shè)計(jì)之初就秉承著幾點(diǎn)要求：

全局唯一，絕對(duì)不會(huì)出現(xiàn)重復(fù)的ID，且ID整體趨勢(shì)遞增。

高可用，服務(wù)完全基于分布式架構(gòu)，即使MySQL宕機(jī)，也能容忍一段時(shí)間的數(shù)據(jù)庫(kù)不可用。

高并發(fā)低延時(shí)，在CentOS 4C8G的虛擬機(jī)上，遠(yuǎn)程調(diào)用QPS可達(dá)5W+，TP99在1ms內(nèi)。

接入簡(jiǎn)單，直接通過(guò)公司RPC服務(wù)或者HTTP調(diào)用即可接入。

Leaf第一個(gè)版本采用了預(yù)分發(fā)的方式生成ID，即可以在DB之上掛N個(gè)Server，每個(gè)Server啟動(dòng)時(shí)，都會(huì)去DB拿固定長(zhǎng)度的ID List。這樣就做到了完全基于分布式的架構(gòu)，同時(shí)因?yàn)镮D是由內(nèi)存分發(fā)，所以也可以做到很高效。接下來(lái)是數(shù)據(jù)持久化問(wèn)題，Leaf每次去DB拿固定長(zhǎng)度的ID List，然后把最大的ID持久化下來(lái)，也就是并非每個(gè)ID都做持久化，僅僅持久化一批ID中最大的那一個(gè)。這個(gè)方式有點(diǎn)像游戲里的定期存檔功能，只不過(guò)存檔的是未來(lái)某個(gè)時(shí)間下發(fā)給用戶(hù)的ID，這樣極大地減輕了DB持久化的壓力。

整個(gè)服務(wù)的具體處理過(guò)程如下：

Leaf Server 1：從DB加載號(hào)段[1，1000]。

Leaf Server 2：從DB加載號(hào)段[1001，2000]。

Leaf Server 3：從DB加載號(hào)段[2001，3000]。

用戶(hù)通過(guò)Round-robin的方式調(diào)用Leaf Server的各個(gè)服務(wù)，所以某一個(gè)Client獲取到的ID序列可能是：1，1001，2001，2，1002，2002......也可能是：1，2，1001，2001，2002，2003，3，4......當(dāng)某個(gè)Leaf Server號(hào)段用完之后，下一次請(qǐng)求就會(huì)從DB中加載新的號(hào)段，這樣保證了每次加載的號(hào)段是遞增的。

Leaf數(shù)據(jù)庫(kù)中的號(hào)段表格式如下：

+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+

Leaf Server加載號(hào)段的SQL語(yǔ)句如下：

Begin
UPDATE table SET max_id=max_id+step WHERE biz_tag=xxx
SELECT tag, max_id, step FROM table WHERE biz_tag=xxx
Commit

整體上，V1版本實(shí)現(xiàn)比較簡(jiǎn)單，主要是為了盡快解決業(yè)務(wù)層DB壓力的問(wèn)題，而快速迭代出的一個(gè)版本。因而在生產(chǎn)環(huán)境中，也發(fā)現(xiàn)了些問(wèn)題。比如：

在更新DB的時(shí)候會(huì)出現(xiàn)耗時(shí)尖刺，系統(tǒng)最大耗時(shí)取決于更新DB號(hào)段的時(shí)間。

當(dāng)更新DB號(hào)段的時(shí)候，如果DB宕機(jī)或者發(fā)生主從切換，會(huì)導(dǎo)致一段時(shí)間的服務(wù)不可用。

為了解決這兩個(gè)問(wèn)題，Leaf采用了異步更新的策略，同時(shí)通過(guò)雙Buffer的方式，保證無(wú)論何時(shí)DB出現(xiàn)問(wèn)題，都能有一個(gè)Buffer的號(hào)段可以正常對(duì)外提供服務(wù)，只要DB在一個(gè)Buffer的下發(fā)的周期內(nèi)恢復(fù)，就不會(huì)影響整個(gè)Leaf的可用性。

這個(gè)版本代碼在線(xiàn)上穩(wěn)定運(yùn)行了半年左右，Leaf又遇到了新的問(wèn)題：

號(hào)段長(zhǎng)度始終是固定的，假如Leaf本來(lái)能在DB不可用的情況下，維持10分鐘正常工作，那么如果流量增加10倍就只能維持1分鐘正常工作了。

號(hào)段長(zhǎng)度設(shè)置的過(guò)長(zhǎng)，導(dǎo)致緩存中的號(hào)段遲遲消耗不完，進(jìn)而導(dǎo)致更新DB的新號(hào)段與前一次下發(fā)的號(hào)段ID跨度過(guò)大。

假設(shè)服務(wù)QPS為Q，號(hào)段長(zhǎng)度為L(zhǎng)，號(hào)段更新周期為T(mén)，那么Q * T = L。最開(kāi)始L長(zhǎng)度是固定的，導(dǎo)致隨著Q的增長(zhǎng)，T會(huì)越來(lái)越小。但是Leaf本質(zhì)的需求是希望T是固定的。那么如果L可以和Q正相關(guān)的話(huà)，T就可以趨近一個(gè)定值了。所以L(fǎng)eaf每次更新號(hào)段的時(shí)候，根據(jù)上一次更新號(hào)段的周期T和號(hào)段長(zhǎng)度step，來(lái)決定下一次的號(hào)段長(zhǎng)度nextStep：

T < 15min，nextStep = step * 2

15min < T < 30min，nextStep = step

T > 30min，nextStep = step / 2

至此，滿(mǎn)足了號(hào)段消耗穩(wěn)定趨于某個(gè)時(shí)間區(qū)間的需求。當(dāng)然，面對(duì)瞬時(shí)流量幾十、幾百倍的暴增，該種方案仍不能滿(mǎn)足可以容忍數(shù)據(jù)庫(kù)在一段時(shí)間不可用、系統(tǒng)仍能穩(wěn)定運(yùn)行的需求。因?yàn)楸举|(zhì)上來(lái)講，Leaf雖然在DB層做了些容錯(cuò)方案，但是號(hào)段方式的ID下發(fā)，最終還是需要強(qiáng)依賴(lài)DB。

在MySQL這一層，Leaf目前采取了半同步的方式同步數(shù)據(jù)，通過(guò)公司DB中間件Zebra加MHA做的主從切換。未來(lái)追求完全的強(qiáng)一致，會(huì)考慮切換到MySQL Group Replication。

現(xiàn)階段由于公司數(shù)據(jù)庫(kù)強(qiáng)一致的特性還在演進(jìn)中，Leaf采用了一個(gè)臨時(shí)方案來(lái)保證機(jī)房斷網(wǎng)場(chǎng)景下的數(shù)據(jù)一致性：

多機(jī)房部署數(shù)據(jù)庫(kù)，每個(gè)機(jī)房一個(gè)實(shí)例，保證都是跨機(jī)房同步數(shù)據(jù)。

半同步超時(shí)時(shí)間設(shè)置到無(wú)限大，防止半同步方式退化為異步復(fù)制。

針對(duì)服務(wù)自身的監(jiān)控，Leaf提供了Web層的內(nèi)存數(shù)據(jù)映射界面，可以實(shí)時(shí)看到所有號(hào)段的下發(fā)狀態(tài)。比如每個(gè)號(hào)段雙buffer的使用情況，當(dāng)前ID下發(fā)到了哪個(gè)位置等信息都可以在Web界面上查看。

Snowflake，Twitter開(kāi)源的一種分布式ID生成算法?；?4位數(shù)實(shí)現(xiàn)，下圖為Snowflake算法的ID構(gòu)成圖。

第1位置為0。

第2-42位是相對(duì)時(shí)間戳，通過(guò)當(dāng)前時(shí)間戳減去一個(gè)固定的歷史時(shí)間戳生成。

第43-52位是機(jī)器號(hào)workerID，每個(gè)Server的機(jī)器ID不同。

第53-64位是自增ID。

這樣通過(guò)時(shí)間+機(jī)器號(hào)+自增ID的組合來(lái)實(shí)現(xiàn)了完全分布式的ID下發(fā)。

在這里，Leaf提供了Java版本的實(shí)現(xiàn)，同時(shí)對(duì)Zookeeper生成機(jī)器號(hào)做了弱依賴(lài)處理，即使Zookeeper有問(wèn)題，也不會(huì)影響服務(wù)。Leaf在第一次從Zookeeper拿取workerID后，會(huì)在本機(jī)文件系統(tǒng)上緩存一個(gè)workerID文件。即使ZooKeeper出現(xiàn)問(wèn)題，同時(shí)恰好機(jī)器也在重啟，也能保證服務(wù)的正常運(yùn)行。這樣做到了對(duì)第三方組件的弱依賴(lài)，一定程度上提高了SLA。

號(hào)段加載優(yōu)化：Leaf目前重啟后的第一次請(qǐng)求還是會(huì)同步加載MySQL，之所以這么做而非服務(wù)初始化加載號(hào)段的原因，主要是MySQL中的Leaf Key并非一定都被這個(gè)Leaf服務(wù)節(jié)點(diǎn)所加載，如果每個(gè)Leaf節(jié)點(diǎn)都在初始化加載所有的Leaf Key會(huì)導(dǎo)致號(hào)段的大量浪費(fèi)。因此，未來(lái)會(huì)在Leaf服務(wù)Shutdown時(shí)，備份這個(gè)服務(wù)節(jié)點(diǎn)近一天使用過(guò)的Leaf Key列表，這樣重啟后會(huì)預(yù)先從MySQL加載Key List中的號(hào)段。

單調(diào)遞增：簡(jiǎn)易的方式，是只要保證同一時(shí)間、同一個(gè)Leaf Key都從一個(gè)Leaf服務(wù)節(jié)點(diǎn)獲取ID，即可保證遞增。需要注意的問(wèn)題是Leaf服務(wù)節(jié)點(diǎn)切換時(shí)，舊Leaf 服務(wù)用過(guò)的號(hào)段需要廢棄。路由邏輯，可采用主備的模型或者每個(gè)Leaf Key 配置路由表的方式來(lái)實(shí)現(xiàn)。

分布式ID生成的方案有很多種，Leaf開(kāi)源版本提供了兩種ID的生成方式：

號(hào)段模式：低位趨勢(shì)增長(zhǎng)，較少的ID號(hào)段浪費(fèi)，能夠容忍MySQL的短時(shí)間不可用。

Snowflake模式：完全分布式，ID有語(yǔ)義。

讀者可以按需選擇適合自身業(yè)務(wù)場(chǎng)景的ID下發(fā)方式。希望美團(tuán)的方案能給予大家一些幫助，同時(shí)也希望各位能夠一起交流、共建。

Leaf項(xiàng)目Github地址：https://github.com/Meituan-Dianping/Leaf 。

如有任何疑問(wèn)和問(wèn)題，歡迎提交至Github issues。