默認
打賞 發表評論 4
想開發IM:買成品怕坑?租第3方怕貴?找開源自已擼?盡量別走彎路了... 找站長給點建議
美團技術分享:深度解密美團的分布式ID生成算法
閱讀(5569) | 評論(4 收藏5 淘帖1 3

本文來自美團技術團隊“照東”的分享,原題《Leaf——美團點評分布式ID生成系統》,即時通訊網收錄時有勘誤、修訂并重新排版,感謝原作者的分享。


1、引言


鑒于IM系統中聊天消息ID生成算法和生成策略的重要性(因為某種意義上來說:聊天消息ID的優劣決定了IM應用層某些功能實現的難易度),所以即時通訊網近期正在著重整理有關IM中的聊天消息ID算法方面的文章,包括微信團隊的這篇《微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)》,以及融云分享的《融云技術分享:解密融云IM產品的聊天消息ID生成策略》一文。

本文分享了美團系統中正在使用的兩種ID生成算法:

  • 1)Leaf-segment方案:可生成全局唯一、全局有序的ID;
  • 2)Leaf-snowflake方案:可生成全局唯一、局部有序的ID。

對于美團的Leaf-segment這個ID生成方案,因為生成的ID全局唯一、全局有序,所以非常適合IM這種應用場景,這也是即時通訊網整理并分享給社區的原因。

友情提示:IM系統中的消息ID不同于電商等傳統信息系統,IM中的消息ID通常較少用于服務端架構中的檢索目的(例外是:消息撤回等使用頻率較低的功能中會用到),所以服務端架構中的ID查詢性能上可以不必追求極致(必竟IM消息對應于人的自然溝通,通常都是以時間為檢索條件,比如離線消息拉取、群消息拉取、漫游消息拉取等),所以在學習諸如美團的ID生成算法時,沒有必要生搬硬套,適度借鑒,按照IM系統的特性進行融會貫通地設計才是最佳實踐

免責申明:本文來自美團官方技術團隊的分享,僅用于技術交流學習和研究目的,請勿用于非法用途,文中如涉及商業秘密,請告之我處理!

美團技術分享:深度解密美團的分布式ID生成算法_cccc.jpg

2、關于作者


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

3、相關文章



4、正文概述


在復雜分布式系統中,往往需要對大量的數據和消息進行唯一標識。如在美團點評的金融、支付、餐飲、酒店、貓眼電影等產品的系統中,數據日漸增長,對數據分庫分表后需要有一個唯一ID來標識一條數據或消息,數據庫的自增ID顯然不能滿足需求;特別一點的如訂單、騎手、優惠券也都需要有唯一ID做標識。此時一個能夠生成全局唯一ID的系統是非常必要的。

概括下來,那業務系統對ID號的要求有哪些呢?

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

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

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

由此總結下一個分布式ID生成系統應做到如下幾點:

  • 1)平均延遲和TP999延遲都要盡可能低;
  • 2)可用性5個9;
  • 3)高QPS。

5、美團為什么沒用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有以下優點和缺點。

優點:
性能非常高:本地生成,沒有網絡消耗。

缺點:
  • 1)不易于存儲:UUID太長,16字節128位,通常以36長度的字符串表示,很多場景不適用;
  • 2)信息不安全:基于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的無序性可能會引起數據位置頻繁變動,嚴重影響性能。

總之,UUID有很多合適的應用場景,但對于美團點評相關的業務系統來說,UUID顯然不是最佳選擇。

6、美團為什么不直接用Snowflake算法?


6.1SnowFlake算法原理


SnowFlake 算法,是 Twitter 開源的分布式 ID 生成算法。其核心思想就是:使用一個 64 bit 的 long 型的數字作為全局唯一 ID。

這 64 個 bit 中,其中 1 個 bit 是不用的,然后用其中的 41 bit 作為毫秒數,用 10 bit 作為工作機器 ID,12 bit 作為序列號。

SnowFlake的ID構成:
美團技術分享:深度解密美團的分布式ID生成算法_1.png

SnowFlake的ID樣本:
美團技術分享:深度解密美團的分布式ID生成算法_aaa.jpg

給大家舉個例子吧,如上圖所示,比如下面那個 64 bit 的 long 型數字:

  • 1)第一個部分,是 1 個 bit:0,這個是無意義的;
  • 2)第二個部分,是 41 個 bit:表示的是時間戳;
  • 3)第三個部分,是 5 個 bit:表示的是機房 ID,10001;
  • 4)第四個部分,是 5 個 bit:表示的是機器 ID,1 1001;
  • 5)第五個部分,是 12 個 bit:表示的序號,就是某個機房某臺機器上這一毫秒內同時生成的 ID 的序號,0000 00000000。

① 1 bit:是不用的,為啥呢?

因為二進制里第一個 bit 為如果是 1,那么都是負數,但是我們生成的 ID 都是正數,所以第一個 bit 統一都是 0。

② 41 bit:表示的是時間戳,單位是毫秒。

41 bit 可以表示的數字多達 2^41 - 1,也就是可以標識 2 ^ 41 - 1 個毫秒值,換算成年就是表示 69 年的時間。

③ 10 bit:記錄工作機器 ID,代表的是這個服務最多可以部署在 2^10 臺機器上,也就是 1024 臺機器。

但是 10 bit 里 5 個 bit 代表機房 id,5 個 bit 代表機器 ID。意思就是最多代表 2 ^ 5 個機房(32 個機房),每個機房里可以代表 2 ^ 5 個機器(32 臺機器)。

④12 bit:這個是用來記錄同一個毫秒內產生的不同 ID。

12 bit 可以代表的最大正整數是 2 ^ 12 - 1 = 4096,也就是說可以用這個 12 bit 代表的數字來區分同一個毫秒內的 4096 個不同的 ID。理論上snowflake方案的QPS約為409.6w/s,這種分配方式可以保證在任何一個IDC的任何一臺機器在任意毫秒內生成的ID都是不同的。

簡單來說,你的某個服務假設要生成一個全局唯一 ID,那么就可以發送一個請求給部署了 SnowFlake 算法的系統,由這個 SnowFlake 算法系統來生成唯一 ID。

  • 1)這個 SnowFlake 算法系統首先肯定是知道自己所在的機房和機器的,比如機房 ID = 17,機器 ID = 12;
  • 2)接著 SnowFlake 算法系統接收到這個請求之后,首先就會用二進制位運算的方式生成一個 64 bit 的 long 型 ID,64 個 bit 中的第一個 bit 是無意義的;
  • 3)接著 41 個 bit,就可以用當前時間戳(單位到毫秒),然后接著 5 個 bit 設置上這個機房 id,還有 5 個 bit 設置上機器 ID;
  • 4)最后再判斷一下,當前這臺機房的這臺機器上這一毫秒內,這是第幾個請求,給這次生成 ID 的請求累加一個序號,作為最后的 12 個 bit。

最終一個 64 個 bit 的 ID 就出來了,類似于:
美團技術分享:深度解密美團的分布式ID生成算法_bbb.jpg

這個算法可以保證說,一個機房的一臺機器上,在同一毫秒內,生成了一個唯一的 ID。可能一個毫秒內會生成多個 ID,但是有最后 12 個 bit 的序號來區分開來。

下面我們簡單看看這個 SnowFlake 算法的一個代碼實現,這就是個示例,大家如果理解了這個意思之后,以后可以自己嘗試改造這個算法。

總之就是用一個 64 bit 的數字中各個 bit 位來設置不同的標志位,區分每一個 ID。

SnowFlake 算法的一個典型Java實現代碼,可以參見文章中的第“6.5 方案四:SnowFlake 算法的思想分析”節:《通俗易懂:如何設計能支撐百萬并發的數據庫架構?》。

6.2對于美團來說,SnowFlake算法的優缺點


對于美團的業務系統來說,這種方式的優缺點如下。

► 優點:
  • 1)毫秒數在高位,自增序列在低位,整個ID都是趨勢遞增的;
  • 2)不依賴數據庫等第三方系統,以服務的方式部署,穩定性更高,生成ID的性能也是非常高的;
  • 3)可以根據自身業務特性分配bit位,非常靈活。

► 缺點:
強依賴機器時鐘,如果機器上時鐘回撥,會導致發號重復或者服務會處于不可用狀態。

► 應用舉例——Mongdb的objectID:
MongoDB官方文檔 ObjectID 可以算作是和snowflake類似方法,通過“時間+機器碼+pid+inc”共12個字節,通過4+3+2+3的方式最終標識成一個24長度的十六進制字符。

7、數據庫的自增ID對于美團來說,也不合適


以MySQL舉例,利用給字段設置auto_increment_incrementauto_increment_offset來保證ID自增,每次業務使用下列SQL讀寫MySQL得到ID號。
begin;
REPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID();
commit;

美團技術分享:深度解密美團的分布式ID生成算法_2.png

這種方案的優缺點如下。

優點:

  • 1)非常簡單,利用現有數據庫系統的功能實現,成本小,有DBA專業維護;
  • 2)ID號單調自增,可以實現一些對ID有特殊要求的業務。

缺點:

  • 1)強依賴DB,當DB異常時整個系統不可用,屬于致命問題。配置主從復制可以盡可能的增加可用性,但是數據一致性在特殊情況下難以保證。主從切換時的不一致可能會導致重復發號;
  • 2)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那么整個架構就變成了如下圖所示:
美團技術分享:深度解密美團的分布式ID生成算法_3.png

這種必讀是后的架構貌似能夠滿足性能的需求,但有以下幾個缺點:

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

綜合對比上述幾種方案,每種方案都不完全符合我們的要求。所以美團建立了Leaf工程(Leaf這個名字是來自德國哲學家、數學家萊布尼茨的一句話: >There are no two identical leaves in the world > “世界上沒有兩片相同的樹葉”),分別在上述第二種(Snowflake)和第三種(數據庫自增ID)方案上做了相應的優化,實現了Leaf-snowflake和Leaf-segment方案。接下來,我們詳細介紹這兩種方案的實現思路。

8、美團的Leaf-segment方案:可生成全局唯一、全局有序的ID


8.1基本原理


美團的Leaf-segment方案,實際上是在上面介紹的數據庫自增ID方案上的一種改進方案,它可生成全局唯一、全局有序的ID,可以用于:事務版本號、IM聊天中的增量消息、全局排序等業務中。

美團的Leaf-segment對數據庫自增ID方案做了如下改變:

  • 1)原方案每次獲取ID都得讀寫一次數據庫,造成數據庫壓力大。改為利用proxy server批量獲取,每次獲取一個segment(step決定大小)號段的值。用完之后再去數據庫獲取新的號段,可以大大的減輕數據庫的壓力;
  • 2)各個業務不同的發號需求用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,大致架構如下圖所示:
美團技術分享:深度解密美團的分布式ID生成算法_4.png

test_tag在第一臺Leaf機器上是1~1000的號段,當這個號段用完時,會去加載另一個長度為step=1000的號段,假設另外兩臺號段都沒有更新,這個時候第一臺機器新加載的號段就應該是3001~4000。

同時數據庫對應的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

這種模式有以下優缺點。

優點:

  • 1)Leaf服務可以很方便的線性擴展,性能完全能夠支撐大多數業務場景;
  • 2)ID號碼是趨勢遞增的8byte的64位數字,滿足上述數據庫存儲的主鍵要求;
  • 3)容災性高:Leaf服務內部有號段緩存,即使DB宕機,短時間內Leaf仍能正常對外提供服務;
  • 4)可以自定義max_id的大小,非常方便業務從原有的ID方式上遷移過來。

缺點:

  • 1)ID號碼不夠隨機,能夠泄露發號數量的信息,不太安全;
  • 2)TP999數據波動大,當號段使用完之后還是會hang在更新數據庫的I/O上,tg999數據會出現偶爾的尖刺;
  • 3)DB宕機會造成整個系統不可用。

8.2雙buffer優化


對于上述第二個缺點,Leaf-segment方案做了一些優化,簡單的說就是:

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


為此,我們希望DB取號段的過程能夠做到無阻塞,不需要在DB取號段的時候阻塞請求線程,即當號段消費到某個點時就異步的把下一個號段加載到內存中。而不需要等到號段用盡的時候才去更新號段。這樣做就可以很大程度上的降低系統的TP999指標。

詳細實現如下圖所示:
美團技術分享:深度解密美團的分布式ID生成算法_5.png

采用雙buffer的方式,Leaf服務內部有兩個號段緩存區segment。當前號段已下發10%時,如果下一個號段未更新,則另啟一個更新線程去更新下一個號段。當前號段全部下發完后,如果下個號段準備好了則切換到下個號段為當前segment接著下發,循環往復。

主要特性如下:

  • 1)每個biz-tag都有消費速度監控,通常推薦segment長度設置為服務高峰期發號QPS的600倍(10分鐘),這樣即使DB宕機,Leaf仍能持續發號10-20分鐘不受影響;
  • 2)每次請求來臨時都會判斷下個號段的狀態,從而更新此號段,所以偶爾的網絡抖動不會影響下個號段的更新。

8.3高可用容災


對于上述Leaf-segment算法缺點的第三點“DB可用性”問題:我們目前采用一主兩從的方式,同時分機房部署,Master和Slave之間采用半同步方式同步數據。同時使用公司Atlas數據庫中間件(已開源,改名為 DBProxy)做主從切換。

當然這種方案在一些情況會退化成異步模式,甚至在非常極端情況下仍然會造成數據不一致的情況,但是出現的概率非常小。如果你的系統要保證100%的數據強一致,可以選擇使用“類Paxos算法”實現的強一致MySQL方案,如MySQL 5.7前段時間剛剛GA的MySQL Group Replication。但是運維成本和精力都會相應的增加,根據實際情況選型即可。

美團技術分享:深度解密美團的分布式ID生成算法_6.png

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

不過,Leaf-segment方案雖好,但必竟不適用于所有場景。

Leaf-segment方案可以生成趨勢遞增的ID,同時ID號是可計算的,但不適用于訂單ID生成場景。比如競對在兩天中午12點分別下單,通過訂單id號相減就能大致計算出公司一天的訂單量,這個是不能忍受的。面對這一問題,美團技術團隊實現了 Leaf-snowflake這個方案,請繼續讀下文。

9、美團的Leaf-snowflake方案:可生成全局唯一、局部有序的ID


鑒于上節所說:Leaf-segment方案不適用于美團的訂單號這種場景(Leaf-segment方案可以生成趨勢遞增的ID,同時ID號是可計算的,很容易被猜出美團每日的訂單量這種商業秘密),所以Leaf-snowflake方案就應運而生了。

9.1基本原理


美團技術分享:深度解密美團的分布式ID生成算法_7.png

嚴格來說,Leaf-snowflake方案是Twittersnowflake改進版,它完全沿用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號,啟動服務。

美團技術分享:深度解密美團的分布式ID生成算法_8.png

9.2弱依賴ZooKeeper


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

9.3解決時鐘問題


因為這種方案依賴時間(見本文“6、美團為什么不直接用Snowflake算法?”一節),如果機器的時鐘發生了回撥,那么就會有可能生成重復的ID號,需要解決時鐘回退的問題。

美團技術分享:深度解密美團的分布式ID生成算法_9.png

參見上圖整個啟動流程圖,服務啟動時首先檢查自己是否寫過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 <= 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年閏秒出現那一次出現過部分機器回撥,由于Leaf-snowflake的策略保證,成功避免了對業務造成的影響

PS:網上已有人按照文章中Leaf-snowflake方案做了一個開源版本,可以學習一下,項目地址:https://github.com/weizhenyi/leaf-snowflake。作者宣稱的測試情況,TPS:1W+/sec,單機190秒生成了200W無重復,單調遞增的long型整數ID。

10、本文小結


Leaf在美團點評公司內部服務包含金融、支付交易、餐飲、外賣、酒店旅游、貓眼電影等眾多業務線。

目前Leaf的性能在4C8G的機器上QPS能壓測到近5w/s,TP999 1ms,已經能夠滿足大部分的業務的需求。每天提供億數量級的調用量,作為公司內部公共的基礎技術設施,必須保證高SLA和高性能的服務,我們目前還僅僅達到了及格線,還有很多提高的空間。

附錄:更多IM開發熱門技術文章


新手入門一篇就夠:從零開發移動端IM
移動端IM開發者必讀(一):通俗易懂,理解移動網絡的“弱”和“慢”
移動端IM開發者必讀(二):史上最全移動弱網絡優化方法總結
從客戶端的角度來談談移動端IM的消息可靠性和送達機制
現代移動端網絡短連接的優化手段總結:請求速度、弱網適應、安全保障
騰訊技術分享:社交網絡圖片的帶寬壓縮技術演進之路
小白必讀:閑話HTTP短連接中的Session和Token
IM開發基礎知識補課:正確理解前置HTTP SSO單點登陸接口的原理
移動端IM中大規模群消息的推送如何保證效率、實時性?
移動端IM開發需要面對的技術問題
開發IM是自己設計協議用字節流好還是字符流好?
請問有人知道語音留言聊天的主流實現方式嗎?
IM消息送達保證機制實現(一):保證在線實時消息的可靠投遞
IM消息送達保證機制實現(二):保證離線消息的可靠投遞
如何保證IM實時消息的“時序性”與“一致性”?
一個低成本確保IM消息時序的方法探討
IM單聊和群聊中的在線狀態同步應該用“推”還是“拉”?
IM群聊消息如此復雜,如何保證不丟不重?
談談移動端 IM 開發中登錄請求的優化
移動端IM登錄時拉取數據如何作到省流量?
淺談移動端IM的多點登陸和消息漫游原理
完全自已開發的IM該如何設計“失敗重試”機制?
通俗易懂:基于集群的移動端IM接入層負載均衡方案分享
微信對網絡影響的技術試驗及分析(論文全文)
即時通訊系統的原理、技術和應用(技術論文)
開源IM工程“蘑菇街TeamTalk”的現狀:一場有始無終的開源秀
QQ音樂團隊分享:Android中的圖片壓縮技術詳解(上篇)
QQ音樂團隊分享:Android中的圖片壓縮技術詳解(下篇)
騰訊原創分享(一):如何大幅提升移動網絡下手機QQ的圖片傳輸速度和成功率
騰訊原創分享(二):如何大幅壓縮移動網絡下APP的流量消耗(上篇)
騰訊原創分享(三):如何大幅壓縮移動網絡下APP的流量消耗(下篇)
如約而至:微信自用的移動端IM網絡層跨平臺組件庫Mars已正式開源
基于社交網絡的Yelp是如何實現海量用戶圖片的無損壓縮的?
騰訊技術分享:騰訊是如何大幅降低帶寬和網絡流量的(圖片壓縮篇)
騰訊技術分享:騰訊是如何大幅降低帶寬和網絡流量的(音視頻技術篇)
字符編碼那點事:快速理解ASCII、Unicode、GBK和UTF-8
全面掌握移動端主流圖片格式的特點、性能、調優等
子彈短信光鮮的背后:網易云信首席架構師分享億級IM平臺的技術實踐
IM開發基礎知識補課(五):通俗易懂,正確理解并用好MQ消息隊列
微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)
自已開發IM有那么難嗎?手把手教你自擼一個Andriod版簡易IM (有源碼)
融云技術分享:解密融云IM產品的聊天消息ID生成策略
>> 更多同類文章 ……

即時通訊網 - 即時通訊開發者社區! 來源: - 即時通訊開發者社區!

標簽:ID生成 美團
上一篇:別做夢了,社交產品哪有那么容易成功下一篇:微信那么牛,為什么海外成功的卻是抖音?

本帖已收錄至以下技術專輯

推薦方案
評論 4
美團的這兩種id生成算法算起來很牛,不過可能不太適合中小場景,
還是有點復雜,
技術不行的程序員可能hold不住。

那個leaf-snowflake值得研究一下,這玩意很實用
簽名: 好想把妹!
引用:不要·不要 發表于 2019-09-23 13:12
美團的這兩種id生成算法算起來很牛,不過可能不太適合中小場景,
還是有點復雜,
技術不行的程序員可能ho ...

小場景直接自增就夠用了,不需要這么大的刀,殺蒼蠅。
精辟
簽名: 加班、加班、加班
引用:laojichuxin 發表于 2019-09-30 17:19
小場景直接自增就夠用了,不需要這么大的刀,殺蒼蠅。

活體解刨蒼蠅
簽名: 《IM里“附近的人”功能實現原理是什么?如何高效率地實現它?》http://www.hqkrtb.live/thread-2827-1-1.html
打賞樓主 ×
使用微信打賞! 使用支付寶打賞!

返回頂部
乐彩网17500