保證消息不會亂序——消息序号生成器
為什麼消息的時序一緻性很重要？
對于聊天、直播互動等業務來說，消息的時序代表的是發送方的意見表述和接收方的語義邏輯了解，如果時序一緻性不能保證，可能就會造成聊天語義不連貫、容易出現曲解和誤會。
可以想象一下，一個人說話颠三倒四，前言不搭後語的樣子，就了解我們為什麼要尤其注重消息的時序一緻性了。
對于點對點的聊天場景，時序一緻性需要保證接收方的接收順序和發送方的發出順序一緻；而對于群組聊天，時序一緻性保證的是群裡所有接收人看到的消息展現順序都一樣。
保證消息的時序一緻性很困難
如果發送方和接收方的消息收發都是單線程操作，并且和 IM 服務端都隻有唯一的一個 TCP 連接配接，來進行消息傳輸，IM 服務端也隻有一個線程來處理消息接收和消息推送。這種場景下，消息的時序一緻性是比較容易能得到保障的。
但在實際的後端工程實作上，由于單發送方、單接收方、單處理線程的模型吞吐量和效率都太低，基本上不太可能存在。
更多的場景下，我們可能需要面對的是多發送方、多接收方、服務端多線程并發處理的情況。
時序一緻性的要求
消息的時序一緻性其實是要求我們的消息具備“時序可比較性”，也就是消息相對某一個共同的“時序基準”可以來進行比較，是以，要保證消息的時序一緻性的一個關鍵問題是：我們是否能找到這麼一個時序基準，使得我們的消息具備“時序可比較性”。
在工程實作上，我們可以分成這樣幾步。
- 1.如何找到時序基準。
- 2.時序基準的可用性問題。
- 3.有了時序基準，還有其他的誤差嗎，有什麼辦法可以減少這些誤差？
如何找到時序基準？
發送方的本地序号和本地時鐘
首先，發送方的本地序号和本地時鐘是否可以作為“時序基準”？
- 所謂發送方的本地序号和本地時鐘是指發送方在發送消息時連同消息再攜帶一個本地的時間戳或者本地維護的一個序号給到 IM 服務端，IM 服務端再把這個時間戳或者序号和消息一起發送給消息接收方，消息接收方根據這個時間戳或者序号來進行消息的排序。
仔細分析一下，貌似發送方的本地序号或者本地時鐘不适合用來作為接收方排序的“時序基準”，原因有下面幾點。
- 發送方時鐘存在較大不穩定因素，使用者可以随時調整時鐘導緻序号回退等問題。
- 發送方本地序号如果重裝應用會導緻序号清零，也會導緻序号回退的問題。
- 類似“群聊消息”和“單使用者的多點登入”這種多發送方場景，都存在：同一時鐘的某一時間點，都可能有多條消息發給同一接收對象。比如同一個群裡，多個人同時發言；或者同一個使用者登入兩台裝置，兩台裝置同時給某一接收方發消息。多裝置間由于存在時鐘不同步的問題，并不能保證裝置帶上來的時間是準确的，可能存在群裡的使用者 A 先發言，B 後發言，但由于使用者 A 的手機時鐘比使用者 B 的慢了半分鐘，如果以這個時間作為“時序基準”來進行排序，可能反而導緻使用者 A 的發言被認為是晚于使用者 B 的。
是以以發送方的本地時鐘或者本地序号作為“時序基準”是不可靠的。
IM 伺服器的本地時鐘
那麼，我們接下來看看 IM 伺服器的本地時鐘是否可以作為“時序基準”？
這裡也解釋一下，IM 伺服器的本地時鐘作為“時序基準”是指：發送方把消息送出給 IM 伺服器後，IM 伺服器依據自身伺服器的時鐘生成一個時間戳，再把消息推送給接收方時攜帶這個時間戳，接收方依據這個時間戳來進行消息的排序。
好像 IM 伺服器的本地時鐘作為接收方消息排序的“時序基準”也不太合适。
因為，在實際工程中，IM 服務都是叢集化部署，叢集化部署也就是許多伺服器同時部署任務。
雖然多台伺服器通過 NTP 時間同步服務，能降低服務叢集機器間的時鐘差異到毫秒級别，但仍然還是存在一定的時鐘誤差，而且 IM 伺服器規模相對比較大，時鐘的統一性維護上也比較有挑戰，整體時鐘很難保持極低誤差，是以一般也不能用 IM 伺服器的本地時鐘來作為消息的“時序基準”。
IM 服務端的全局序列
既然單機本地化的時鐘或者序号都存在問題，那麼如果有一個全局的時鐘或者序号是不是就能解決這個問題了呢？所有的消息的排序都依托于這個全局的序号，這樣就不存在時鐘不同步的問題了。那麼最後，我們來看看 IM 服務端的全局序列是否可以作為“時序基準”？
比如說如果有一個全局遞增的序号生成器，應該就能避免多伺服器時鐘不同步的問題了，IM 服務端就能通過這個序号生成器發出的序号，來作為消息排序的“時序基準”。
“時序基準”的可用性問題：使用“全局序号生成器”發出的序号，來作為消息排序的“時序基準”，能解決每一條消息沒有标準“生産日期”的問題。但如果是面向高并發和需要保證高可用的場景，還需要考慮這個“全局序号生成器”的可用性問題。
首先，類似 Redis 的原子自增和 DB 的自增 id，都要求在主庫上來執行“取号”操作，而主庫基本都是單點部署，在可用性上的保障會相對較差，另外，針對高并發的取号操作這個單點的主庫可能容易出現性能瓶頸。
而采用類似 snowflake 算法的時間相關的分布式“序号生成器”，雖然在發号性能上一般問題不大，但也存在一些問題：一個是發出的号攜帶的時間精度有限，一般能到秒級或者毫秒級，比如微網誌的 ID 生成器就是精确到秒級的，另外由于這種服務大多都是叢集化部署，攜帶的時間采用的伺服器時間，也存在時鐘不一緻的問題（雖然時鐘同步上比控制大量的 IM 伺服器也相對容易一些）。
由上可知，基于“全局序号生成器”仍然存在不少問題，但是這種方法在某些場合下有不錯的适用性。
從業務層面考慮，對于群聊和多點登入這種場景，沒有必要保證全局的跨多個群的絕對時序性，隻需要保證某一個群的消息有序即可。
這樣可以針對每一個群有獨立一個“ID 生成器”，能通過哈希規則把壓力分散到多個主庫執行個體上，大量降低多群共用一個“ID 生成器”的并發壓力。
對于大部分即時消息業務來說，産品層面可以接受消息時序上存在一定的細微誤差，比如同一秒收到同一個群的多條消息，業務上是可以接受這一秒的多條消息，未嚴格按照“接收時的順序”來排序的，實際上，這種細微誤差對于使用者來說，基本也是無感覺的。
那麼，對于依賴“分布式的時間相關的 ID 生成器”生成的序号來進行排序，如果時間精度業務上可以接受也是沒問題的。
從之前微信對外的分享，我們可以了解到：微信的聊天和朋友圈的消息時序也是通過一個“遞增”的版本号服務來進行實作的。不過這個版本号是每個使用者獨立空間的，保證遞增，不保證連續。
微網誌的消息箱則是依賴“分布式的時間相關的 ID 生成器”來對私信、群聊等業務進行排序，目前的精度能保證秒間有序。
“時序基準”之外的其他誤差
有了“時序基準”，是不是就能確定消息能按照“既定順序”到達接收方呢？答案是并不一定能做到。原因在于下面兩點。
- IM 伺服器都是叢集化部署，每台伺服器的機器性能存在差異，是以處理效率有差别，并不能保證先到的消息一定可以先推送到接收方，比如有的伺服器處理得慢，或者剛好碰到一次 GC，導緻它接收的更早消息，反而比其他處理更快的機器更晚推送出去。
- IM 服務端接收到發送方的消息後，之後相應的處理一般都是多線程進行處理的，比如“取序号”“暫存消息”“查詢接收方連接配接資訊”等，由于多線程處理流程，并不能保證先取到序号的消息能先到達接收方，這樣的話對于多個接收方看到的消息順序可能是不一緻的。
是以一般還需要端上能支援對消息的“本地整流”。
消息服務端包内整流
雖然大部分情況下，聊天、直播互動等即時消息業務能接受“小誤差的消息亂序”，但某些特定場景下，可能需要 IM 服務能保證絕對的時序。
比如發送方的某一個行為同時觸發了多條消息，而且這多條消息在業務層面需要嚴格按照觸發的時序來投遞。
- 一個例子：使用者 A 給使用者 B 發送最後一條分手消息同時勾上了“取關對方”的選項，這個時候可能會同時産生“發消息”和“取關”兩條消息，如果服務端處理時，把“取關”這條信令消息先做了處理，就可能導緻那條“發出的消息”由于“取關”了，發送失敗的情況。
- 對于這種情況，我們一般可以調整實作方式，在發送方對多個請求進行業務層合并，多條消息合并成一條；也可以讓發送方通過單發送線程和單 TCP 連接配接能保證兩條消息有序到達。
但即使 IM 服務端接收時有序，由于多線程處理的原因，真正處理或者下推時還是可能出現時序錯亂的問題，解決這種“需要保證多條消息絕對有序性”可以通過 IM 服務端包内整流來實作。
比如：我們在實作離線推送時，在網關機啟動後會自動訂閱一個本 IP 的 Topic，當使用者上線時，網關機會告知業務層使用者有上線操作，這時業務層會把這個使用者的多條離線消息 pub 給這個使用者連接配接的那個網關機訂閱的 Topic，當網關機收到這些消息後，再通過長連接配接推送給使用者，整個過程大概是下圖這樣的。
但是很多時候會出現 Redis 隊列元件的 Sharding 和網關機多線程消費處理導緻亂序的情況，這樣，如果一些信令（比如删除所有會話）的操作被亂序推送給用戶端，可能就會造成端上的邏輯錯誤。
離線推送服務端整流的過程：
- 首先，生産者為每個消息包生成一個 packageID，為包内的每條消息加個有序自增的 seqId。
- 其次，消費者根據每條消息的 packageID 和 seqID 進行整流，最終執行子產品隻有在一定逾時時間内完整有序地收到所有消息才執行最終操作，否則将根據業務需要觸發重試或者直接放棄操作。通過服務端整流，服務端包内整流大概就是圖中這個樣子，我們要做的是在最終伺服器取到 TCP 連接配接後下推的時候，根據包的 ID，對一定時間内的消息做一個整流和排序，這樣即使服務端處理多條消息時出現亂序，仍然可以在最終推送給用戶端時整流為有序的。
消息接收端整流
攜帶不同序号的消息到達接收端後，可能會出現“先産生的消息後到”“後産生的消息先到”等問題，消息接收端的整流就是解決這樣的一個問題的。
消息用戶端本地整流的方式可以根據具體業務的特點來實作，目前業界比較常見的實作方式比較簡單，步驟如下：
1.下推消息時，連同消息和序号一起推送給接收方；
2.接收方收到消息後進行判定，如果目前消息序号大于前一條消息的序号就将目前消息追加在會話裡；
3.否則繼續往前查找倒數第二條、第三條等，一直查找到恰好小于目前推送消息的那條消息，然後插入在其後展示。
，連同消息和序号一起推送給接收方；
2.接收方收到消息後進行判定，如果目前消息序号大于前一條消息的序号就将目前消息追加在會話裡；
3.否則繼續往前查找倒數第二條、第三條等，一直查找到恰好小于目前推送消息的那條消息，然後插入在其後展示。