分布式一致性算法Yac

来源：计算机应用杂志2017年第9期北京时间：

作者：张健, 汪洋, 刘丹丹

单位：1. 武汉大学 计算机学院, 武汉 430072;2. 武汉大学 软件工程国家重点实验室, 武汉 430072

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

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

基金资助：国家自然科学基金资助项目（61103216）。