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

有效

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

1.一種低延遲的分布式計算共識算法，包括：

(1)執行EPaxos算法模式；

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

(2.1)計算Lat1(EPaxos)：統計副本R_i處理的客戶端提交的命令總數T_i，執行slow-path的命令數C_i，從客戶端到副本R_i所需的時間t_ci，從副本R_i到所有副本所花時間中第k少的時間min_k{i}，從副本R_i到所有副本所花時間中第p少的時間min_p{i}，則EPaxos算法模式下系統的平均延遲為：

其中，R_i表示第i個副本，i∈[1,N]，N表示副本總數；k表示fast path中的法定人數；p表示slow path中的法定人數，也為Multi-Paxos算法模式下的法定人數；

(2.2)估計Lat1(Multi-Paxos)：分別估計各個副本R_r為領導者時，Multi-Paxos算法模式下系統的平均延遲：

取最小的Lat1(Multi-Paxos)_r作為Multi-Paxos算法模式下系統的平均延遲Lat1(Multi-Paxos)，令領導者R_l為此時的R_r；

其中，r∈[1,N]；t_ir表示從副本R_i到副本R_r所需的時間；

(3)比較Lat1(EPaxos)和Lat1(Multi-Paxos)的大小，若Lat1(Multi-Paxos)Lat1(EPaxos)，從EPaxos算法模式轉換至Multi-Paxos算法模式，轉至步驟(4)，否則，轉至步驟(1)；

(4)執行Multi-Paxos算法模式，即在Multi-Paxos算法模式下客戶端將命令提交給最近的副本，副本再將命令傳遞給領導者；

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

(5.1)計算Lat2(Multi-Paxos)：統計副本R_i傳遞的客戶端提交的命令總數T_i，從客戶端到副本R_i所需的時間t_ci，從副本R_i到領導者R_l所需的時間t_il，從領導者R_l到所有副本所花時間中第p少的時間min_p{l}，則Multi-Paxos算法模式下系統的平均延遲為：

(5.2)估計Lat2(EPaxos)：統計從副本R_i到所有副本所花時間中第k少的時間min_k{i}，到所有副本所花時間中第p少的時間min_p{i}，傳遞的命令中對各個關鍵字K_m操作的命令數CK_im，則在EPaxos算法模式下，含有最大CK_im的副本R_i傳遞的關于關鍵字K_m的命令中執行slow path的命令數S_im近似為min{SK_im,∑_{r∈[1,N],r！}＝iCK_rm}，其余副本R_i傳遞的關于關鍵字K_m的命令中執行slow path的命令數S_im近似為CK_im，則對任意副本R_i，執行slow path的命令總數C_i近似為∑_mS_im，故EPaxos算法模式下系統的平均延遲近似表示為：

其中，m∈[1,M]，M表示關鍵字總數；

(6)比較Lat2(EPaxos)和Lat2(Multi-Paxos)的大小，若Lat2(EPaxos)≤Lat2(Multi-Paxos)，從Multi-Paxos算法模式轉換至EPaxos算法模式，轉至步驟(1)，否則，轉至步驟(4)。