本文将详细介绍Raft共识算法。

论文参考：《In Search of an Understandable Consensus Algorithm》

Raft是一种用于管理复制日志的共识算法，其设计目标是提高可理解性。Raft通过分解共识的关键元素，如领导者选举、日志复制和安全性，来增强可理解性。它采用强领导者机制，确保日志条目仅从领导者流向其他服务器，从而简化了复制日志的管理。领导者选举使用随机定时器，快速解决冲突。Raft还引入了一种新的集群成员变更机制，利用重叠多数来保证安全性，使得在配置变化期间集群能够正常运行。总的来说，Raft提供了一个简单易懂且有效的共识算法基础，适合在生产环境中应用。

状态机复制

复制状态机是分布式系统中解决容错问题的重要方法。在这种方法中，多个服务器上的状态机计算相同的状态副本，即使部分服务器发生故障，系统仍能继续运行。许多大规模系统如GFS、HDFS和RAMCloud都使用复制状态机来管理领导者选举和存储配置信息。

复制状态机通常通过复制日志来实现。每个服务器存储包含一系列命令的日志，这些命令按顺序被状态机执行。由于所有日志包含相同顺序的相同命令，且状态机是确定性的，因此每个状态机都会计算出相同的状态和输出序列。共识算法的任务就是保持复制日志的一致性。复制状态机的实现如下图所示：

复制状态机环境下的用户请求执行流程如下：

客户端向服务器的共识模块发送命令请求。
共识模块将接收到的命令添加到日志中，并与其他服务器的共识模块通信以确保日志复制的一致性。
一旦命令被正确复制，服务器的状态机按照日志顺序处理这些命令，更新状态（如图中显示的x、y、z变量值）。
最后，处理结果返回给客户端。

整个流程确保了所有服务器上的状态机都能按相同顺序执行相同的命令序列，从而维持系统状态的一致性。（图中的多层服务器表示这是一个分布式系统，每个服务器都包含相同的组件结构）。

生产环境中的共识算法具有以下特性：

在所有非拜占庭条件下（包括网络延迟、分区和数据包丢失、重复和重排序）确保安全性；
只要大多数服务器正常运行并能相互通信，系统就能保持完全功能；
不依赖时序来确保日志一致性；
在常见情况下，只需集群中大多数节点响应单轮远程过程调用（RPC），命令就能完成执行。

Raft算法

Raft设计初衷中最重要的一点便是它的可理解性（作者不希望Raft像Paxos那样难以理解，同时存在算法描述和实现不一致的问题）。为了提高算法的可理解性，主要引入了以下两点改进：

分解问题：Raft将leader选取、日志复制、安全性和关系专业分为独立的部分处理，分解问题的复杂度。
缩小状态空间：通过减少状态的数量缩小状态空间，使系统更加连贯，并尽可能的消除不确定性。

Raft算法的实现首先会选举一个leader，这个leader负责从client哪里接收日志条目，并复制到其他的server。鉴于使用了leader，Raft把共识问题分为了三个小问题分别是：

leader的选举：当当前leader损坏时，必须重新选取leader
日志的复制：leader负责将从client哪里接收的日志条目通过集群复制到其他的server
安全性：Raft保证在任何时候，下图中的安全性均适用：

Raft算法全貌如下：

Raft算法基础

服务器状态

Raft服务器共有三种状态：leader（领导者）、follower（追随者）和candidate（候选人），在通常情况下，只有一个leader，它负责处理所有的client请求，其它都是follower。当一个follower收不到来自leader的日志条目时，他会发起投票，并成为一个candidate。一个leader一般会一直运行知道它失败。服务器之间的状态转换图如下：

任期（terms）

Raft将时间划分为任意长度的任期（term），如下图，每个任期以选举开始。在选举中，一个或多个candidate尝试成为leader。如果candidate赢得选举，则在该任期内担任leader；若选举出现平票，则该任期无leader，随后进入新任期并重新选举。Raft保证每个任期最多只有一个leader。各服务器可能在不同时间观察到任期的变化，有时甚至可能错过整个任期。任期作为逻辑时钟，用于检测过时信息（如失效的leader）。每个服务器存储当前的任期号，并在通信时交换。如果发现自己的任期号落后，会更新为较大的值；candidate或leader若发现自己任期过时，会立即退回到follower状态。对于带有过时任期号的请求，服务器会拒绝处理。

Raft通过远程过程调用（RPC）进行通信，核心算法使用两种RPC：candidate在选举期间发起的RequestVote RPC，以及leader用于日志复制和发送心跳的AppendEntries RPC。

leader选举

Raft通过心跳机制触发leader选举。当服务器启动时，初始状态为follower，只要收到来自leader或candidate的有效RPC，便保持follower状态。leader通过定期发送心跳消息（不包含日志条目的AppendEntries RPC）维持其权威性。如果follower在选举超时时间内未收到leader的RPC，则它认为当前没有有效的leader，并发起选举。

选举开始时，follower增加当前任期号并转为candidate状态，同时投自己一票后向集群中其他服务器并行发送RequestVote RPC。candidate会持续等待投票结果，直到以下三种情况之一发生：

赢得选举（成功）：若candidate获得集群中多数服务器的投票，则赢得选举并成为leader，然后向其他服务器发送心跳以确立权威，来防止新一轮选举。
另一个服务器成为leader（失败）：如果candidate在等待投票期间收到来自另一个leader的AppendEntries RPC，且该RPC的任期号不小于自身的当前任期号，则承认对方为合法leader并退回到follower状态；否则（自己的任期号要大）的话，拒绝该RPC并继续保持candidate状态。
没有获胜者（平票）：若多个follower同时成为candidate且票数近乎平分，导致没有候选人获得多数票，则每个candidate会超时后增加任期号并重新发起选举。

为减少平分投票的发生，Raft中的每个server都会设置一个随机化的选举超时时间（如150-300ms），这使得大多数情况下只有一个服务器超时并发送RequestVote RPC，他大概率会成功当选leader。即使出现平分投票的情况，随机化超时机制也能快速解决问题，每个服务器会设定随机的时间，并等待这个时间后再次成为candidate。

日志复制

领导者被选举后，会负责处理客户端请求。每个请求都包含需要在复制服务器的状态机上执行的命令。领导者会将命令追加到自己的日志中，并通过AppendEntries RPC并行通知其他服务器复制该条目。一旦确认该条目被安全地复制到大多数服务器上，领导者就会将该命令应用到自己的状态机，并将执行结果返回给客户端。

日志的组织结构非常严谨，每个日志条目都存储了状态机命令以及领导者接收到该条目时的任期编号。这些任期编号用于检测日志之间的不一致性，同时确保日志具有某些重要特性。每个日志条目还包含一个整数索引，用于标识其在日志中的位置。日志结构如下图所示：

只要领导者将一条日志复制到大多数的服务器上，那么这条日志就会被提交，如图中的日志7，之前的所有日志都会是被提交的状态。

Raft通过以下两个特性来保证日志的一致性：

如果不同日志中的两个条目具有相同的索引和任期，则它们存储相同的命令
如果不同日志中的两个条目具有相同的索引和任期，则之前的所有日志条目都相同

当出现领导者崩溃时，可能会导致日志不一致的情况。如下图所示：

图中的每个框都表示一条日志，框中的数字代表任期（term）， follower可能缺少条目 (a–b)，可能有额外的未提交条目 (c–d)，或两者都有 (e–f)。例如，如果f服务器是第2任期的领导者，向其日志添加了多个条目，然后在提交其中任何条目之前崩溃，则可能会出现场景 (f)；它很快重新启动，成为第3任期的领导者，并在其日志中添加了更多条目；在提交第2任期或第3任期中的任何条目之前，服务器再次崩溃并在后面的几个任期内保持关闭状态。

新的领导者会通过强制跟随者复制自己的日志来解决这种不一致。具体来说，领导者会找到自己与跟随者日志中最新的共同条目，删除跟随者在该点之后的所有条目，然后将自己在该点之后的所有条目发送给跟随者。为了实现这个机制，领导者会为每个跟随者维护一个nextIndex值，表示下一个要发送给该跟随者的日志条目的索引。当新领导者上任时，它会将所有nextIndex初始化为自己最后一个日志条目的下一个位置，并发送AppendEntries RPC。如果发现跟随者的日志与自己不一致，领导者会通过递减nextIndex并重发RPC的方式，最终找到两者的日志匹配点。

这种日志复制机制具有良好的容错性和性能特征。只要集群中的多数服务器正常运行，系统就能继续工作。在正常情况下，新的日志条目只需要一轮RPC就能复制到集群的多数节点上。而且，单个慢速跟随者不会影响整体性能。领导者永远不会覆盖或删除自己的日志条目，这保证了系统的安全性。通过这种设计，Raft能够在保证安全性的同时提供良好的性能，使其成为一个实用的分布式共识算法。即使在网络不稳定或服务器故障的情况下，系统也能保持正确运行并最终达成一致。

安全性

前面介绍了Raft算法如何选举领导者和复制日志条目。然而，这些机制还不足以确保每个状态机都能按照完全相同的顺序执行相同的命令。这是因为可能会出现一些特殊情况，导致系统的一致性被破坏。

举个例子，假设一个跟随者在领导者提交多个日志条目的时候处于离线状态。如果这个跟随者后来被选举为新的领导者，它可能会用新的条目覆盖那些已经提交的条目。这就会导致不同的状态机执行了不同的命令序列，破坏了系统的一致性。为了解决这个问题，Raft算法对哪些服务器可以被选举为领导者增加了限制条件。这个限制确保了在任何给定任期内，被选举的领导者都必须包含之前任期中所有已提交的条目。这就是所谓的领导者完整性特性。有了这个选举限制，Raft算法进一步完善了提交规则，使其更加精确。

选举限制

Raft通过选举限制确保新领导者从一开始就包含之前任期的所有已提交条目。这意味着日志条目只能从领导者单向流向跟随者，领导者永远不会覆盖自己日志中已存在的条目。

为了实现这一点，Raft在投票过程中加入了限制条件。候选人必须联系集群中的多数节点才能当选，这意味着每个已提交的条目必定存在于这些服务器中的至少一个。如果候选人的日志至少与多数派中的任何其他日志一样新，那么它就包含了所有已提交的条目。在RequestVote RPC中实现了这个限制：请求中包含候选人的日志信息，如果投票者发现自己的日志比候选人的更新，就会拒绝投票。Raft通过比较日志最后条目的索引和任期来判断两个日志的新旧程度：

如果最后条目的任期不同，任期更大的日志更新
如果最后条目的任期相同，则更长的日志更新

这种机制确保了系统的安全性，防止了已提交条目被覆盖的问题。

提交以前任期的日志条目

在Raft中，领导者一旦确认其当前任期的日志条目在大多数服务器上存储，就可以认为该条目已提交。这意味着只要有超过一半的服务器成功接收并存储了这个条目，领导者就可以安全地将其视为已提交，并将其应用到状态机中。然而，对于来自之前任期的日志条目，仅仅因为它们在大多数服务器上存储，领导者并不能立即得出这些条目已提交的结论。比如下图所示的情况：
旧日志条目

步骤 (a)：S1作为领导者，部分复制了索引为2的日志条目。
步骤 (b)：S1崩溃，S5在第3任期被选为领导者，获得来自S3、S4及自身的投票，并收到了不同的索引为2的日志条目，此时S5崩溃。
步骤 (c)：S5崩溃后，S1重新启动并被选为领导者，继续进行日志复制。此时，第2任期的日志条目已在大多数服务器上复制，但尚未提交。
步骤 (d)：如果S1再次崩溃，S5可能会被选为领导者（获得来自S2、S3和S4的投票），并用其第3任期的条目覆盖之前的条目
步骤 (e)：如果S1在崩溃之前，已将把当前任期的条目复制到大多数服务器上，则该条目被视为已提交（此时S5无法赢得选举）。此时，所有之前的日志条目也被视为已提交。

图中展示了一个旧的日志条目在大多数服务器上存储，但仍然可能被未来的新领导者覆盖。这种情况可能导致不同的状态机执行不同的命令序列，从而破坏系统的一致性。

为了避免上述问题，Raft不通过计数副本来提交之前任期的日志条目。只有当前任期的日志条目在确认复制后才会被提交。一旦当前任期的条目被提交，根据日志匹配特性，所有之前的条目也会间接地被认为是已提交。这种设计确保了即使旧条目在多数服务器上存在，也不会被错误地认为是已提交。Raft引入了额外复杂性，因为它在复制过程中保留了日志条目的原始任期编号。在其他共识算法中，当新领导者重新复制之前“任期”的条目时，通常会使用新的“任期编号”。而Raft的方法则使得对日志条目的推理变得更简单，因为这些条目在时间和不同日志中保持相同的任期编号。此外，与其他算法相比，Raft的新领导者发送来自之前任期的日志条目的数量更少。其他算法需要发送冗余的日志条目以重新编号，然后才能进行提交，而Raft则避免了这种冗余，从而提高了效率。

leader完整性的成立

原文中通过一个反证法证明了leader的完整性，同时鉴于leader完整性的成立，状态机的完整性也得到了证明。想了解证明过程可以去看看原文，证明过程也比较简单明了。

leader完整性：领导者完整性特性确保在任期T的领导者（leaderT）提交的日志条目，未来任期的任何领导者（例如任期U的leaderU）都必须包含这些已提交的条目。

所以在上面那张图中的步骤（d）是不会发生的，也就是是说以前任期复制但未提交的条目不会被覆盖。

状态机完整性：

日志一致：当一个服务器将日志条目应用到其状态机时，该服务器的日志必须与领导者的日志在该条目之前完全相同，并且该条目必须是已提交的。这意味着该条目已经被大多数服务器接受并存储。

最低任期的考虑：考虑任何服务器在某个给定日志索引上应用日志条目的最低任期。根据领导者完整性特性，所有更高任期的领导者都会存储相同的日志条目。因此，在后续任期中应用该索引的服务器也会应用相同的值。

有序应用：Raft要求所有服务器按照日志索引顺序应用条目。这意味着所有服务器都将以相同的顺序将相同的日志条目应用到其状态机中。

综上，通过leader一致性，Raft确保了状态机安全性特性，即所有服务器在相同的日志索引上应用相同的日志条目，从而保证了系统的一致性和可靠性。

follower和candidate的失败

当一个跟随者或候选者崩溃时，未来发送给它们的RequestVote和AppendEntries RPC将会失败。Raft通过无限重试来应对这些失败；如果崩溃的服务器重新启动，这些RPC请求将成功完成。如果服务器在完成RPC请求后崩溃但尚未响应，重新启动后它会再次接收到相同的RPC请求。Raft的RPC设计为幂等性，这意味着重复接收相同请求不会造成任何问题。例如，当一个跟随者收到包含已存在日志条目的AppendEntries请求时，它会忽略新请求中的这些条目。

时序和可用性

领导者选举是Raft中对时间要求最为关键的方面。Raft能够选举并维持稳定的领导者，只要满足以下时间要求：

broadcastTime << electionTimeout<< MTBF

其中，broadcastTime是服务器并行发送RPC并接收响应的平均时间；electionTimeout是选举超时；MTBF是单个服务器的平均故障间隔。广播时间应比选举超时小一个数量级，以便领导者能够可靠地发送心跳消息，防止跟随者启动选举。同时，这种不等式也降低了出现平票的可能性。选举超时应比MTBF小几个数量级，以确保系统持续进展。在通常情况下，broadcastTime可能在0.5毫秒到20毫秒之间，因此，electionTimeout很可能在10毫秒到500毫秒之间。典型服务器的MTBF通常为几个月或更长。所以这个要求很好满足。

集群重配

在一些情况下，我们需要重新配置整个集群，如有新的服务器加入，这是停止服务等待配置完成后再启动服务会导致服务的停止，从而影响真个系统的可用性。所以，Raft采用了自动配置的方法。

在集群配置变更的过程中，Raft共识算法采用了两阶段的方法以确保系统的安全性，避免在过渡期间出现两个领导者被选出的情况。直接从旧配置切换到新配置是不安全的，因为无法实现所有服务器的原子切换，这可能导致集群分裂成两个独立的多数派。如下图：

如图所示，在新配置和旧配置交织的阶段可能会出现两个leader同时领导集群的情况。

因此，Raft引入了一个过渡状态，称为联合共识（joint consensus），以确保在变更过程中集群仍能处理客户端请求。集群重配流程图如下：

图中展示了更改配置的时间线，具体流程如下：

创建配置条目：领导者首先在日志中创建C(old,new)配置条目，但此时尚未提交。
提交联合共识：领导者将C(old,new)条目提交给C(old)和C(new)的多数派。这意味着在这一阶段，旧配置（C(old)）和新配置（C(new)）共同参与决策。
创建新配置条目：一旦C(old,new)被提交，领导者接着创建C(new)条目，并将其提交给C(new)的多数派。

整个过程中，C(old)和C(new)没有任何时刻可以独立做出决策，从而确保了系统的安全性和一致性。

联合共识的工作机制如下：

日志条目存储与复制：当领导者接收到变更配置的请求时，会将联合共识的配置（包括旧配置和新配置）存储为日志条目并进行复制。所有服务器在日志中记录最新配置，并根据该配置进行决策。
决策规则：在联合共识阶段，任何来自旧配置或新配置的服务器都可以成为领导者。对于选举和日志条目的提交，需要分别获得旧配置和新配置的多数同意。这意味着在这一阶段，集群可以继续正常服务，而不会因为配置变更而中断。
安全性保障：在提交新配置日志条目之前，领导者会确保不会允许任何一方单方面做出决策，从而保证了系统的安全性。一旦联合共识被提交，旧配置和新配置都需要相互批准才能进行决策。

为了进一步优化集群的可用性，Raft还考虑了以下几个问题：

新服务器加入：新服务器在加入集群时可能没有存储任何日志条目，这可能导致它们需要较长时间才能赶上其他服务器。为了解决这个问题，新服务器会作为非投票成员加入集群，领导者会将日志条目复制给它们，但这些新服务器不会被计算在多数派中。一旦它们赶上其他服务器，就可以开始一次配置变更，让他们真正的加入集群，并拥有投票权。
领导者不在新配置中：如果当前领导者不在新的配置中，它会在提交新配置日志条目后降级为跟随者状态。在此期间，领导者仍然负责复制日志条目，但不再计算自己在多数派中，这样可以确保新配置能够独立运作。
移除服务器的干扰：被移除的服务器可能会对集群造成干扰，因为它们无法接收到心跳消息，会超时并发起新的选举。为了防止这种情况，Raft规定服务器在认为当前存在领导者时（没有达到最小的选举超时时间），会忽略来自这些移除服务器的投票请求。这种机制确保了只要当前领导者能够向集群发送心跳信号，就不会被较大的任期号所取代，从而保持集群的稳定性和可用性。

日志压缩——快照

Raft的日志在正常操作中会不断增长，以记录更多的客户端请求，但日志不能无限制地增长。随着日志的增加，它占用的空间和重放所需的时间也会增加，这可能导致可用性问题。因此，需要一种机制来丢弃日志中积累的过时信息。

快照是最简单的压缩方法。在快照过程中，当前系统状态被写入稳定存储中，然后丢弃到该点为止的整个日志。Raft中的快照机制允许每个服务器独立地进行快照，只覆盖其日志中已提交的条目。

Raft的日志结构如下图：

图中日志经存储已提交条目点之前的最终状态，图中快照建立时的日志index为5，所以最后的状态为x <- 0, y <- 9，这样根据日志，系统就可以恢复到index为6前的最终状态。日志中还包含一些其它的信息例如：最后一个日志条目的索引和其任期，保留这些是为了支持快照后第一个日志条目的 AppendEntries 一致性检查。同时，日志中还需要包含截止当前的最新配置，来支持集群的重配。

领导者需要向滞后的跟随者发送快照，尤其是在领导者已经丢弃了需要发送给跟随者的下一个日志条目时。领导者使用新的RPC（InstallSnapshot）将快照发送给滞后的跟随者。InstallSnapshot RPC如下图所示：

跟随者在接收到快照后，需要决定如何处理现有的日志条目。如果快照包含新的信息，通常会丢弃整个日志；如果快照描述的是其日志的前缀，则仅删除被快照覆盖的条目，保留后续条目。

在进行快照时，服务器需要决定何时进行快照。如果频繁快照，会浪费磁盘带宽和能量；如果不够频繁，则可能耗尽存储容量并增加重启时重放日志所需的时间。一种简单策略是当日志达到固定字节大小时进行快照。此外，写入快照可能需要很长时间，因此使用写时复制技术（copy-on-write）（例如Linux中的fork便采用了写时复制技术）以便可以接受新的更新而不影响正在写入的快照。

客户端同Raft的交互

客户端如何与集群进行交互，特别是如何找到集群的领导者以及如何支持线性化语义？

客户端寻找领导者

客户端将所有请求发送给领导者。当客户端启动时，会随机连接到一个服务器。如果该服务器不是领导者，它会拒绝请求并提供最新领导者的信息（AppendEntries RPC中会包含leader的RPC）。如果领导者崩溃，客户端请求会超时，随后客户端会尝试与其他随机选择的服务器重新连接。

线性化语义

Raft旨在实现线性化语义，即每个操作看起来在某个时间点瞬时执行且只执行一次。然而，由于领导者可能崩溃，导致命令被重复执行（如在leader回复客户端时崩溃，那么客户端会重新请求，已经被执行过一次的日志条目会被再执行一遍，并将结果返回给客户端），因此需要为每个命令分配唯一的序列号。状态机会跟踪每个客户端处理的最新序列号及其响应。如果接收到的命令序列号已被处理，则立即返回响应，而不重新执行请求（这是一个只读的请求）。

对于只读操作，Raft可以在不写入日志的情况下处理，但可能会返回过时数据（leader更新）。为了保证线性化读取不返回过时数据，Raft采取了两项额外措施：首先，领导者必须了解哪些条目已被提交，Raft通过在领导者任期开始时提交一个空的无操作条目来解决此问题；其次，领导者在处理只读请求之前必须检查自己是否被取代（新leader当选，则信息过时），以确保信息不陈旧，这通过与大多数集群成员交换心跳消息来实现。通过这些机制，Raft能够有效地管理客户端请求并保持一致性。

总结

在本文中，我们深入探讨了Raft共识算法的核心概念及其在分布式系统中的重要性。Raft通过明确的领导者选举、日志复制和安全性机制，提供了一种易于理解且高效的方式来实现一致性。总而言之，Raft不仅是一种强大的共识算法，它还通过清晰的设计和实现，使得开发者能够轻松理解和应用这一技术。在现代分布式系统中，Raft为数据一致性和可靠性提供了坚实的基础，成为许多开源项目和商业应用的重要组成部分。随着对分布式计算需求的不断增长，Raft无疑将在未来继续发挥关键作用。