第5章 分布式共识算法 #

在前面的章节中，我们讨论了如何通过复制来防止单点故障导致的某些数据丢失，如何通过分区来承载海量数据，如何通过分布式事务来确保跨节点操作的原子性。

然而，当我们试图将这些机制组合成一个真正能够全天候运行、自动容错的生产级系统时，会发现一个明显的缺口：如何在部分节点故障的情况下，依然让存活的节点对系统的状态达成一致？

传统的两阶段提交协议（2PC）虽然解决了"所有节点要么全部提交，要么全部回滚"的一致性问题，但它是阻塞式的——一旦协调者发生故障，整个集群可能陷入无限等待。这揭示了分布式系统中一个更深层次的挑战：我们需要一种机制，它不仅能达成一致，还必须具备容错性。换言之，即使集群中的少数节点（如半数以下）发生了崩溃或网络隔离，系统依然能够继续推进，对外提供服务。

这便是**共识算法（Consensus Algorithms）**的舞台。

从本质上讲，共识算法解决的是分布式计算中著名的"协商"问题：在一个不可靠的网络环境中，由一组并发的进程提议某个值，并最终就该值达成唯一的、不可逆的协定。

这一看似简单的目标，实则是分布式系统中最坚硬的内核。共识算法不仅是实现状态机复制（State Machine Replication）的理论基础，更是现代分布式数据库实现自动 Leader 选举（Leader Election）、原子广播（Atomic Broadcast）以及配置变更的核心动力。无论是 Paxos 的精妙理论，还是 Raft 的工程实践，它们都旨在将不确定的物理世界（丢包、延迟、宕机）抽象为一个逻辑上严格有序的整体。

在本章中，我们将深入探讨共识算法的原理与演进，理解它们是如何在"一致性"与"可用性"之间找到那条完美的平衡线。

5.1 共识算法简介 #

5.1.1 概述 #

在分布式系统中，**共识（Consensus）**问题占据着核心地位。在此之前，我们讨论了通过复制来保证数据的持久性，通过分区来扩展系统的容量。然而，当这些机制在面临部分节点故障或网络分区时，如何让整个系统依然能够像一个单一的、连贯的整体一样行动，便是共识算法所要解决的根本问题。

直观地说，共识就是指多个参与者（进程或节点）对某个特定的值（Value）达成一致看法的过程。这个"值"在不同的场景下可以代表不同的含义：它可能是一个布尔值（决定事务提交还是回滚），选出的主节点 ID（Leader Election），或者是一条具体的日志条目（Log Entry）。这个定义看似抽象，但其实涵盖了大量实际应用场景：

• 在主从复制中，客户端需要通过主节点才能写入数据，因此节点之间需要选举出一个领导者来协调任务分发、日志复制等工作。如果没有一个可靠的共识机制，可能会出现多个节点同时认为自己是领导者，导致**脑裂（split-brain）**现象，导致数据冲突。
• 在分布式数据库、分布式存储等系统中，数据通常会被复制到多个节点上以提高可用性和容错能力。然而，如何保证所有副本在写入时保持一致？这就需要共识算法来协调写入顺序和结果。
• 考虑银行转账问题。用户A要转账给用户B，这里涉及到两个操作：从用户A的账号上扣除款项，向用户B的账号增加款项。这两个操作必须合在一起成为一个"原子操作"：要么都成功，要么都失败。表现在具体的操作上，系统的所有节点需要对这个原子操作形成一致：所有的节点都提交成功，或者都终止操作回滚数据，不能出现在某些节点上提交成功，而在另外的节点上中断的情况。
• 集群的配置发生变更，例如集群增加或者删除了节点时，这些配置信息同样需要在集群的节点中达成共识。
• 在 2.5 节中我们提到，系统的状态由事件按照顺序组成，所以如果一组事件如果能对一个分布式系统中的所有节点保持一样的顺序，那么这些事件在所有节点中就会得到同样的状态，而这里的"事件顺序"也是一种共识。
• 系统中的多个节点需要访问临界区资源时，需要决定访问的顺序。

以上的问题虽然各不相同，在不同的问题场景中需要达成的一致内容各不相同：可能是消息传递的顺序、一组进程是存活还是宕机、哪个节点是主节点、谁能访问共享资源、事务应该终止还是结束等等，不管这些细节如何。但是它们都有一个共同的特性：系统中的节点，需要就某些共享信息达成一致。

5.1.2 共识算法的难点 #

如果网络是完美可靠的，或者节点之间不存在延迟，达成共识将变得轻而易举。共识算法之所以复杂且困难，根源在于我们所处的分布式环境通常是异步（Asynchronous）且不可靠的。

在此环境下，共识算法面临以下核心挑战：

• 节点故障：节点可能因为硬件故障、软件错误或断电而停止工作。例如，一个数据库节点宕机，可能导致数据写入失败或不一致。共识算法需要确保即使部分节点宕机，系统仍能达成一致。
• 网络问题：分布式系统中的节点通过网络通信，可能面临延迟、分区（网络断开）或消息丢失。例如，两个数据中心之间的网络中断可能导致节点无法同步状态。共识算法需要通过超时、重试或投票机制来处理这些问题。
• 拜占庭故障：某些节点可能表现出恶意行为，比如发送错误的消息、伪造数据或故意不响应，这种情况在区块链等开放系统中尤其常见。共识算法需要设计机制来识别和隔离恶意节点。
• 数据一致性：在分布式数据库或文件系统中，多个副本需要保持一致。例如，用户在不同节点上更新数据时，系统必须确保所有副本最终反映相同的状态。共识算法通过定义如何选择"正确"的值来解决这一问题。

想象一群探险者在迷雾森林中寻找宝藏，每个人都有一份不完整的地图（分布式系统中的节点状态）。他们需要通过喊话（网络通信）来决定集合地点，但有人可能迷路（节点故障），有人可能故意指错方向（拜占庭故障），还有人可能听不清喊话（网络延迟）。共识算法就像一个魔法协议，确保所有诚实的探险者最终聚集在同一个地点，即使面对这些挑战。

5.1.3 共识和一致性 #

受翻译的影响，很多讨论共识算法的中文资料都称它们是"分布式一致性算法"，虽然"一致性"（Consistency）和"共识"（Consensus）这两个词非常相似，但它们在分布式系统中有着明确的区别和紧密的联系。在本节介绍两者的区别和联系，为了规范和严谨，本书中严格区分使用"共识"和"一致性"。

一致性

一致性是指多个副本之间的数据是否一致，或者客户端访问系统时是否能看到一致的数据视图。一致性更多是从外部视角来看待系统的状态，强调的是读写操作的结果是否符合预期的行为模型。在 3.2 节中详细讨论了常见的一致性模型。

共识

共识则是一种协议或算法机制，用于在多个节点之间就某个值达成一致。它是实现一致性的一种手段，尤其是在多副本系统中，共识是实现强一致性的重要工具。

共识协议通常满足以下几个性质：

• 终止性（Termination）：所有非故障的节点最终都会做出决定。
• 一致性（Agreement）：所有非故障的节点对同一个值达成一致。
• 有效性（Validity）：共识值必须是某个节点提出的合法值。

共识更偏重于内部逻辑的协调机制，是系统为了达到某种一致状态而采取的具体技术路径。

按照 2.2 节中提到的系统要满足的安全性和活性目标，一个分布式共识算法必须满足：

• 安全性：系统中的不同节点，不能确定有冲突的值。例如，系统中不能同时存在一个以上的主节点，不能出现某些节点提交一个值，另外的节点提交另外的值的情况。
• 活性：确保系统即使在出现某些节点失效或者网络问题的情况下，最终仍然能确定一个值。

尽管两者有区别，但在很多场景下它们是密不可分的：

• 共识是实现一致性的一种方式。例如，通过 Paxos、Raft 等共识算法，可以确保多个副本的日志顺序一致，从而实现线性一致性。
• 一致性是对系统行为的描述，共识是对系统机制的实现。你可以把一致性看作目标，共识则是实现该目标的工具之一。

例如，在一个分布式数据库中，客户端希望看到最新的写入结果（强一致性需求），那么系统内部可能使用Raft协议来同步各个副本的日志（共识机制），从而确保读取时返回的数据是最新的。

5.2 FLP不可能定理 #

上一节对共识算法做了简单的介绍，一个自然而然的疑问随之产生：是否存在一个通用的、完美的共识算法，可以在任何网络环境下都可靠工作？

1985 年，Fischer、Lynch 和 Paterson 三位科学家发表了著名论文《Impossibility of Distributed Consensus with One Faulty Process》[1]，给出了一个令人沮丧但至关重要的答案。这一结论后来被称为 FLP不可能定理（FLP Impossibility Theorem）。它为分布式系统的共识问题划定了一道不可逾越的理论边界，深刻影响了随后四十年的分布式系统设计哲学。

FLP 定理的核心结论可以表述为：在一个完全异步（Asynchronous）的分布式系统中，即使只有一个进程可能发生崩溃故障（Crash Fault），也不存在一个确定性（Deterministic）的共识算法，能够保证在有限时间内达成共识。

简而言之，在异步系统中，共识算法无法同时满足安全性（Safety，即一致性）、活性（Liveness，即终止性）和容错性。这被称为分布式共识的"不可能三角"。

要真正理解 FLP 定理的深意，必须首先理解它所描述的"系统模型"及其关键假设：

• 进程故障模型采用崩溃模型（2.3.1 节）： 这是一个非常温和的故障模型。节点只会因为崩溃而停止运行，不会像拜占庭故障（2.3.2 节）那样产生恶意欺骗或篡改数据。定理指出，哪怕是最简单的停机，也能破坏共识。
• 通信可靠： 消息虽然可能乱序，但最终会被送达，不会丢失，也不会被篡改。
• 完全异步环境： 这是问题的根源所在。在异步系统中，系统中不存在全局时钟，且进程处理消息的时间、消息在网络中传递的时间、不同进程之间的时钟漂移等都没有时间上限。

在这样的异步环境中，一个致命的模糊性出现了：当一个进程 A 向进程 B 发送消息却迟迟未收到回复时，进程 A 根本无法判断进程 B 是已经"崩溃"了，还是仅仅"非常慢"（或者是网络传输非常慢）。

FLP 定理的本质，揭示了"不确定性"对算法决策的破坏力。

想象一群探险者（分布式节点）试图在迷雾森林中通过传递纸条（消息）来决定集合地点。

• 为了保证一致性（Safety）：探险者们约定，必须收到所有关键队友的确认才能行动，以免大家走到不同的地方。
• 为了保证活性（Liveness）：探险者们希望能尽快做出决定，不能永远等下去。

假如探险者 A 发出提议后，探险者 B 一直没有回复，此时系统面对两种选择：

• 如果 B 真的晕倒了（崩溃），A 应该忽略 B，与其他队友达成共识，以保证活性。
• 如果 B 只是走得很慢（异步延迟），A 若贸然决定忽略 B，等 B 终于赶到时，可能会提出一个不同的提议，从而破坏一致性。

在完全异步的系统中，没有任何"超时机制"是绝对可靠的。任何时候，算法都可能处于一种临界状态：再等下去可能陷入无限等待（牺牲活性），不等下去可能导致由于信息不全而做出错误决策（牺牲一致性）。FLP 证明了，聪明的对手总能通过控制消息的延迟和调度，让算法永远在"达成共识"的边缘徘徊，却永远无法跨过那条线。

FLP不可能定理的证明超出本书的范畴，可以参考原论文或[2]，以下对定理做一个直观的解释。由于系统是异步的，一个算法无法区分一个进程是"崩溃了"还是"只是非常慢"。任何一个追求"一致性"的确定性算法，为了确保安全（不出现意见分歧），在遇到可疑情况时（比如等待某个进程的响应），它必须无限期地等下去，因为如果它不等而贸然做决定，那个"慢"的进程可能之后会发出不同的值，从而破坏一致性。这就导致了算法可能永远无法满足"终止性"，即陷入无限等待。

反之，如果算法为了追求"终止性"（尽快做出决定），它可能在某些极端时序下，导致不同的进程基于不完整的信息做出了不同的决定，从而破坏了"一致性"。

FLP 定理乍看之下似乎宣判了分布式共识的死刑，既然理论上"不可能"，我们为什么还要研究 Paxos、Raft 这些算法，且它们在工程中运行良好呢？

事实上，FLP 定理并非为了阻碍发展，而是指明了方向。它告诉我们，不要试图在纯粹的异步模型下寻找完美的解，而必须在模型上做出妥协或放宽假设。工程实践中，主流的共识算法通常采取以下策略来"绕过"FLP 的限制：

• 放宽对"异步"的假设（引入故障检测）：现实网络虽然不可靠，但通常不是完全异步的。我们引入"故障检测器（Failure Detector）"（如心跳机制和超时判定）。虽然超时判断并不总是准确的（例如可能误判一个慢节点为死节点），但这将"异步模型"转化为"部分同步模型（Partially Synchronous Model）"。Raft 和 Paxos 实际上都依赖于这种假设：在系统趋于稳定的时期，消息延迟是有界的，从而能够达成共识。
• 牺牲确定性（引入随机性）：某些算法引入随机数。当节点无法决定时，随机选择一个值或随机等待一段时间。这种随机性打破了导致无限循环的对称性。虽然理论上仍有概率永远无法终止，但在概率上，随着时间推移，达成共识的概率迅速趋近于 1。
• 牺牲活性换取安全性：这是最常见的权衡。以 Paxos 和 Raft 为例，它们在设计上坚守"一致性（Safety）“底线。当网络极度不稳定或发生脑裂时，算法可能会暂时停止服务（无法选出 Leader，失去活性），直到网络恢复稳定。也就是说，它们保证永远不出错，但不保证在任何时刻都能立刻给出结果。

综上所述，FLP 不可能定理是分布式领域的"不确定性原理”。它提醒架构师和开发者：在设计分布式系统时，必须在一致性、可用性和网络延迟之间进行权衡（Trade-off），完美的共识在理论的彼岸，而我们要做的，是在现实的约束下通过合理的假设构建足够可靠的系统。

5.3 Paxos算法 #

Paxos算法[3][4]是由Leslie Lamport[5]提出的一种分布式共识算法，在分布式共识领域，它几乎就是"共识"本身的同义词，它为如何在不可靠的分布式网络中达成一致性提供了最严谨的数学证明。用Chubby作者Mike Burrows[6]的话说：

“世界上只有一种共识协议，就是 Paxos，其他所有共识算法都是 Paxos 的退化版本。（There is only one consensus protocol, and that’s “Paxos” — all other approaches are just broken versions of Paxos）"。

尽管这一说法略显夸张，但不可否认的是，包括 Raft、ZAB（ZooKeeper Atomic Broadcast）在内的现代共识算法，其核心思想与 Paxos 在本质上是一脉相承的。

然而，Paxos 以"晦涩难懂"而著称，其极高的抽象程度使得工程实现变得异常困难。在接下来的小节中，我们将避开复杂的数学证明，直接深入 Paxos 的原理，去探究它是如何通过两阶段的交互，在混乱的分布式环境中建立秩序的。

5.3.1 Paxos算法的诞生 #

Leslie Lamport在1988年首次提出了Paxos算法，最初的论文《The Part-Time Parliament》[3]于1990年提交，但直到1998年才正式发表在ACM Transactions on Computer Systems上。论文之所以难产，有以下几个原因：

• Lamport在论文中用了一个非常奇特的叙述方式：他把分布式一致性问题包装成了一个虚构的古希腊岛屿"Paxos"上的议会故事，议员们通过送信的方式投票决定法律。这个比喻虽然生动，但让当时的审稿人一脸懵逼，觉得这论文"太不严肃"或者"看不懂”。结果，论文被拒了好几次，Lamport后来回忆说，审稿人觉得他的写作风格像是在"开玩笑"。这篇论文直到1998年才被接受，而那时候分布式系统的研究已经开始火热，Paxos的重要性才逐渐被认可。
• Lamport对学术界的审稿过程颇为不满，他后来在博客和访谈中提到，Paxos论文的发表过程让他觉得"学术界有时候太保守"。为了让大家更容易理解，他在2001年又写了一篇更直白的论文《Paxos Made Simple》[4]，直接把"Paxos岛"的故事扔掉，用更清晰的术语解释算法。这篇论文成了Paxos的"入门圣经"，至今被广泛引用。不过，Lamport在文中开玩笑说：“Paxos算法的简单性只有在你已经理解它之后才显得简单。“这句自嘲成了分布式系统圈的经典梗。

可以看到，在Paxos论文发布的最初几年，并没有引起行业太多的重视。一直到了2006年，Google的Chubby[7]服务使用Paxos算法解决分布式共识问题，这才让人们开始研究起Paxos算法，后续的ZAB、Raft等共识算法也都受到了Paxos算法的启发。2013年，Lamport因为对分布式系统的杰出理论贡献获得了当年的图灵奖。

5.3.2 Paxos的直观解释 #

与其它解释Paxos算法原理的资料不同，本书并不打算一上来就照搬论文中的描述来讲解Paxos算法原理，这样子只能让读者了解"How”，为了让读者能更好理解Paxos算法的"Why”，这里从共识算法所要解决的问题出发，考虑各种不同的策略，一路推导出Paxos算法的核心思想[8]。

在一个分布式系统中，为了系统的高可用性，必须提供一定的冗余度。例如，数据不能只存储在一个节点上，这样如果节点宕机将丢失数据。为了解决这个问题，引入了复制技术：同一份数据，需要保存在多个节点上。这样由多个节点组成的系统，需要看起来像一个整体：无论访问系统中的哪一个节点，都能得到同样的值，这就是所谓的"强一致性"。共识算法，正是为了解决复制数据时的强一致性问题而提出的。

回到问题的本源，共识算法要解决的问题是"复制数据时的强一致性问题"，因此共识算法可以看做是一种在节点间复制数据的"复制策略"，我们下面逐个尝试不同的复制策略，看看其中都遇到了哪些问题。

不完美的复制策略 #

尽管在前面已经讨论过不同的复制模式，但是为了讲解的方便，仍然在这里从不同的复制策略出发，讨论每个策略的优缺点，从这些策略中逐步进化为Paxos使用的复制策略。

主从异步复制

在主从异步复制的流程如下：

• 客户端的写请求发送到主节点；
• 主节点持久化写请求数据；
• 主节点应答客户端，写入数据成功；
• 主节点复制数据到从节点。

主从异步复制的优点是应答速度快，只要主节点持久化数据之后就认为写入成功应答客户端，但是如果在主节点复制数据到从节点的过程中出错，导致复制数据失败，那么这份数据只有主节点上的备份。

因此，主从异步复制不是一个可靠的复制策略。

主从同步复制

在主从异步复制中，系统会由于没有将数据复制到从节点导致可靠性不够，那么我们将策略改为同步复制，要求主节点将数据复制到所有节点才能应答客户端，因此主从异步复制的流程如下：

• 客户端的写请求发送到主节点；
• 主节点持久化写请求数据；
• 主节点复制数据到从节点；
• 在收到所有从节点的复制成功应答之后，主节点应答客户端，写入数据成功；

由于数据需要复制到所有从节点之后才能应答客户端，主从同步复制的可靠性比异步复制更高，但是也面临另外的问题：系统中一个节点如果一直没有应答，将导致这个写请求无法完成，系统的可用性降低。

主从半同步复制

看起来同步和异步复制都各有优缺点，主从半同步复制就在两个方案之间做一个折中：主节点在应答客户端写入成功之前，要求复制数据到足够多（不需要是全部）的从节点。这样数据不止保存在一个副本上，提供了较高的可用性，同时系统也不会因为单一节点的不可用导致整个系统的不可用。

如图 5.4 所示，系统要求主节点只需要复制数据到一个从节点成功，就能应答客户端，读者可以与图 5.3 进行对比两种方案的异同。

但是半同步复制也有缺陷：可能在任何一个从节点上，数据都不完整。考虑这样一个场景：

• 客户端向主节点写入数据a，主节点只复制到从节点1就应答客户端；
• 同一个时间，客户端向主节点写入数据b，主节点只复制到从节点2就应答客户端；
• 如果此时主节点宕机，那么无论是从节点1还是从节点2，都没有一份系统完整的数据。

多数派读写

为了解决半同步复制中数据不一致的问题，将半同步复制策略改为多数派读写策略（4.2.2 节）：

• 多数派写：每次写入都要求写入到半数以上的节点才能返回；
• 多数派读：每次读取都必须从半数以上的节点读取该数据。

假设多数派写入的节点数量为W，多数派读时的节点的数量为R，系统中总的节点数量为N，上面的策略表示为：

$$ \begin{aligned} &\text{多数派写：} W > N/2 + 1，\\ &\text{多数派读：} R > N/2 + 1 \end{aligned} $$

由于 $W + R > N$，所以多数派读和写操作的节点集合一定有重合。因此在进行多数派读操作时，一定能读到前面多数派写入的结果。在多数派读写策略下，数据的可靠性得到了保证，可用性也得到了保证，系统能够最多容忍$(N -1) / 2$个节点的不可用。

带时间戳的多数派读写

然而多数派读写策略也有其它的问题。考虑以下三节点组成的系统写入数据的场景：

• 节点1、节点2都写入的x=a的数据。
• 下一次对这个数据更新时，向节点2、节点3写入了x=b的数据。
• 也就是说，在这两次数据写入之后，节点1的数据为x=a，而节点2和节点3的数据为x=b。

如果一个客户端要读取数据，按照多数派读的策略，读到了节点1和节点3的数据，根据上面的分析，将有两条不同的数据。那么，客户端应该以那条数据为准呢？

为了解决多数派读时在不同节点读到不同数据的冲突问题，在写入时给数据加上一个单调递增的时间戳，这样在多数派读时选择时间戳更大的数据，忽略时间戳小的数据。在前面的例子中，节点3上x=b的数据时间戳比节点1上x=a的数据时间戳更大，因此应该选择这个数据。

然而给数据加上了时间戳的多数派读写，依然还有问题。为了表述方便，在写入的值中加入下标表示时间戳，例如$a_1$表示时间戳1的时候写入的值为a。继续以上面三节点组成的系统写入数据的场景为例：

• 在时间戳1，节点1、节点2都写入的x=$a_1$的数据。
• 下一次对这个数据更新时，时间戳为2，客户端向节点2、节点3写入x=$b_2$的数据，但是由于客户端在写入节点2的时候出错，只有节点3写入成功。
• 也就是说，在这两次数据写入之后，节点1和节点2的数据为x=$a_1$，而节点3的数据为x=$b_2$。最新的数据x=$b_2$，只在一个节点写入成功了。

当客户端读取数据时，它的结果依赖于它的结果来自哪些节点组成的多数派读：

• 如果联系到节点1和节点2，读到的数据是x=$a_1$；
• 如果联系到节点1（或者节点2）和节点3，根据时间戳选择最新的数据，读到的数据是x=$b_2$；

可见，在这样的场景下，带时间戳的多数派读写系统对外的数据也可能出现数据不一致的情况。

从多数派读写到Paxos #

我们在上面依次了解了几种不同的复制策略以及它们的缺陷，现在来到了本节要介绍的Paxos算法，它可以认为是在带时间戳的多数派读写基础上的升级：通过两次并不严谨的带时间戳的多数派读写，实现了严谨的强一致共识算法。

为了描述Paxos算法的思想，我们实现一个强一致的存储服务，这个服务有以下的特点：

• 这是一个由三个节点组成的分布式系统。
• 采用带时间戳的多数派读写策略。
• 为了简化问题，假设该系统只存储一个变量x。
• 该存储服务对外提供三个接口：
  • get()：读变量x的最新的数据。
  • set(n)：写变量x下个版本的值为n。
  • incr(n)：对变量x加n，也生成一个新版本的数据。

在服务提供的三个接口中，get和set接口使用多数派读写就可以实现。而incr(n)操作需要分解为两步的多数派读写来实现，如图 5.6 所示：

• 通过多数派读，得到变量x的最新值i。
• 通过多数派写，写入变量x的最新值i + n。

然而由于incr命令需要分解为两步来实现，所以在同时存在多个客户端并发进行incr操作时，可能出现一个客户端覆盖另外一个客户端写入结果的情况，如图 5.7 所示：

• 两个客户端同时进行incr(1)和incr(2)操作；
• 客户端1的incr(1)操作，读和写之间是客户端2完整的incr(2)操作，这样当客户端1的写入数据时，就会覆盖客户端2写入的值，出现两个相同时间戳的不同值。
• 当这两个客户端都完成各自的incr操作时，读请求将读到相同版本的两个不同的值：$3_2$和$4_2$。

从上面的例子可以看出，有多个客户端并发进行incr操作时，出现冲突的原因是：系统中存在同一个版本的不同值。为了解决这个问题，我们约定：一个版本只能有一个确定的值，即每个版本写入之后将不允许进行修改，新写入的值只能写入到下一个版本中。

于是问题转换为另一个更简单的问题：如何确定一个值已经被写入了。最直观的做法是：每次在客户端要写入数据之前，先做一次多数派读，以确定是否已经有其它客户端在写入了这个版本的数据。

但是这个方案依然存在并发问题：如图 5.8 所示，两个客户端同时进行写入前的读操作，都得到了当前没有其它进程在写入的反馈，于是进一步写入自己的数据，造成了数据的冲突。

为了解决上面的问题，存储节点还需要加一个记忆功能，它是如下来工作的：

• 每个存储节点必须记住最后一个进行写前读取操作的客户端。
• 只允许最后一个完成写前读取操作的客户端后续写入数据。

在存储节点加上了记忆最后一个进行写前读取操作的功能之后，系统就可以阻止过期的客户端进行写入操作。这个方法能够工作，是因为在多数派读写中，一个系统最多只允许一个多数派写成功，Paxos算法就是利用两次多数派读写来实现强一致。

如图 5.9 所示：

• 客户端1首先进行写前读取操作，这个多数派请求被节点2和节点3接收，因此这两个节点记下来最后一次来进行写前读取操作的客户端是客户端1。
• 同样的，客户端2也进行写前读取操作，它的多数派请求被节点1和节点2接收，因此这两个节点记下来最后一次来进行写前读取操作的客户端是客户端2。这里需要提示的是，节点2之前保存的最后一次写前读取操作来自客户端1，在收到客户端2的写前读取操作之后，修改成了客户端2。保存节点的最后一个写前读取操作客户端，在写入完成之前是允许被修改的。
• 这样到目前为止，节点1和节点2只能接受客户端2的写入操作，而只有节点3能够接受客户端1的写入操作。基于这个原因，当客户端1要求写入数据时，不能完成多数派写操作，而客户端2由于有两个节点，最终可以完成多数派写操作。

以上就是Paxos算法最核心的思想，我们做一个简单的回顾，来看看是如何从多数派读写，通过不断增强条件来定义要解决的问题，演化为Paxos算法的，如图 5.10 所示：

• 最开始，基于带时间戳的多数派读写来实现我们的系统。
• 但是这个系统会出现并发写冲突问题。为了解决这个问题，我们约定：一个版本只能写入一个确定的值，每个版本写入之后不允许进行修改。
• 于是问题转换为如何确定一个值已经被写入了。为了解决这个问题，每次在客户端要写入数据之前，先做一次多数派读来确定是否有其它客户端在写入数据。
• 但是这样的做法仍然存在并发问题，于是要求节点增加记忆功能：记住最后一个在节点上进行写前读取操作的客户端，只允许这个客户端进行写入操作。

至此，可以给Paxos算法的核心思想做一个简单的概括：

• Paxos是一个基于多数派读写来实现的强一致存储系统。
• 它使用两轮多数派读写（RPC）来确定一个值：第一轮多数派读写用于确认当前有没有其它客户端也在并发写入数据，第二轮多数派读写用于写入数据。
• Paxos解决冲突的办法，是要求一个值在"确定"以后就不能被修改，这里说的"确定"指的是在第二轮多数派写中写入的数据。

5.3.3 Paxos算法描述 #

有了以上对Paxos核心思想的直观解释，开始正式讲解Paxos算法的完整流程。本节首先讲解Paxos的经典算法，下一节再展开其它优化的讨论。在展开描述之前，需要首先明确Paxos算法的故障模式和常用术语。

• 系统中的节点可能以任意的速度来处理消息，也可能由于各种故障会停机、重启。
• 消息可能会延迟很长时间，也可能出现乱序、重复的情况，但是不能出现被破坏的情况，即Paxos算法并不处理拜占庭环境的故障。

在Paxos算法中，有以下角色和术语：

• Proposer（提交者）：可以理解为进行数据读写的客户端。
• Acceptor（接收者）：可以理解为存储数据的节点，即服务端。
• Round（轮次）：用来标识一次Paxos算法流程，即每次Proposer提交数据写入时，都有一个对应的轮次与这次提交对应。根据前面的描述，每次完整的Paxos算法流程将有两阶段：一次多数派读，一次多数派写。轮次使用单调递增的数字表示。

备注：本质上来说，任何满足全序关系的集合都可以用来表示轮次，我们在后面讲解Raft算法时还会讨论这个问题。轮次必须满足单调递增的全序特性，是为了能够区分提交的先后顺序，因为提交者在提交之前会申请到自己所在的轮次，所以轮次也可以用来区分不同的提交者。在这里不讨论如何生成一个满足单调递增的服务。

根据前面的描述，为了解决冲突问题，存储节点必须记录下来最后进行写前读取的客户端操作，具体到Paxos算法中，存储节点需要记录以下的数据：

• last_round：Acceptor记录下来的最后一次进行写前读取的Proposer，以此来决定谁可以写入数据。
• value：最后被写入的值。
• value_round：与value是一对的，记录下来value在哪个轮次被写入。

备注：为了简单起见，以下的图例中，使用二元组(last_round,(value,value_round))来表示，例如(1,(1,1))表示该节点的last_round = 1、value = 1和value_round = 1，而使用(0,(Nil,Nil))表示该节点此前没有接收过阶段1请求以及写入过数据。

有了以上的准备，我们来看看每一轮提交的两阶段流程。

准备阶段 #

根据前面的描述，第一阶段的任务是：确定当前是否有别的客户端也同时在写入数据。在这一阶段，Proposer和Acceptor的流程是：

• Proposer：请求时带上自己的轮次，如果Acceptor当前没有比这一轮次更大的客户端请求，将保存这个轮次。
• Acceptor：在收到Proposer的第一阶段请求时，将该请求中的轮次与本地的last_round进行对比：
  • 如果last_round大于请求轮次，将拒绝该请求。
  • 否则，将以该请求的轮次来更新last_round。
  • Acceptor将返回本地保存的last_round、value和value_round。

可以看到，Acceptor的处理逻辑，能够保证只有更大的轮次能够继续处理请求，如果同时有多个客户端并发写入数据，只有后来的客户端才会在第一阶段请求成功。

以下给出阶段1请求处理的三个例子：

• 如图 5.11 中，3个节点此前都没有接收过阶段1请求以及写入过数据，因此在收到客户端round=1的阶段1请求后，将二元组从(0,(Nil,Nil))修改为(1,(Nil,Nil))并且返回给Proposer，表示当前接收的最大的阶段1请求轮次为1，同时没有写入过任何数据。
• 如图 5.12 中，3个节点当前的二元组为(1,(1,1))，其中接收的最大阶段1请求轮次为1，比Proposer提交的轮次更小，因此数据会从(1,(1,1))修改为(2,(1,1))。
• 如图 5.13 中，3个节点当前的二元组为(3,(1,1))，其中接收的最大阶段1请求轮次为3，比Proposer提交的轮次更大，因此Acceptor节点会拒绝Proposer的阶段1请求。

接受阶段 #

Proposer在收到Acceptor的应答之后，可能出现以下的情况：

• 如果有半数以上的Acceptor应答中返回的last_round不等于Proposer第一阶段请求时的轮次，那么认为集群拒绝了该Proposer的第一阶段请求。
• 否则，Proposer可以提交第二阶段的数据，该数据通过以下规则来进行选择：
  • 如果Acceptor的应答中，没有任何非空的value，说明此前没有任何值被其它Proposer完成了写入（因为一个第一阶段的多数派读一定可以读到一个第二阶段的多数派写写入的数据），这种情况下Proposer可以继续写入它要写入的值。
  • 但是，如果某个应答中包含有非空的value，此时Proposer必须假设当前有其它客户端正在写入数据，虽然并不知道对方是否已经结束，但是任何写入的值都不能被修改，所以此时Proposer应该保持原有的值，于是Proposer应该以所有应答中最大的value_round所对应的value做为阶段二的写入值。
    • 这时，可以认为Proposer执行了一次（不知道是否已经中断的）其它Proposer的修复。

简而言之，第二阶段Proposer的逻辑是：

• 首先判断集群是否允许Proposer写入数据，依据是有半数以上的Acceptor应答了和Proposer第一阶段相同的轮次。
• 在允许Proposer写入数据的情况下，根据以下规则来选择写入的值：
  • 如果所有应答都是空值，那么Proposer可以选择写入自己要提交的数据；
  • 否则，选择所有应答中value_round最大的值进行写入。

Acceptor收到Proposer的第二阶段请求时，将如下处理：

• 首先判断请求的轮次和本地保存的last_round是否一致，不一致则拒绝请求。
• 将请求中的值和轮次保存到本地的value和value_round中。

以上就是Paxos算法两阶段提交的完整全流程，我们来看具体的示例以加深理解。

无冲突Paxos算法示例

如图 5.14 所示，Proposer阶段1请求的应答中，两个节点的last_round都与自己的轮次相同，并且之前没有写入值，因此Proposer可以选择在第二阶段提交自己的写入值x。

解决并发冲突的Paxos算法示例

如图 5.15 所示，两个Proposer同时写入数据：

• 阶段一：
  • 左边的Proposer以轮次1进行阶段一请求，由于此时节点上的数据为(0,(Nil,Nil))，所以阶段一请求通过，节点1和节点2把自己的last_round修改为1。
  • 此后，右边的Proposer以轮次2进行阶段一请求，由于此时节点3上的数据为(0,(Nil,Nil))，而节点2的last_round为1，比轮次2更小，所以该Proposer的阶段一请求通过，节点2和节点3把自己的last_round修改为2。
• 阶段二： 由于两个Proposer都通过了阶段一的请求，同时节点中的value为Nil，所以两个Proposer可以选择提交自己的值，左边的Proposer提交值x，右边的Proposer提交值y。
  • 左边的Proposer以轮次1进行阶段二请求，此时节点1上的last_round为1，因此节点1允许修改数据，修改为(1,(x,1))；而节点2的last_round为2，所以节点2拒绝了轮次1的阶段二请求。由于没有半数以上节点通过阶段二请求，所以左边Proposer的阶段二请求失败。
  • 此后，右边的Proposer以轮次2进行阶段二请求，由于此时节点2和节点3上last_round为2，因此这两个节点都同意了轮次2的阶段二请求，这两个节点将数据修改为(2.(y,2))。

修复数据的Paxos算法示例

如图 5.16 所示：

• 阶段一：Proposer以轮次2提交阶段1的请求，节点1上当前的数据是(1,(y,1))，因此节点1将节点上的last_round修改为2，以(2,(y,2))的数据返回；而节点2当前的数据是(0,(Nil,Nil))，因此节点2以(2,(Nil,Nil))的数据返回。
• 阶段二：Proposer通过了阶段一的请求，因为有两个节点返回的last_round为2，但是由于节点1返回的数据是(y,1)，所以Proposer需要以这个值执行数据修复。最后在阶段二之后，节点1和节点2的数据被修改为(2,(y,1))。

5.4 Multi Paxos算法 #

在上一节中，我们完整推导了 Paxos 算法（通常称为 Basic Paxos）。Basic Paxos 虽然从理论上完美解决了在不可靠网络中对单个值达成共识的问题，但在实际的工程应用中，它面临着严重的性能瓶颈。

我们知道，一个典型的分布式存储系统（如 KV 存储、数据库）需要对一系列连续的操作（日志流）达成共识，而不仅仅是一个值。如果简单地对每一条日志都运行一次完整的 Basic Paxos 实例，将会带来以下问题：

• 性能低下：达成一个共识需要两轮 RPC（Prepare 和 Accept）。在高并发场景下，消息量会成倍增加，导致网络拥塞和高延迟。
• 活锁风险：如果有多个 Proposer 同时频繁提交请求，容易陷入互相争抢轮次（Round）的死循环，导致谁都无法成功提交，形成活锁（Livelock）。

为了解决上述问题，Lamport 提出了 Multi Paxos。Multi Paxos 并非一个全新定义的算法，而是在 Basic Paxos 基础上的一系列优化策略的统称。其核心思想是：将 Leadership（领导权）的竞争与日志的提交解耦，只要Leader没有发生变更，就可以让唯一的 Leader 负责所有日志的提交。它的核心优化是：一次 Prepare，多次 Accept。

在 Basic Paxos 中，Prepare 阶段主要有两个作用：一是争取提案权（通过轮次号），二是学习旧值（通过 Promise）。

Multi Paxos 观察到，如果一个 Proposer 刚刚通过了 Prepare 阶段并成功提交了一个值，这意味着它已经获得了当前最高的轮次号，并且大多数 Acceptor 已经承诺不再接受更低轮次的请求。那么，该 Proposer 在后续的提交中，完全可以复用这个已经获得的"特权"，而无需每次都重新经过 Prepare 阶段。

优化后的流程如下：

1. 阶段一（Prepare）： Proposer 选举。
   • 节点 A 向集群广播 Prepare 请求。
   • 一旦获得多数派 Acceptor 的承诺，节点 A 不仅通过了当前日志索引的提案权，实际上也锁定了后续所有日志索引的提案权。此时，节点 A 成为事实上的 Leader。
2. 阶段二（Accept）： 连续提交。
   • 当 Leader（节点 A）接收到客户端的新写请求时，它直接跳过 Prepare 阶段，使用当前持有的轮次号，直接发起 Accept 请求。
   • Acceptor 只要发现该请求的轮次号不低于自身记录的最高轮次，就予以接受。
   • 这样，正常的日志复制路径就从两轮 RPC 缩减为一轮 RPC，极大地提升了吞吐量并降低了延迟。

只有当 Leader 节点发生故障，或者网络分区导致出现新的 Proposer 竞争时，才会再次触发 Prepare 阶段，进行新一轮的 Leader 选举。

以上就是Multi Paxos算法的核心思想，图 5.17 对比了同样连续写入两个值，Basic Paxos和Multi Paxos的算法流程，Multi Paxos算法在确定了Leader之后，可以跳过第一阶段，持续提交写入数据。

遗憾的是，在最初Lamport对Multi Paxos的描述中，缺失了很多细节，以至于并没有哪一篇论文能够算作提出Multi Paxos的初始论文，对Multi Paxos算法感兴趣的读者可以参考论文[7]和[9]。Leslie Lamport 在描述 Multi-Paxos 时，依然保持了他一贯的数学抽象风格，他在论文中并没有规定具体的 Leader 选举细节、日志恢复流程以及成员变更机制。这导致了即使是 Google 这样顶尖的技术公司，在实现 Chubby 的 Multi-Paxos 时也付出了巨大的工程代价。

我们可以这样总结：Multi-Paxos 提供了一种通过"强 Leader"优化性能的思路，但留下了一个充满细节陷阱的填空题。

正是为了填补这些空白，Raft 算法应运而生。Raft 可以被看作是 Multi-Paxos 的一个强限制版本或特定实现。Raft 通过强制规定"Leader 必须拥有最新日志"、“日志必须连续提交”、“任期（Term）代替轮次"等约束，将 Multi-Paxos 中许多模糊的自由度（Degrees of Freedom）消除，从而构建了一个更易理解、更易于工程实现的共识框架。

在接下来的小节中，我们将正式进入 Raft 算法的世界，你会发现，Raft 的许多核心机制，正是对本节所述 Multi-Paxos 思想的具体化和规范化。

5.5 Raft算法 #

Paxos算法的提出，为分布式系统的共识算法提供了理论基础。但是Paxos论文中的算法解释，仅仅回答了如何实现分布式系统共识的"Why"问题，即如何通过两阶段多数派读写来达成共识，更多是算法原理的证明和解释。但是一个生产系统，要在算法之上考虑更多的问题才能落地，例如：

• 如何选出Leader节点，如何避免系统中同时存在一个以上的Leader节点。
• 如何处理集群成员的变更（添加或者删除节点）。
• 如何与客户端交互，实现线性一致性。
• 如何复制日志，新增节点时如何快速同步当前的集群数据。

这些在工程实践上的"How"问题，在Paxos算法提出之后，一直没有得到很好的解决。例如Google工程师在[10]中抱怨道：

尽管用一页伪代码就能描述 Paxos 算法，但我们的完整实现包含了数千行 C++ 代码。代码量的激增并不仅仅是因为我们使用了 C++ 而非伪代码表示法，也不完全是代码风格的冗余所致。将这个算法转化为一个实用的、生产级可用的系统，需要实现诸多特性和优化——其中有些曾在文献中发表过，有些则没有。

除此以外，在论文[10]中也提出：

Paxos 算法的描述与实际系统的需求之间存在巨大差距 $\cdots$ 最终系统将基于未经证实的协议。（There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system $\cdots$ the final system will be based on an unproven protocol）

这些都说明Paxos算法的论文和生产实现之间存在着巨大的鸿沟。这种情况直到2014年Diego Ongaro和John Ousterhout发表了论文《In Search of an Understandable Consensus Algorithm》[11]才发生改变，该论文的目标是提供一个比Paxos算法更易懂、易于实现、易于工程实现的共识算法。

备注：在最初的18页论文中，对部分细节展开得不多，在作者的另一篇长达258页的论文《Consensus: Bridging Theory and Practice》[12]中有更详细的实现细节描述。

在Raft论文发布以后，出现了很多基于Raft算法实现的强一致数据服务，如etcd、TIKV、Consul等，读者可以在Raft的官网看到各种语言实现的Raft算法，其中也包括笔者参与的OpenRaft项目。

备注：Diego Ongaro在Raft社区的Google Groups中详细说明了"Raft"这个算法名字的由来。最开始，他们考虑一个名字和可靠性（Reliable）、复制（Replicated）、冗余（Redundant）和容错（Fault Tolerant）相关的词汇，于是和很多其它计算机领域的缩写一样，造出了R{eliable|eplicated|edundant} And Fault Tolerant这样的词，Raft这个单词在英文中的意思是"木筏”。其次，英文单词log在计算机领域是日志的意思，在英文中也有原木的意思。Raft是木筏，Log（原木）则是组成木筏的组件，这暗合了Raft算法使用日志复制来实现共识算法的思想。最后，Lamport最开始提出Paxos算法的论文[3]中，虚拟出一个叫Paxos的岛屿，而Raft算法正是为了解决Paxos算法的难以理解和工程落地问题，采用Raft（木筏）逃离Paxos岛，可谓是一语双关。

Raft最初的目的是为了实现一个更容易理解的共识算法，它选择了和Multi Paxos同样基于领导者的实现。Raft通过将共识问题分解为几个易于理解的子问题来实现这些目标：

• 领导者选举（Leader Election）：当集群启动或领导者故障时，需要选举出一个新的领导者，只有在集群存在领导者的情况下，才能处理客户端的读写请求。
• 日志复制（Log Replication）：领导者接收客户端请求，并将其以日志的形式复制到集群中的其它节点。
• 安全性（Safety）：除了上面的流程以外，Raft算法还要满足一些安全性要求，才能正确工作。例如，集群中不能同时存在多个Leader节点；确保所有状态机以相同的顺序执行相同的命令，这是最关键的约束条件。

在本书中我们按照以下顺序讲解Raft算法的原理：

• 基本概念：首先将会讲解Raft算法中的一些基本概念，如Raft节点的几种状态及其转换的机制、任期做为逻辑时钟的重要性。
• 领导者选举：负责在分布式系统中选出一个领导者节点，处理客户端请求并协调其他节点。采用包括随机超时、投票机制和任期管理，确保系统在领导者故障时快速选出新领导者。
• 日志复制：领导者将客户端操作以日志条目形式复制到所有跟随者节点，确保所有节点日志一致。包括日志追加、提交和应用到状态机的过程，以及处理日志不一致的回溯机制。
• 安全性保证：通过投票规则和日志匹配属性等机制，确保新领导者包含所有已提交日志，系统状态机在所有节点上一致执行，防止数据不一致或丢失。
• 成员变更：成员变更指的是在分布式系统中动态添加或移除节点的能力，例如扩展集群规模或替换故障节点，这是在各种Paxos论文中都没有提及，但是却非常重要的共识算法工程难题之一。
• 日志压缩：日志压缩是Raft用来解决日志无限增长问题的机制。随着系统运行时间增加，日志条目会不断累积，占用大量存储空间并增加状态机回放时间。日志压缩通过保存状态机的快照（Snapshot）并清除旧日志来优化存储和性能。

5.5.1 基本概念 #

三种状态

在Raft算法中，节点在任意时间内只能处于以下三种状态之一：

• 领导者（Leader）：负责接收客户端请求，管理日志复制，并与所有其他节点通信，一个任期内只有一个领导者。
• 跟随者（Follower）：被动地响应领导者的请求（如日志复制或心跳消息），并在领导者不可用时切换到候选者状态参与选举。
• 候选者（Candidate）：在发起领导者选举时，节点会暂时成为候选者，尝试争取其他节点的选票以成为新的领导者。

这几个状态之间的转换机制如图 5.18 所示：

1. 节点启动后，首先进入Follower状态。
2. 如果Follower节点在选举超时到来之前没有收到来自Leader节点的任何消息，认为当前不存在Leader，将切换到Candidate状态，递增任期号发起一轮选举。
3. Candidate发起一轮新的选举之后，如果在选举超时之前没有选出新的Leader，例如部分节点宕机无法响应、例如同时间有另外的节点也在发起选举，导致无法有半数以上的节点选出Leader，这些情况下，Candidate都将再次发起下一轮的选举。
4. 如果Candidate获得超过半数以上节点的同意，就成为了这一轮的Leader。
5. 在Candidate状态下，除了再次发起一轮选举、或者赢得选举成为新的Leader这两种情况，还有一种情况就是其它节点赢得了选择成为Leader，或者发现其它有更大任期号的节点，这两种情况下Candidate将切换到Follower状态。
6. Leader节点如果发现有更大任期的其它节点，将切换到Follower状态。这种情况通常发生在网络分区的情况下。

这里需要注意几个事项：

• 系统只有在当前存在Leader节点的情况下才能处理客户端的读写请求，因此如果系统频繁处于无Leader节点的选举状态，将影响系统的可用性，我们将在 5.5.7 节中继续深入探讨可用性问题。
• Raft算法的安全性要求系统同一时间只能存在一个Leader节点，如果系统存在多个Leader节点，就是所谓的脑裂现象，我们将在 5.5.5 节中继续探讨Leader节点的安全性问题。
• 如果在选举超时前，Follower节点都没有收到来自Leader节点的消息，就切换到Candidate状态发起一轮选举，从理论上说，存在两个不同的Follower节点同时发起选举，且最后都没有得到多数派投票的情况，这种情况也被称为活锁（livelock），虽然不影响系统的安全性但是会影响活性。Raft算法的做法是不同的节点随机选择一个时间做为自己的选举超时时间，以避免活锁问题。

任期

在Raft算法中，**任期（Term）**是一个核心概念，扮演着逻辑时钟（2.6.3 节）的角色，用于协调分布式系统中节点的行为，确保一致性和正确性。任期号有以下的实现规则：

• 任期使用单调递增的自然数来实现，每一次选举对应一个任期。
• 初始化：系统启动时，所有节点的任期号为0。
• 递增规则：Follower选举超时转换为Candidate时，需要将本节点的任期号递增再发起一轮新的选举。
• 持久化：**当前任期号（Current Term）**必须持久化保存，以确保节点重启后不会回退到较低的任期号，导致系统混乱。
• 收到更高任期的消息时，将把Current Term修改为对方的任期号，同时如果是Leader状态，将切换到Follower状态。
• 心跳传播：领导者通过心跳消息定期广播当前任期号，保持节点间的任期一致性。

每一轮选举有对应的任期号，任期号通常分为选举阶段和正常运行阶段。但是也会出现某些任期只有选举阶段的情况，如图 5.19 中的任期2所示，这是因为没有在选举超时之前选出这一任期的Leader，这种情况下只能递增任期号进行下一轮选举。

任期在Raft的领导者选举、日志复制和安全保证等关键机制中起着至关重要的作用：

• 作为逻辑时钟协调系统状态：任期是一个单调递增的整数，代表系统中一个逻辑时间段，用于区分不同的领导者选举和日志复制周期。每个节点维护自己的当前任期号（Current Term），并在以下场景中使用：
  • 区分新旧状态：任期号帮助节点识别过时的消息或领导者。例如，如果一个节点收到一个任期号低于自己当前任期号的消息，它会拒绝该消息，因为它可能来自过时的领导者或候选者。
  • 同步节点行为：当节点收到更高任期号的消息时，它会更新自己的任期号并转换为Follower，确保系统在更高任期下协调一致。
• 驱动领导者选举：任期在领导者选举中起着关键作用，用于组织选举过程和防止冲突：
  • 触发选举：当一个跟随者在其选举超时（Election Timeout）内未收到领导者的心跳消息时，它会增加自己的任期号，转换为候选者（Candidate），并发起新一轮选举。
  • 投票限制：每个节点在一个任期内只能投一票，且只投给任期号不低于自己当前任期号的候选者。这避免了重复投票或支持过时候选者。
  • 领导者确立：当候选者获得多数节点的选票后，它成为该任期的领导者，并通过心跳消息将自己的任期号传播给其他节点，抑制其他节点发起新选举。
  • 解决分裂投票：如果选举失败（例如多个候选者导致票数分散），节点会等待随机超时后进入新的任期并重新选举，任期号的递增确保选举最终收敛。
• 确保日志复制的一致性：任期在日志复制过程中用于保证日志的正确性和一致性：
  • 日志条目的任期标记：每个日志条目都包含创建它的领导者的任期号。这使得节点能够区分不同任期生成的日志条目，防止过时或冲突的日志被错误应用。
  • 日志匹配检查：在日志复制时，领导者通过追加条目（AppendEntries）消息发送日志条目，跟随者会检查前一个日志条目的索引和任期号是否匹配。如果不匹配（例如由于网络分区导致日志冲突），领导者会回溯并覆盖跟随者的日志，确保一致性。
  • 提交规则：只有在当前任期内，领导者才能提交日志条目（即确认日志被复制到多数节点）。这确保了即使领导者切换，之前的已提交日志不会被覆盖。
• 防止过时领导者的干扰：任期号的高低为节点提供了一种判断领导者合法性的机制：
  • 拒绝过时领导者：如果一个过时的领导者（例如因网络分区而未察觉自己已失去权威）尝试发送心跳或日志复制请求，接收到的节点会因其任期号较低而拒绝这些请求。
  • 强制更新：当节点收到更高任期号的消息（如来自新领导者的心跳或候选者的投票请求），它会立即更新自己的任期号并转换为跟随者，从而避免与新领导者冲突。
• 提供安全保证：任期是Raft算法安全属性的重要组成部分，特别是在确保**领导者完整性（Leader Completeness）**方面：
  • 日志完整性：Raft算法通过任期号确保新当选的领导者包含所有已提交的日志条目。投票规则要求候选者的日志至少与大多数节点的日志一样"新"（基于任期号和日志索引），从而防止丢失已提交的数据。
  • 状态机一致性：任期号确保日志按顺序提交和应用到状态机，避免因领导者切换或网络分区导致状态不一致。
• 支持成员变更和故障恢复：在成员变更和故障恢复场景中，任期号帮助系统保持一致性：
  • 成员变更：在联合共识过程中，任期号用于标识配置变更日志条目，确保新旧配置的节点在同一任期下协调一致。
  • 故障恢复：当故障节点重新加入集群时，它会通过接收更高任期号的消息更新自己的状态，快速与当前领导者同步。

5.5.2 领导者选举 #

Raft算法中，使用心跳机制来触发选举流程。每个节点内都有一个称为**“选举超时（election timeout）”**的定时器，当节点在选举超时到来之前没有收到来自Leader节点的消息，就会触发选举流程。

在图 5.18 中，一个节点在启动后将首先进入Follower状态，如果在选举超时到来之前，Follower节点都没有收到来自Leader的消息，此时Follower将认为当前系统中不存在Leader节点，将切换到Candidate状态发起选举。本小节将详细讲解这部分的选举流程。

图 5.20 是选举Leader的详细流程：

1. 如果Follower节点在选举超时之前，没有收到来自Leader的消息，将切换到Candidate状态。
2. Candidate节点将递增本节点当前任期号，以该任期号发起一轮新的选举。
3. Candidate节点通过向系统中所有节点广播RequestVote消息来选举本节点为新的Leader。
4. 假如在选举超时之前，节点收到了来自集群多数派节点的投票，将认为选举成功，切换到Leader状态，成为该任期的Leader。
5. 假如在选举超时之前，节点收到了来自其它节点的Leader消息，将认为当前任期集群中已经存在Leader，此时会切换到Follower状态。
6. 假如在选举超时之前，以上两种情况都不满足，那么节点将认为在这一轮任期没有选出Leader节点，此时会跳转回第2步，递增任期号发起下一轮选举。这也是图 5.19 中任期2中没有选出Leader节点的原因。

我们来看Raft算法中Leader选举流程中，需要满足怎样的安全性和活性，以及算法是如何保证这两方面的属性。

在Leader选举流程中，安全性需要保证：任意一个任期内，只能选举出一个Leader。为了满足这一要求，需要以下的保证：

• 任何节点在一轮任期中，只能给一个节点投票，并且遵循"先到先得"的原则：即如果已经在一轮投票中给一个节点投票，后续再收到同一轮其它节点的请求将拒绝投票。为了做到这一点，需要每个节点保存下来给哪个节点投了票，这一数据需要持久化保存，因为需要在节点重启的时候从持久化存储中恢复这一数据，以避免出现问题。
• 选举流程要求得到多数派的同意才能当选。由于系统中的任意两个多数派集合肯定有交集，因此肯定只能选出一个节点做为Leader。

接下来是活性问题，即要求系统最终能够选举出Leader节点。在上面的选举流程中，第6步表示在一个新任期的选举流程中没有选出一个Leader，这种情况通常发生在同一时间有一个以上的节点在进行选举，而最终没有一个选举节点得到多数派的投票。理论上来说，这一问题可能会一直延续下去，即：一轮选举不成功，继续递增任期号同时开始下一轮选举，如此循环往复。这就导致了所谓的**活锁（livelock）**问题。

为了解决这一问题，Raft算法将选举超时随机化，每个节点不是使用一个固定的超时时间，而是节点启动时随机在[T,2T]区间中选择一个值（T为系统配置的选举超时）做为本节点的选举超时，通过这一手段让系统中的各节点选举超时时间分散。

5.5.3 日志复制 #

日志复制流程如图 5.21 所示，每个节点服务器分为三个模块：共识算法模块、日志模块和状态机。图中的集群由三个节点组成，客户端写入数据的流程如下：

1. 客户端向Leader节点发起写入数据请求，该请求由共识算法模块进行处理。
2. 共识算法模块将把客户端提交的数据，和当前任期号、递增之后的索引一起组成变更日志保存在本地，同时也会向系统中的其它节点同步这一日志，其它节点收到该同步日志消息时，在将日志保存到本地日志模块之后，将向Leader节点应答日志同步成功。
3. 当Leader节点收到系统中的多数派节点应答，将认为日志可以提交（commit），此时会将日志输入到状态机模块。
4. 状态机模块将日志**应用（apply）**之后，将应答客户端写入数据成功。

请注意以上几个操作的时机：

• 提交（commit）：日志只有在多数派节点上同步成功后，才能被认为是已提交成功的日志。
• 应用（apply）：只有提交成功的日志，才能被应用到状态机中，进而应答客户端写入成功。
• 基于以上两个原因，可以知道在任意时刻，已经被应用的日志索引（AppliedIndex）都不会大于提交成功的日志索引（CommittedIndex），因为日志首先要提交成功才能被应用。

以上是日志复制的基本流程。在一个线上的系统中，在某些时刻，不同节点上的日志进度是不同的。我们提到，一个分布式系统能够保持一致的原因是：所有节点上日志的顺序都是一致的，接下来来看看Raft算法是如何保证在所有节点上一致的日志顺序。

Raft中的一条日志，包含以下三部分数据：

• 日志所在的任期。
• 日志的索引。
• 日志所对应的应用层数据。例如，如果某次操作中是设置变量x等于3，那么对应的应用层数据就是保存这一操作对应的参数：操作的类型、变量、数值等，如图 5.21 中日志模块的"x=1"、“y=2”。

这三部分数据中，任期号和索引组成了一个满足全序顺序的二元组。能够满足"全序"对于日志尤为重要，在Raft算法中，根据以下算法来对比日志的顺序：

1. 首先对比日志的任期号，任期号更大的顺序更大。如图 5.22 中，“z=3"对应的日志任期号为2，它比前两条日志的任期号更大，所以这条日志的顺序更大。
2. 如果任期号相同，则索引更大的日志顺序更大。如图 5.22 中，“y=2"对应的日志和"x=1"对应的日志任期号都是1，在任期号相同的情况下，索引更大的日志顺序更大，因为索引为2的"y=2"日志顺序更大。

日志满足全序性，这意味着：任意两个日志都能对比顺序，这给日志按顺序排列提供了依据。

备注：以上已经介绍了Raft算法中任期的概念以及日志的格式需要满足全序性，我们不妨思考一个问题：在Raft算法中，任意一条日志都采用*(任期号,满足单调递增的日志索引)*的二元组来表示，可不可以去掉任期号，只使用满足单调递增的日志索引来表示一条日志？

这个问题的答案是：仅使用日志索引，无法保证日志的"全序性”。也就是说，可能出现相同日志索引但是不同内容的冲突情况。这是因为，Raft算法必须在存在Leader节点的情况下，才能接收客户端的读写请求，因此需要任期这个维度来标识不同的Leader节点。

假设现在只采用日志索引来标示日志，考虑以下的场景，有一个由5个节点组成的Raft集群。在初始状态下，节点1为Leader节点，此时集群中已经存在两条日志：{索引1：x=1，索引2：y=2}。

此时出现网络分区问题，将集群分为两个分区（也就是出现了脑裂问题）：Leader节点1和节点2在一个分区，形成了一个五节点集群的少数派分区，剩余三个节点在另一个分区，形成了一个五节点集群的多数派分区。此时可能出现以下的情况：

• 节点1不知道此时分成了两个分区，仍然认为自己还是Leader节点，继续接收客户端请求。它添加了新的日志，但由于无法联系到多数派节点，这些日志无法提交。此时在节点1上的日志为{索引1：x=1，索引2：y=2, 索引3：z=3（未提交）}。
• 剩余三个多数派节点所在的分区中，选出了新的Leader节点，假设为节点3，它接收客户端请求，成功复制到该分区的多数派节点中，因此日志被提交。此时在节点3上的日志为{索引1：x=1，索引2：y=2, 索引3：k=8（已提交）}。

可以看到在这个场景中，两个分区的Leader节点写入了相同日志索引但是不同内容的数据。当网络分区问题恢复以后，仅凭相同的日志索引，无法知道应该采用谁的数据。

究其原因，就是因为日志索引不能表达不同轮次选出Leader这一维度的信息。尽管日志索引本身是单调递增的，但是当由于网络分区等原因，导致两个Leader都使用相同的日志索引时，此时这些日志索引只满足"偏序性”，但不满足"全序性"，如果不能保证全序，势必无法解决数据的冲突。

在Paxos算法中，由于没有Leader的概念，一个Paxos集群不需要选举出一个Leader才能工作，所以只使用日志索引即可。

日志复制的安全性

在Raft算法中，日志复制需要满足以下两条安全性规则（在Raft论文中，被称为**“日志匹配属性（Log Matching Property）”**）：

• 如果两个日志的**（任期号，索引）**二元组一致，说明日志中存储的数据也是一样的。
• 如果两条日志有相同的**（任期号，索引）**，那么在这两条日志之前的日志都是一样的。

上面的两个属性可以和数学归纳法进行类比：第一条是基础情况，说明两条日志只要满足（任期号，索引）二元组一致，那么数据也是一致的；而第二条是递归情况，只要两条日志的（任期号，索引）二元组一致，那么往前"递归"时的每条日志也都保持一致。

我们来看Raft算法在日志复制流程是中如何保证这两个属性得到满足的。

首先，回顾上面的日志复制流程，每次Leader节点收到客户端提交的数据时，共识算法模块将客户端提交的数据，以及当前索引号、递增后的索引一起组成变更日志，这个流程保证了每一条日志的**（任期号，索引）**二元组都不相同，这样保证了日志匹配属性的第一条规则。

日志匹配属性的第二条规则，通过Leader节点复制日志流程时的一致性检查来保证，Leader节点需要找到和Follower节点之间最后一次相同的日志位置，从这个位置开始向Follower节点复制日志。Leader向Follower节点复制日志时，Follower节点如果发现该日志的（任期号，索引）二元组和自身的最后一条日志之间有空隙，将拒绝该复制日志请求，同时在拒绝请求的消息中，带上本节点最后一条日志的（任期号，索引）二元组，以便Leader节点从这个位置开始向Follower复制日志。也正是由于这个原因，Raft不能像Paxos算法那样，允许相邻的日志之间出现空隙。Leader节点上需要为每一个Follower节点维护一个名为nextIndex的索引信息，保存Follower节点当前的日志复制进度。在Leader刚刚当选时，将默认从最新的日志开始复制，如果复制收到了Follower节点的拒绝，再相应进行调整。

如图 5.23 所示是一次Leader向Follower节点同步日志时的调整流程：

• Leader节点当前的最大日志索引为3，初始时nextIndex=3，以这个日志向Follower节点复制日志。
• Follower节点上当前的最大日志索引为1，与Leader节点同步的日志数组的起始索引3之间存在空隙，因此Follower拒绝了这个请求，并且在拒绝应答中回复当前节点的日志索引为2。
• Leader收到Follower的拒绝应答之后，将nextIndex修改为2，即拒绝请求中Follower回复的本地最大日志索引，从日志2开始向Follower同步日志。
• Follower收到了起始索引为2的日志数组，与本节点最后一条日志索引1是相邻的，因此Follower接受这个日志数组，同步成功。Leader收到Follower的复制成功应答之后，将nextIndex修改为4，即上一轮复制的日志数组中最大的日志索引的下一个位置，这样下一次Leader就从日志索引4向这个Follower节点复制日志。

Follower节点与Leader节点上日志数据不一致的情况，有以下几种可能：

• 缺失日志：此时Follower节点需要追上Leader节点的日志进度。
• 有未提交的日志：回忆图 5.21 的复制日志流程，第2步中Follower收到了Leader节点同步的日志之后就写入本节点的日志模块，但是到这一步日志还不是提交状态，因为后面可能出现Leader节点宕机、或者不满足多数派节点都应答的条件，这些已写入Follower日志模块但是还未达到提交条件的日志就被称为未提交日志，这部分日志需要被相同索引的已提交日志覆盖。
• 以上两种情况都存在。

图 5.24 演示了几种日志不同步的情况。最上面的数字是日志索引，可以看到日志索引必须保持单调递增且连续的特性。在带颜色矩阵中的数字则是任期号，相同的任期号使用同一种颜色。为了简化问题的讨论，图中没有应用层的数据，只有日志的索引和任期，但是并不影响问题的讨论。从图中可以看到，任期号可以不连续，比如索引为3的日志任期号为1，而它的下一条索引为4的日志任期号为4。当前Leader节点的最后一条日志二元组为(6,10)，以下分别解释这几种场景：

• 场景a：最后一条日志为(6,9)，顺序比Leader上最后一条日志(6,10)更小，属于缺失日志的情况。
• 场景b：最后一条日志为(4,4)，这条日志与Leader节点上索引为4的日志二元组相同，因此是一致的日志，根据日志匹配属性的第二条规则，前面的日志肯定也保持一致。但是情况b的最后一条日志(4,4)顺序比Leader上最后一条日志(6,10)更小，属于缺失日志的情况。
• 场景c：最后一条日志为(6,10)，顺序比Leader上最后一条日志(6,10)更大，属于有未提交日志的情况，日志11需要被删除。
• 场景d：最后一条日志为(7,11)，顺序比Leader上最后一条日志(6,10)更大，属于有未提交日志的情况，日志11和12需要被删除。
• 场景e：最后一条日志为(4,7)，而Leader节点上索引为7的日志二元组为(5,7)，两者并不匹配，Leader节点需要首先找到Follower节点上最后一个相同二元组的日志（日志(4,5)），从这个位置继续同步日志，Follower节点上未提交的日志（日志索引6和7）将被覆盖。
• 场景f：最后一条日志为(2,6)，而Leader节点上索引为6的日志二元组为(5,6)，两者并不匹配，Leader节点需要首先找到Follower节点上最后一个相同二元组的日志（日志(1,3)），从这个位置继续同步日志，Follower节点上未提交的日志（日志索引4、5、6）将被覆盖。

5.5.4 安全性 #

以上描述了Raft算法中最重要的两个流程：Leader选举和日志复制，但是目前为止还不足以保证系统的安全性问题：任何节点都要以相同顺序执行日志。例如，在Leader节点提交日志的时候，某个Follower节点刚好宕机，等到这个节点恢复以后，它可能被选为新任期的Leader，覆盖了旧任期节点提交的日志，这就导致了不同的日志执行顺序。

本小节将在前面流程的基础上增加一些限制条件，以确保算法的安全性。

Leader选举

在前面Leader选举的流程中，我们提到了只要一个Candidate节点能够赢得多数派的选票，就能成为新任期的Leader节点，但是并没有提及Candidate赢得其它节点选票的条件是什么。

以"是否在一个任期给另外的节点投票"做为投票的依据是不够的。考虑这样一种场景：

• Leader节点上的日志[4,5,6]获得了多数派节点的同意，成为已提交日志。
• 在同一时间，Follower节点A宕机，在它的日志中不存在这几条日志。
• Leader节点宕机，Follower节点A恢复并且选举超时切换到Candidate状态进行一轮选举。
• 由于在这一轮其它还在线的节点都没有进行过投票，所以把票都投给了节点A，节点A成为这一轮的Leader节点。
• 节点A上不存在上一任期提交的日志[4,5,6]，因此这部分日志最终会被覆盖。

为了避免出现这种已提交日志被新任节点覆盖的情况，节点投票时需要对比Candidate节点的日志和本节点上的日志顺序（判断日志顺序的算法在日志复制小节中给出），Raft算法要求只能给不比本节点日志更旧的Candidate节点投票。

加上Leader选举的这个限制条件之后，我们再来看前面可能出现已提交日志被覆盖的场景：由于日志[4,5,6]是上一任节点提交的日志，说明这几条日志被多数派节点通过，这也就意味着多数派节点上存在这几条日志，因此当Follower节点A发起投票时，由于这个节点上不存在这几条日志，那么它一定不会赢得多数派的投票，这样也就避免了覆盖上一任节点已提交日志的情况。

复制旧任期的未提交日志

我们继续讨论由于Leader节点崩溃导致的日志复制问题。请看这样的问题：如果Leader节点在本地写入日志后崩溃，当该节点恢复并且在另一个新的任期再次当选为Leader节点时，是否可以直接复制本节点上一个当选任期中的本地未提交日志到系统中的其它节点？

我们来看看如果允许这么做，将会出现什么问题，如图 5.25 所示：

• 系统中共有5个节点。和图 5.24 中一样，上面的数字代表日志索引，而带颜色矩阵中的数字则是任期号，不同的任期号使用不同的颜色进行区分。
• (a)：S1节点是任期2的Leader节点，在向本节点和S2节点写入日志(2,2)之后，S1节点崩溃。
• (b)：此时S5节点选举超时，以任期号3发起一轮新的选举。由于S5节点的最大日志索引为(1,1)，可以赢得多数派的选票，因此当选为任期3的Leader。S5在向本地写入日志(3,2)之后崩溃。
• (c1)：S5节点崩溃之后，S1节点恢复并且选举超时，于是S1将以任期4发起一轮新的选举。由于S1节点上的最新日志是(2,2)，同样也能赢得这一轮选举。如果这时允许Leader节点直接复制在节点上还未提交的旧任期日志，S1节点将首先同步本地未提交的日志(2,2)到系统其它节点。在节点S3应答成功后，由于此时S1、S2、S3节点都有这一日志，满足多数派通过的条件，因此S1认为日志(2,2)已被提交，它继续在本地写入下一条日志(4,3)，然后又崩溃了。
• (d)：此时如果节点S5从崩溃中恢复，选举超时之后赢得选举（S5节点上的最后日志为(3,2)，可以赢得多数派投票），将可能出现S5将日志(3,2)复制到所有节点，覆盖了(c)中已经被写入到多数派的日志(2,2)！

从以上分析可以看出，如果在(c1)中允许S1节点恢复并且在新任期当前之后，直接复制旧任期的未提交日志，将可能出现(d)这样已写入多数派的日志被覆盖的情况。

为了解决这一问题，Raft算法规定：**在Leader节点当选之后，第一条被复制的日志只能是本任期的日志。**根据日志匹配属性中的第二条规则，如果本任期的日志能够成功提交，那么在它之前的旧任期日志也都能提交。

根据这个规定，(c1)变成了(c2)：S1节点在任期4再次当选为Leader之后，将不会首先复制本地的旧任期日志(2,2)，而是复制一个当前任期的日志(4,3)。如果这条日志能够复制到多数派，根据日志匹配属性的第二条规则，在这条日志之前的日志(2,2)也将提交成功。而如果日志(4,3)没有被成功复制到多数派（例如节点S1在复制日志(4,3)的过程中再次宕机），那么覆盖日志(4,3)和(2,2)就不算是覆盖已提交日志。

备注：在具体实现中，节点在刚当选为Leader节点之后，将首先复制一条本任期的空日志（即没有数据内容的日志，空日志也被称为"no ops日志"），避免出现节点当选后一直没有日志写入，导致旧任期日志一直无法提交成功的情况。

5.5.5 集群成员变更 #

在Raft算法中，**集群成员变更（Membership Change）**是一个关键功能，用于动态添加或移除节点，确保系统在动态环境中保持一致性和可用性。Raft的成员变更算法设计目标是保证安全性（不破坏一致性）和可用性（尽量减少服务中断）。

安全性 #

成员变更流程中，需要保证的安全性是：任意时刻在集群中不能同时出现一个以上的Leader节点，否则将出现**脑裂（split brain）**问题。

为了避免出现脑裂现象，变更流程中必须避免出现两个不相交多数派的场景。如图 5.26 中，旧的集群配置$C_{old}$中有三个节点（节点1-3），向系统添加2个新节点（节点4-5）。随着时间推进，新的集群配置$C_{new}$（节点1-5）将被提交到系统中的所有节点（包括旧集群节点和新集群节点），但是不同的节点新配置提交的时间并不一致，图中使用绿色表示节点当前的配置仍然是旧的$C_{old}$配置，紫色表示节点当前的配置是新的$C_{new}$配置。在某一时刻可能出现这样的情况：

• 节点1和节点2上还是旧的$C_{old}$配置，所以此时这两个节点认为当前集群仍然是只有节点1、2、3组成的三节点集群，这样节点1和节点2就能构成一个旧配置下的多数派。
• 节点3上此时已经变更为新的$C_{new}$配置，于是节点3、4、5也能构成一个$C_{new}$配置下的多数派。
• 如果在这一时刻发生选举，因为有两个不相交的多数派集合，就可能选出两个不一样的Leader节点。

所以，如何避免在集群变更中出现不相交的多数派，成为保证集群变更安全性的核心问题。围绕着这个问题，我们接下来讨论集群变更的两种方式：单步成员变更和联合成员变更。

单步成员变更 #

在单步成员变更算法中，每一次只允许变更（添加、删除）一个节点。如图 5.27 所示，考虑了旧集群节点数量为奇数和偶数，以及添加和删除节点组合起来的四种情况，每一种情况都不会出现有两个不相交的多数派集合。以(b)为例，向一个3节点集群添加一个节点，旧集群中的多数派必须至少包含2个旧集群节点（蓝色部分），而新集群的多数派必须包含3个节点（橙色部分），两者必然有交集。

单步成员变更的正确性问题

单步成员变更在某些情况下会出现正确性问题，导致已经提交的日志被覆盖，Raft作者Diego Ongaro早在2015年就发现了这个问题，并且在Raft开发者邮件组中详细说明了这个问题[13]。

如图 5.28 所示是单步变更时出现正确性问题的例子，集群的初始成员是a、b、c、d这四个节点，节点u和v使用单步变更方式加入集群。图中演示了在这个变更过程中如果出现Leader切换，就会导致丢失已提交日志的情况。以下按照时间顺序解释各时间点的事件：

• $t_0$：集群的初始成员配置为$C_0 = \{a,b,c,d\}$。
• $t_1$：$C_0$集群在任期0选出了节点a做为该任期的Leader节点。
• $t_2$：为了将节点u加入集群，Leader节点a同步变更日志$C_u$到集群，但是日志只同步到了节点a和节点u，未完成提交。
• $t_3$：Leader节点a宕机。
• $t_4$：在节点a宕机之后，集群进入新的任期，节点d被选为这一任期的Leader，节点b和节点c成为这一任期的Follower。
• $t_5$：为了将节点v加入集群，Leader节点d开始向集群同步新的集群配置$C_v$，这条日志被同步到了节点c、d和v，成功提交。
• $t_6$：节点d写入一条普通日志，由于写入三个节点，所以这条日志成功提交。
• $t_7$：Leader节点d宕机。
• $t_8$：节点a恢复运行，并且在新任期中重新当选为Leader节点。这是因为：节点a最后的日志中没有加入节点v的日志，因此在它看来集群当前只有$C_u$配置下的4个节点，而节点u、a和b上并没有在$t_5$时提交的日志，因此这几个节点都将同意节点a的选举请求。
• $t_9$：节点a同步本地未提交的集群单步变更日志$C_u$到集群所有节点（除了节点v），造成已经提交的日志$C_v$和E丢失。

为什么会出现这样的问题呢？根本原因是上一任Leader的成员变更日志还没有同步到多数派就宕机了，新Leader一上任就进行成员变更，使用新的成员配置提交日志，之前上一任Leader重新上任之后可能形成另外一个多数派集合，产生脑裂，将已提交的日志覆盖，造成数据丢失。

Raft作者在发现这个问题之后，也给出了修复方法。修复方法很简单, 和Raft的日志Commit条件类似：新任Leader必须在当前提交一条日志之后，才允许同步成员变更日志。也即Leader在当前还未提交日志之前，不允许同步成员变更日志。

按照这个修复方法，最简单的实现就是Leader上任后先提交一条no-op日志，然后再同步成员变更日志。这条no-op日志可以保证跟上一任Leader未提交的成员变更日志至少有一个节点交集，这样可以发现上一任Leader的日志是旧的，从而阻止上一任Leader重新选为Leader，进而阻止了脑裂的产生。

对应上面这个例子，就是$L_1$当选Leader后必须先提交一条no-op日志，然后才能开始同步$C_v$和E，以便能发现$L_2$的日志是旧的，从而阻止$L_2$当选Leader。

单步成员变更的可用性问题

除了正确性问题，单步变更还有可用性问题。图 5.29 所示，系统最初有三个节点a、b和c，分别位于三个不同的数据中心。此时希望将节点a下线，替换为同一数据中心的节点d。如果按照单步变更方式实现这个变更，那么会经历两步：首先将节点d加入集群，再将节点a从集群中下线。如果在将节点d加入集群而节点a还未下线的时候，集群发生网络分区，节点a和节点d所在的数据中心1与另外两个数据中心的网络无法连接，那么无论是节点a和节点d所在的分区，还是节点b和节点c所在的分区都无法选出一个新任的节点Leader，这将导致系统的可用性受到影响。

为了解决这一问题，可以考虑首先将节点a下线，再将节点d上线，这样即便有网络分区情况也不会出现无法选出Leader节点的情况，但是这样的操作顺序在中间会存在系统中只有两个节点的情况，2个节点组成的集群只能允许一个节点出现故障，也会对系统的安全造成影响。

从以上两个问题可以看到，单步成员变更时需要特别小心，因此在实践中更多时候采用的是**联合成员变更（Joint Consensus）**算法。

联合成员变更 #

从以上单步成员变更的问题分析中，我们看到直接切换成员变更可能存在的风险：

• 安全性问题：如果每个节点切换到新配置的时间不一致，可能会出现两个不相交的多数派，导致选举出两个Leader节点。
• 可用性问题：单步成员变更可能在存在网络分区时导致集群不可用。例如，假设集群从配置{abc}变更为{bcd}，中间状态{abcd}可能因网络分区（如ad|bc）导致无法达成多数派。

联合共识通过引入一个过渡阶段$C_{old,new}$，确保旧配置和新配置的多数派都同意变更，从而避免上述问题。它的核心思想是：在变更成员配置时，集群先进入一个过渡状态（联合共识状态），在这个过渡状态中同时使用旧配置（$C_{old}$）和新配置（$C_{new}$）的组合（$C_{old,new}$），然后再切换到新配置（$C_{new}$）。由于中间过渡状态下的集合$C_{old,new}$和变更前的$C_{old}$以及变更后的$C_{new}$都有交集，所以不会出现两个不相交多数派，也就不会选出两个Leader节点，避免了安全性问题。

图 5.30 演示了联合成员变更算法的两阶段流程：

• 阶段一：旧集群Leader节点收到成员变更请求后，领导者生成一个包含旧配置（$C_{old}$）和新配置（$C_{new}$）的联合日志条目（$C_{old,new}$），并将其复制到所有节点。在此阶段，所有日志（包括普通日志和成员变更日志）必须同时满足$C_{old}$和$C_{new}$的多数派确认才能提交。这意味着：日志需要分别被复制到$C_{old}$和$C_{new}$中的大多数节点。一旦$C_{old,new}$日志被提交，集群正式进入联合共识阶段。
• 阶段二：切换到新配置（$C_{new}$）：
  • 领导者生成一个仅包含新配置（$C_{new}$）的日志条目，并将其复制到所有节点。
  • 此日志只需要$C_{new}$中的多数派确认即可提交。
  • 一旦$C_{new}$日志被提交，集群完成成员变更，旧配置（$C_{old}$）被废弃。

联合成员变更算法通过几个关键约束来保证变更流程的安全性：

• 领导者选举限制：在联合共识阶段，只有拥有所有已提交日志（包括$C_{old,new}$日志）的节点才能成为领导者。这确保新领导者了解最新的成员配置，避免不一致。
• 日志复制限制：在联合共识阶段，日志必须同时被$C_{old}$和$C_{new}$的多数派确认，防止任何一方单方面提交日志。
• 两阶段切换：通过引入过渡状态（$C_{old,new}$），Raft避免了直接从$C_{old}$切换到$C_{new}$可能导致的冲突。

我们来看看联合成员变更算法，在变更过程中如果出错，如何保证系统的高可用性，选出新leader。

如果在第一阶段出错，这时候选出来的Leader只有可能有两种情况：旧的$C_{old}$节点集合，或者已经收到了$C_{old,new}$节点集合：

• 只有$C_{old}$节点集合的节点：由于这时候这个leader并没有第一阶段提交的$C_{old,new}$节点集合变更，因此那些已有$C_{old,new}$节点集合的Follower这部分的日志将被截断，成员变更失败，回退回$C_{old}$集合。
• 有$C_{old,new}$节点集合的节点：这意味这个Leader已经有第一阶段提交的$C_{old,new}$节点集合变更，可以继续将未完成的成员变更流程走完。

同理，可以去推导一下在第二阶段出现Leader宕机时，选出来的Leader只可能具备两种情况，但是这两种情况都不可能选出多个leader。

可以看到对比单步成员变更算法，联合成员变更算法保证了安全性和可用性：

• 安全性：中间过渡阶段的$C_{old,new}$联合共识确保$C_{old}$和$C_{new}$不会同时形成两个不相交的多数派，防止出现两个领导者。通过要求$C_{old}$和$C_{new}$日志同时满足两个配置的多数派，Raft保证了变更过程中的一致性。
• 可用性：联合共识避免了单阶段变更可能导致的集群不可用问题。例如，在上述示例中，单阶段变更可能经过中间状态abcd，若发生网络分区（如ad|bc），可能无法达成多数派。而联合共识通过$C_{old,new}$过渡状态避免了这种风险。

5.5.6 网络分区时的活性问题 #

在某些极端情况下，由于网络分区问题会导致Raft频繁进行Leader选举，以至于出现活性问题影响系统的可用性[14][15]。我们来考察这些问题以及对应的解决方案。

首先来回顾一下标准的Raft选举流程，当一个 Follower 在超时时间内未收到 Leader 的心跳时，它会执行以下动作：首先增加本地的任期号，将状态转换为 Candidate，向集群广播 RequestVote RPC发起选举请求。

考虑如图 5.31 所示的场景，由4个节点组成的集群中，1、2、3节点互通，但是由于网络分区等原因，节点4只能发送消息给其它节点，收不到来自其它节点的消息。节点4一直收不到来自Leader节点的消息，根据选举流程在选举超时之后将递增自己的任期号发起一轮选举。现任的Leader节点在收到节点4上的选举请求后，根据Raft的选举规则，Leader节点上的日志任期号更小，从而被迫转为Follower节点，这会导致集群强制进入一轮本不必要的选举，造成服务短暂不可用。虽然节点4的日志并不比其它节点的更新，最终节点4不会赢得选举，新任期的节点仍然会在互通的三个节点之间产生。但是由于每次选举超时都会发起选举，所以影响了系统的可用性。

这种因网络分区产生的高任期节点，即使它无法赢得选举，它也会通过强制退位现任 Leader 来扰乱集群的稳定性。

这个问题的本质是：由并不具备当选条件（有当前最新的日志）的节点，发起了一轮新的选举。为了解决这类问题，引入了Pre-Vote阶段：

• 要发起选举的节点，首先进入PreCandidate状态发起"预选举"，在预选举时节点并不会去递增任期号，而只是和其它节点对比是否有更新的日志数据。注意其它节点在收到预选举阶段的请求时，并不会切换节点的状态（因为任期号并没有增加），所以预选举阶段并不会影响系统的可用性。
• 如果节点能够收到多数派的预选举阶段投票，就认为该节点上的日志满足获得选举的条件，可以发起一轮正常的选举流程。

回到图 5.31 中的情况，引入了预选举阶段后，节点4在预选举阶段将不会赢得多数派选票，也就不会发起一轮正常的选举流程了。

从上面的分析可以看到，采用预选举规避发起选举的方案有一个假设的前提：由于网络分区导致发起一轮新选举的节点上并不具备最新的日志，因此这个节点将不会赢得预选举阶段的多数派选票。可是如果这一前提并不存在，又面临了新的问题。

如图 5.32 所示，三个节点上的日志相同（即都具备当选为Leader的条件），节点1和节点3互通，节点2和节点3互通，但是节点2与节点1无法通信。如果此时节点1是Leader节点，由于节点2无法收到来自节点1的消息，节点2会发起一轮新的选举，由于日志都是一样的，节点2将收获节点3的选票，当选为新任的Leader节点。

在上面的场景中，如果三个节点的日志一直保持一致（例如在这段时间内没有新的数据写入），那么将频繁发生Leader节点的变更：节点1和节点3由于无法通信，因此都会在对方当选之后选举超时发起新的选举。

为了解决这个问题，引入了**Leader租期（Leader Lease）**机制：规定Follower节点如果在一次选举超时时间之内收到了来自当前Leader节点的消息，将不会给其它节点投票。

仅仅引入预选举流程和Leader租期机制还没有解决所有网络分区导致的活性问题。以图 5.33 为例，5个节点组成的集群中，节点1、2、3保持互通，当前的Leader节点为节点4，但是节点4只和节点2相连，节点5与其它所有节点断开连接。在这种情况下，节点1和节点3由于收不到Leader节点4的消息，将发起一轮新的选举。但是节点2由于能够收到Leader节点4的消息，将不会给选举请求投票，因此最终选举以失败告终。

这个问题的本质是：当前的Leader节点4由于网络分区原因，与集群多数派节点断开连接。在这种情况下，Leader节点4已经不适合继续当选Leader节点了。因此Leader节点需要一种机制，来探测自己做为Leader节点的合理性。

etcd引入了CheckQuorum机制[16]：Leader节点定期会给其它节点发送心跳请求，如果没有收到多数派节点的响应，将认为自己已经和多数派节点断开连接，主动放弃Leader的任期。

图 5.34 是对以上三种方案的简单总结。

5.5.7 日志压缩 #

Raft算法运行在操作日志体系之上，久而久之会积累很多冗余的数据，如图 5.35 所示，系统当前的状态是最后的数据{x=0,y=5}，过程中的很多操作数据都可以丢弃了。

系统存在大量冗余数据会出现以下问题：

• 启动速度慢：考虑系统重启时需要按序重放日志构建正确的运行状态，大量日志会导致系统重启速度慢；
• 空间占用大：系统只需要存储最近的状态即可，在此之前的数据不再需要，以图 5.35 所示，对变量x和y而言只需要存储最后的{x=0,y=5}。

基于以上的原因，需要对日志进行压缩，去除冗余的过期数据。Raft算法引入**快照（snapshot）**来解决，我们曾经在 4.3.2 节中对快照机制做过详细的介绍，所谓快照可以理解为在某个时间点对系统状态的完整复制，对于同一个对象，快照只保留了最后的数据。快照数据需要包含以下的内容：

• 快照中最后一条日志的索引和任期号。
• 压缩后快照中状态机的数据。

如图 5.36 所示，如果对日志索引5及之前的数据进行快照压缩，将得到：

• 快照中最后一条日志的索引为5，任期号为3。
• 压缩后快照中状态机的数据为{x=0,y=3}。

在采用快照压缩日志之后，系统启动时分为两步：

• 如果存在快照数据，将首先读取快照数据，得到当前的状态机数据。
• 再接下来读取剩余的日志，每读取一条日志同步更新当前的状态机数据。

同样以图 5.36 为例：

• 系统当前存在快照数据，首先读取快照数据，得到当前系统状态机数据为{x=0,y=3}。
• 读取日志6，读到数据{y=4}，当前系统状态机数据为{x=0,y=4}。
• 读取日志7，读到数据{y=5}，当前系统状态机数据为{x=0,y=5}。

备注：对于快照数据需要注意，只有被提交的日志才能被保存到快照数据中，因为没有提交的日志可能会被删除，例如图 5.24 中(d)的日志11和12当前还没有达到已提交状态，这类日志就不能保存到快照中。

在 5.5.3 节中讨论日志复制时，还是基于纯粹的日志系统存储来讲解的。在使用快照压缩日志之后，我们看一看日志复制机制需要做哪些改动。

首先是生成快照的时机。如果频繁生成快照，将给系统造成不小的负担；但是如果快照相差过大，同样会出现前面启动速度慢、空间占用大等问题。实际上这里没有满足所有系统要求的方案，常见的方式是指定每生成多少日志就需要生成一次快照，将这个选项交给用户来配置。

其次，与复制日志不同的是，快照文件通常会大得多，如果一次性传输很大的文件速度慢而且如果中间过程出错，就需要从头再来。通常会采取**分块（chunk）**的方式来同步快照文件，既可以同时传递多个分块文件，也可以减小文件出错时的重传文件大小范围。例如：将快照文件分为N份，每一份分块文件中保存该分块数据在快照文件中的偏移量，最后一份分块文件比其它分块文件还多一个结束标志和快照文件的校验码。只有当收到所有分块文件并且拼装校验成功后，才认为接收了完整的快照文件。

5.5.8 实现线性一致性读 #

Raft算法实现的是线性一致性（3.2.1 节），即要求：每次读请求都能读到最新写入的数据。考虑以下的场景：当系统发生分区时，旧的Leader节点2被划到了一个节点数量不超过半数的分区，而在另一个分区，已经选出了新的Leader节点。如果此时客户端向旧Leader节点2读数据，那么可能将读到过期的数据，这显然不符合线性一致性的要求。

可以看到，这里的难点在于：Leader节点需要一种机制来确保自己当前仍然是系统的Leader节点，这样才能安全得向客户端返回读请求的结果。

一种实现线性一致性读的方案是：Leader节点收到客户端读请求之后，当成一个写请求来处理，收到读请求时同样写入一条空日志，如果日志能够正常得被半数以上节点复制，并最终提交到状态机中，就认为Leader节点还没有过期，可以向客户端返回读请求的结果。这种方案存在的问题是：每次读请求都要完整运行一次Raft日志提交流程，开销太大。

Raft算法通过在Leader节点中引入一个称为readIndex变量的方式来优化线性一致性读，这是目前最常用、性能更好的优化方案。它的核心思想是：在不真正追加日志的情况下，获取一个能够代表当前系统最新状态的"索引点"（ReadIndex），然后等到状态机应用到这个点之后再读。流程如下：

1. 领导者确认身份：Leader节点需要在当选后的新任期提交一条no-op的空日志，如果这条空日志能够提交成功，那么Leader节点上的索引commintIndex就能保证和任期内的其它节点一样大。这一点在 5.5.4 节中已经有详细的讨论。
2. 获取读索引：随着日志被提交成功，commintIndex就会相应增大，领导者将当前已提交的最新日志索引（commitIndex）记录为 readIndex。
3. 等待状态机应用：领导者需要等待自己的状态机至少应用到了readIndex这个位置。这是为了确保所有在 readIndex之前提交的写操作都已经被本地状态机执行了。
4. 执行读取：一旦状态机应用进度 >= readIndex，领导者就可以安全地从本地状态机中读取数据。
5. 返回结果：领导者将结果返回给客户端。

在 ReadIndex 方案中，第二步"确认身份"仍然需要一轮心跳广播，这在高并发读场景下仍有优化空间。5.5.6 节中提到的领导者租约是一种常见的优化。它的原理是，领导者假设在它上次成功心跳后的一段短时间内（租约期内），只要它自己没有宕机，网络没有严重分区，它就应该仍然是领导者。在租约有效期内，领导者可以跳过第二步的心跳确认，直接使用当前的 commitIndex 作为 readIndex。但是这个方案也存在一定风险：如果时钟漂移严重或网络在租约期内发生分区，可能导致过期领导者提供脏读（违反线性一致性）。因此，需要谨慎设置租约时长。

5.6 本章小结 #

本章系统阐述了分布式共识算法（Consensus Algorithms）的核心原理、理论边界及其在工程实践中的演进脉络。共识算法作为构建强一致性分布式系统的基石，解决了在部分节点故障或网络分区等不确定环境下，分布式集群如何就系统状态达成一致的核心问题。

回顾本章内容，我们从以下几个维度对分布式共识算法进行了深入剖析：

理论边界与模型假设

本章首先探讨了 FLP 不可能定理，明确了在完全异步的分布式系统中，不存在一个既满足确定性又能保证容错的共识算法。这一理论基石揭示了安全性与活性之间的权衡关系。主流共识算法（如 Paxos 和 Raft）的设计哲学均是在严格保障安全性（即一致性）的前提下，通过引入"部分同步"假设（如超时机制）来满足系统的活性需求。

Paxos算法的推导与优化

我们通过从"主从复制"到"多数派读写"的逐步推导，解析了 Paxos 算法的诞生背景。Basic Paxos 通过两阶段提交（Prepare 与 Accept）解决了提案冲突问题，确立了共识算法的基本范式。随后介绍的 Multi-Paxos 引入了稳定的领导者（Leader）概念，通过减少 RPC 交互次数和连续日志提交，解决了 Basic Paxos 在高并发场景下的性能瓶颈，为工程实现提供了优化方向。

Raft 算法的架构与机制

作为对 Multi-Paxos 的工程化与规范化，Raft 算法将复杂的共识问题解耦为三个独立的子问题：

• 领导者选举：利用任期（Term）作为逻辑时钟，配合随机超时机制，确保了领导者的唯一性与合法性。
• 日志复制：通过强制的"日志匹配属性"，保证了日志在集群间的连续性与一致性。
• 安全性约束：确立了"领导者完备性（Leader Completeness）“原则，确保已提交的日志不会丢失。

算法的理论正确性仅仅是系统落地的起点。本章重点讨论了将共识算法应用于生产级系统时必须解决的关键问题：

• 集群成员变更：分析了动态调整节点时可能产生的"脑裂"风险，并详细阐述了单步变更与联合共识（Joint Consensus）的解决方案。
• 日志压缩：介绍了利用快照机制解决日志无限增长带来的存储与恢复问题。
• 性能与活性优化：探讨了 Pre-Vote 机制以避免网络分区导致的无效选举，以及 ReadIndex 和 Lease Read 机制如何在保障线性一致性读的前提下提升读取性能。

综上所述，分布式共识算法本质上是通过严格的多数派协议与状态机复制机制，将不确定的物理网络抽象为逻辑上严格有序的整体。深入理解 Paxos 与 Raft 及其背后的设计权衡，是掌握分布式系统一致性问题的关键所在。

---

参考文献 #

[1] Fischer M J, Lynch N A, Paterson M S. Impossibility of distributed consensus with one faulty process[J]. Journal of the ACM (JACM), 1985, 32(2): 374-382.

[2] Brief FLP. https://www.the-paper-trail.org/post/2008-08-13-a-brief-tour-of-flp-impossibility/

[3] Lamport L. The part-time parliament[J]. ACM Transactions on Computer Systems (TOCS), 1998, 16(2): 133-169.

[4] Lamport L. Paxos made simple[J]. ACM Sigact News, 2001, 32(4): 18-25.

[5] Leslie Lamport. https://en.wikipedia.org/wiki/Leslie_Lamport

[6] Michael Burrows (computer scientist). https://en.wikipedia.org/wiki/Michael_Burrows_(computer_scientist)

[7] Burrows M. The Chubby lock service for loosely-coupled distributed systems[C]//Proceedings of the 7th symposium on Operating systems design and implementation. 2006: 335-350.

[8] 可靠分布式系统 paxos的直观解释. https://blog.openacid.com/algo/paxos/

[9] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[10] Chandra T D, Griesemer R, Redstone J. Paxos made live: an engineering perspective[C]//Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

[11] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm[C]//2014 USENIX Annual Technical Conference. 2014: 305-320.

[12] Ongaro D. Consensus: Bridging theory and practice[D]. Stanford University, 2014.

[13] Raft-dev: Single-server membership changes safety. https://groups.google.com/g/raft-dev/c/t4xj6dJTP6E

[14] A Byzantine Failure in the Real World. https://blog.cloudflare.com/a-byzantine-failure-in-the-real-world/

[15] Raft liveness and the full omission fault. https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission/

[16] etcd issue #3866: CheckQuorum. https://github.com/etcd-io/etcd/issues/3866