原创分享 6.824 分布式系统课程第六课: 错误容忍:Raft(1)

ty4z2008-github · 2020年04月29日 · 350 次阅读

笔记: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 数据结构

状态:

  • 磁盘:currentTermvotedForlog[]
  • 内存:commitIndexlastApplied
  • leader 节点 (内存):nextIndex()matchIndex[]

日志追加 RPC 过程:

  • 参数:termleaderIdprevLogIndexprevLogTermentries[]leaderCommit
  • 回调结果:termsuccess
  • 接收者
  • term<currentTerm 返回false
  • preLogIndexpreLogTerm不匹配时返回false
  • entires[]存在冲突的条目(index相同,term不同)。应删除此日志以及>index 后的所有条目
  • 添加任何在已有的日志中不存在的新条目
  • 如果leaderCommit > commitIndex,则commitIndex设置为min(leaderCommit,entries[].lastIndex)

投票 RPC:

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

接收者:

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

协定:

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

参考文献

博客地址

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册