未来两周内，我想和大家讨论的主题是分布式一致性共识算法中的 raft 算法.

  本系列会分为两篇：第一篇谈及 raft 算法的实现原理；第二篇通过工程实践案例（项目源码）对 raft 算法原理进行论证和补充.

  本文是其中的第一篇，第二篇链接见：小徐先生：raft 工程化案例之 etcd 源码实现. 下面开始.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  再举一个程序员们耳熟而详的例子，这就好比是我们在刷 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 协议所要做的正是这样一件事情.

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

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

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

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

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

  节点的三种角色之一. 集群的首脑，负责发起”提议“、”提交“被多数派认可的决断.

  节点的三种角色之一. 需要对 leader 的 ”提议“ 、”提交“和 candidate 的 ”竞选“ 进行响应.

  节点的三种角色之一. 是一种处于竞选流程中的临时状态，根据多数派投票的结果会切为 leader 或 follower 的稳定态.

  中强一致性. 对于写请求，服务端保证最终一定能提供出正确的结果，但需要同步时间. 同步期间，可能被读到不一致的老数据.

  两阶段提交的第一个阶段. 指的是 leader 向所有节点发起日志同步请求的过程.

  两阶段提交的第二个阶段. 指的是 leader 认可一笔写请求已经被系统采纳的动作.

  任期是用于标识 leader 更迭的概念. 每个任期内至多只允许有一个 leader.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  （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 小节中给出.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  ① 倘若第 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}中形成多数派认可的那一刻，就已经成功了.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  下面谈及一个极端的 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. 只要这个请求被提交了，多数派也就写入了一遍当前任期的日志，于是本小节所谈及的异常问题就不可能再发生了.

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

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

  假设节点 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 前面部分的日志也都完全一致，即各节点已提交的预写日志顺序和内容都完全一致.

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

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

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

  每个 candidate 发起真实选举之前，会有一个提前试探的过程，试探机制是向集群所有节点发送请求，只有得到多数派的响应，证明自己不存在网络环境问题时，才会将竞选任期自增，并且发起线 如果保证客户端提交写请求不丢失、不重复？

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

  本文只作了 raft 算法的原理阐述，具有一定的抽象性. 我个人比较秉持”原理需要被源码证明“的观点，因此接下来会花时间梳理基于 raft 算法进行工程落地的项目，通过手撕源码的方式来对本文所谈及的原理加以证明和补充. 后续我也会花时间手写一个 raft 开源库，尝试在实践中获取更多感性认知，力求提高自己对 raft 的认知水平.

  ）是一个基于 Golang 实现的分布式 kv 存储系统，期间对 raft 算法的实现是最贴近于论文本身的，后续就先以 etcd 为目标，开始源码攻坚战.敬请期待笔者的新作吧！

  我会不定期更新个人纯原创的编程技术博客，技术栈以 go 语言为主，让我们一起点亮更多的编程技能树吧！