【论文阅读笔记】In Search of an Understandable Consensus Algorithm (Extended Version)

1 介绍

分布式一致性共识算法指的是在分布式系统中，使得所有节点对同一份数据的认知能够达成共识的算法。且算法允许所有节点像一个整体一样工作，即使其中一些节点出现故障也能够继续工作。之前的大部分一致性算法实现都是基于Paxos，但Paxos难以理解和实现，为此作者开始寻找一种新的易于理解的一致性算法，Raft则是作者工作的产出。

在设计Raft的过程中，作者采用了一系列策略来增强其可理解性，包括：

• 算法分解：Raft将核心功能模块化，分离出领导人选举、日志复制和安全性三个关键部分，使每个部分的逻辑更加清晰。
• 状态空间缩减：相比于Paxos，Raft减少了不确定性和服务器间的不一致性状态，简化了状态机模型，从而降低了理解和实现的难度。

Raft 算法在许多方面和现有的一致性算法都很相似，但是它也有一些特性：

• 强领导人机制：Raft采用了更强的领导人角色，所有日志条目仅由领导人发送给其他服务器，这种集中控制方式简化了日志管理，增强了算法的直观性。
• 领导人选举：Raft使用随机计时器来触发领导人选举，这种机制在心跳机制的基础上增加了少许复杂性，但有效地解决了选举冲突，实现了快速而简单的决策过程。
• 成员关系调整：Raft 使用一种联合共识的方法来处理集群成员变换的问题，在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠，这就使得集群在成员变换的时候依然可以继续工作。

2 复制状态机

复制状态机是共识算法的核心应用背景，它是指一组服务器上的状态机生成相同状态的副本，即使部分服务器宕机也能持续运行。这种架构在大规模分布式系统中尤其重要，因为它能够解决一系列容错问题。例如，大规模的系统中通常都有一个集群领导人，像 GFS、HDFS 和 RAMCloud，典型应用就是一个独立的复制状态机去管理领导人选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。

复制状态机通常都是基于复制日志实现的，如图 1。每个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。所有日志都包含相同的指令序列，确保状态机一致，因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

一致性算法的任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，即使有些服务器发生故障。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成了一个高可靠的状态机。

实际系统中使用的一致性算法主要有以下特性：

• 安全性保证（绝对不会返回一个错误的结果）。
• 即使部分服务器失败，只要多数服务器运行，系统依然可用。
• 不依赖于时序，能够应对时钟错误和消息延迟。
• 大多数情况下，指令可以在一轮远程过程调用后完成，不受少数慢节点影响。

3 Paxos的问题

1. Paxos极其难以理解。

2. 没有为构建实际系统实现提供良好的基础。

4 为了可理解性的设计

设计Raft算法的初衷：

1. 必须提供一个完整的实际的系统实现基础，减少开发者工作量；

2. 必须在任何情况下都是安全的并且在大多数的情况下都是可用的；

3. 它的大部分操作必须是高效的；

4. 可理解性，它必须保证对于普遍的人群都可以十分容易的去理解；

5. 便于系统构建者形成直观理解，便于实际应用和扩展；

Raft设计原则：

1. 问题分解：将复杂问题拆解为独立、易于理解和解决的子问题。例如，Raft 的领导人选举、日志复制、安全性和成员变更。

2. 状态空间简化：减少状态数量，降低系统复杂性并在可能的时候消除不确定性。确保日志无空洞，限制日志不一致的可能性。

3. 随机化应用：在领导人选举中使用随机化，简化机制，快速解决冲突。

5 Raft一致性算法

Raft 是一种管理复制日志的一致性算法，通过选举领导人并由其管理日志来实现一致性。领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并告诉其他的服务器什么时候可以安全地将日志条目应用到他们的状态机中。这一决策过程无需与其他服务器进行商议，从而简化了整个复制日志的管理流程，并且数据都从领导人流向其他服务器。一个领导人可能会发生故障，或者和其他服务器失去连接，在这种情况下一个新的领导人会被选举出来。

Raft算法的一致性问题被巧妙地分解为三个关键子问题：

• 领导选举：当领导人发生故障的时候, 一个新的领导人需要被选举出来，确保系统的连续性和稳定性（5.2）
• 日志复制：领导人必须从客户端接收日志条目然后复制到集群中的其他节点，并强制要求其他节点的日志和自己保持一致。
• 安全性：Raft通过特定的机制（5.4）确保一旦日志条目被应用到某个服务器的状态机中，其他服务器不会在同一日志索引位置应用不同的指令，从而保障了系统状态的一致性和安全性。

5.1 Raft基础

一个 Raft 集群由若干个服务器节点构成，如常见的 5 节点配置，能容忍最多 2 个节点失效。节点有以下三种状态：

• 领导人：唯一决策者，处理所有客户端请求，并且管理复制日志。

• 跟随者：被动角色，仅响应领导人和候选人的请求。

• 候选人：竞选状态，用于选举新领导人
  

跟随者在收不到消息时，升级为候选人，启动选举；获得多数票的候选人成为领导人；领导人宕机或发现任期过期，降级为跟随者。

Raft 通过任期来划分时间，每个任期都始于一次选举。任期用整数标记，每段任期有其选举过程。如果选举成功，选出的领导人将负责管理集群，直到该任期结束。任期在Raft中充当逻辑时钟的作用，帮助节点检测过期信息，如过期的领导人。

每个节点维护一个当前任期号，通信时交换任期号，节点自动更新至较大值，领导人或候选人如果发现任期号过期，会恢复为跟随者；节点拒绝过期任期请求。

在 Raft 算法中，节点间的通信依赖于RPC。基本的一致性算法主要使用两种类型的 RPCs：

• 请求投票RPC：候选人发起，用于选举。

• 附加条目RPC：领导人发起，复制日志和提供心跳机制。

• 安装快照PRC：领导人发起，安装快照。为了提高性能，服务器在未及时收到响应时会重试 RPC，并且能够并行发起 RPC。

5.2 领导人选举

Raft 算法采用心跳机制来触发领导人选举过程。服务器启动时，默认处于跟随者状态，仅当接收到来自领导人或候选人的有效 RPC 时才保持这一状态。领导人定期向所有跟随者发送心跳包，即不含日志项的附加条目RPC，以此维护其领导地位。若跟随者在设定的选举超时时间内未收到任何消息，它将假定无有效领导人并发起选举，以选出新的领导人。

选举流程开始时，跟随者增加自己的当前任期号并转换为候选人状态，然后向集群中其他服务器节点发送请求投票RPC来给自己投票。候选人保持该状态，直至出现以下三种情况之一：

• 赢得选举。

• 其他服务器成为领导人。

• 在一定时间内无明确获胜者。

赢得选举的条件是获得集群大多数服务器节点的选票，每台服务器对同一任期号的投票遵循先来先服务原则，并有额外限制（5.4）以确保选举安全性，避免了脑裂（同一人气，集群出现两个领导人）。一旦当选，候选人即刻转变为领导人，通过发送心跳消息确立领导地位并阻止发起新选举。

在等待投票的过程中，候选人可能接收到领导人发送的附加条目RPC，如果该领导人任期号不低于候选人的任期号，候选人将认可其合法性，回归跟随者状态；反之，候选人将拒绝RPC，继续竞选。若多个候选人同时发起选举，选票分散可能导致无人胜出，所有候选人均会因超时而重新开始选举，但任期号会递增。

为防止选票分散，Raft算法引入了随机化选举超时时间策略。各服务器在固定时间范围内（例如$[150,200]$）随机选取超时值，使得通常情况下仅有一台服务器超时，进而顺利赢得选举并在其他服务器超时前发送心跳。即使发生选票分散，随机化的超时机制也降低了下一轮选举中再次分散的可能性。

作者最初设计考虑过引入排名系统以决定优先级，但发现这可能导致高排名服务器故障时的可用性问题，且算法调整复杂，难以确保没有副作用。经过多次调整，最终确定随机重试方法更为直观易懂，且避免了排名系统带来的复杂性和潜在问题。

5.3 日志复制

一旦选举产生领导人，它便开始处理客户端请求，每个请求携带一条被复制状态机执行的指令。领导人将此指令作为新日志条目追加至日志中，并并行发起附加条目RPC给其他服务器复制，日志条目在被安全复制后，领导人将其应用到状态机并将执行结果返回给客户端，即使面对跟随者崩溃、延迟或网络丢包，领导人也会持续重试RPC（尽管已经回复了客户端）直至所有跟随者存储所有日志条目。

日志结构如下图所示，条目按序编号，包含创建时的任期号及待执行指令。日志条目在满足一定条件时变为可提交状态，即安全地应用到状态机中。领导人决定何时提交日志条目，Raft算法保证所有提交条目持久化并最终被执行。日志条目在被复制到多数服务器时即被提交，包括前任领导人创建的条目。领导人追踪最大已提交条目索引，并在附加条目RPC中包含该索引，使跟随者同步应用已提交条目。

Raft的日志机制维持不同服务器日志之间的高层次一致性，简化系统行为并增强可预测性，是安全性的重要组成部分。关键特性是若两日志条目索引和任期号相同，则它们存储相同指令，并且前序条目也相同。。这是因为日志匹配特性，领导人最多在一个任期内特定索引创建日志条目，且日志条目位置固定不变。附加条目RPC包含前一条目的索引和任期号，若跟随者找不到匹配条目则拒绝，确保日志匹配特性。

正常运行时，领导人与跟随者日志一致，但在领导人崩溃后可能出现不一致，如图7所示。领导人通过强制跟随者复制自己的日志解决不一致，覆盖冲突条目。领导人维护nextIndex记录每个跟随者下一个待发送条目索引，初始化为自身最后条目索引+1。当一致性检查失败，领导人就会减小nextIndex直至找到共同点，删除跟随者冲突条目并发送自身条目。成功后，跟随者日志与领导人保持一直。

算法可优化减少拒绝次数，跟随者可返回冲突条目任期号及对应最小索引，领导人据此一次性跳过冲突任期所有条目。但实践中，这种优化可能非必需，因不一致性罕见且涉及条目不多。

通过日志复制机制，领导人无需特殊操作即可恢复一致性，只需执行常规流程，日志在响应一致性检查失败时自动对齐。领导人从不覆盖或删除自身日志，确保一致性。日志复制机制体现了高可用性、快速复制及对慢跟随者的容忍度。

5.4 安全性

在 Raft 算法中，尽管已经描述了领导人的选举和日志的复制过程，但这些机制本身并不足以保证所有状态机按照相同的顺序执行相同的指令。存在一种情况，即一个跟随者在领导人提交了若干日志条目后变得不可用，之后这个跟随者可能被选举为新的领导人，并可能覆盖这些已提交的日志条目，导致不同状态机可能执行不同的指令序列。

为了解决这个问题，Raft 算法在领导选举时增加了限制，确保任何给定任期的领导人都拥有之前任期的所有已提交的日志条目（即领导人完整特性）。这一限制简化了提交规则，并为复制状态机的正确行为提供了证明。

5.4.1 选举限制

在基于领导人的一致性算法中，领导人都必须存储所有已提交的日志条目。Raft 算法通过简单的方法确保新选举的领导人拥有之前任期中所有已提交的日志条目，避免了额外的日志传输机制和复杂性。

Raft 使用投票机制来阻止未包含所有已提交日志条目的候选人赢得选举。候选人必须获得集群中大多数节点的同意，这确保了所有已提交的日志条目至少存在于一个节点上。如果候选人的日志至少和大多数的服务器节点一样新，那么他一定持有了所有已经提交的日志条目。请求投票RPC 实现了这样的限制：RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

Raft通过比较日志中最后一条条目的任期号和索引来判断哪个日志更“新”。

• 如果任期号不同，任期号更大的日志更“新”。
• 如果任期号相同，则条目更多（索引值更大）的日志更“新”。

5.4.2 提交之前任期内的日志条目

领导人在当前任期内创建的日志条目，当被复制到大多数服务器上时，则可认为是可提交的。如果一个领导人在提交日志条目之前崩溃了，未来后续的领导人会继续尝试复制这条日志记录。然而，对于之前任期中的日志条目，即使它们已经被复制到大多数服务器上，也不能简单地通过副本数量来确定它们是否已提交，如图8所示。这是因为在领导人崩溃和重新选举的过程中，可能会出现新的领导人并不包含所有之前任期的日志条目，这可能导致已复制的日志被覆盖。

为了避免这种情况，Raft不会通过副本数目去提交一个之前任期内的日志条目，只有当前任期的日志条目才能通过复制到大多数服务器来提交。一旦当前任期的日志条目被提交，根据日志匹配特性，之前任期的日志条目也会被间接的提交。

Raft 在处理日志时保留了原始的任期号，这虽然增加了提交规则的复杂性，但简化了日志的识别和管理。与其它算法不同，Raft 在复制之前任期日志不需要使用新的任期号，在提交前不用发送冗余的日志条目来重新编号，

5.4.3 安全性论证

在 Raft 算法中，领导人完整性特性是确保一致性的关键。这一特性保证了在任期 T 的领导人提交的日志条目，必须被存储在未来任期的领导人日志中。

设任期U（>T）的领导人U缺失该条目，如下图所示，在U的选举中，至少存在一个节点（如S3）同时持有T任期的日志并投票给U。

• 关键点：此节点在投票前接受T任期已提交日志，且在投票时仍保存该条目。
• 矛盾一：此节点把自己选票投给领导人 U 时，说明领导人 U 的日志必须和投票者自己一样新。但假设U不包含T任期提交的日志。
• 矛盾二：若U最后日志任期大于此节点，则前领导人必含提交日志，由日志匹配特性知U亦应含该日志，产生矛盾。

故所有大于T任期的领导人必定包含T任期中所有已提交日志条目。日志匹配原则确保未来领导人同样包含间接提交的条目。领导人完整性特性支撑状态机安全特性，防止不同日志在相同索引值上被应用。

5.5 追随者和候选人崩溃

• 崩溃影响：崩溃导致后续RPC失败，影响通信和一致性。
• 处理机制：
  • 无限重试：系统通过持续重试RPC来处理这类失败。
  • 重启恢复：当崩溃服务器重启，未完成的RPC能够继续执行至成功。
• RPC幂等性保障：指多次执行相同操作产生的效果等同于一次执行，故重复执行RPC也不会引起不一致或错误状态。

5.6 时间和可用性

Raft 算法的一个核心要求是安全性不应依赖于时间，即系统不应因为事件的快慢而产生错误的结果。然而，系统的可用性，即及时响应客户端的能力，不可避免地依赖于时间因素。特别是在领导人选举过程中，时间要求尤为关键。

关键的时间因素有：

• 广播时间 (Broadcast Time)：服务器向集群成员并行发送RPC并接收响应的平均时间。
• 选举超时时间 (Election Timeout)：跟随者等待领导人心跳的最长时限，过期则发起选举。
• 平均故障间隔时间 (Mean Time Between Failures, MTBF)：服务器两次故障之间的平均时间。

Raft 要求满足以下时间不等式以保证系统正常运行：

$\text{Broadcast Time}\ll \text{Election Timeout}\ll \text{MTBF}$

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。广播时间受存储技术影响，范围约为$[0.5,20]\text{ ms}$，选举超时时间基于广播时间设置，要比广播时间大几个数量级，一般在$[10,500]\text{ ms}$，而MTBF通常数月以上，远大于选举超时时间，满足系统稳定运行需求。

6 集群成员变化

Raft 算法在设计时假设集群配置是固定的，但在实际应用中，集群配置需要动态调整，如替换宕机的机器或改变复制级别。直接更改集群配置存在风险，可能导致同一任期内两个领导人同时存在，因此需要一种安全的配置变更机制。为了确保配置变更的安全性，必须采用两阶段方法。在Raft中，集群切换到一个过渡配置，称为联合共识，结合了新旧配置：

• 日志条目被复制给新旧配置的所有服务器。
• 新旧配置的服务器都可以成为领导人。
• 达成一致（选举和提交）需要分别在新旧配置上获得大多数支持。

联合共识允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，联合共识可以让集群在配置转换的过程中依然响应客户端的请求。配置变更过程如下图所示：

1. 请求接收：领导人接收到从 $C_{\text{old}}$ 到 $C_{\text{new}}$ 的配置变更请求。
2. 联合共识日志条目：领导人创建 $C_{\text{old,new}}$ 配置条目并将其作为日志条目存储和复制。
3. 提交联合共识：一旦 $C_{\text{old,new}}$ 被提交，新旧配置都不能单方面做出决定，只有拥有 $C_{\text{old,new}}$ 日志条目的服务器才能成为领导人。
4. 新配置日志条目：这个时候，领导人创建 $C_{\text{new}}$ 配置条目并复制给集群，最终在 $C_{\text{new}}$ 规则下提交，旧的配置变得无关紧要。

7 日志压缩

Raft 算法通过复制日志来维护一致性，但随着时间的推移，日志会不断增长，占用大量空间并影响性能。为了解决这个问题，Raft 使用快照技术压缩日志，通过存储系统状态至持久化存储，随后丢弃先前日志。

下图展示了快照的基本思想，每个服务器独立创建快照，只包含已提交的日志条目，主要的工作包括将状态机的状态写入快照中。Raft也包含一些少量元数据到快照中：最后索引和任期号。保留这些数据是为了支持一致性检查，允许服务器清除过期日志。

领导人偶尔也需要通过安装快照RPC将快照分块发送给一些落后的追随者，追随者收到快照后，他必须自己决定对于已经存在的日志该如何处理，一般来说是覆盖冲突日志，保留后续未冲突日志。

在快照时，有两个性能相关的因素需要考虑：

• 创建时机：服务器需要决定何时创建快照，以避免频繁写入或存储空间耗尽。Raft 的策略是当日志大小达到一个阈值之后，就开始快照。
• 写入时间：写入快照可能需要显著时间，为了不影响正常的操作，应通过写时复制技术避免影响正常操作。

8 客户端交互

Raft中的客户端发送所有请求给领导人。客户端初始化时随机选择服务器，非领导人服务器会拒绝客户端请求并提供最近接收到的领导人信息。如果领导人崩溃后，客户端请求超时，重启随机选择过程直至找到新领导人。

Raft目标是要实现线性化语义，由于Raft是可能同时执行同一条命令多次的，为了解决这个问题，客户端为每条指令分配唯一序列号，状态机跟踪每个客户端的最新序列号和相应响应。如果接收到的指令序列号已经被执行，状态机直接返回结果而不重新执行。

只读操作可以不写入日志直接处理。但不记录日志可能导致返回脏数据，即领导人在不知情的情况下被新领导人取代。线性化的读操作必须不能返回脏数据，Raft 需要使用两个额外的措施在不使用日志的情况下保证这一点。

1. 最新提交日志信息：领导人需要知道任期内所有被提交的日志条目。Raft 通过让领导人在任期开始时提交一个空白日志条目来实现。

2. 领导人状态检查：在处理只读请求前，领导人必须检查自己是否已被废黜。Raft 通过让领导人在响应只读请求前与集群大多数节点交换心跳信息来处理这个问题。

9 总结

Raft 是一种用于管理复制日志的一致性算法，旨在解决分布式系统中的一致性问题。它通过领导人选举、日志复制和安全性保证来实现系统的高可用性和一致性。

Raft 的五大保证：

1. 选举安全性：在任一给定任期内，最多只能有一个领导人被选举出来。

2. 领导人只追加：领导人不会覆盖或删除其日志中的条目；它只追加新的条目。

3. 日志匹配：如果两个日志在相同索引和任期号处含有相同的条目，则在该索引之前的所有条目都是相同的。

4. 领导人完整性：如果一个日志条目在给定任期被提交，那么该条目将出现在所有更高编号任期的领导人的日志中。

5. 状态机安全性：如果一个服务器将某个索引的日志条目应用到其状态机中，其他服务器不会对该索引应用不同的日志条目。