A Low Latency Distributed Consensus Algorithm In Wide Area Networks

Distributed consensus algorithm is a core problem in distributed systems.In order to enhance the availability,distributed systems back up the data to multiple replica nodes and use the distributed consensus algorithm to reach a consensus on the command sequence executed by multiple replica nodes,so as to ensure the data consistency of each replica.With the development of distributed systems,more and more systems are deployed in wide area networks.They put forward further requirements for distributed consensus algorithms.on the premise of ensuring the correct operation of the system,they use as low latency as possible to reach consensus on each command which can improve the performance of system.Paxos is the most representative distributed consensus algorithm,which is completed in two phases: leader election phase and accept phase.In order to ensure that the value of the proposal determined in the two phases is unique,Paxos requires that more than half of the nodes in the system agree to the proposal message of each phase,and these nodes form a quorum to ensure the quorum intersection condition for different phases.In global distributed networks,the communication is the main cost of reaching consensus.The quorum of each phase composed of more than half of the nodes,which requires a lot of communications and results in a large consensus latency.If the number of nodes in quorums can be reduced,the communication cost and consensus latency can be reduced.For this,the existing algorithms propose a variety of quorum intersection conditions,including Majority,Flexible Quorum,Expanding Quorum,etc.Its main idea is to reduce the number of nodes in second phase quorums with high frequency while increasing the number of nodes in first phase quorums with low frequency.It realizes the minimization of the second phase quorum,but there is no solution on the minimization of the first phase quorum.Moreover,in order to solve the load bottleneck of leader node and the load imbalance between the leader and other nodes,the existing algorithms adopt two schemes,Multi-Leader and Leader-Less,who ignore the location relationship between the leader and the client —— The closer the distance,the lower the latency.To solve the above problems,this paper proposes a Paxos variant algorithm——SQPaxos(Smallest Quorum Paxos),who reduces consensus latency from two aspects:quorum intersection condition and leader allocation mechanism.The contributions of this paper are as follows:(1)Smallest Quorum.According to the fault tolerance requirement of system and safety requirements of algorithm,SQPaxos determines the minimum number of nodes in first phase quorums and second phase quorums.At the same time,in order to meet the quorum intersection condition,we propose to establish the mapping relationship between proposal number and node number.By using the uniqueness of the proposal number,a fixed set of nodes is assigned to the proposal according to the proposal number,which constitutes the first phase quorum and the second phase quorum respectively.(2)An adaptive leader allocation mechanism.Based on multi leader,the leader is transferred to the region with high operating frequency adaptively by counting the frequency of client requests from different regions.Experimental results show that,in terms of quorum,the average latency of SQPaxos is lower than FPaxos,DPaxos and Multi-Paxos.For leader performance testing,the average latency of SQPaxos using adaptive leader mechanism is lower than that of SQPaxos without adaptive leader mechanism,WPaxos and EPaxos.The experimental results verify the effectiveness of the proposed method.