分布式一致性算法Yac

doi:10.11772/j.issn.1001-9081.2017.09.2524

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

分布式一致性算法Yac

张健¹, 汪洋¹, 刘丹丹²

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 Jian¹, WANG Yang¹, LIU Dandan²

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).

摘要/Abstract

摘要： 传统静态拓扑主从模型分布式一致性算法存在严重负载不均及单点性能瓶颈效应，且崩溃节点大于集群规模的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

中图分类号:

TP301.6

张健, 汪洋, 刘丹丹. 分布式一致性算法Yac[J]. 计算机应用, 2017, 37(9): 2524-2530.

ZHANG Jian, WANG Yang, LIU Dandan. Yac:yet another distributed consensus algorithm[J]. Journal of Computer Applications, 2017, 37(9): 2524-2530.

参考文献

[1] LAMPORT L, SHOSTAK R, PEASE M. The byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3):382-401.
[2] LAMPORT L. The part-time parliament[J]. ACM Transactions on Computer Systems, 1998, 16(2):133-169.
[3] LAMPORT L. Paxos made simple[J]. ACM SIGACT News, 2016, 32(4):18-25.
[4] LAMPORT L. Fast paxos[J]. Distributed Computing, 2006, 19(2):79-103.
[5] ZHAO W. Fast paxos made easy:theory and implementation[J]. International Journal of Distributed Systems and Technologies, 2015, 6(1):15-33.
[6] BURROWS M. The chubby lock service for loosely-coupled distributed systems[C]//Proceedings of the 7th Symposium on Operating Systems Design and Implementation. Berkeley, CA:USENIX Association, 2006:335-350.
[7] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]//Proceedings of the 2014 USENIX Annual Technical Conference. Berkeley, CA:USENIX Association, 2014:305-320.
[8] JUNQUEIRA F, REED B. ZooKeeper:Distributed Process Coordination[M]. Sebastopol, CA:O'Reilly, 2013:3-42.
[9] JUNQUEIRA F P, REED B C, SERAFINI M. Zab:high-performance broadcast for primary-backup systems[C]//Proceedings of the 2011 IEEE/IFIP 41st International Conference on Dependable Systems & Networks. Piscataway, NJ:IEEE, 2011:245-256.
[10] HUNT P, KONAR M, JUNQUEIRA F P, et al. ZooKeeper:wait-free coordination for internet-scale systems[C]//Proceedings of the 2010 USENIX Annual Technical Conference. Berkeley, CA:USENIX Association, 2010:11.
[11] MARANDI P J, PRIMI M, SCHIPER N, et al. Ring Paxos:a high-throughput atomic broadcast protocol[EB/OL].[2016-12-09]. http://www.microsoft.com/en-us/research/wp-content/uploads/2016/06/RingPaxos.pdf.
[12] KUMAR V, AGARWAL A. HT-Paxos:high throughput state-machine replication protocol for large clustered data centers[EB/OL].[2017-01-04]. http://xueshu.baidu.com/s?wd=paperuri%3A%28b741b6286079366bc618b67547ec68f0%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http%3A%2F%2Fde.arxiv.org%2Fpdf%2F1407.1237&ie=utf-8&sc_us=11391865198545652672.
[13] BIELY M, MILOSEVIC Z, SANTOS N, et al. S-Paxos:offloading the leader for high throughput state machine replication[C]//Proceedings of the 2012 IEEE 31st Symposium on Reliable Distributed Systems. Washington, DC:IEEE Computer Society, 2012:111-120.
[14] MORARU I, ANDERSEN D G, KAMINSKY M. Paxos quorum leases:fast reads without sacrificing writes[C]//Proceedings of the ACM Symposium on Cloud Computing. New York:ACM, 2014:1-13.
[15] GILBERT S, LYNCH N. Perspectives on the CAP theorem[J]. Computer, 2012, 45(2):30-36.
[16] 许子灿,吴荣泉.基于消息传递的Paxos算法研究[J].计算机工程,2011,37(21):287-290.(XU Z C, WU R Q. Research on Paxos algorithm based on messages passing[J]. Computer Engineering, 2011, 37(21):287-290.)
[17] 杨春明,杜炯.一种基于Paxos算法的高可用分布式锁服务系统[J].西南科技大学学报,2014,29(2):60-65.(YANG C M, DU J. A highly available distributed lock service system based Paxos algorithm[J]. Journal of Southwest University of Science and Technology, 2014, 29(2):60-65.)

分布式一致性算法Yac

Yac:yet another distributed consensus algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	许红亮, 杨桂芹, 蒋占军. 基于软件定义网络的数据中心自适应多路径负载均衡算法[J]. 计算机应用, 2021, 41(4): 1160-1164.
[2]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[3]	李翠, 陈庆奎. 基于DPDK并行通信的动态监控模型[J]. 计算机应用, 2020, 40(2): 335-341.
[4]	李祝红, 赵灿明, 闫龙, 张信明. 智能电网中电力线通信网络负载均衡的机会路由协议[J]. 计算机应用, 2019, 39(3): 812-816.
[5]	王泽武, 孙磊, 郭松辉, 孙瑞辰. 密码云中基于熵权评价的虚拟密码机调度方法[J]. 计算机应用, 2018, 38(5): 1353-1359.
[6]	鲁亮, 于炯, 卞琛, 英昌甜, 师康利, 蒲勇霖. Storm环境下基于权重的任务调度算法[J]. 计算机应用, 2018, 38(3): 699-706.
[7]	樊自甫, 周凯恒, 姚杰. 基于博弈论的SDN主控制器重选机制[J]. 计算机应用, 2018, 38(3): 776-779.
[8]	耿海军, 刘洁琦. 基于逐跳计算的分布式负载均衡算法[J]. 计算机应用, 2018, 38(12): 3524-3528.
[9]	徐力杰. 非对称占空比传感网中的广播能效优化算法[J]. 计算机应用, 2018, 38(11): 3275-3281.
[10]	罗晓霞, 司丰玮, 罗香玉. 大图结构特征对划分效果的影响[J]. 计算机应用, 2018, 38(1): 1-5.
[11]	周渭博, 钟勇, 李振东. 基于存储熵的存储负载均衡算法[J]. 计算机应用, 2017, 37(8): 2209-2213.
[12]	李强, 刘晓峰. 基于Hopfield神经网络的云存储负载均衡策略[J]. 计算机应用, 2017, 37(8): 2214-2217.
[13]	韩虎, 王鹏, 程琨, 李波. 基于多尺度量子谐振子算法的云计算任务调度[J]. 计算机应用, 2017, 37(7): 1888-1892.
[14]	李祝红, 赵灿明, 周方, 张信明. 电力通信网络中高效的OSPF流量负载均衡协议[J]. 计算机应用, 2017, 37(7): 1873-1876.
[15]	刘必果, 束永安, 付应辉. 基于多目标优化的软件定义网络负载均衡方案[J]. 计算机应用, 2017, 37(6): 1555-1559.