基于Raft协议的两节点主备系统调度算法

胡琪，王晓懿，贺国平

（北京工业大学北京市物联网软件与系统工程技术研究中心，北京 100124）

0 引言

以城市轨道交通列车指挥调度系统为代表的工业系统，往往在指挥调度中心外的若干运营现场额外部署服务节点。为降低中心离线时运营现场因服务节点故障导致服务中断的概率，需要在运营现场部署冗余服务节点并保证节点间的数据一致性，但产生的工程成本是不得回避的问题。以城市轨道交通列车指挥调度系统为例，一条线路上往往设置了若干个部署服务节点的集中站，如果在集中站部署3台服务器，将比部署两台服务器多出50%的设备采购成本，如图1所示。

Fig.1 Typical architecture of dispatch system图1 指挥调度系统典型架构

此类工业系统往往因工程成本原因在运营现场部署两个服务节点，并且对这两个服务节点有着兼顾可用性与一致性的工程需求。但是，主流的分布式一致性协议受限于多数派的限制，要求分布式系统具有3个以上的服务节点才能兼顾可用性与数据一致性，不适用于此类工业系统。

因此，针对运营现场仅有的两个服务节点在出现单节点故障时无法满足多数派要求问题，本文基于Raft一致性协议提出一种调度算法，通过Ping请求与应答等机制使路由器能够参与Leader选举与数据同步过程，在两节点分布式系统上基本达到三节点分布式系统运行效果。

1 相关研究

如图2所示，为解决分布式系统对可用性与一致性的支持，业界提出了很多解决办法与改进措施。

Fig.2 Brief history of distributed consistency protocols图2 分布式一致性协议简史

WARO协议（Write All Read One）提出发生数据更新时只有在所有的服务器节点上更新成功才认为更新成功，从而保证所有的节点上数据一致。WARO随后被改进，分别提出了2PC协议和Quorum协议。2PC协议将数据同步过程分为Propose和Commit两个阶段，在分布式系统上保持了事务的ACID特性；Quorum算法通过限定读写操作最小参与的节点数为节点总数的半数加一，提高了分布式系统的可用性，能够容忍小于节点总数半数的节点损坏。

通过融合Quorum的多数派设计与2PC的两个阶段，Lamport为业界提供了一个完善的分布式一致问题解决方案，但是工程界在尝试实现Paxos时遇到了理论与应用之间的鸿沟。后续提出了Multi-Paxos、Fast-Paxos、Cheap-Paxos来尝试将Paxos工程化。Ongaro等的 一致性协议受到Multi-Paxos影响，也基于多数派思想以及两个阶段数据提交思想，通过强化Leader节点的地位，保证日志的连续性等简化设计，更加易于工程实现并证明实现的正确性。

Paxos与Raft作为主流的分布式一致性协议，被工程界广泛采用。但是，随着应用范围越来越广，这些主流协议仍需进一步改进以应对新出现的工程需求。

针对工程应用中对性能的更高要求，文献［14］将确定性高的节点选为Leader节点，简化Paxos协议的重确认过程，提高了性能与可用性；文献［15］提出将普通日志复制替换为纠删码复制来降低存储和网络成本；文献［16］中以多数派数据读取的设计替换原有的从Leader节点读取的设计，提高了读性能；文献［17］通过利用固定时段的历史日志故障次数统计，实现最多经历一次计时器时间完成Leader节点的确定；文献［18］针对Raft中故障恢复节点需要多次网络通信才能完成数据恢复的问题，提出了AELR算法，通过一次网络通信获取少量的数据即可完成数据恢复；文献［19］在确保数据同步性的安全同时，通过提升数据同步的并发性来提高吞吐量。然而，此类研究主要聚焦于对性能的提升，均以节点数量满足基础运行要求为前提，没有针对工程成本限制导致的节点数量不足、单节点故障时无法构成多数派的问题进行改进，此类研究可作为本算法后续性能提升的参考。

针对工程应用中对可用性的更高要求，文献［20-21］通过在一些非必须的时刻缩减多数派设计的数量限制来提高Paxos的灵活性；MFTFS文件系统引入热备群集和冷备群集，并通过Raft确定主机，实现主热备集群发生单节点故障时由冷备集群中的节点加入热备集群，继续对外提供服务；文献［23］则将Raft协议放在交换机上运行，节约了服务节点开销；文献［24］在Proposer再次发出prepare请求前增加随机长度的延迟，防止发生活锁；文献［25］在Raft协议基础上根据工作负载的增减实现对分布式系统的自动缩放。然而，Flexible Paxos因为基于Paxos设计，存在工程实现难的问题；MFTFS文件系统与Network-Assisted Raft均会导致工程成本增加；TB-Paxos与Geo-Raft在行为逻辑上提高了可用性，但仍以节点数量满足基础运行要求为前提。

综上，当前大部分研究均无法完美解决本文提出的工程需求。为更有利于工程实现，本文以Raft一致性协议作为理论与设计基础，并对其加以改进，解决两节点分布式系统兼顾可用性与数据一致性问题。

2 两节点主备系统调度算法设计

2.1 对Raft一致性协议改造的难点

为防止分网等故障造成“脑裂”和数据冲突问题，多数派设计贯穿了Raft一致性协议的两个核心工作过程：Leader选举与数据同步。在一个基于原生Raft的两节点分布式系统中，由于节点总数为2，大于节点总数半数的最小数值也为2，因此整个系统的任何操作都需要所有节点参与，这也意味着当Leader节点故障离线时，存活的另一Follower节点因Leader选举得票不足无法成为新的Leader节点；当Follower节点故障离线，仍然存活的Leader节点也会因为数据没有同步给另一节点而无法完成数据提交。

但是，任何尝试对多数派设计的修改都将造成正确性问题，例如一个显而易见的方法就是在一个节点发现与另外一个节点失去联系之后会降低多数派标准，使得节点在不能构成多数派的情况下也能完成Leader选举和数据同步。但一旦发生分网故障，整个系统将会出现两个Leader节点，导致两个节点之间产生数据状态差异。

2.2 让路由器成为分布式系统中的节点

通过降低多数派设计的节点数量来解决多数派限制的方案不可行，则通过增加节点来满足多数派的限制成为唯一方向。

若这个节点是一个工程中成本很低或必不可缺的硬件设备，当这个设备成为分布式系统中的节点之后，不会导致成本超出预期，能够满足工程成本需求。

若在Leader选举以及数据同步过程中该设备能够提供关键的辅助信息，那么就能在不打破任何Raft协议基础理论的情况下，让两台服务器及该硬件设备实现三节点分布式系统运行效果。

路由器支持TCP、UDP、ICMP等网络通信协议，具有提供关键辅助信息的潜力，本算法选定路由器这一必不可少且不会额外增加任何工程成本的设备作为分布式系统逻辑上的第3个节点。

2.3 基础设计

受限于实际设备情况，工程中往往无法让路由器运行Raft一致性协议，因此需要对路由器进行抽象设计，利用路由器上运行的若干网络协议来获取一些关键的辅助信息。

Raft一致性协议通过网络传输的内容十分简单，在Leader选举和数据同步功能中分别用到Append Entries请求、RequestVote请求以及它们对应的应答。考虑到路由器节点无法主动发出这两种请求，本算法将路由器节点抽象地视为一个永远不会尝试成为Leader的Follower节点，因此它无需对外发出任何请求，只需要对请求进行应答。

但是接收这两种请求并应答的路由器也面临无法执行问题。为此，本算法选择将IMCP协议中的Ping请求抽象为Raft协议的两种请求内容，将路由器的Ping应答抽象为对两种请求的执行成功应答。对于Leader选举过程，Ping应答就相当于Leader选举投赞成票；对于数据同步过程，Ping应答就相当于数据同步成功应答。

但是，Raft协议设计的两个应答消息携带了一些额外的重要数据，这些数据肯定无法从Ping请求与应答中获取，需要在现有Raft协议的Leader选举与数据同步设计基础上增加一些设计来弥补这些关键数据的缺失。

2.4 对Leader选举过程的设计

受Raft一致性协议规定，当一个Follower节点收到RequestVote请求时，需要检查请求内容来确定是否发出肯定的投票应答：①请求发出者的数据状态是否陈旧；②请求发出者的Term是否陈旧；③是否投出了该Term下唯一的赞成票。

显然，路由器无法完成这3项检查中的任何一个。因此，只能通过在发出RequestVote请求的节点上增加一些设计来解决这一问题。

由于无法满足③中的检查内容，在网络连接正常情况下，任何时刻服务节点向路由器节点发出投票请求，路由器节点都会回复赞成票，这将造成同一个Term内路由器节点发出多次赞成票，导致分布式系统出现多个Leader节点。然而，路由器在收到Ping请求之后进行应答是路由器的固有行为，并不会因为本算法将Ping应答视作赞成的应答而发生任何改变。

因此，本算法基于分时复用思想设计了全局时钟机制，将物理时间拆分为与选举超时时间上限相同的片段，节点只能在所属时间片段的开始时刻向路由器节点发出投票请求，并且在时间片段和当前Term的选举超时结束前收到应答才算得票。其中一个节点所属时间片段序号为奇数，另外一个所属时间片段序号为偶数，因此不存在同一个时间片段内同时有两个服务器节点向路由器节点发出投票请求的情况，进而保证了同一Term内路由器不会多次投出赞成票。

实际工程中不能忽略网络可能存在的丢包问题，例如有可能出现两个节点间所有的消息包均在发送过程中丢失，但是Ping的消息包却成功接收的情况，此时全局时钟无法阻止多个Leader的出现。为此，本算法增加了对指定IP地址抢占的设计。当一个节点尝试由Candidate状态变为Leader状态时，除了收到路由器的Ping应答，还需要成功执行IP抢占，否则无法转变状态至Leader节点，由此保证分布式系统一定不会在同一Term内出现两个Leader。IP抢占功能可以借用一些网络协议实现，如基于ARP协议的IP漂移，或基于DHCP的IP分配与续约等。

Fig.3 State transition图3 状态转换

情况①与情况②中的检查内容属于对发出请求节点状态的检查，路由器同样会因为对Ping请求进行应答的固有特性而无法完成两项检查内容的处理。因此，本算法将该检查转移到发出请求节点的内部进行。如图3所示，本算法在节点上增加了Ping应答是否有效的状态设计，该状态设计包含available（可用状态）、unavailable（不可用状态）两个状态。处于unavailable状态时，来自路由器的Ping应答将被判定为失效，available状态反之，两个状态之间的转换遵循以下原则：

（1）节点启动，路由器投票状态将处于unavailable状态。

（2）节点与路由器通信失败时将处于unavailable状态。

（3）陈旧的节点数据将处于unavilable状态。

（4）尝试抢占指定IP地址失败时将处于unavailable状态。

（5）当节点处于unavailable状态时，若收到来自其他节点的消息并且所存储的数据为一样新或者更新的情况时，则将状态转变为available。基于上述规则，服务节点与路由器节点交互的行为能够与服务节点间交互的行为保持一致。

对于情况①中的检查内容：请求携带的数据是否从陈旧的判断，本算法利用两个服务器节点间的消息交换使每个节点能知道另一节点的数据情况，进而比较和判断本节点数据是否为陈旧。

以一个节点视角来看，它不能在刚启动或者因为网络问题失去与分布式系统联系的情况下确保数据是最新的，因而规则（1）-规则（3）共同保证了数据可能陈旧的节点不会因为接收到路由器节点的投票而成为Leader，规则（4）避免了丢包等网络故障造成的分布式系统中出现多个Leader节点，规则（5）则用于确定一个节点何时具备成为Leader的潜力。

对于情况②中的检查内容：Term的相关判断和处理，本算法在服务器节点间采用原生的Raft机制，Raft协议已经对它的安全性进行了证明；与路由器节点交互时，本算法取消情况②中对Term的检查。一个节点需要与另外一个节点进行信息交换才有可能进入available状态从而通过Ping应答成为Leader节点。而在进行信息交换时，Raft协议提供了节点间Term同步的措施，保证了节点间的Term一定是同步且最新的。

2.5 对数据同步过程的设计

本算法能够保证数据陈旧的节点一定不会成为Leader节点，而Raft协议规定，只有Leader节点才能发起数据同步，因此路由器节点即便不对数据同步的请求进行检查，在两节点分布式系统中也不会存在正确性问题。

本算法在Raft协议数据同步功能基础上增加了数据同步模式转换机制。当Leader节点能够与Follower节点正常通信时，Leader节点将数据同步的标准提高，收到来自路由器和另外一个Follower节点的数据同步成功的应答后才能将数据提交。

当无法与另外一个Follower节点通信时，将数据同步的标准降低，只要收到来自路由器的数据同步应答即可进行数据提交。判定能否与Follower节点正常通信的标准是，在两个选举超时周期内是否收到了来自Follower节点的数据同步应答，以防止新一任的Leader节点产生之前前一任的Leader提交新的数据。通过该设计，避免了路由器Ping应答速度过快，Leader节点与Follower节点产生较大的数据差距问题。

同时，为了提高算法的可用性，还调整了数据新旧程度判别标准。原生Raft通过最新一条log记录的Index和Term进行判别，本算法将其降低至已提交的log记录的Index进行判别：Index一样新或者更新即为节点的数据状态是最新或者更新的。通过该设计，可在一定程度上避免了大量请求情况下时，Follower节点按照Raft一致性协议的判别标准长期处于数据陈旧状态而无法成为新任的Leader。

当然，本文提出的算法还需要对原生Raft的两对请求与应答消息包进行扩容，增加已提交的log记录的Index信息，以便两个节点能够在消息交换时获知另一节点的数据状态。

3 实验验证

实验以基于本算法的两节点分布式系统作为实验组，以基于Raft协议的两节点、三节点分布式系统作为对照组，验证本算法Leader选举正确性、数据同步正确性、性能及可用性。

（1）在验证Leader选举正确性时，实验以300次客户端请求为工作周期，每个节点在工作周期内随机出现节点停止运行、节点恢复运行、网络断开、网络恢复以及网络丢包的故障情况，以此模拟实际运行过程各种复杂故障情景。实验组与对照组的消息丢包率为30%，断网、停机故障出现和恢复的时间周期为10s内的随机数。通过监测是否出现了多个Leader节点故障，从而证明Leader选举正确性。同时通过统计出现多Leader节点的时长，量化Leader选举问题的严重性。实验组与对照组都进行10次实验，并将最终获取到的实验数据求取平均值。

（2）在验证数据同步正确性时，将复用验证Leader选举正确性的实验设计，由客户端向整个分布式系统发送300个内容为连续数字序号的请求，通过检查每个节点的数据同步结果是否出现了数据不一致问题来证明数据同步的正确性。通过统计问题序号出现的个数，量化数据同步问题的严重性。实验组与对照组同样进行10次实验，并将最终获取到的实验数据求取平均值。

（3）测试系统运行核心性能包括：Leader选举的性能测试、数据同步的性能测试。在测试Leader选举性能时，实验以完成100次主机更迭的耗时作为量化评价标准。为测试数据的准确性，本实验仅将每次前一任Leader节点停机到新一任的Leader出现这段时间列入统计。在测试数据同步性能时，实验以连续完成300次数据同步的耗时作为量化评价标准，记录客户端发出第1个请求到收到第300个请求的应答时间间隔。

（4）在对可用性进行考察时，由于故障情况无法穷举，本实验将测试验证一些典型故障下的可用性表现，每个典型故障下进行5次重复的定性实验。首先将故障情况大致分类为节点停机及恢复、网络故障及恢复。

其中，节点停机及恢复包含：仅有一个节点停机、仅有一个节点停机且从停机中恢复、仅有两个节点停机、仅有两个节点停机且依次从停机中恢复。

网络故障包含：仅有一个节点发生断网、仅有一个节点发生断网并从断网故障中恢复、仅有两个节点发生断网、仅有两个节点发生断网且依次从断网中恢复。

实验结果以分数的形式来量化在某一故障下分布式系统的可用性。统计方式为：

能对外提供服务的情况数量/总情况数量×100

例如：基于本算法的两节点分布式系统，在遭遇其中一个节点发生故障停机时包含3种情况：①Follower节点停机；②Leader节点停机且Follower节点数据与Leader节点一样新；③Leader节点停机且Follower节点数据陈旧。其中，当遭遇Leader节点停机且Follower节点数据陈旧时，基于本算法的两节点分布式系统为了保证数据一致性，将停止对外提供服务。因此，可用性得分为：2/3×100=66.6。

4 实验结果分析

在完成验证Leader选举正确性的实验之后得到如图4所示的结果。

Fig.4 Thelength of time in each state of distributed systems图4 分布式系统处于各个状态下的时长

图4统计了在不同设计下分布式系统存在随机故障情况时完成300次数据同步的工作总时长以及处于各种状态下的时长。测试结果中，基于本算法与基于Raft协议的三节点分布式系统均出现两个Leader节点情况，但是通过对逻辑状态以及系统故障情况的分析，该情况符合设计预期。这两个Leader节点中有一个处于陈旧的Term状态且无法完成数据提交。当丢包或者断网故障恢复后，Term陈旧的Leader节点会自我修复进入Follower状态，整个分布式系统的Leader选举正确性不会受到任何影响。

通过统计数据同步情况得到图5中的统计数据。无论是Raft一致性协议还是本算法，数据同步的结果均没有发生序号缺失、覆盖、重复、前后颠倒等情况。因此，它们的数据不一致个数均为0。

Fig.5 Number of data synchronization and number of data inconsistencies图5 数据同步数量与数据不一致次数

由图6可见，统计了完成100次Leader选举的总耗时，用于检验本算法中Leader选举性能。由于基于Raft协议的两节点分布式系统无法支持仅剩一个节点正常运行情况下选举出新的Leader节点，因此设其Leader选举耗时为无限大。基于本算法的两节点分布式系统的Leader选举性能比基于Raft的三节点分布式系统稍差，但未达到数量级以上的差距，不会对工程使用造成影响，其主要原因是本算法增加了全局时钟以及IP抢占设计，造成一定的延迟。

图7统计了连续完成300次数据同步的总耗时，用于检验本算法中数据同步性能。基于本算法的两节点分布式系统比基于Raft协议的两节点分布式系统在数据同步性能上稍有差距。因为在常规的数据同步工作流程中，本算法需要得到来自Follower节点以及路由器节点的数据同步应答才能完成数据提交。而基于Raft协议的两节点分布式系统中，数据同步给另一个节点之后就能够完成数据提交。此外，由于基于Raft协议的三节点分布式系统需要最终将数据同步给另外两个节点，因此造成时间损耗较大。但总体而言，本算法在数据同步性能方面与Raft协议接近。

Fig.6 Timeto complete100 times Leader elections图6 完成100次Leader选举的耗时

Fig.7 Time to complete 300 times data synchronizations图7 完成300次数据同步的耗时

图8分别记录了基于本算法的两节点分布式系统、基于Raft协议的三节点和两节点分布式系统在各种典型故障情况下可用性测试结果。

本算法的可用性接近于Raft协议。在一些严重的故障下，例如分布式系统中有两个节点同时出现停机、断网故障时，它们均停止对外提供服务。

当分布式系统中一个节点出现故障，基于Raft协议的两节点分布式系统将无法继续提供服务，而基于本算法的两节点分布式系统与基于Raft协议的三节点分布式系统依然能够对外提供服务，只不过本算法为了保护数据一致性，在一些仅剩单个节点存活的情况下也将停止对外提供服务。

Fig.8 Availability test results of distributed system图8 分布式系统可用性测试结果

5 结语

本文基于Raft一致性协议，提出能够在两个节点分布式主备系统中运行的调度算法，在不增加工程成本的情况下具备以下实际工程应用特征：①兼顾可用性与一致性；②保证Leader选举与数据同步的正确性；③性能与Raft一致性协议接近；④可用性方面与Raft一致性协议没有明显差距。

但是，本算法在性能、可用性以及对路由器过度依赖方面仍有进一步提升空间。随着路由器设备的可拓展性逐渐增强，后续可考虑将Raft协议简化，让路由器节点运行Raft协议并记录少量的关键信息，构建由多个路由器与服务节点组成的异构分布式系统。在不显著增加成本的情况下具备与3个以上节点的分布式系统同样优秀的性能与可用性，同时避免因单个路由器故障造成的服务中断。