MIT-6.824 (3)

MIT-6.824 分布式系统学习笔记（3）

参考资料：

• chaozh/MIT-6.824: Basic Sources for MIT 6.824 Distributed Systems Class (github.com)

• MIT6.824 (gitbook.io)

• 2020 MIT 6.824 分布式系统_bilibili

Lecture 05 Raft1

• 之前MapReduce、GFS、VMware FT都需要一个单节点决定在多个副本中谁是Primary
  • MapReduce被一个单主节点控制
  • GFS以primary-backup的方式复制数据，依赖一个单主节点确定数据的主拷贝位置
  • VMware FT在一个Primary虚机和一个Backup虚机之间复制计算相关的指令
• 使用这样的一个单节点可以避免脑裂（split brain）

Majority Vote

• 网络分区：网络出现故障使其分割为两份，两边独自运行且不能互相访问

• 服务器的数量是奇数——当出现网络分区时，两个网络分区不再对称

• 在任何时候为了完成任何操作，必须凑够过半的服务器来批准相应的操作——如果网络存在分区，必然不可能有超过一个分区拥有过半数量的服务器（过半指的是所有服务器的一半，包括故障的、未启动的）

• 必然至少包含一个服务器存在于上一个操作的过半服务器中——任意两组过半服务器，至少有一个服务器是重叠的，此时能够有效避免脑裂

• 当Raft Leader竞选成功，Leader必然凑够过半服务器的选票，其中必然与旧Leader的过半服务器有重叠，所以新Leader必然知道旧Leader使用的任期号（term number）；类似的，任何新Leader的过半服务器中，必然有至少一个服务器包含旧Leader的所有操作

Raft初探

• Raft以库（Library）的形式存在于服务中，即如果有一个基于Raft的多副本服务，服务的副本将包含应用程序代码和Raft库：应用程序代码接收RPC或者客户端请求，节点的Raft库相互合作，维护多副本的操作同步

• 可以认为在Raft节点的上层是应用程序代码，应用程序通常有状态，Raft层帮助应用程序将其状态拷贝到其他副本节点

• Raft的状态中，最重要的就是Raft会记录操作的日志。

• 假设一个系统有三个服务器，同时有客户端C1和客户端C2

  • 客户端将请求发送给Raft集群中的Leader节点对应的应用程序（请求是应用程序级别的请求，例如访问Key-Value数据库的请求）
  • Leader节点的应用程序将客户端请求对应的操作发送到Raft层，让其把操作提交到多副本的日志（Log）中，并在完成时通知应用程序层
  • Raft节点交互，直到过半的Raft节点将新的操作加入各自的日志——操作被过半的Raft节点复制
  • 以上操作完成，Leader的Raft层向上发送通知给应用程序，表明操作拷贝给副本，可以真正执行这个操作——客户端发送请求不会立即被执行，当且仅当请求存在于过半的副本节点时，Leader才会实际的执行请求
  • 当操作在Leader被提交后，副本节点的Raft层将相同的操作提交到本地应用程序层，本地应用程序层将该操作更新到自己的状态

• 综上，如果操作是确定的，所有副本节点的状态将是完全一样的

Log同步时序

• 假设有一个客户端，服务器S1是当前Leader，服务器S2、S3为副本
• 客户端将请求发送给服务器1，服务器S1的Raft层发送添加日志（AppendEntries）RPC到S2、S3，S1等到过半节点的响应后执行请求，其他服务器可能也会返回响应给Leader，但是此时不需要等待这个响应，一旦Leader发现请求被commit，Leader将消息通知给其他的副本——事实上，这个消息隐含在commit号中，即，下一次Leader发送心跳，或者是将新的客户端请求同步给其他副本时，Leader将更大的commit号随着AppendEntries RPC发出，其他服务器据此可知上一个消息被commit
• 客户端只会等待Leader执行请求，所以其他副本在什么时候执行请求，不会影响客户端感受的请求时延

Raft log

• Log是Leader对操作排序的一种手段（复制状态机来说所有副本要以相同的顺序执行相同的操作）——Log是一些按照数字编号的槽位，槽位的数字表示Leader选择的顺序
• Follower收到操作但还没有执行时，需要将这个操作存放在某处，直到收到Leader发送的新commit号才执行，因此Log对follower而言是存放临时操作的地方，如果不确定这些操作是否被commit，操作可能会被丢弃
• Leader需要在它的Log中记录操作，因为操作可能需要重传给Follower（即使请求可能已经commit）
• Log可以帮助重启的服务器恢复状态。节点将Log写入到磁盘，故障重启之后，Log会被节点用来从头执行其中的操作进而重建故障前的状态
• 在一个生产环境中，如果想使用系统的极限性能，还需要一条额外的消息来调节Leader的速度
• 以上为普通、无故障操作的时序

应用层接口

• 应用层和Raft层之间的接口（假设应用程序是一个key-value数据库，下层为Raft层）
• 第一个接口：
  • key-value层（应用层）转发客户端请求的接口——实际上是个函数调用，称为Start函数
  • 函数只接收一个参数，即客户端请求
• 第二个接口：
  • Raft层通知key-value层：请求已经commit（该请求不一定是最近一次Start函数传入的请求，例如任何请求commit之前，可能会再有100个请求通过Start函数传给Raft层）
  • 向上的接口以go channel中的一条消息的形式存在（因此有个叫做applyCh的channel，通过它可以发送ApplyMsg消息）
• Start函数的返回值包括：请求如果commit成功会存放在Log中的位置（index），返回当前term number等
• ApplyMsg将会包含请求（command）和对应的Log位置（index）
• 不同副本的log有时会不一样（有些副本因为网络原因没有收到RPC或commit消息）

Leader选举

• Raft生命周期中会有不同的Leader，使用任期号（term number）区分不同的Leader，每个任期最多有一个Leader

• Followers不需要知道Leader的ID，只需要知道当前的任期号

• Raft节点有一个选举定时器（Election Timer），若定时器时间耗尽前，当前节点没有收到当前Leader的消息，该节点会认为Leader已经下线，开始一次选 举：

  • 当前节点增加任期号（term number），
  • 当前节点发出请求投票（RequestVote）RPC给所有的Raft节点（选举时会投票给自己）
  • 此时旧leader可能还在工作，其所在的网络分区会有少于过半的服务器，因此当下次客户端发送请求时，旧Leader会发出AppendEntries RPC，但因为凑不齐过半服务器，所以永远不会commit和执行这个请求

• 任意一个任期内，每一个节点只会对一个候选人投一次票，过半原则导致最多只有一个胜出的候选人

• 如果超半的节点故障或不可用，或者在另一个网络分区，系统会不断地尝试选举Leader，但永远不能选出一个Leader

• 当一个服务器赢得一次选举，它会通过心跳通知其他服务器——立刻发送一条AppendEntries消息给其他所有的服务器（Raft规定，除非当前任期的Leader，没人可以发出AppendEntries消息），因此其他服务器通过接收特定任期号的AppendEntries获知选举成功

选举定时器

• 任何一条AppendEntries消息都会重置Raft节点的选举定时器，阻止任何其他节点成为候选人，因此只要所有环节都正常，心跳机制会阻止任何新的选举发生

• 有的场景会导致候选人不能凑齐过半的投票，进而不能赢得选举，此时系统什么也不会做

• 可能的场景：多个候选人同时请求投票，导致分割选票（Split Vote）

• Raft为选举定时器随机选择超时时间尽量降低分割投票的概率。因为不同的服务器都选取了随机的超时时间，总会有一个选举定时器先超时，而另一个后超时，先超时节点能够在另一个节点超时之前发起一轮选举，获得过半的选票成为新的Leader

• 选举定时器的超时时间上限和下限

  • 至少大于Leader的心跳间隔，一般将选举定时器的超时时间下限设置成心跳间隔的几倍
  • 最大超时时间影响系统从故障中恢复的速度
  • 不同节点的选举定时器的超时时间差必须足够长，使得第一个开始选举的节点能够完成一轮选举——超时时间至少要大于一条RPC需要的往返（Round-Trip）时间

• Lab2如果不能在几秒内从一个Leader故障的场景中恢复，测试代码会报错，需要调小选举定时器超时时间的上限

• 每一次一个节点重置自己的选举定时器时，都需要重新选择一个随机的超时时间，即不要反复使用同一个值

可能的异常情况

• 新任的Leader如何整理在不同副本上可能已经不一致的Log？（假设上一个leader发生故障，因为如果不是因为leader故障，一般不会出现log不一致的问题）
• 见下一节

Lecture 06 Raft2

日志恢复

• Followers在写入Log Entry前，会检查自己前一个Log Entry，是否与Leader发来的前一条Log的信息匹配（AppendEntries RPC包含了prevLogIndex字段和prevLogTerm字段），如果不匹配，则返回False，Leader调整该Follower的nextIndex，并重新发送RPC
  • Leader为每个Follower维护了nextIndex，nextIndex的初始值为新任Leader最后一条日志的index+1
  • Follower如果接受一个AppendEntries消息，需要首先删除本地相应index的Log（如果有的话），再用AppendEntries中的内容替代本地Log
• 综上，Leader使用一种备份机制来探测Followers的Log中，第一个与Leader的Log相同的位置。获得该位置后，Leader给Follower发送从这个位置开始的，剩余的全部Log，从而各个节点的Log可以和Leader保持一致
• Follower中发生冲突的log之所以可以删除，是因为该log entry没有存在于过半服务器中，因此前任leader即使发送了这个log entry，也不会commit这个记录，客户端也不会认为这个log entry被执行（Leader只会在commit之后回复给客户端）

选举约束 Election Restriction

• 哪些节点允许成为Leader？

• 节点只能向满足下面条件之一的candidate投票：

  • candidate最后一条Log Entry的任期大于follower最后一条Log Entry的任期

  • candidate最后一条Log Entry的任期等于本地最后一条Log Entry的任期，且candidate的Log记录长度大于等于本地Log记录的长度

• Raft更喜欢拥有更高任期记录的candidate，更喜欢拥有任期号更高的旧Leader记录的候选人

• 如果candidate都拥有任期最高的旧Leader记录，那么Raft更喜欢拥有更多记录的候选人

快速恢复 Fast Backup

• 如第一节，若Log有冲突，Leader每次回退一条Log Entry——这会花费很长的时间
• 为了能够更快的恢复日志，Raft的大致思想是，让Follower返回足够的信息给Leader，使得Leader可以以任期（Term）为单位回退，而非每次只回退一条Log Entry——如果Leader和Follower的Log不匹配，Leader对每个不同的Term发送一条AppendEntries，而非对每个不同的Log Entry发送一条AppendEntries——这只是一种加速策略
• Follower在回复Leader的AppendEntries消息中，携带3个额外的信息，来加速日志的恢复
  • XTerm：Follower中，与Leader冲突的Log对应的任期
    • Leader在RPC中有两个字段记录该follower前一条Log的任期
    • 如果Follower在对应位置的任期不匹配，会拒绝Leader的AppendEntries消息，将自己的任期号放在XTerm
    • 如果Follower在对应位置没有Log，那么这里会返回 -1
  • XIndex：Follower中，对应任期号为XTerm的第一条Log条目的槽位号
  • XLen：如果Follower在对应位置没有Log，那么XTerm会返回-1。XLen表示空白的Log槽位数

持久化 Persistence

• 当更改了被标记为持久化的某个数据，服务器应该将更新写入到磁盘，或者其它的持久化存储中，持久化的存储确保服务器重启时，服务器可以找到相应的数据，并将其加载到内存中
• Raft论文中，有且仅有三个数据需要持久化存储：Log、currentTerm、votedFor
  • Log是所有的Log Entry，某个服务器刚刚重启，在加入Raft集群前，要检查并确保这些数据有效的存储在它的磁盘上
  • currentTerm和votedFor用来确保每个任期只有最多一个Leader——如果一个服务器收到了一个RequestVote请求，并且为服务器1投票了，之后它故障。如果没有存储它为哪个服务器投过票，当它故障重启之后，收到了来自服务器2的同一个任期的另一个RequestVote请求，它还是会投票给服务器2，因为它发现自己的votedFor是空的，认为自己还没投过票
• 安全的做法是，每次添加一个Log Entry，更新currentTerm或者更新votedFor，都需要持久化这些数据
• 如果持久化存储在一个机械硬盘上，那么每个操作至少要10毫秒，这意味着永远也不可能构建一个每秒能处理超过100个请求的Raft服务——synchronous disk updates的代价

日志快照 Log Snapshot

• 对于一个长期运行的系统，Log会持续增长，需要大量的内存来存储。如果持久化存储在磁盘上，会消耗磁盘的大量空间。并且重启时需要通过重新从头执行这数百万条Log来重建状态
• 快照背后的思想是，应用程序将其状态的拷贝作为一种特殊的Log条目存储下来。之前几乎都忽略了应用程序，假设基于Raft构建一个key-value数据库，Log将会包含一系列的Put/Get或者Read/Write请求。对于大多数的应用程序来说，应用程序的状态远小于Log的大小，因此如果存储Log，可能尺寸会非常大，相应的，如果存储key-value表单，这可能比Log尺寸小得多
• 当Raft认为Log过于庞大，会要求应用程序在Log的特定位置对其状态做一个快照，此时会从Log中选取一个与快照对应的点，然后要求应用程序在那个点的位置做一个快照，Raft会丢弃所有那个点之前的Log记录——在key-value数据库的例子中，快照本质上就是key-value表单
• Raft的持久化存储实际上是持久化应用程序快照，和快照之后的Log
• 应用程序不仅需要有能力能生成一个快照，它还需要能够读取一个之前创建的快照，并通过它稳定的重建自己的内存，Raft并不理解快照中有什么，只有应用程序知道
• Raft需要某种机制让AppendEntries能处理某些Follower Log的结尾到Leader Log开始之间丢失的这一段Log——解决方法是（一个新的消息类型）InstallSnapshot RPC
  • 当Follower刚刚恢复，如果Log短于Leader通过AppendEntries RPC发给它的内容，首先会强制Leader回退自己的Log
  • 在某个点，Leader将不能再回退（已经到了自己Log的起点），此时Leader将自己的快照发给Follower，之后通过AppendEntries将后面的Log发给Follower
• 如果Follower收到了一条InstallSnapshot消息，但是这条消息看起来完全是冗余的，这条InstallSnapshot消息包含的信息比当前Follower的信息还要老，这时，Follower可以忽略这条快照

线性一致

• 一个多副本服务或者任意其他服务正确运行意味着什么？
• 对于正确的定义是线性一致（Linearizability）或者说强一致（Strong consistency）。通常来说，线性一致等价于强一致。一个服务是线性一致的，则表现地就像只有一个服务器，并且服务器没有故障
• 一个系统的执行历史是一系列的客户端请求，如果执行历史整体可以按照一个顺序排列，且排列顺序与客户端请求的实际时间相符合，那么就是线性一致的
• 一个线性一致的执行历史中的操作是非并发的，即时间上不重合的客户端请求与实际执行时间匹配，并且每一个读操作看到的是最近一次写入的值
  • 如果一个操作在另一个操作开始前就结束了，那么这个操作必须在执行历史中出现在另一个操作前面
  • 执行历史中，读操作必须在相应的key的写操作之后