计算机应用 ›› 2017, Vol. 37 ›› Issue (9): 2524-2530.DOI: 10.11772/j.issn.1001-9081.2017.09.2524

• 先进计算 • 上一篇    下一篇

分布式一致性算法Yac

张健1, 汪洋1, 刘丹丹2   

  1. 1. 武汉大学 计算机学院, 武汉 430072;
    2. 武汉大学 软件工程国家重点实验室, 武汉 430072
  • 收稿日期:2017-03-13 修回日期:2017-05-07 出版日期:2017-09-10 发布日期:2017-09-13
  • 通讯作者: 汪洋,943629628@qq.com
  • 作者简介:张健(1976-),男,安徽铜陵人,教授,博士,主要研究方向:云计算、物联网;汪洋(1990-),男,湖北武汉人,硕士研究生,主要研究方向:云计算、分布式计算;刘丹丹(1980-),女,湖北武汉人,副教授,博士,CCF会员,主要研究方向:无线网络、移动计算。
  • 基金资助:
    国家自然科学基金资助项目(61103216)。

Yac:yet another distributed consensus algorithm

ZHANG Jian1, WANG Yang1, LIU Dandan2   

  1. 1. School of Computer Science, Wuhan University, Wuhan Hubei 430072, China;
    2. State Key Lab of Software Engineering, Wuhan University, Wuhan Hubei 430072, China
  • Received:2017-03-13 Revised:2017-05-07 Online:2017-09-10 Published:2017-09-13
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61103216).

摘要: 传统静态拓扑主从模型分布式一致性算法存在严重负载不均及单点性能瓶颈效应,且崩溃节点大于集群规模的50%时算法无法正常工作。针对上述问题,提出基于动态拓扑及有限表决思想的分布式一致性算法(Yac)。算法动态生成参与一致性表决的成员子集及Leader节点并时分迁移,形成统计负载均衡;去除要求全体多数派成员参与表决的强约束,使算法具备更高的失效容忍性;并通过日志链机制重新建立算法安全性约束,同时证明了算法的正确性。实验结果表明,改进算法的单点负载集中效应显著低于主流静态拓扑主从模型分布式一致性算法Zookeeper;改进算法失效容忍性优于Zookeeper,且最坏情况下与Zookeeper算法保持持平;同等集群规模下,改进算法比Zookeeper拥有更高吞吐量上限。

关键词: 分布式一致性, Paxos算法, 表决团, 日志链, 负载均衡

Abstract: 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 Zookeeper 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.

Key words: distributed consensus, Paxos algorithm, voting group, log chain, load balance

中图分类号: