1.Raft 简介

Raft is a consensus algorithm for managing a replicated log.It
produces a result equivalent to (multi-)Paxos, and it is as efficient
as Paxos, but its structure is different from Paxos; this makes Raft
more understandable than Paxos and also provides a better foundation
for building practical systems.In order to enhance understandability,
Raft separates the key elements of consensus, such as leader election,
log replication, and safety, and it enforces a stronger degree of
coherency to reduce the number of states that must be considered. Raft
also includes membership, which uses overlapping majorities to
guarantee safety. ——Raft 论文

简而言之，分布式系统将一组独立的计算机 (也可以叫做服务器) 包装成了一个“整体”向用户提供服务，当用户通过客户端发出一个请求时，分布式系统需要将此请求的操作正确地同步到集群每一台服务器上执行，Raft 算法可以通过日志同步复制实现这个目标。

Raft 的目标是将客户端请求操作正确地部署到集群内所有服务器上。每个服务器都有一个日志来记录这些请求操作，状态机 (state machine) 依照日志来执行操作，假设我们能够保证所有服务器的日志都保持一致，那我们就能实现集群内每一台服务器的状态机都能按照相同的顺序执行相同的操作，得到相同的执行结果。这就是为什么 Raft 的核心问题是管理日志，并保证它们在集群内的同步复制，以及何时传给状态机执行才是安全的。

我们允许一些服务器崩溃，实际上只要集群内大部分计算机能够正常运行，Raft 一致性算法就可以运转。

问题 1：直接将客户端的请求操作发送到每一个服务器上执行就好了，为什么需要额外设计 Raft 算法？
答：Raft 是工程上使用较为广泛的强一致性、去中心化、高可用的共识算法，在现实世界里，部分服务器崩溃、网络延时、网络分割是普遍发生的情况，在这样的前提下 Raft 可以做到正确同步。同时，只要集群内大部分计算机能够正常运行，Raft 共识算法就可以正常运转。例如，我们有 3 台服务器，那么我们就可以接受其中 1 台服务器崩溃，，当我们有 5 台服务器，可以接受其中的 2 台服务器崩溃。

Raft 算法实现容错的方式是，我们允许服务器崩溃，但希望服务器即使不执行也不要执行错误的操作(拜占庭行为)，一些服务器可能中途崩溃停止了操作，当服务器重新上线后，通过 Raft 算法恢复到正确的状态。

实现共识主要有两种方式：Leader-less 和 Leader-based。Raft 选择第二种，好处在于：

• 将共识问题分解成一个两阶段模型，有领导时的普通操作阶段与没领导的时候进行领导选举阶段；
• 简化了普通操作阶段，集群内其他服务器都听领导服务器的指挥就行，不会产生冲突，Raft 所有的复杂操作都和领导选举有关。
• 比 Leader-less 方式更加高效，Leader-less 方式需要处理服务器之间的冲突；

2.Raft 概览

Raft 的工作主要是：Raft 先选出在集群内选出一个服务器做领导，领导在任期内完全负责对各个服务器的日志管理，当领导接收到客户端的操作请求，就同步复制到其他服务器上，并在“安全”的时候执行这些操作。当领导节点出现故障，Raft 选出一个新的领导。
后面会以 PPT 中呈现的六大组件来讲述这些工作的详细情况。

在了解详细情况前，要先知道 Raft 为服务器设置了三种状态(state)，分别是:

• Leader（领导): 处理与客户端的交互与各个服务器日志的同步复制
• Candidate(候选人): 在竞选领导时会出现的一种状态
• Follower(跟随者): 处于被动状态，在无领导的时候响应候选人的投票请求，在有领导的时候响应领导的指挥。

给出的状态图直观的表达了三种状态的区别。

时间被分割成一段段领导的任期(term)，每段任期都由唯一的序号表示，序号顺序增长，不会被重复使用。每个任期会分为两部分，分别是选举阶段和普通操作阶段，如果选举成功，被选择的领导会持续到任期结束，每个任期内只有一台服务器会成为领导。也会出现任期内没有选举出领导(term3)，这可能是由分票导致的，如果没选出领导就立即进入下一任期重新开始选举。任期是一个十分重要的概念，每一个服务器需要持久化存储任期信息(存储在硬盘这样的可靠媒介上)，这样崩溃的服务器在恢复后可以用任期来判断过期信息。

这张图是整个算法的完整概括，是工程化实现 Raft 算法的“操作手册”，包含了后面所讲的概念和细节。

可以分为: 对三种状态的描述、需要持久化存储的信息，以及描述了集群内各服务器之间是如何通信的。Raft 服务器的所有通信都基于远程过程调用(RPCs)，这里描述了选举阶段用到的 RequestVote RPC 和普通操作阶段用到的 AppendEntries RPC。

3.Raft 六大组件

3.1 选举

Raft 协议的第一个组件是选举。

每一台服务器是以 Follower 的状态启动的，在这个状态下，服务器只会被动的响应其他服务器的请求，不过，为了使 Follower 一直保持此状态，必须使他们相信集群中有一个领导存在。为了能够达成目标，Leader 需要定时发送心跳消息 (heartBeats) 告知 Follower 自己的存在，如果 Leader 想要延长任期，需要不断向每一个 Follower 发送 heartBeats(实质是没有内容的 AppendEntries)。如果一段时间内，Follower 没有收到任何的远程调用，那么它就假定集群内不存在一个 Leader，它就会重新发起一个选举，这段时间被称为选举超时(ElectionTimeout)。

当一个 Follower 服务器开始选举的时候，它会做下面这些事情：

• 增加当前任期号，开始新的一轮任期；
• 该 Follower 服务器将自己的状态转换为 Candidate，在这种状态下，它的目标就是成为 Leader；
• 为自己投一票；
• 并发地向集群内其他服务器发送 RequestVote RPCs；

通常这些 RequestVote RPCs 请求会不断地发出，直到出现以下情况的一种：
一、收到了来自集群内大多数服务器的投票。之后它会成为 Leader，并向集群内其他服务器发送 heartBeats 告知自己的存在。
二、

第一，在大多数情况下，也是我们希望出现的情况就是候选者得到了多数票，然后它会将自己的状态转换为领导者并立即向集群其他服务器发送心跳检测，这可以建立它的领导者地位，有效的标记领导者所管理的范围。

第二，可能出现有其他的候选者也同时在运行，或许它们也有可能获得多数票成为领导者，在这个点上，如果候选者收到来自于有效领导者的 RPC 调用，那么它会立即放弃成为领导者的可能，随即回到跟随者的状态。

第三，有可能没有任何服务器得以获胜，如果存在有多个服务器都同时成为候选者，它们会导致分票，没有服务器会获得多数选票。为了检测到出现这种状况的可能性，随着时间的推移，当没有出现以上第一、第二种情况时，它既没有成为领导者，也没能获得来自于其他领导者的响应，那么它就会假定出现分票的情况。在这种情况下，只要简单地增加任期号，重新选举即可。