背景及概念介绍
Raft是Diego Ongaro和John Ousterhout于2013年开发的一种基于领导者的共识算法，允许分布式系统中各节点在出现故障时可以针对一系列的数值达成一致，以可靠、复制、冗余、容错而闻名。比起Paxos协议来说Raft更加通俗易懂、易于实现。但需要注意的是Raft与Paxos不同，节点是信任当前的leader的，并不适用于拜占庭容错的算法。

Raft提供了一种在计算系统集群中分布多个状态机的通用方法，可以确保集群中的每个节点都同意相同的一系列状态变更，同时其采用了更强的领导形式。比如日志条目仅会从leader节点流向其他节点，如果客户端与其他节点建立通信，那么其他节点将会将其重定向给leader，简化了日志复制等操作的管理。
此处我们引入一个新的概念：复制状态机。

在分布式系统中，共识算法通常出现在复制状态机的背景下。复制状态机是解决系统中的各种容错问题的一个通用方法，可以通过复制日志并协调客户端与服务器副本的交互来构建容错系统。
 

如上图所示，在分布式系统中每个服务器都存储有一个日志（包含一系列命令），以及一个状态机。状态机按顺序执行这些命令。每个日志包含相同顺序的相同命令，因此每个状态机都从其日志中获取输入命令处理相同的命令序列。由于状态机是确定性的，所有节点从同一个 state 出发，每个状态机都会执行相同的操作序列，最终会产生相同的结果，达到相同的state。

我们只要保证集群中所有节点的log是一致的，那么经过一系列应用（apply）后最终得到的状态机也必然会是一致的。问题来了，如何保证log复制时的一致性？

通过共识模块（Consensus Module）。

共识模块在接收到客户端的命令后会将其添加到日志中，并与其他服务器的共识模块进行通信来确保每台服务器的日志都包含相同顺序的请求。复制完成后每台服务器的状态机都会按照日志的命令序列进行处理，产生相同的输出后将输出返回客户端。至此，形成了一个单一的、高度可靠的复制状态机。

与其他共识算法略有不同，Raft将分布式系统中易出现的共识问题分成了几个相对独立的子问题：
a.领导者选举（Leader election）：Raft 集群存在一个主节点（leader），客户端向集群发起的所有操作都必须经由主节点处理。主节点负责处理数据更新和复制的任务，因此没有leader，集群将无法工作。需要先进行领导者选举再进行下述操作；
b.日志复制（Log replication）：Leader节点会负责接收客户端发过来的操作请求，将操作包装为日志条目并在集群中进行同步操作来确保其他节点的日志与自己的日志一致。在保证大部分节点都同步了本次操作后，就可以安全地给客户端回应响应了；
c.安全属性（Safety）：分布式系统中有很多种情况可能发生，算法需要设置多项安全属性（限制）为系统的正确性以及可用性提供安全保证。具体有哪些关键的安全属性以及Raft如何确保，后面将详细介绍。
Raft核心算法其实就是由这三个子问题组成的：选主（Leader election）、日志复制（Log replication）、安全性（Safety）。这三部分共同实现了 Raft 核心的共识和容错机制。接下来我们针对这三个子问题进行深度剖析。

算法剖析
Raft算法中的节点角色
集群中的每个节点角色都处于三种状态中的任何一种，Leader（领导者）、Follower（跟随者）、Candidate（候选者）。通常只有一个leader，所有其他服务器都是follower。Leader是所有请求的处理节点，接收客户端发起的操作请求后写入本地之日后同步至集群其它节点。Follower不会发出请求，只被动响应来自Leader跟Candidate的请求。Candidate则主要用于选举新的leader。下图展现了状态转变的大致过程。
 

领导者选举（Leader election）
因为后续leader会负责将日志复制到follower节点上，因此会定期通过发送心跳消息来告知follower他还在正常运行。每个follower都有一个超时机制，通常150到300毫秒之间。在这段时间内如果follower收到了来自leader的心跳信息，时间则会重置，如果没有收到，follower 会将其状态更改为Candidate并发起leader选举。获得整个集群大多数选票的Candidate将成为新任leader，然后向所有其他服务器发送心跳消息防止出现新的选举。Leader通常会一直持续运行到失败为止。
 

比如如下图图解所示：


在这个阶段会涉及一个新的概念：任期（term），每个任期都由一个单调递增的数字（任期号）标识。
 

Raft将时间划分为任意长度的term，如上图所示，每当 candidate 触发 leader election 时都会增加 term。服务器每个任期只能投票一次，按照先到先得的原则。Candidate如果收到了来自其他服务器节点（follower）的多数选票，那么本届任期则由它担任新任leader执行数据更新、复制等操作直至任期结束。但并不是每个term都一定对应一个leader，有时候某个term内会由于分散投票导致选不出leader，这时candicate会递增任期号并开始新一轮选举。

题外话：为什么要有任期号的概念？

服务器不会在每时每刻都去观察不同任期之间的变化，因此任期在Raft中承担逻辑时钟（logic clock）的作用，服务器可以通过任期号来检测leader的状态是否已过期，就像前面提到的每个节点都保存了一个current term number，在通信时会互相进行交换做出决策。比如说下方情况出现：
 

• 在Raft算法中的节点角色部分中提到的状态转换图，有一条状态线是discovers server with higher term。这条线的背景是当leader发生了宕机或网络断连，此时其它follower无法收到leader的心跳信息，首个触发超时的节点会变为candidate并开始拉票（此时也会新增一个term），由于该candidate的term大于原leader的term，因此所有follower都会投票给它，这名candidate会变为新的leader。一段时间后原leader恢复了，收到了来自新leader的心跳包，发现自己当前的term小于心跳中的term，那么他会立即恢复为follower状态并将其term进行更新。

当然还有许多用途，比如可以通过任期号来检测leader是否已过期等等，具体细节可以继续看下去~
节点间主要通过两种类型的远程过程调用（RPC）来进行通信：
 

• RequestVotes RPC：由候选节点发送，用于在选举期间向其他节点请求选票；
• AppendEntries RPC：这个RPC由leader发起，携带最新收到的命令。它还用作心跳消息。当follower收到此消息时，选举计时器将被重置。

大概流程我们稍微了解了，下面我们来具体了解一下选举领导者的详细过程。