6.824 分布式系统课程第六课: 错误容忍：Raft（1） - Jeffery的博客 | Jeffery Blog

6.824 分布式系统课程第六课: 错误容忍：Raft（1）

笔记：Lecture 6: Fault Tolerance: Raft (1)

视频：Lecture 6: Fault Tolerance: Raft (1)

论文地址：In Search of an Understandable Consensus Algorithm

Raft选举和日志处理（实验2A、2B），第二课讲Raft一致性、客户端行为、快照（实验2C、实验3）

选择Raft的原因：Paxos太难理解

因为相比较Paxos而言，理解起来要容易。第一，Paxos的原论文也比较晦涩难懂。譬如Paxos的single-decree 版本管理。第二，实际生产系统中的应用并不广泛。multi-Paxos的协议也没有得到广泛应用。虽然有些系统使用了Paxos——Chubby。但并没有开源。

目前现存容错系统的处理方式

• MapReduce的复制计算，但是依赖单master
• GFS副本数据，依赖master另外选主
• VMware FT复制服务依赖test-and-set选择master

虽然单点master可以避免“脑裂”，但是master始终是单点。

“脑裂”如何产生？这种故障会导致什么问题？

假设我们的复制服务是test-and-set模式：多个客户端发送set请求到服务，服务端收到写入请求后，返回当前值（假设是0）给客户端，此时当且只有一个客户端收到结果，且为0.（锁，其他客户端等待）

假设如下的场景：C1，C2，S1，S2。客户端C1可以与S1通信，但是不能和s2通信。那么此时只有S1上存在一份副本，当S1出现宕机时。整个系统就会出现问题。

请问C1是否应该当只有S1在线时，继续进行任务？

1. 如果S2真的宕机，C1必须在没有S2的情况下继续进行。 否则，服务不允许出现故障!
2. 如果S2工作正常，但是C1与S2之间因为网络故障无法连接。。此时C1不应该在没有S2的情况下进行。 因为S2可能还活着，并为C2客户提供服务

面对上面的情况，要么是认为正常故障，继续提供复制。要么因为“脑分裂”导致可能出现错误的操作。

面对上面的问题，计算机是无法区分“服务器故障”和“网络故障”：

两者产生的结果都是：发送给节点的请求无法被响应。

通常比较棘手的这种情况被称为网络分区：C1可以正常与S1通信，C2可以正常与S2通信。但C1+S1无法看到C2+S2的响应。这种情况处理起来比较棘手，在以往的场景下都是需要人介入来处理。或者是单点靠谱的master（FT的test-and-set 策略），或者是靠谱的网络（没有响应就是服务器崩溃）

面对上面的问题的处理方式还不够优美。是否还有更好的处理方式？

解决写复制分区的问题，可以利用：大多数投票的方式处理。

奇数台的服务器，譬如：3、5、7。只要超过一半的机器认可，就可以继续复制。例如3台时需要2台投票同意。

Q：为什么使用这种方式（大多数投票）可以是解决脑分裂遇到的问题？

A：只会出现其中一个分区拥有多数票，打破了不同客户端看到节点数目的对称性。少数票的节点应遵循拥有大多数票分区的复制。一般而言2f + 1可以容忍f个故障服务器，我们也把这样的系统称为仲裁系统。

多数票决策系统有一个特征，就是需要任意两个节点存在交集。譬如：Raft的leader选举，新的选举也不会丢失最新的复制日志。

分布式复制容错的研究已经持续了很多年，在1990前后，诞生了两种分布式复制容错技术Viewstamped Replication和Paxos。随后的15年，Raft诞生，并且得到在工业界的广泛应用。

下面来看看Raft

Raft数据结构

• 磁盘：currentTerm、votedFor、log[]
• 内存：commitIndex、lastApplied
• leader节点(内存)：nextIndex()、matchIndex[]

日志追加RPC过程：

• 参数：term、leaderId、prevLogIndex、prevLogTerm、entries[]、leaderCommit
• 回调结果：term、success
• 接收者
  1. 当term<currentTerm 返回false
  2. preLogIndex与preLogTerm不匹配时返回false
  3. entires[]存在冲突的条目（index相同，term不同）。应删除此日志以及>index后的所有条目
  4. 添加任何在已有的日志中不存在的新条目
  5. 如果leaderCommit > commitIndex，则commitIndex设置为min(leaderCommit,entries[].lastIndex)

投票RPC：

• 参数：term、candidateId、lastLogIndex、lastLogTerm
• 回调结果：term、voteGranted(true意味着收到投票)

1. 当term<currentTerm 返回false
2. 如果votedFor为空或者与candidateId相同，并且候选人的日志和自己的日志一样新，则给该候选人投票

• 所有服务器All node
  1. 如果commitIndex > lastApplied：lastApplied增加，状态机状态设置为log[lastApplied]
  2. 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm，则currentTerm赋值为 T，并切换状态为追随者（Follower）
• 追随者Follower
  1. 响应候选者和leader的请求
  2. 如果超时还没有收到leader的AppendEntries请求或者是candidated的投票，自己就晋升为candidated
• 候选者Condidates
  1. 转换为候选者后开始选举：currentTerm自增、投票给自己、重置选举计时器、请求投票RPC给其他服务器
  2. 如果大多数投票通过，则成为leader
  3. 如果收到来自leader的AppendEntries请求，则成为follower
  4. 如果超时，则开始新一轮选举
• 领导人Leader
  1. 一旦成为leader，就需要向所有节点发送AppendEntries RPC心跳包；空闲时重复发送空包以防止选举超时
  2. 收到客户端请求，先追加到本地日志，然后更新状态机新值
  3. follower上次收到的日志缩影大于将要收到的日志索引nextIndex，则通过AppendEntriesRPC把nextIndex之后的日志发送出去。
• 发送成功则将该追随者的 nextIndex和matchIndex更新
• 因为日志不一致导致的发送失败，nextIndex递减并且重新发送
  1. 当存在一个N，使得N > commitIndex和matchIndex[i]>=N，并且log[N].term == currentTerm。则更新commitIndex = N

在开发时，Raft作为library运行在每个副本中。如图

当客户端发送一条put写命令时：

1. 客户端发送put/get命令到leader的K/V层
2. leader添加命令到日志
3. leader发送AppendEntries RPC调用到follower
4. follower存储日志到磁盘
5. leader等待大多数的follower响应（包括自己）
6. 当收到大多数响应时，标记此日志为commited（已提交）状态。这意味当集群机器出现故障时，数据不会丢失。出现leader选举时，下一个leader也能看到最新日志。
7. leader执行命令告知客户端成功
8. 与此同时，leader在下一次进行AppendEntries RPC告知follower这条日志可以执行存储
9. follwer 看到是commit则会实际的写入到KV层

Q：为什么需要引入日志？

A：单独的KV DB存储无法完整的保存状态机的状态。日志可以保证命令执行的顺序（只做append），也可以帮助确保leader和follower日志一致。

日志存储临时命令直到提交，日志可以防止leader的命令重发导致重复执行，日志因为进行了持久化，即使服务器重启也能回放。

Q：是不是所有的副本日志都一样？

并不是，有些副本的日志可能出现滞后。短暂时间内，日志记录不同。不过，最终所有的副本会收敛为一致，commit机制可以确保所有的命令都被正确执行。

实验2 Raft接口

rf.Start(command) (index, term, isleader)`

• 实验3中 k/v 服务器的Put()/Get()操作通过RPC调用Start()
• Start()只对leader有意义
• 在新的日志记录启动Raft协议
  • 添加到leader日志
  • leader发送附属日志给AppendEntries RPC
  • Start()返回w/o调用RPC后的响应
  • 在applyCh部分，k/v 层的Get()/Put()操作需等待commit才能算完成
• 如果服务器在commit之前失去leader，则此次通信可能会失败，执行的命令可能会丢失，客户端需要重发
• isleader: 如果服务器不是leader则为false，客户端识别此字段为false时需要重试另外一台
• term: currentTerm, 给调用者区分leader是否被降级
• index：区分日志是否已经commit

ApplyMsg，包含日志的最新索引（index）和执行的命令：（command,index）

• 每个提交的日志在applyCh会发送一个ApplyMsg
• 接收消息后执行命令，更新本地副本状态
• leader通过RPC发送响应结果给等待的客户端

Raft设计有两个主要的部分：

• 选择新leader
• 即使出现故障，也能保证日志一致

讨论：Leader选举

Q：为什么只有一个leader？

A：保证所有的副本执行相同命令并且保证顺序一致（有些设计是没有leader的，譬如：Paxos）

Raft中Leader的序列编号意义（raft把时间分为多个周期，每个周期都有一个编号）

新leader–>新的周期

在新的周期内，最多只存在一个leader也可能没有。

编号可以帮助服务器找到那个是最新的leader，而不会再次请求旧的leader

Raft中成员何时开始新一轮的选举？

• 没有收到当前消息发送的选举超时消息时
• 增加自己的currentTerm,并发送RPC要其他节点投票
• 会有可能选举多次，导致选举时间变长。但保证了安全
• 旧的leader可能还活着，那么此时就认为它是领导者

如何确保在一个周期内只有一个leader？

• leader必须获得大多数节点的赞成投票（假设节点数为2n，则至少需要获得n+1）
• 每个节点每个周期内只能给投一票。
  • 候选人则是投票给本身
  • 非候选人则投票给第一个询问票的节点
• 同一个周期内，只有一个节点能获得大多数投票
  • 即使网络分区也只会出现一个leader
  • 当有服务器出现故障时也不影响选举

节点如何了解新选举的leader已经产生？

• 获得大多数的投票的leader，对于这些投票的机器认为对方是candidate
• 新leader的通过AppendEntries心跳包发送一个高的周期编号给其他节点。其他节点收到这个心跳包后停止选举，并认为对方是leader

选举失败的可能性原因可能有两个：

• 大多数的服务器无法响应
• 大家都是候选人状态，无法获得到多数票

如果选举不成功怎么办？

• 选举超时（没有心跳），开始新的选举（新的周期）
• 周期编号高的继续，低编号的候选人退出

Raft如何避免分裂投票？

每个节点的超时都是在150～300ms选择一个随机值。随机值打破节点之间的对称性，所有节点的随机值中会出现一个最小的随机值。有足够的时间在是一轮超时获得选举。其他节点看到新的leader发送的AppendEntries 心跳并且不会变为candidate。（随机延时在网络协议中也比较常见）

如何处理选举超时时间？

• 至少能容纳几个心跳包间隔（防止网络丢包），避免不必要的选举而浪费时间
• 随机部分足够长的时间，让一个候选人在下一个候选人开始前发起投票，然后再让下一个候选人开始。
• 足够短的时间对故障做出快速反应，避免长时间的服务中断。
• 足够短的时间，可以在短时间内，允许多重试几次选举。
• 一般要求在5秒内完成选举任务

如果旧的leader不知道新的leader当选怎么办？

• 旧的leader可能没有收到选举消息
• 旧的leader在少数量节点的分区网络中
• 新的leader意味着大多数节点的currentTerm已经递增
  • 旧的leader无法通过AppendEntries获得大多数投票
  • 旧leader无法执行和commit新的log
  • 基于以上，这种情况下就不会产生“脑裂”，但是有一小部分会收到旧的AppendEntries，不过在旧的周期结束时，日志会被丢弃。

---

• Previous
  MIT 6.824 分布式系统课程第五课：Go线程和Raft

---