Leaf-分布式ID生成系統(tǒng)

本文摘錄于 https://tech.meituan.com/2017/04/21/mt-leaf.html

成都創(chuàng)新互聯(lián)是一家專業(yè)提供高安企業(yè)網(wǎng)站建設(shè),專注與做網(wǎng)站、網(wǎng)站設(shè)計、H5高端網(wǎng)站建設(shè)、小程序制作等業(yè)務(wù)。10年已為高安眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。

2017年04月21日作者: 照東文章鏈接

業(yè)務(wù)系統(tǒng)對生成全局唯一ID的要求有哪些呢？

全局唯一性：不能出現(xiàn)重復(fù)的ID號，這是最基本的要求。

趨勢遞增：主鍵的選擇應(yīng)該盡量使用有序的主鍵保證寫入性能。

單調(diào)遞增：保證下一個ID一定大于上一個ID，例如事務(wù)版本號、IM增量消息、排序等特殊需求。

信息安全：如果ID是連續(xù)的，容易被惡意用戶扒取，所以在一些應(yīng)用場景下，會需要ID無規(guī)則、不規(guī)則。

ID生成系統(tǒng)應(yīng)該做到如下幾點：

平均延遲和TP999延遲都要盡可能低；

可用性5個9；

高QPS。

幾種ID總結(jié)：

一.UUID

UUID(Universally Unique Identifier)的標(biāo)準(zhǔn)型式包含32個16進(jìn)制數(shù)字，以連字號分為五段，形式為8-4-4-4-12的36個字符。

優(yōu)點：

性能非常高：本地生成，沒有網(wǎng)絡(luò)消耗。

缺點：

不易于存儲：UUID太長，16字節(jié)128位，通常以36長度的字符串表示，很多場景不適用。

信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。

ID作為主鍵時在特定的環(huán)境會存在一些問題，比如做DB主鍵的場景下，UUID就非常不適用：

① MySQL官方有明確的建議主鍵要盡量越短越好[4]，36個字符長度的UUID不符合要求。

② 對MySQL索引不利：如果作為數(shù)據(jù)庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動，嚴(yán)重影響性能。

二.類snowflake方案

這種方案大致來說是一種以劃分命名空間（UUID也算，由于比較常見，所以單獨分析）來生成ID的一種算法，這種方案把64-bit分別劃分成多段，分開來標(biāo)示機(jī)器、時間等

這種方式的優(yōu)缺點是：

優(yōu)點：

毫秒數(shù)在高位，自增序列在低位，整個ID都是趨勢遞增的。

不依賴數(shù)據(jù)庫等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的。

可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。

缺點：

強(qiáng)依賴機(jī)器時鐘，如果機(jī)器上時鐘回?fù)?，會?dǎo)致發(fā)號重復(fù)或者服務(wù)會處于不可用狀態(tài)。

三。數(shù)據(jù)庫生成

以MySQL舉例，利用給字段設(shè)置auto_increment_increment和auto_increment_offset來保證ID自增，每次業(yè)務(wù)使用下列SQL讀寫MySQL得到ID號。

begin;

REPLACE INTO Tickets64 (stub) VALUES ('a');

SELECT LAST_INSERT_ID();

commit;

這種方案的優(yōu)缺點如下：

優(yōu)點：

非常簡單，利用現(xiàn)有數(shù)據(jù)庫系統(tǒng)的功能實現(xiàn)，成本小，有DBA專業(yè)維護(hù)。

ID號單調(diào)自增，可以實現(xiàn)一些對ID有特殊要求的業(yè)務(wù)。

缺點：

強(qiáng)依賴DB，當(dāng)DB異常時整個系統(tǒng)不可用，屬于致命問題。配置主從復(fù)制可以盡可能的增加可用性，但是數(shù)據(jù)一致性在特殊情況下難以保證。主從切換時的不一致可能會導(dǎo)致重復(fù)發(fā)號。

ID發(fā)號性能瓶頸限制在單臺MySQL的讀寫性能。

對于MySQL性能問題，可用如下方案解決：在分布式系統(tǒng)中我們可以多部署幾臺機(jī)器，每臺機(jī)器設(shè)置不同的初始值，且步長和機(jī)器數(shù)相等。

比如有兩臺機(jī)器。設(shè)置步長step為2，TicketServer1的初始值為1（1，3，5，7，9，11…）、TicketServer2的初始值為2（2，4，6，8，10…）。

這是Flickr團(tuán)隊在2010年撰文介紹的一種主鍵生成策略（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。

如下所示，為了實現(xiàn)上述方案分別設(shè)置兩臺機(jī)器對應(yīng)的參數(shù)，TicketServer1從1開始發(fā)號，TicketServer2從2開始發(fā)號，兩臺機(jī)器每次發(fā)號之后都遞增2。

Leaf-分布式ID生成系統(tǒng)

image

這種架構(gòu)貌似能夠滿足性能的需求，但有以下幾個缺點：

系統(tǒng)水平擴(kuò)展比較困難，比如定義好了步長和機(jī)器臺數(shù)之后，如果要添加機(jī)器該怎么做？假設(shè)現(xiàn)在只有一臺機(jī)器發(fā)號是1,2,3,4,5（步長是1），這個時候需要擴(kuò)容機(jī)器一臺?？梢赃@樣做：把第二臺機(jī)器的初始值設(shè)置得比第一臺超過很多，比如14（假設(shè)在擴(kuò)容時間之內(nèi)第一臺不可能發(fā)到14），同時設(shè)置步長為2，那么這臺機(jī)器下發(fā)的號碼都是14以后的偶數(shù)。然后摘掉第一臺，把ID值保留為奇數(shù)，比如7，然后修改第一臺的步長為2。讓它符合我們定義的號段標(biāo)準(zhǔn)，對于這個例子來說就是讓第一臺以后只能產(chǎn)生奇數(shù)。擴(kuò)容方案看起來復(fù)雜嗎？貌似還好，現(xiàn)在想象一下如果我們線上有100臺機(jī)器，這個時候要擴(kuò)容該怎么做？簡直是噩夢。所以系統(tǒng)水平擴(kuò)展方案復(fù)雜難以實現(xiàn)。
ID沒有了單調(diào)遞增的特性，只能趨勢遞增，這個缺點對于一般業(yè)務(wù)需求不是很重要，可以容忍。
數(shù)據(jù)庫壓力還是很大，每次獲取ID都得讀寫一次數(shù)據(jù)庫，只能靠堆機(jī)器來提高性能。

Leaf這個名字是來自德國哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話： >There are no two identical leaves in the world > “世界上沒有兩片相同的樹葉”

綜合對比上述幾種方案，每種方案都不完全符合我們的要求。所以Leaf分別在上述第二種和第三種方案上做了相應(yīng)的優(yōu)化，實現(xiàn)了Leaf-segment和Leaf-snowflake方案。

Leaf-segment數(shù)據(jù)庫方案

第一種Leaf-segment方案，在使用數(shù)據(jù)庫的方案上，做了如下改變： - 原方案每次獲取ID都得讀寫一次數(shù)據(jù)庫，造成數(shù)據(jù)庫壓力大。改為利用proxy server批量獲取，每次獲取一個segment(step決定大小)號段的值。用完之后再去數(shù)據(jù)庫獲取新的號段，可以大大的減輕數(shù)據(jù)庫的壓力。 - 各個業(yè)務(wù)不同的發(fā)號需求用biz_tag字段來區(qū)分，每個biz-tag的ID獲取相互隔離，互不影響。如果以后有性能需求需要對數(shù)據(jù)庫擴(kuò)容，不需要上述描述的復(fù)雜的擴(kuò)容操作，只需要對biz_tag分庫分表就行。

數(shù)據(jù)庫表設(shè)計如下：

+-------------+--------------+------+-----+-------------------+-----------------------------+| 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 |
+-------------+--------------+------+-----+-------------------+-----------------------------+

重要字段說明：biz_tag用來區(qū)分業(yè)務(wù)，max_id表示該biz_tag目前所被分配的ID號段的最大值，step表示每次分配的號段長度。原來獲取ID每次都需要寫數(shù)據(jù)庫，現(xiàn)在只需要把step設(shè)置得足夠大，比如1000。那么只有當(dāng)1000個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。讀寫數(shù)據(jù)庫的頻率從1減小到了1/step，大致架構(gòu)如下圖所示：

Leaf-分布式ID生成系統(tǒng)

image

test_tag在第一臺Leaf機(jī)器上是1~1000的號段，當(dāng)這個號段用完時，會去加載另一個長度為step=1000的號段，假設(shè)另外兩臺號段都沒有更新，這個時候第一臺機(jī)器新加載的號段就應(yīng)該是3001~4000。同時數(shù)據(jù)庫對應(yīng)的biz_tag這條數(shù)據(jù)的max_id會從3000被更新成4000，更新號段的SQL語句如下：

BeginUPDATE table SET max_id=max_id+step WHERE biz_tag=xxxSELECT tag, max_id, step FROM table WHERE biz_tag=xxxCommit

這種模式有以下優(yōu)缺點：

優(yōu)點：

Leaf服務(wù)可以很方便的線性擴(kuò)展，性能完全能夠支撐大多數(shù)業(yè)務(wù)場景。
ID號碼是趨勢遞增的8byte的64位數(shù)字，滿足上述數(shù)據(jù)庫存儲的主鍵要求。
容災(zāi)性高：Leaf服務(wù)內(nèi)部有號段緩存，即使DB宕機(jī)，短時間內(nèi)Leaf仍能正常對外提供服務(wù)。
可以自定義max_id的大小，非常方便業(yè)務(wù)從原有的ID方式上遷移過來。

缺點：

ID號碼不夠隨機(jī)，能夠泄露發(fā)號數(shù)量的信息，不太安全。
TP999數(shù)據(jù)波動大，當(dāng)號段使用完之后還是會hang在更新數(shù)據(jù)庫的I/O上，tg999數(shù)據(jù)會出現(xiàn)偶爾的尖刺。
DB宕機(jī)會造成整個系統(tǒng)不可用。

雙buffer優(yōu)化

對于第二個缺點，Leaf-segment做了一些優(yōu)化，簡單的說就是：

Leaf 取號段的時機(jī)是在號段消耗完的時候進(jìn)行的，也就意味著號段臨界點的ID下發(fā)時間取決于下一次從DB取回號段的時間，并且在這期間進(jìn)來的請求也會因為DB號段沒有取回來，導(dǎo)致線程阻塞。如果請求DB的網(wǎng)絡(luò)和DB的性能穩(wěn)定，這種情況對系統(tǒng)的影響是不大的，但是假如取DB的時候網(wǎng)絡(luò)發(fā)生抖動，或者DB發(fā)生慢查詢就會導(dǎo)致整個系統(tǒng)的響應(yīng)時間變慢。

為此，我們希望DB取號段的過程能夠做到無阻塞，不需要在DB取號段的時候阻塞請求線程，即當(dāng)號段消費到某個點時就異步的把下一個號段加載到內(nèi)存中。而不需要等到號段用盡的時候才去更新號段。這樣做就可以很大程度上的降低系統(tǒng)的TP999指標(biāo)。詳細(xì)實現(xiàn)如下圖所示：

Leaf-分布式ID生成系統(tǒng)

image

采用雙buffer的方式，Leaf服務(wù)內(nèi)部有兩個號段緩存區(qū)segment。當(dāng)前號段已下發(fā)10%時，如果下一個號段未更新，則另啟一個更新線程去更新下一個號段。當(dāng)前號段全部下發(fā)完后，如果下個號段準(zhǔn)備好了則切換到下個號段為當(dāng)前segment接著下發(fā)，循環(huán)往復(fù)。

每個biz-tag都有消費速度監(jiān)控，通常推薦segment長度設(shè)置為服務(wù)高峰期發(fā)號QPS的600倍（10分鐘），這樣即使DB宕機(jī)，Leaf仍能持續(xù)發(fā)號10-20分鐘不受影響。
每次請求來臨時都會判斷下個號段的狀態(tài)，從而更新此號段，所以偶爾的網(wǎng)絡(luò)抖動不會影響下個號段的更新。

Leaf高可用容災(zāi)

對于第三點“DB可用性”問題，我們目前采用一主兩從的方式，同時分機(jī)房部署，Master和Slave之間采用半同步方式[5] 同步數(shù)據(jù)。同時使用公司Atlas數(shù)據(jù)庫中間件(已開源，改名為 DBProxy )做主從切換。當(dāng)然這種方案在一些情況會退化成異步模式，甚至在非常極端情況下仍然會造成數(shù)據(jù)不一致的情況，但是出現(xiàn)的概率非常小。如果你的系統(tǒng)要保證100%的數(shù)據(jù)強(qiáng)一致，可以選擇使用“類Paxos算法”實現(xiàn)的強(qiáng)一致MySQL方案，如MySQL 5.7前段時間剛剛GA的 MySQL Group Replication 。但是運維成本和精力都會相應(yīng)的增加，根據(jù)實際情況選型即可。

Leaf-分布式ID生成系統(tǒng)

image

同時Leaf服務(wù)分IDC部署，內(nèi)部的服務(wù)化框架是“MTthrift RPC”。服務(wù)調(diào)用的時候，根據(jù)負(fù)載均衡算法會優(yōu)先調(diào)用同機(jī)房的Leaf服務(wù)。在該IDC內(nèi)Leaf服務(wù)不可用的時候才會選擇其他機(jī)房的Leaf服務(wù)。同時服務(wù)治理平臺OCTO還提供了針對服務(wù)的過載保護(hù)、一鍵截流、動態(tài)流量分配等對服務(wù)的保護(hù)措施。

Leaf-segment方案可以生成趨勢遞增的ID，同時ID號是可計算的，不適用于訂單ID生成場景，比如競對在兩天中午12點分別下單，通過訂單id號相減就能大致計算出公司一天的訂單量，這個是不能忍受的。面對這一問題，我們提供了 Leaf-snowflake方案。

Leaf-分布式ID生成系統(tǒng)

image

Leaf-snowflake方案完全沿用snowflake方案的bit位設(shè)計，即是“1+41+10+12”的方式組裝ID號。對于workerID的分配，當(dāng)服務(wù)集群數(shù)量較小的情況下，完全可以手動配置。Leaf服務(wù)規(guī)模較大，動手配置成本太高。所以使用Zookeeper持久順序節(jié)點的特性自動對snowflake節(jié)點配置wokerID。Leaf-snowflake是按照下面幾個步驟啟動的：

啟動Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點）。
如果有注冊過直接取回自己的workerID（zk順序節(jié)點生成的int類型ID號），啟動服務(wù)。
如果沒有注冊過，就在該父節(jié)點下面創(chuàng)建一個持久順序節(jié)點，創(chuàng)建成功后取回順序號當(dāng)做自己的workerID號，啟動服務(wù)。

Leaf-分布式ID生成系統(tǒng)

image

弱依賴ZooKeeper

除了每次會去ZK拿數(shù)據(jù)以外，也會在本機(jī)文件系統(tǒng)上緩存一個workerID文件。當(dāng)ZooKeeper出現(xiàn)問題，恰好機(jī)器出現(xiàn)問題需要重啟時，能保證服務(wù)能夠正常啟動。這樣做到了對三方組件的弱依賴。一定程度上提高了SLA

解決時鐘問題

因為這種方案依賴時間，如果機(jī)器的時鐘發(fā)生了回?fù)埽敲淳蜁锌赡苌芍貜?fù)的ID號，需要解決時鐘回退的問題。

Leaf-分布式ID生成系統(tǒng)

image

參見上圖整個啟動流程圖，服務(wù)啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點：

若寫過，則用自身系統(tǒng)時間與leaf_forever/${self}節(jié)點記錄時間做比較，若小于leaf_forever/${self}時間則認(rèn)為機(jī)器時間發(fā)生了大步長回?fù)?，服?wù)啟動失敗并報警。
若未寫過，證明是新服務(wù)節(jié)點，直接創(chuàng)建持久節(jié)點leaf_forever/${self}并寫入自身系統(tǒng)時間，接下來綜合對比其余Leaf節(jié)點的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準(zhǔn)確，具體做法是取leaf_temporary下的所有臨時節(jié)點(所有運行中的Leaf-snowflake節(jié)點)的服務(wù)IP：Port，然后通過RPC請求得到所有節(jié)點的系統(tǒng)時間，計算sum(time)/nodeSize。
若abs( 系統(tǒng)時間-sum(time)/nodeSize ) < 閾值，認(rèn)為當(dāng)前系統(tǒng)時間準(zhǔn)確，正常啟動服務(wù)，同時寫臨時節(jié)點leaf_temporary/${self} 維持租約。
否則認(rèn)為本機(jī)系統(tǒng)時間發(fā)生大步長偏移，啟動失敗并報警。
每隔一段時間(3s)上報自身系統(tǒng)時間寫入leaf_forever/${self}。

由于強(qiáng)依賴時鐘，對時間的要求比較敏感，在機(jī)器工作時NTP同步也會造成秒級別的回退，建議可以直接關(guān)閉NTP同步。要么在時鐘回?fù)艿臅r候直接不提供服務(wù)直接返回ERROR_CODE，等時鐘追上即可。或者做一層重試，然后上報報警系統(tǒng)，更或者是發(fā)現(xiàn)有時鐘回?fù)苤笞詣诱旧砉?jié)點并報警，如下：

 //發(fā)生了回?fù)?，此刻時間小于上次發(fā)號時間
 if (timestamp < lastTimestamp) {  			  
            long offset = lastTimestamp - timestamp;            if (offset <= 5) {                try {                	//時間偏差大小小于5ms，則等待兩倍時間
                    wait(offset << 1);//wait
                    timestamp = timeGen();                    if (timestamp < lastTimestamp) {                       //還是小于，拋異常并上報
                        throwClockBackwardsEx(timestamp);
                      }    
                } catch (InterruptedException e) {  
                   throw  e;
                }
            } else {                //throw
                throwClockBackwardsEx(timestamp);
            }
        } //分配ID

從上線情況來看，在2017年閏秒出現(xiàn)那一次出現(xiàn)過部分機(jī)器回?fù)埽捎贚eaf-snowflake的策略保證，成功避免了對業(yè)務(wù)造成的影響。

Leaf在美團(tuán)點評公司內(nèi)部服務(wù)包含金融、支付交易、餐飲、外賣、酒店旅游、貓眼電影等眾多業(yè)務(wù)線。目前Leaf的性能在4C8G的機(jī)器上QPS能壓測到近5w/s，TP999 1ms，已經(jīng)能夠滿足大部分的業(yè)務(wù)的需求。每天提供億數(shù)量級的調(diào)用量，作為公司內(nèi)部公共的基礎(chǔ)技術(shù)設(shè)施，必須保證高SLA和高性能的服務(wù)，我們目前還僅僅達(dá)到了及格線，還有很多提高的空間。

施瓦茨. 高性能MySQL[M]. 電子工業(yè)出版社, 2010:162-171.
維基百科：UUID .
snowflake .
MySQL: Clustered and Secondary Indexes .
半同步復(fù)制 Semisynchronous Replication .

新聞標(biāo)題：Leaf-分布式ID生成系統(tǒng)
URL鏈接：http://m.jiaotiyi.com/article/pjhhic.html

網(wǎng)站建設(shè)知識

Leaf-分布式ID生成系統(tǒng)

Leaf-segment數(shù)據(jù)庫方案

雙buffer優(yōu)化

Leaf高可用容災(zāi)

弱依賴ZooKeeper

解決時鐘問題

其他資訊