一种改进的广域网低延迟分布式共识算法  

An Improved Low Delay Distributed Consensus Algorithm in WAN

作　　者：弓婷 牛保宁 张栩豪 GONG Ting;NIU Baoning;ZHANG Xuhao(College of Information and Computer, Taiyuan University of Technology, Jinzhong 030600, China)

机构地区：[1]太原理工大学信息与计算机学院,山西晋中030600

出　　处：《太原理工大学学报》2021年第4期592-599,共8页Journal of Taiyuan University of Technology

基　　金：国家自然科学基金资助项目(62072326);山西省重点研发计划(国际科技合作)资助项目(201903D421007)。

摘　　要：针对现有广域网分布式共识算法使用的两阶段Quorum节点数量多,忽视Leader与客户端的位置关系这两个问题,提出一种改进的Paxos算法——SQPaxos(Smallest Quorum Paxos).在Quorum方面,SQPaxos分别确定最小的第一阶段和第二阶段Quorum节点数量,建立提案号与节点编号间的映射关系,为每个提案分配节点构成Quorum,满足Quorum相交要求,降低共识延迟。在Leader与客户端的位置关系方面,提出自适应Leader分配机制,在Multi-Leader基础上,通过统计不同区域的客户端发起请求的频率,自适应地将Leader转移至操作频率高的区域,降低Leader与客户端间的通信延迟。实验结果表明:实现了最小化两阶段Quorum的SQPaxos能够大幅降低广域网共识延迟。同时,采用自适应Leader分配机制的算法与未使用的和使用其他Leader分配机制的算法相比,能够一定程度减少共识延迟。In order to solve the problem that the number of Quorum nodes in two-phase of WAN distributed consensus algorithm is large and the location relationship between leader and client is ignored,a Paxos variant algorithm—Smallest Quorum Paxos(SQPaxos)—was proposed.In terms of quorums,SQPaxos determines the minimum number of nodes in the first phase Quorums and second phase Quorums,establishes the mapping relationship between proposal number and node number,and allocates nodes for each proposal to form Quorums,so as to meet the Quorum intersection condition and reduce consensus latency.In terms of the location relationship between leader and client,an adaptive leader allocation mechanism was proposed.Based on the multi-leader,by counting the frequency of requests from clients in different regions,the leader is adaptively transferred to the regions with high operation frequency to reduce the latency between leader and client.The experimental results show that SQPaxos which realizes the minimization of two-phase Quorums can greatly reduce the consensus latency.At the same time,the algorithm using adaptive leader allocation mechanism can reduce latency compared with the algorithm without using the mochanism or using other leader allocation mechanisms.

关 键 词：分布式共识算法 Paxos QUORUM Multi-Paxos Leader节点 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]