Leaf——美團點評分布式ID生成系統

在複雜分布式系統中，往往需要對大量的資料和消息進行唯一辨別。如在美團點評的金融、支付、餐飲、酒店、貓眼電影等産品的系統中，資料日漸增長，對資料分庫分表後需要有一個唯一ID來辨別一條資料或消息，資料庫的自增ID顯然不能滿足需求；特别一點的如訂單、騎手、優惠券也都需要有唯一ID做辨別。此時一個能夠生成全局唯一ID的系統是非常必要的。概括下來，那業務系統對ID号的要求有哪些呢？

全局唯一性：不能出現重複的ID号，既然是唯一辨別，這是最基本的要求。
趨勢遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數RDBMS使用B-tree的資料結構來存儲索引資料，在主鍵的選擇上面我們應該盡量使用有序的主鍵保證寫入性能。
單調遞增：保證下一個ID一定大于上一個ID，例如事務版本号、IM增量消息、排序等特殊需求。
資訊安全：如果ID是連續的，惡意使用者的扒取工作就非常容易做了，直接按照順序下載下傳指定URL即可；如果是訂單号就更危險了，競對可以直接知道我們一天的單量。是以在一些應用場景下，會需要ID無規則、不規則。

上述123對應三類不同的場景，3和4需求還是互斥的，無法使用同一個方案滿足。

同時除了對ID号碼自身的要求，業務還對ID号生成系統的可用性要求極高，想象一下，如果ID生成系統癱瘓，整個美團點評支付、優惠券發券、騎手派單等關鍵動作都無法執行，這就會帶來一場災難。

由此總結下一個ID生成系統應該做到如下幾點：

平均延遲和TP999延遲都要盡可能低；
可用性5個9；
高QPS。

UUID

UUID(Universally Unique Identifier)的标準型式包含32個16進制數字，以連字号分為五段，形式為8-4-4-4-12的36個字元，示例：

550e8400-e29b-41d4-a716-446655440000

，到目前為止業界一共有5種方式生成UUID，詳情見IETF釋出的UUID規範 A Universally Unique IDentifier (UUID) URN Namespace。

優點：

性能非常高：本地生成，沒有網絡消耗。

缺點：

不易于存儲：UUID太長，16位元組128位，通常以36長度的字元串表示，很多場景不适用。
資訊不安全：基于MAC位址生成UUID的算法可能會造成MAC位址洩露，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
ID作為主鍵時在特定的環境會存在一些問題，比如做DB主鍵的場景下，UUID就非常不适用：

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

All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index.*** If the primary key is long, the secondary indexes use more space, so it is advantageous to have a short primary key***.

② 對MySQL索引不利：如果作為資料庫主鍵，在InnoDB引擎下，UUID的無序性可能會引起資料位置頻繁變動，嚴重影響性能。

類snowflake方案

這種方案大緻來說是一種以劃分命名空間（UUID也算，由于比較常見，是以單獨分析）來生成ID的一種算法，這種方案把64-bit分别劃分成多段，分開來标示機器、時間等，比如在snowflake中的64-bit分别表示如下圖（圖檔來自網絡）所示：

image

41-bit的時間可以表示（1L<<41）/(1000L*3600*24*365)=69年的時間，10-bit機器可以分别表示1024台機器。如果我們對IDC劃分有需求，還可以将10-bit分5-bit給IDC，分5-bit給工作機器。這樣就可以表示32個IDC，每個IDC下可以有32台機器，可以根據自身需求定義。12個自增序列号可以表示2^12個ID，理論上snowflake方案的QPS約為409.6w/s，這種配置設定方式可以保證在任何一個IDC的任何一台機器在任意毫秒内生成的ID都是不同的。

這種方式的優缺點是：

毫秒數在高位，自增序列在低位，整個ID都是趨勢遞增的。
不依賴資料庫等第三方系統，以服務的方式部署，穩定性更高，生成ID的性能也是非常高的。
可以根據自身業務特性配置設定bit位，非常靈活。

強依賴機器時鐘，如果機器上時鐘回撥，會導緻發号重複或者服務會處于不可用狀态。

應用舉例Mongdb objectID

MongoDB官方文檔 ObjectID可以算作是和snowflake類似方法，通過“時間+機器碼+pid+inc”共12個位元組，通過4+3+2+3的方式最終辨別成一個24長度的十六進制字元。

資料庫生成

以MySQL舉例，利用給字段設定

auto_increment_increment

和

auto_increment_offset

來保證ID自增，每次業務使用下列SQL讀寫MySQL得到ID号。

begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;

這種方案的優缺點如下：

非常簡單，利用現有資料庫系統的功能實作，成本小，有DBA專業維護。
ID号單調自增，可以實作一些對ID有特殊要求的業務。

強依賴DB，當DB異常時整個系統不可用，屬于緻命問題。配置主從複制可以盡可能的增加可用性，但是資料一緻性在特殊情況下難以保證。主從切換時的不一緻可能會導緻重複發号。
ID發号性能瓶頸限制在單台MySQL的讀寫性能。

對于MySQL性能問題，可用如下方案解決：在分布式系統中我們可以多部署幾台機器，每台機器設定不同的初始值，且步長和機器數相等。比如有兩台機器。設定步長step為2，TicketServer1的初始值為1（1，3，5，7，9，11…）、TicketServer2的初始值為2（2，4，6，8，10…）。這是Flickr團隊在2010年撰文介紹的一種主鍵生成政策（Ticket Servers: Distributed Unique Primary Keys on the Cheap ）。如下所示，為了實作上述方案分别設定兩台機器對應的參數，TicketServer1從1開始發号，TicketServer2從2開始發号，兩台機器每次發号之後都遞增2。

TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
              TicketServer2:

auto-increment-increment = 2

auto-increment-offset = 2

假設我們要部署N台機器，步長需設定為N，每台的初始值依次為0,1,2…N-1那麼整個架構就變成了如下圖所示：

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

系統水準擴充比較困難，比如定義好了步長和機器台數之後，如果要添加機器該怎麼做？假設現在隻有一台機器發号是1,2,3,4,5（步長是1），這個時候需要擴容機器一台。可以這樣做：把第二台機器的初始值設定得比第一台超過很多，比如14（假設在擴容時間之内第一台不可能發到14），同時設定步長為2，那麼這台機器下發的号碼都是14以後的偶數。然後摘掉第一台，把ID值保留為奇數，比如7，然後修改第一台的步長為2。讓它符合我們定義的号段标準，對于這個例子來說就是讓第一台以後隻能産生奇數。擴容方案看起來複雜嗎？貌似還好，現在想象一下如果我們線上有100台機器，這個時候要擴容該怎麼做？簡直是噩夢。是以系統水準擴充方案複雜難以實作。
ID沒有了單調遞增的特性，隻能趨勢遞增，這個缺點對于一般業務需求不是很重要，可以容忍。
資料庫壓力還是很大，每次擷取ID都得讀寫一次資料庫，隻能靠堆機器來提高性能。

Leaf這個名字是來自德國哲學家、數學家萊布尼茨的一句話：

>There are no two identical leaves in the world

“世界上沒有兩片相同的樹葉”

綜合對比上述幾種方案，每種方案都不完全符合我們的要求。是以Leaf分别在上述第二種和第三種方案上做了相應的優化，實作了Leaf-segment和Leaf-snowflake方案。

Leaf-segment資料庫方案

第一種Leaf-segment方案，在使用資料庫的方案上，做了如下改變：

原方案每次擷取ID都得讀寫一次資料庫，造成資料庫壓力大。改為利用proxy server批量擷取，每次擷取一個segment(step決定大小)号段的值。用完之後再去資料庫擷取新的号段，可以大大的減輕資料庫的壓力。
各個業務不同的發号需求用biz_tag字段來區分，每個biz-tag的ID擷取互相隔離，互不影響。如果以後有性能需求需要對資料庫擴容，不需要上述描述的複雜的擴容操作，隻需要對biz_tag分庫分表就行。

資料庫表設計如下：
```
+-------------+--------------+------+-----+-------------------+-----------------------------+

| 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用來區分業務，max_id表示該biz_tag目前所被配置設定的ID号段的最大值，step表示每次配置設定的号段長度。原來擷取ID每次都需要寫資料庫，現在隻需要把step設定得足夠大，比如1000。那麼隻有當1000個号被消耗完了之後才會去重新讀寫一次資料庫。讀寫資料庫的頻率從1減小到了1/step，大緻架構如下圖所示：

Leaf——美團點評分布式ID生成系統
test_tag在第一台Leaf機器上是11000的号段，當這個号段用完時，會去加載另一個長度為step=1000的号段，假設另外兩台号段都沒有更新，這個時候第一台機器新加載的号段就應該是30014000。同時資料庫對應的biz_tag這條資料的max_id會從3000被更新成4000，更新号段的SQL語句如下：
```
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

 
```
這種模式有以下優缺點：
- Leaf服務可以很友善的線性擴充，性能完全能夠支撐大多數業務場景。
- ID号碼是趨勢遞增的8byte的64位數字，滿足上述資料庫存儲的主鍵要求。
- 容災性高：Leaf服務内部有号段緩存，即使DB當機，短時間内Leaf仍能正常對外提供服務。
- 可以自定義max_id的大小，非常友善業務從原有的ID方式上遷移過來。
- ID号碼不夠随機，能夠洩露發号數量的資訊，不太安全。
- TP999資料波動大，當号段使用完之後還是會hang在更新資料庫的I/O上，tg999資料會出現偶爾的尖刺。
- DB當機會造成整個系統不可用。
雙buffer優化

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

Leaf 取号段的時機是在号段消耗完的時候進行的，也就意味着号段臨界點的ID下發時間取決于下一次從DB取回号段的時間，并且在這期間進來的請求也會因為DB号段沒有取回來，導緻線程阻塞。如果請求DB的網絡和DB的性能穩定，這種情況對系統的影響是不大的，但是假如取DB的時候網絡發生抖動，或者DB發生慢查詢就會導緻整個系統的響應時間變慢。

為此，我們希望DB取号段的過程能夠做到無阻塞，不需要在DB取号段的時候阻塞請求線程，即當号段消費到某個點時就異步的把下一個号段加載到記憶體中。而不需要等到号段用盡的時候才去更新号段。這樣做就可以很大程度上的降低系統的TP999名額。詳細實作如下圖所示：

Leaf——美團點評分布式ID生成系統
采用雙buffer的方式，Leaf服務内部有兩個号段緩存區segment。目前号段已下發10%時，如果下一個号段未更新，則另啟一個更新線程去更新下一個号段。目前号段全部下發完後，如果下個号段準備好了則切換到下個号段為目前segment接着下發，循環往複。
- 每個biz-tag都有消費速度監控，通常推薦segment長度設定為服務高峰期發号QPS的600倍（10分鐘），這樣即使DB當機，Leaf仍能持續發号10-20分鐘不受影響。
- 每次請求來臨時都會判斷下個号段的狀态，進而更新此号段，是以偶爾的網絡抖動不會影響下個号段的更新。
Leaf高可用容災
對于第三點“DB可用性”問題，我們目前采用一主兩從的方式，同時分機房部署，Master和Slave之間采用半同步方式[5]同步資料。同時使用公司Atlas資料庫中間件(已開源，改名為DBProxy)做主從切換。當然這種方案在一些情況會退化成異步模式，甚至在非常極端情況下仍然會造成資料不一緻的情況，但是出現的機率非常小。如果你的系統要保證100%的資料強一緻，可以選擇使用“類Paxos算法”實作的強一緻MySQL方案，如MySQL 5.7前段時間剛剛GA的MySQL Group Replication。但是運維成本和精力都會相應的增加，根據實際情況選型即可。

Leaf——美團點評分布式ID生成系統

同時Leaf服務分IDC部署，内部的服務化架構是“MTthrift RPC”。服務調用的時候，根據負載均衡算法會優先調用同機房的Leaf服務。在該IDC内Leaf服務不可用的時候才會選擇其他機房的Leaf服務。同時服務治理平台OCTO還提供了針對服務的過載保護、一鍵截流、動态流量配置設定等對服務的保護措施。

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

Leaf——美團點評分布式ID生成系統
Leaf-snowflake方案完全沿用snowflake方案的bit位設計，即是“1+41+10+12”的方式組裝ID号。對于workerID的配置設定，當服務叢集數量較小的情況下，完全可以手動配置。Leaf服務規模較大，動手配置成本太高。是以使用Zookeeper持久順序節點的特性自動對snowflake節點配置wokerID。Leaf-snowflake是按照下面幾個步驟啟動的：
1. 啟動Leaf-snowflake服務，連接配接Zookeeper，在leaf_forever父節點下檢查自己是否已經注冊過（是否有該順序子節點）。
2. 如果有注冊過直接取回自己的workerID（zk順序節點生成的int類型ID号），啟動服務。
3. 如果沒有注冊過，就在該父節點下面建立一個持久順序節點，建立成功後取回順序号當做自己的workerID号，啟動服務。
Leaf——美團點評分布式ID生成系統

弱依賴ZooKeeper
除了每次會去ZK拿資料以外，也會在本機檔案系統上緩存一個workerID檔案。當ZooKeeper出現問題，恰好機器出現問題需要重新開機時，能保證服務能夠正常啟動。這樣做到了對三方元件的弱依賴。一定程度上提高了SLA
解決時鐘問題
因為這種方案依賴時間，如果機器的時鐘發生了回撥，那麼就會有可能生成重複的ID号，需要解決時鐘回退的問題。

Leaf——美團點評分布式ID生成系統
參見上圖整個啟動流程圖，服務啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節點：
1. 若寫過，則用自身系統時間與leaf_forever/${self}節點記錄時間做比較，若小于leaf_forever/${self}時間則認為機器時間發生了大步長回撥，服務啟動失敗并報警。
2. 若未寫過，證明是新服務節點，直接建立持久節點leaf_forever/${self}并寫入自身系統時間，接下來綜合對比其餘Leaf節點的系統時間來判斷自身系統時間是否準确，具體做法是取leaf_temporary下的所有臨時節點(所有運作中的Leaf-snowflake節點)的服務IP：Port，然後通過RPC請求得到所有節點的系統時間，計算sum(time)/nodeSize。
3. 若abs( 系統時間-sum(time)/nodeSize ) < 門檻值，認為目前系統時間準确，正常啟動服務，同時寫臨時節點leaf_temporary/${self} 維持租約。
4. 否則認為本機系統時間發生大步長偏移，啟動失敗并報警。
5. 每隔一段時間(3s)上報自身系統時間寫入leaf_forever/${self}。
由于強依賴時鐘，對時間的要求比較敏感，在機器工作時NTP同步也會造成秒級别的回退，建議可以直接關閉NTP同步。要麼在時鐘回撥的時候直接不提供服務直接傳回ERROR_CODE，等時鐘追上即可。或者做一層重試，然後上報報警系統，更或者是發現有時鐘回撥之後自動摘除本身節點并報警，如下：
```
//發生了回撥，此刻時間小于上次發号時間

if (timestamp < lastTimestamp) {


 long offset = lastTimestamp - timestamp;
 if (offset &lt;= 5) {
 try {
 	//時間偏差大小小于5ms，則等待兩倍時間
 wait(offset &lt;&lt; 1);//wait
 timestamp = timeGen();
 if (timestamp &lt; lastTimestamp) {
 //還是小于，抛異常并上報
 throwClockBackwardsEx(timestamp);
 } 
 } catch (InterruptedException e) { 
 throw e;
 }
 } else {
 //throw
 throwClockBackwardsEx(timestamp);
 }
 }
 
 
```



//配置設定ID

從上線情況來看，在2017年閏秒出現那一次出現過部分機器回撥，由于Leaf-snowflake的政策保證，成功避免了對業務造成的影響。

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

照東，美團點評基礎架構團隊成員，主要參與美團大型分布式鍊路跟蹤系統Mtrace和美團點評分布式ID生成系統Leaf的開發工作。曾就職于阿裡巴巴，2016年7月加入美團。

最後做一個招聘廣告：如果你對大規模分布式環境下的服務治理、分布式會話鍊追蹤等系統感興趣，誠摯歡迎投遞履歷至：zhangjinlu#meituan.com。

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

原文位址：https://tech.meituan.com/2017/04/21/mt-leaf.html

Leaf——美團點評分布式ID生成系統

UUID

類snowflake方案

應用舉例Mongdb objectID

資料庫生成

Leaf-segment資料庫方案

雙buffer優化

Leaf高可用容災

弱依賴ZooKeeper

解決時鐘問題

繼續閱讀

寶塔面闆mysql恢複2018.1.8更新

Centos7 MySQL 5.7 安裝MySQL 5.7 安裝

celery使用入門

windows不能在本地計算機上運作oracleDbConsoleorcl

查找入職員工時間排名倒數第三的員工所有資訊

Hibernate使用Hibernate的“3個準備，7個步驟”Hibernate API簡介操作實體對象對象識别

雲計算面試題——mysql/存儲引擎/備份

關于SQL語言

SQL語言基礎：常用的資料查詢語句

MapReduce的幾個企業級經典面試案例MapReduce的幾個企業級經典面試案例

Ubuntu16.04安裝Apache+MySQL+PHP1. 安裝Apache2. 安裝MySQL3. 安裝PHP4. 安裝phpMyAdmin

MySQL的4種隔離級别？出現問題

neo4j之cypher使用文檔

mysql使用source指令導入.sql檔案

sqlServer根據經緯查距離

Oracle 批量查詢傳入List 傳回List