MIT6.824学习笔记（四） -- Raft

2024-08-30
MIT6.824

MIT6.824（2020）学习笔记，Lecture 6和7 - Raft。

1. 背景

前面学习了 MapReduce（MIT6.824学习笔记（一） – 课程介绍 及 MapReduce） 和 GFS（MIT6.824学习笔记（三） – GFS），关于Go语言RPC和线程的Lecture 2暂时先挂起了。

Lecture 4关于主备副本，暂时只看了讲义：6.824 2020 Lecture 4: Primary/Backup Replication，了解了虚拟机主备容错的基本过程，可以先过渡到Raft。

Lecture 5讲Go语言的协程，内存模型和并发控制等特性，也暂时跳过，实验时练习。

Raft部分分了上下两堂课，Lecture 6 - Raft (1) 和 Lecture 7 - Raft (2) 。

相关资料：

说明：本博客作为个人学习实践笔记，可供参考但非系统教程，可能存在错误或遗漏，欢迎指正。若需系统学习，建议参考原链接。

2. Raft论文

论文相关链接：

涉及Paxos算法，可了解相关论文：

2.1. 基本介绍

2.1.1. Raft介绍

Raft算法出自斯坦福大学的博士生 Diego Ongaro 于2014年发表的论文：In Search of an Understandable Consensus Algorithm(Extended Version)。

Raft这一名字来源于”Reliable, Replicated, Redundant, And Fault-Tolerant”（“可靠、可复制、可冗余、可容错”）的首字母缩写。

Raft是一种为了管理复制日志的一致性算法(consensus algorithm)。它提供了和 Paxos/Multi-Paxos 算法相同的功能和性能，但是它 更易理解 且 更容易构建实际的系统。

在设计 Raft 算法的时候，使用了一些特别的技巧来提升它的可理解性，包括算法分解（Raft 主要被分成了领导人选举，日志复制和安全三个模块）和减少状态机的状态（相对于 Paxos，Raft 减少了非确定性和服务器互相处于非一致性的方式）。

Raft算法在许多方面和现有的一致性算法都很相似，但也有些独特的特性：

  • 强领导人，Raft使用一种更强的领导能力形式。如日志条目只从领导人发送给其他的服务器，简化了复制日志管理并且使Raft算法更加易于理解。
  • 领导人选举，Raft算法在心跳机制上增加了一个随机计时器来选举领导人，在解决冲突的时候会更加简单快捷。
  • 成员关系变更，Raft使用一种共同协商一致的方法来处理集群成员变换的问题，当变更发生时集群仍能正常继续工作。

集群内的节点都对选举出的领袖采取信任，因此Raft不是一种拜占庭容错算法。

2.1.2. 拜占庭将军问题

这里介绍下拜占庭容错（Byzantine Fault Tolerance，BFT）对应的拜占庭将军问题（Byzantine Generals Problem）。该问题是由莱斯利·兰波特在其同名论文（可见其1982年的论文）中提出的分布式对等网络通信容错问题。拜占庭将军问题被认为是容错性问题中最难的问题类型之一。

介绍下作者：

莱斯利·兰波特（英语：Leslie Lamport，1941年2月7日—），美国计算机科学家。也是排版系统LaTeX的开发者。Lamport在计算机科学领域，特别是分布式系统，领域有着深远的影响，也奠定的此领域的基础。他最著名的贡献是在分布式系统中的逻辑时钟和事件排序，Bakery算法和互斥解决方案，并发程序的规范和验证，不可靠网络中的Paxos协议，以及复制状态机（Replicated State Machines）的概念。他的成果为他赢得了许多奖项和荣誉，包括2013年的图灵奖、Dijkstra奖、IEEE约翰·冯·诺依曼奖和the Jean-Claude Laprie Award in Dependable Computing。他还于2011年当选为美国国家科学院院士。

番外：今天一个技术群里还在讨论LaTeX来着，有点巧。

下面信息参考：维基百科：拜占庭将军问题

问题描述：

  • 一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。
  • 因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统的问题在于，可能将军中出现叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。示例：

  • 假设有9位将军投票，其中有1名叛徒。8名忠诚的将军中4人投进攻，4人投撤离。
  • 这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。
  • 这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离。这样各支军队的一致协同就遭到了破坏。

由于将军之间需要通过信使通讯，叛变将军可能通过伪造信件来以其他将军的身份发送假投票。而即使在保证所有将军忠诚的情况下，也不能排除信使被敌人截杀，甚至被敌人间谍替换等情况。因此很难通过保证人员可靠性及通讯可靠性来解决问题。

假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。上述的故事映射到计算机系统里，将军便成了计算机，而信差就是通信系统。

拜占庭容错算法（Byzantine Fault Tolerance，BFT）的发展历程可见参考链接。

之前在 区块链学习笔记 中，了解过拜占庭将军问题，但只是限于很表面，此时结合工作经验和分布式角度看，清晰很多。对于比特币，使用的是工作量证明（POW）应对此类问题。

2.2. 复制状态机

一致性算法是从复制状态机（Replicated state machines）的背景下提出的。在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。

复制状态机在分布式系统中被用于解决很多容错的问题，典型应用就是一个独立的复制状态机去管理领导选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper（关于Chubby可以见上面贴的Google的《Paxos Made Live - An Engineering Perspective》论文，其一致性算法是基于Paxos实现的）。

复制状态机通常都是基于 复制日志 实现的，如下所示为复制状态机架构图：

复制状态机的架构

一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。

  • 每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。
    • 每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。
    • 因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。
  • 一致性算法的任务是 保证复制日志的一致性。
    • 服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，即使有些服务器发生故障。
    • 一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成了一个高可靠的状态机。

实际使用中的一致性算法通常包含以下特性：

  • 安全保证性（绝对不会返回一个错误的结果）：在非拜占庭错误情况下，包括网络延迟、分区、丢包、重复和乱序等错误都可以保证正确。
  • 可用性：只要大多数（>n/2）机器可运行，并能相互通信、并能和客户端通信，就可以保证可用。
  • 不依赖时间来保证一致性：错误的时钟或者极端的消息延迟在最坏情况下可能会导致可用性问题
  • 通常情况下，一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用（RPC）时完成。小部分比较慢的节点不会影响系统整体的性能。

2.3. Paxos算法的问题

在过去的 10 年里（相较于2014），Leslie Lamport 的 Paxos 算法几乎已经成为一致性的代名词：Paxos 是在课程教学中最经常使用的算法，同时也是大多数一致性算法实现的起点。

Paxos首先定义了一个能够通过单一决策达成一致的协议，比如单条的复制日志项，这一子集叫做单决策Paxos（相对的还有Multi-Paxos）。Paxos 的正确性已经被证明，在通常情况下也很高效。

但是Paxos 有两个明显的缺点：1、难以理解； 2、没有为构建实际的实现提供良好的基础（还没有一种被广泛认同的多决策问题的算法）。

2.4. Raft一致性算法

下面是一个关于Raft一致性算法的浓缩总结（不包括成员变换和日志压缩）：

Raft一致性算法的浓缩总结

包含：

  • 状态
    • 所有服务器上的持久性状态
    • 所有服务器上的易失性状态
    • 领导人（服务器）上的易失性状态
  • 附加条目（AppendEntries）RPC
    • 由领导人调用，用于日志条目的复制，同时也被当做心跳使用
  • 请求投票（RequestVote）RPC
    • 由候选人负责调用用来征集选票
  • 所有服务器需遵守的规则
    • 所有服务器、跟随者、候选人、领导人 各自的规则

Raft在任何时候都保证的几个特性：

  • 选举安全特性（Election Safety）：对于一个给定的任期号，最多只会有一个领导人被选举出来
  • 领导人只附加原则（Leader Append-Only）：领导人绝对不会删除或者覆盖自己的日志，只会增加
  • 日志匹配原则（Log Matching）：如果两个日志在某一相同索引位置日志条目的任期号相同，那么这两个日志从头到该索引位置之间的内容都完全一致
  • 领导人完整性（Leader Completeness）：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
  • 状态机安全特性（State Machine Safety）：如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他服务器在该索引位置不会应用不同的日志条目

2.4.1. Raft基础

在任何时刻，每一个服务器节点都处于这三个状态之一：领导人（Leader）、跟随者（Follower）或者候选人（Candidate）

  • 在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。
  • 跟随者都是被动的：他们不会发送任何请求，只是简单的响应来自领导人或者候选人的请求。领导人处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导人）。
  • 第三种状态，候选人，是用来选举新领导人时使用。

raft服务器状态变化：

raft服务器状态变化

  • 当服务器程序启动时，他们都是跟随者身份
  • 跟随者只响应来自其他服务器（候选人和领导人）的请求。
  • 如果跟随者接收不到消息，那么他就会变成候选人并发起一次选举。
  • 获得集群中大多数选票的候选人将成为领导人。在一个任期内，领导人一直都会是领导人，直到自己宕机了。

Raft把时间分割成任意长度的任期，任期用连续的整数标记。每一段任期从一次选举开始，一个或者多个候选人尝试成为领导人。在某些情况下，一次选举过程会造成选票的瓜分。在这种情况下，这一任期会以没有领导人结束；一个新的任期（和一次新的选举）会很快重新开始。Raft 保证了在一个给定的任期内，最多只有一个领导人。

任期在 Raft 算法中充当逻辑时钟的作用，任期使得服务器可以检测一些过期的信息。

Raft算法中服务器节点之间通信使用远程过程调用（RPC），并且基本的一致性算法只需要两种类型的RPC。请求投票（RequestVote） RPC 由候选人在选举期间发起，然后附加条目（AppendEntries）RPC 由领导人发起，用来复制日志和提供一种心跳机制。另外，为了传输快照增加了第三种RPC。

2.4.2. 领导人选举

Raft 使用一种心跳机制来触发领导人选举。

  • 服务器程序启动时，都是跟随者身份。
  • 领导人周期性的向所有跟随者发送心跳包（不包含日志项的AppendEntries），来维持自己的权威。
  • 如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导人，并且发起选举以选出新的领导人。

要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态，然后他会并行地向集群中的其他服务器节点发送请求投票（RequestVote）RPC来给自己投票。

每一个服务器最多会对一个任期号投出一张选票，并按照先来先服务的原则。

3种可能情况：

  1. 当一个候选人从整个集群的大多数服务器节点获得了针对同一个任期号的选票，那么他就赢得了这次选举并成为领导人。然后他会向其他的服务器发送心跳消息来建立自己的权威并且阻止发起新的选举。
  2. 在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导人的附加条目（AppendEntries）RPC
    • 如果这个领导人的任期号不小于候选人当前的任期号，那么候选人会承认领导人合法并回到跟随者状态。
    • 如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。
  3. 候选人既没有赢得选举也没有输：如果有多个跟随者同时成为候选人，那么选票可能会被瓜分以至于没有候选人可以赢得大多数人的支持。该情况下会增加当前任期号来开始一轮新的选举。
    • Raft 算法使用随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。

2.4.3. 日志复制

领导人被选举出来后，就开始提供服务。客户端的每个请求中都包含一条被复制状态机执行的指令，领导人将该指令作为一个新条目追加到日志中，而后并行地发起附加条目RPC，让其他服务器复制这个条目。

当这条日志条目被安全地复制（见下文），领导人会应用（apply）这条日志条目到它的状态机中然后把执行的结果返回给客户端。如果跟随者崩溃或者运行缓慢，或者网络丢包，领导人会不断的重复尝试附加条目RPC（尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

每一个日志条目存储一条状态机指令和从领导人收到这条指令时的任期号。日志中的任期号用来检查是否出现不一致的情况，每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置。

日志组织方式如下：

日志组织方式

  • 日志由有序序号（最上面的log index）标记的条目组成
    • 每一条日志条目都有一个整数索引值来表明它在日志中的位置
  • 每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令（如上述将x变为3）。
    • 每一个日志条目存储一条状态机指令和从领导人收到这条指令时的任期号
    • 日志中的任期号用来检查是否出现不一致的情况，同时也用来保证上述提到的“Raft在任何时候都保证的几个特性”的某些性质
  • 一个条目当可以安全地（超过半数）被应用到状态机中去的时候，就认为是可以提交了。

领导人来决定什么时候把日志条目应用到状态机中是安全的；这种日志条目被称为已提交（committed）。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行。在领导人将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交。

Raft 维护着以下的特性，这些特性共同组成了上述的日志匹配特性（Log Matching Property）：

  1. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
    • 领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变。
  2. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。
    • 该特性由附加日志 RPC 的一个简单的一致性检查所保证。在发送附加日志 RPC 的时候，领导人会把新的日志条目前紧挨着的条目的索引位置和任期号包含在日志内。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目。

领导人崩溃的情况会使得日志处于不一致的状态，这种不一致问题会在领导人和跟随者的一系列崩溃下加剧。跟随者可能会丢失一些在新的领导人中存在的日志条目，也可能拥有一些领导人没有的日志条目，或者两者都发生。丢失或者多出日志条目可能会持续多个任期。

比如下图所述：

领导人异常崩溃的情况

  • 说明：当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号
  • 跟随者可能会缺少一些日志条目（a-b）
  • 可能会有一些未被提交的日志条目（c-d）
  • 或者两种情况都存在（e-f）
    • 场景 f 可能会这样发生：
    • 某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；
    • 很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；
    • 在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

在 Raft 算法中，领导人是通过强制跟随者直接复制自己的日志来处理不一致问题的。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖。

要使得跟随者的日志进入和自己一致的状态，领导人必须找到最后两者达成一致的地方，然后删除跟随者从那个点之后的所有日志条目，并发送自己在那个点之后的日志给跟随者。所有的这些操作都在进行 附加日志RPC 的一致性检查时完成。

领导人针对每一个跟随者维护了一个 nextIndex，这表示下一个需要发送给跟随者的日志条目的索引地址。通过如下过程达成一致：

  • 当一个领导人刚获得权力的时候，其初始化所有的 nextIndex 值为自己的最后一条日志的 index 加 1
  • 如果一个跟随者的日志和领导人不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败
  • 在被跟随者拒绝之后，领导人就会减小 nextIndex 值并进行重试
  • 最终 nextIndex 会在某个位置使得领导人和跟随者的日志达成一致
  • 当这种情况发生，附加日志 RPC 就会成功，这时就会把跟随者冲突的日志条目全部删除并且加上领导人的日志
  • 一旦附加日志 RPC 成功，那么跟随者的日志就会和领导人保持一致，并且在接下来的任期里一直继续保持

2.4.4. 安全性

论文中的本小节对领导人完整特性（Leader Completeness Property）做了简要证明，此处不作记录。

即：如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中

选举限制：

请求投票（RequestVote）RPC 实现了这样的限制：RPC 中包含了候选人的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

Raft通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

提交之前任期内的日志条目：

  • 只有领导人当前任期里的日志条目通过计算副本数目可以被提交；
  • 一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。

安全性：

  • 通过领导人完整特性，就能证明状态机安全特性，即如果服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上
  • 在一个服务器应用（apply）一条日志条目到它的状态机中时，其日志必须和领导人之前条目到该条目的日志一致，并且这些条目都是已被提交的（committed）
  • 日志完全特性保证拥有更高任期号的领导人会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。
  • 最后，Raft 要求服务器按照日志中索引位置顺序应用日志条目。和状态机安全特性结合起来看，这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中，并且是按照相同的顺序。

2.4.5. 跟随者和候选人崩溃

如果跟随者或者候选人崩溃了，那么后续发送给它们的RequestVote RPC和AppendEntries RPC都会失败。

Raft中处理这种失败就是通过无限的重试

  • 如果崩溃的服务器重新启动，那么这些 RPC 将成功完成
  • 如果一个服务器完成了一个RPC，但是在响应之前崩溃了，那么在它重新启动之后就会再次收到同样的请求
  • Raft 的 RPC 都是幂等的，所以这样重试不会造成任何问题
    • 例如一个跟随者如果收到附加日志请求，但是它已经包含了这一日志，那么它就会直接忽略这个新的请求。

2.4.6. 时间和可用性

Raft 的要求之一就是安全性不能依赖时间：整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是，可用性（系统可以及时的响应客户端）不可避免的要依赖于时间。

例如，如果消息交换比服务器故障间隔时间长，候选人将没有足够长的时间来赢得选举；没有一个稳定的领导人，Raft 将无法工作。

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

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

其中：

  • 广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间
  • 平均故障间隔时间（Mean Time Between Failures）就是对于一台服务器而言，两次故障之间的平均时间

不等式说明：

  • 广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；
    • 通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能
  • 选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行
    • 当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用

广播时间和平均故障间隔时间是由底层系统决定的，但是选举超时时间是我们自己选择的。

  • Raft 的 RPC 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。
  • 因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。
  • 大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

2.5. 集群成员变化

集群的配置指：加入到一致性算法的服务器集合。

在实践中，偶尔是会改变集群的配置的，例如替换那些宕机的机器或者改变复制级别。尽管可以通过暂停整个集群，更新所有配置，然后重启整个集群的方式来实现，但是在更改的时候集群会不可用。另外，如果存在手工操作步骤，那么就会有操作失误的风险。为了避免这样的问题，论文中设计了自动化配置更改，并将其纳入 Raft 共识算法。

为了保证安全性，配置更改必须使用两阶段方法（two-phase approach）。

  • 在 Raft 中，集群先切换到一个过渡的配置，称为共同一致（joint consensus）；
  • 一旦共同一致已经被提交了，那么系统就切换到新的配置上。共同一致是老配置和新配置的结合

TODO：论文中的新、旧配置（C-old、C-old,new、C-new）过渡示意图，过了一下感觉有点复杂，暂时放一下

当服务器确认当前领导人存在时，服务器会忽略请求投票RPC。确切地说，当服务器在当前最小选举超时时间内收到一个请求投票 RPC 时，不会更新当前的任期号或者投出选票。这不会影响正常的选举，每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。这有利于避免被移除的服务器扰乱：如果领导人能够发送心跳给集群，那么它就不会被更大的任期号废黜。

2.6. 日志压缩

Raft 的日志在正常操作中不断地增长，但是在实际的系统中，日志不能无限制地增长。随着日志不断增长，他会占用越来越多的空间，花费越来越多的时间来重置。如果没有一定的机制去清除日志里积累的陈旧的信息，那么会带来可用性问题。

快照是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。

Raft中快照的基础思想如下示意图所示：

raft快照示意图

  • 一个服务器用新的快照替换了从 1 到 5 的条目，快照值存储了当前的状态（此处是x和y的值）。快照的最后被包含索引和任期用于定位快照中当前状态（此处是第6项）之前的日志。
  • 每个服务器独立地创建快照，只包括已经被提交的日志。主要的工作包括将状态机的状态写入到快照中。
  • Raft 也包含一些少量的元数据到快照中：最后被包含索引指的是被快照取代的最后的条目在日志中的索引值（状态机最后应用的日志），最后被包含的任期指的是该条目的任期号。
    • 保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查，因为这个条目需要前一日志条目的索引值和任期号。
    • 为了支持集群成员更新，快照中也将最后的一次配置作为最后一个条目存下来。
    • 一旦服务器完成一次快照，它就可以删除最后索引位置之前的所有日志和快照了。

尽管通常服务器都是独立地创建快照，但是领导人必须偶尔的发送快照给一些落后的跟随者。

  • 对于一个运行非常缓慢的跟随者或者新加入集群的服务器，这时让这个跟随者更新到最新的状态的方式，就是通过网络把快照发送给它们。
  • 领导人通过调用 安装快照RPC（InstallSnapshot RPC），将快照的分块发送给跟随者
  • 当跟随者通过这种 RPC 接收到快照时，它必须自己决定对于已经存在的日志该如何处理。
    • 通常快照会包含没有在接收者日志中存在的信息。在这种情况下，跟随者丢弃其整个日志；它全部被快照取代，并且可能包含与快照冲突的未提交条目。
    • 如果接收到的快照是自己日志的前面部分（由于网络重传或者错误），那么被快照包含的条目将会被全部删除，但是快照后面的条目仍然有效，必须保留。

2.7. 客户端交互

Raft 中的客户端发送所有请求给领导人。当客户端启动的时候，它会随机挑选一个服务器进行通信。

  • 如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供它最近接收到的领导人的信息
    • 附加条目请求（AppendEntries requests）中包含了领导人的网络地址
  • 如果领导人崩溃了，那么客户端的请求就会超时
  • 客户端之后会再次重试随机挑选服务器的过程

Raft 的目标是要实现线性化语义（linearizable semantics）：每次操作在它的调用和响应之间的某个时刻立即执行，且恰好执行一次（exactly once）。

但是，Raft是可能执行同一条命令多次的，例如：如果领导人在提交了这条日志之后，但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

3. 课程笔记

3.1. 脑裂（Split Brain）

之前课程涉及的容错模型：

  • MapReduce中，通过一个master程序副本负责任务分配和程序控制
  • GFS中，也以单个master负责控制系统交互，另外在GFS之外有监控机制负责master副本的容错切换
  • VMware FT中，在主备虚拟机之间复制信息，并通过一个Test-and-Set服务判断是否需要切换接管

这三个例子中，它们都是一个多副本系统（replication system），但是在背后，它们存在一个共性：它们需要一个单节点来决定，在多个副本中，谁是主（Primary）。

单节点的好处是决策简单，坏处是容易有单点故障（Single Point of Failure）。这个单点会在系统出现局部故障时，选择数据的主拷贝来继续工作。使用单点的原因是，我们需要避免脑裂（Split-Brain）。

在有两个拷贝副本的配置中，看起来我们只有两种选择：要么等待两个服务器响应，那么这个时候就没有容错能力；要么只等待一个服务器响应，那么就会进入错误的场景，而这种错误的场景，通常被称为脑裂。

很长一段时间内，人们都使用下面两种方式来构建多副本系统：

  • 第一种是构建一个不可能出现故障的网络。带着合理的假设和大量的资金，同时小心的控制物理环境，人们可以足够接近这个假设。
  • 另一种就是人工解决问题，不要引入任何自动完成的操作。出问题后让运维人员去机房检查两个服务器，进行决策。

这虽然不太完美，因为人工响应不能很及时，而不出现故障的网络又很贵，但是这些方法至少是可行的。

3.2. 过半票决（Majority Vote）

哪怕网络可能出现故障，可能出现分区（网络故障分割的两边独自运行），实际上是可以正确的实现能够自动完成故障切换的系统。

在构建能自动恢复，同时又避免脑裂的多副本系统时，关键点在于过半票决（Majority Vote）。过半票决系统的第一步在于，服务器的数量要是奇数，而不是偶数。

在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作。这里的过半是指超过所有服务器总数的一半。通常这也被称为多数投票（quorum）系统。

  • 如果网络存在分区，那么必然不可能有超过一个分区拥有过半数量的服务器。
  • 例如，假设总共有三个服务器，如果一个网络分区有一个服务器，那么它不是一个过半的分区。如果一个网络分区有两个服务器，那么另一个分区必然只有一个服务器。因此另一个分区必然不能凑齐过半的服务器，也必然不能完成任何操作。

在过半票决这种思想的支持下，大概1990年的时候，有两个系统基本同时被提出。

  1. 一个叫做Paxos，Raft论文对这个系统做了很多的讨论
  2. 另一个叫做ViewStamped Replication（VSR）

尽管Paxos的知名度高得多，Raft从设计上来说，与VSR更接近。VSR是由MIT发明的。这两个系统有着数十年的历史，但是他们仅仅是在15年前（相对2020年此处对应2005年左右），也就是他们发明的15年之后，才开始走到最前线，被大量的大规模分布式系统所使用。

3.3. Raft相关讲解

3.3.1. Raft简要流程

Raft会以库（Library）的形式存在于服务中。

如果有一个基于Raft的多副本服务，那么每个服务的副本将会由两部分组成：应用程序代码和Raft库。

  • 应用程序代码接收RPC或者其他客户端请求；
  • 不同节点的Raft库之间相互合作，来维护多副本之间的操作同步。

以Key-Value数据库为例：

  • 对于一个Key-Value数据库而言，对应的状态就是Key-Value Table。应用程序往下就是Raft层。
  • Key-Value数据库需要对Raft层进行函数调用，来传递自己的状态和Raft反馈的信息

客户端发送请求给Key-Value数据库，这个请求不会立即被执行，因为这个请求还没有被拷贝（过半节点拷贝该请求操作）。当且仅当这个请求存在于过半的副本节点中时，Raft才会通知Leader节点，只有在这个时候，Leader才会实际的执行这个请求。对于Put请求来说，就是更新Value，对于Get请求来说，就是读取Value。最终，请求返回给客户端，这就是一个普通请求的处理过程。

3.3.2. Log同步时序

（下述3个服务器用S1、S2和S3表示，S1为Leader）

  • Leader（S1）收到客户端请求后，其Raft层会发送一个附加日志（AppendEntries）的RPC到其他两个副本（S2，S3），并等待响应
  • 当Leader收到了过半服务器的正确响应，Leader会执行（来自客户端的）请求，得到结果，并将结果返回给客户端。
    • Leader知道过半服务器已经添加了Log，可以执行客户端请求，并返回给客户端。
    • 但是其他服务器（如S2）只知道：我从Leader那收到了这个请求，但是我不知道这个请求是不是已经被Leader提交（committed）了，这取决于我的响应是否被Leader收到。比如服务器2只知道，它的响应提交给了网络，或许Leader没有收到这个响应，也就不会决定commit这个请求。
  • 所以这里还有一个阶段：一旦Leader发现请求被commit之后，它需要将这个消息通知给其他的副本。所以这里有一个额外的消息。
    • 在Raft中，没有明确的committed消息。相应的，committed消息被夹带在下一个AppendEntries消息中，由Leader下一次的AppendEntries对应的RPC发出。任何情况下，当有了committed消息时，这条消息会填在AppendEntries的RPC中。
    • 下一次Leader需要发送心跳，或者是收到了一个新的客户端请求，要将这个请求同步给其他副本时，Leader会将新的更大的commit号随着AppendEntries消息发出，当其他副本收到了这个消息，就知道之前的commit号已经被Leader提交，其他副本接下来也会执行相应的请求，更新本地的状态。

课程此处的讲解，提及一个很重要的自己看论文没理清的点：在Raft中，没有明确的committed消息。结合后面“日志恢复”和“持久化”的讲述，更容易理解上面“日志复制”里的这张图（通过持久化的任期和是否超半数来确定操作是否被commit了）：

领导人异常崩溃的情况

3.3.3. Raft Log 的作用

为什么Raft系统这么关注Log，Log究竟起了什么作用？

  • 1、Raft系统之所以对Log关注这么多的一个原因是，Log是Leader用来对操作排序的一种手段。这对于复制状态机而言至关重要，对于这些复制状态机来说，所有副本不仅要执行相同的操作，还需要用相同的顺序执行这些操作。
  • 2、Log的另一个用途：Follower副本收到操作但还未提交时，Log用来存放临时操作，直到收到了Leader发送的新的commit号才执行。这些操作可能会被丢弃。
  • 3、Log的另一个用途：用于Leader，Leader需要在它的Log中记录操作，因为这些操作可能需要重传给Follower。
    • 如果一些Follower由于网络原因或者其他原因短时间离线了或者丢了一些消息，Leader需要能够向Follower重传丢失的Log消息。
    • 所以，Leader也需要一个地方来存放客户端请求的拷贝。即使对那些已经commit的请求，为了能够向丢失了相应操作的副本重传，也需要存储在Leader的Log中。
  • 4、所有节点都需要保存Log还有一个原因：它可以帮助重启的服务器恢复状态。
    • 每个Raft节点都需要将Log写入到它的磁盘中，这样它故障重启之后，Log还能保留。而这个Log会被Raft节点用来从头执行其中的操作进而重建故障前的状态，并继续以这个状态运行。
    • 所以，Log也会被用来持久化存储操作，服务器可以依赖这些操作来恢复状态。

3.3.4. Leader选举（Leader Election）

Raft生命周期中可能会有不同的Leader，它使用任期号（term number）来区分不同的Leader。Followers（非Leader副本节点）不需要知道Leader的ID，它们只需要知道当前的任期号。

对于每个任期来说，或许没有Leader，或许有一个Leader，但是不可能有两个Leader出现在同一个任期中。每个任期必然最多只有一个Leader。

开始一次选举：

  • 当前服务器会增加任期号（term number）
  • 之后，当前服务器会发出请求投票（RequestVote）RPC，这个消息会发给所有的Raft节点。其实只需要发送到N-1个节点，因为Raft规定了，Leader的候选人总是会在选举时投票给自己。

新领导人（赢得了选举的候选人）会通过心跳通知其他服务器。Raft论文的图2（Raft一致性算法的浓缩总结图）规定了，如果你赢得了选举，你需要立刻发送一条AppendEntries消息给其他所有的服务器。

  • 这条代表心跳的AppendEntries并不会直接说：我赢得了选举，我就是任期23的Leader。
  • 这里的表达会更隐晦一些：Raft规定，除非是当前任期的Leader，没人可以发出AppendEntries消息。
    • 所以假设我是一个服务器，我发现对于任期19有一次选举，过了一会我收到了一条AppendEntries消息，这个消息的任期号就是19。那么这条消息告诉我，我不知道的某个节点赢得了任期19的选举。所以，其他服务器通过接收特定任期号的AppendEntries来知道，选举成功了。

3.3.5. 选举定时器（Leader Timer）

任何一条AppendEntries消息都会重置所有Raft节点的选举定时器。

这样，只要Leader还在线，并且它还在以合理的速率（不能太慢）发出心跳或者其他的AppendEntries消息，Followers收到了AppendEntries消息，会重置自己的选举定时器，这样Leader就可以阻止任何其他节点成为一个候选人。

Raft不能完全避免分割选票（Split Vote），但是可以使得这个场景出现的概率大大降低。Raft通过为选举定时器随机地选择超时时间来达到这一点。

需要注意的一点是，不同节点的选举定时器的超时时间差（比如S2和S3之间）必须要足够长，使得第一个开始选举的节点能够完成一轮选举。这里至少需要大于发送一条RPC所需要的往返（Round-Trip）时间。

3.3.6. 日志恢复（Log Backlog）

课程也提及了一个自己看论文时没太去思考理解的点：论文的各个插图中，有的服务器（比如下面的S1）可能缺失了某些槽位的日志（或者说操作），虽然没展示，但是其持久化信息里是有之前leader任期的，所以选举出新leader后下一个任期不会搞错。

课程讲述场景：

1
2
3
4
5

Raft ---  LOG
    10  11  12  13
S1  3   
S2  3   3   4
S3  3   3   5

假设下一个任期是6，尽管你无法从黑板上确认这一点，但是下一个任期号至少是6或者更大。同时假设S3在任期6被选为Leader。

即如下所示：

1
2
3
4
5

Raft ---  LOG
    10  11  12  13
S1  3   
S2  3   3   4
S3  3   3   5   6
  • 在某个时刻，新Leader S3会发送任期6的第一个AppendEntries RPC，来传输任期6的第一个Log，这个Log应该在槽位13。
    • 这里的AppendEntries RPC还包含了prevLogIndex字段和prevLogTerm字段。所以Leader在发送AppendEntries消息时，会附带前一个槽位的信息。
    • 此处场景中，prevLogIndex是前一个槽位的位置，也就是12；prevLogTerm是S3上前一个槽位的任期号，也就是5。
  • Followers收到AppendEntries消息，在写入Log之前，会检查本地的前一个Log条目，是否与Leader发来的有关前一条Log的信息匹配。
    • 对于S2 它显然是不匹配的。S2 在槽位12已经有一个条目，但是它来自任期4，而不是任期5。所以S2将拒绝这个AppendEntries，并返回False给Leader。
    • S1在槽位12还没有任何Log，所以S1也将拒绝Leader的这个AppendEntries。
  • 所以，Leader看到了两个拒绝

Raft后续的处理方式：

  • Leader为每个Follower维护了nextIndex。所以它有一个S2的nextIndex，还有一个S1的nextIndex。
    • 如果Leader之前发送的是有关槽位13的Log，这意味着Leader对于其他两个服务器的nextIndex都是13。
  • 为了响应Followers返回的拒绝，Leader会减小对应的nextIndex。所以它现在减小了两个Followers的nextIndex。
  • 这一次，Leader发送的AppendEntries消息中，prevLogIndex等于11（此时nextIndex减为12），prevLogTerm等于3。同时，这次Leader发送的AppendEntries消息包含了prevLogIndex之后的所有条目，也就是S3上槽位12和槽位13的Log。
    • 对于S2来说，这次收到的AppendEntries消息中，prevLogIndex等于11，prevLogTerm等于3，与自己本地的Log匹配，所以，S2会接受这个消息。
      • Raft论文中的图2规定，如果接受一个AppendEntries消息，那么需要首先删除本地相应的Log（如果有的话），再用AppendEntries中的内容替代本地Log。
      • 所以，S2会这么做：它会删除本地槽位12的记录，再添加AppendEntries中的Log条目。这个时候，S2的Log与S3保持了一致。
    • 对于S1，由于11槽位是空的，本次还是会拒绝这个AppendEntries消息；
      • 于是Leader继续减小nextIndex到11，并在AppendEntries消息中带上从槽位11开始之后的Log，并且带上相应的prevLogIndex（10）和prevLogTerm（3），
      • 这时的请求可以被S1接受，并得到肯定的返回。于是Log就达到一致了。
  • 而Leader在收到了Followers对于AppendEntries的肯定的返回之后，它会增加相应的nextIndex到14

3.3.7. 选举约束（Election Restriction）

解答了一个问题：为什么不选择拥有最长Log记录的节点作为Leader？

示例：假设有3个服务器，现在服务器1（S1）有任期5，6，7的Log，服务器2和服务器3（S2和S3）有任期5，8的Log。

1
2
3
4

Raft ---  LOG
S1  5   6   7
S2  5   8
S3  5   8

解释下达到上面状态的前置过程：

  • 1、S1在某个时间点（6位置）赢得了选举，它的任期号是6
  • 2、然后S1收到了一个客户端请求，在发出AppendEntries之前，它先将请求存放在自己的Log中，然后它就故障了，没能发出任何AppendEntries消息（所以自己有任期6的条目，而S2、S3则没有）

对应状态：

1
2
3
4

Raft ---  LOG
S1  5   6   
S2  5   
S3  5
  • 3、之后它很快就故障重启了，因为它是之前的Leader，所以会有一场新的选举。这次，它又被选为Leader。然后它收到了一个任期7的客户端请求，将这个请求加在本地Log之后，它又故障了。

对应状态：

1
2
3
4

Raft ---  LOG
S1  5   6   7
S2  5   
S3  5
  • 4、S1故障（假设关机未恢复）之后，又有了一次新的选举，这时S1已经关机了，不能再参加选举，这次S2被选为Leader。如果S2当选，而S1还在关机状态，S2会使用什么任期号呢？
    • 核心： 尽管没有写在黑板上，但是S1在任期6，7能当选，它必然拥有了过半节点的投票，过半服务器至少包含了S2，S3中的一个节点。如果去看处理RequestVote的代码和Raft论文的图2，当某个节点为候选人投票时，节点应该将候选人的任期号记录在持久化存储中。所里在这里，S2或者S3或者它们两者都知道任期6和任期7的存在。
    • 因此，当S1故障了，它们中至少一个知道当前的任期是8。
    • 所以下一个任期号将会是8，S2或者S3会赢得选举。不管是哪一个，新的Leader会继续将客户端请求转换成AppendEntries发给其他节点。

对应状态：

1
2
3
4

Raft ---  LOG
S1  5   6   7
S2  5   8
S3  5   8

结论：S2和S3可以组成过半服务器，所以任期8的Log已经被commit了，对应的请求很可能已经执行了，应用层也很可能发送一个回复给客户端了。所以我们不能删除任期8的Log。因此，S1也就不能成为Leader并将自己的Log强制写入S2和S3。正因为这个原因，我们不能在选举的时候直接选择拥有最长Log记录的节点。当然，最短Log记录的节点也不行。

Raft有一个稍微复杂的选举限制（Election Restriction），节点只能向满足下面条件之一的候选人投出赞成票：

  • 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号；
  • 或者，候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

3.3.8. 持久化（Persistence）

Raft论文的图2（Raft一致性算法的浓缩总结图）中，有且仅有三个数据是需要持久化存储的，它们分别是Log、currentTerm、votedFor。

  • Log是所有的Log条目。当某个服务器刚刚重启，在它加入到Raft集群之前，它必须要检查并确保这些数据有效的存储在它的磁盘上
  • currentTerm和votedFor都是用来确保每个任期只有最多一个Leader
  • currentTerm的情况要更微妙一些，但是实际上还是为了实现一个任期内最多只有一个Leader

4. 工业届的Raft实现

浏览参考下别人的论文学习分享笔记：Raft 算法介绍

工业界的一些Raft实现：

  • tikv
  • consul
  • etcd
  • sofajraft
  • …

5. 小结

学习了Raft论文和课程讲解，后续看下具体实现，etcd和braft。

6. 参考

1、课表，其中有讲义：6.824 Schedule: Spring 2020

2、维基百科：Raft

3、论文：Raft论文

4、Raft论文翻译

5、别人的论文学习笔记：Raft 算法介绍

6、B站视频：Lecture 6: Fault Tolerance - Raft(1)

7、课程中文翻译：Lecture 06 - Raft1

8、课程中文翻译：lecture 07 - Raft2

9、《Paxos Made Simple》论文翻译

10、《Paxos Made Live - An Engineering Perspective》论文翻译

11、维基百科：拜占庭将军问题

上一篇 学习Linux存储IO栈（四） -- 通用块层

下一篇 MySQL学习实践（一） -- 整体架构和基本操作的流程

Comments

目录
分类

归档