类Paxos共识算法研究进展

Paxos-like Consensus Algorithms:A Review

随着互联网数据量和业务量的快速增长,集群规模越来越大,由于机器和网络等故障使得业务中断的可能性越来越高.如何实现一个容错的分布式系统十分重要.多机达成共识是分布式容错系统中一个最基础,最核心的问题.Paxos等一系列共识算法的出现有效地解决了这个问题.近年来,越来越多的系统使用共识相关技术,关于分布式共识算法的研究也层出不穷.这些共识算法可以被划分成2个大类:强领导者共识算法和弱领导者共识算法.随着远程直接内存访问(remote direct memory access, RDMA)等网络技术和现场可编程门阵列(field-programmable gate array, FPGA)等硬件技术的发展,又出现了一些结合新型网络和硬件技术的共识算法研究,用来提升分布式系统的性能.将从分布式共识算法发展历程的角度,介绍Paxos系列算法,阐述算法演进过程中的关键研究,讨论相关算法在不同场景下的优劣势,并展望该类算法的未来发展方向与前景.

With the rapid growth of data volume and Web services,the cluster size is getting bigger and bigger in datacenters.The probability of service interruption grows dramatically due to machine and network failures.How to achieve a fault-tolerant distributed system becomes very important.State machine replication is one of the most general methods for building a fault-tolerant system,and distributed consensus problem is one of the most basic and core issues in replicated state machine systems.Paxos and a series of Paxos-like consensus algorithms can effectively solve this problem.In recent years,more and more systems use consensus-related techniques to ensure their reliability and availability,and studies on distributed consensus algorithms are also emerging in an endless stream.These consensus algorithms can be divided into two categories,leader-based consensus algorithms and leaderless consensus algorithms.With the development of network technologies such as remote direct memory access(RDMA)and hardware technologies such as field-programmable gate array(FPGA),some consensus algorithms combining with new network technologies and hardware technologies have appeared,which are used to improve the performance of distributed systems.In this paper,we introduce Paxos series algorithms from the perspective of the development of distributed consensus algorithms,discuss the advantages and disadvantages of the algorithms in different scenarios,and further give a future outlook on the research and application directions.