分布式一致性算法Yac

摘要

There are serious load imbalance and single point performance bottleneck effect in the traditional static topology leader-based distributed consensus algorithm,and the algorithm is unable to work properly when the number of breakdown nodes is larger than 50％ of the cluster size.To solve the above problems,a distributed consensus algorithm (Yac) based on dynamic topology and limited voting was proposed.The algorithm dynamically generated the membership subset and Leader nodes to participate in the consensus voting,and varied with time,achieving statistical load balance.With removal of the strong constraints of all the majority of members to participate in voting,the algorithm had a higher degree of failure tolerance.The security constraints of the algorithm were reestablished by the log chain mechanism,and the correctness of the algorithm was proved.The experimental results show that the load concentration effect of single point in the improved algorithm is significantly lower than that of the mainstream static topology leader-based distributed consensus algorithm Zookeeper.The improved algorithm has better fault tolerance than Zookeepor in most cases and maintains the same as Zookeeper in the worst case.Under the same cluster size,the improved algorithm has higher throughput upper limit than Zookeeper.%传统静态拓扑主从模型分布式一致性算法存在严重负载不均及单点性能瓶颈效应,且崩溃节点大于集群规模的50％时算法无法正常工作.针对上述问题,提出基于动态拓扑及有限表决思想的分布式一致性算法(Yac).算法动态生成参与一致性表决的成员子集及Leader节点并时分迁移,形成统计负载均衡;去除要求全体多数派成员参与表决的强约束,使算法具备更高的失效容忍性;并通过日志链机制重新建立算法安全性约束,同时证明了算法的正确性.实验结果表明,改进算法的单点负载集中效应显著低于主流静态拓扑主从模型分布式一致性算法Zookeeper;改进算法失效容忍性优于Zookeeper,且最坏情况下与Zookeeper算法保持持平;同等集群规模下,改进算法比Zookeeper拥有更高吞吐量上限.