为了实现进程高可用，我们可以对进程进行备份，而实现进程的主从备份主要有两种方法：
- State Transfer（状态转移）：主服务器将完整的状态内容都传输给备份服务器
- Replicated State Machine（备份状态机）：将需要备份的服务器视为一个确定性状态机 —— 主备以相同的状态启动，以相同顺序导入相同的输入，最后它们就会进入相同的状态、给出相同的输出
其中 Replicated State Machine 是较为常用的主从备份实现方式。常见的 Replicated State Machine 架构如下：
- 客户端向服务发起请求，执行指定操作
- 共识模块将该操作以日志的形式备份到其他备份实例上
- 当日志安全备份后，指定操作被应用于上层状态机
- 服务返回操作结果至客户端
在 Replicated State Machine 中，分布式共识算法的职责就是按照固定的顺序将指定的日志内容备份到集群的其他实例上。
Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。在领导者将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交。同时，领导者的日志中之前的所有日志条目也都会被提交，包括由其他领导者创建的条目。
领导者处理不一致是通过强制跟随者直接复制自己的日志来解决的。这意味着在跟随者中的冲突的日志条目会被领导者的日志覆盖。
Raft集群
一个Raft集群由若干节点组成，节点可能处于以下三种角色的其中之一：Leader、Follwer或Candidate，职责如下：
- Leader负责从客户端处接收新的日志记录，备份到其他服务器上，并在日志安全备份后通知其他服务器将该日志记录应用到位于其上层的状态机上。
- Follower接收来自Leader和Candidate请求，自身不会发出任何请求
- Candidate会在Leader选举时负责投票选出Leader
Raft性质
- Election Safety（选举安全）：在任意给定的 Term 中，至多一个节点会被选举为 Leader。
- Leader Append-Only（Leader 只追加）：Leader 绝不会覆写或删除其所记录的日志，只会追加日志。
- Log Matching（日志匹配）：若两份日志在给定 Term 及给定 index 值处有相同的记录，那么两份日志在该位置及之前的所有内容完全一致
- Leader Completeness（Leader 完整性）：若给定日志记录在某一个 Term 中已经被提交，那么后续所有 Term 的 Leader 都将包含该日志记录
- State Machine Safety（状态机安全性）：如果一个服务器在给定 index 值处将某个日志记录应用于其上层状态机，那么其他服务器在该 index 值处都只会应用相同的日志记录
Raft设计
Raft 的设计分为几个关键部分：服务器状态（State）、请求****投票 RPC（RequestVote RPC）、追加日志条目 RPC（AppendEntries RPC） 和 服务器行为规则（Rules for Servers）。
服务器状态（State）
这部分描述了 Raft 中每个服务器（节点）需要维护的状态信息，分为持久化状态和易失性状态。
持久化状态：
currentTerm：当前服务器所知的最新任期号（从0开始，单调递增）。用于检测过时的通信。
votedFor：在当前任期中投给哪个候选者（candidate）的票；如果没有投票则为 null。（保证同一个任期内每个服务器只能投一次票，防止重启后在同一个任期内投票给其他server）
log[]：日志条目数组，每个条目包含命令和接收该命令时的任期号。索引从1开始。
易失性状态：
commitIndex：已知被提交的最高日志条目索引（初始为0，单调递增）。表示哪些日志已安全复制并可应用。
lastApplied：最高已被应用到状态机的日志条目索引（初始为0，单调递增）。
Leader维护状态（易失）：
nextIndex[]：对每个跟随者（follower），下一个要发送给它的日志条目的索引（初始为 leader 最后日志索引 + 1）。
matchIndex[]：对每个跟随者，已知在该 follower 上成功复制的最高日志条目索引（初始为0，单调递增）。
请求投票RPC（RequestVote RPC）
这是候选者（Candidate）发起选举时调用的 RPC，用于收集选票。
参数：
term： 候选者的当前任期。candidateId: 请求投票的候选者 ID。lastLogIndex: 候选者最后一个日志条目的索引。lastLogTerm: 候选者最后一个日志条目的任期。
返回结果：
term: 接收方的当前任期（供候选者更新自身任期）。voteGranted: 是否授予投票（true 表示同意）。
接收方实现逻辑：
- 如果请求的
term < currentTerm，返回 false（拒绝旧任期的请求）。 - 如果
votedFor是 null 或等于candidateId，且候选者的日志至少与接收方一样新（即日志更完整或一致），则授予投票。
追加日志条目RPC（AppendEntries RPC）
由 Leader 发起，用于复制日志条目到 Follower。也作为心跳（heartbeat）使用。
参数：
term: Leader 的当前任期。leaderId: Leader 的 ID（Follower 可据此重定向客户端请求）。prevLogIndex: 要添加的新日志条目前一个日志条目的索引。prevLogTerm: 上述日志条目的任期。entries[]: 要追加的日志条目列表（可以为空，用于心跳）。leaderCommit: Leader 的 commitIndex。
返回结果：
term: 接收方的当前任期。success: 是否成功（即是否匹配 prevLogIndex 和 prevLogTerm）。
接收方实现逻辑：
- 若
term < currentTerm，返回 false。 - 若日志中没有
prevLogIndex对应的条目，或其任期不符，返回 false。 - 若已有相同索引但不同任期的日志条目，则删除该条目及之后所有条目（保持一致性）。
- 添加新的日志条目（不在本地日志中的）。
- 若
leaderCommit > commitIndex，则设置commitIndex = min(leaderCommit, 最后一条新日志的索引)，并应用日志。（prevLogIndex+len(entries)）
服务器行为规则（Rules for Servers）
这部分列出了每种角色（Follower、Candidate、Leader）的行为规则。
所有服务器通用规则：
- 若
commitIndex > lastApplied，则递增lastApplied并将对应日志应用到状态机。 - 若收到的 RPC 包含比当前更大的
term，则更新currentTerm并转为 Follower。
Follower规则：
- 响应来自 Candidate 和 Leader 的 RPC。
- 若选举超时未收到 AppendEntries RPC 或未授权投票，则转为 Candidate。
Candidate规则：
- 开始选举时：
- 增加
currentTerm - 投票给自己
- 重置选举计时器
- 向所有其他服务器发送 RequestVote RPC
- 增加
- 若获得多数票 → 成为 Leader
- 若收到 AppendEntries RPC → 转为 Follower
- 若选举超时 → 重新开始选举
Leader规则
- 选举成功后：
- 发送空的 AppendEntries（心跳）给所有 Follower，防止超时。
- 收到客户端命令：
- 添加到本地日志，然后应用到状态机。
- 若某个 Follower 的
lastIndex >= nextIndex：- 发送从
nextIndex开始的日志条目。 - 成功则更新
nextIndex和matchIndex。
- 发送从
- 若 AppendEntries 失败（因日志不一致）：
- 减少
nextIndex并重试。
- 减少
- 若存在某个索引 N > commitIndex，且大多数 Follower 的
matchIndex[i] >= N且log[N].term == currentTerm：- 设置
commitIndex = N
- 设置
Leader选举
在初次启动时，节点是Follower角色，如果它一直能够收到Leader节点发出的RPC请求，他就会一直处于Follower角色，如果接收不到来自 Leader 的通信，Follower 会等待一个称为 Election Timeout（选举超时）的超时时间，然后便会开始发起新一轮选举。Follower 发起选举时会对自己存储的 Term ID 进行自增，并进入 Candidate 状态。随后，它会将自己的一票投给自己，并向其他节点并行地发出 RequestVote RPC 请求。当 Candidate 在某个 Term 接收到来自集群中大多数节点发来的投票时，它便会成为 Leader，然后它便会向其他节点进行通信，确保其他节点知悉它是 Leader 而不会发起又一轮投票。
若选举发生平局情况或没有任何一个节点收到大多数节点的票，此时节点在等待Election Timeout后发起新一轮选举。每个节点的election Timeout 的取值是随机的。
日志备份
Leader将接收到的客户端命令以日志记录的形式追加到自己的记录里，并通过 AppendEntries RPC 备份到其他节点上；
Leader 在进行 AppendEntries RPC 调用时会同时携带新日志记录之前的日志记录的 index 值及 Term ID；如果 Follower 在自己的日志存储中没有找到这条日志记录，那么 Follower 就会拒绝这条新记录，Leader 会不断重试 AppendEntries RPC 调用，确认它与各个follower所能相互统一的最后一条日志记录的index值，然后会将follower在该index之后的所有日志删除，再将自身存储的日志记录备份到follower上
当某个日志记录顺利备份到集群的大多数节点上后，Leader便会认为该日志记录已提交Committed，即该日志记录可被安全的应用到上层状态机上。
日志压缩（compaction）
随着raft集群的不断运行，节点上的日志体积会不断增大，这会逐渐占用节点的磁盘资源，此外过长的日志也会延长节点重放日志的耗时引入服务可用性问题。为此，集群需要对过往的日志进行压缩。
快照是进行日志压缩最简便的方案。在进行快照时，状态机当前的完整状态会被写入到持久存储中，而后就能够安全地把直到该时间点以前的日志记录移除了。完成快照后，Raft 也会在快照中记录其所覆盖到的最新日志记录的 index 和 Term ID，以便后面的日志记录能够被继续追加。每个节点会独立地生成快照，避免传输快照占用网络带宽。当某个Follower落后太多或者新加入的节点，Leader仍然会将自己持有的快照传输给Follower。
注意点
- Follower在处理AppendEntries时，如果Follower的日志在prevLogIndex处不存在，或者其存在但是term≠prevLogTerm，返回success=false，并不会直接截断日志，此时Leader会在下一次重试时发送更早的日志（减小nextIndex），直到找到一个匹配点。只有当
prevLogIndex和prevLogTerm都匹配时，Follower 才会删除prevLogIndex之后的所有日志，追加entries[]中的新条目。所以截断日志的前提不只是preLogIndex，还需要确认prevLogTerm匹配。 - 只有在以下三种情况重置选举定时器：
- 收到来自当前领导只的AppendEntriesRPC（若该RPC任期已过期，则不应重置）
- 自己启动一次选举
- 你向另一个节点授予了投票（接收到投票请求时不重置）
- 如果你当前已经是候选人（即正在运行一次选举），但选举定时器再次触发，你应当启动新一轮选举
- 如果 RPC 请求或响应中包含的任期 T 大于当前节点的
currentTerm，则必须将currentTerm设置为 T，并立即转为 Follower 状态，若不更新currentTerm，则节点有可能误以为自己在本任期内已经投过票，导致无法正确推进 - 究竟该如何基于一个复制日志（replicated log）来实现一个应用程序?正确的做法是将你的服务设计为一个状态机（state machine），其中客户端的操作会驱动状态机从一个状态转移到另一个状态。你应该在某处维护一个循环（通常称为“applier loop”），每次取出一条客户端操作（所有服务器上都以相同的顺序取出——这正是 Raft 所保证的），并按顺序将每条操作应用到状态机上。这意味着，面向客户端的 RPC 方法只需将客户端的操作提交给 Raft，然后等待这个“applier 循环”将其应用。只有当轮到该客户端命令被处理时，才真正执行它，并读取返回值——注意，这同样适用于读请求！
- 如何知道某个客户端操作何时完成？一种简单的解决方案是：在将客户端操作插入 Raft 日志时，记录下它被写入的具体日志索引（index）。当该索引处的日志条目被传递给
apply()时，你可以检查实际应用的操作是否就是你当初写入的那一个。如果是，说明操作成功；如果不是（例如被其他 Leader 覆盖了），就说明发生了故障，此时便可向客户端返回错误，提示其重试**。同一个日志索引在不同时间可能对应完全不同的命令。因此，仅靠索引无法唯一标识一个客户端请求；** - 一旦你允许客户端在遇到错误时重试操作，就必须引入某种重复请求检测机制（duplicate detection scheme）。例如，如果一个客户端向你的服务器发送了一个
APPEND请求，但没有收到响应，于是又将相同的请求重新发送给另一个服务器，那么你的apply()函数必须确保这个APPEND操作不会被执行两次。为此，你需要为每个客户端请求分配某种唯一标识符，以便判断自己是否曾经见过——更重要的是，是否已经应用过——该操作。此外，这一去重状态必须成为你状态机的一部分，这样才能保证所有 Raft 服务器对重复请求做出一致的处理。可以为每个客户端分配一个唯一的客户端ID，让客户端发送的每个请求附带一个单调递增的序列号，重发请求采用相同的序列号，服务器维护为每个客户端已处理过的最大序列号。