fzdwx

Lab2 文档翻译#

由于我的英文不是很好，所以使用翻译软件进行翻译，然后人工进行校对进行理解.

original 地址: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html

Introduction#

这是一系列实验中的第一个，我们将构建一个 fault-tolerant key/value storage system.
在本实验中我们将实现 Raft (一种复制的状态机协议). 在下一个实验中，我们将在 Raft 上构建一个 key/value service.
然后，您将在有多个副本的状态机上进行 shard (分片？根据 key 进行 hash 来决定路由到哪个副本上) 来提高性能.

复制 (replication) 通过在多个复制服务器上存储其状态 (即数据) 的完整副本来实现 fault tolerance.
即使有一些服务器出现 failure (崩溃或网络断开和抖动) replication 也允许它们继续运行。挑战在于 failures 可能导致副本存在不同的数据.

Raft 将客户端的请求组织成一个序列，被称为 log , 并且确保所有 replica servers 看到相同的 log.
每个 replica 按照日志的顺序来执行客户端的请求，将它们应用于其本地的服务状态副本 (就是运行来自客户端的命令).
由于所有存活的副本读取的日志内容都是相同的，所以都以相同的顺序来执行请求，因此它们都有相同的服务状态.
如果一个服务器发生了 failure 但是后来又 recovery (恢复) 了，Raft 会负责将它的 log 更新到最新状态。只要至少大多数的服务器还活着，并且能够继续通信，
那么 Raft 将持续运行。如果没有到达这个数量，那么 Raft 将会停止运行，直到达到这个数量才会重新开始运行.

在本 lab 中，你将把 Raft 实现为一个带有相关方法的 GO 的对象类型，目的是为了能在更大的模块中使用.
一组 Raft 实例通过 RPC 来维护 replicated logs. 你的 Raft 实例将支持一连串不确定编号的 command,
也可以叫 log entries. 这些 entity 通过 index (索引) 来进行编号。具有给定索引的 log entry 将被 commit,
此时，您的 Raft 应该将这条 log 发送到 larger service 上执行.

你应该遵循extended Raft paper中设计，
特别是图 2. 你将实现论文中的大部分内容，包括保存持久化状态和节点故障自动重启后读取状态.
你将不会实现集群成员的变化 (Section 6).

你可能会发现这个指南很有用，
还有这个关于 concurrency 的锁
和结构的建议，
如果需要更广泛的视角，可以看看 Paxos,Chubby,Paxos Made Live,Spanner,Zookeeper,Harp,Viewstamped Replication
和Bolosky et al.

请记住，本 lab 中最具挑战性的部分可能不是实现你的解决方案，而是调试它。为了帮助应对这一挑战，你可能需要把事件花在如何使你的实现更容易调试.
你可以参考指导页和这篇关于有效打印声明的博文.

我们还提供了Raft 交互图,
可以帮助阐明 Raft 代码如何与上层 (使用者？) 交互.

The code#

通过向raft/raft.go添加代码来实现 Raft. 在该文件中，你会发现骨架代码，以及如何发送和接收 RPC 的例子.
你的实现必须支持以下接口，测试者和 (最终) 你的 key/value service 将使用该接口。你可以在raft.go的注释中找到更多细节.

{{< block type="tip">}}
Raft 实例只能通过 rpc 进行通信且必须使用labrpc这个包 (例如不能使用文件以及共享变量).
{{< /block >}}

// create a new Raft server instance:
rf := Make(peers, me, persister, applyCh)

// start agreement on a new log entry:
rf.Start(command interface{}) (index, term, isleader)

// ask a Raft for its current term, and whether it thinks it is leader
rf.GetState() (term, isLeader)

// each time a new entry is committed to the log, each Raft peer
// should send an ApplyMsg to the service (or tester).
type ApplyMsg

Make#

Make(peers []*labrpc.ClientEnd, me int,persister *Persister, applyCh chan ApplyMsg)

用于创建 Raft server.

1. 所有的 raft server 的端口都在peers[]存放 (包括当前的服务), 当前服务的端口可以通过peers[me]来获取.
2. 所有的服务的perrs[]数组都具有相同的顺序.
3. presister是一个用来存放persistent state的地方，并且在初始的时候会保存最具的状态，如果有.
4. applyCh是 service 或 tester 发送消息给 raft 的通道.Make()
   必须快速返回，所以它应该为一些长时间运行的任务启动goruntines.

Start#

使用 Raft 的服务（例如 kv 服务器）希望就下一个要附加到 Raft 日志的命令开始协议。如果此服务器不是领导者，则返回
false. 否则启动协议并立即返回。无法保证此命令将永远提交到 Raft 日志，因为领导者可能会失败或失去选举。即使 Raft
实例被杀死，这个函数也应该优雅地返回。第一个返回值是该命令在提交时将出现的索引。第二个返回值是当前术语。如果此服务器认为它是领导者，则第三个返回值为
true.

Start(command interface{}) (int, int, bool)

使用 Raft 的服务 (e.g k/v server) 希望就下一个要追加到 Raft 日志的命令开始协议.
如果当前 Raft server 不是 leader 则返回false. 否则启动协议并立即返回，无需等待日志追加完成.
所以无法保证此命令将一定会被提交到 Raft 日志中，因为 leader 可能会失败或者在输掉选举.
即使 Raft 实例被 kill 这个函数也应该 return gracefully (优雅返回).

第一个返回值是该命令在 commit 时将被设置的 index. 第二个返回值是当前的 term (任期). 如果此服务器认为自己是 leader
则第三个返回值是true.

每个新提交的Raft log entity都应该发送一个AppliMsg到Make()的applyCh中.

2A - Leader Election#

实现 Raft leader election 以及 heartbeats (AppendEntries RPCs中不附带 log entries).

2A 的目标是：选出一个 leader, 如果没有 failure, 它仍然是 leader,
如果 old leader 失败或者与 old leader 之间的数据包发生丢失则由 new leader 接管.

{{< block type="tip">}}
这个失败是 leader 出现故障的意思？就是说只要它没出现运行故障或者网络问题就永远是 leader？
{{< /block >}}

要点:

1. 通过运行go test -run 2A来进行测试你的实现.
2. 按照论文的图 2, 主要关心发送和接收RequestVote RPCs
   , 与the Rules for Servers that relate to elections
   以及the State related to leader election.
3. 添加图 2中与 leader election 相关的状态到Raft这个结构体中，且还需要定义一个结构来保存每个日志的信息.
4. 实现RequestVote(), 这样 raft 服务们就能互相投票了。添加RequestVOteArgs和RequestVoteReply者两个结构体。修改Make()
   , 创建一个 goroutine, 用于检查心跳消息，如果有一段时间没有收到 peer 的消息时将发送RequestVote RPCs来定期发起领导者选举。这样，如果有
   leader 了，peer 将知道谁是 leader, 或者自己成为 leader.
5. 实现心跳，需要定义一个AppendEntries RPC结构 (尽管你可能还不需要所有参数),
   并且让 leader 定期发送它。编写一个AppendEntries RPC的 handle method, 用于重置选举超时，
   这样当有一个人已经当选时，其他服务器不会又成为 leader.
6. 确保不同 peer 的选举超时不在同一时间发生，否则所有 peer 将只为自己投票，这样就没有人会成为 leader 了.
7. 在测试时，leader 每秒发送的 RPC 请求不能超过 10 次.
8. 在测试时，要求 Raft 在 old leader 失败后 5 秒内选举 new leader (如果大多数节点仍然能继续通讯).
   但是请记住，如果出现split vote(如果数据包丢失或者候选人选择了相同的随机退避时间就有可能发生),leader 选举可能需要多轮.
   所以必须设置足够短的选举超时 (也就是心跳间隔), 即使会选举多轮，也有可能在 5 秒内完成.
9. 论文的Leader election这一节中提到的选举超时范围是 150 到 300 毫秒.
   只有当 leader 发送心跳的频率大大高于 150 毫秒一次时，上面提到的范围才有意义。由于在测试时限制每秒 10 次心跳，
   所以必须使用比论文中更大的选举超时时间，但是不能太大，因为可能会无法在 5 秒内完成选举.
10. 如果您的代码无法通过测试，请再次阅读论文中的图 2,leader 选举的全部逻辑分布在图中多个部分.
11. 不要忘记实现GetState().
12. 在测试时，如果要关闭一个 raft 实例，会调用rf.kill(). 我们可以调用rf.killed来检查是否被调用了kill(). 您可能希望在所有的循环中都这样
    做，以避免死亡的 Raft 实例打印混乱的信息.
13. go RPC只发送名称以大写字母开头的结构体字段。子结构体也必须拥有大写的字段名.

2B - log#

实现 leader 以及 follower 的代码来添加新的日志.

要点:

1. 你的首要目标就是通过TestBasicAgree2B. 从实现Start()开始，根据图 2, 编写代码，
   通过AppendEntries发送和接收新的日志。发送最近提交的日志到对方的applyCh中
2. 需要实现election restriction
3. 在早期的 Lab 2B 测试中未能达成协议的一种方法是：即时 leader 还存活也要重复进行选举.
   在 election timer 中找 bug, 或者在赢得选举后不立即发送心跳的问题.
4. 你的代码中可能有重复检查某些事件的循环。不要让这些循环连续的的执行而没有暂停，这将使你的实现慢到无法通过测试.
   使用 Go 的condition variables 或者加入 `time.sleep (10 * Millisecond) 在每个循环中.
5. 读懂config.go以及test_test.go以便了解在测试什么内容.

代码实现思路#

大概记录一下代码的实现思路以及遇到的问题.

2A#

1. 根据图 2 中的 state 这一节添加对应的属性
2. 添加RaftRole属性，代表当前的角色: leader,candidate,follower
3. 实现ticker这个函数:
   • 可以使用两个time.timer来作为触发器
   • 判断是否很久没有收到心跳，来发起选举
   • 判断是否需要发送心跳，来维持自己的权威
4. 这个时候要注意这条规则: 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm, 则 currentTerm 赋值为 T,
   并切换状态为 follower.
5. 实现发起选举的流程
   • 根据图 2 中的Rules for Servers的candaidte流程一步一步实现
   • 并行发起RequestVote RPC, 如果票数大于 1/2 则转换为 leader (可能需要广播心跳).
6. 实现RequestVote
   • 根据图 2 中的RequestVote RPC一步一步实现就好
7. 实现AppendEntries
   • 只需要简单的实现转换为 follower 以及刷新选举超时时间即可.
8. 所有节点收到响应后刷新选举超时时间 (具体情况具体判断)
9. 成为 leader 后开始刷新心跳超时时间 (来刷新 follower 的选举超时时间)

遇到的问题:

1. 第一个测试会有warning: Term changed even though there were no failures出现

就是在有一个 leader 的时候其他 follower 还是发起了选举。猜测原因是election timeout和AppendEntries的时间点很邻近，这个只能调试
两种超时时间，我的选举超时时间是 200~350ms, 心跳固定在 125ms.

然后我在转换角色的时候加了一个if new role == old role then return的判断，这里导致election timeout没有刷新.

2. 在响应或请求时要第一时间处理第 4 条.

Raft 论文翻译#

选取一些重要的片段进行翻译

original 地址: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf

Abstract#

Raft 是一种为了管理复制日志的共识算法。它提供了和 Paxos 算法相同的功能和性能，但它的算法结构和 Paxos 不同，
Raft 更容易理解并且更容易构建实际的系统。为了提升可理解性，Raft 将共识算法分成了几个关键的模块，例如领导人选举，日志复制和安全性.
同时它通过实施一个更强的一致性来减少需要考虑的状态的数量.Raft 还包括一个机制来允许集群成员的动态改变，它利用重叠的大多数来保证安全性.

Introduction#

Raft 算法和已经存在的共识算法在某些地方很相似 (主要是 Oki 以及 Liskov's Viewstamped Replication), 但是它有以下新特性:

• 强领导者: Raft 使用一种比其他共识算法更强的领导形式。例如，日志只从 leader 发送给其他服务器.
  这简化了对复制日志的管理并使得 Raft 更容易理解.
• 领导选举: Raft 使用随机的计时器来选取 leader. 这种方式仅仅是在所有共识算法都需要改进的心跳机制上有些许改进，然而这使得
  Raft 在解决冲突时更简单和快速.
• 成员调整: Raft 使用了新的联合共识 (join consensus) 算法来处理集群成员变换的问，
  在处于调整过程中的两种不同的配置的大多数集群会有重叠 (overlap), 这就允许集群在成员变更的时候，持续正常运行.

Replicated State Machine#

Replicated State Machine(复制状态机) 在分布式系统中被用于解决各种容错问题。例如 GFS、HDFS、RAMCloud 等单 leader 的大型集群系统，
通常使用独立的复制状态机来管理领导选举和存储配置信息来保证在 leader 崩溃的情况下也要存活下来，复制状态机的例子包括 Chubby
以及 Zookeeper.

共识算法是在复制状态机的背景下提出的，在这种方法中，在一组服务器上的状态机对同一个的状态会计算出相同的副本，并且在一些服务器宕机的情况下也可以继续运行.

如图一所示，复制状态机是通过复制日志实现的。每个服务器保存者一个包含一系列命令的日志，其状态机按照顺序来执行它们.
每个日志包含相同顺序的相同命令，所以每个状态机都执行相同的命令序列。因为状态机是确定的，所以每个状态机会计算出相同的状态和相同顺序的输出.

共识算法的任务是 保证复制日志的一致性。服务器上的共识模块接收来自客户端的命令并把它们添加到日志中，
并与其他服务器上的共识模块进行通讯以确保它们的每一条日志最终都相同 (相同的请求有相同的顺序), 即使有一些服务发生故障.
一旦命令被正确的复制，每一个服务的状态机会按照日志的顺序去处理它们，然后将结果返回给客户端.

因此，这些服务似乎成为了一个单一的，高度可靠的状态机.

在实际的共识算法通常有以下属性:

• 确保非拜占庭 (non-Byzantine) 条件下的安全性(永远不返回错误的结果), 包括网络延迟，分区以及网络数据包丢失、冗余、乱序.
• 只要大多数的服务都在运行并能相互通信且和客户端通信，它们就能发挥出全部的功能 (可用性). 因此，一个 5 台服务的集群能容忍 2 台服务出现故障.
  假定服务应为停机而出现故障，它们可能稍后会从stable storage中恢复状态并从新加入集群.
• 不依赖与时序来保证日志的一致性：错误的时钟和极端的信息延迟延迟在最坏的情况下会导致可用性问题.
• 在一般情况下，一个命令的完成在于集群中的大多数对单轮远程调用作出响应，少数比较慢的服务不会影响系统的整体性能.

The Raft consensus algorithm#

Raft 就是用于管理上一解描述的复制日志的算法.图 2
是对该算法的精简型式的总结，图 3列出来该算法的关键属性，接下来对这些部分进行逐一讨论.

Raft 通过选出一位 leader 然后给予它完全管理日志复制的责任来实现共识.leader 接收来自客户端的日志，然后复制给其他服务，并且通知在何时
它们可以安全的消费 (作用到状态机上) 这些日志.leader 简化了日志复制的管理。例如: leader 可以自主确定新日志存放在哪个位置而不用询问其他服务，
并且数据都从 leader 流向其他服务器.leader 可能会发生故障，或者和其他服务器失去连接，这个时候需要重新选举 leader.

基于 leader 的方法，Raft 将一致性问题为了三个子过程来解决:

• leader 选举：当 leader 失败 (宕机) 时需要选举新 leader
• 日志复制: leader 接收来自客户端的日志，并复制给集群中的其他机器，强制其他服务器与自己的一致
• 安全: Raft 的安全就在于图 3中的安全属性：如果任何服务器消费了一个日志，那么其他任何服务器就不
  能在相同的日志索引消费不同的日志

Figure 2#

state:

• 在所有服务器上持久化 (在响应 RPC 请求之前，已经更新到了稳定的存储设备)
  • currentTerm: 服务器已知最新的任期（在服务器首次启动时初始化为 0, 单调递增）
  • votedFor: 当前任期内收到选票的 candidate Id, 如果没有投给任何候选人则为空
  • log[]: 日志条目，每个条目包含了用于状态机的命令，以及领导人接收到该条目时的任期 (初始索引为 1)
• 所有服务器上的易失性状态
  • commitIndex: 已知的提交的日志中的最大索引 (初始 0, 单调递增)
  • lastApplied: 状态机已经执行的日志中的最大索引 (初始 0, 单调递增)
• 在 leader 上不稳定存在 (在每次重新选举后初始化)
  • nextIndex[]: 对于每一个服务器，发送到该服务器的下一个日志条目的索引 (初始为 leader 的最后一条日志索引 + 1)
  • matchIndex[]: 对于每一个服务器，已知的已经复制到该服务器的最高日志条目的索引 (初始 0, 单调递增)

AppendEntries RPC

由 leader 发起调用来复制日志，同时也用于心跳检测

• Arguments:
  • term: leader 的任期
  • leaderId: 用于 follower 找到 leader (有时 client 把请求发送给了 follower)
  • prevLogIndex: 紧邻新日志条目之前的那个日志条目的索引
  • prevLogTerm: 紧邻新日志条目之前的那个日志条目的任期
  • entries[]: 需要被保存的日志 (为空时是心跳检测，可能一次会发送多条来提升效率)
  • leaderCommit: leader 已提交的最高的日志条目的索引
• Results:
  • term: currentTerm, 用于 leader 更新自己的term
  • success: 如果 follower 的pervLogIndex以及prevLogTerm能够匹配上则为 true
• Receiver implementation:
  • if term < currentTerm then return false(如果 leader 的任期小于接收者的当前任期，接收者可以是 follower 以及
    candidate)
  • if log[prevLogIndex].term != prevLogTerm then return false(在接收者日志中 如果能找到一个和 prevLogIndex 以及
    prevLogTerm 一样的索引和任期的日志条目则继续执行下面的步骤否则返回假)
  • if log[oldIndex].term != log[newIndex].term then remove log[oldIndex,lastIndex](
    如果一个已经存在的日志与新的日志 (请求中的日志条目) 冲突 (索引相同，任期不同), 则删除该索引处以及之后的所有日志)
  • 添加在日志列表中不存在的新日志
  • if leaderCommit > commitIndex then commitIndex=min(leaderCommit,log[].last.commitIndex)(
    如果 leader 的已知已提交的最高日志条目的索引大于接收者的已知已提交最高日志条目的索引，则把接收者的已知已经提交的最高的日志条目的索引 commitIndex
    重置为 leader 的已知已经提交的最高的日志条目的索引 leaderCommit 或者是 上一个新条目的索引 取两者的最小值)

RequestVote RPC

候选人调用，收集选票

• Arguments:
  • term: candidate 的任期号
  • candidateId: 发起请求的 candidate 的 id
  • lastLogIndex: candidate 的最后一条日志的索引
  • lastLogTerm: candidate 最后一条日志对应的任期号
• Results:
  • term: 当前任期号，用于 candidate 更新自己的term
  • voteGranted: true 表示候选人获得了选票
• Receiver implementation:
  • if term < currentTerm then return false(如果 term < currentTerm 返回 false)
  • if (votedFor==null||votedFor==candidateId)&&(lastLogIndex,lastLogTerm)==log[].last then return true
    (如果 votedFor 为空或者与 candidateId 相同，并且候选人的日志和自己的日志一样新，则给该候选人投票)

Rules for Servers

• All Servers:
  • if commitIndex > lastApplied then incr lastApplied and exec log[lastApplied]（如果 commitIndex >
    lastApplied,lastApplied 自增，将 log [lastApplied] 应用到状态机）
  • if appendEntries.logs exist (log.term > currentTerm) then currentTerm = log.term and set status = follower(如果
    RPC 的请求或者响应中包含一个 term T 大于 currentTerm, 则 currentTerm 赋值为 T, 并切换状态为 follower)
• Followers:
  • 不会发出任何请求，只会对来自 candidates 以及 leader 的请求做出响应
  • 选举超时后，如果未收到当前 leader (term 相同) 的AppendEntries RPC或投票给了 candidate, 则转换为 candidate
• Candidates:
  • 转换成 candidate 之后开始选举
    • incr currentTerm
    • 投票给自己
    • reset election timer
    • 发送RequestVote RPC给其他所有服务器
  • 如果收到了多数的选票则成为 leader
  • 如果收到 new leader 的AppendEntries RPC则成为 follower
  • 如果选举超时则开始新一轮的选举
• Leaders:
  • 一旦成为 leader 则向其他服务器发送空的AppendEntries RPC, 在空闲时重复发送以防止选举超时
  • 如果收到来自 client 的命令：添加到本地日志，在执行并作用到状态机后作出响应给 client
  • 对于 follower if last log index >= nextIndex(最后日志条目的索引值大于等于 nextIndex):
    则通过AppendEntries RPC将 nextIndex 之后的所有日志都发送发送出去
    • 如果成功：将该 follower 的nextIndex以及matchIndex更新
    • 如果因为日志不一致导致失败: nextIndex递减并重新发送
  • 如果存在一个数 N, 满足N > commitIndex, 大多数的matchIndex[i] >= N
    以及log[N].term == currentTerm: set commitIndex = N

Figure 3#

• Election Safety: 在给定 term 内只能选出一个 leader
• Leader Append-Only: leader 永远不覆盖或删除日志，只会添加
• Log Matching: 如果两个日志在包含相同的 index 以及 term, 那么就认定它们完全相同
• Leader Completeness: 如果一条日志在给定的 term 内提交，那么它一定会出现在 term 更大的 leader 的日志中
• State Machine Safety: 如果一个服务器已经将给定索引位置的日志条目应用到状态机之中，则其他所有服务器不会在相同索引处出现不同的日志

Raft basics#

一个 Raft 集群可以包含多个服务器；5 是一个典型的数量，它允许系统容忍 2 次故障 (有两台服务宕机).
在给定的时间中每个服务都处在以下三种状态之一:
leader, follower, candidate. 正常情况下，恰好只有一个 leader, 所有其他服务器都是 follower.

• follower 是被动的：它们不会自己发出请求，而只是响应来自 leader 和 candidate 的请求.
• leader 处理所有 client 的请求 (如果 client 联系到 follower, 则 follower 重定向到 leader).
• candidate 用于选举出一个新的 leader (可以看图 4).

Figure 4#

如图 5 所示: Raft 将时间分为任意长度的 terms.terms 的编号是连续的整数。每一个 term 开始于 election, 一个或多个 candidate
尝试成为 leader. 如果一个 candidate 赢得了选举，那么它将在剩下的 term 内担任 leader.

在某些特殊情况下选举的结果是 split vote. 在这种情况下，term 将会结束并且没有 leader. 一个新的 term (伴随新一轮的选举) 将很快开始.
Raft 保证在给定的 term 内最多只有一个 leader.

Figure 5#

不同的服务器可能会在不同的时间观察到 term 之间的转换，在某些情况下，一个服务器可能不会观察到选举甚至整个 term 的全程.
term 在 Raft 中充当了逻辑时钟，term 使得可以服务器检测过时的信息：如过时的 leader.

每个服务器都存储一个当前的 term 编号，该编号随时间单调地增加。每当服务器进行通信时，就会交换当前 term；
如果一个服务器的当前 term 比另一个服务器的小，那么它就会将其当前 term 更新为较大的值.

如果一个 candidate 或 leader 发现它的 term 已经过时，它将立即恢复到 follower 的状态.

如果一个服务器收到的请求是一个过时的 term 编号，它将拒绝该请求.

Raft 服务器使用 RPC 进行通信，而基本的共识算法只需要两种类型的 RPC.RequestVote RPCs由 candidate 在选举期间发起；
AppendEntries RPCs由 leader 发起，用于复制日志条目并提供一种心跳机制。在下面的章节还增加了第三个 RPC, 用于在服务器之间传输快照.
如果服务器没有及时收到响应，它们会重试 RPC, 并且为了获得最佳性能，它们会并行地发出 RPC.

Leader election#

Raft 使用心跳机制来触发 leader 选举。当服务器启动时，初始状态都是 follower. 只要服务器收到来自 leader 或 candidate 的有效 RPC,
它就一直处于 follower 状态. leader 定期向所有 follower 发送心跳（AppendEntries RPCs, 不携带日志条目）, 以保持他们的权威.
如果 follower 在一段时间内没有收到任何通信 (election timeout), 那么它就认为没有可用的 leader, 并开始选举以选择一个新的
leader.

要开始一场选举，follower 要增加它的当前 term 并过转换到 candidate 状态.
然后，它为自己投票，并行的向集群中的每个其他服务器发出RequestVote RPCs.
candidate 将一直处于这种状态，直到发生以下三种情况之一:

1. 它赢得了选举
2. 另一个服务器确立了自己的领导地位
3. 一段时间之后没有任何人获胜.

接下来就对这些结果进行讨论:

它赢得了选举

如果一个 candidate 在同一任期 (term) 内获得了整个集群中大多数服务器的投票，那么它就赢得了选举.
每台服务器在给定的 term 内最多为一名 candidate 投票，以先来后到为原则.

少数服从多数的原则保证了最多只有一名 candidate 能够在某一 term 内赢得选举
(图 3中的选举 Safety 属性).
一旦一个 candidate 在选举中获胜，它就成为 leader. 然后，它向所有其他服务器发送心跳信息 (不携带日志的AppendEntries RPC),
以建立其权威并防止新的选举发生.

另一个服务器确立了自己的领导地位

在等待投票的过程中，candidate 可能会收到另一个服务器的AppendEntries RPC, 声称自己是领导者.
如果这个 leader 的 term (会携带在 RPC 中) 不小于 candidate 当前的 term,
那么 candidate 就会承认 leader 是合法的并返回到 follower 状态.
如果 RPC 中的 term 比 candidate 当前的 term 小，那么候选者会拒绝 RPC, 并继续处于 candidate 状态.

一段时间之后没有任何人获胜

第三个可能的结果是 candidate 既没有赢得选举，也没有输掉选举：如果许多 follower 同时成为 candidate, 那么票数可能被分割，
因此没有 candidate 能获得足够的投票.
当这种情况发生时，每个 candidate 都会超时，然后通过增加其 term 和发起新一轮的RequestVote RPC来开始新的选举.
然而，如果没有额外的措施，split vote可能会无限期地重复.

Raft 使用随机的选举超时时间，以确保 split vote 很少发生，并能迅速解决.
为了从一开始就防止 split vote, 选举超时时间是从一个固定的时间间隔 (例如 150-300ms) 中随机选择的.
这样每个服务器的选举超时时间就不同了，所以在大多数情况下，只有一个服务器会超时.

如果一个服务赢得了选举，就在其他服务超时之前发送心跳，split vote就是使用这样的机制来处理.
每个 candidate 在选举开始时重新启动其随机选举超时 (重新计时？), 并等待超时过后再开始下一次选举；
这减少了在新的选举中再次出现 split vote 的可能性.

选举是一个用于说明可理解性是如何指导我们在设计方案做权衡的例子.
最初我们计划使用一个排名系统：每个 candidate 被分配一个唯一的排名，用来在竞争的 candidate 之间进行选择.
如果一个候选人发现了另一个排名更高的候选人，它就会回到 follower 的状态，这样排名更高的候选人就能更容易地赢得下一次选举.
我们发现这种方法在可用性方面产生了一些微妙的问题 (如果一个排名较高的服务发生故障了，一个排名较低的服务器可能需超时并再次成为
candidate , 但如果它过早地这样做，它可能会重置选举 leader 的进展). 我们对算法进行了多次调整，但每次调整后都会出现新的角落案例.
最终我们得出结论，随机重试的方法更明显，更容易理解.

Log replication#

一旦一个领导者被选出，它就开始为 client 的请求提供服务。每个 client 的请求都包含一个要由复制的状态机执行的 command.
leader 将该 command 作为一个新的条目附加到它的日志中，然后并行发起AppendEntries RPC给其他每个服务器以复制该条日志.
当条目被安全的复制后 (下面会介绍),leader 将这条日志应用于其状态机，并将执行结果返回给 client.
如果 follower 崩溃或运行缓慢，又或者网络数据包丢失，leader 会无限期地重试AppendEntries RPC(甚至在它回应了客户端之后),
直到所有 follower 最终存储所有日志条目.

日志的组织方式如图 6所示。每个日志条目都存储了一个状态机命令，
以及 leader 收到该条目时的 term 编号。日志条目中的 term 编号被用来检测日志之间的不一致，
并确保图 3中的一些属性。每个日志条目也有一个整数的索引来标识它在日志中的位置.

leader 决定何时将日志条目应用于状态机是安全的，这样的条目被称为 committed.
Raft 保证所提交的条目是持久化的并且最终会被所有可用的状态机执行.
一旦创建该条目的 leader 将其复制到大多数服务器上，该日志条目就会被提交 (例如，图 6 中的条目 7).
这也会提交 leader 日志中所有之前的条目，包括之前领导者创建的条目.
leader 会跟踪它所知道的已提交的最大索引，并且它在未来的AppendEntries RPC(包括心跳) 中包括该索引，以便其他服务器最终发现.
一旦 follower 得知一个日志条目被提交，它就会将该条目应用于其本地状态机 (按日志顺序).

我们设计的 Raft 日志机制在不同服务器上的日志之间保持高度的一致性。这不仅简化了系统的行为，使其更具可预测性，而且是确保安全的重要组成部分.
Raft 维护了以下特性，它们共同构成了图 3中的Log Matching特性:

如果不同的两个日志具有相同的 index 以及 term

• 那么就认为它们存储的是同一个 command
• 那么就认为它们之前的所有日志也是相同的

第一个属性来自于这样一个事实，即一个 leader 在一个 term 内只能在一个 index 上创建一个日志条目，并且日志条目永远不会改变它们在日志中的位置.
第二个属性由AppendEntries RPC执行的简单一致性检查来保证.
当发送AppendEntries RPC时，leader 会包含其日志中紧接新条目之前的条目的 index 和 term.
如果 follower 在其日志中没有找到具有相同 index 和 term 的条目，那么它将拒绝新条目.
一致性检查就像一个归纳步骤：日志的初始状态是肯定满足Log Matching属性的，
并且每当日志被扩展时，一致性检查都会保留Log Matching属性.
因此，每当AppendEntries成功返回时，leader 知道 follower 的日志与自己的日志在新条目之前是相同的

在正常运行期间，leader 和 follower 的日志保持一致，所以AppendEntries一致性检查不会失败.
然而，leader 崩溃会使日志不一致 (old leader 可能没有完全复制其日志中的所有条目).
这些不一致会在一系列 leader 和 follower 的崩溃中加剧。图 7 说明了 follower 的日志可能与 new leader 的日志不同的方式.

• follower 可能会丢失 leader 的条目
• follower 可能会有 leader 没有的额外条目
• 或者两者都有

日志中缺失和多余的条目可能跨越多个 term.

在 Raft 中，leader 通过强迫 follower 的日志重复自己的日志来处理不一致的情况。这意味着 follower 日志中的冲突条目将被 leader
日志中的条目覆盖。在下一节将表明，如果再加上一个限制，这就是安全的.

为了使 follower 的日志与自己的日志保持一致，leader 必须找到两个日志一致的最新日志条目，删除该点之后 follower 日志中的所有条目，
并将该点之后的所有 leader 条目发送给 follower. 所有这些操作都是为了响应AppendEntries RPC执行的一致性检查而发生的.
leader 为每个 follower 维护一个 nextIndex , 这是 leader 将发送给该 follower 的下一个日志条目的 index.
当 leader 当选时，它会初始化所有 nextIndex 的值为自己最后一条日志的 index + 1 (图 7 中的 11).
如果 follower 的日志与 leader 的日志不一致，则AppendEntries一致性检查将在下一个AppendEntries RPC中失败.
follower 拒绝后，leader 会减少 nextIndex 的值并重试AppendEntries RPC.
最终nextIndex将达到 leader 和 follower 日志匹配的点.
发生这种情况时，AppendEntries将成功，这将删除 follower 日志中的任何冲突条目，并从 leader 日志中添加条目 (如果有).
一旦AppendEntries成功，follower 的 log 就会和 leader 的一致，并且在接下来的任期内保持这种状态.

如果需要，可以优化协议以减少被拒绝的AppendEntries RPC的数量。例如，当拒绝AppendEntries请求时，
follower 可以包含冲突条目的 term 以它在 term 中存储的第一个索引.
有了这些信息，leader 可以减少 nextIndex 以绕过该 term 中的所有冲突条目；
每个有日志冲突的 term 都只需要一个AppendEntries RPC, 而不是每个日志条目一个 RPC.
在实践中，我们怀疑这种优化是否必要，因为失败很少发生，而且不太可能有很多不一致的条目.

通过这种机制，leader 在上台时无需采取任何特殊措施来恢复日志一致性。它刚刚开始正常运行，
并且日志会自动收敛以响应AppendEntries一致性检查的失败.
leader 永远不会覆盖或删除自己日志中的条目 (图 3中的Leader Append-Only).

理想的 Raft:

• 只要大多数服务器启动，Raft 就可以接受、复制和应用新的日志条目
• 可以通过单轮 RPC 将新条目复制到集群的大部分；
• 并且单个慢速 follower 不会影响性能.

Safety#

在前面的章节里面介绍了 Raft 怎样选举领导以及复制日志.
然而，这些机制还远不够来保证每个状态机以相同的顺序来执行相同的 command.
例如，一个 follower 可能是不可用状态 (unavailable) 而 leader 提交了若干个日志，然后它可能会被选为 leader 然后覆盖这些日志；
结果就是不同的状态机可能执行了不同的 command sequence.

在这一节通过添加对哪些服务器可以被选举为 leader 的限制来完善 Raft.
这个限制确保 leader 在任意给定 term 内，包含了之前任职期间的所有被提交的日志 (图 3中的Leader Completeness Property)
增加这个选举限制，让我们使提交时的规则更加准确.
最后，我们会展示一个简要的证明为Leader Completeness Property并且说明是怎样引导出正确行为的复制状态机.

Election restriction#

在任何基于 leader 的共识算法中，leader 必须将已提交的日志存储。在一些共识算法中，比如Viewstamped Replication,
一个节点能当选 leader, 即使它一开始没有包含所有已提交的日志.
这些算法都有额外的机制来识别丢失的日志并发送给 new leader, 要么在选举的过程中或者在选举之后不久.
不幸的是，这种方法会导致相当大的额外的机制和复杂性.

Raft 使用了一种更加简单的方法，它可以保证在选举的时候新的 leader 拥有所有之前任期中已经提交的日志条目，
而不需要传送这些日志条目给 leader. 这意味着日志条目的传送是单向的，只从 leader 传给 follower,
并且 leader 从不会覆盖自身本地日志中已经存在的条目.

Raft 使用投票的过程来阻止 candidate 赢得选举，除非它的日志包含所有已经提交的条目.cand-
idate 为了被选举必须联系集群中的大部分节点，这意味着每个被提交的日志在这些服务上至少存在一个节点上.
如果 candidate 的日志至少与大多数日志中的任何其他日志一样最新 (“最新” 的定义在下面), 那么它一定保存了所有已提交的日志.

RequestVote RPC实现的限制: RPC 会包含关于 candidate 的日志信息，如果 voter 自己的日志比 candidate 的日志更新，
那么 vote 会拒绝投票.

Raft 通过比较最后一个日志的 index 以及 term 来决定两个日志中的那个是最新的.
如果最后一条日志的 term 不同，则更大的那份就是更新的.
如果日志有相同的 term, 那么哪个日志长 (日志数组的长度？还是 index 的大小？), 哪个就是最新的.

Committing entries from previous terms#

如Log replication介绍的那样，
只要日志被存储到大多数节点中，leader 就知道这条日志是可以在当前 term 内被提交的.
如果 leader 在提交日志之前崩溃了，未来的 leader 将会尝试完成这条日志的复制.
然而，leader 不能立即推断出在前一个 term 的日志在保存到大多数服务器上时就一定被提交了.
图 8 说明了一种情况：一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的领导者覆盖掉.

为了消除图 8 中的问题，Raft 永远不使用通过计算副本数量的方式去提交前一个 term 的日志.
只有 leader 当前 term 内的日志条目才会通过计算副本数量的方式来提交；
一旦当前 term 的日志以这种方式提交，那么由于Log Matching则之前的所有日志条目也被间接提交.
在某些情况下，leader 能安全的知道一个老的日志是否已经被提交 (例如，该日志是否存储到服务器上),
但是 Raft 为了简化问题使用了一种更加保守的方法.

当 leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号，这在提交规则上产生了额外的复杂性.
在其他的共识算法中，如果一个新的 leader 要重新复制之前的任期里的日志时，它必须使用当前新的任期号.
Raft 使用的方法更加容易辨别出日志，因为它可以随着时间和日志的变化对日志维护着同一个任期编号.
另外，和其他的算法相比，Raft 中的 new leader 只需要发送更少日志条目 (
其他算法中必须在他们被提交之前发送更多的冗余日志条目来为他们重新编号).
但是，这在实践中可能并不十分重要，因为领导者更换很少会发生.

Follower and candidate crashes#

如果 follower 或者 candidate 崩溃了，那么后续发给他们的 RPC 都会失败.
Raft 的处理方式就是无限重试，如果后续它们恢复了，这些请求就会成功.
如果一个节点在接收了一个 RPC 请求后，但是还没有响应的时候崩溃了，那么它在恢复的时候会再次收到同样的请求.
Raft 的 RPC 都是幂等的，所以重试不会造成任何问题.
如果一个 follower 收到AppendEntires RPC中包含已经存在的日志，那么它会直接忽略这个新的请求.

Timing and availability#

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果.
但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间.
例如，如果消息交换比服务器故障间隔时间长，候选人将没有足够长的时间来赢得选举；没有一个稳定的领导人，Raft 将无法工作.

领导人选举是 Raft 中对时间要求最为关键的方面.Raft 可以选举并维持一个稳定的领导人，只要系统满足下面的时间要求：

{{< center >}}
broadcastTime ≪ electionTimeout ≪ MTBF (平均故障时间)
{{< /center >}}

1. broadcastTime: 从一个服务器并行的发送 RPC 给集群中的其他服务器并接收响应的平均时间
2. electionTimeout: 选举超时时间
3. MTBF: 对一台服务器而言，两次故障之间的平均时间

broadcastTime 必须比 electionTimeout 小一个数量级才能够发送稳定的心跳消息来阻止 follower 进入选举状态.
通过随机生成的 electionTimeout, 这个不等式使得 split vote 的情况变为不可能.
electionTimeout 应该比 MTBF 小上几个数量级，这样系统才能稳定的运行.
当 leader 崩溃后，整个系统会在一个 electionTimeout 内不可用，我们希望这种情况在整个系统的运行中很少出现.

broadcastTime 和 MTBF 是由系统决定的，但是 electionTimeout 是我们自己选择的.Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，
所以 broadcastTime 大约是 0.5 毫秒到 20 毫秒，取决于存储的技术.
因此，electionTimeout 可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的 MTBF 都在几个月甚至更长，很容易满足时间的需求.

Cluster membership changes#

Links#

1. 项目地址: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
2. Raft 官网: https://raft.github.io/
3. GFS 相关资料: https://fzdwx.github.io/posts/2022-10-07-gfs/#links
4. Raft paper: https://pdos.csail.mit.edu/6.824/papers/raft-extended.pdf
5. Raft paper 中文翻译: https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md
6. Diagram of Raft interactions： https://pdos.csail.mit.edu/6.824/notes/raft_diagram.pdf
7. Students guid to Raft: https://thesquareplanet.com/blog/students-guide-to-raft/
8. Raft locking: https://pdos.csail.mit.edu/6.824/labs/raft-locking.txt
9. Raft structure: https://pdos.csail.mit.edu/6.824/labs/raft-structure.txt
10. Paxos Replicated State Machines as the Basis of a High-Performance Data
    Store https://static.usenix.org/event/nsdi11/tech/full_papers/Bolosky.pdf
11. TiKV 对于 Raft 优化 https://cn.pingcap.com/blog/optimizing-raft-in-tikv
12. https://www.cnblogs.com/niejunlei/p/9719557.html
13. https://blog.csdn.net/viskaz/article/details/124232474
14. https://www.cnblogs.com/brianleelxt/p/13251540.html