前言
在正式开始介绍 Raft 协议之间，我们有必要简单介绍一下其相关概念。在分布式系统中，一致性是比较常见的概念，所谓一致性指的是集群中的多个节点在状态上达成一致。在程序和操作系统不会崩溃、硬件不会损坏、服务器不会掉电、网络绝对可靠且没有延迟的理想情况下，我们可以将集群中的多个节点看作一个整体，此时要保证它们的一致性并不困难。
但是在现实的场景中，很难保证上述极端的条件全部满足，节点之间的一致性也就很难保证，这样就需要 Paxos、 Raft 等一致性协议。一致性协议可以保证在集群中大部分节点可用的情况下，集群依然可以工作并给出一个正确的结果，从而保证依赖于该集群的其他服务不受影响。这里的“大部分节点可用”指的是集群中超过半数以上的节点可用，例如，集群中共有 5个节点，此时其中有 2 个节点出现故障宕机，剩余的可用节点数为 3，此时，集群中大多数节点处于可用的状态，从外部来看集群依然是可用的。
常见的一致性算法有 Paxos、 Raft 等，Paxos 协议是 Leslie Lamport 于1990年提出的一种基于消息传递的、具有高度容错特性的一致性算法，Paxos 算法解决的主要问题是分布式系统内如何就某个值达成一致。在相当长的一段时间内，Paxos 算法几乎成为一致性算法的代名词，但是 Paxos 有两个明显的缺点：第一个也是最明显的缺点就是 Paxos 算法难以理解，Paxos 算法的论文本身就比较晦涩难懂，要完全理解 Paxos 协议需要付出较大的努力，很多经验丰富的开发者在看完 Paxos 论文之后，无法将其有效地应用到具体工程实践中，这明显增加了工程化的门槛，也正因如此，才出现了几次用更简单的术语来解释 Paxos 的尝试。Paxos 算法的第二个缺点就是它没有提供构建现实系统的良好基础，也有很多工程化 Paxos 算法的尝试，但是它们对 Paxos 算法本身做了比较大的改动，彼此之间的实现差距都比较大，实现的功能和目的都有所不同，同时与Paxos算法的描述有很多出入。例如，著名 Chubby，它实现了一个类Paxos的算法，但其中很多细节并未被明确。本章并不打算详细介绍 Paxos 协议的相关内容，如果读者对Paxos感兴趣，则可以参考Lamport发表的三篇论文：《The Part-Time Parliament》、《Paxos made simple》、《Fast Paxos》。
正因为上述的缺点，导致 Paxos 协议处于一种比较尴尬的境地：在理论上 Paxos 算法是正确可行的，但是实际的工程中很少有与 Paxos 算法类似的实践。很多工程实践（包括上面提到的Chubby）都是从 Paxos 协议的研究开始的，然后在实践的过程中发现很多难题，之后通过各种技巧和手段进行改进，最后开发出一种与 Paxos 明显不同的东西，这就导致最终开发出来的程序建立在一个未经证明的协议之上。也正因为如此，人们开始寻找新的一致性算法，寻找的结果也就是本章介绍的重点 Raft 协议。
Raft 算法是一种用于管理复制日志的一致性算法，其功能与 Paxos 算法相同类似，但其算法结构和 Paxos 算法不同，在设计 Raft 算法时设计者就将易于理解作为其目标之一，这使得 Raft 算法更易于构建实际的系统，大幅度减少了工程化的工作量，也方便开发者此基础上进行扩展。虽然 Raft 论文已经很好理解，但是本章并不打算直接翻译 Raft 论文，而是尽可能通过示例介绍 Raft 协议如何处理各种不同的场景，并且重点介绍 Raft 协议中的 Leader 选举和日志复制等方面的内容。
Leader 选举
Raft 协议的工作模式是一个 Leader 节点和多个 Follower 节点的模式，也就是常说的 Leader - Follower 模式。在 Raft 协议中，每个节点都维护了一个状态机，该状态机有三种状态，分别是 Leader 状态、 Follower 状态和 Candidate 状态，在任意时刻，集群中的任意一个节点都处于这三个状态之一。各个状态和转换条件如图2-1所示。
图2-1
在多数情况下，集群中有一个 Leader 节点，其他节点都处于 Follower 状态，下面简单介绍一下每个状态的节点负责的主要工作。
- Leader 节点负责处理所有客户端的请求，当接收到客户端的写入请求时， Leader 节点会在本地追加一条相应的日志，然后将其封装成消息发送到集群中其他的 Follower 节点。当 Follower 节点收到该消息时会对其进行响应。如果集群中多数（超过半数）节点都已收到该请求对应的日志记录时，则 Leader 节点认为该条日志记录已提交（committed），可以向客户端返回响应。Leader 还会处理客户端的只读请求，其中涉及一个简单的优化，后面介绍具体实现时，再进行详细介绍。Leader 节点的另一项工作是定期向集群中的 Follower 节点发送心跳消息，这主要是为了防止集群中的其他 Follower 节点的选举计时器超时而触发新一轮选举。
- Follower 节点不会发送任何请求，它们只是简单地响应来自 Leader 或者 Candidate 的请求； Follower 节点也不处理 Client 的请求，而是将请求重定向给集群的 Leader 节点进行处理。
- Candidate 节点是由 Follower 节点转换而来的，当 Follower 节点长时间没有收到 Leader 节点发送的心跳消息时，则该节点的选举计时器就会过期，同时会将自身状态转换成 Candidate ，发起新一轮选举。选举的具体过程在下面详细描述。
了解了 Raft 协 议中节点的三种状态及各个状态下节点的主要行为之后，我们通过一个示例介绍 Raft 协议中 Leader 选举的大致流程。为了方便描述，我们假设当前集群中有三个节点（A、B、C），如图2-2所示。
图2-2
在 Raft 协议中有两个时间控制 Leader 选举发生，其中一个是选举超时时间（election timeout），每个 Follower 节点在接收不到 Leader 节点的心跳消息之后，并不会立即发起新一轮选举，而是需要等待一段时间之后才切换成 Candidate 状态发起新一轮选举。这段等待时长就是这里所说的 election timeout（后面介绍etcd的具体实现时会提到， Follower 节点等待的时长并不完全等于该配置）。之所以这样设计，主要是 Leader 节点发送的心跳消息可能因为瞬间的网络延迟或程序瞬间的卡顿而迟到（或是丢失），因此就触发新一轮选举是没有必要的。election timeout一般设置为 150ms～300ms 之间的随机数。另一个超时时间是心跳超时时间（heartbeat timeout），也就是 Leader 节点向集群中其他 Follower 节点发送心跳消息的时间间隔。
集群启动时 Leader 选取
当集群初始化时，所有节点都处于 Follower 的状态，此时的集群中没有 Leader 节点。当 Follower 节点一段时间（选举计时器超时）内收不到 Leader 节点的心跳消息，则认为 Leader 节点出现故障导致其任期（Term）过期， Follower 节点会转换成 Candidate 状态，发起新一轮的选举。所谓 “任期（Term）”，实际上就是一个全局的、连续递增的整数，在 Raft 协议中每进行一次选举，任期（Term）加一，在每个节点中都会记录当前的任期值（currentTerm）。每一个任期都是从一次选举开始的，在选举时，会出现一个或者多个 Candidate 节点尝试成为 Leader 节点，如果其中一个 Candidate 节点赢得选举，则该节点就会切换为 Leader 状态并成为该任期的 Leader 节点，直到该任期结束。
回到前面的示例中，此时节点 A 由于长时间未收到 Leader 的心跳消息，就会切换成为 Candidate 状态并发起选举（节点A的选举计时器（election timer）已被重置）。在选举过程中，节点A首先会将自己的选票投给自己，并会向集群中其他节点发送选举请求（Request Vote）以获取其选票，如图2-3（1）所示；此时的节点B和节点C还都是处于Term=0的任期之中，且都是 Follower 状态，均未投出Term=1任期中的选票，所以节点B和节点C在接收到节点A的选举请求后会将选票投给节点A，另外，节点B、C在收到节点A的选举请求的同时会将选举定时器重置，这是为了防止一个任期中同时出现多个 Candidate 节点，导致选举失败，如图2-3（2）所示。注意，节点B和节点C也会递增自身记录的Term值。
图2-3
在节点 A 收到节点 B、C 的投票之后，其收到了集群中超过半数的选票，所以在 Term=1这个任期中，该集群的 Leader 节点就是节点A，其他节点将切换成 Follower 状态，如图2-4所示。另外需要读者了解的是，集群中的节点除了记录当期任期号（currentTerm），还会记录在该任期中当前节点的投票结果（VoteFor）。
图2-4
继续前面的示例，成为Term=1任期的 Leader 节点之后，节点A会定期向集群中的其他节点发送心跳消息，如图2-5（1）所示，这样就可以防止节点B和节点C中的选举计时器（election timer）超时而触发新一轮的选举；当节点B和节点C（ Follower ）收到节点A的心跳消息之后会重置选举计时器，如图2-5（2）所示，由此可见，心跳超时时间（heartbeat timeout）需要远远小于选举超时时间（election timeout）。
图2-5
到这里读者可能会问，如果有两个或两个以上节点的选举计时器同时过期，则这些节点会同时由 Follower 状态切换成 Candidate 状态，然后同时触发新一轮选举，在该轮选举中，每个 Candidate 节点获取的选票都不到半数，无法选举出 Leader 节点，那么 Raft 协议会如何处理呢？这种情况确实存在，假设集群中有4个节点，其中节点A和节点B的选举计时器同时到期，切换到 Candidate 状态并向集群中其他节点发出选举请求，如图2-6（1）所示。
这里假设节点A发出的选举请求先抵达节点C，节点B发出的选举请求先抵达节点D，如图2-6（2）所示，节点A和节点B除了得到自身的选票之外，还分别得到了节点C和节点D投出的选票，得票数都是2，都没有超过半数。在这种情况下，Term=4这个任期会以选举失败结束，随着时间的流逝，当任意节点的选举计时器到期之后，会再次发起新一轮的选举。前面提到过 election timeout 是在一个时间区间内取的随机数，所以在配置合理的时候，像上述情况多次出现的概率并不大。
图2-6
继续上面的示例，这里假设节点A的选举计时器再次到期（此次节点B、C、D 的选举计时器并未到期），它会切换成 Candidate 状态并发起新一轮选举（Term=5），如图2-7（1）所示，其中节点B虽然处于 Candidate 状态，但是接收到Term值比自身记录的Term值大的请求时，节点会切换成 Follower 状态并更新自身记录的Term值，所以该示例中的节点B也会将选票投给节点A，如图2-7（2）所示。
图2-7
在获取集群中半数以上的选票并成为新任期（Term=5）的 Leader 之后，节点 A 会定期向集群中其他节点发送心跳消息；当集群中其他节点收到 Leader 节点的心跳消息的时候，会重置选举定时器（当 Follower 节点每次收到心跳消息时，都会重置选举定时器），如图2-8所示。
图2-8
Lerder 节点宕机后重新选取
介绍完集群启动时的 Leader 选举流程之后，下面分析 Leader 节点宕机之后重新选举的场景。继续上述4节点集群的示例，在系统运行一段时间后，集群当前的 Leader 节点（A）因为故障而宕机，此时将不再有心跳消息发送到集群的其他 Follower 节点（节点B、C、D），一段时间后，会有一个 Follower 节点的选举计时器最先超时，这里假设节点D的选举计时器最先超时，然后它将切换为 Candidate 状态并发起新一轮选举，如图2-9（1）所示。
图2-9
当节点B和节点C收到节点D的选举请求后，会将其选票投给节点D，由于节点A已经宕机，没有参加此次选举，也就无法进行投票，但是在此轮选举中，节点D依然获得了半数以上的选票，故成为新任期（Term=6）的 Leader 节点，并开始向其他 Follower 节点发送心跳消息，如图2-10所示。
图2-10
当节点A恢复之后，会收到节点D发来的心跳消息，该消息中携带的任期号（Term=6）大于节点A当前记录的任期号（Term=5），所以节点A会切换成 Follower 状态。在 Raft 协议中，当某个节点接收到的消息所携带的任期号大于当前节点本身记录的任期号，那么该节点会更新自身记录的任期号，同时会切换为 Follower 状态并重置选举计时器，这是 Raft 算法中所有节点都要遵循的一条准则。
最后请读者考虑一个场景：如果集群中选出的 Leader 节点频繁崩溃或是其他原因导致选举频繁发生，这会使整个集群中没有一个稳定的 Leader 节点，这样客户端无法与集群中的 Leader 节点正常交互，也就会导致整个集群无法正常工作。
Leader 选举是 Raft 算法中对时间要求较为严格的一个点，一般要求整个集群中的时间满足如下不等式：
广播时间 ＜＜ 选举超时时间 ＜＜ 平均故障间隔时间
在上述不等式中，广播时间指的是从一个节点发送心跳消息到集群中的其他节点并接收响应的平均时间；平均故障间隔时间就是对于一个节点而言，两次故障之间的平均时间。为了保证整个 Raft 集群可用，广播时间必须比选举超时时间小一个数量级，这样 Leader 节点才能够发送稳定的心跳消息来重置其他 Follower 节点的选举计时器，从而防止它们切换成 Candidate 状态，触发新一轮选举。在前面的描述中也提到过，选举超时时间是一个随机数，通过这种随机的方式，会使得多个 Candidate 节点瓜分选票的情况明显减少，也就减少了选举耗时。另外，选举超时时间应该比平均故障间隔时间小几个数量级，这样 Leader 节点才能稳定存在，整个集群才能稳定运行。当 Leader 节点崩溃之后，整个集群会有大约相当于选举超时的时间不可用，这种情况占比整个集群稳定运行的时间还是非常小的。
广播时间和平均故障间隔时间是由网络和服务器本身决定的，但是选举超时时间是可以由我们自己调节的。一般情况下，广播时间可以做到0.5ms～50ms，选举超时时间设置为200ms～1s之间，而大多数服务器的平均故障间隔时间都在几个月甚至更长，很容易满足上述不等式的时间需求。
日志复制
通过上一节介绍的 Leader 选举过程，集群中最终会选举出一个 Leader 节点，而集群中剩余的其他节点将会成为 Follower 节点。
日志复制过程
日志复制过程如下：
- Leader 节点除了向 Follower 节点发送心跳消息，还会处理客户端的请求，并将客户端的更新操作以消息（Append Entries 消息）的形式发送到集群中所有的 Follower 节点。
- 当 Follower 节点记录收到的这些消息之后，会向 Leader 节点返回相应的响应消息。
- 当 Leader 节点在收到半数以上的 Follower 节点的响应消息之后，会对客户端的请求进行应答。
- 最后， Leader 会提交客户端的更新操作，该过程会发送 Append Entries 消息到 Follower 节点，通知 Follower 节点该操作已经提交，同时 Leader 节点和 Follower 节点也就可以将该操作应用到自己的状态机中。
上面这段描述仅仅是 Raft 协议中日志复制部分的大致流程，下面我们依然通过一个示例描述该过程，为了方便描述，我们依然假设当前集群中有三个节点（A、B、C），其中A是 Leader 节点，B、C是 Follower 节点，此时有一个客户端发送了一个更新操作到集群，如图 2-11（1）所示。前面提到过，集群中只有 Leader 节点才能处理客户端的更新操作，这里假设客户端直接将请求发给了节点A。当收到客户端的请求时，节点A会将该更新操作记录到本地的Log中，如图2-11（2）所示。
图2-11
之后，节点A会向其他节点发送Append Entries消息，其中记录了 Leader 节点最近接收到的请求日志，如图2-12（1）所示。集群中其他 Follower 节点收到该Append Entries消息之后，会将该操作记录到本地的Log中，并返回相应的响应消息，如图2-12（2）所示。
图2-12
当 Leader 节点收到半数以上的响应消息之后，会认为集群中有半数以上的节点已经记录了该更新操作， Leader 节点会将该更新操作对应的日志记录设置为已提交（committed），并应用到自身的状态机中。同时 Leader 节点还会对客户端的请求做出响应，如图 2-13（1）所示。同时， Leader 节点也会向集群中的其他 Follower 节点发送消息，通知它们该更新操作已经被提交， Follower 节点收到该消息之后，才会将该更新操作应用到自己的状态机中，如图2-13（2）所示。
图2-13
nextIndex 和 matchIndex 数组
在上述示例的描述中我们可以看到，集群中各个节点都会维护一个本地 Log 用于记录更新操作，除此之外，每个节点还会维护 commitIndex 和 lastApplied 两个值，它们是本地Log 的索引值，其中 commitIndex 表示的是当前节点已知的、最大的、已提交的日志索引值，lastApplied 表示的是当前节点最后一条被应用到状态机中的日志索引值。当节点中的 commitIndex 值大于 lastApplied 值时，会将 lastApplied 加1，并将 lastApplied 对应的日志应用到其状态机中。
注：当 commitIndex 值大于 lastApplied 值时，说明日志被写入当前节点，但未提交；
在 Leader 节点中不仅需要知道自己的上述信息，还需要了解集群中其他 Follower 节点的这些信息，例如， Leader 节点需要了解每个 Follower 节点的日志复制到哪个位置，从而决定下次发送 Append Entries 消息中包含哪些日志记录。为此， Leader 节点会维护 nextIndex[] 和 matchIndex[] 两个数组，这两个数组中记录的都是日志索引值，其代表含义如下：
- nextIndex[] 数组记录了需要发送给每个 Follower 节点的下一条日志的索引值；
- matchIndex[] 表示记录了已经复制给每个 Follower 节点的最大的日志索引值；
这里简单看一下 Leader 节点与某一个 Follower 节点复制日志时，对应 nextIndex 和 matchIndex 值的变化：Follower 节点中最后一条日志的索引值大于等于该 Follower 节点对应的 nextIndex 值，那么通过 Append Entries 消息发送从 nextIndex 开始的所有日志。之后， Leader 节点会检测该 Follower 节点返回的相应响应，如果成功则更新相应该 Follower 节点对应的 nextIndex 值和 matchIndex 值；如果因为日志不一致而失败，则减少 nextIndex 值重试。
示例：
下面我们依然通过一个示例来说明 nextIndex[] 和 matchIndex[] 在日志复制过程中的作用，假设集群现在有三个节点，其中节点A是 Leader 节点（Term=1），而 Follower 节点C因为宕机导致有一段时间未与 Leader 节点同步日志。此时，节点C的 Log 中并不包含全部的已提交日志，而只是节点A的 Log 的子集，节点C故障排除后重新启动，当前集群的状态如图2-14所示（这里只关心 Log、nextIndex[]、matchIndex[]，其他的细节省略，另外需要注意的是，图中的Term=1表示的是日志发送时的任期号，而非当前的任期号）。
图2-14
A作为 Leader 节点，记录了nextIndex[] 和 matchIndex[]，所以知道应该向节点C发送哪些日志，在本例中， Leader 节点在下次发送 Append Entries 消息时会携带 Index=2 的消息（这里为了描述简单，每条消息只携带单条日志， Raft 协议采用批量发送的方式，这样效率更高），如图2-15（1）所示。当节点C收到 Append Entries 消息后，会将日志记录到本地 Log 中，然后向 Leader 节点返回追加日志成功的响应，当 Leader 节点收到响应之后，会递增节点 C 对应的 nextIndex 和 matchIndex，这样 Leader 节点就知道下次发送日志的位置了，该过程如图2-15（2）所示。
在上例中，当 Leader 节点并未发生过切换，所以 Leader 节点始终准确地知道节点C对应 nextIndex 值和 matchIndex 值。
如果在上述示例中，在节点C故障恢复后，节点A宕机后重启，并且导致节点B成为新任期（Term=2）的 Leader 节点，则此时节点 B 并不知道旧 Leader 节点中记录的 nextIndex[] 和 matchIndex[] 信息，所以新 Leader 节点会重置 nextIndex[] 和 matchIndex[]，其中会将 nextIndex[] 全部重置为其自身 Log 的最后一条已提交日志的 Index 值，而 matchIndex[] 全部重置为0，如图2-16所示。
图2-15
图2-16
随后，新任期中的 Leader 节点会向其他节点发送 Append Entries 消息，如图2-17（1）所示，节点A已经拥有了当前 Leader 的全部日志记录，所以会返回追加成功的响应并等待后续的日志，而节点C并没有 Index=2 和 Index=3 两条日志，所以返回追加日志失败的响应，在收到该响应后， Leader 节点会将 nextIndex 前移，如图2-17（2）所示。
图2-17
然后新 Leader 节点会再次尝试发送 Append Entries 消息，循环往复，不断减小 nextIndex值，直至节点C返回追加成功的响应，之后就进入了正常追加消息记录的流程，不再赘述。
Follower 节点投票
了解了 Log 日志及节点中基本的数据结构之后，请读者回顾前面描述的选举过程，其中 Follower 节点的投票过程并不像前面描述的那样简单（先收到哪个 Candidate 节点的选举请求，就将选票投给哪个 Candidate 节点）， Follower 节点还需要比较该 Candidate 节点的日志记录与自身的日志记录，拒绝那些日志没有自己新的 Candidate 节点发来的投票请求，确保将选票投给包含了全部已提交（committed）日志记录的 Candidate 节点。这也就保证了已提交的日志记录不会丢失： Candidate 节点为了成为 Leader 节点，必然会在选举过程中向集群中半数以上的节点发送选举请求，因为已提交的日志记录必须存在集群中半数以上的节点中，这也就意味着每一条已提交的日志记录肯定在这些接收到节点中的至少存在一份。也就是说，记录全部已提交日志的节点和接收到 Candidate 节点的选举请求的节点必然存在交集，如图2-18所示。
图2-18
如果 Candidate 节点上的日志记录与集群中大多数节点上的日志记录一样新，那么其日志一定包含所有已经提交的日志记录，也就可以获得这些节点的投票并成为 Leader 。
日志新旧比较策略
在比较两个节点的日志新旧时， Raft 协议通过比较两节点日志中的最后一条日志记录的索引值和任期号，以决定谁的日志比较新：首先会比较最后一条日志记录的任期号，如果最后的日志记录的任期号不同，那么任期号大的日志记录比较新；如果最后一条日志记录的任期号相同，那么日志索引较大的比较新。
这里只是大概介绍一下 Raft 协议的流程和节点使用的各种数据结构，读者需要了解的是 Raft 协议的工作原理，如果对上述数据结构描述感到困惑，在后面介绍 etcd-raft 模块时，还会再次涉及这些数据结构，到时候读者可以结合代码及这里的描述进一步进行分析。
注：日志较旧的节点可能发生过宕机等故障，导致当前节点可能存在与集群其他节点数据不一致问题，所以不能担任 leader 节点；
网络分区的场景
接下来，我们来看一下 Raft 协议是如何处理网络分区情况的。
网络分区概念：在一个集群中，如果有部分节点的网络发生故障，与集群中另一部分节点的连接中断，就会出现网络分区，如图2-19所示，集群有A、B、C、D、E五个节点，其中节点A、B相互之间网络连通，节点C、D、E相互之间网络连通，但是这两部分节点之间出现网络故障，这就形成了网络分区。
图2-19
网络分区下 Leader 选举及日志复制
这里依然通过一个示例来说明 Raft 协议对网络分区场景的处理。假设集群中节点 A 是 Leader 节点，它会向其他四个节点发送 Append Entries 消息和心跳消息，如图2-20（1）所示。当出网络分区时，节点A的心跳消息只有节点B才能收到，而集群中的其他节点收不到，如图2-20（2）所示（图中节点A发往节点C、D、E的消息由于网络分区，并不会抵达节点C、D、E，故未在图中画出）。
图2-20
Leader 节点划分到节点较多的分区中
随着时间的流逝，集群中与 Leader 节点隔离的网络分区（C、D、E）中，会率先有一个节点的选举计时器（election timer）超时，这里假设该节点是E，此时的节点E就会切换成 Candidate 状态并发起下一轮选举，如图2-21（1）所示。由于网络分区，当前集群中只有节点C、D能够收到节点E的选举请求，这里假设节点C、D都会将选票投给节点E，如图2-21（2）所示。
图2-21
到此为止，节点 E 在此次选举中收到了得到三票（其中包括它本身的一票），达到集群半数以上，所以节点E成为新任期（Term=2）的 Leader 节点，如图2-22所示：
图2-22
当网络故障被修复时，上述的网络分区也就会消失，此时节点 A（任期 Term=1 的 Leader 节点）发送的心跳消息会被节点C、D、E接收到（图2-22中虽然省略了这些由于网络分区而无法送达的心跳消息，但实际上节点A依然认为自己是 Leader 节点，在发送心跳消息时也会向节点C、D、E发送心跳消息），但是这些心跳消息中携带的Term值小于当前C、D、E节点的Term值，会被C、D、E节点忽略；同时，节点E（Term=2任期的 Leader 节点）发送的心跳消息会被节点 A、B 接收到（图2-22 中同样省略了这些无法送达的心跳消息），不同的是，这些心跳消息携带的Term值大于当前A、B节点的Term值，所以节点A、B会切换成 Follower 状态，这样整个集群中的 Leader 节点依然是节点E。
注：当 Follower 节点收到比自己Term小的节点的心跳消息时，此心跳消息会被忽略；
Leader 节点划分到节点较少的分区中
读者可能会问：如果网络分区时， Leader 节点划分到节点较多的分区中，如图2-23所示，此时节点较少的分区中，会有节点的选举计时器超时，切换成 Candidate 状态并发起新一轮的选举。但是由于该分区中节点数不足半数，所以无法选举出新的 Leader 节点。待一段时间之后，该分区中又会出现某个节点的选举计时器超时，会再次发起新一轮的选举，循环往复，从而导致不断发起选举，Term号不断增长。
在 Raft 协议中对这种情况有一个优化，当某个节点要发起选举之前，需要先进入一个叫作 PreVote 的状态，在该状态下，节点会先尝试连接集群中的其他节点，如果能够成功连接到半数以上的节点，才能真正发起新一轮的选举。通过这种方式就可以解决上述的问题，在后面分析 etcd-raft 模块时，还会详细介绍其具体实现。
图2-23
回到前面的示例简单来介绍网络分区恢复时的相关处理。当网络分区恢复时，集群中存在新旧两个 Leader 节点（A和E），其中节点E的Term值较高，会成为整个集群中的 Leader 节点。但是由于之前的网络分区，节点A、B的本地 Log 中可能存在未提交的日志记录，如图2-24（1）所示，此时节点A和B会回滚未提交的日志记录，并重新复制新 Leader 节点的日志，如图2-24 （2）所示。
图2-24
这样在网络分区恢复之后，整个集群的日志又会恢复一致。到此为止，网络分区场景下的 Leader 选举及日志复制过程就介绍完了，希望通过对这种特殊场景的介绍，读者能够更深刻地了解 Raft 协议的工作原理。
网络分区下客户端与集群的交互及日志复制
另一个需要介绍的问题是，网络分区场景下，客户端与集群的交互过程及日志复制的过程。这里我们先简单介绍一下客户端如何与集群进行交互并找到集群的 Leader 节点。在前面提到过，集群中只有 Leader 节点可以处理客户端发来的请求，当 Follower 节点收到客户端的请求时，也必须将 Leader 节点信息告知客户端，然后由 Leader 节点处理其请求，具体步骤如下：
（1）当客户端初次连接到集群时，会随机挑选一个服务器节点进行通信。
（2）如果客户端第一次挑选的节点不是 Leader 节点，那么该节点会拒绝客户端的请求，并且将它所知道的 Leader 节点的信息返回给客户端。
（3）当客户端连接到 Leader 节点之后，即可发送消息进行交互。
（4）如果在交互过程中 Leader 节点宕机，那么客户端的请求会超时，客户端会再次随机挑选集群中的节点，并从步骤1重新开始执行。
注：未发生网络分区时，客户端把请求直接发送到 Leader 节点；
网络未分区客户端与集群的交互及日志复制
这里依然通过一个示例来介绍整个过程，假设集群依然有五个节点，在未发生网络分区时，节点A为集群的 Leader 节点，此时的客户端请求会发送到节点A，经过前面描述的日志复制过程后，节点A也会向客户端返回响应，与如图2-25（1）和（2）所示。
图2-25
网络分区客户端与集群的交互及日志复制
当节点A、B与节点C、D、E之间发生网络分区之后，客户端发往节点 A的请求将会超时，这主要是因为节点A无法将请求发送到集群中超过半数的节点上，该请求相应的日志记录也就无法提交，从而导致无法给客户端返回相应的响应，该过程如图2-26（1）和（2）所示。
注：Leader 节点在收到客户端请求后，会将请求发送到集群中的 Follower 节点，只有在收到半数以上 Follower 节点的响应后，Leader 节点才会给客户端相应的响应；
图2-26
前面已经介绍了网络分区之后的 Leader 选举过程，这里不再赘述，该示例中假设节点E被选举为新任期（Term=2）的 Leader 节点。当请求超时之后，客户端会重新随机选择一个节点，并获取新 Leader 节点的信息，客户端最终会连接到节点E并发送请求，而该网络分区中有超过半数的节点，请求对应的日志记录可以提交，所以客户端的请求不会再次出现超时，之后客户端会一直与节点E进行交互直至下次请求超时。上述过程的如图2-27（1）～（4）所示。
图2-27
图2-27（续）
在 Raft 协议的论文中，还给出了另一种 proxy 的方案：假设客户端连接到集群中的某个 Follower 节点，该 Follower 节点会将客户端发送的所有请求转发给 Leader 节点进行处理，当 Leader 节点响应 Follower 节点之后，再由 Follower 节点响应客户端。当出现请求超时的情况时，客户端同样需要随机选择新的节点进行连接。
日志压缩与快照
通过前面章节的描述可知，随着客户端与集群不断地交互，每个节点上的日志记录会不断增加，但是服务器的空间都是有限的，日志量不能无限制地增长。另外，在节点重启时会重放日志记录，如果日志记录过多，则需要花费较长的时间完成重放操作。这就需要压缩和清除机制来减少日志量，从而避免上述情况。
定期生成快照是最常见也是最简单的压缩方法。在创建快照文件时，会将整个节点的状态进行序列化，然后写入稳定的持久化存储中，这样，在该快照文件之前的日志记录就可以全部丢弃了。例如，集群中变量 a 的值为100，客户端发送了一个更新请求将变量 a 更新为13，经过前面描述的日志复制过程之后，该请求对应的日志记录最终被提交并应用到集群中的每个节点中。此时每个节点中维护的变量 a 都是 13，而 a=13 这条日志记录就无须继续保留。在 ZooKeeper、Chubby 和 etcd 中都有类似上述的快照处理逻辑，这里只是介绍创建快照文件和压缩日志的基本逻辑，在后面的章节会具体介绍其实现。
在快照中除了节点当前的数据状态，还包含了其最后一条日志记录的任期号和索引号，如图2-28所示，该快照包含了6条日志记录，在快照的元数据中记录了第6条日志记录的任期号和索引号，在生成快照文件之后，即可将1～6条日志记录丢弃了。
图2-28
一般情况下，集群中的每个节点都会自己独立、定时地创建快照，在其状态恢复时，都会使用自己本地最新的快照数据。如果 Follower 节点长时间宕机（或是刚刚加入集群的新节点），就有可能导致其日志记录远远落后于当前的 Leader 节点，与此同时， Leader 节点中陈旧的日志记录已被删除了。在这种场景下，为了将该 Follower 节点恢复到正确的状态， Leader 节点会将快照发送给该 Follower 节点， Follower 节点会使用该快照数据进行状态恢复。当 Leader 节点需要向 Follower 节点发送快照时，会发送一种特殊的消息类型（快照消息）。etcd 的网络层为了高效地传输消息，会将快照的发送与普通消息（Append Entries消息、心跳消息等）的发送分开在不同的消息通道中完成，在后面介绍 etcd 网络层时会详细介绍。
当 Follower 节点接收到该快照消息时，必须决定如何处理已存在的日志记录，在快照中之所以保留前面介绍的一些元数据，其作用之一就是为了在 Follower 节点收到快照之后进行一致性检查。一般情况下，快照已包含了该 Follower 节点中不存在的日志记录，此时 Follower 节点直接丢弃其所有的日志记录，因为这些日志最终会被 Leader 传递来的快照所代替。如果 Follower 节点接收到的快照只包含了自己本地日志的一部分，那么被该快照所包含的全部日志记录会被全部删除，但是快照之后的日志则会保留。
有的读者可能会考虑过另一种替代方案，即只有 Leader 节点创建快照，然后发送给所有的 Follower 节点。但是该方案有几个缺点：首先就是快照数据会比较大，并且发送快照数据是比较浪费网络带宽的，也比较耗时，这显然比 Follower 节点从本地直接加载要耗时很多；其次就是 Leader 的实现会更加复杂。
在 Raft 协议中，每个节点都会创建快照，所以创建快照的时机决定了快照的性能。如果创建快照过于频繁，那么就会消耗大量的资源，导致每个节点的性能下降；如果创建快照的频率过低，那么两次创建快照之间积累的日志记录会比较多，快照就无法为节点节约内存等资源。所以我们要在两者之间进行权衡，常见的策略是当日志记录个数达到一个固定阈值的时候，就触发一次创建快照的操作，生成相应的快照文件，我们可以通过调节该阈值来控制创建快照的频率。
其他技术点
linearizable 语义、只读请求、PreVote 状态、Leader 节点转移都是针对 Raft 协议的一些优化！
linearizable 语义
Raft 协议的目标是实现 linearizable 语义，即在客户端每次向集群发送一次读请求时，该请求只会被执行一次。但是根据前面的描述，客户端虽然只是想发送一次请求，但是集群可能多次收到该请求。例如， Leader 节点负责提交日志记录（通知了其他 Follower 节点）并将日志记录应用到了其状态机中，但是在向客户端返回相应的响应消息之前宕机了，那么客户端会连接到新的 Leader 节点并重发对应的请求，这就导致该请求再次被执行。或者，网络出现故障，导致请求丢失或是延迟，如图2-29所示，就会导致同一条请求被执行两次。
图2-29
通过序列号去重：常见的解决方案就是客户端对于每个请求都产生一个唯一的序列号，然后由服务端为每个客户端维护一个Session，并对每个请求进行去重。当服务端接收到一个请求时，会检测其序列号，如果该请求已经被执行过了，那么就立即返回结果，而不会重新执行。
linearizable 语义目标：在客户端每次向集群发送一次读请求时，该请求只会被执行一次！
只读请求
在介绍 Raft 协议的日志复制时提到，请求对应的日志记录会写入 Leader 节点的本地 Log 中并完成复制到集群中半数以上的节点，之后才会真正提交并应用到状态机中。为了提高只读请求的性能，我们可以考虑直接处理而不记录对应的日志记录（也不会经过日志复制的过程）。但是，在不增加任何限制的情况下，这么做可能会冒着返回脏数据的风险，因为 Leader 节点响应客户端请求时可能已经故障（或是已经发生了网络分区），集群已经选出了新的 Leader 节点，但是旧的 Leader 节点自身还不知道。
为了不返回脏数据，同时为了保证 linearizability 语义， Raft 协议在处理只读请求时，除了直接读取 Leader 节点对应的状态信息，还需要使用额外的措施。
处理只读请求的大致逻辑如下：
（1） Leader 节点必须有关于已提交日志的最新信息，虽然在节点刚刚赢得选举成为 Leader 时，拥有所有已经被提交的日志记录，但是在其任期刚开始时，它可能不知道哪些是已经被提交的日志。为了明确这些信息，它会在其任期开始时提交一条空日志记录，这样上一个任期中的所有日志都会被提交。
（2） Leader 节点会记录该只读请求对应的编号作为 readIndex，当 Leader 节点的提交位置（commitIndex）达到或是超过该位置之后，即可响应该只读请求。
（3） Leader 节点在处理只读的请求之前必须检查集群中是否有新的 Leader 节点，自己是否已经被作废，如果该节点已经不再是集群的 Leader 节点，则该节点中日志记录就可能包含脏数据，必须由新 Leader 节点来处理此次只读请求。 Raft 协议中，通过让 Leader 节点在处理只读请求之前，先和集群中的半数以上的节点交换一次心跳消息来解决这个问题。如果该 Leader 节点可以与集群中半数以上的节点交换一次心跳，则表示该 Leader 节点依然为该集群最新的 Leader 节点。这样，readIndex 值也就是整个集群中所有节点所能看到的最大提交位置（commitIndex）。
（4）随着日志记录的不断提交， Leader 节点的提交位置（commitIndex）最终会超过上述 readIndex，此时 Leader 就可以响应客户端的只读请求了。
只读请求目标：服务端直接处理只读请求而不记录对应的日志，以提高只读请求的性能！
这里简单介绍一下 linearizability 的含义，线性化（linearizability）是分布式系统中比较重要的概念。linearizability 是对单对象上的单个操作的一种顺序保证，它提供了对于同一个对象的一系列读写操作都是按照实时时间排序的保证。简单地说，linearizability 保证对于一个对象的写操作一旦完成，需要立即被后续的读操作看到，即读操作一定是读到该对象的最新的值。从该角度来看，linearizability 与 atomic consistency 是同义词，也是CAP原则中的C（consistency）。另外，并且 linearizability 是可组合的，如果系统中每个对象的操作都是 linearizable，则系统中所有操作是 linearizable。
PreVote 状态
在前面介绍网络分区场景时提到，在节点数不足集群半数的网络分区中，始终没有节点可以获取半数以上的选票成为 Leader 节点，所以每过一段时间，就有节点的选举计时器超时并切换成 Candidate 状态，发起新一轮的选举。
这虽然不影响集群的使用（在节点超过半数的网络分区中，已经成功选举出 Leader 节点并对外提供服务），但是会导致不断发起选举的节点的 Term 号不断增长。当网络分区结束时，由于该节点的 Term 值高于集群当前的 Leader 节点的 Term 值，就会迫使当前 Leader 节点发生状态切换，并重新发起一次新的选举。
Raft 协议为了优化此次无意义的选举，给节点添加了一个 PreVote 的状态：当某个节点要发起选举之前，需要先进入 PreVote 的状态。在 PreVote 状态下的节点会先尝试连接集群中的其他节点，如果能够成功连接到半数以上的节点，才能真正切换成 Candidate 状态并发起新一轮的选举。在后面分析etcd-raft模块时，我们可以看到相关实现。
PreVote 目标：避免无效选举！
Leader 节点转移
通过前面的介绍我们知道， Leader 节点在整个集群中的作用至关重要。但是在有的场景中需要对 Leader 节点进行手动切换。例如，我们要将 Leader 节点所在的机器进行系统升级或是停机维护等。此时，我们可能需要集群中指定的 Follower 节点成为新的 Leader 节点，继续对外提供服务。在原 Leader 节点所在的机器维护结束之后，我们可能还需要将 Leader 节点再转移到该机器上（可能该机器的配置等条件优于集群中的其他机器，更适合做 Leader 节点）。这种场景下就需要特定的 Follower 节点成为下一任期的 Leader 节点。根据前面介绍的 Leader 选举过程我们知道，Leader 节点的选举在本质上是随机的，无法满足上述需求。
Raft 协议给出的方案是：首先暂停接收客户端请求，让一个指定的 Follower 节点的本地日志与当前的 Leader 节点完全同步，在完成同步之后，该特定的 Follower 节点立刻发起新一轮的选举。由于其Term值较大，原 Leader 节点自然被其替换下来。该方案需要控制好选举计时器及特定 Follower 与 Leader 节点同步的时间，防止其他 Follower 节点在这段时间内发起选举，当然，发生这种情况的概率还是比较低的。
Leader 节点转移目标：手动切换 Leader 节点和 Follower 节点！
在实现 Raft 协议的时候，除了上面提到的扩展点和优化点，在 Raft 大论文中还提到一些其他的相关内容，非常值得参考。笔者也极力推荐读者亲自阅读该论文，毕竟本书篇幅有限，无法将其内容逐一介绍。
本章小结
本章主要介绍了 Raft 协议的基本概念和基本流程，其中包括 Leader 节点的选举、节点间的复制、日志的压缩、快照的生成，以及网络分区等场景的介绍，最后还介绍了在实现 Raft 协议时可能会遇到的特殊问题的相关方案。在本章中介绍每个流程时，都是通过示例方式进行描述的，希望读者在阅读完本章后，对 Raft 协议有一个初步的了解，为后面分析etcd-raft模块打下基础。在后面分析 etcd-raft 模块时，也建议读者回顾本章 Raft 算法的实例，了解 etcd 实现与 Raft 算法的细微差异。
