本文來(lái)自美團(tuán)技術(shù)團(tuán)隊(duì)“照東”的分享，原題《Leaf——美團(tuán)點(diǎn)評(píng)分布式ID生成系統(tǒng)》，收錄時(shí)有勘誤、修訂并重新排版，感謝原作者的分享。
1、引言
鑒于IM系統(tǒng)中聊天消息ID生成算法和生成策略的重要性（因?yàn)槟撤N意義上來(lái)說(shuō)：聊天消息ID的優(yōu)劣決定了IM應(yīng)用層某些功能實(shí)現(xiàn)的難易度），所以即時(shí)通訊網(wǎng)近期正在著重整理有關(guān)IM中的聊天消息ID算法方面的文章，包括微信團(tuán)隊(duì)的這篇《微信技術(shù)分享：微信的海量IM聊天消息序列號(hào)生成實(shí)踐（算法原理篇）》，以及融云分享的《融云技術(shù)分享：解密融云IM產(chǎn)品的聊天消息ID生成策略》一文。
本文分享了美團(tuán)系統(tǒng)中正在使用的兩種ID生成算法：
1）Leaf-segment方案：可生成全局唯一、全局有序的ID；
2）Leaf-snowflake方案：可生成全局唯一、局部有序的ID。
對(duì)于美團(tuán)的Leaf-segment這個(gè)ID生成方案，因?yàn)樯傻腎D全局唯一、全局有序，所以非常適合IM這種應(yīng)用場(chǎng)景，這也是即時(shí)通訊網(wǎng)整理并分享給社區(qū)的原因。
友情提示：IM系統(tǒng)中的消息ID不同于電商等傳統(tǒng)信息系統(tǒng)，IM中的消息ID通常較少用于服務(wù)端架構(gòu)中的檢索目的（例外是：消息撤回等使用頻率較低的功能中會(huì)用到），所以服務(wù)端架構(gòu)中的ID查詢(xún)性能上可以不必追求極致（必竟IM消息對(duì)應(yīng)于人的自然溝通，通常都是以時(shí)間為檢索條件，比如離線消息拉取、群消息拉取、漫游消息拉取等），所以在學(xué)習(xí)諸如美團(tuán)的ID生成算法時(shí)，沒(méi)有必要生搬硬套，適度借鑒，按照IM系統(tǒng)的特性進(jìn)行融會(huì)貫通地設(shè)計(jì)才是最佳實(shí)踐。
免責(zé)申明：本文來(lái)自美團(tuán)官方技術(shù)團(tuán)隊(duì)的分享，僅用于技術(shù)交流學(xué)習(xí)和研究目的，請(qǐng)勿用于非法用途，文中如涉及商業(yè)秘密，請(qǐng)告之我處理！
（本文同步發(fā)布于：http://www.52im.net/thread-2751-1-1.html）
2、關(guān)于作者
照東：美團(tuán)點(diǎn)評(píng)基礎(chǔ)架構(gòu)團(tuán)隊(duì)成員，主要參與美團(tuán)大型分布式鏈路跟蹤系統(tǒng)Mtrace和美團(tuán)點(diǎn)評(píng)分布式ID生成系統(tǒng)Leaf的開(kāi)發(fā)工作。曾就職于阿里巴巴，2016年7月加入美團(tuán)。
3、相關(guān)文章
4、正文概述
在復(fù)雜分布式系統(tǒng)中，往往需要對(duì)大量的數(shù)據(jù)和消息進(jìn)行唯一標(biāo)識(shí)。如在美團(tuán)點(diǎn)評(píng)的金融、支付、餐飲、酒店、貓眼電影等產(chǎn)品的系統(tǒng)中，數(shù)據(jù)日漸增長(zhǎng)，對(duì)數(shù)據(jù)分庫(kù)分表后需要有一個(gè)唯一ID來(lái)標(biāo)識(shí)一條數(shù)據(jù)或消息，數(shù)據(jù)庫(kù)的自增ID顯然不能滿足需求；特別一點(diǎn)的如訂單、騎手、優(yōu)惠券也都需要有唯一ID做標(biāo)識(shí)。此時(shí)一個(gè)能夠生成全局唯一ID的系統(tǒng)是非常必要的。
概括下來(lái)，那業(yè)務(wù)系統(tǒng)對(duì)ID號(hào)的要求有哪些呢？
1）全局唯一性：不能出現(xiàn)重復(fù)的ID號(hào)，既然是唯一標(biāo)識(shí)，這是最基本的要求；
2）趨勢(shì)遞增：在MySQL InnoDB引擎中使用的是聚集索引，由于多數(shù)RDBMS使用B-tree的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)索引數(shù)據(jù)，在主鍵的選擇上面我們應(yīng)該盡量使用有序的主鍵保證寫(xiě)入性能；
3）單調(diào)遞增：保證下一個(gè)ID一定大于上一個(gè)ID，例如事務(wù)版本號(hào)、IM聊天中的增量消息、排序等特殊需求；
4）信息安全：如果ID是連續(xù)的，惡意用戶(hù)的扒取工作就非常容易做了，直接按照順序下載指定URL即可；如果是訂單號(hào)就更危險(xiǎn)了，競(jìng)對(duì)可以直接知道我們一天的單量。所以在一些應(yīng)用場(chǎng)景下，會(huì)需要ID無(wú)規(guī)則、不規(guī)則。
上述123對(duì)應(yīng)三類(lèi)不同的場(chǎng)景，3和4需求還是互斥的，無(wú)法使用同一個(gè)方案滿足。
同時(shí)除了對(duì)ID號(hào)碼自身的要求，業(yè)務(wù)還對(duì)ID號(hào)生成系統(tǒng)的可用性要求極高，想象一下，如果ID生成系統(tǒng)癱瘓，整個(gè)美團(tuán)點(diǎn)評(píng)支付、優(yōu)惠券發(fā)券、騎手派單等關(guān)鍵動(dòng)作都無(wú)法執(zhí)行，這就會(huì)帶來(lái)一場(chǎng)災(zāi)難。
由此總結(jié)下一個(gè)分布式ID生成系統(tǒng)應(yīng)做到如下幾點(diǎn)：
1）平均延遲和TP999延遲都要盡可能低；
2）可用性5個(gè)9；
3）高QPS。
5、美團(tuán)為什么沒(méi)用UUID？
UUID（Universally Unique Identifier）的標(biāo)準(zhǔn)型式包含32個(gè)16進(jìn)制數(shù)字，以連字號(hào)分為五段，形式為8-4-4-4-12的36個(gè)字符，示例：550e8400-e29b-41d4-a716-446655440000，到目前為止業(yè)界一共有5種方式生成UUID，詳情見(jiàn)IETF發(fā)布的UUID規(guī)范：《A Universally Unique IDentifier (UUID) URN Namespace》。
對(duì)于美團(tuán)點(diǎn)評(píng)這些具體的業(yè)務(wù)系統(tǒng)來(lái)說(shuō)，UUID有以下優(yōu)點(diǎn)和缺點(diǎn)。
優(yōu)點(diǎn)：
性能非常高：本地生成，沒(méi)有網(wǎng)絡(luò)消耗。
缺點(diǎn)：
1）不易于存儲(chǔ)：UUID太長(zhǎng)，16字節(jié)128位，通常以36長(zhǎng)度的字符串表示，很多場(chǎng)景不適用；
2）信息不安全：基于MAC地址生成UUID的算法可能會(huì)造成MAC地址泄露，這個(gè)漏洞曾被用于尋找梅麗莎病毒的制作者位置。
ID作為主鍵時(shí)在特定的環(huán)境會(huì)存在一些問(wèn)題，比如做DB主鍵的場(chǎng)景下，UUID就非常不適用：
① MySQL官方有明確的建議主鍵要盡量越短越好[4]，36個(gè)字符長(zhǎng)度的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***.
② 對(duì)MySQL索引不利：如果作為數(shù)據(jù)庫(kù)主鍵，在InnoDB引擎下，UUID的無(wú)序性可能會(huì)引起數(shù)據(jù)位置頻繁變動(dòng)，嚴(yán)重影響性能。
總之，UUID有很多合適的應(yīng)用場(chǎng)景，但對(duì)于美團(tuán)點(diǎn)評(píng)相關(guān)的業(yè)務(wù)系統(tǒng)來(lái)說(shuō)，UUID顯然不是最佳選擇。
6、美團(tuán)為什么不直接用Snowflake算法？
6.1 SnowFlake算法原理
SnowFlake 算法，是 Twitter 開(kāi)源的分布式 ID 生成算法。其核心思想就是：使用一個(gè) 64 bit 的 long 型的數(shù)字作為全局唯一 ID。
這 64 個(gè) bit 中，其中 1 個(gè) bit 是不用的，然后用其中的 41 bit 作為毫秒數(shù)，用 10 bit 作為工作機(jī)器 ID，12 bit 作為序列號(hào)。
SnowFlake的ID構(gòu)成：
SnowFlake的ID樣本：
給大家舉個(gè)例子吧，如上圖所示，比如下面那個(gè) 64 bit 的 long 型數(shù)字：
1）第一個(gè)部分，是 1 個(gè) bit：0，這個(gè)是無(wú)意義的；
2）第二個(gè)部分，是 41 個(gè) bit：表示的是時(shí)間戳；
3）第三個(gè)部分，是 5 個(gè) bit：表示的是機(jī)房 ID，10001；
4）第四個(gè)部分，是 5 個(gè) bit：表示的是機(jī)器 ID，1 1001；
5）第五個(gè)部分，是 12 個(gè) bit：表示的序號(hào)，就是某個(gè)機(jī)房某臺(tái)機(jī)器上這一毫秒內(nèi)同時(shí)生成的 ID 的序號(hào)，0000 00000000。
① 1 bit：是不用的，為啥呢？
因?yàn)槎M(jìn)制里第一個(gè) bit 為如果是 1，那么都是負(fù)數(shù)，但是我們生成的 ID 都是正數(shù)，所以第一個(gè) bit 統(tǒng)一都是 0。
② 41 bit：表示的是時(shí)間戳，單位是毫秒。
41 bit 可以表示的數(shù)字多達(dá) 2^41 - 1，也就是可以標(biāo)識(shí) 2 ^ 41 - 1 個(gè)毫秒值，換算成年就是表示 69 年的時(shí)間。
③ 10 bit：記錄工作機(jī)器 ID，代表的是這個(gè)服務(wù)最多可以部署在 2^10 臺(tái)機(jī)器上，也就是 1024 臺(tái)機(jī)器。
但是 10 bit 里 5 個(gè) bit 代表機(jī)房 id，5 個(gè) bit 代表機(jī)器 ID。意思就是最多代表 2 ^ 5 個(gè)機(jī)房（32 個(gè)機(jī)房），每個(gè)機(jī)房里可以代表 2 ^ 5 個(gè)機(jī)器（32 臺(tái)機(jī)器）。
④12 bit：這個(gè)是用來(lái)記錄同一個(gè)毫秒內(nèi)產(chǎn)生的不同 ID。
12 bit 可以代表的最大正整數(shù)是 2 ^ 12 - 1 = 4096，也就是說(shuō)可以用這個(gè) 12 bit 代表的數(shù)字來(lái)區(qū)分同一個(gè)毫秒內(nèi)的 4096 個(gè)不同的 ID。理論上snowflake方案的QPS約為409.6w/s，這種分配方式可以保證在任何一個(gè)IDC的任何一臺(tái)機(jī)器在任意毫秒內(nèi)生成的ID都是不同的。
簡(jiǎn)單來(lái)說(shuō)，你的某個(gè)服務(wù)假設(shè)要生成一個(gè)全局唯一 ID，那么就可以發(fā)送一個(gè)請(qǐng)求給部署了 SnowFlake 算法的系統(tǒng)，由這個(gè) SnowFlake 算法系統(tǒng)來(lái)生成唯一 ID。
1）這個(gè) SnowFlake 算法系統(tǒng)首先肯定是知道自己所在的機(jī)房和機(jī)器的，比如機(jī)房 ID = 17，機(jī)器 ID = 12；
2）接著 SnowFlake 算法系統(tǒng)接收到這個(gè)請(qǐng)求之后，首先就會(huì)用二進(jìn)制位運(yùn)算的方式生成一個(gè) 64 bit 的 long 型 ID，64 個(gè) bit 中的第一個(gè) bit 是無(wú)意義的；
3）接著 41 個(gè) bit，就可以用當(dāng)前時(shí)間戳（單位到毫秒），然后接著 5 個(gè) bit 設(shè)置上這個(gè)機(jī)房 id，還有 5 個(gè) bit 設(shè)置上機(jī)器 ID；
4）最后再判斷一下，當(dāng)前這臺(tái)機(jī)房的這臺(tái)機(jī)器上這一毫秒內(nèi)，這是第幾個(gè)請(qǐng)求，給這次生成 ID 的請(qǐng)求累加一個(gè)序號(hào)，作為最后的 12 個(gè) bit。
最終一個(gè) 64 個(gè) bit 的 ID 就出來(lái)了，類(lèi)似于：
這個(gè)算法可以保證說(shuō)，一個(gè)機(jī)房的一臺(tái)機(jī)器上，在同一毫秒內(nèi)，生成了一個(gè)唯一的 ID。可能一個(gè)毫秒內(nèi)會(huì)生成多個(gè) ID，但是有最后 12 個(gè) bit 的序號(hào)來(lái)區(qū)分開(kāi)來(lái)。
下面我們簡(jiǎn)單看看這個(gè) SnowFlake 算法的一個(gè)代碼實(shí)現(xiàn)，這就是個(gè)示例，大家如果理解了這個(gè)意思之后，以后可以自己嘗試改造這個(gè)算法。
總之就是用一個(gè) 64 bit 的數(shù)字中各個(gè) bit 位來(lái)設(shè)置不同的標(biāo)志位，區(qū)分每一個(gè) ID。
SnowFlake 算法的一個(gè)典型Java實(shí)現(xiàn)代碼，可以參見(jiàn)文章中的第“6.5 方案四：SnowFlake 算法的思想分析”節(jié)：《通俗易懂：如何設(shè)計(jì)能支撐百萬(wàn)并發(fā)的數(shù)據(jù)庫(kù)架構(gòu)？》。
6.2 對(duì)于美團(tuán)來(lái)說(shuō)，SnowFlake算法的優(yōu)缺點(diǎn)
對(duì)于美團(tuán)的業(yè)務(wù)系統(tǒng)來(lái)說(shuō)，這種方式的優(yōu)缺點(diǎn)如下。
► 優(yōu)點(diǎn)：
1）毫秒數(shù)在高位，自增序列在低位，整個(gè)ID都是趨勢(shì)遞增的；
2）不依賴(lài)數(shù)據(jù)庫(kù)等第三方系統(tǒng)，以服務(wù)的方式部署，穩(wěn)定性更高，生成ID的性能也是非常高的；
3）可以根據(jù)自身業(yè)務(wù)特性分配bit位，非常靈活。
► 缺點(diǎn)：
強(qiáng)依賴(lài)機(jī)器時(shí)鐘，如果機(jī)器上時(shí)鐘回?fù)埽瑫?huì)導(dǎo)致發(fā)號(hào)重復(fù)或者服務(wù)會(huì)處于不可用狀態(tài)。
► 應(yīng)用舉例——Mongdb的objectID：
MongoDB官方文檔 ObjectID 可以算作是和snowflake類(lèi)似方法，通過(guò)“時(shí)間+機(jī)器碼+pid+inc”共12個(gè)字節(jié)，通過(guò)4+3+2+3的方式最終標(biāo)識(shí)成一個(gè)24長(zhǎng)度的十六進(jìn)制字符。
7、數(shù)據(jù)庫(kù)的自增ID對(duì)于美團(tuán)來(lái)說(shuō)，也不合適
以MySQL舉例，利用給字段設(shè)置auto_increment_increment和auto_increment_offset來(lái)保證ID自增，每次業(yè)務(wù)使用下列SQL讀寫(xiě)MySQL得到ID號(hào)。
begin;
REPLACEINTOTickets64 (stub) VALUES('a');
SELECTLAST_INSERT_ID();
commit;
這種方案的優(yōu)缺點(diǎn)如下。
優(yōu)點(diǎn)：
1）非常簡(jiǎn)單，利用現(xiàn)有數(shù)據(jù)庫(kù)系統(tǒng)的功能實(shí)現(xiàn)，成本小，有DBA專(zhuān)業(yè)維護(hù)；
2）ID號(hào)單調(diào)自增，可以實(shí)現(xiàn)一些對(duì)ID有特殊要求的業(yè)務(wù)。
缺點(diǎn)：
1）強(qiáng)依賴(lài)DB，當(dāng)DB異常時(shí)整個(gè)系統(tǒng)不可用，屬于致命問(wèn)題。配置主從復(fù)制可以盡可能的增加可用性，但是數(shù)據(jù)一致性在特殊情況下難以保證。主從切換時(shí)的不一致可能會(huì)導(dǎo)致重復(fù)發(fā)號(hào)；
2）ID發(fā)號(hào)性能瓶頸限制在單臺(tái)MySQL的讀寫(xiě)性能。
對(duì)于MySQL性能問(wèn)題，可用如下方案解決：在分布式系統(tǒng)中可以多部署幾臺(tái)機(jī)器，每臺(tái)機(jī)器設(shè)置不同的初始值，且步長(zhǎng)和機(jī)器數(shù)相等。比如有兩臺(tái)機(jī)器。設(shè)置步長(zhǎng)step為2，TicketServer1的初始值為1（1，3，5，7，9，11…）、TicketServer2的初始值為2（2，4，6，8，10…）。這是Flickr團(tuán)隊(duì)在2010年撰文介紹的一種主鍵生成策略（詳見(jiàn)：《Ticket Servers: Distributed Unique Primary Keys on the Cheap》）。如下所示，為了實(shí)現(xiàn)上述方案分別設(shè)置兩臺(tái)機(jī)器對(duì)應(yīng)的參數(shù)，TicketServer1從1開(kāi)始發(fā)號(hào)，TicketServer2從2開(kāi)始發(fā)號(hào)，兩臺(tái)機(jī)器每次發(fā)號(hào)之后都遞增2。
TicketServer1:
auto-increment-increment = 2
auto-increment-offset = 1
TicketServer2:
auto-increment-increment = 2
auto-increment-offset = 2
假設(shè)我們要部署N臺(tái)機(jī)器，步長(zhǎng)需設(shè)置為N，每臺(tái)的初始值依次為0,1,2…N-1那么整個(gè)架構(gòu)就變成了如下圖所示：
這種必讀是后的架構(gòu)貌似能夠滿足性能的需求，但有以下幾個(gè)缺點(diǎn)：
1）系統(tǒng)水平擴(kuò)展比較困難：比如定義好了步長(zhǎng)和機(jī)器臺(tái)數(shù)之后，如果要添加機(jī)器該怎么做？假設(shè)現(xiàn)在只有一臺(tái)機(jī)器發(fā)號(hào)是1,2,3,4,5（步長(zhǎng)是1），這個(gè)時(shí)候需要擴(kuò)容機(jī)器一臺(tái)。可以這樣做：把第二臺(tái)機(jī)器的初始值設(shè)置得比第一臺(tái)超過(guò)很多，比如14（假設(shè)在擴(kuò)容時(shí)間之內(nèi)第一臺(tái)不可能發(fā)到14），同時(shí)設(shè)置步長(zhǎng)為2，那么這臺(tái)機(jī)器下發(fā)的號(hào)碼都是14以后的偶數(shù)。然后摘掉第一臺(tái)，把ID值保留為奇數(shù)，比如7，然后修改第一臺(tái)的步長(zhǎng)為2。讓它符合我們定義的號(hào)段標(biāo)準(zhǔn)，對(duì)于這個(gè)例子來(lái)說(shuō)就是讓第一臺(tái)以后只能產(chǎn)生奇數(shù)。擴(kuò)容方案看起來(lái)復(fù)雜嗎？貌似還好，現(xiàn)在想象一下如果我們線上有100臺(tái)機(jī)器，這個(gè)時(shí)候要擴(kuò)容該怎么做？簡(jiǎn)直是噩夢(mèng)。所以系統(tǒng)水平擴(kuò)展方案復(fù)雜難以實(shí)現(xiàn)；
2）ID沒(méi)有了單調(diào)遞增的特性：只能趨勢(shì)遞增，這個(gè)缺點(diǎn)對(duì)于一般業(yè)務(wù)需求不是很重要，可以容忍；
3）數(shù)據(jù)庫(kù)壓力還是很大：每次獲取ID都得讀寫(xiě)一次數(shù)據(jù)庫(kù)，只能靠堆機(jī)器來(lái)提高性能。
綜合對(duì)比上述幾種方案，每種方案都不完全符合我們的要求。所以美團(tuán)建立了Leaf工程（Leaf這個(gè)名字是來(lái)自德國(guó)哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話： >There are no two identical leaves in the world > “世界上沒(méi)有兩片相同的樹(shù)葉”），分別在上述第二種（Snowflake）和第三種（數(shù)據(jù)庫(kù)自增ID）方案上做了相應(yīng)的優(yōu)化，實(shí)現(xiàn)了Leaf-snowflake和Leaf-segment方案。接下來(lái)，我們?cè)敿?xì)介紹這兩種方案的實(shí)現(xiàn)思路。
8、美團(tuán)的Leaf-segment方案：可生成全局唯一、全局有序的ID
8.1 基本原理
美團(tuán)的Leaf-segment方案，實(shí)際上是在上面介紹的數(shù)據(jù)庫(kù)自增ID方案上的一種改進(jìn)方案，它可生成全局唯一、全局有序的ID，可以用于：事務(wù)版本號(hào)、IM聊天中的增量消息、全局排序等業(yè)務(wù)中。
美團(tuán)的Leaf-segment對(duì)數(shù)據(jù)庫(kù)自增ID方案做了如下改變：
1）原方案每次獲取ID都得讀寫(xiě)一次數(shù)據(jù)庫(kù)，造成數(shù)據(jù)庫(kù)壓力大。改為利用proxy server批量獲取，每次獲取一個(gè)segment(step決定大小)號(hào)段的值。用完之后再去數(shù)據(jù)庫(kù)獲取新的號(hào)段，可以大大的減輕數(shù)據(jù)庫(kù)的壓力；
2）各個(gè)業(yè)務(wù)不同的發(fā)號(hào)需求用biz_tag字段來(lái)區(qū)分，每個(gè)biz-tag的ID獲取相互隔離，互不影響。如果以后有性能需求需要對(duì)數(shù)據(jù)庫(kù)擴(kuò)容，不需要上述描述的復(fù)雜的擴(kuò)容操作，只需要對(duì)biz_tag分庫(kù)分表就行。
數(shù)據(jù)庫(kù)表設(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|
+-------------+--------------+------+-----+-------------------+-----------------------------+
重要字段說(shuō)明：
biz_tag：用來(lái)區(qū)分業(yè)務(wù)；
max_id：表示該biz_tag目前所被分配的ID號(hào)段的最大值；
step：表示每次分配的號(hào)段長(zhǎng)度。
原來(lái)獲取ID每次都需要寫(xiě)數(shù)據(jù)庫(kù)，現(xiàn)在只需要把step設(shè)置得足夠大，比如1000。那么只有當(dāng)1000個(gè)號(hào)被消耗完了之后才會(huì)去重新讀寫(xiě)一次數(shù)據(jù)庫(kù)。
讀寫(xiě)數(shù)據(jù)庫(kù)的頻率從1減小到了1/step，大致架構(gòu)如下圖所示：
test_tag在第一臺(tái)Leaf機(jī)器上是1~1000的號(hào)段，當(dāng)這個(gè)號(hào)段用完時(shí)，會(huì)去加載另一個(gè)長(zhǎng)度為step=1000的號(hào)段，假設(shè)另外兩臺(tái)號(hào)段都沒(méi)有更新，這個(gè)時(shí)候第一臺(tái)機(jī)器新加載的號(hào)段就應(yīng)該是3001~4000。
同時(shí)數(shù)據(jù)庫(kù)對(duì)應(yīng)的biz_tag這條數(shù)據(jù)的max_id會(huì)從3000被更新成4000，更新號(hào)段的SQL語(yǔ)句如下：
Begin
UPDATEtableSETmax_id=max_id+step WHEREbiz_tag=xxx
SELECTtag, max_id, step FROMtableWHEREbiz_tag=xxx
Commit
這種模式有以下優(yōu)缺點(diǎn)。
優(yōu)點(diǎn)：
1）Leaf服務(wù)可以很方便的線性擴(kuò)展，性能完全能夠支撐大多數(shù)業(yè)務(wù)場(chǎng)景；
2）ID號(hào)碼是趨勢(shì)遞增的8byte的64位數(shù)字，滿足上述數(shù)據(jù)庫(kù)存儲(chǔ)的主鍵要求；
3）容災(zāi)性高：Leaf服務(wù)內(nèi)部有號(hào)段緩存，即使DB宕機(jī)，短時(shí)間內(nèi)Leaf仍能正常對(duì)外提供服務(wù)；
4）可以自定義max_id的大小，非常方便業(yè)務(wù)從原有的ID方式上遷移過(guò)來(lái)。
缺點(diǎn)：
1）ID號(hào)碼不夠隨機(jī)，能夠泄露發(fā)號(hào)數(shù)量的信息，不太安全；
2）TP999數(shù)據(jù)波動(dòng)大，當(dāng)號(hào)段使用完之后還是會(huì)hang在更新數(shù)據(jù)庫(kù)的I/O上，tg999數(shù)據(jù)會(huì)出現(xiàn)偶爾的尖刺；
3）DB宕機(jī)會(huì)造成整個(gè)系統(tǒng)不可用。
8.2 雙buffer優(yōu)化
對(duì)于上述第二個(gè)缺點(diǎn)，Leaf-segment方案做了一些優(yōu)化，簡(jiǎn)單的說(shuō)就是：
Leaf 取號(hào)段的時(shí)機(jī)是在號(hào)段消耗完的時(shí)候進(jìn)行的，也就意味著號(hào)段臨界點(diǎn)的ID下發(fā)時(shí)間取決于下一次從DB取回號(hào)段的時(shí)間，并且在這期間進(jìn)來(lái)的請(qǐng)求也會(huì)因?yàn)镈B號(hào)段沒(méi)有取回來(lái)，導(dǎo)致線程阻塞。如果請(qǐng)求DB的網(wǎng)絡(luò)和DB的性能穩(wěn)定，這種情況對(duì)系統(tǒng)的影響是不大的，但是假如取DB的時(shí)候網(wǎng)絡(luò)發(fā)生抖動(dòng)，或者DB發(fā)生慢查詢(xún)就會(huì)導(dǎo)致整個(gè)系統(tǒng)的響應(yīng)時(shí)間變慢。
為此，我們希望DB取號(hào)段的過(guò)程能夠做到無(wú)阻塞，不需要在DB取號(hào)段的時(shí)候阻塞請(qǐng)求線程，即當(dāng)號(hào)段消費(fèi)到某個(gè)點(diǎn)時(shí)就異步的把下一個(gè)號(hào)段加載到內(nèi)存中。而不需要等到號(hào)段用盡的時(shí)候才去更新號(hào)段。這樣做就可以很大程度上的降低系統(tǒng)的TP999指標(biāo)。
詳細(xì)實(shí)現(xiàn)如下圖所示：
采用雙buffer的方式，Leaf服務(wù)內(nèi)部有兩個(gè)號(hào)段緩存區(qū)segment。當(dāng)前號(hào)段已下發(fā)10%時(shí)，如果下一個(gè)號(hào)段未更新，則另啟一個(gè)更新線程去更新下一個(gè)號(hào)段。當(dāng)前號(hào)段全部下發(fā)完后，如果下個(gè)號(hào)段準(zhǔn)備好了則切換到下個(gè)號(hào)段為當(dāng)前segment接著下發(fā)，循環(huán)往復(fù)。
主要特性如下：
1）每個(gè)biz-tag都有消費(fèi)速度監(jiān)控，通常推薦segment長(zhǎng)度設(shè)置為服務(wù)高峰期發(fā)號(hào)QPS的600倍（10分鐘），這樣即使DB宕機(jī)，Leaf仍能持續(xù)發(fā)號(hào)10-20分鐘不受影響；
2）每次請(qǐng)求來(lái)臨時(shí)都會(huì)判斷下個(gè)號(hào)段的狀態(tài)，從而更新此號(hào)段，所以偶爾的網(wǎng)絡(luò)抖動(dòng)不會(huì)影響下個(gè)號(hào)段的更新。
8.3 高可用容災(zāi)
對(duì)于上述Leaf-segment算法缺點(diǎn)的第三點(diǎn)“DB可用性”問(wèn)題：我們目前采用一主兩從的方式，同時(shí)分機(jī)房部署，Master和Slave之間采用半同步方式同步數(shù)據(jù)。同時(shí)使用公司Atlas數(shù)據(jù)庫(kù)中間件(已開(kāi)源，改名為 DBProxy)做主從切換。
當(dāng)然這種方案在一些情況會(huì)退化成異步模式，甚至在非常極端情況下仍然會(huì)造成數(shù)據(jù)不一致的情況，但是出現(xiàn)的概率非常小。如果你的系統(tǒng)要保證100%的數(shù)據(jù)強(qiáng)一致，可以選擇使用“類(lèi)Paxos算法”實(shí)現(xiàn)的強(qiáng)一致MySQL方案，如MySQL 5.7前段時(shí)間剛剛GA的MySQL Group Replication。但是運(yùn)維成本和精力都會(huì)相應(yīng)的增加，根據(jù)實(shí)際情況選型即可。
同時(shí)Leaf服務(wù)分IDC部署，內(nèi)部的服務(wù)化框架是“MTthrift RPC”。服務(wù)調(diào)用的時(shí)候，根據(jù)負(fù)載均衡算法會(huì)優(yōu)先調(diào)用同機(jī)房的Leaf服務(wù)。在該IDC內(nèi)Leaf服務(wù)不可用的時(shí)候才會(huì)選擇其他機(jī)房的Leaf服務(wù)。同時(shí)服務(wù)治理平臺(tái)OCTO還提供了針對(duì)服務(wù)的過(guò)載保護(hù)、一鍵截流、動(dòng)態(tài)流量分配等對(duì)服務(wù)的保護(hù)措施。
不過(guò)，Leaf-segment方案雖好，但必竟不適用于所有場(chǎng)景。
Leaf-segment方案可以生成趨勢(shì)遞增的ID，同時(shí)ID號(hào)是可計(jì)算的，但不適用于訂單ID生成場(chǎng)景。比如競(jìng)對(duì)在兩天中午12點(diǎn)分別下單，通過(guò)訂單id號(hào)相減就能大致計(jì)算出公司一天的訂單量，這個(gè)是不能忍受的。面對(duì)這一問(wèn)題，美團(tuán)技術(shù)團(tuán)隊(duì)實(shí)現(xiàn)了 Leaf-snowflake這個(gè)方案，請(qǐng)繼續(xù)讀下文。
9、美團(tuán)的Leaf-snowflake方案：可生成全局唯一、局部有序的ID
鑒于上節(jié)所說(shuō)：Leaf-segment方案不適用于美團(tuán)的訂單號(hào)這種場(chǎng)景（Leaf-segment方案可以生成趨勢(shì)遞增的ID，同時(shí)ID號(hào)是可計(jì)算的，很容易被猜出美團(tuán)每日的訂單量這種商業(yè)秘密），所以Leaf-snowflake方案就應(yīng)運(yùn)而生了。
9.1 基本原理
嚴(yán)格來(lái)說(shuō)，Leaf-snowflake方案是Twittersnowflake改進(jìn)版，它完全沿用snowflake方案的bit位設(shè)計(jì)（如上圖所示），即是“1+41+10+12”的方式組裝ID號(hào)。
對(duì)于workerID的分配，當(dāng)服務(wù)集群數(shù)量較小的情況下，完全可以手動(dòng)配置。Leaf服務(wù)規(guī)模較大，動(dòng)手配置成本太高。所以使用Zookeeper持久順序節(jié)點(diǎn)的特性自動(dòng)對(duì)snowflake節(jié)點(diǎn)配置wokerID。
Leaf-snowflake是按照下面幾個(gè)步驟啟動(dòng)的：
1）啟動(dòng)Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊(cè)過(guò)（是否有該順序子節(jié)點(diǎn)）；
2）如果有注冊(cè)過(guò)直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類(lèi)型ID號(hào)），啟動(dòng)服務(wù)；
3）如果沒(méi)有注冊(cè)過(guò)，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的workerID號(hào)，啟動(dòng)服務(wù)。
9.2 弱依賴(lài)ZooKeeper
除了每次會(huì)去ZK拿數(shù)據(jù)以外，也會(huì)在本機(jī)文件系統(tǒng)上緩存一個(gè)workerID文件。當(dāng)ZooKeeper出現(xiàn)問(wèn)題，恰好機(jī)器出現(xiàn)問(wèn)題需要重啟時(shí)，能保證服務(wù)能夠正常啟動(dòng)。這樣做到了對(duì)三方組件的弱依賴(lài)。一定程度上提高了SLA。
9.3 解決時(shí)鐘問(wèn)題
因?yàn)檫@種方案依賴(lài)時(shí)間（見(jiàn)本文“6、美團(tuán)為什么不直接用Snowflake算法？”一節(jié)），如果機(jī)器的時(shí)鐘發(fā)生了回?fù)埽敲淳蜁?huì)有可能生成重復(fù)的ID號(hào)，需要解決時(shí)鐘回退的問(wèn)題。
參見(jiàn)上圖整個(gè)啟動(dòng)流程圖，服務(wù)啟動(dòng)時(shí)首先檢查自己是否寫(xiě)過(guò)ZooKeeper leaf_forever節(jié)點(diǎn)：
1）若寫(xiě)過(guò)，則用自身系統(tǒng)時(shí)間與leaf_forever/${self}節(jié)點(diǎn)記錄時(shí)間做比較，若小于leaf_forever/${self}時(shí)間則認(rèn)為機(jī)器時(shí)間發(fā)生了大步長(zhǎng)回?fù)埽?wù)啟動(dòng)失敗并報(bào)警；
2）若未寫(xiě)過(guò)，證明是新服務(wù)節(jié)點(diǎn)，直接創(chuàng)建持久節(jié)點(diǎn)leaf_forever/${self}并寫(xiě)入自身系統(tǒng)時(shí)間，接下來(lái)綜合對(duì)比其余Leaf節(jié)點(diǎn)的系統(tǒng)時(shí)間來(lái)判斷自身系統(tǒng)時(shí)間是否準(zhǔn)確，具體做法是取leaf_temporary下的所有臨時(shí)節(jié)點(diǎn)(所有運(yùn)行中的Leaf-snowflake節(jié)點(diǎn))的服務(wù)IP：Port，然后通過(guò)RPC請(qǐng)求得到所有節(jié)點(diǎn)的系統(tǒng)時(shí)間，計(jì)算sum(time)/nodeSize；
3）若abs( 系統(tǒng)時(shí)間-sum(time)/nodeSize ) < 閾值，認(rèn)為當(dāng)前系統(tǒng)時(shí)間準(zhǔn)確，正常啟動(dòng)服務(wù)，同時(shí)寫(xiě)臨時(shí)節(jié)點(diǎn)leaf_temporary/${self} 維持租約；
4）否則認(rèn)為本機(jī)系統(tǒng)時(shí)間發(fā)生大步長(zhǎng)偏移，啟動(dòng)失敗并報(bào)警；
5）每隔一段時(shí)間(3s)上報(bào)自身系統(tǒng)時(shí)間寫(xiě)入leaf_forever/${self}。
由于強(qiáng)依賴(lài)時(shí)鐘，對(duì)時(shí)間的要求比較敏感，在機(jī)器工作時(shí)NTP同步也會(huì)造成秒級(jí)別的回退，建議可以直接關(guān)閉NTP同步。要么在時(shí)鐘回?fù)艿臅r(shí)候直接不提供服務(wù)直接返回ERROR_CODE，等時(shí)鐘追上即可。或者做一層重試，然后上報(bào)報(bào)警系統(tǒng)，更或者是發(fā)現(xiàn)有時(shí)鐘回?fù)苤笞詣?dòng)摘除本身節(jié)點(diǎn)并報(bào)警。
實(shí)現(xiàn)代碼如下：
//發(fā)生了回?fù)埽丝虝r(shí)間小于上次發(fā)號(hào)時(shí)間
if(timestamp < lastTimestamp) {
longoffset = lastTimestamp - timestamp;
if(offset <= 5) {
try{
//時(shí)間偏差大小小于5ms，則等待兩倍時(shí)間
wait(offset << 1);//wait
timestamp = timeGen();
if(timestamp < lastTimestamp) {
//還是小于，拋異常并上報(bào)
throwClockBackwardsEx(timestamp);
}
} catch(InterruptedException e) {
throwe;
}
} else{
//throw
throwClockBackwardsEx(timestamp);
}
}
//分配ID
從上線情況來(lái)看，在2017年閏秒出現(xiàn)那一次出現(xiàn)過(guò)部分機(jī)器回?fù)埽捎贚eaf-snowflake的策略保證，成功避免了對(duì)業(yè)務(wù)造成的影響。
PS：網(wǎng)上已有人按照文章中Leaf-snowflake方案做了一個(gè)開(kāi)源版本，可以學(xué)習(xí)一下，項(xiàng)目地址：https://github.com/weizhenyi/leaf-snowflake。作者宣稱(chēng)的測(cè)試情況，TPS：1W+/sec，單機(jī)190秒生成了200W無(wú)重復(fù)，單調(diào)遞增的long型整數(shù)ID。
10、本文小結(jié)
Leaf在美團(tuán)點(diǎn)評(píng)公司內(nèi)部服務(wù)包含金融、支付交易、餐飲、外賣(mài)、酒店旅游、貓眼電影等眾多業(yè)務(wù)線。
目前Leaf的性能在4C8G的機(jī)器上QPS能壓測(cè)到近5w/s，TP999 1ms，已經(jīng)能夠滿足大部分的業(yè)務(wù)的需求。每天提供億數(shù)量級(jí)的調(diào)用量，作為公司內(nèi)部公共的基礎(chǔ)技術(shù)設(shè)施，必須保證高SLA和高性能的服務(wù)，我們目前還僅僅達(dá)到了及格線，還有很多提高的空間。
附錄：更多IM開(kāi)發(fā)熱門(mén)技術(shù)文章
《新手入門(mén)一篇就夠：從零開(kāi)發(fā)移動(dòng)端IM》
《移動(dòng)端IM開(kāi)發(fā)者必讀(一)：通俗易懂，理解移動(dòng)網(wǎng)絡(luò)的“弱”和“慢”》
《移動(dòng)端IM開(kāi)發(fā)者必讀(二)：史上最全移動(dòng)弱網(wǎng)絡(luò)優(yōu)化方法總結(jié)》
《從客戶(hù)端的角度來(lái)談?wù)勔苿?dòng)端IM的消息可靠性和送達(dá)機(jī)制》
《現(xiàn)代移動(dòng)端網(wǎng)絡(luò)短連接的優(yōu)化手段總結(jié)：請(qǐng)求速度、弱網(wǎng)適應(yīng)、安全保障》
《騰訊技術(shù)分享：社交網(wǎng)絡(luò)圖片的帶寬壓縮技術(shù)演進(jìn)之路》
《小白必讀：閑話HTTP短連接中的Session和Token》
《IM開(kāi)發(fā)基礎(chǔ)知識(shí)補(bǔ)課：正確理解前置HTTP SSO單點(diǎn)登陸接口的原理》
《移動(dòng)端IM中大規(guī)模群消息的推送如何保證效率、實(shí)時(shí)性？》
《移動(dòng)端IM開(kāi)發(fā)需要面對(duì)的技術(shù)問(wèn)題》
《開(kāi)發(fā)IM是自己設(shè)計(jì)協(xié)議用字節(jié)流好還是字符流好？》
《請(qǐng)問(wèn)有人知道語(yǔ)音留言聊天的主流實(shí)現(xiàn)方式嗎？》
《IM消息送達(dá)保證機(jī)制實(shí)現(xiàn)(一)：保證在線實(shí)時(shí)消息的可靠投遞》
《IM消息送達(dá)保證機(jī)制實(shí)現(xiàn)(二)：保證離線消息的可靠投遞》
《如何保證IM實(shí)時(shí)消息的“時(shí)序性”與“一致性”？》
《一個(gè)低成本確保IM消息時(shí)序的方法探討》
《IM單聊和群聊中的在線狀態(tài)同步應(yīng)該用“推”還是“拉”？》
《IM群聊消息如此復(fù)雜，如何保證不丟不重？》
《談?wù)勔苿?dòng)端 IM 開(kāi)發(fā)中登錄請(qǐng)求的優(yōu)化》
《移動(dòng)端IM登錄時(shí)拉取數(shù)據(jù)如何作到省流量？》
《淺談移動(dòng)端IM的多點(diǎn)登陸和消息漫游原理》
《完全自已開(kāi)發(fā)的IM該如何設(shè)計(jì)“失敗重試”機(jī)制？》
《通俗易懂：基于集群的移動(dòng)端IM接入層負(fù)載均衡方案分享》
《微信對(duì)網(wǎng)絡(luò)影響的技術(shù)試驗(yàn)及分析（論文全文）》
《即時(shí)通訊系統(tǒng)的原理、技術(shù)和應(yīng)用（技術(shù)論文）》
《開(kāi)源IM工程“蘑菇街TeamTalk”的現(xiàn)狀：一場(chǎng)有始無(wú)終的開(kāi)源秀》
《QQ音樂(lè)團(tuán)隊(duì)分享：Android中的圖片壓縮技術(shù)詳解（上篇）》
《QQ音樂(lè)團(tuán)隊(duì)分享：Android中的圖片壓縮技術(shù)詳解（下篇）》
《騰訊原創(chuàng)分享(一)：如何大幅提升移動(dòng)網(wǎng)絡(luò)下手機(jī)QQ的圖片傳輸速度和成功率》
《騰訊原創(chuàng)分享(二)：如何大幅壓縮移動(dòng)網(wǎng)絡(luò)下APP的流量消耗（上篇）》
《騰訊原創(chuàng)分享(三)：如何大幅壓縮移動(dòng)網(wǎng)絡(luò)下APP的流量消耗（下篇）》
《如約而至：微信自用的移動(dòng)端IM網(wǎng)絡(luò)層跨平臺(tái)組件庫(kù)Mars已正式開(kāi)源》
《基于社交網(wǎng)絡(luò)的Yelp是如何實(shí)現(xiàn)海量用戶(hù)圖片的無(wú)損壓縮的？》
《騰訊技術(shù)分享：騰訊是如何大幅降低帶寬和網(wǎng)絡(luò)流量的(圖片壓縮篇)》
《騰訊技術(shù)分享：騰訊是如何大幅降低帶寬和網(wǎng)絡(luò)流量的(音視頻技術(shù)篇)》
《字符編碼那點(diǎn)事：快速理解ASCII、Unicode、GBK和UTF-8》
《全面掌握移動(dòng)端主流圖片格式的特點(diǎn)、性能、調(diào)優(yōu)等》
《子彈短信光鮮的背后：網(wǎng)易云信首席架構(gòu)師分享億級(jí)IM平臺(tái)的技術(shù)實(shí)踐》
《IM開(kāi)發(fā)基礎(chǔ)知識(shí)補(bǔ)課(五)：通俗易懂，正確理解并用好MQ消息隊(duì)列》
《微信技術(shù)分享：微信的海量IM聊天消息序列號(hào)生成實(shí)踐（算法原理篇）》
《自已開(kāi)發(fā)IM有那么難嗎？手把手教你自擼一個(gè)Andriod版簡(jiǎn)易IM (有源碼)》
《融云技術(shù)分享：解密融云IM產(chǎn)品的聊天消息ID生成策略》
>> 更多同類(lèi)文章 ……
（本文同步發(fā)布于：http://www.52im.net/thread-2751-1-1.html）