Raft 是一个共识算法（consensus algorithm）。Raft 是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。
Raft 算法是基于复制状态机模型推导的。复制状态机
Raft 算法包括三个子问题：
- 领袖选举: Leader 故障后集群能快速选出新 Leader
- 日志复制: 集群只有 Leader 能写入日志， Leader 负责复制日志到 Follower 节点，并强制 Follower 节点与自己保持相同
- 安全性: 一个任期内集群只能产生一个 Leader、已提交的日志条目在发生 Leader 选举时，一定会存在更高任期的新 Leader 日志中、各个节点的状态机应用的任意位置的日志条目内容应一样。
基本概念
一般情况下，分布式系统中存在两种节点关系模型:
- 对称: 所有节点都是平等的，不存在主节点。客户端可以与任意节点进行交互
- 非对称: 基于选主模型，只有主节点拥有决策权。任意时刻有且仅有一个主节点，客户端只与主节点进行交互
基于简化操作和效率等因素考虑，Raft 算法采用的是非对称节点关系模型。在一个由 Raft 协议组织的集群中，一共包含如下 3 类角色:
- Leader（领袖）唯一性，拥有同步日志的特权，需定时广播心跳给 Follower 节点，以维持领导者身份
- Candidate（候选人），可以发起 Leader 选举
- Follower（群众），同步从 Leader 收到的日志，etcd 启动的时候默认为此状态
Raft 算法将时间划分为任意个不同长度的任期，任期是单调递增的，用连续的数字（1,2,3…）表示。在 Raft 中，每个任期开始进行一次领导人选举。一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，那么它就会在该任期的剩余时间内担任领导人。在某些情况下，选票会被瓜分，导致没有哪位候选人能够得到超过半数的选票，这样本次任期将以没有选出领导人而结束。那么系统就会自动进入下一个任期，开始一次新的选举。Raft 算法保证在给定的一个任期内最多只有一个领导人。某些 Term 会由于选举失败，存在没有领导人的情况。
每个 Raft 节点各自都在本地维护一个当前任期值，触发这个数字变化（增加）主要有两个场景：开始选举或与其他节点交换信息。 当节点之间交换信息时，会相互交换当前的任期号:
- 如果一个节点（包括领导人）的当前任期号比其他节点的任期号小，则将自己本地的任期号自觉地更新为较大的任期号
- 如果一个候选人或者领导人意识到它的任期号过时了（比别人的小），那么它会立刻切换回群众状态
- 如果一个节点收到的请求所携带的任期号是过时的，那么该节点就会拒绝响应本次请求
需要注意的是，由于分布式系统中节点之间无法做到在任意时刻完全同步，因此不同的 Raft 节点可能会在不同的时刻感知到任期的切换。甚至在出现网络分区或节点异常的情况下，某个节点可能会感知不到一次选举或者一个完整的任期。这也是 Raft 强制使用较新的 Term 更新旧的 Term 的原因。
分布式环境下的“时间同步”是一个大难题，但是有时为了识别“过期信息”，时间信息又是必不可少的。于是，任期在 Raft 中起着逻辑时钟的作用，同时也可用于在 Raft 节点中检测过期信息一比如过期的领导人。
领导人选举
Raft 选举一个权力至高无上的领导人，任何领导人都拥有之前任期提交的全部日志条目。采取赋予它管理复制日志重任的方式来维护节点间复制日志的一致性。领导人从客户端接收日志条目，再把日志条目复制到其他服务器上，并且在保证安全性的前提下，告诉其他服务器将日志条目应用到它们的状态机中。强领导人的存在大大简化了复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志文件的什么位置，而不需要和其他服务器商议，并且数据都是单向地从领导人流向其他服务器。当然，在这种方式下，领导人自身的日志正确性显得尤为重要。
- 没有包含所有已提交日志条目的节点成为不了领导人
- 日志条目只有一个流向：从 Leader 流向 Follower。领导人永远不会覆盖已经存在的日志条目
上图是节点状态变化关系图，当 Follower 节点接收 Leader 节点心跳消息超时后，它会转变成 Candidate 节点，并可发起竞选 Leader 投票，若获得集群多数节点的支持后，它就可转变成 Leader 节点。
Raft 算法使用投票的方式来阻止那些没有包含所有已提交日志条目的节点赢得选举。一个候选人为了赢得选举必须要与集群中的大多数节点进行通信，这就意味着每一条已经提交的日志条目都会出现在至少其中一个与之通信的节点上（可以用反证法证明）。如果候选人的日志比集群内的大多数节点上的日志更加新（或至少一样新），那么它一定包含所有已经提交的日志条目。因此，RequestVote RPC 的接收方有一个检查：如果自己的日志比RPC 调用方（候选人）的日志更加新，就会拒绝候选人的投票请求。 比较的依据是日志文件中最后一个条目的索引和任期号：如果两个日志条目的任期号不同， 则任期号大的更加新；如果任期号相同，则索引值更大（即日志文件条目更多）的日志更加新。
Leader 在任期内必须定期向集群内的其他节点广播心跳包，昭告自己的存在。Follower 每次收到心跳包后就会主动将自己的选举定时器清零重置（reset）。因此如果 Follower 选举定时器超时，则意味着在 Raft 规定的一个选举超时时间周期内， Leader 的心跳包并没有发给 Follower（或者已经发送了但在网络传输过程中发生了延迟或被丢弃了），于是 Follower 就假定 Leader 已经不存在或者发生了故障，于是会发起一次新的选举。
如果一个 Follower 决定开始参加选举，那么它会执行如下步骤：
- 将自己本地维护的当前任期号（current term id）加 1。
- 将自己的状态切换到候选人（Candidate），并为自己投票。也就是说每个候选人的第一张选票来自于自己。
- 向其所在集群中的其他节点发送 RequestVote RPC ( RPC 消息会携带 “current term id”值），要求它们投票给自己。
一个候选人有三种状态迁移的可能性：
- 得到大多数节点的选票（包括自己），成为 Leader 。
- 发现其他节点赢得了选举，主动切换回 Follower 。
- 过了一段时间后，发现没有人赢得选举，重新发起一次选举。
分别详细讲述三种情况：
- 第一种场景：一个候选人如果在一个任期内收到了集群中大多数 Follower 的投票，就算赢得了选举。在一个任期内，一个 Raft 节点最多只能为一个候选人投票，按照先到先得的原则，投给最早来拉选票的候选人。“选举安全性原则”使得在一个任期内最多有一个候选人能够赢得选举。一旦某个候选人赢得了选举，它就会向其它节点发送心跳信息来建立自己的领导地位。
- 第二种场景：当一个候选人在等待其他人的选票时，它有可能会收到来自其他节点的，声称自己是领导人的心跳包（其实就是一个空内容的 AppendEntries RPC ）。此时，这个候选人会将信将疑地检查包含在这位“领导人” RPC 中的任期号：如果比自己本地维护的当前任期要大，则承认该领导人合法，并且主动将自己的状态切换回 Follower；反之，候选人则认为该“领导人”不合法，拒绝此次RPC ，并且返回当前较新的那个任期号，以便让“领导人”意识到自己的任期号已经过时了，该节点将继续保持候选人状态不变。
- 第三种场景：一个候选人既没有赢得选举也没有输掉选举。如果多个 Follower 在同一时刻都成了候选人，那么选票可能会被多个候选人平分，这就使得没有哪个候选人能够获得超过半数的选票。当这种情形发生时，显然不能一直这样“僵持下去”，于是 Raft 的每一个候选人又都设置了超时时间，发生超时后，每个候选人自增任期号（Term＋＋）并且发起新一轮的拉选票活动。然而，如果没有其他手段来分配选票的话，选票均分的情况可能会无限循环下去（理论上存在这种可能性，还记得FLP 不可能性定理吗） 。为了避免发生这种问题， Raft 采用了一种非常简单的方法一一随机重试。例如，设置一个区间（150～300ms），超时时间将从这个区间内随机选择。错开发起竞选的时间窗口，可以使得在大多数情况下只有一个节点会率先超时，该节点会在其他节点超时之前赢得选举，并且向其他节点发送心跳信息。要知道，在每次选票打平时都会采用这种随机的方式，因此连续发生选票被均分的概率非常小。
日志复制
一次正常的 Raft 日志的复制流程:
1) 客户端向 Leader 发送写请求 2) Leader 将写请求解析成操作指令追加到本地日志文件中 3) Leader 为每个 Follower 广播 AppendEntries RPC 4) Follower 通过一致性检查，选择从哪个位置开始追加 Leader 的日志条目 5) 一旦日志项提交成功， Leader 就将该日志条目对应的指令应用（apply)到本地状态机，并向客户端返回操作结果。 6) Leader 后续通过 AppendEntries RPC 将已经成功（在大多数节点上）提交的日志项告知 Follower。 7) Follower 收到提交的日志项之后，将其应用至本地状态机。
从上面的步骤可以看出，针对 Raft 日志条目有两个操作，提交（commit)和应用（apply），应用必须发生在提交之后，即某个日志条目只有被提交之后才能被应用到本地状态机上。
一旦某个领导人赢得了选举，那么它就会开始接收客户端的请求。每一个客户端请求都将被解析成一条需要复制状态机执行的指令。领导人将把这条指令作为一条新的日志条目加入它的日志文件中，然后并行地向其他 Raft 节点发起 AppendEntries RPC ，要求其它节点复制这个日志条目。当这个日志条目被“安全”地复制之后， Leader 会将这条日志应用（apply ，即执行该指令）到它的状态机中，并且向客户端返回执行结果。如果 Follower 发生错误，运行缓慢没有及时响应 AppendEntries RPC，或者发生了网络丢包的问题，那么领导人会无限地重试 AppendEntries RPC （甚至在它响应了客户端之后），直到所有的追随者最终存储了和 Leader 一样的日志条目。
在图中，日志由有序编号的日志条目组成。每一个日志条目一般均包含三个属性： 整数索引（log index）、任期号（term）和指令（command）。每个条目所包含的整数索引即该条目在日志文件中的槽位。term 是指其被领导人创建时所在的任期号，对应到图中就是每个方块中的数字，用于检测在不同的服务器上日志的不一致性问题。指令即用于被状态机执行的外部命令（对应到图中就是x←3,y←l 等）。如果某个日志条目能够被状态机安全执行，就认为是可以被提交（committed）了。
领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的。Raft 算法保证可被提交的日志条目是持久化的，并且最终是会被所有状态机执行的。一旦领导人创建的条目在当前任期内被复制到半数以上的节点上了，那么这个条目就称为可被提交的。
领导人日志中的所有条目都是可被提交的，包括之前的领导人创建的日志条目。领导人跟踪记录他所知道的被提交日志条目的最大索引值，并且这个索引值会包含在他向其他节点发送的AppendEntries RPC 中，目的就 是让其他节点知道该索引值对应的日志条目已经被提交。由于领导人广播的心跳包就是一个内容为空的AppendEntries RPC ，因此其他节点也能通过领导人的心跳包获悉某个日志条目的提交情况。一旦Follower 得知某个日志条目已经被提交，那么它会将该条日志应用至本地的状态机（按照日志顺序）。
Raft 算法设计了以下日志机制来保证不同节点上日志的一致性:
- 如果在不同的日志中两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
- 如果在不同的日志中两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。
第一条特性的满足条件在于，领导人在一个任期里在给定的一个日志索引位置上最多创建一条日志条目，同时该条目在日志文件中的槽位永远也不会改变。
第二条特性的满足条件在于， AppendEntriesRPC 有一个简单的一致性检查。领导人在发送一个 AppendEntries RPC 消息试图向其他节点追加新的日志条目时，会把这些新日志条目之前一个槽位的日志条目的任期号和索引位置包含在消息体中。如果 Follower 在它的日志文件中没有找到相同的任期号和索引的日志，它就会拒绝该 AppendEntries RPC ，即拒绝在自己的状态机中追加新日志条目。
用归纳法证明：初始化时空日志文件一定是满足日志匹配原则的，一致性检查保证了向日志文件追加新日志条目时的日志匹配原则。因此，只要某个 Follower 成功返回 AppendEntries RPC ，那么领导人就能放心地认为他的日志与该 Follower 的已经保持一致了。
当一个新的 Leader 被选举出来时，它的日志与其他的 Follower 的日志可能是不一样的。这时就需要一个机制来保证日志是－致的。产生一个新 Leader 时，集群状态可能如下图所示。
一个格子代表一个日志条目，格子中的数字是它对应的任期号。假设最上面的那个是领导人， a～f 是可能出现的 Follower 的日志，那么 a～f 所代表的场景分别如下：
- a 和 b 表示 Follower 丢失一些日志条目的场景
- c 和 d 表示 Follower 可能多出来一些未提交的条目的场景
- e 和 f 表示上述两种情况都有的场景
丢失的或者多出来的条目可能会持续多个任期。举个例子，场景 f 会在如下情况下发生：如果一台服务器在任期 2 时是领导人，并且其向他自己的日志文件中追加了一些日志条目，然而在将这些日志条目提交之前系统出现了故障。但是他很快又重启了，选举成功继续成为任期 3 的领导人，而且又向他自己的日志文件中追加了一些日志条目。但是很不幸的是，在任期 2 和任期 3 中创建的日志条目在被提交之前又出现了故障，并且在后面几个任期内也一直处于故障状态。
一般情况下， Leader 和 Follower 的日志都是保持一致的，因此 AppendEntries RPC 的一致性检查通常不会失败。然而，如果领袖节点在故障之前没有向其他节点完全复制日志文件中的所有条目，则会导致日志不一致的问题。在 Raft 算法中， Leader 通过强制Follower 复制它的日志来处理日志不一致的问题。这就意味着， Follower 上与Leader 的冲突日志会被领导者的日志强制覆写。这在添加了一个额外的限制之后其实是安全的，下文会详细说明其中的原因。
为了让 Follower 的日志同自己的保持一致， Leader 需要找到第一个 Follower 与它的日志条目不一致的位置，然后让 Follower 连续删除该位置之后（包括该位置）所有的日志条目，并且将自己在该位置（包括该位置）之后的日志条目发送给 Follower 。
那么， Leader 是如何精准地找到每个 Follower 与其日志条目不一致的那个槽位的呢？这些操作都会在AppendEntries RPC 进行一致性检查时完成。 Leader 为每一个 Follower 维护了一个 nextIndex ，它表示领导人将要发送给该追随者的下一条日志条目的索引。当一个 Leader 赢得选举时，它会假设每个 Follower 上的日志都与自己的保持－致，于是先将 nextlndex 初始化为它最新的日志条目索引数 ＋1 。在上图所示的例子中，由于 Leader 最新的日志条目 index 为 10 ，所以 nextlndex 的初始值是 11 。
当 Leader 向 Follower 发送 App endEntries RPC 时，它携带了（ term_id, nextIndex-1 ）二元组信息， term id 即 nextindex-1 这个槽位的日志条目的 term 。Follower 接收到 AppendEntries RPC 消息后， 会进行一致性检查， 即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就向 Leader 返回 AppendEntries RPC 失败。如果返回失败信息，就意味着 Follower 发现自己的日志与领导人的不一致。在失败之后，领导人会将 nextIndex 递减(nextlndex－－），然后重试AppendEntries RPC ， 直到 AppendEntries RPC 返回成功为止。这才表明在 nextIndex 位置的日志条目中领导人与追随者的保持一致。这时，Follower 上 nextIndex 位置之前的日志条目将全部保留，在此之后（与 Leader 有冲突）的日志条目将被 Follower 全部删除，并且从该位置起追加 Leader 上在 nextIndex 位置之后的所有日志条目。因此，一旦 AppendEntries RPC 返回成功， Leader 和 Follower 的日志就可以保持一致了。
以上即Raft 日志的一致性检查的全过程，下面将以上图中的 Leader 和 b 节点为例，举例说明日志一致性检查 Leader 和 Follower 之间的交互过程。
首先， Leader 的 nextIndex 的初始值为 11, Leader 向 b 发送 AppendEntries RPC(6,10 ）。然而，b 在自己日志文件的 10 号位置没有找到 term 为 6 的日志记录（因为b 根本就没有10 号日志项），于是 b 向 Leader 返回了一个拒绝消息。接着， Leader 将 nextIndex 减 1 ，变成 10 ，然后继续向 b 发送 AppendEntriesRPC(6,9), b 在自己日志文件的 9 号位置同样没有找到 term 为 6 的日志记录。(6,8), (5,7), (5,6), (4,5 ）这样依次循环下去都没有找到相应的日志记录，直到发送了（ 4,4)， b 才在自己日志文件的第 4 号位置找到了 term 为 4 的日志记录，于是接受了 Leader 的 AppendEntries RPC 请求，并将自己的日志文件中从 5 号位置开始的日志记录全部删除。随后， Leader 就从 5 号位置开始把余下的所有日志条目一次性推送给b(5～10）。
Raft 算法的日志复制机制，使得 Leader 和 Follower 只需要调用和响应 AppendEntries RPC 即可让集群内节点的各复制状态机的日志逐渐地趋于一致，而无须再采取额外的措施。一个领导人从来不会删除自己的日志（包括前任领导人创建的日志），也不会被别人覆盖日志。
Raft 算法的日志复制机制表明：只要集群中的大部分节点是正常的，那么 Raft 算法就能接受客户端复制日志的请求，并将其复制到各节点上且应用(Apply）到各节点的复制状态机上。通常情况下，一次AppendEntries RPC 就能完成一条新的日志条目在集群内的大多数节点上的复制。而且 Raft 只要求日志条目在大多数节点上完成复制就算提交成功，因此速度较慢的 Follower 并不会影响整体的日志复制性能。
即使日志条目被半数以上的节点写盘（复制）了，也并不代表它已经被提交（ commited ）到Raft 集群了一因为一旦某条日志被提交，那么它将永远没法被删除或修改。这个例子同时也说明了，领导人无法单纯地依靠之前任期的日志条目信息判断它的提交状态。
