raft 是目前工业界广泛使用的分布式一致性协议, 被广泛应用在分布式系统中, 例如 ETCD、TiKV、Consul 等著名开源软件都使用了 raft 协议来实现分布式系统中的强一致性, paxos 算法作为分布式一致性算法的鼻祖, 其以难以理解和很难工程化著称, raft 的作者希望设计一种更简洁的算法来替代 paxos, 使其在保证正确性和可靠性的前提下能够容易理解和实现, 本文详细剖析了 raft 协议的设计思想和实现原理, 便于读者更清晰地了解 raft 协议

3.1 问题背景

系统的可靠性是系统开发人员需要考虑的一个重要问题, 在一些关键的业务场景中, 系统宕机将会造成灾难性的后果, 冗余是提升和保证系统可靠性的一种有效的手段, 这可以用一个简单的概率公式来量化这个指标, 假设单机系统宕机的概率为 , 则设置 N 个结点以后, 系统宕机的概率将会降低到 (我们假定结点之间是相互独立的, 并且不考虑系统的公共模块对系统可用性的影响), 这样便构成了分布式系统的雏形, 当然还要做一些额外的操作, 比如对结点的管理、流量的分配等, 分布式系统简单来说就是由多个计算机组成的集合共同对外提供服务, 在外部看来, 它们就像是一个整体, 分布式系统设计的目的不仅仅是为了提高可靠性, 同时也可以并行地处理那些没有先后顺序的任务从而提升系统效率, 但分布式系统带来这些好处的同时也引入了新的问题, 一个典型的问题是如何保证多个计算机结点之间的数据一致性, 这是一个富有挑战性的问题, 系统中的任何结点在任何时刻都存在宕机的可能, 还有网络延时、丢包、数据在网络传输过程中出错等各种情况的出现, 分布式一致性算法即是要解决以上这些问题, 保证分布式系统中各个结点的数据一致性

3.2 概述

在详细讨论 raft 协议之前, 先给出协议中的一些基本概念

  1. 复制状态机(Replicated state machines)

    • raft 引入了复制状态机的概念(Replicated state machines), 将集群中的每个服务器看做一个状态机, 它们接收外部的指令, 进行状态的改变, 例如机器的存储器就可以看做是一个状态机, 它们接收来自外部的指令, 进行数据的写入和更新, 假定内存 A 地址有一个值为 3 的变量, 在没有接收到新的外部指令的时候, A 地址的值一直保持为 3, 当接收到例如 的指令后, 状态机(内存)进行状态的改变, 其 A 地址的值变更为 5, 不考虑硬件错误, 这样的状态机是一个确定型状态机, 即只要初始状态和接收到的指令是确定的, 那么它任意时刻的状态也是确定的, 这样以来, 所谓保持分布式一致性即是保证集群中所有状态机的状态一致性

  2. 领导人(leader)、跟随者(follower) 和 候选人(candidate)

    • 在 raft 协议中, 所有服务器结点的地位不是对等的, raft 将所有服务器结点划分为 3 个互不相交的子集, 任何一个结点都隶属于某一个集合, 其中地位最高的结点称为领导人(leader), 它负责接收来自客户端的调用, 组织日志复制给其它结点, 统筹管理整个计算机集群, raft 保证集群中在任意时刻至多有一个领导人, 跟随者(follower)接收来自领导人(leader)的复制日志, 按照领导人(leader)的要求进行相应的动作, 跟随者持续地向集群中的所有其它结点发送心跳包, 向集群中的所有结点宣示他的权威, 以维护自己的统治地位, 一旦跟随者(follower)在给定的时间内没有收到来自领导人(follower)的心跳包, 它便认为领导人出了故障, 于是转变自己的身份为候选人(candidate)进行领导人的竞选

  3. 任期(term)

    • raft 将系统时间划分为一个个逻辑段, 每个逻辑段的时间长度是不一致的, 可以是任意长度, 每一个逻辑段称为一个任期(term), raft 对每一个任期都设置一个整型编号, 称为任期号, 每一个任期可以进一步划分为两个子段, 其中第一个子段是选举期, 第二个子段是任职期, 选举期将竞选产生集群的领导人, 若领导人选举成功, 则进入了任职期, 在任职期内只要领导人持续保持健康状态(即持续不间断地向其他跟随者发送心跳包), 则这个时期可以无限期地持续, 当然在 raft 中选举不一定都是成功的, 可能存在某个 term 中的选举期没有任何候选人胜出, 这样 raft 会进行下一个 term, 重新进行选举, 直到有新的领导人胜出, 从而进入任职期, 下面我们将看到 raft 采用了特别的机制来尽可能地避免一个 term 中没有任何候选人竞选成功的情形出现

  4. 日志(log)与日志复制(log replication)

    • 在 1 中我们提到, raft 将集群中的所有服务器看做若干个状态机, 状态机接收指令进行状态的变更, 在 raft 协议中, 指令是以日志的形式的传递的, 虽然集群中有 个结点, 但只有一个结点(领导人)接收客户端的请求, 其它所有结点接收来自领导人的复制日志(Replicated log), 进行解析、和执行, 从而进行状态的变更, 所有服务器结点按序执行相同的日志(指令), 从而保持状态一致性

  5. 日志提交(commit)

    • 领导人在接收到客户端请求之后, 会产生一个相应的日志项(log entry), 日志项中包含了指令, 领导人不会立即执行这个指令, 它首先会进行日志项复制, 当日志项被成功地复制到集群中的大多数结点 后, 领导人会提交(commit)这个日志项, 并执行其中的指令(即将该日志应用(apply)到状态机中)

3.3 领导人选举(Leader Election)

从这一节开始, 我们将详细讨论 raft 协议的设计思想与实现原理, 首先来讨论领导人选举模块, raft 协议保证在任何时刻系统至多只有一个领导人, 领导人会周期性地向其它各个结点发送心跳信息, 以维护领导人的统治地位, 当跟随者超过特定的时间没有收到领导人的心跳信息之后, 它便认为领导人已经宕机或因为其它原因而不可用了, 这时跟随者将发起新的领导人选举, 对于系统中的每个结点, 无论其身份如何, 都拥有一个 currentTerm 的变量, 该变量表征了当前的任期号, 跟随者在发起新一轮选举时会首先将自己的 currentTerm 变量加一, 然后将自己的身份转换为候选人(candidate), 然后并行地向系统中其它所有结点发送 RPC 请求, 以请求大家为自己投票, 同时它也会将自己的选票投给自己, raft 协议要求每个结点至多只能将选票投给一个候选人, 当候选人收到了超过半数的选票时便选举成功, 身份转变为领导人, 此时选举过程结束

当然实际的情况或许不会这么顺利, 当领导人宕机以后, 可能有多个跟随者都同时或几乎同时发现了这一状况, 他们都立即转变了为候选人, 并发起了选举, 最后可能出现大家的选票不相上下, 使得没有任何一个候选人胜出, 如若不采取其他措施, 系统将陷入死锁而无法挣脱出来, 为了解决问题, raft 协议对每一轮选举都设置了超时时间, 对于每一个跟随者, 从它转变为候选人发起选举的时刻, 会将选举计时器归零, 如若计时器超过了设定的超时时间, 系统中仍然没有新的领导人被选举出来, 则此轮选举失败, 候选人会将 currentTerm 再加一, 并发起新一轮的选举, 同时会重新将选举计时器再次归零, 这样可以避免系统出现死锁, 但是仅仅加入选举计时器是不够的, 试想这样一种场景, 某一时刻, 系统中的领导人发生宕机, 跟随者在指定的时间间隔内没有收到来自领导人的心跳信息, 于是转变自己的身份为候选人并发起选举, 原先的跟随者在几乎相同的时刻发起了选举, 即便设置了超时计时器, 也可能出现候选人几乎同时到达选举超时的情况出现, 此时所有候选人又几乎同时发起了新一轮选举, 如此这样下去, 系统会耗费大量的时间在领导人选举上, 即如若不采取额外的措施, 系统会发生大量的「选举碰撞」, 为了避免这种情况的出现, raft 将选举超时时间改为了随机化, 每个结点都在一个固定的时间长度内随机选定一个选举超时时间, 这样即便大家同时发起选举, 由于每个结点的选举超时时间是不同的, 因为系统中一定存在一个结点会首先达到选举超时, 这时它又发起新一轮的选举, 由于每次选举都会将 currentTerm 加一, 所以最早达到选举超时的结点再发起新一轮选举后, 它的 currentTerm 比系统中的其它候选人结点都大, 从而赢得选举, 随机化不仅仅用在选举超时时长上, 也用在了两次选举之间的等待时长上, 对于候选者来说, 当一轮选举达到超时时间, 并且没有选出领导人后, 它不会马上开始下一轮选举, 而是等待一个随机的时长, 等待一段时间后重新发起新一轮选举, 这样以来, 不同候选者之间发生选举碰撞的概率大大减少, 这里的思想其实很类似于以太网的 CSMA/CD 协议(载波监听多点接入/碰撞检测协议), 都是用随机化的等待时长来尽可能地减少碰撞

候选人在竞选的过程中, 可能收到声称自己是领导人的结点发来的数据包, 候选人会检查数据包中的 currentTerm, 如果数据包的 currentTerm 大于或等于候选人自身的, 则候选人会放弃选举, 并将自己的身份转变为跟随者, 反之, 它会拒绝这个数据包, 并继续保持候选人的身份进行竞选

至此我们可以看到, 系统中的结点可能会在领导人、跟随者、候选人之间发生转变(如上图所示), 当跟随者超过特定的时间没有收到来自领导人的心跳包时会转变为候选人, 当候选人竞选失败时, 会重新转变为跟随者, 当候选人竞选成功时, 会转变为领导人, 当一个领导人发现系统中有任期号(term number)比自己大的结点时, 会将自己的身份转变为跟随者

3.4 日志复制(Log Replication)

日志复制是 raft 协议的一个关键模块, raft 协议为了简化, 约束了日志数据的流向只能从领导人到其它结点, 领导人接收来自客户端的请求, 并将客户端的请求转换为一个日志项(log entry)追加到它的日志中, 然后它会并行地向其它所有结点发送数据包, 将新的日志项传递给其它所有结点, 当集群中的大多数结点都获得了日志项副本之后, 领导人会提交该日志, 并执行指令改变状态机的状态, 这里注意 commit(提交) 和 apply(应用) 的区别, commit 是针对日志的, apply 是针对状态机的

前面提到, 我们不考虑硬件错误, 所有结点的状态机都是确定型状态机, 因此只要保证日志的一致性(这里的一致性不仅仅包括每个日志项的内容一致, 同时包括日志项的顺序也是一致的), 则状态机按序执行日志后, 最终的状态也一定是一致的, 因此 raft 算法的关键转移到了保证日志的一致性上, raft 将日志组织成线性结构, 日志是由日志项串联而成的, 同时会有一个索引来标识每一个日志项的相对位置, 每一个日志项可以用一个二元组来表征

log entry := (term_number, command)

即每一个日志项都包含有该日志产生时的领导人的任期号, 以及所要执行的指令, 对于领导人来说, 无论何时、无论发生何种状况, 都需要做到日志只能增添而不能删除, 领导人对集群有绝对的权威, 当领导人与跟随者的日志不相同时, 跟随者会用领导人的日志覆盖自身的, raft 协议保证领导人在将日志复制给其他结点之后, 对于任意一个其它结点的日志和领导人的日志相比, 若某一日志项的索引和任期号都相同, 则其中存储的指令一定是相同的, 这点源于 raft 要求领导人在某个任期之内, 在指定的索引上至多会产生一个日志项, 并且领导人不允许对日志项做删除或变更位置(改变索引)操作; 其次, raft 协议保证若不同结点日志的两个日志项的索引和任期号都相等时, 则小于此索引的所有日志项都相等, 对于这一点, 当领导人向其它结点发送日志项的时候, 会同时携带着该日志项的前一个日志项的索引和任期编号, 我们记为 (preLogIndex, preLogTerm), 跟随者收到数据以后, 首先检查其是否含有索引为 preLogIndex 和任期号为 preLogTerm 的日志项, 若不含有, 则拒绝领导人发来的这个请求, 领导人对所有的跟随者维护了一个 nextIndex 列表, 列表的每一项都对应着领导人下次将发给某个跟随者的日志索引, 当领导人刚刚当选时, 它会将所有跟随者的 nextIndex 都初始化为其自身的最大的日志索引加一(领导人假设它刚刚当选时, 所有跟随者和自己的日志是相等的), 但其实这时可能存在部分跟随者, 它们的日志比领导人少, 当领导人向它们发送索引为 nextIndex 的日志项时, 在发送的同时会附带着该日志项的前一个日志项的索引 preLogIndex 和前一个日志项中的任期编号 preLogTerm, 当跟随者自身不含有索引为 preLogIndex 并且任期号为 preLogTerm 的日志项时, 它会拒绝领导人发来的日志项, 此时领导人将该跟随者的 nextIndex 减去一, 同步地, preLogIndex 也减去 1, preLogTerm 更新为 preLogIndex - 1 的日志项包含的任期编号, 然后向该跟随者发送新的 nextIndex 对应的日志项,并且附带着新的 preLogIndex 和 preLogTerm, 如果跟随者仍然不含有索引为 preLogIndex 和任期编号为 preLogTerm 的日志项时, 则领导人继续将 nextIndex 减去一, 重复上述的过程, 最终一定会到达跟随者包含索引为 preLogIndex 以及任期编号为 preLogTerm 的日志项的状态, 此时跟随者接受领导人发来的日志项, 然后复制从这次的 nextIndex 开始的之后所有领导人的日志项, 最终跟随者将与领导人的日志完全相同

3.5 安全性约束(Safety)

上面我们所讨论的方案并不是一个安全的方案, 在系统正常运行的时候是没有问题的, 但当领导人发生宕机, 而恰好某一个跟随者被选举为了新的领导人, 但是它并没有之前的领导人的日志, 由于领导人的权威性, 那些含有旧领导人日志的跟随者会被新领导人的日志覆盖掉, 这会导致系统错误, 因此需要对协议做更多的约束, 对于领导人选举过程, raft 限制对于那些没有包含所有已提交日志的候选人不允许成为新的领导人, 这样就可以避免新的领导人比原来的领导人包含的日志少, 具体的实现的时候是这样的, 每个候选人要想赢得选举, 它必须要经过集群中的半数以上的结点同意, 它在其向其它结点发送请求投票的请求时, 会带上自己最新的日志的索引和任期, 收到该请求的结点会检查自身和日志是不是比候选人的日志更新, 日志新旧的比较策略是这样的:

  • 如果两份日志的最新日志项的任期编号相同, 则看索引哪个更大, 索引更大则更新

  • 如果两份日志的最新日志项的任期编号不相同, 则任期编号更大的日志更新

这样以来, 候选人若想赢得选举, 它一定包含了所有已提交的日志, 从而避免那些没有含有所有已提交日志的结点成为候选人

其次, raft 约束了领导人不允许直接提交任期号为之前任期的日志, 即便它已经被复制了集群中的半数以上的结点中, 借用论文中的例子来说明如果不加这个限制会出现哪些问题, 如下图所示

在阶段 (a), S1 为集群中的领导人, 它将任期号为 2, 它将索引为 2 的日志项部分复制到了其它结点上, 但是没有完全复制完就宕机了, 进入了阶段 (b), S5 被选举为了新的集群领导人, 它的任期号为 3(即在 S1 的任期号上加一), 进入阶段 (c) 以后, S5 发生了宕机, 而 S1 重新被选举为了集群的领导人, 它的任期号为 4, 它继续复制任期号为 2 的日志, 当它将任期号为 2 的日志复制到 S3 结点以后, 此时任期号为 2 的日志已经被复制到了集群中的大多数结点了, 因此该日志可以提交了, 于是 S1 提交了日志, 将它应用到状态机中, 其它结点也都将该日志应用到了状态机中, 到了阶段 (d), S1 结点再次宕机, 此时 S5 重新被选举为领导人, 这是 S5 复制任期号为 3 的日志到集群中的所有结点中, 我们看到在阶段 (c) 中已经提交到索引为 2 的日志被覆盖掉了, 这是严重的错误, 为了避免这个问题, raft 要求领导人不允许直接提交非当前任期的日志, 即在上面这个例子中, 不允许 S1 在任期号为 4 的任期内去直接提交任期号为 3 的日志, 只能首先尝试将当期任期的日志提交, 以上面这个例子, S1 在阶段 (c) 想要提交 term=2 的日志, 由于其 term=4, 因此它必须先将 term=4 的日志提交, 为了提交 term=4 的日志, 它需要首先将 term=4 的日志复制到集群中的大多数结点中, 如 (e) 所示, 当 term=4 的日志被复制到了集群中的半数以上结点之后, term=4 的日志已经是可以提交的状态了, 因为 raft 保证所有的日志按序、无遗漏地应用到状态机, 因此当它准备提交 term=4 的日志, 将其应用到状态机时, 它会检查之前的日志是否已经提交(raft 会维护一个 commitIndex, 标志当前最新的已提交的日志项的索引), 这时会发现之前 term=2 的日志没有提交, 并且它已经被复制到集群中的大多数结点了, 所以 raft 这时会首先提交 term=2 的日志, 将其应用到状态机, 然后提交 term=4 的日志, 将其应用到状态机, 也就是说 raft 不允许领导人直接提交非当前任期的日志, 而必须是在提交当前任期的日志时, 「间接」地提交之前任期的、已经被复制到集群中大多数结点的日志, 我们将这里所说的之前任期的日志称为 preLog, 这样做的原理是, 如果领导人直接先去提交 preLog, 有可能 preLog 被复制到集群中的其他结点并应用到状态机后, 领导人发生崩溃, 新任领导人不含有 preLog, 它上任以后会强制要求跟随者覆盖掉已经提交的 preLog, 这样会发生的严重的错误, 因为对于任何结点来说, 已提交的日志是绝对不能再更改的, 而加了这条约束以后, 领导人若想要提交 preLog, 它必须先尝试提交 currentLog, 即先将 currentLog 复制到集群中大多数结点中, 这样以来, 就使得即便它崩溃了, 不含有 preLog 的候选人也不会赢得选举, 因为 currentLog 已经被复制到集群中大多数结点, 因为要想赢得选举, 候选人必须含有 currentLog, 若其含有 currentLog, 则其也一定含有 preLog, 从而避免了上述错误的发生

前面我们讨论了领导人崩溃的情形, 当领导人崩溃后, 候选人必须满足一定条件才能成为新的领导人, 如若集群中的跟随者或候选人崩溃, 则情形更为简单, raft 保证结点之间信息传递的幂等性, 若跟随者或候选人崩溃, 则领导人向它们传递信息时一定收不到回复, 因为领导人会不断地重试, 直到崩溃的跟随者或候选人重新变为正常状态, 当然或许跟随者或候选人在收到领导人的日志并应用之后崩溃了, 但这时它还没有回复领导人, 因此领导人会认为跟随者或候选人没有成功接收、应用这条日志, 它会持续给跟随者或候选人继续发送这条日志, 当候选人或跟随者重启之后, 它会收到并处理领导人发来的日志, 由于这条日志之前已经应用过了, 所以它不会重新再应用而是直接向领导人回复成功, 以便告知领导人它已成功处理了该条日志, 这样便保证了幂等性

3.6 集群成员变更(Cluster Membership Changes)

由于分布式系统是一个紧密结合的自治系统, 每个结点都会存储其它结点的地址, 毕竟每个结点都有可能成为候选人进行领导人竞选, 所以它必须知道集群中的所有结点以便请求其它结点为自己投票, 也就是说每个结点都存有一份配置文件, 该配置文件描述了集群整体的拓扑结构, 以上我们所讨论的都是在集群中的成员固定不变的情形下, 实际运行中的集群经常会进行结点的调整, 比如对结点进行扩容或缩容等, 即运行中的集群可能需要进行配置文件的变更, 这对集群的一致性造成了很大的挑战, 对于含有 的结点的集群来说, 理论上讲我们没有办法在完全不停服的状态下对所有结点进行配置文件的原子性更新, 最简单的方式是将集群中的所有结点停机, 然后更新配置文件, 并重启所有结点, 但是实际生产环境中的集群往往不允许这样操作, 因为即便短暂的停机也会造成严重的影响, 而倘若对配置文件执行热更新操作, 如不采取特别的措施, 可能会造成集群一致性的破坏, 可以用一个实际的例子来说明这个问题, 如下图所示

原先集群中只有 Server1、Server2、Server3 共三个结点, 现要对集群进行扩容操作, 将三结点扩充到五结点, 所以需要进行配置文件的更新, 由于配置文件无法做到完全同时的更新, 所以在中间的某个时刻, 即图中箭头所指向的时刻, Server1 和Server2 都仍然是旧的配置, 它们所看到的集群仍然是一个三结点集群, Server2 可能会在 Server1 和 Server2 的投票下成为领导人(因为三结点中有两票, 满足大多数原则), 而 Server3~Server5 它们使用新集群的配置, 它们所看到的集群都是五结点集群, Server3 可能在 Server3~Server5 的投票下也成为领导人, 这样以来在同一时刻, 集群中同时有两个领导人出现, 从而造成错误, 要解决这个问题, raft 采用采用两阶段(two-phase)的方案, 具体的方式如下, 首先当集群要进行扩容或缩容时, 需要向领导人发送配置变更请求, 领导人收到请求后会将旧的配置(记为 )和新的配置(记为 )取并集, 形成一个联合配置 , 然后将该配置作为一个日志项广播给集群中的所有其它结点, 其它结点自从收到该日志项开始便开始应用其中的配置(即 ), 这里无需等到日志提交, 因此在广播的过程中, 整个集群中的所有结点使用的配置有两种, 一种仍然在使用旧配置, 一种已经开始使用联合配置, 这个时候如果领导人宕机了, 则新的领导人可能使用旧配置也可能是使用联合配置, 但不会有只使用新配置的结点, 与普通日志一样, 当日志被复制到集群中的大多数结点之后, 便可以进行提交了, 这便是第一阶段提交, 第一阶段提交以后, 我们可以知道对于整个集群来说, 只有使用联合配置的结点才可能成为领导人, 也就是说无论是单纯的旧配置还是单纯的新配置, 它们都无法仅仅靠自己的配置选出领导人, 而前面所说的之所以会同时出现两个领导人, 原因就在于完全使用旧配置的结点间投票选出了旧配置下的领导人, 完全使用新配置的结点间投票选出了新配置下的领导人, raft 加入联合配置以后, 只有使用联合配置的结点才能成为领导人, 从而避免了割裂, 这时领导人会再生成一个新的日志项, 该日志项中只有新的配置 , 然后将该日志项广播给集群中的所有其它结点, 当集群中的大多数结点都接收到了该日志项后, 该日志便可以被提交了, 此时大多数结点都已完全使用新配置了, 这便是第二阶段的提交, 这时只在旧配置中的结点不在新配置中的结点就可以下线关机了, 以上就是两阶段提交的全部细节, 可以看到两阶段提交规避了在配置文件更新过程中, 集群可能出现的同一时刻有两个领导人的状态, 使得在整个更新过程中仍然能保证安全性

上面的论述仅仅解决了更新配置过程中的安全性问题, 但还有一些性能问题需要进一步分析, 首先第一个问题是当集群中有新结点加入的时候, 它的历史日志是空的, 因为可能需要耗费很久的时间来追日志, 比如说原先集群中一共有 3 个结点, 更新配置之后加入了 6 个结点, 这 6 个结点的日志都是空的, 由于 raft 协议要求日志被复制到集群中大多数结点之后才允许提交, 进而应用到状态机, 所以必须要等待新加入的结点追平原先结点的日志之后, 系统才可以提交新的日志, 这会造成可用性问题, 要解决这个问题, raft 采用的方式是对于新加入的结点, 它只接收领导人发来的日志, 不参与投票, 同时它们也不考虑算在大多数结点之内, 即尽管系统中加入了 6 个新结点, 成为了 9 个结点, 但是系统仍然在原先 3 个结点中的「大多数」结点投票以后, 即可提交日志, 直到新结点追平日志之后, 它才和正常结点一样, 这样便解决了新结点日志落后对系统性能造成的影响

其次, 领导人可能被下线, 即领导人不在新配置中, raft 协议规定倘若新配置()被提交之后, 领导人不在新配置中了, 则它自动转变为跟随者(实际上它或许是直接关机下线, 取决于实际的业务场景), 由于系统没有领导人, 所以一段时间之后会自发启动领导人选举, 进而产生新配置下的领导人

第三个可能影响性能的问题是, 在实际的应用场景中, 更新配置之后, 某个结点可能不在新配置中了, 但是它并没有被关机下线, 而仍然保持运行的状态, 由于新配置中已经没有它自身了, 所以新配置中的领导人也不会给它发送心跳包, 它超过特定间隔没有收到心跳包后便认为领导人已经宕机, 便主动发起了选举, 对集群的运行造成了干扰, raft 协议规定的方式, 如果结点仍能正常的在固定间隔收到领导人的心跳包, 则无视其它结点发来的请求投票请求, 实际上这个问题也可以更简单的方式来规避, 第一种方式对已移除的结点关机下线, 这样它也不会再发请求投票请求, 第二种方式倘若已移除的结点不关机, 由于每个服务器都有自己的地址, 于是可以在配置文件里的集群拓扑同时记录自身的地址, 请求选票时若发现服务器拓扑没有自身的地址则代表已被移除, 此时服务器停止向集群发送数据

3.7 日志压缩(Log Compaction)

对于任何一个通过日志来实现一致性的协议来说, 在实际工程化时都会面临日志不断增长的问题, 一方面大量的日志占用了太多的存储空间, 增加了存储成本; 另一方面, 当日志特别长时, 新加入集群的结点将需要非常长的时间来重放日志, 为了解决问题, raft 采用了快照的方式, 实际上我们并不需要历史的所有时序数据, 而只需要保证当前时刻的状态机的状态是一致的即可, 因此历史的指令没有必要全部存储, raft 的快照可以近似用如下图示来说明

索引为 1~5 的日志项被创建为了一个快照, 快照中保存了状态机最后的状态, 同时也保存了最后一个日志项的索引和任期号, 显然, 应用这个快照和按序重放索引为 1~5 的日志项后, 状态机的状态是完全一致的, 当日志特别长时, 快照可大大降低存储空间, raft 协议规定生成快照的日志项必须是已提交过的, 集群中的各个结点自主生成已提交的日志项的快照, 领导人每隔一段时间也会将自己的快照广播发送给集群中的所有其它结点, 其它结点收到快照后会根据快照中说明的索引检查自己是否已含有此快照中的全部信息, 如果没有, 则删除自己全部的日志项, 然后应用这个快照, 若快照的最大索引小于自身的, 则结点简单地将快照对应的索引之前的所有日志项删除, 并应用这个快照, 而自身原有的在此索引之后的日志项仍然保留, 这样以来, 即便是新加入集群的结点, 也可以使用快照快速达到与领导人的同步

3.8 拓展阅读

以上我们完整详细地讨论了 raft 协议的内容, 有兴趣的读者可以阅读一下 raft 的原论文, 并阅读一下工业界优秀的实现源码