改进的Raft一致性算法及其研究

陈 陆,黄树成*，徐克辉

(1.江苏科技大学 计算机学院,镇江 212003)(2.中国船舶重工集团有限公司 第七二四研究所，南京 211153)

分布式领域中的一致性[1]、可用性和分区容错性理论(consistency,availability,partition tolerance,CAP)告诉我们,任何一个分布式系统都无法同时满足一致性、可用性和分区容错性这3个基本需求，最多只能满足其中两项．但是,一个分布式系统无论在CAP三者之间如何权衡,都无法彻底放弃一致性,如果真的放弃一致性,那么就说明这个系统中的数据根本不可信,数据也就没有意义,那么这个系统也就没有任何价值可言．

一致性问题指多个服务器在状态上达成一致.但是在一个分布式系统中,因为各种意外,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态．这样就需要一种一致性协议.一致性协议是为了确保容错性,也就是即使系统中有一两个服务器宕机,也不会影响其处理过程．过去,Paxos一直是分布式一致性协议的标准,但是Paxos难于理解,更难以实现,Google的分布式锁系统Chubby[2]作为Paxos的实现，曾经出现很多问题．

Raft是由斯坦福大学的文献[3]中提出的一种基于复制状态机的分布式一致性算法．Raft算法在没有对Paxos的性能和精确度作让步的情况下,扩大了应用场景并且比Paxos更易于理解．

文中基于文献[3]中关于Raft的性能分析实验,将Raft算法部署在由5台虚拟机组成的集群上,在应用Raft一致性的集群上的实验结果表明:文中提出的事务磁盘持久化、网络日志同步，与传统的Raft相比,在频繁更新日志信息条目的情况下获得了良好的效果．此外,较传统的Raft而言,优化过的Raft极大程度降低了读写磁盘的频率,进而提高了Raft算法的效率．

1 相关研究

分布式系统的一致性框架是以复制状态机为原型搭建的(图1).

图1 复制状态机部件Fig.1 Components of the replicated state machine

复制状态机的原型由状态机(支持容错功能)、日志存储模块、一致性模块3部分组成．当前最流行的开源分布式一致性应用程序ZooKeeper和被应用于Google FileSystem和 BigTable的支持容错恢复的分布式锁服务Chubby都基于此而实现．

保证复制日志相同是一致性算法的工作．在一台处于Leader角色的服务器上,一致性模块接收客户端发送来的指令，然后增加到自己的日志中．它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的指令,尽管有些服务器会宕机．一旦指令被正确复制,每一个服务器的状态机按照日志顺序处理他们,然后输出结果被返回给客户端．因此,服务器集群看起来形成一个高可靠的状态机．

2 改进的Raft算法

2.1 算法假设

Raft算法成立的前提条件和Multi-Paxos[4-6]一样,其基本假设:

(1) 分布式系统是异步的,例如,消息传递的延迟时间没有上界或者执行计算的时间也没有限制．我们不能假设此分布式系统是时钟同步的．

(2) 集群中节点间的网络通信是不可靠的,包括网络延迟、数据包丢失等情况．

(3) 不能发生拜占庭错误．

(4) 客户端的应用程序只能和集群中的Leader节点交互,并且一个集群中的Leader节点是通过集群自身的选举算法选举出来的．

(5) 集群中的每一个节点都有一个单调递增的纪元值(term)．

(6) 运行在每一个节点上的状态机初始状态都相同,并且根据客户端的操作准确返回交互信息．

2.2 Leader选举

集群中的Leader节点每隔Timeout时间就会向Follower发送空的心跳包,如果Timeout时间内,Leader收到了Follower的心跳包的回复,那么它就会始终保持Follower状态．如果节点在Timeout时间之内没有收到来自Leader节点的心跳包,它就会认为集群中的Leader节点出现了故障,那么处于Follower状态的节点就会升级成Candidate．

一旦一个节点的状态从Follower变成Candidate,该节点的纪元值就会在原来的基础上加1,发起选举,图2是一个用非确定型有穷自动机表示的Raft算法中各节点的状态转换图．

通常这样的一组进程Π={P1,P2,P3,…,PN} 组成的分布式系统中,其每一个进程都存在于各自的节点上,各进程节点之间通过互相通信来实现消息传递,每一个进程都有可能因一次或者多次的进程崩溃而退出,这些进程也会在恢复原来状态之后重新加入到Π中,当进程Px(1≤x≤N)收到Π中大部分的节点发送的Request Vote数据包,该进程所在的节点当选为Leader节点,我们将投票的节点子集称为Quorum，文中用Q表示,并且其满足:

∧ ∀Q,Q⊆Π

∧ ∀Q1和Q2,Q1∩Q2 ≠φ

其中Q1和Q2 为Π中的任意两个子集．

如图2,选举的结果会有两种可能性．① 某节点收到了集群中大多数节点的Request Vote数据包,该节点赢得此次选举,从Candidate状态升级为Leader；② 集群中没有一个节点收到集群中的大多数节点的Request Vote,因此,该集群重新发起一次选举．

图2 Raft算法状态转换模型Fig.2 State transition model for Raft algorithm

2.3 改进算法的策略

既然当一个节点已经被选举为该集群中的Leader,那么它就能为复制状态机处理来自客户端的事务请求,客户端通过指令来和Leader节点交互,Leader把客户端的指令都提交到复制状态机中．Leader节点把每一条接收到的指令加上索引,保存到自己日志当中．Leader节点将收到的这条指令拷贝到为该节点投票的集群中的大多数节点中,保存到各节点的日志中,然后提交执行[7]．

如图3,当Leader节点,即节点1的一致性模块收到了y←9这条指令,节点1首先将它复制到自身日志中,然后通过RPC,以Append Entries Request数据包的形式发送到处于Follower状态的节点2和节点3中,假设不会发生任何异常,节点2和3将这条指令复制到自身的日志中,并且返回SUCCESS给节点1．节点1收到SUCCESS后,将该条指令条目提交,并且向节点2和节点3发送Commit,节点2和节点3提交指令,最终集群中的节点状态达到一致．

图3 日志提交的简单示例Fig.3 Simple example of log submission

当有数据时,Leader向Follower不断发出Append Entries Request数据包,每个Append Entries Request可以包含多个日志条目,每个Append Entries Request被正常处理后，Follower都会发回一个Append Entries Response.为了简单起见,Leader在超时未收到Append Entries Response的情况，不会发出下一个Append Entries Request,此时即使Leader有比上次发出的Append Entries Request所包含的最后一个日志条目更加新的日志条目,也要等到收到Append Entries Response后才开始同步．在这种单步的日志同步方式下,网络的延时越长,就对Leader节点同步提交的吞吐量的影响越大．

基于TCP协议中的滑动窗和长肥管道机制中,窗口相当于一个缓冲,TCP传输报文要求每个都有确认．在实际传输数据的时候不可能每个报文发送后就立即收到确认,如果每发送一次报文就等待确认,会导致传输速率变慢,所以TCP允许在没收到上一个确认前发送下N个报文,但是发送报文不能超过窗口大小.如果窗口设置较小,而此时又处于长肥网络当中,就会导致有些响应报文还未到达发送端时,发送端就已经达到窗口大小,这时发送端就必须重新发送之前的报文(而实际上只是接收端的响应未到达发送端),这样就会导致报文有大量重传,叠加效应就会导致传输速度远低于带宽(被无用的重传占用了).相反,窗口足够大,发送端连续发送的N个报文都能在窗口内收到响应,不会有数据重传,理论上的传输速度就会等于带宽值．

根据此理论，可以将同步方式改进为:如果连续多次发送的Append Entries Request数据包都及时收到了Follower节点的回复,那么则认为网络连接是通畅的,就可以改同步单条的提交模式为异步多条．此时Leader将多个Append Entries Request先后发出,然后统一等待回包．采用这种方式可以提高日志同步的吞吐量,但却增加了实现的复杂度,要增加两个模式的跳转,异步模式时的回包乱序,重放处理等．

出于持久化的目的,提交到复制状态机的日志条目都会写进磁盘,因此每次提交日志都需要读写一次磁盘,大大降低了效率．因此,在类UNIX系统平台上,一般通过将数据写入内存后调用Fsync来使日志从内存保存到磁盘．服务器使用的机械盘每秒进行读写操作的次数(inpnt/output operations per second,IOPS)只有300～400次，而固态硬盘SSD的IOPS有几千次,如果每次将一条日志条目写入磁盘就调用一次fsync,那么每秒的写吞吐量只有对应的IOPS,是相当低的．如果将fsync操作的时延平摊到多个日志条目,也就是采用批量写入磁盘加上fsync的方式,则可以提高每秒吞吐量．若将进行fsync写的每批日志条目数定义为M,将每秒最多可以完成的fsync写操作的次数定义为N,那么吞吐量IOPS为M×N.IOPS值对于M的变化曲线是一个类似倒U型曲线，如图4.经测试,对于固态硬盘,当M=2 000,N=300的时候曲线到达高点,此时的吞吐量约为600 000,此后,随着数据包内的日志条目的增加,IOPS值会随之减小．采用这种方法可以提高当有事务操作时磁盘的吞吐量,但却增加了日志条目的写平均延时．

图4 IPOS值变化曲线Fig.4 Changeing curve of IPOS values

3 实验及性能分析

实验的运行环境如下:3台虚拟机内存为4GB, CPU 为Intel Core i3-2310M 2.39 GHz,2台虚拟机内存为4GB, CPU 为Intel Core i3-2310M 2.39 GHz,5台虚拟机在同一网段内,操作系统为Ubuntu 14.04,IDE为LiteIDE,使用编程语言为Golang．

为了评估文中提出的改进的Raft算法的有效性,从3个方面对改进前后的算法进行对比分析:① 测试在600 ms和900 ms内,当集群中的Leader节点出现错误,未能在Timeout时间内对Follower节点发送Append Entries Response数据包,集群中重新选举出新 Leader节点的成功的概率；② 当集群中出现2台虚拟机(非Leader节点且小于半数的机器)宕机时[8],集群能恢复对外服务所需要的时间；③ 当集群中出现节点移动、网络稀疏或信号衰减等各种原因常常导致网络连接中断和网络分割(network partition),此时出现2个或多个Leader,当网络连接恢复后,集群恢复正常状态所需的时间．

表1、2为根据Follower状态节点Timeout值，不同算法在一定时间内选举出Leader节点的成功概率．实验结果表明,改进Raft算法显著缩短了集群中选举出Leader节点的时间,进而提高了效率．

表1 原始Raft算法和改进后Raft算法在600 ms内不同的Timeout下选出Leader节点的成功率Table 1 Success rates of selecting Leader node in 600 ms of Timeout of initial and improved Raft algorithm %

表2 原始Raft算法和改进后Raft算法在900 ms内不同的Timeout下选出Leader节点的成功率Table 2 Success rates of selecting Leader node in 900 ms of Timeout of initial and improved Raft algorithm %

设定了5组实验,实验中每次都使集群中的相同的两台虚拟机宕机,然后测试集群继续恢复对外服务所需的时间．

图5 在小部分节点发生故障的情况下,集群恢复服务所需的时间Fig.5 Time required for the cluster to restore the service in the case of minority of nodes failure

从图5可以看出,优化过的Raft恢复的时间要明显少于未优化过的算法版本．

在实际应用的大型分布式系统中,多个集群会不在同一地域内,但仍然对外提供相同的服务[9]．因此,在虚拟机集群中模拟了出现网络分区故障的情况,同样设定了5组实验,每次使相同的两台机器出现分区,然后再恢复网络连接,从而测出恢复对外服务的时间(图6)．

图6 在出现网络分区故障的情况下集群恢复服务所需的时间Fig.6 Time required for the cluster to restore the service in the case of network partition failure

4 结论

文中对解决分布式系统中的一致性问题的Raft算法进行了探讨.在传统的Raft算法中,由于需要保证日志条目不会因为节点中进程崩溃而消失,因此需要将条目不停地保存到磁盘中,并且传统的Raft算法每次收到一个条目便写一次磁盘,大大耗费了时间．并且,Leader节点只有在正常确认发送给每一个Follower节点的Append Entries Request得到正常回复才会继续地工作,这会导致一旦某个节点异常,集群中的leader节点始终无法发送下一条指令．为了缓解不足,文中针对上述问题提出了优化方法．实验结果表明,文中提出的写磁盘持久化和日志的网络同步能够在保持算法准确运行的同时,提升算法的效率．