一种面向小集群同步的改进Raft的分布式一致性模型

余 琅，戴振邦，黄家珞，刘官启，郑林杰，虎俊瑶

（西北民族大学数学与计算机科学学院 甘肃 兰州 730124）

0 引言

分布式云存储服务是新一代数字技术发展的重要基石。分布式系统只能满足一致性[1]、可用性、分区容错性（Consistency、Availability、Partition tolerance）中的两种特性，即CAP理论。对于大部分分布式应用来说，都需要满足A、P特性，舍弃一致性。在保证业务的高并发性、高可用性和高稳定性的同时，如何保证数据的一致性成为一个比较严峻的问题。在最理想的情况下，集群中每个存储单元的变化都能立即被其他节点知道，并且能时刻保持数据的一致性[2]，这就是强一致性模型。但大多数情况下，网络IO是不可控制的。在保证强一致性的大多数情况下，我们会牺牲高可用性，比如Guerraoui等[3]基于增量更新所提出的ICG方案，通过牺牲通信开销和查询正确度，提高了ICG的操作延时。

因此，在大部分分布式应用中选择保证可用性、分区容错性，而舍弃强一致性。与MySQL集群一样，Redis集群采用最终一致性以保证集群数据的同步收敛，来达到分布式系统的稳定性。

1 Raft模型选举

Raft算法[4]是一种基于Paxos的典型主从复制模式，相较于Paxos更加容易理解和工程实现，解决主机选举问题是Raft模型的首要关键点。初始状态下，所有服务器都是Follower，并且随机睡眠一段时间（0～1 000 ms），接着进行倒计时。最先被唤醒的Follower会升级为Candidate，并请求其他Follower为它投票，多于半数则成为Leader。由此完成Leader的选举。

1.1 Raft心跳以及Leader宕机解决方案

在Raft模型中，Leader通过不断地向所有Follower发送心跳包来判断其是否在线的方法来维护一个Follower集合。在某Follower宕机后，Leader会将这个Follower移出集合，以确保每台Follower的可用性。但Leader挂机后，休眠的Follower将进入激活状态，其中某些Follower会进入Candidate状态，并向其他Follower进行选举声明，要求投票，收到半数投票后的Candidate将升级为Leader。

Raft模型利用上述方案解决了集群中主从的转换问题。但在Raft模型中，Leader挂机后可能会同时有多个Follower升级为Candidate。由于在相同的选举周期中每个Follower只有一次投票机会，若群集数量足够，则可以避免同时将多个Candidate升级为Leader。但在少量集群的情况下，若选举过程中Candidate比Follower更多，所有的Candidate都会无法升级为Leader，结果会导致阻塞系统多个选举期。

1.2 最终一致性保证

Raft模型中只有Leader能够执行写操作，当Leader接受写操作时，就更新写日志，同时对Leader管理的Follower进行同步复制。为了确保可用性，只有在其他Follower全部同步完成之后，才会将所读请求负载均衡地分配给各个服务器，否则读操作会全部转发到Leader中操作。

1.3 Raft日志

对于Raft模型来说，每台服务器无论是领导者还是跟随者，都各自保存一份日志。日志来自于客户端的请求，其本身被分成了多条记录，记录是由下标索引的位置来进行确定其唯一性。在记录中有两个主要信息：（1）每条记录都包括一条供状态机执行的命令，命令的格式可以是客户端与状态机所达成一致的某种格式。（2）每条记录都包括一个任期号，这个任期号是该条记录创建时，领导者所处的任期。随着日志记录的增多，这个任期号也会单调上升。每台服务器都必须保证日志能在崩溃后还可以恢复，所以日志通常是存于磁盘或其他稳定的存储介质中。无论服务器作何更新，它都需要在接收到其他服务器的响应之前将内容写入磁盘。如果某条记录在大多数服务器的日志中都存在，那么我们就称该条记录已提交(Committed)。如果一条记录是已提交的，那么它就能安全的被状态机执行，Raft 就可保证该条记录的持久性。

1.4 Raft日志一致性

Raft期望能将集群日志维持高水准的一致性。理想状态下，所有日志在任何时候信息都是相同的，甚至是服务器崩溃时也如此。虽难以达到理想状态，但Raft会尽可能地保证在所有服务器上的日志是一样的。

日志记录的索引以及任期号在任何时候都是有效的，他们的组合可以唯一地标识每一条日志的记录。如果在不同的服务器中有两条记录的索引是相同的，任期号也是相同的，那么就可以保证它们所存储的记录也是相同的。除此之外，还能保证在这条记录之前的所有记录都能一一对应。所以任期号和索引的组合可以保证整个日志的起始位置至该点位置的记录的一致性。如果某条记录是已提交的，那么在该记录之前的记录都应该处于已提交状态。

2 Raft模型针对小集群优化方案

2.1 同步方案——网状同步

在同步方案中，我们不采用Raft的原本同步方案，Leader不再主动进行心跳检测，而是让Follower进行定期向Leader报告当前信息。Leader会添加Follower集合和Leader集合的差集，然后将其发送给Follower最新的集群集合。通过这种方式，我们可以确保所有Follower都能在一个周期内与Leader维护系统的集群集合相同，实现网状同步。

如图1所示，若服务器在接入时因为网络等问题发生故障，导致Follower相对于Leader发生分区（图1左），就不可实现分布式的可用性。但在经过上述过程（网状同步）之后，Follower会重新被分配到Leader上，同时该服务器会对Leader进行同步，从而解决分区问题。

2.2 选举问题优化方案——继承

上文提到了当 Leader发生宕机时 Raft模型所提供的解决方案，并提到了在该解决方案中由于集群较小，服务器数量较少可能导致多个选举周期阻塞问题。该问题的关键在于同一时间有多个Follower升级为Candidate的投票分歧问题。吴奕等[5]提出了为每个节点设置C标志位的策略。但该方法适用于具有大量节点的集群。那么我们在小集群中可以选择使用Leader定期地选择出下一个Candidate的方法来解决该问题。在 Leader发生宕机之后，Candidate经过其他 Follower同意便可继承 Leader的角色（这里为了确定Leader发生宕机问题，Candidate不可以直接升级为Leader，要由半数以上的Follower同意后才可以升级为Leader）。同时 Raft算法中的周期选举被替换为周期分配。在周期分配模式中，Leader将为所维护的节点集合分配角色，包括一个 Candidate和多个Follower。

2.3 优化后每个节点的工作流程

如图2所示：在优化之后，每个服务器在一个工作周期中执行以下任务：Leader：定期发送任命报告，为每个服务器分配新的角色。Candidate：定期检查Leader的存活状态，若发现宕机就让Follower进行检测，一旦有一半以上的Follower检测到Leader不在线，则Candidate将立即升级为Leader，并为所有的Follower分配新角色。若当Leader在线时，Candidate也会进行Follower的工作。Follower：定期上报服务器集合状态，更新最新的服务器集合。

2.4 优化效果

以上的优化，在我们用Goland语言设计的goDFS——分布式文件系统中得到实现。在实验过程中可实现网状同步。在选举过程中，通过Leader定期地选择出下一个Candidate，不再使用Raft模型原始的选举方法，可以有效避免同时产生多个Candidate，避免不断重新选举导致系统堵塞的情况。

在选举过程中，Leader通过继承的方式定期地选择出下一个Candidate。虽然该方法使Leader和Candidate同时宕机的概率非常小，但在实验中我们也手动停止Leader和Candidate的运行，结果是会导致集群崩溃，说明该算法后期还需进行优化。

2.5 优化后的集群失效问题

通过上述说明，继承模式相对于选举模式而言，不会产生多个Candidate竞争所引起的选举周期阻塞问题，在Leader正常的情况下有更小的开销。但继承模式相对于选举模式来说安全性较低，如当Candidate和Leader同时宕机时，则不能将其恢复为正常状态，即Leader会失效。对于小型集群来说，Leader的压力更大，而Candidate和Leader同时宕机的概率是极小的。而且在少量机器中，两个节点同时失效，也会使集群崩溃。但在一般情况下，小集群中使用继承模式是可以保证集群稳定运行，且一定程度上可解决小集群同步问题。

2.6 继承失败问题以及解决方案

继承的解决方案虽然一定程度上解决了Raft竞争选举中断导致的多集群问题，但是继承方案仍然存在一定的问题，如可能发生Leader和Candidate同时挂机的情况（在Leader重新任命一个Candidate之前，Leade发生故障，并且同时Candidate也发生故障导致导致节点继承失败）。对于该问题我们可以对选举流程进行优化。一种可行的方法是，Leader在选举时可以指定多个Candidate作为候选者，通过对Candidate的冗余来解决上述问题。当Leader和其中一个或多个Candidate宕机时，其他Candidate可以再次请求Follower进行投票来选举Leader。但同时，也会引入多个Candidate竞争的问题，这时我们可以控制在选举Leader时对 Candidate进行排序，使得 Candidate形成线性关联关系，即使在选举过程中发生多个Candidate升级为多个Leader的问题，也会在下一个周期由最高级别的Candidate（Leader）发生网状同步来恢复集群的一致性。但系统在一段时间可能会出现多个集群，即便恢复后，也有可能发生日志的冲突，因此需要一定的时间进行恢复。

第二种方法是由Candidate选择一个服务器进行信息备份，Candidate的备份服务器会监听Candidate的状态。当Candidate以及Leader都发生宕机时，Candidate的备份服务器则会进行继承升级，成为新的Leader。虽然这种方案并没有从根本上解决Leader以及Candidate同时失效的问题，但是在集群数量较少的情况下，Candidate以及Leader都发生宕机后，则整个系统大概率将会进入降级或者不可用的状态，所以在一定程度上可以解决Leader以及Candidate同时失效的问题。

3 结语

本文针对Raft模型在小集群情况下对Leader选举方案和日志同步方案进行优化，但仍有些问题需要探讨和研究。如在选举过程中我们采用的是继承的方法，通过Leader状态的服务器定期地选择出下一个Candidate。但该方法可能会出现Leader和Candidate同时宕机的极小概率情况，在小集群中会导致集群崩溃。在3.5所提的方法中，Leader在选举时指定多个Candidate作为候选者的方法会使得某段时间内系统出现多个集群，需要一定的时间来进行恢复，即便恢复后，日志也有可能发生冲突，所以恢复所需要的时间具有不确定性。但在小集群中由于节点少，同步日志的时间和恢复时间仍然是较短的，因此该方法仍然具有一定的可行性。另一种方法是由Candidate选择一个服务器进行信息备份，这种方案并没有从根本上解决Leader和Candidate同时宕机的问题，但Candidate 和Leader同时宕机大概率会使得系统将会进入降级状态或者崩溃不可用，所以该方法在小集群中的使用仍然具有一定的适用性。因此这些问题优化的设计和实现后期仍有待研究。