[發明專利]一種低延遲的分布式計算共識算法

有效

• 申請號: 201711414657.2
• 申請日: 2017-12-25
• 公開（公告）號: CN108170763B
• 公開（公告）日: 2021-07-27
• 發明（設計）人: 葛洪偉;趙守月;葛陽
• 申請（專利權）人: 江南大學
• 主分類號: G06F16/182
• 分類號: G06F16/182;G06F9/50
• 代理公司: 哈爾濱市陽光惠遠知識產權代理有限公司 23211
• 代理人: 張勇

本發明公開了一種低延遲的分布式計算共識算法，主要解決在并發客戶端之間的命令沖突率增大時，系統響應延遲增加的問題。該算法將EPaxos算法和不受并發客戶端命令沖突情況影響的Multi?Paxos算法相結合，根據算法運行過程中的客戶端負載情況、并發客戶端命令沖突情況以及網絡實時情況，每隔一段時間進行EPaxos算法和Multi?Paxos算法系統平均延遲的計算，根據計算結果，智能地轉換到系統平均延遲較小的算法模式。本發明算法具有更好的適應能力、更優的延遲性能、更高的綜合效率，實現了在并發客戶端之間的命令沖突率較大的情況下，較EPaxos算法能獲得更低的系統響應延遲；在客戶端負載不均衡時，比Multi?Paxos算法更能適應多樣的客戶端環境。

技術領域

本發明屬于分布式計算領域，涉及非拜占庭故障的異步分布式系統環境下解決共識問題的算法。具體地說是一種低延遲的分布式計算共識算法，可用于分布式存儲系統，分布式應用程序協調服務等領域。

背景技術

分布式計算是一個古老而寬泛的話題，而近幾年因為“大數據”概念的興起，又煥發出了新的青春與活力。共識問題是分布式計算中最重要的問題之一，是許多商業分布式系統的核心，它刻畫了不同處理器之間的協調問題，即如何從互相沖突的輸入值產生一致的輸出值。現如今的許多基于分布式系統的軟件，如Hadoop，HBase，Spanner，Dynamo等，都需要解決共識問題。在非拜占庭故障的異步分布式系統環境下解決共識問題，更加接近共識問題的現實環境，提出的解決方法也更具有普適性。對非拜占庭故障的異步分布式系統環境下的共識問題進行研究，對于分布式計算、大數據的研究，有著重要的推動意義。

FLP不可能定理指出：在存在故障(即使只有一個進程故障)的異步系統中，不存在用于解決共識問題的確定性算法。這說明，解決共識問題的算法必須在安全性(safety)和靈活性(liveness)之間取舍。Leslie Lamport提出的Multi-Paxos算法是確保安全性的共識算法中的經典。為了防止在并發情況下陷入活鎖，Multi-Paxos算法需要選舉一個領導者和并發客戶端進行交流，接受并發客戶端傳遞的命令。但是領導者的設置使得在廣域網環境下的分布式系統中，客戶端和分布式系統交互需要更大的延遲(和領導者不在同一局域網的客戶端需要花費更多的時間和領導者進行通信)。當領導者所在局域網的網絡延遲增加，將會影響到整個系統的響應時間。針對此問題，許多算法對Multi-Paxos算法進行了改進，其中，EPaxos算法是近幾年提出，影響較為深遠的Multi-Paxos算法變種。EPaxos算法不選舉特定的領導者，允許所有的副本接受客戶端提出的命令。通過讓客戶端將命令發送給最近的副本，降低了廣域網環境下系統響應的延遲。但是EPaxos算法隨著并發客戶端之間的命令沖突率的增大，系統的響應延遲也會增加。

發明內容

針對上述問題，本發明提出一種低延遲的分布式計算共識算法，以解決在并發客戶端之間的命令沖突率增大時，系統響應延遲增加的問題，能夠在并發客戶端之間的命令沖突率較大的情況下，較EPaxos算法獲得更低的系統響應延遲；在客戶端負載不均衡時，比Multi-Paoxs算法更能適應多樣的客戶端環境。

實現本發明的關鍵技術是：在EPaxos算法的基礎上，將EPaxos算法和不受并發客戶端命令沖突影響的Multi-Paxos算法相結合，根據算法運行過程中客戶端的負載情況、并發客戶端的命令沖突情況以及網絡的實時情況，進行系統平均延遲的計算，通過每隔一段時間分別計算的EPaxos算法模式下和Multi-Paxos算法模式下的系統平均延遲，智能地轉換到系統平均延遲較小的算法模式。

為實現上述目標，具體實現步驟如下：

(1)執行EPaxos算法模式；

(2)根據算法運行過程中客戶端的負載情況、并發客戶端的命令沖突情況以及網絡的實時情況，每隔時間段t_s計算EPaxos算法模式下系統的平均延遲Lat1(EPaxos)以及估計Multi-Paxos算法模式下系統的平均延遲Lat1(Multi-Paxos)：