作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 移动互联与通信技术 • 上一篇    下一篇

低带宽广域网环境下的一致性算法研究

马文韬  1,胡创  1,王文杰  2,龚奕利  1   

  1. (1.武汉大学 计算机学院,武汉 430072; 2.密歇根大学,安娜堡 美国 48824)
  • 收稿日期:2015-06-25 出版日期:2016-09-15 发布日期:2016-09-15
  • 作者简介:马文韬(1989-),男,硕士,主研方向为网络通信、分布式计算;胡创,硕士;王文杰,博士;龚奕利(通讯作者),副教授、博士。
  • 基金资助:
    国家自然科学基金资助项目(61100020);华为公司创新研究计划基金资助项目。

Research on Consensus Algorithm in Low-bandwidth Wide Area Networks

MA Wentao  1,HU Chuang  1,WANG Wenjie  2,GONG Yili  1   

  1. (1.School of Computer,Wuhan University,Wuhan 430072,China; 2.University of Michigan,Ann Arbor 48824,USA)
  • Received:2015-06-25 Online:2016-09-15 Published:2016-09-15

摘要: 基于消息传递机制的Paxos算法在执行过程中需要进行大量网络通信,应用于广域网环境时易受带宽的限制而影响算法效率。为此,对Paxos的通信模型进行优化,提出改进的W-Paxos算法。通过在每个数据中心内部增设代理节点来接收、处理和发送广域网消息,从而大幅减少广域网消息数量,解决因Paxos消息过多而引发的网络拥塞、延迟增加等问题。由于仅对经典Paxos的通信模型进行优化,因此改进算法适用于多数Paxos协议族中的协议。实验结果表明,在低带宽环境下,W-Paxos产生的消息数量较Mencius和EPaxos算法更少,能有效减缓领导者的负载压力,提高吞吐率并降低通信延迟。

关键词: 一致性, Paxos算法, W-Paxos算法, 分布式系统, 代理

Abstract: Paxos algorithm based on message passing mechanism incurs a large amount of communication during execution.When applied to Wide Area Networks(WAN) environment,it is vulnerable to the limit of bandwidth,which affects the efficiency of the algorithm.Aiming at this problem,this paper optimizes the communication model of Paxos and presents an improved algorithm,which is named W-Paxos.It sets a proxy node in each data center for forwarding,disposing and sending WAN messages to reduce the messages in WAN massively so as to avoid network congestion and increasing delay.Since W-Paxos only optimizes the communication model without changing other parts of the protocol,it is applicable to almost all Paxos-based protocols.Experimental results show that,compared with Mencius and EPaxos algorithms,W-Paxos generates fewer messages,therefore it can retard the workload of the consensus leaders,increase the throughtput and reduce the communication delay.

Key words: consensus, Paxos algorithm, W-Paxos algorithm, distributed system, proxy

中图分类号: