漫畫：架構師是吧？什麼是哈希輪？

• 2019 年 10 月 7 日
• 筆記

就這樣過了幾天，小碼哥刷了刷簡歷…..

小碼收到獵頭小姐姐的面試邀約後，認真進行了準備，並在約定時間到達了面試公司….

支付系統數據一致性問題 在支付系統中數據的一致性問題是一個非常重要的問題，因為一旦發生數據不一致就意味着資金的損失，要麼是用戶支付了錢沒有成功購買到商品；要麼是平台沒有收到用戶的錢，卻給用戶錯誤地發送了支付成功的消息。無論哪種情況都會造成業務方對支付系統的不信任，因此我們要在整體系統流程上進行設計和考慮。 從系統流程方向上看，支付系統數據不一致的發生主要有兩個點：一是支付平台與第三方支付渠道（如支付寶、微信等）之間；二是支付平台與各個業務接入方之間。在支付系統建設中，所有的措施與手段都是圍繞確保「業務接入方<->支付平台<->支付渠道」這三者之間的數據一致性而展開的！

分佈式事務消息解決方案

在實時流程上我們採用了基於Rocket MQ的分佈式事務消息方案。通過MQ+分佈式事務消息機制解耦了支付平台與第三方支付渠道之間的回調依賴及支付平台與業務接入方之間的回調依賴。示意圖如下：

而之所以選擇通過MQ+分佈式事務消息來解耦，前面提到過支付系統最容易產生數據不一致的地方就是面向第三方渠道以及面向業務接入方，而面向第三方渠道的不一致的風險會更高，因為第三方支付渠道屬於上游外部依賴，擁有更多的不確定性。在大多數情況下，第三方支付渠道與支付平台之間依賴於異步支付結果通知機制來保證支付狀態的回調，所以支付平台需要率先同步接受第三方支付的回調，並確保在完成支付訂單狀態更新的事務後同步向第三方支付渠道返回處理結果。

從正常的業務流程上看並沒有什麼問題，但是由於將接受第三方支付回調及處理支付平台狀態邏輯放在同一個事務中，在極端情況下，如支付系統出現故障導致第三方支付渠道無法正常回調、或者由於支付回調量過大而導致支付平台處理回調通知失敗的話就會造成數據不一致。

而通過MQ解耦後系統將接收支付回調與處理支付回調邏輯隔離在了兩個不同的流程之中，並基於分佈式事務消息的機制來保證消息的投遞與處理的事務一致性，實踐證明這種方案可以較大地提升系統性能並且在一定程度上降低數據不一致的發生幾率。基於這樣的結論，我們在支付平台與業務接入方的回調方式上也採取了類似的機制。

即將講到本文的重點，請大家抽根煙、保持耐心…

支付狀態實時對賬解決方案 在實時流程中我們利用分佈式事務消息主要針對的問題是在正常流程下，支付平台對第三方支付結果回調處理錯誤、以及支付平台對業務接入方回調邏輯錯誤的情況下而產生的支付狀態數據不一致問題。

但這並不能100%的解決支付掉單問題，因此還需要設計一套對賬機制來確保剩下的漏網異常數據能夠被及時補償。從業務的角度看，對賬是支付平台確保數據一致性的重要手段，而對賬的方式有日終T+1對賬及實時對賬兩種形式，日終對賬主要解決的是T+1資金結算的準確性，而從技術角度看日終對賬主要以離線計算為主，是一種事後策略，更多地是滿足財務對資金數據的核算需求。

而實時對賬則有所不同，它具有在線計算的特點，主要是解決用戶流程中的支付掉單痛點，提升用戶支付體驗。需要說明實時對賬並不能完全替代日終對賬，它們二者面向的需求場景不一樣，但是實時對賬能夠有效減小日終對賬發現差錯的幾率！

Rocket MQ延遲消息對賬 延遲消息對賬的主要實現方式就是在向第三方渠道發起支付請求後，向Rocket MQ服務器指定隊列發送一條延遲對賬消息。例如可以設置30秒的延遲時間，30秒後Rocket MQ就會將消息真正投遞到指定Topic中，處理實時對賬的Consumer服務此時就會消費到延遲對賬消息。

實時對賬Consumer服務在處理消息時會遇到以下幾種情況：

• 第三方回調已經完成，支付平台訂單狀態處於正確狀態，此時邏輯不做任何處理，延遲消息被正常消費掉；
• 第三方回調未發生，支付平台訂單狀態未知，查詢第三方渠道訂單接口獲取該筆支付的結果狀態，如果為成功/失敗，則更新支付平台訂單狀態完成回盤邏輯處理；
• 第三方回調未發生，支付平台訂單狀態未知，查詢第三方渠道訂單接口獲取該筆支付結果狀態，如果仍然是未支付，則將該延遲對賬消息扔回MQ，並設置其延遲時間為2小時，2小時後再核查一次，如果仍然是未支付則表示用戶無再次支付意願，將訂單狀態置為失效；

比如setDelayTimeLevel(3)表示延遲10s。

無論是定時任務還是延遲消息，都需要一定的策略和邏輯來進行觸發，試想一下如果需要觸發的任務量非常巨大的話，需要輪訓讀取到期數據的耗時將會非常長。而且由於每個任務預設的時間長度不一樣，輪訓的頻次如果都是一樣的話，也會造成系統資源的浪費。

正是基於這樣的考慮，所以Rocket MQ只支持固定的延遲等級，而在存儲結構上Rocket MQ會為每個延遲等級分配一個鏈表，Broker收到的任何一條延遲消息時都可以根據消息的延遲時間判斷其延遲等級，從而將其入到對應的鏈表裡（在Rocket MQ的實現中會將延遲消息的原始Topic、QueueId替換為特定的Topic、QueueId則會替換為延遲級別對應的id），每條鏈表內承載的延遲消息具有相同的延遲等級，先入的消息一定比後入的消息優先被投遞，所以鏈表成了一個有序的FIFO隊列。

在Rocket MQ的延遲消息機制中由於不同等級的延遲會分屬於不同的定時隊列，加上延遲等級的數目是固定的每個延遲等級都會有自己獨立的定時器，所以相對來說開銷就會降低很多！

哈希輪算法

哈希輪又稱「哈希時間輪」（Hash TimingWheel），在面臨大量定時任務並且定時時長非常離散的任務系統中，哈希時間輪擁有非常強大的性能。從結構上看，哈希時間輪是一個存儲定時任務的環形隊列。如下圖所示：

從結構上來一個哈希輪會被劃分成多個不同的槽（slot），每個槽指向一條雙向鏈表結構的定時器鏈表，每條鏈表上的定時器時長具有相同的特徵。例如，假設現在哈希輪的指針指向槽cs,指針轉動的時間間隔為si，那麼如果此時我們要增加一個定時時間為ti的定時器，那麼該定時器會被插入槽ts所在的鏈表中，公式如下：

ts = (cs+(ti/si))%N

可以看出，哈希輪實際上是使用了哈希表的思想來將定時器散列到不同的雙向鏈表中。在哈希輪中，如果要提高定時精度那麼指針轉動的頻率si值要足夠小；而如果要提高執行效率，則要求時間輪槽的數量足夠大，因為這樣每個鏈表上的任務數量就少了，每次需要處理的定時器就不多！

以上介紹的只是簡單的哈希時間輪，在大多數實現中（例如Kafka）為了支持更多的場景還會使用多級時間輪的結構，不同的輪子可以採取不同的粒度，例如精度高的轉一圈，精度低的僅往前移動一個槽！在具體實現哈希輪算法時可以根據實際應用場景設計不同的策略！

任意時長延遲消息

延遲消息在投遞後延遲一段時間才對用戶可見，如果要支持任意時長的延遲消息，假如支持30天，精度為1秒，按照之前的延遲等級劃分，時間輪需要被分割成30*24*60*60=2,592,000個槽，如果支持的延遲時長天數更多，那麼時間輪需要被分割的槽的個數還會增加，但是時間輪是需要被加載到內存中操作的，而這顯然是不能被接受的。 所以單個時間輪的方案是無法實現任意時長的延遲消息，因此需要構建支持時、分、秒的多級時間輪來解決。

但是在多級時間輪方案中，需要加載大量的數據到內存，這會造成比較大的內存開銷，所以對於未來1小時或者未來一天的數據是可以不加載到內存的，通過延遲加載的方式只加載延遲時間臨近的消息！

另外一個問題是在Rocket MQ中CommitLog是有時效性的，例如一般只會保存最近7天的數據，過期的數據將被刪除。而對於延遲消息，可能需要在30天之後被投遞，而這顯然是不能被刪除的數據，因此如果要在Rocket MQ中實現任意時長的延遲消息，還需要將延遲消息的存儲從CommitLog剝離出來單獨進行存儲！

就這樣小碼哥進入了談薪階段，最後的結果是….

參考資料：

https://www.cnblogs.com/hzmark/p/mq-delay-msg.html

https://www.jianshu.com/p/0f0fec47a0ad

http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf