默認
打賞 發表評論 8
想開發IM:買成品怕坑?租第3方怕貴?找開源自已擼?盡量別走彎路了... 找站長給點建議
微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)
閱讀(25051) | 評論(8 收藏8 淘帖3 3

1、點評


對于IM系統來說,如何做到IM聊天消息離線差異拉取(差異拉取是為了節省流量)、消息多端同步、消息順序保證等,是典型的IM技術難點。

就像即時通訊網整理的以下IM開發干貨系列一樣:


上面這些文章所涉及的IM聊天消息的省流量、可靠投遞、離線拉取、時序性、一致性、多端同步等等問題,總結下來其實就是要解決好一個問題:即如何保證聊天消息的唯一性判定和順序判定

很多即時通訊網的群友在討論這個問題的時候,普遍考慮的是使用整型自增序列號作為消息ID(即MsgId):這樣既能保證消息的唯一性又方便保證順序性,但問題是在分布式情況下是很難保證消息id的唯一性且順序遞增的,維護id生成的一致性難度太大了(網絡延遲、調試出錯等等都可能導致不同的機器取到的消息id存在碰撞的可能)。

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_22.jpg

不過,通過本文中微信團隊分享的微信消息序列號生成思路,實際上要解決消息的唯一性、順序性問題,可以將一個技術點分解成兩個:即將原先每條消息一個自增且唯一的消息ID分拆成兩個關鍵屬性——消息ID(msgId)、消息序列號(seqId,即消息ID只要保證唯一性而不需要兼顧順序性(比如直接用UUID)、消息序列號只要保證順序性而不需要兼顧唯一性(就像本文中微信的思路一樣),這樣的技術分解就能很好的解決原本一個消息ID既要保證唯一性又要保證順序性的難題。

那么,如何優雅地解決“消息序列號只要保證順序性而不需要兼顧唯一性”的問題呢?這就是本文所要分享的內容,強烈建議深入理解和閱讀

本文因篇幅較長,分為上下兩篇,敬請點擊閱讀:
上篇:《微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)》(本文
下篇:《微信技術分享:微信的海量IM聊天消息序列號生成實踐(容災方案篇)

推薦:融云團隊分享的消息ID生成文章也值得一讀《融云技術分享:解密融云IM產品的聊天消息ID生成策略》,美團的這篇也不錯《美團技術分享:深度解密美團的分布式ID生成算法》。

2、正文引言


微信在立項之初,就已確立了利用數據版本號(注:具體的實現也就是本文要分享的消息序列號)實現終端與后臺的數據增量同步機制,確保發消息時消息可靠送達對方手機,避免了大量潛在的家庭糾紛。時至今日,微信已經走過第五個年頭,這套同步機制仍然在消息收發、朋友圈通知、好友數據更新等需要數據同步的地方發揮著核心的作用。

而在這同步機制的背后,需要一個高可用、高可靠的消息序列號生成器來產生同步數據用的版本號(注:因為序列號天生的遞增特性,完全可以當版本號來使用,但又不僅限于版本號的用途)。這個消息序列號生成器我們微信內部稱之為 seqsvr ,目前已經發展為一個每天萬億級調用的重量級系統,其中每次申請序列號平時調用耗時1ms,99.9%的調用耗時小于3ms,服務部署于數百臺4核 CPU 服務器上。

本篇將重點介紹微信的消息序列號生成器 seqsvr 的算法原理、架構核心思想,以及 seqsvr 隨著業務量快速上漲所做的架構演變下篇《微信技術分享:微信的海量IM聊天消息序列號生成實踐(容災方案篇)》會著重討論分布式容災方案,敬請關注)。

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_1370849023895.jpg

3、關于作者


曾欽松:微信高級工程師,負責過微信基礎架構、微信翻譯引擎、微信圍棋PhoenixGo,致力于高可用高性能后臺系統的設計與研發。2011年畢業于西安電子科技大學,早先曾在騰訊搜搜從事檢索架構、分布式數據庫方面的工作。

4、技術思路


微信服務器端為每一份需要與客戶端同步的數據(例如聊天消息)都會賦予一個唯一的、遞增的序列號(后文稱為 sequence ),作為這份數據的版本號(這是利用了序列號遞增的特性)。在客戶端與服務器端同步的時候,客戶端會帶上已經同步下去數據的最大版本號,后臺會根據客戶端最大版本號與服務器端的最大版本號,計算出需要同步的增量數據,返回給客戶端。這樣不僅保證了客戶端與服務器端的數據同步的可靠性,同時也大幅減少了同步時的冗余數據(就像這篇文章中討論的一樣:《如何保證IM實時消息的“時序性”與“一致性”?)。

這里不用樂觀鎖機制來生成版本號,而是使用了一個獨立的 seqsvr 來處理序列號操作:

  • 1)一方面因為業務有大量的 sequence 查詢需求——查詢已經分配出去的最后一個 sequence ,而基于 seqsvr 的查詢操作可以做到非常輕量級,避免對存儲層的大量 IO 查詢操作;
  • 2)另一方面微信用戶的不同種類的數據存在不同的 Key-Value 系統中,使用統一的序列號有助于避免重復開發,同時業務邏輯可以很方便地判斷一個用戶的各類數據是否有更新。

從 seqsvr 申請的、用作數據版本號的 sequence ,具有兩種基本的性質:

  • 1)遞增的64位整型變量;
  • 2)每個用戶都有自己獨立的64位 sequence 空間。

舉個例子,小明當前申請的 sequence 為100,那么他下一次申請的 sequence ,可能為101,也可能是110,總之一定大于之前申請的100。而小紅呢,她的 sequence 與小明的 sequence 是獨立開的,假如她當前申請到的 sequence 為50,然后期間不管小明申請多少次 sequence 怎么折騰,都不會影響到她下一次申請到的值(很可能是51)。

這里用了每個用戶獨立的64位 sequence 的體系,而不是用一個全局的64位(或更高位) sequence ,很大原因是全局唯一的 sequence 會有非常嚴重的申請互斥問題,不容易去實現一個高性能高可靠的架構。對微信業務來說,每個用戶獨立的64位 sequence 空間已經滿足業務要求。

目前 sequence 用在終端與后臺的數據同步外,同時也廣泛用于微信后臺邏輯層的基礎數據一致性cache中,大幅減少邏輯層對存儲層的訪問。雖然一個用于終端——后臺數據同步,一個用于后臺cache的一致性保證,場景大不相同。

但我們仔細分析就會發現,兩個場景都是利用 sequence 可靠遞增的性質來實現數據的一致性保證,這就要求我們的 seqsvr 保證分配出去的 sequence 是穩定遞增的,一旦出現回退必然導致各種數據錯亂、消息消失;另外,這兩個場景都非常普遍,我們在使用微信的時候會不知不覺地對應到這兩個場景:小明給小紅發消息、小紅拉黑小明、小明發一條失戀狀態的朋友圈,一次簡單的分手背后可能申請了無數次 sequence。

微信目前擁有數億的活躍用戶,每時每刻都會有海量 sequence 申請,這對 seqsvr 的設計也是個極大的挑戰。那么,既要 sequence 可靠遞增,又要能頂住海量的訪問,要如何設計 seqsvr 的架構?我們先從 seqsvr 的架構原型說起。

5、具體的技術架構原型


不考慮 seqsvr 的具體架構的話,它應該是一個巨大的64位數組,而我們每一個微信用戶,都在這個大數組里獨占一格8 bytes 的空間,這個格子就放著用戶已經分配出去的最后一個 sequence:cur_seq。每個用戶來申請sequence的時候,只需要將用戶的cur_seq+=1,保存回數組,并返回給用戶。

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_a.jpg
▲ 圖1:小明申請了一個sequence,返回101

5.1預分配中間層


任何一件看起來很簡單的事,在海量的訪問量下都會變得不簡單。前文提到,seqsvr 需要保證分配出去的sequence 遞增(數據可靠),還需要滿足海量的訪問量(每天接近萬億級別的訪問)。滿足數據可靠的話,我們很容易想到把數據持久化到硬盤,但是按照目前每秒千萬級的訪問量(~10^7 QPS),基本沒有任何硬盤系統能扛住。

后臺架構設計很多時候是一門關于權衡的哲學,針對不同的場景去考慮能不能降低某方面的要求,以換取其它方面的提升。仔細考慮我們的需求,我們只要求遞增,并沒有要求連續,也就是說出現一大段跳躍是允許的(例如分配出的sequence序列:1,2,3,10,100,101)。

于是我們實現了一個簡單優雅的策略:

  • 1)內存中儲存最近一個分配出去的sequence:cur_seq,以及分配上限:max_seq;
  • 2)分配sequence時,將cur_seq++,同時與分配上限max_seq比較:如果cur_seq > max_seq,將分配上限提升一個步長max_seq += step,并持久化max_seq;
  • 3)重啟時,讀出持久化的max_seq,賦值給cur_seq。

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_b.jpg
▲ 圖2:小明、小紅、小白都各自申請了一個sequence,但只有小白的max_seq增加了步長100

這樣通過增加一個預分配 sequence 的中間層,在保證 sequence 不回退的前提下,大幅地提升了分配 sequence 的性能。實際應用中每次提升的步長為10000,那么持久化的硬盤IO次數從之前~10^7 QPS降低到~10^3 QPS,處于可接受范圍。在正常運作時分配出去的sequence是順序遞增的,只有在機器重啟后,第一次分配的 sequence 會產生一個比較大的跳躍,跳躍大小取決于步長大小。

5.2分號段共享存儲


請求帶來的硬盤IO問題解決了,可以支持服務平穩運行,但該模型還是存在一個問題:重啟時要讀取大量的max_seq數據加載到內存中。

我們可以簡單計算下,以目前 uid(用戶唯一ID)上限2^32個、一個 max_seq 8bytes 的空間,數據大小一共為32GB,從硬盤加載需要不少時間。另一方面,出于數據可靠性的考慮,必然需要一個可靠存儲系統來保存max_seq數據,重啟時通過網絡從該可靠存儲系統加載數據。如果max_seq數據過大的話,會導致重啟時在數據傳輸花費大量時間,造成一段時間不可服務。

為了解決這個問題,我們引入號段 Section 的概念,uid 相鄰的一段用戶屬于一個號段,而同個號段內的用戶共享一個 max_seq,這樣大幅減少了max_seq 數據的大小,同時也降低了IO次數

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_c.jpg
▲ 圖3:小明、小紅、小白屬于同個Section,他們共用一個max_seq。在每個人都申請一個sequence的時候,只有小白突破了max_seq上限,需要更新max_seq并持久化

目前 seqsvr 一個 Section 包含10萬個 uid,max_seq 數據只有300+KB,為我們實現從可靠存儲系統讀取max_seq 數據重啟打下基礎。

5.3工程實現


工程實現在上面兩個策略上做了一些調整,主要是出于數據可靠性及災難隔離考慮:

  • 1)把存儲層和緩存中間層分成兩個模塊 StoreSvr 及 AllocSvr 。StoreSvr 為存儲層,利用了多機 NRW 策略來保證數據持久化后不丟失; AllocSvr 則是緩存中間層,部署于多臺機器,每臺 AllocSvr 負責若干號段的 sequence 分配,分攤海量的 sequence 申請請求。
  • 2)整個系統又按 uid 范圍進行分 Set,每個 Set 都是一個完整的、獨立的 StoreSvr+AllocSvr 子系統。分 Set 設計目的是為了做災難隔離,一個 Set 出現故障只會影響該 Set 內的用戶,而不會影響到其它用戶。

微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)_d.jpg
▲ 圖4:原型架構圖

6、本篇小結


寫到這里把 seqsvr 基本原型講完了,正是如此簡單優雅的模型,可靠、穩定地支撐著微信五年來的高速發展。五年里訪問量一倍又一倍地上漲,seqsvr 本身也做過大大小小的重構,但 seqsvr 的分層架構一直沒有改變過,并且在可預見的未來里也會一直保持不變。

原型跟生產環境的版本存在一定差距,最主要的差距在于容災上。像微信的 IM 類應用,對系統可用性非常敏感,而 seqsvr 又處于收發消息、朋友圈等功能的關鍵路徑上,對可用性要求非常高,出現長時間不可服務是分分鐘寫故障報告的節奏。

本文的下篇《微信技術分享:微信的海量IM聊天消息序列號生成實踐(容災方案篇)會講講 seqsvr 的容災方案演變。

附錄:更多QQ、微信團隊原創技術文章


微信朋友圈千億訪問量背后的技術挑戰和實踐總結
騰訊技術分享:騰訊是如何大幅降低帶寬和網絡流量的(圖片壓縮篇)
騰訊技術分享:騰訊是如何大幅降低帶寬和網絡流量的(音視頻技術篇)
微信團隊分享:微信移動端的全文檢索多音字問題解決方案
騰訊技術分享:Android版手機QQ的緩存監控與優化實踐
微信團隊分享:iOS版微信的高性能通用key-value組件技術實踐
微信團隊分享:iOS版微信是如何防止特殊字符導致的炸群、APP崩潰的?
騰訊技術分享:Android手Q的線程死鎖監控系統技術實踐
微信團隊原創分享:iOS版微信的內存監控系統技術實踐
讓互聯網更快:新一代QUIC協議在騰訊的技術實踐分享
iOS后臺喚醒實戰:微信收款到賬語音提醒技術總結
騰訊技術分享:社交網絡圖片的帶寬壓縮技術演進之路
微信團隊分享:視頻圖像的超分辨率技術原理和應用場景
微信團隊分享:微信每日億次實時音視頻聊天背后的技術解密
QQ音樂團隊分享:Android中的圖片壓縮技術詳解(上篇)
QQ音樂團隊分享:Android中的圖片壓縮技術詳解(下篇)
騰訊團隊分享:手機QQ中的人臉識別酷炫動畫效果實現詳解
騰訊團隊分享 :一次手Q聊天界面中圖片顯示bug的追蹤過程分享
微信團隊分享:微信Android版小視頻編碼填過的那些坑
微信手機端的本地數據全文檢索優化之路
企業微信客戶端中組織架構數據的同步更新方案優化實戰
微信團隊披露:微信界面卡死超級bug“15。。。。”的來龍去脈
QQ 18年:解密8億月活的QQ后臺服務接口隔離技術
月活8.89億的超級IM微信是如何進行Android端兼容測試的
以手機QQ為例探討移動端IM中的“輕應用”
一篇文章get微信開源移動端數據庫組件WCDB的一切!
微信客戶端團隊負責人技術訪談:如何著手客戶端性能監控和優化
微信后臺基于時間序的海量數據冷熱分級架構設計實踐
微信團隊原創分享:Android版微信的臃腫之困與模塊化實踐之路
微信后臺團隊:微信后臺異步消息隊列的優化升級實踐分享
微信團隊原創分享:微信客戶端SQLite數據庫損壞修復實踐
騰訊原創分享(一):如何大幅提升移動網絡下手機QQ的圖片傳輸速度和成功率
騰訊原創分享(二):如何大幅壓縮移動網絡下APP的流量消耗(下篇)
騰訊原創分享(三):如何大幅壓縮移動網絡下APP的流量消耗(上篇)
微信Mars:微信內部正在使用的網絡層封裝庫,即將開源
如約而至:微信自用的移動端IM網絡層跨平臺組件庫Mars已正式開源
開源libco庫:單機千萬連接、支撐微信8億用戶的后臺框架基石 [源碼下載]
微信新一代通信安全解決方案:基于TLS1.3的MMTLS詳解
微信團隊原創分享:Android版微信后臺保活實戰分享(進程保活篇)
微信團隊原創分享:Android版微信后臺保活實戰分享(網絡保活篇)
Android版微信從300KB到30MB的技術演進(PPT講稿) [附件下載]
微信團隊原創分享:Android版微信從300KB到30MB的技術演進
微信技術總監談架構:微信之道——大道至簡(演講全文)
微信技術總監談架構:微信之道——大道至簡(PPT講稿) [附件下載]
如何解讀《微信技術總監談架構:微信之道——大道至簡》
微信海量用戶背后的后臺系統存儲架構(視頻+PPT) [附件下載]
微信異步化改造實踐:8億月活、單機千萬連接背后的后臺解決方案
微信朋友圈海量技術之道PPT [附件下載]
微信對網絡影響的技術試驗及分析(論文全文)
一份微信后臺技術架構的總結性筆記
架構之道:3個程序員成就微信朋友圈日均10億發布量[有視頻]
快速裂變:見證微信強大后臺架構從0到1的演進歷程(一)
快速裂變:見證微信強大后臺架構從0到1的演進歷程(二)
微信團隊原創分享:Android內存泄漏監控和優化技巧總結
全面總結iOS版微信升級iOS9遇到的各種“坑”
微信團隊原創資源混淆工具:讓你的APK立減1M
微信團隊原創Android資源混淆工具:AndResGuard [有源碼]
Android版微信安裝包“減肥”實戰記錄
iOS版微信安裝包“減肥”實戰記錄
移動端IM實踐:iOS版微信界面卡頓監測方案
微信“紅包照片”背后的技術難題
移動端IM實踐:iOS版微信小視頻功能技術方案實錄
移動端IM實踐:Android版微信如何大幅提升交互性能(一)
移動端IM實踐:Android版微信如何大幅提升交互性能(二)
移動端IM實踐:實現Android版微信的智能心跳機制
移動端IM實踐:WhatsApp、Line、微信的心跳策略分析
移動端IM實踐:谷歌消息推送服務(GCM)研究(來自微信)
移動端IM實踐:iOS版微信的多設備字體適配方案探討
信鴿團隊原創:一起走過 iOS10 上消息推送(APNS)的坑
騰訊信鴿技術分享:百億級實時消息推送的實戰經驗
IPv6技術詳解:基本概念、應用現狀、技術實踐(上篇)
IPv6技術詳解:基本概念、應用現狀、技術實踐(下篇)
騰訊TEG團隊原創:基于MySQL的分布式數據庫TDSQL十年鍛造經驗分享
微信多媒體團隊訪談:音視頻開發的學習、微信的音視頻技術和挑戰等
了解iOS消息推送一文就夠:史上最全iOS Push技術詳解
騰訊技術分享:微信小程序音視頻技術背后的故事
騰訊資深架構師干貨總結:一文讀懂大型分布式系統設計的方方面面
微信多媒體團隊梁俊斌訪談:聊一聊我所了解的音視頻技術
騰訊音視頻實驗室:使用AI黑科技實現超低碼率的高清實時視頻聊天
騰訊技術分享:微信小程序音視頻與WebRTC互通的技術思路和實踐
手把手教你讀取Android版微信和手Q的聊天記錄(僅作技術研究學習)
微信技術分享:微信的海量IM聊天消息序列號生成實踐(算法原理篇)
>> 更多同類文章 ……

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

上一篇:如何了解業內的IM性能數據?下一篇:微信技術分享:微信的海量IM聊天消息序列號生成實踐(容災方案篇)

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

推薦方案
評論 8
這篇文章發遲了, 之前后端同樣的問題糾結了好久, 最后還是連湊帶懵的搞出來的, 現在也只能湊活用著,
簽名: 好久沒來了,簽個到
引用:PonyZhao 發表于 2018-10-15 09:52
這篇文章發遲了, 之前后端同樣的問題糾結了好久, 最后還是連湊帶懵的搞出來的, 現在也只能湊活用著,

微信的思路確實很實用
簽名: 《IM要做手機掃碼登陸?先看看微信的掃碼登錄功能技術原理》http://www.4239727.live/thread-2941-1-1.html
厲害
序列的請求是由服務端內部發起的吧,那從客戶端到服務端,再到拿到序列,這個過程如何能保證拿到的序列順序與客戶端發起的順序一致呢?
引用:juwell 發表于 2019-10-17 17:25
序列的請求是由服務端內部發起的吧,那從客戶端到服務端,再到拿到序列,這個過程如何能保證拿到的序列順序 ...

你沒看懂吧,說白了每次拿的是個起始值,然后在間隔內自已用的時候遞增,下次再取的時候再取一個新的起始值
簽名: 《IM要做手機掃碼登陸?先看看微信的掃碼登錄功能技術原理》http://www.4239727.live/thread-2941-1-1.html
引用:JackJiang 發表于 2019-10-17 18:59
你沒看懂吧,說白了每次拿的是個起始值,然后在間隔內自已用的時候遞增,下次再取的時候再取一個新的起始 ...

請教下:這個id是由 發送消息的手機或桌面app客戶端來拿,還是消息發送到服務端后轉發的時候由后端來拿?謝謝。
簽名: very good
引用:sleeper 發表于 2019-11-02 16:37
請教下:這個id是由 發送消息的手機或桌面app客戶端來拿,還是消息發送到服務端后轉發的時候由后端來拿? ...

由客戶端來拿的話,比較合適,因為后端是個很大的分布式系統,同一個用戶在網絡斷開或重連后,不一定能落到同一臺接入端,后端拉的話,事情就有點復雜了。

不過,具體微信是怎么實施的,主要看他們的策略,但文章中的id生成原理就是這樣。
簽名: 《IM要做手機掃碼登陸?先看看微信的掃碼登錄功能技術原理》http://www.4239727.live/thread-2941-1-1.html
很不錯
打賞樓主 ×
使用微信打賞! 使用支付寶打賞!

返回頂部
股票配资平台都找股牛网