1 引入分布式共识算法的背景

1.1 如何提高大规模数据的读写性能？

（1）更好的机器.

属于纵向扩展，在系统设计上没什么工作量，但压力来到了硬件设计这一侧. 机器的性能达到一定程度之后，想要更进一步的梯度会陡然提升.

这就好比一门满分 100 分的考试，从90分提升到 98分的难度可能大于从60分提升到90分的难度.

（2）更多的机器.

属于横向扩展，理论上，在网络环境绝对理想化的情况下，这种方式可以做到上不封顶（没什么是加机器解决不了的，手动狗头）.

设立更多的机器，既可以在系统安全性方面做到状态数据的容灾备份，也能够在处理请求流程中通过负载均衡的方式减轻单个节点压力，从而提高系统的整体上限.

关于第（2）点需要补充说明的点是，在现实中并没有绝对理想的网络环境，集群节点数量也有一个合适的范围，一味地增加节点不加以约束，最终只会导致集群内部的网络请求行为反过来成为系统瓶颈点.

1.2 分布式的优势和问题？

首先，理清一个概念. 本文所谈及的分布式，更多指的是在同一模块内，为提高系统的吞吐量而采用的多节点的横向分布式，而非基于职责内聚性而进行模块划分并通过 rpc 交互串联整体的纵向分布式.

那么，这种横向分布式的优势主要体现在两点：

（1）数据备份：避免单点故障导致数据丢失或服务不可用；

（2）负载均衡：多个节点共同分担总任务，那么理论上单个节点的任务强度与节点数量成反比.

随之而来的是，横向分布式所带来的问题：

（1）如何保证不同节点之间，数据的一致性？（这里又可以进一步分为最终一致性和即时一次性）

（2）如何保证分布式系统的秩序？（能正常提供服务，不出现脑裂、崩溃、耗时过长等问题）

以上问题的根本原因在于网络的不确定性.

单节点的优势在于，单机的内存和磁盘读写操作都是很稳定的，要么成功，要么失败，则耗时很短.

而分布式引入了网络交互的流程，网络请求的耗时远远慢于单机操作，且网络请求可能存在丢失、超时、乱序等异常情况，这些情形都需要被妥善处理，从而导致系统整体复杂度的上升.

1.3 CAP 理论

下面聊聊经典的分布式系统理论：CAP 理论（Consistency-Availability-Partition tolerance Theory）.

（1）C：Consitency，一致性.

该项强调数据的正确性. 具体而言，每次读操作，要么读到最新，要么读失败. 这要求整个分布式系统像是一个不可拆分的整体，写操作作用于集群像作用于单机一样，具有广义的“原子性”.

（2）A：Availability，可用性.

该项站在使用者的角度，强调使用服务的体验.客户端的请求能够得到响应，不发生错误，也不能出现过长的等待时间.

（3）P：Partition tolerance，分区容错性.

分区容错性强调的是，在网络环境不可靠的背景下，整个系统仍然是正常运作的，不至于出现系统崩溃或者秩序混乱的局面.

CAP 理论强调的是，一个系统中，C、A、P 三项性质至多只能满足其二，即每个系统依据其架构设计会具有 CP、AP 或者 CA 的倾向性.

首先，对于单机系统，其无须考虑 P，因此可以保证 CA 的满足；

其次，对于分布式系统而言, P 是必须得到保证的，否则这就违背了“分布式”的语义. 那么分布式系统会分为两种流派：

（1）CP：强调系统数据的正确性，但由于建立保证不同节点间保证数据严格一致的机制，可能会牺牲系统的可用性.

（2）AP：强调系统的可用性，那就必须在数据一致性上做出妥协退让.

分布式系统中，C 和 A 之间的矛盾正是在于网络环境的不稳定，下面对这两项所涉及的一些问题进一步展开介绍.

1.4 C 的问题

（1）即时一致性问题：

试想一个场景：

I 当前集群的服务端有 master 和 follower 两个节点.

II 客户端写请求打到了 master，写入 x = 3 这一项内容；

III 紧接着，客户端读请求打到了 follower，查询 x = 3 的值.

那么在第（3）步中所取得的 x 的值会是多少呢？答案是不确定的. 因为这取决于 master 和 follower 之间数据同步的机制.

倘若，为了满足更快响应客户端的诉求，服务端采用了异步完成数据同步任务的机制，那么客户端的读请求就可能在 follower 同步到 set x = 3 这一项任务之前就打到 follower，此时会取到 x 的老数据或者 x 不存在的响应，总之，读到的数据和客户端期待的结果产生了差距.

以上，就是分布式系统中的即时一致性问题.

（2）顺序一致性问题

现在请试想另一种场景：

I 客户端依次向 master 发送了 set x = 3、set x = 4 的两笔请求；

II master 在本机依次完成了两笔写操作，于是状态机中记录的结果为 x = 4；

III 同时，master 异步开启将请求同步到 follower 的任务，任务发出的顺序也是 ① set x = 3 ② set x = 4；

IV 由于网络问题，第 ① 笔请求出了点状况，导致第 ② 笔请求后发先至，第 ① 笔请求随后而至；

V 于是 follower 先执行 ② set x = 4，后执行 ① set x = 3，最终 follower 状态机内的结果为 x = 3.

这个问题相比场景（1）就更严重了，因为 follower 中已经记录了错误的数据，接下来不论何时面对客户端的读请求都会返回这个错误的结果. 这种情况下，我们就称分布式系统的最终一致性也遭到了破坏.

1.5 A 的问题

为避免出现 1.4 小节涉及的问题，一种简单粗暴的方式是写操作 + 数据同步串行化，大致流程拆解如下：

（1）set x = 3 的写请求到达 master；

（2）master 将 x = 3 写入本机状态机；

（3）master 将 set x = 3 同步到所有 follower；

（4）当 master 接收到所有 follower 同步成功的响应，确保数据在整个请求均同步完成后，才给客户端 ack；

（5）客户端无论向集群中哪个节点发起读请求，都保证能拿到最新的数据.

这种流程与 1.4 小节的核心区别在于，数据同步任务不再是异步执行，而是与写请求串行化执行. 这种方式保证了在数据未同步完成前，客户端会因为未拿到 ack 而陷入阻塞，不会发起读请求.

这种串行处理的方式能够保证数据的强一致性，但是会存在哪些问题呢？

（1）倘若集群中某个 follower 出现宕机, master 同步数据时会因为未集齐所有 follower 的响应, 而无法给客户端 ack，这样一个节点的问题就会被放大到导致整个系统不可用；

（2）倘若某个 follower 的网络环境或者本机环境出现问题，它给出同步数据响应的时间出乎意料的长，那么整个系统的响应效率都会被其拖垮，这就是所谓的木桶效应.

1.6 基于木桶效应面对 CAP

评价一个系统时，评价的标准不光体现在它的高光方面，更重要的是需要权衡它的下限. 这就类似于木桶效应，一个木桶能乘多少水，只取决于它最短的那块木板.

再举一个程序员们耳熟而详的例子，这就好比是我们在刷 leetcode 时需要设计一个数据结构，哪怕它有 M-1 个方法都是 O(1) 时间复杂度，只要唯独有 1 个方法是 O(N) 的时间复杂度，我们就只能说这是一个线性复杂度的数据结构.

那么此时的优化方案是什么呢？基于合理的设计思路，倘若能够将 O(N) 的这次存在性能抖动的任务进行负载均衡，通过巧妙数据结构设计，将这部分复杂度分摊到其他 M - 1 个方法中，使得

M 个方法的复杂度都变成 O(logN). 此时尽管 M-1 个方法复杂度由 O(1) 提高到了 O(logN)，但是数据结构的最低复杂度也从 O(N) 下降到了 O(logN). 这就是质变，这就能称得上是一个优越的改进.

这一思路之于 CAP 理论也同样适用. 强调 C 则舍弃了 A，突出 A 则违背了 C，这样必然导致对方成为了木桶效应中对系统最不利的那一块短板，显得无比眨扎眼.

实际上，C 和 A 并非站在绝对意义的对立面，其间还是存在可以调和取舍的空间. 这就好比是一道由黑逐渐过渡转白的连续光谱，除了黑白分明的两端之外，期间其实存在一段过渡的灰色空间，根据位置的不同，有的离黑色近些，颜色就深一些，有的离白色近些，颜色就淡些.

从这个角度出发，我们要做的是在光谱的灰色区域中找到一个合适的位置，提高系统的整体下限. 而所有分布式共识算法，以及我们今天所介绍的主题 raft 协议所要做的正是这样一件事情.

1.7 分布式一致性共识算法

分布式一致性共识算法指的是在分布式系统中，使得所有节点对同一份数据的认知能够达成共识的算法.

可以看到，不论是命名还是概述，都在突出其实现目标在于 C，即数据一致性. 然而，在 1.5 小节中我们已谈及，倘若基于写请求 + 数据同步串行化的方式进行实施，实际上是可以满足强 C 的，但是对应的 A 就会破坏得支离破碎.

因此，分布式一致性共识算法，实际上是在基于各种精妙的算法机制，能够在尽可能少地牺牲 C 的基础之上，将 A 提升到尽可能高的水平.

我们今天的主角 raft 算法扮演的正是这样一个角色.

在可用性 A 方面，raft 算法能保证当分布式系统中存在半数以上节点存活时，系统是稳定可用的，同时请求耗时取决于多数派的下限，而非所有节点的下限；

在一致性 C 方面，标准的 raft 算法能够保证数据满足最终一致性，同时在各种工程化的落地实现中，我们可以在 raft 算法的基础上稍加改进，即可保证数据的即时一致性，进一步做到强 C.

2 raft 算法核心概念

2.1 术语表

还有几个 raft 算法中的核心概念在上表尚未提及，专门留到后续几个小节作详细介绍.

2.2 多数派原则

多数派，指的是一个群体的数量达到总数的一半以上.

多数派原则指的是，系统的决断无需全员参与,多数派达成的共识即可视为整个系统的答复.

以集群存在 5 个节点为例，多数派则需要集齐 3 个及 3 个以上节点，至多可以允许 2 个节点存在开小差背离主流的情况. 同理，倘若集群 6 个节点，则多数派需要集齐 4 个及 4 个以上节点，因此同样至多允许 2 个节点开小差. 综上，这是奉行多数派原则的集群通常将节点个数设置为奇数的原因之一.

多数派原则将会贯穿 raft 算法的始终，接下来不论是数据的同步，还是领导者的选举，只需要达到多数派的认可，就可即时采纳结果，同时处于拒绝态或者未响应态的少数派在随后感知到该决断已经被集群多数派认同后，最终也会执行采纳.

多数派原则是提高分布式系统可用性 A 的关键. 对于整个系统而言，执行一项操作要求全员共同响应以实现强 C 的保证是过于苛刻的，因为我们无法保证所有节点都能健康运作，这种底线思维是研发人员所必须具备的素养. 但是倘若退而求其次，只要多数派达成共识即可正常决断和响应，这样下限就提高很多了. 由全员响应进化为多数派共识，这将把一种底线思维下的随机性问题进化为一个数学期望问题.

多数派原则大大提升了 A 的分数，那么接下来的讨论重点就在于，raft 算法如何在多数派这一框架下，达成 C 的要求.

2.3 一主多从、读写分离

接下来补充 raft 协议的第二、三个设定.

一主多从：

raft 算法下系统中的节点分为领导者 leader 和跟随者 follower 两类角色.

leader拥有更广阔的视野，需要总览全局，领导一些日常事务的推进；

follower 职责相对简单但同样重要，因为这是一个基于多数派原则运作的民众团体，所有角色只要拧成一股绳，聚成了多数派，就能代表整个系统进行决断，甚至包括推翻 leader.

读写分离：

读操作可以由集群的任意节点提供服务；

写操作统一需要由 leader 收口处理，并向 follower 同步. 倘若 follower 率先收到了来自客户端的写请求，也需要转发给 leader 进行处理.

这种读写分离的机制，通过读操作的负载均衡提高了系统整体的吞吐量，也通过写操作的统一收口降低了共识算法的复杂度，但与此同时也衍生出两个问题：

（1）读操作可由任意节点提供服务，那么倘若一个存在数据状态滞后的 follower 提供了服务，那么客户端就可能读到老数据. 因此到此为止，raft 只能保证到数据的最终一致性，而无法满足即时一致性. 在工程落地中，也针对读操作的即时一致性提出了改进方案，具体可见本文 4.2 小节；

（2）集群一主多从，纵览全局. 倘若 leader 出了问题，群龙无首，系统岂不是会分崩离析吗？针对这个问题，raft 建立了一套完善的领导者选举机制，保证在 leader 不可用时会有替补席的 follower 挺身而出，改朝换代成为新的 leader，保证系统的正常运作，具体可见本文第 5 节.

2.4 状态机与预写日志

状态机 （state machine）是节点实际存储数据的容器,写请求的最后一步是将结果写入状态机，而读请求也需要从状态机中获取数据进行响应.

预写日志（write ahead log，简称 wal）是通过日志的方式记录下每一笔写请求的明细（例如 set x = 3 这样一笔记录），使得变更历史有迹可循. 在 raft 算法中，写请求会先组织成预写日志的形式添加到日志数组中，当一个日志（写请求）达到集群多数派的认可后，才能够被提交，将变更应用到状态机当中.

下面思考一个问题，为什么需要设计预写日志这一道流程，而不是直接将写请求应用到状态机呢？这样是否徒然增加了系统的复杂度？

预写日志的设计正是共识算法的精妙之处，其目的是为了解决 1.4 小节所提及的顺序一致性的问题.

预写日志由一个数组承载，为一段时间内的多笔写请求提供了一个缓存区；同时，每笔预写日志

是一笔写请求的抽象，通过其记录的明细，使得我们可以对写请求的内容进行比较. 这样的机制之下，我们只要保证预写日志数组中，被准许应用到状态机的部分每笔预写日志的内容都完全相同，这样就能解决写请求乱序的问题，从而达成数据的最终一致性.

2.5 两阶段提交

两阶段提交可以分别从单机和系统的两个维度进行解读.

从单机层面，一笔写请求会分为添加到预写日志和应用到状态机两个步骤，这是对两阶段提交的一种体现；

在整个系统层面，两阶段提交的流程可拆解如下：

（1）leader 接收到来自客户端的一笔写请求；

（2）leader 将写请求添加到本地的预写日志中，并向集群中其他节点广播同步这笔写请求. 这个过程可以称之为“提议”（proposal）；

（3）集群中各节点接收到同步请求后，会一套检验机制判断是否能执行同步（添加到预写日志），校验机制这里不细述，留待 4.1 小节细说；

（4）倘若集群总计半数以上的节点（包括 leader 自身）都将这笔请求添加预写日志，并给予了 leader 肯定的答复（ack），那么 leader 此时会“提交”这个请求，并给予客户端写请求已成功处理的响应；

（5）其他节点在随后的时段中，会通过与 leader 的交互（心跳或其他同步数据的请求）感知到这个“提交”动作，最终也在预写日志中提交这笔请求；

（6）被提交的预写日志具备了被应用到状态机的资格. 但应用的时机取决于实现方式，倘若只追求最终一致性，可以选择异步应用；倘若追求立即一致性，则会要求 leader 先应用到状态机，才能给予客户端 ack.

上述流程中，第（2）步是提议阶段（proposal），第（4）步是提交阶段（commit），两者相加，构成了所谓的“两阶段提交”的流程.

回头思考，可以发现正是这种两阶段提交的方式，实现了与多数派原则的串联打通. 因为有第一阶段的 proposal，leader 获得了群访 follower 收集民意的机会，一旦多数派达成共识，可以立即提交请求，并响应客户端，这样请求的耗时只取决于多数派中的短板，而不取决于全员的短板，大大提高了可用性.

需要注意的是，所有被提交的请求，都视为已经被系统所采纳，需要受到“最终一致性”这个语义的保护. 那么为什么说一个请求只要被多数派认可（添加到预写日志），就能够具备最终一致性呢，这其实是需要通过领导者选举机制的保证，同时，这个问题的答案将在本文 7.6 小节中给出.

2.6 领导者选举

leader 是写请求的入口，如果出了问题，会导致整个集群不可写.

raft 中建立了一套完整的选举机制，倘若 leader 挂了，会由 follower 补位成为新的 leader.

这里讨论两个问题：

（1）follower 如何感应到 leader 挂了，从而主动进行补位？

leader 需要定期向 follower 发送心跳，证明自己仍然健在. 与之对应的，follower 会建立一个心跳检测定时器，当超过指定时长未收到 leader 的心跳，则认为 leader 已死，会切换成候选人（candidate）发起竞选，尝试补位成为新的 leader.

（2）什么样的 follower 有资格补位成为 leader？

follower 成为 candidate 后,会广播向所有节点拉票，当投赞同票的节点数（包括candidate 本身）达到多数派的时候，该 candidate 会胜任，成为新的 leader.

此处，参与投票的选民在决定结果时会有一套固定的判断机制，这将呼应了 2.5 小节最后提及的多数派准则下最终一致性的保证机制这一问题. 判断机制详细内容将在本文 5.3 小节中作展开.

2.7 任期与日志索引

任期 term，就像是朝代，集群由一个 leader 切换到另一个 leader 的过程称之为“改朝换代”，此时对应的任期数会进行累加.

每当一个 candidate 发起一轮竞选时，会将当前 term 在旧任期的基础上加1，倘若胜任成为新的 leader，这就将成为自己的“国号”.

值得一提的是，不是每个 term 都有 leader，因为可能在 candidate 未胜出的前提下，term 又进一步进行了累加，从而实现朝代的跨越.

但能够保证的是，每个 term 至多只会有一个 leader，具体的证明过程可见本文 7.1 小节.

节点中的预写日志存放在一个数组中，每则日志在数组中的位置称之为索引 index.

于是，每一则预写日志会有两个核心的标识属性：

（1）term：标志了这则日志是哪个任期的 leader 在位时同步写入的；

（2）index：标志了这则日志在预写日志数组的位置.

通过 {term , index} 二元组可以组成一个全局唯一键，定位到一则日志，并且能够保证位于不同节点中日志，只要其 term 和 index 均相同，其内容一定完全一致. 这一项证明可见本文 7.2 小节.

至此，raft 算法的核心概念初步介绍完毕，第 2 节只是做了主流程的阐述，一些细节还留待后续内容进行补充完善. 下面第 3 节将以 raft 算法下节点的三种角色以及其切换流程作为主线，进一步展开 raft 选举机制的原理介绍.

3 raft 算法下节点的角色流转

3.1 角色定义及切换

raft 算法中，集群节点的角色类型分为：领导者 leader、跟随者 follower、候选人 candidate 三种角色. 各角色的具体职责将在后续 3.2-3.4 小节中详细介绍，下面先对各角色间的切换机制进行一个总览性的描述.

（1）leader -> follower

倘若 leader 发现当前系统中出现了更大的任期，则会进行“禅让”，主动退位成 follower.

这里 leader 发现更大任期的方式包括：I 向 follower 提交日志同步请求时,从 follower 的响应参数中获得; II 收到了来自新任 leader 的心跳或者同步日志请求；III 收到了任期更大的 candidate 的拉票请求.

（2）follower -> candidate

leader 需要定期向 follower 发送心跳，告知自己仍健在的消息.

倘若 follower 超过一定时长没收到 leader 心跳时，会将状态切换为 candidate ，在当前任期的基础上加 1 作为竞选任期，发起竞选尝试补位.

（3）candidate -> follower

candidate 参与竞选过程中，出现以下两种情形时会退回 follower：

I 多数派投了反对票；

II 竞选期间，收到了任期大于等于自身竞选任期的 leader 传来的请求.

（4）candidate -> leader

candidate 竞选时，倘若多数派投了赞同票，则切换为 leader.

（5）candidate -> candidate

candidate 的竞选流程有一个时间阈值. 倘若超时仍未形成有效结论（多数派赞同或拒绝），则会维持 candidate 身份，将竞选任期加1，发起新一轮竞选.

3.2 领导者

领导者是写请求的统一入口，在接收到来自客户端的写请求时，会开启“两阶段提交”的流程：

（1）广播 proposal，向所有节点同步这一请求；

（2）当请求得到多数派的赞同后，才会提交这一请求.

leader 还需要周期性地向集群中所有节点发送自己的心跳，告知自己的健康状况，用途包括：

（1）让 follower 重置心跳检测定时器，避免其切换成 candidate 发起竞选；

（2）在心跳请求中携带上 leader 最新已提交日志的标识 id（term + index），推动 follower 更新日志提交进度.

同时需要注意，心跳请求是单向传输，而非双向通信. 因此，follower 无需对 leader 的心跳请求进行回复.

3.3 跟随者

follower 的职责包括如下几项：

（1）负责同步 leader 传来的写请求，此时也有一个参与民主反馈的过程，倘若同步成功，会给予 leader 正向反馈，当 leader 的同步请求收到半数以上的认可时，会提交日志；

（2）通过接收 leader 心跳的方式，获取到携带的 commitIndex 信息，及时完成已被多数派认可的预写日志的提交，以推进其写入状态机的进度. 这一项相当于做到了数据的备份，也被读请求最终一致性提供了保证;

（3）负责为参与竞选 candidate 的投票，决定赞同与否的判断机制见 5.3 小节；

（4）通过心跳检测定时器时时关注 leader 的健康状态，当超时未收到心跳时，会切换为 candidate 发起竞选.

3.4 候选人

candidate 是一个临时态，成为 candidate 意味着此时正处于成与败的分叉路口，candidate 有关的核心流程如下：

（1）倘若 follower 切为 candidate，会将当前任期加1，作为竞选任期；

（2）会将自身的一票投给自己；

（3）广播向所有节点拉票；

（4）倘若拉票请求超时前，得到多数派认可，则上位为 leader；

（5）倘若拉票请求超时前，遭到多数派拒绝，则老实退回 follower；

（6）倘若拉票请求超时前，收到了任期大于等于自身竞选任期的 leader 的请求，则老实退回 follower；

（7）倘若拉票请求超时，则竞选任期加 1，发起新一轮竞选拉票请求.

4 raft 算法下的外部请求链路梳理

本节会站在更宏观的视角，观察客户端与服务端（ 一 leader + 多 follower）之间的交互流程，分为写和读两个流程.

4.1 写

（1）写操作需要由 leader 统一收口. 倘若 follower 接收到了写请求，则会告知客户端 leader 的所在位置（节点 id），让客户端重新将写请求发送给 leader 处理；

（2）leader 接收到写请求后，会先将请求抽象成一笔预写日志，追加到预写日志数组的末尾；

（3）leader 会广播向集群中所有节点发送同步这笔日志的请求，称之为第一阶段的“提议”；

（4）follower 将日志同步到本机的预写日志数组后，会给 leader 回复一个“同步成功”的ack；

（5）leader 发现这笔请求对应的预写日志已经被集群中的多数派（包括自身）完成同步时，会”提交“该日志，并向客户端回复“写请求成功”的 ack.

上面描述了一个最理想化的写流程链路，其中还存在几个场景需要进行补充：

case 1：leader 任期滞后.

在第（4）步中，倘若 follower 发现当前 leader 的 term 小于自己记录的最新任期，本着”前朝的剑不斩本朝官“的原则，follower 会拒绝 leader 的这次同步请求，并在响应中告知 leader 当前最新的 term；leader 感知到新 term 的存在后，也会识相地主动完成退位.

case 2：follower 日志滞后.

同样在第（4）步中，此时虽然 leader 的 term 是最新的，但是在这笔最新同步日志之前， follower 的预写日志数据还存在缺失的数据，此时 follower 会拒绝 leader 的同步请求；leader 发现 follower 响应的任期与自身相同却又拒绝同步，会递归尝试向 follower 同步预写日志数组中的前一笔日志，直到补齐 follower 缺失的全部日志后，流程则会回归到正常的轨道.

case 3：follower 日志”超前“.

同样在第（4）步中，leader 的 term 是最新的，但是 follower 在 leader 最新同步日志的索引及其之后已存在日志，且日志内容还与当前 leader 不一致. 此时 follower 需要移除这部分”超前“的日志，然后同步 leader 传送的日志，向当前在任 leader 看齐.

小结：case 2 和 case 3 的处理方式共同保证了，在 raft 算法下，各节点间预写日志数组的已提交部分无论在内容还是顺序上都是完全一致的.

case 4：如何将最终一致性升级到即时一致性？

标准的 raft 算法模型中，在 C 方面只能做到”最终一致性“的语义. 倘若想要升级为”即时一致性“，就需要在写流程和读流程中都做些额外的处理.

在写流程第（5）步中，leader 不仅需要提交这笔写请求对应的预写日志，还需要确保将这笔日志应用到状态机中，才能给予客户端”请求成功“的 ack，以此保证读 leader 状态机时，能读取到最新的数据.

4.2 读

raft 标准模型中，客户端的读请求可以被集群中的任意节点处理，最终会取状态机中的数据进行响应. 由于预写日志 + 二阶段提交 + 多数派原则的机制保证了被提交的日志具有”最终一致性“的语义，而只有被提交的日志才有资格被应用到状态机，因此状态机的数据也必然具有最终一致性，而无法保证即时一次性（follower 和 leader 之间的数据状态）

如果要求读流程满足即时一次性的要求，则要做一些额外的处理：

（1）appliedIndex 校验：每次 leader 处理写请求后，会把最晚一笔应用到状态机的日志索引 appliedIndex 反馈给客户端. 后续客户端和 follower 交互时，会携带 appliedIndex. 倘若 follower 发现自身的 appliedIndex 落后于客户端的 appliedIndex，说明本机存在数据滞后，则拒绝这笔请求，由客户端发送到其他节点进行处理.

（2）强制读主：follower 收到读请求时，也统一转发给 leader 处理. 只要 leader 处理写请求时，保证先写状态机，后给客户端响应，那么状态机的数据可以保证即时一致性. 但是这样的弊端就是 leader 的压力过大，其他 follower 节点只沦为备份数据副本的配角.

同时，这种强制读主的方案还存在一个问题，就是领导者在处理读请求时，需要额外对自己做一次合法性身份证明. 这是因为倘若当前网络出现分区情况，外界早已更换朝代，而 leader 仍坐落于小分区中不知大清已亡，固执地认为自己是正统，那么此时提供的读服务就无法保证即时一致性，会退化为最终一致性.

解决这个问题的方案是，leader 提供读服务时，需要额外向集群所有节点发起一轮广播，当得到多数派的认可，证明自己身份仍然合法时，才会对读请求进行响应.

这个 leader 身份合法校验的问题只存在于读请求中而不影响写请求，这是因为 leader 处理写流程时，在提议阶段就必须与外界通信，获取多数派的反馈.这个反馈的过程实际上就已经完成了对 leader 身份合法性的校验.

5 raft 算法下的内部请求链路梳理

第 4 节聊完了客户端与服务端交互的过程. 本节侧重于讨论服务端内部不同角色的节点之间的交互流程，主要按照请求类型分类展开.

5.1 日志同步请求

（1）请求起点：领导者

（2）请求意图：领导者向其他节点同步预写日志(proposal).

（3）请求参数：

（4）请求终点：

终点1：leader

处理方式：

I 倘若该任期小于自身，拒绝，并回复自己的最新任期；

II 倘若该任期大于自身，退位为 follower,按照 follower 的模式处理该请求.

终点2：follower

处理方式：

I：倘若 leader 任期落后于自己，拒绝请求，并回复自己所在的任期；

II：倘若 follower 存在不一致的日志，则删除多余的日志，同步 leader 日志与之保持一致；

III：倘若 follower 存在日志滞后，则拒绝请求，让 leader 重发更早的日志，直到补齐所有缺失.

终点3：candidate

I：倘若 leader 任期大于等于自己，退回 follower，按照 follower 模式处理请求；

II：如果 leader 任期小于自己，拒绝，并回复自己的最新任期.

（5）响应参数：

（6）leader 后处理

倘若多数派都完成了日志同步，leader 会提交这笔日志；

倘若某个节点拒绝了同步请求，并回复了一个更新的任期，leader 会退位回 follower，并更新任期；

倘若某个节点拒绝了同步请求，但回复了相同的任期，leader 会递归发送前一条日志给该节点，直到其接受同步请求为止；

倘若一个节点超时未给 leader 回复，leader 会重发这笔同步日志的请求.

5.2 心跳&提交同步请求

（1）请求起点：领导者

（2）请求意图：周期性发送心跳证明自己还健在；同时日志提交的进度.

（3）请求参数：

（4）请求终点：

终点1：leader

处理方式：

I 倘若该任期小于自身，直接无视；

II 倘若该任期大于自身，退位为 follower,按照 follower 的模式处理该请求.

终点2：follower

处理方式：

I 倘若任期小于自身，直接无视

II 重置 leader 心跳检测计时器. 查看 leaderCommit, 看是否有预写日志可以被提交.

终点3：候选人

处理方式：

I 倘若任期小于自身，直接无视

II 如果任期大于等于自己，退回 follower，按照 follower 模式处理请求.

注意，心跳请求是单向非阻塞的，leader 发送心跳后无需等待其他节点的回复.

5.3 竞选拉票请求

（1）请求起点：候选人

（2）请求意图：拉票，希望得到多数派认同，上位成为 leader

（3）请求参数：

term：当前竞选领导者的任期；

candidateID：候选人的节点 ID；

lastLogIndex：候选人最后一笔预写日志的索引；

lastLogTerm：候选人最后一笔预写日志的任期.

（4）请求终点：

终点1：leader

处理方式：

I 倘若 candidate 的竞选任期小于自身，拒绝，并回复自己的最新任期；

II 倘若 candidate 的竞选任期大于自身，退位为 follower,按照 follower 的模式处理该请求.

终点2：follower

处理方式：

I：倘若 candidate 的竞选任期小于自身，拒绝，并回复自己的最新任期；

II：倘若自己已经将票投给了其他 candidate，拒绝；

III：倘若自己已经将票投给了这个 candidate，接受；（candidate 侧会幂等去重）

IV：倘若 candidate 的 lastLogTerm 大于自己最后一笔预写日志的 term，接受；

V：倘若 candidate 的 lastLogTerm 小于自己最后一笔预写日志的 term，拒绝；

VI：倘若 candidate 的 lastLogTerm 等于自己最后一笔预写日志的 term，且 candidate 的 lastLogIndex 大于等于自己最后一笔预写日志的 index，接受；

VII：倘若 candidate 的 lastLogTerm 等于自己最后一笔预写日志的 term，且 candidate 的 lastLogIndex 小于自己最后一笔预写日志的 index，拒绝.

终点3：candidate

I：倘若 candidate 的竞选任期小于等于自己的竞选任期，拒绝；

II：倘若 candidate 的竞选任期大于自己的竞选任期，退回 follower，按照 follower 的模式处理.

（5）响应参数：

（6）candidate 后处理

I 倘若多数派投了赞同票（包括自己），晋升为 leader，竞选任期则为新的国号；

II 倘若多数派投了反对票，则退回 follower；

III 倘若反对票中，出现了比自己更高的任期，退回 follower，更新任期；

IV 倘若形成多数派决议前，收到了任期大于等于自己的 leader 的请求，退回 follower，更新任期；

V 倘若拉票请求超时，则自增竞选任期，发起新一轮竞选.

（7）小结

在第（4）部分，通过 follower 决定投票的判断机制，可以看出，follower 只愿意将票投给数据状态不滞后于自己的 candidate. 又由于 candidate 要获取多数派的赞同票才能上位成为 leader，换言之，只有数据一致性状态在多数派中处于领先地位的 candidate 才有资格成为 leader. 这一项机制非常重要，正是由它保证了”两阶段提交，提交即可响应“这一流程的合理性.

更具体的问题和证明见本文 7.5 小节.

6 raft 算法下的集群变更

第 6 节实际上属于 raft 算法工程化落地的内容. 因为在 raft 算法的标准定义中，会把背景定义得更加理想化，不涉及到主动执行集群节点数量变更的情况.

但在工程实践中，我们不可避免地需要对集群进行动态调整,因此,我们需要保证,当有节点加入或者退出集群时，整个集群要保证能够正常运作，避免出现脑裂的情况.

6.1 集群变更流程

配置变更的过程和 leader 同步日志的过程是一致的. 配置变更的请求会被包装成一条写请求，走进两阶段提交的流程当中，有所区别的是，此时由于涉及集群节点数量的变更，因此配置变更期间的多数派仍以变更前的节点名单为准，即多数派要求的节点数量为变更前集群的节点数量，多数派的组成节点要求为变更前已存在于集群的老节点.

下面以集群新增节点的过程加以说明：

（1）配置变更请求需要由 leader 统一收口处理；

（2）leader 发起提议（proposal），将”配置变更“的日志广播给集群中的所有节点. 配置变更的明细参数形如 ${变更前集群的节点名单}_${新加入的集群节点名单}，需要能明确标识出哪些节点是原有的老节点，哪些节点是新加入的节点；

（3）当配置变更的提议要被老节点中的多数派认可时，leader 才会提交（commit）配置变更动作，在配置参数中将新老两部分节点的名单合并到一起；

（4）在配置变更期间，leader 选举时，需要获得老节点中多数派的赞同票，才能当选；

（5）配置变更期间，处理写请求时，需要在提议阶段获得老节点中多数派的认可，才能进行提交.

注意，在第（3）-（5）点中，无论处理配置变更提议、写请求提议还是领导选举提议，此时集群的多数派都定义为老节点范围内的多数派. 那么我们不妨利用逆向思维，思考一下，倘若不这样加以约束，而是采用变更后全节点范围的多数派来组织流程，会出现哪些问题呢？

6.2 bad case 案例梳理

背景：集群原本有 3 个节点：a、b、c，c 为 leader. 在 moment1 时刻，d、e 需要加入集群.

倘若以集群变更后的节点数量来决定多数派，那么只需要 a、b、c、d、e 中有 3 个节点达成共识，就形成了多数派. 下面我们来论证在这种模式下，会存在什么问题.

（1） 反例1：配置变更期间选举的 bad case

I moment1：客户端向 leader c 提交配置变更请求{abc-de}；

II moment2：leader c 广播发起提议{abc-de}，由于 c、d、e 3 个节点都对配置变更达成认可，形成多数派，于是 leader 提交配置变更请求；（此时 a、b 由于网络原因，还未同步配置变更，仍持有老的节点配置信息：a、b、c）

III moment3：leader c 宕机；

IV moment4：a、b 心跳检测超时，a 率先发起竞选，并且获得 a、b 两个节点的选票. 由于 a 和 b 此时持有老的节点信息，因此认为 2 个节点即为多数派，因此 a 成功上任；同时，节点 d 也发起竞选，获得了 d、e 以及刚从宕机中恢复的节点 c 的选票，获得了 5 个节点下的多数派

票数：3票，也成功当选；

V moment5：集群中出现两个 leader：a 和 d，发生脑裂.

上述问题的解法就是，在配置变更期间，需要将多数派定义为旧节点范围内的多数派. 添加这一设定之后：

① 倘若第 II 步中，leader c 仍在配置变更请求{abc-de}被同步到 c、d、e 后宕机. 那么在新一轮选举中，d、e就无法当选，因为无法获得旧节点{abc}中的多数派认可（a、b此时由于未同步配置，因此压根不认可d、e的身份），因此只有 a、b 可能当选，配置变更的请求会被作废. 但由于 leader c 同步配置变更的提议也未被{abc}中的多数派认可，因此无法提交，也不能给客户端响应. 最终形成的局面就是，本轮配置变更请求作废，客户端在超时未得到 ack 后，会重新发起一次 d、e 加入集群的配置变更请求；

② 倘若第 II 步中，leader c 的配置变更请求{abc-de}已经得到 b 的认可，那么 bc 会形成旧节点{abc}中的多数派；leader c 可以直接提交该笔请求. 接下来，即便 leader c 宕机了，在{ab}中，b 会由于预写日志数据更新而胜出成为下一任 leader，那么后续请求{abc-de}会有 b 代替完成. 因此配置变更请求{abc-de}在{abc}中形成多数派认可的那一刻，就已经成功了.

（2） 反例2：配置变更期间写的 bad case

与第（1）例类似，在配置变更期间，也需要将处理写请求时的多数派定义为旧节点中的多数派，否则会出现如下问题：

（1）配置变更期间，一笔写请求到达 c，并被 c、d、e 认可，c 认为形成多数派，即提交并响应该请求；

（2）随后 c 宕机，由于选举需要遵循旧节点多数派原则，最终 a 胜出，且 a 始终同步这笔写请求. 在下一笔请求到达后，a 的同步日志提议会将前一笔写请求覆盖，最终，一笔已经提交过的写请求被意外丢弃了.

7 Q&A

下面通过对几个经典问题的解答，实现对 raft 算法原理的补充.

7.1 为什么能保证一个任期内至多只有一个领导者？

可以，通过选举的机制可以保证.

首先，candidate 竞选前会自增 term，因此 term 在总体上为单调递增趋势；

其次，在选举机制上，一个 term 内，一个 follower 只有一票，因此只能投票给一个 candidate；

最后，基于多数派原则，一个 candidate 只有拿到半数以上的赞同票才能当选 leader.

因此，同一个 term 内，不可能出现有两个 candidate 同时获得半数以上的赞同票，因此一个 term 至多只有一个 leader.

7.2 为什么能保证通过任期和索引相同的日志内容一定相同？

首先，预写日志具有 append-only 的性质，只作追加，不存在更新和删除操作；

其次，基于 7.1 可得知，同一个 term 只有一个 leader；

因此，在 term 相同的情况下，所有节点在同一个 index 上的日志都会与 term 内 leader 对应 index 位置的日志保持一致；

综上，term 和 index 共同组成了一个全局唯一标识键. 只要term 和 index 均相同，日志内容一定相同

7.3 如果两个节点中分别存在一笔任期和索引均相同的日志，那么在这两笔日志之前的日志是否也保证在顺序和内容上都完全一致？

可以.

（1）如 4.2 小节中 case2 和 case3 所述，对于节点 a，一笔 term = x、index = y 的预写日志允许被写入的前提是，其上一笔预写日志的任期和索引一定和 term 为 x 的leader 的上一笔日志相同；

（2）又由 7.2 小节证明，只要日志的索引和任期相同，其内容一定相同；

（3）进一步采用数学归纳法，可以推导得到，节点 a 从这笔写入日志开始向前追溯的所有日志均与任期为 x 的 leader 完全一致；

（4）倘若节点 b 也存在一笔 term = x、index = y 的日志，那么这笔日志一定也是由 term 为 x 的同一 leader 同步写入；

（5）与（2）（3）同理，节点 b 自此向前的所有日志都会与 leader 完全相同；

（6）于是可得，节点 a、b 自此向前的日志都完全相同.

7.4 关于选举机制方面，如何解决选票瓜分引发的问题？

试想一个场景，集群中有 a、b、c 3 个节点，三者网络环境以及硬件配置都非常相近.

其中，c 为leader，集齐两个节点形成共识即可视为多数派，接下来发生了如下事件：

（1）leader c 某时刻宕机；

（2）节点 a、b 心跳检测计时器同时超时，因此同时发起竞选；

（3）发起竞选时，a、b 都对任期加1，并且都会先把手中的一票投给自己，然后向对方拉票；

（4）由于 a、b 手中的票都已投给自己，因此会分别拒绝对方的拉票请求；

（5）a、b 都无法获得多数派的选票，竞选在同一时刻超时，并且同时发起下一轮竞选；

（6）接下来不断重复（3）-（5）步，a、b 陷入僵持局面，始终无人胜出，导致集群不可用.

解决方案：

每个节点在心跳超时阈值和竞选超时阈值上添加一个随机扰动值，通过这一扰动，避免多个节点在进入完全相同的竞选节奏. 于是进入 candidate 状态的节点有了先后之分，胜负自然就可见分晓.

7.5 为什么新任 leader 一定拥有旧 leader 已提交的日志？

这是由两阶段提交和选举流程中的多数派原则保证的：

（1）只有被集群多数派完成同步的日志才会被 leader 提交；

（2）在选举流程中，节点只会把票投给日志进度不滞后于自身的 candidate；

（3）在竞选流程，candidate 需要获取多数派的赞同票才能胜任，成为新任 leader.

基于第（3）点可知，新任 leader 的日志进度一定能在竞选流程的多数派中出于不滞后的地位.

而在集群节点个数固定的情况下，本轮竞选流程的多数派和认可前任 leader 同步日志请求的多数派至少存在一个重复的节点，否则就违背了多数派的语义（集群半数以上），因此可以得知，新任 leader 一定拥有前任 leader 那笔被多数派认可的日志，即旧 leader 提交的日志.

7.6 是否一项提议只需要被多数派通过就可以提交？

基于 7.5 小节可知，当一笔日志被多数派完成同步后，则后续所有新任的 leader 一定会拥有这笔日志，因此这笔日志已经被集群采纳，可以保证其安全性.

上面的论述看起来天衣无缝，然而，本小节所谈及问题的答案其实是否定的.

下面谈及一个极端的 case，并通过一个机制的补充，来让本节所关心的问题被彻底解决.

【极端 case】

背景：集群中存在 s1-s5 5 个节点，只需要 3 个节点达成共识，即可形成多数派.

（1）moment1：此时 leader 为 s1，term 为 1，s1 接受了一笔写请求，刚将其同步到 s1、s2，还未形成多数派时，s1 就宕机了；

（2）moment2：s5 收获了 s3、s4、s5 的选票，当选 leader，接受了一笔写请求，只在本机完成预写日志的落盘就宕机了；

（3）moment3：s1 收获了 s1、s2、s3、s4 的选票，重新当选 leader，继续推进 term = 1 时那笔遗留写请求的提交，成功将其同步到了 s1、s2、s3，获得多数派的认同，于是提交这笔写请求. 提交之后，s1 又宕机了.

（4）moment4：s2 由于遗留了一笔 term 为 2 的日志 term，领先集群所有节点，因此可以收获集群所有节点的选票. 于是 s5 再度当选 leader，继续推进 term 为 2 时遗留的写请求，由于这笔日志的 index 与第（3）步中 s1 同步日志的 index 相同，又因为其 term 值更大，最终会覆盖 s1、s2、s3 中的老日志，这就导致一笔已经被 s1 提交的日志最终被 s5 回滚了.

注意，在 raft 算法的设定中，已提交的日志就认为是写入成功了，是绝对不允许被回滚的，这种极端 case 就会 raft 算法的公信力造成破坏.

于是为解决这一问题，raft 算法中新增了一项限制，新上任的 leader 需要至少完成一笔本任期内的写请求，才能够执行提交动作.

补充这一设定后，在上述 case 的第（3）步，leader s1 尽管完成了 term 1 遗留日志的同步，也不能执行提交动作. 直到其完成一笔 term 3 的写请求之后，才能执行老日志的提交. 这是因为此时，集群中的多数派已经被同步了 term 3 的日志，即使 s1 再发生宕机情况，s5 也不可能凭借 term2 的遗留日志而重新当选了.

事实上，在工程实践上，通常每个 leader 上任之后，都会向集群广播同步一笔内容为空的日志，称之为 no-op. 只要这个请求被提交了，多数派也就写入了一遍当前任期的日志，于是本小节所谈及的异常问题就不可能再发生了.

7.7 leader 向 follower 同步日志时，如何保证不出现乱序、丢失、重复的问题？

不乱序、不重复：follower 同步日志前，会校验上一笔日志是否和 leader 的上一笔完全一致，只有这样才会执行同步动作.

不丢失：基于 ack 机制保证. 倘若 leader 超时未收到 follower 同步日志的 ack，会重发同步日志请求.

7.8 如何保证各节点已提交的预写日志顺序和内容都完全一致？

假设节点 a 最后一笔已提交的预写日志的 term = x、index = y，这说明集群中有多数派认同了 term 为 x 的 leader 同步该笔日志的请求.

首先证明：倘若其他节点在 index = y 位置的日志已提交了，则这笔日志的 term 一定也为 x.

证明思路：倘若节点 b 在 index = y 处的日志已提交，且任期为 z，那么就说明集群中有多数派认可了任期为 z 的 leader 同步的 term = z、index = y 的日志的请求. 由于集群不可能存在两个对立的多数派，因此唯一的可能性就是 z = x，原题得证.

接下来基于 7.2 小节的证明结论，我们可以得知各节点在 term = x、index = y 前面部分的日志也都完全一致，即各节点已提交的预写日志顺序和内容都完全一致.

7.9 如何保证状态机数据的最终一致性？

基于 7.8 得知，被提交的预写日志顺序和内容都必然是完全一致的.

又由于只有被提交的预写日志才能被应用到状态机，因此状态机的数据必然会按照正确的顺序和请求内容被依次更新，最终一致性得以保证.

7.10 如何解决网络分区引发的无意义选举问题？

倘若集群产生网络分区，部分处于小分区的节点由于无法接收到 leader 的心跳，导致进入选举流程. 又因为网络分区问题，导致选举始终无法获得多数派的响应，最终 candidate 会无限自增 term. 直到网络恢复的那一刻，由于 candidate 异常的高 term，导致 leader 退位，集群进入新一轮的选举流程.

尽管小分区中的节点由于数据的滞后不可能在选举中胜出，最后必然是大分区中的节点胜任，节点数据的一致性依然可以得到保证. 但是这个无意义的选举过程同样会导致集群陷入暂不可用的阶段. 因此，我们可以通过这样的措施来避免这类无意义的选举：

每个 candidate 发起真实选举之前，会有一个提前试探的过程，试探机制是向集群所有节点发送请求，只有得到多数派的响应，证明自己不存在网络环境问题时，才会将竞选任期自增，并且发起真实的选举流程.

7.11 如果保证客户端提交写请求不丢失、不重复？

不丢失：通过 ack 机制保证. 客户端超时未收到服务端的 ack，则会重发请求.

不重复：客户端记录写请求的序列号，与服务端交互时透传这个序列号. 最终由服务端的 leader 实现对相同序列号写请求的幂等去重.