背景
在復雜分布式系統(tǒng)中，往往需要對大量的數(shù)據(jù)和消息進行唯一標識蚯涮。如在美團點評的金融治专、支付、餐飲遭顶、酒店张峰、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長棒旗，對數(shù)據(jù)分庫分表后需要有一個唯一ID來標識一條數(shù)據(jù)或消息喘批，數(shù)據(jù)庫的自增ID顯然不能滿足需求；特別一點的如訂單嗦哆、騎手谤祖、優(yōu)惠券也都需要有唯一ID做標識。此時一個能夠生成全局唯一ID的系統(tǒng)是非常必要的老速。概括下來粥喜，那業(yè)務系統(tǒng)對ID號的要求有哪些呢？
全局唯一性：不能出現(xiàn)重復的ID號橘券，既然是唯一標識额湘，這是最基本的要求卿吐。
趨勢遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構來存儲索引數(shù)據(jù)锋华，在主鍵的選擇上面我們應該盡量使用有序的主鍵保證寫入性能嗡官。
單調(diào)遞增：保證下一個ID一定大于上一個ID，例如事務版本號毯焕、IM增量消息衍腥、排序等特殊需求。
信息安全：如果ID是連續(xù)的纳猫，惡意用戶的扒取工作就非常容易做了婆咸，直接按照順序下載指定URL即可；如果是訂單號就更危險了芜辕，競對可以直接知道我們一天的單量尚骄。所以在一些應用場景下，會需要ID無規(guī)則侵续、不規(guī)則倔丈。
上述123對應三類不同的場景，3和4需求還是互斥的状蜗，無法使用同一個方案滿足需五。
同時除了對ID號碼自身的要求，業(yè)務還對ID號生成系統(tǒng)的可用性要求極高诗舰，想象一下警儒，如果ID生成系統(tǒng)癱瘓，整個美團點評支付眶根、優(yōu)惠券發(fā)券、騎手派單等關鍵動作都無法執(zhí)行边琉，這就會帶來一場災難属百。
由此總結(jié)下一個ID生成系統(tǒng)應該做到如下幾點：
平均延遲和TP999延遲都要盡可能低；
可用性5個9变姨；
高QPS族扰。
常見方法介紹
UUID
UUID(Universally Unique Identifier)的標準型式包含32個16進制數(shù)字，以連字號分為五段定欧，形式為8-4-4-4-12的36個字符渔呵，示例：550e8400-e29b-41d4-a716-446655440000，到目前為止業(yè)界一共有5種方式生成UUID砍鸠，詳情見IETF發(fā)布的UUID規(guī)范?A Universally Unique IDentifier (UUID) URN Namespace扩氢。
優(yōu)點：
性能非常高：本地生成，沒有網(wǎng)絡消耗爷辱。
缺點：
不易于存儲：UUID太長录豺，16字節(jié)128位朦肘，通常以36長度的字符串表示，很多場景不適用双饥。
信息不安全：基于MAC地址生成UUID的算法可能會造成MAC地址泄露媒抠，這個漏洞曾被用于尋找梅麗莎病毒的制作者位置。
ID作為主鍵時在特定的環(huán)境會存在一些問題咏花，比如做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索引不利：如果作為數(shù)據(jù)庫主鍵冲秽，在InnoDB引擎下，UUID的無序性可能會引起數(shù)據(jù)位置頻繁變動矩父，嚴重影響性能锉桑。
類snowflake方案
這種方案大致來說是一種以劃分命名空間（UUID也算，由于比較常見窍株，所以單獨分析）來生成ID的一種算法民轴，這種方案把64-bit分別劃分成多段，分開來標示機器球订、時間等后裸，比如在snowflake中的64-bit分別表示如下圖（圖片來自網(wǎng)絡）所示：
41-bit的時間可以表示（1L<<41）/(1000L*3600*24*365)=69年的時間，10-bit機器可以分別表示1024臺機器冒滩。如果我們對IDC劃分有需求微驶，還可以將10-bit分5-bit給IDC，分5-bit給工作機器开睡。這樣就可以表示32個IDC因苹，每個IDC下可以有32臺機器，可以根據(jù)自身需求定義篇恒。12個自增序列號可以表示2^12個ID扶檐，理論上snowflake方案的QPS約為409.6w/s，這種分配方式可以保證在任何一個IDC的任何一臺機器在任意毫秒內(nèi)生成的ID都是不同的胁艰。
這種方式的優(yōu)缺點是：
優(yōu)點：
毫秒數(shù)在高位款筑，自增序列在低位，整個ID都是趨勢遞增的腾么。
不依賴數(shù)據(jù)庫等第三方系統(tǒng)奈梳，以服務的方式部署，穩(wěn)定性更高解虱，生成ID的性能也是非常高的攘须。
可以根據(jù)自身業(yè)務特性分配bit位，非常靈活饭寺。
缺點：
強依賴機器時鐘阻课，如果機器上時鐘回撥叫挟，會導致發(fā)號重復或者服務會處于不可用狀態(tài)。
應用舉例Mongdb objectID
MongoDB官方文檔 ObjectID可以算作是和snowflake類似方法限煞，通過“時間+機器碼+pid+inc”共12個字節(jié)抹恳，通過4+3+2+3的方式最終標識成一個24長度的十六進制字符。
數(shù)據(jù)庫生成
以MySQL舉例署驻，利用給字段設置auto_increment_increment和auto_increment_offset來保證ID自增奋献，每次業(yè)務使用下列SQL讀寫MySQL得到ID號。
begin;REPLACEINTOTickets64 (stub)VALUES('a');SELECTLAST_INSERT_ID();commit;
這種方案的優(yōu)缺點如下：
優(yōu)點：
非常簡單旺上，利用現(xiàn)有數(shù)據(jù)庫系統(tǒng)的功能實現(xiàn)瓶蚂，成本小，有DBA專業(yè)維護宣吱。
ID號單調(diào)自增窃这，可以實現(xiàn)一些對ID有特殊要求的業(yè)務。
缺點：
強依賴DB征候，當DB異常時整個系統(tǒng)不可用杭攻，屬于致命問題。配置主從復制可以盡可能的增加可用性疤坝，但是數(shù)據(jù)一致性在特殊情況下難以保證兆解。主從切換時的不一致可能會導致重復發(fā)號。
ID發(fā)號性能瓶頸限制在單臺MySQL的讀寫性能跑揉。
對于MySQL性能問題锅睛，可用如下方案解決：在分布式系統(tǒng)中我們可以多部署幾臺機器，每臺機器設置不同的初始值历谍，且步長和機器數(shù)相等现拒。比如有兩臺機器。設置步長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?）寨蹋。如下所示松蒜，為了實現(xiàn)上述方案分別設置兩臺機器對應的參數(shù)，TicketServer1從1開始發(fā)號已旧，TicketServer2從2開始發(fā)號秸苗，兩臺機器每次發(fā)號之后都遞增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那么整個架構就變成了如下圖所示：
這種架構貌似能夠滿足性能的需求，但有以下幾個缺點：
系統(tǒng)水平擴展比較困難秸讹，比如定義好了步長和機器臺數(shù)之后檀咙，如果要添加機器該怎么做璃诀？假設現(xiàn)在只有一臺機器發(fā)號是1,2,3,4,5（步長是1）棕诵，這個時候需要擴容機器一臺年鸳∩θ罚可以這樣做：把第二臺機器的初始值設置得比第一臺超過很多膳算，比如14（假設在擴容時間之內(nèi)第一臺不可能發(fā)到14）涕蜂，同時設置步長為2机隙，那么這臺機器下發(fā)的號碼都是14以后的偶數(shù)有鹿。然后摘掉第一臺葱跋，把ID值保留為奇數(shù)，比如7稍味，然后修改第一臺的步長為2模庐。讓它符合我們定義的號段標準僵朗，對于這個例子來說就是讓第一臺以后只能產(chǎn)生奇數(shù)验庙。擴容方案看起來復雜嗎悴了？貌似還好湃交，現(xiàn)在想象一下如果我們線上有100臺機器搞莺，這個時候要擴容該怎么做才沧？簡直是噩夢温圆。所以系統(tǒng)水平擴展方案復雜難以實現(xiàn)岁歉。
ID沒有了單調(diào)遞增的特性锅移，只能趨勢遞增帆啃，這個缺點對于一般業(yè)務需求不是很重要窍帝，可以容忍。
數(shù)據(jù)庫壓力還是很大诽偷，每次獲取ID都得讀寫一次數(shù)據(jù)庫疯坤，只能靠堆機器來提高性能。
Leaf方案實現(xiàn)
Leaf這個名字是來自德國哲學家压怠、數(shù)學家萊布尼茨的一句話： >There are no two identical leaves in the world > “世界上沒有兩片相同的樹葉”
綜合對比上述幾種方案，每種方案都不完全符合我們的要求飞苇。所以Leaf分別在上述第二種和第三種方案上做了相應的優(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è)務不同的發(fā)號需求用biz_tag字段來區(qū)分，每個biz-tag的ID獲取相互隔離逞频，互不影響纯衍。如果以后有性能需求需要對數(shù)據(jù)庫擴容，不需要上述描述的復雜的擴容操作苗胀，只需要對biz_tag分庫分表就行襟诸。
數(shù)據(jù)庫表設計如下：
+-------------+--------------+------+-----+-------------------+-----------------------------+| 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 | onupdateCURRENT_TIMESTAMP|+-------------+--------------+------+-----+-------------------+-----------------------------+
重要字段說明：biz_tag用來區(qū)分業(yè)務，max_id表示該biz_tag目前所被分配的ID號段的最大值基协，step表示每次分配的號段長度歌亲。原來獲取ID每次都需要寫數(shù)據(jù)庫，現(xiàn)在只需要把step設置得足夠大澜驮，比如1000陷揪。那么只有當1000個號被消耗完了之后才會去重新讀寫一次數(shù)據(jù)庫。讀寫數(shù)據(jù)庫的頻率從1減小到了1/step，大致架構如下圖所示：
test_tag在第一臺Leaf機器上是1~1000的號段悍缠，當這個號段用完時卦绣，會去加載另一個長度為step=1000的號段，假設另外兩臺號段都沒有更新飞蚓，這個時候第一臺機器新加載的號段就應該是3001~4000滤港。同時數(shù)據(jù)庫對應的biz_tag這條數(shù)據(jù)的max_id會從3000被更新成4000，更新號段的SQL語句如下：
BeginUPDATEtableSETmax_id=max_id+stepWHEREbiz_tag=xxxSELECTtag, max_id, stepFROMtableWHEREbiz_tag=xxxCommit
這種模式有以下優(yōu)缺點：
優(yōu)點：
Leaf服務可以很方便的線性擴展趴拧，性能完全能夠支撐大多數(shù)業(yè)務場景溅漾。
ID號碼是趨勢遞增的8byte的64位數(shù)字，滿足上述數(shù)據(jù)庫存儲的主鍵要求著榴。
容災性高：Leaf服務內(nèi)部有號段緩存添履，即使DB宕機，短時間內(nèi)Leaf仍能正常對外提供服務兄渺。
可以自定義max_id的大小缝龄，非常方便業(yè)務從原有的ID方式上遷移過來。
缺點：
ID號碼不夠隨機挂谍，能夠泄露發(fā)號數(shù)量的信息叔壤，不太安全。
TP999數(shù)據(jù)波動大口叙，當號段使用完之后還是會hang在更新數(shù)據(jù)庫的I/O上炼绘，tg999數(shù)據(jù)會出現(xiàn)偶爾的尖刺。
DB宕機會造成整個系統(tǒng)不可用妄田。
雙buffer優(yōu)化
對于第二個缺點俺亮，Leaf-segment做了一些優(yōu)化，簡單的說就是：
Leaf 取號段的時機是在號段消耗完的時候進行的疟呐，也就意味著號段臨界點的ID下發(fā)時間取決于下一次從DB取回號段的時間脚曾，并且在這期間進來的請求也會因為DB號段沒有取回來，導致線程阻塞启具。如果請求DB的網(wǎng)絡和DB的性能穩(wěn)定本讥，這種情況對系統(tǒng)的影響是不大的，但是假如取DB的時候網(wǎng)絡發(fā)生抖動鲁冯，或者DB發(fā)生慢查詢就會導致整個系統(tǒng)的響應時間變慢拷沸。
為此，我們希望DB取號段的過程能夠做到無阻塞薯演，不需要在DB取號段的時候阻塞請求線程撞芍，即當號段消費到某個點時就異步的把下一個號段加載到內(nèi)存中。而不需要等到號段用盡的時候才去更新號段跨扮。這樣做就可以很大程度上的降低系統(tǒng)的TP999指標序无。詳細實現(xiàn)如下圖所示：
采用雙buffer的方式验毡，Leaf服務內(nèi)部有兩個號段緩存區(qū)segment。當前號段已下發(fā)10%時愉镰，如果下一個號段未更新米罚，則另啟一個更新線程去更新下一個號段。當前號段全部下發(fā)完后丈探，如果下個號段準備好了則切換到下個號段為當前segment接著下發(fā)，循環(huán)往復拔莱。
每個biz-tag都有消費速度監(jiān)控碗降，通常推薦segment長度設置為服務高峰期發(fā)號QPS的600倍（10分鐘），這樣即使DB宕機塘秦，Leaf仍能持續(xù)發(fā)號10-20分鐘不受影響讼渊。
每次請求來臨時都會判斷下個號段的狀態(tài)，從而更新此號段尊剔，所以偶爾的網(wǎng)絡抖動不會影響下個號段的更新爪幻。
Leaf高可用容災
對于第三點“DB可用性”問題，我們目前采用一主兩從的方式须误，同時分機房部署挨稿，Master和Slave之間采用半同步方式[5]同步數(shù)據(jù)。同時使用公司Atlas數(shù)據(jù)庫中間件(已開源京痢，改名為DBProxy)做主從切換奶甘。當然這種方案在一些情況會退化成異步模式，甚至在非常極端情況下仍然會造成數(shù)據(jù)不一致的情況祭椰，但是出現(xiàn)的概率非常小臭家。如果你的系統(tǒng)要保證100%的數(shù)據(jù)強一致，可以選擇使用“類Paxos算法”實現(xiàn)的強一致MySQL方案方淤，如MySQL 5.7前段時間剛剛GA的MySQL Group Replication钉赁。但是運維成本和精力都會相應的增加，根據(jù)實際情況選型即可携茂。
同時Leaf服務分IDC部署你踩，內(nèi)部的服務化框架是“MTthrift RPC”。服務調(diào)用的時候邑蒋，根據(jù)負載均衡算法會優(yōu)先調(diào)用同機房的Leaf服務姓蜂。在該IDC內(nèi)Leaf服務不可用的時候才會選擇其他機房的Leaf服務。同時服務治理平臺OCTO還提供了針對服務的過載保護医吊、一鍵截流钱慢、動態(tài)流量分配等對服務的保護措施。
Leaf-snowflake方案
Leaf-segment方案可以生成趨勢遞增的ID卿堂，同時ID號是可計算的束莫，不適用于訂單ID生成場景懒棉，比如競對在兩天中午12點分別下單，通過訂單id號相減就能大致計算出公司一天的訂單量览绿，這個是不能忍受的策严。面對這一問題，我們提供了 Leaf-snowflake方案饿敲。
Leaf-snowflake方案完全沿用snowflake方案的bit位設計妻导，即是“1+41+10+12”的方式組裝ID號。對于workerID的分配怀各，當服務集群數(shù)量較小的情況下倔韭，完全可以手動配置。Leaf服務規(guī)模較大瓢对，動手配置成本太高寿酌。所以使用Zookeeper持久順序節(jié)點的特性自動對snowflake節(jié)點配置wokerID。Leaf-snowflake是按照下面幾個步驟啟動的：
啟動Leaf-snowflake服務硕蛹，連接Zookeeper醇疼，在leaf_forever父節(jié)點下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點）。
如果有注冊過直接取回自己的workerID（zk順序節(jié)點生成的int類型ID號）法焰，啟動服務秧荆。
如果沒有注冊過，就在該父節(jié)點下面創(chuàng)建一個持久順序節(jié)點壶栋，創(chuàng)建成功后取回順序號當做自己的workerID號辰如，啟動服務。
弱依賴ZooKeeper
除了每次會去ZK拿數(shù)據(jù)以外贵试，也會在本機文件系統(tǒng)上緩存一個workerID文件琉兜。當ZooKeeper出現(xiàn)問題，恰好機器出現(xiàn)問題需要重啟時毙玻，能保證服務能夠正常啟動豌蟋。這樣做到了對三方組件的弱依賴。一定程度上提高了SLA
解決時鐘問題
因為這種方案依賴時間桑滩，如果機器的時鐘發(fā)生了回撥梧疲，那么就會有可能生成重復的ID號，需要解決時鐘回退的問題运准。
參見上圖整個啟動流程圖幌氮，服務啟動時首先檢查自己是否寫過ZooKeeper leaf_forever節(jié)點：
若寫過，則用自身系統(tǒng)時間與leaf_forever/${self}節(jié)點記錄時間做比較胁澳，若小于leaf_forever/${self}時間則認為機器時間發(fā)生了大步長回撥该互，服務啟動失敗并報警。
若未寫過韭畸，證明是新服務節(jié)點宇智，直接創(chuàng)建持久節(jié)點leaf_forever/${self}并寫入自身系統(tǒng)時間蔓搞，接下來綜合對比其余Leaf節(jié)點的系統(tǒng)時間來判斷自身系統(tǒng)時間是否準確，具體做法是取leaf_temporary下的所有臨時節(jié)點(所有運行中的Leaf-snowflake節(jié)點)的服務IP：Port随橘，然后通過RPC請求得到所有節(jié)點的系統(tǒng)時間喂分，計算sum(time)/nodeSize。
若abs( 系統(tǒng)時間-sum(time)/nodeSize ) < 閾值机蔗，認為當前系統(tǒng)時間準確蒲祈，正常啟動服務，同時寫臨時節(jié)點leaf_temporary/${self} 維持租約蜒车。
否則認為本機系統(tǒng)時間發(fā)生大步長偏移讳嘱，啟動失敗并報警。
每隔一段時間(3s)上報自身系統(tǒng)時間寫入leaf_forever/${self}酿愧。
由于強依賴時鐘，對時間的要求比較敏感邀泉，在機器工作時NTP同步也會造成秒級別的回退嬉挡，建議可以直接關閉NTP同步。要么在時鐘回撥的時候直接不提供服務直接返回ERROR_CODE汇恤，等時鐘追上即可庞钢。或者做一層重試，然后上報報警系統(tǒng)因谎，更或者是發(fā)現(xiàn)有時鐘回撥之后自動摘除本身節(jié)點并報警基括，如下：
//發(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)過部分機器回撥匠璧，由于Leaf-snowflake的策略保證桐款，成功避免了對業(yè)務造成的影響。
Leaf現(xiàn)狀
Leaf在美團點評公司內(nèi)部服務包含金融夷恍、支付交易魔眨、餐飲、外賣酿雪、酒店旅游遏暴、貓眼電影等眾多業(yè)務線。目前Leaf的性能在4C8G的機器上QPS能壓測到近5w/s指黎，TP999 1ms朋凉，已經(jīng)能夠滿足大部分的業(yè)務的需求。每天提供億數(shù)量級的調(diào)用量袋励，作為公司內(nèi)部公共的基礎技術設施侥啤，必須保證高SLA和高性能的服務当叭，我們目前還僅僅達到了及格線，還有很多提高的空間盖灸。
https://tech.meituan.com/2017/04/21/mt-leaf.html
參考資料
施瓦茨. 高性能MySQL[M]. 電子工業(yè)出版社, 2010:162-171.
MySQL: Clustered and Secondary Indexes.
