Raft 算法概述

What is Raft

Raft 协议是一种共识算法（consensus algorithm）

简单来说，其实就是大家投票，超过半数，通过✅

为什么需要 Raft ？

回答该问题之前可以思考一下另一个问题：为什么需要共识算法？

为了解决单点问题，软件系统工程师引入了数据复制技术，实现多副本。而多副本间的数据复制就会出现一致性问题。所以需要共识算法来解决该问题。

共识算法的祖师爷是 Paxos，但是由于它过于复杂，难于理解，工程实践上也较难落地，导致在工程界落地较慢。 Raft 算法正是为了可理解性、易实现而诞生的

概述

Raft给服务器设置了三种状态，分别是领导者(leader)、跟随者(follower)和候选者(candidate)。跟随者通过投票选出领导者，只有得到“大多数”跟随者投票的服务器能成为领导者；领导者负责将命令同步给跟随者，只有被“大多数”跟随者确认的命令才能提交。

raft 会先选举出 leader，leader 完全负责 replicated log 的管理。leader 负责接受所有客户端更新请求，然后复制到 follower 节点，并在“安全”的时候执行这些请求。如果 leader 故障，followes 会重新选举出新的 leader。

通过 leader，raft 将一致性问题分解成三个相当独立的子问题：

Leader Election：当集群启动或者 leader 失效时必须选出一个新的l eader。
Log Replication：leader 必须接收客户端提交的日志，并将其复制到集群中的其他节点，强制其他节点的日志与 leader 一样。
Safety：最关键的安全点就是图3.2中的 State Machine Safety Property。如果任何一个 server 已经在它的状态机apply了一条日志，其他的 server 不可能在相同的 index 处 apply 其他不同的日志条目。后面将会讲述 raft 如何实现这一点

Leader选举

在 raft 中，一个节点任一时刻都会处于以下三个状态之一：

Leader
- leader 处理所有来自客户端的请求(如果客户端访问 follower，会把请求重定向到 leader)
Follower
- follower 是消极的，他们不会主动发出请求而仅仅对来自 leader 和 candidate 的请求作出回应。
Candidate
- Candidate 状态用来选举出一个 leader。

在正常情况下会只有一个 leader，其他节点都是 follower

Raft 使用心跳机制来触发 leader 选举，具体状态转换流程如图：

流程大概如下：

所有节点处于Follower
大家等待Leader的心跳，一段时间收不到，从follower切换到candidate,在term+1发起选举
如果收到 majority 的投票（含自己的一票）则切换到 leader 状态；
如果发现其他节点 term 比自己更新，则主动切换到 follower

Term如下

term是一段一段的

election timeout

可能会出现的一种情况是，所有 follower 节点，检测到超时后都同时发起选举，因为都会默认投票给自己，这就会导致最终没有节点可能获取到超过半数的选票，最终选举失败，然后选举超时后又开始下一轮选举，进入死循环。

Raft 使用随机选举超时来确保选票被瓜分的情况很少出现。election timeout 的值会在一个固定区间内随机的选取(比如150-300ms)。这使得在大部分情况下仅有一个 server 会检测到超时，它将会在其他节点发现超时前发起选举，则有很大概率赢得选举

Log Replication

当有了 leader，系统就可以对外提供服务了。每一个客户端的写请求都包含着一个待状态机执行的命令，leader 会将这个命令作为新的一条日志追加到自己的日志中，然后并行向其他 server 发出AppendEntries RPC 来复制日志。

当日志被安全的复制之后，leader可以将日志 apply 到自己的状态机，并将执行结果返回给客户端。如果 follower 宕机或运行很慢，甚至丢包，leader 会无限的重试RPC (即使已经将结果报告给了客户端)，直到所有的 follower 最终都存储了相同的日志。

Replicated State Machine

共识算法的实现一般是基于复制状态机（Replicated state machines）.replicated state machine 用于解决分布式系统中的各种容错问题。

简单来说：相同的初始状态 + 相同的输入 = 相同的结束状态。

通常使用 replicated log 来实现 Replicated state machine ，如下图所示：

每一个 server 都有一个日志保存了一系列的指令，state machine 会顺序执行这些指令。每一个日志都以相同顺序保存着相同的指令，因此每一个 state machine 处理相同的指令，state machine 是一样的，所以最终会达到相同的状态及输出。

共识算法的任务则是保证 replicated log 的一致。server 中的一致性模块接收客户端传来的指令并添加到自己的日志中，它也可以和其他 server 中的一致性模块沟通来确保每一条 log 都能有相同的内容和顺序，即使其中一些 server 宕机。一旦指令被正确复制，就可以称作committed。每一个 server 中的状态机按日志顺序处理committed 指令，并将输出返回客户端。

上述情况是个理想的情况，但现实中可能因为各种问题，造成每个 Follower 的日志不一致（如下图）。Raft 在日志复制请求（AppendEntries RPC）的设计上， 不允许直接复制最新的日志，而跳过中间尚未复制的日志 。如下图领导者如果发送索引 8 的日志复制请求给第一个跟随者，这个跟随者目前最新的日志只有到索引 5，所以会拒绝领导者的请求，此时领导者会继续发送索引 7 的日志复制请求给第一个跟随者，跟随者一样会拒绝，直到领导者发送索引 6 的日志复制请求给第一个跟随者时，跟随者才会接受，并从索引 6 开始重新同步到索引 8。

所以如果 Raft 集群要对外服务，则至少要有一半以上的节点有完整的日志记录时，才可以对外服务，因为没有完整日志记录的节点，就无法对最新写进日志的要求回复成功

Leader Completeness

在任何基于leader的一致性算法中，leader必须最终存有全部committed日志。

在一些一致性算法（如Viewstamped Replication），节点即使不包含全部 committed 日志也能被选举为 leader，这些算法通过其他的机制来定位缺失的日志，并将其转移给新的 leader。然而这增加了系统的复杂度，raft 使用了更加简单的方法来确保所有 committed 的日志存在于每个新选举出来的 leader，不需要转移日志。因此日志只需要从 leader 流向 follower 即可，而且不需要重写自己的日志。

Raft 使用投票过程来确保选举成为 leader 的 candidate 一定包含全部committed 的日志。

具体如下：