【MIT 6.5840/6.824】In Search of an Understandable Consensus Algorithm 学习笔记

6.5840/6.824 Lab与笔记汇总
本文为笔者阅读论文In Search of an Understandable Consensus Algorithm过程中的随笔记录，较为随意，希望能为大家提供一点理解上的帮助

1 Introduction

一致性算法允许一组机器作为一个连贯的群体工作，可以在一些成员的失败时仍保持正常运行。Paxos一直占着一致性算法的主导地位，但是它非常难以理解，而且为了支持实际系统，它的架构需要进行复杂的修改。
本文提出的Raft则是一种容易理解的一致性算法。Raft采用了特殊的技术来改善可理解性，包括分解（Raft将一致性的关键元素拆分为leader election、log replication和safety）和状态空间缩减（Raft降低了不确定性的程度以及服务器相互不一致的方式）
Raft在许多方面与现有的一致性算法相似，但也有一些新颖的特点：

• Strong leader：Raft使用比其他一致性算法更强的领导形式，比如日志条目只从leader流向其他服务器
• Leader election：Raft使用随机计时器来选择leader
• Membership changes：Raft的更改集群中服务器集的机制使用了一种新的联合一致性方法，其中两个不同配置的大多数服务器会重叠，这允许集群在配置更改期间继续正常运行

2 Replicated state machines

复制状态机用于在分布式系统中提供容错。复制状态机通常使用replicated log实现，如下图。每个服务器都存储一个log，其中包含一系列命令，服务器中的状态机会按顺序执行这些命令。由于每个log都以相同的顺序包含相同的命令，因此每个状态机都会处理相同的命令序列，最终的输出也相同。
一致性算法的工作之一就是保持replicated log的一致性，server中的一致性模块会从客户端接收命令，并将命令追加到log中。它会与其他server的一致性模块交互，确保每一个log的命令序列都一致。正确复制命令后，每个server的状态机都会按照log中的命令顺序处理它们，然后将输出返回给客户端。

实际系统中的一致性算法通常具有以下属性：

• 它们会确保在非拜占庭条件（每个节点均遵循协议）下的安全性，包括网络延迟、分区和丢包、重复和重新排序
• 只要集群中的大多数服务器都可以运行并且可以相互通信以及与客户端通信，它们就可以正常工作
• 它们不依赖于时间来确保日志的一致性
• 只要大多数集群中的服务器响应了单轮远程过程调用，命令就可以完成；少数慢速服务器不影响整体系统性能

3 What’s wrong with Paxos?

第一个缺点是Paxos非常难以理解。
Paxos的第二个问题是它没有为构建实际系统提供良好的基础。Lamport的描述主要是关于single-decree的Paxos；他勾勒了multi-Paxos的可能方法，但许多细节被遗漏了。
结论就是，Paxos既没有为系统构建也没有为教育提供良好的基础。

4 Designing for understandability

Raft使用了两种普遍适用的技术，第一种是众所周知的问题分解方法（只要可能，就将问题分解成可以相对独立地解决、解释和理解的单独部分），如Raft中，分离了leader election、log replication、safty和membership changes。第二种方法是通过减少要考虑的状态数量来简化状态空间，使系统更加连贯，并尽可能消除不确定性。
尽管在大多数情况下，我们试图消除非确定性，但在某些情况下，非确定性实际上提高了可理解性。特别是，随机方法引入了非确定性，但它们倾向于通过以类似的方式处理所有可能的选择来减少状态空间。本文使用随机化来简化Raft的leader election算法。

5 The Raft consensus algorithm

Raft通过首先挑选一个杰出的leader来实现一致性，然后赋予leader管理replicated log的完全责任。leader接收来自客户端的log条目，然后将它们复制给其他服务器节点，并告诉服务器们何时启动状态机是安全的。这简化了replicated log的管理。leader可能失败或与其他服务器断开连接，在这种情况下，会选出新的leader。

5.1 Raft basics

一个Raft集群包含多个服务器；通常是五个，它允许系统容忍两次故障。在任何给定时间，每个服务器都处于三种状态之一：leader、follower、candidate。在正常运行中，只有一个leader，所有其他服务器都是follower。follower是被动的：他们自己不发出请求，只是回应leader和candidate的请求。leader处理所有的客户端请求（如果客户端请求follower，follower将其重定向到leader）。第三个状态，candidate，用于挑选新的leader，将在5.2节中讲述。三种状态的转换如下图所示。

Raft将时间划分为任意长度的term，如下图所示。term用连续的整数编号。每一个term都以election开始，其中一个或者多个candidate试图成为leader。如果一个candidate赢得了选举，那么将在这个term的剩余时间内作为leader。有时候选举无法选出leader，就像下图t3一样，这时会很快进行下一次选举。Raft确保在给定的term中最多只有一个leader。
terms在Raft中充当逻辑时钟，它们允许服务器检测过时的信息，例如过时的leader。每个服务器都存储一个当前term编号，该编号随着时间的推移单调增加。每当服务器通信时，都会交换当前term编号；如果一台服务器的当前term编号小于另一台服务器的当前term编号，则它会将其当前term编号更新为较大的值。如果candidate或leader发现其term已过期，它会立即变为follower。如果服务器收到带有陈旧term编号的请求，它会拒绝该请求。

Raft服务器之间采用RPC进行通信，基础的一致性算法只需要两种类型的RPC。RequestVote RPC由candidate在选举期间发起；AppendEntries RPC由leader发起，用于复制log条目并提供一种heartbeat形式（5.3节讲述）。如果服务器没有及时收到回复，它们会重试RPC，同时它们会并行发出RPC以获得最佳性能。

5.2 Leader election

Raft采用heartbeat机制来触发leader选举。服务器会作为follower启动，如果从leader或者candidate收到有效的RPC，就一直保持follower状态。leader会定期向所有follower发送heartbeat信号（没有携带log条目的AppendEntries RPC调用），以保持其权威。如果follower在一段时间内（election timeout）没有收到任何信号，那么它会假设当前没有leader，并开始选举新的leader。
为了开始新一轮选举，follower增加当前term编号，并转为candidate状态。然后，它为自己投票，并向集群中的每个其他服务器并行发出RequestVote RPC。candidate状态会一直持续，直到以下条件的其中一个成立：

• 它赢得选举
• 其他服务器赢得选举
• 一段时间过去后，没有胜利者

如果candidate在同个term内收到了集群中大多数机器的投票，那么赢得选举，就成为leader。它会向所有其他服务器发送heartbeat信号，以建立权威防止新的选举。
在等待投票时，candidate可能会收到另一个自称leader的服务器的AppendEntries RPC调用。如果该leader的term编号大于或等于candidate的term编号，那么candidate会承认该leader是合法的，并回到follower状态。如果RPC编号小于candidate的当前编号，则拒绝该RPC并继续处于candidate状态。
可能会有平票的情况，这时所有candidate都会超时，并开启新一轮选举。Raft使用随机选举超时来确保平票情况很少发生，如果发生了也可以快速解决。上面提到的election timeout会从固定间隔（例如150-300ms）中随机选择，这分散了服务器启动选举，因此大多数情况下只有一台服务器会超时，成为leader，然后在其他服务器超时前发送heartbeat信号确立权威。

5.3 Log replication

一旦选择了leader，它就开始为客户端请求提供服务。每个客户端请求都包含一个命令。leader将该命令作为新条目附加到其日志中，然后向每个其他服务器并行发出AppendEntries RPC以复制该条目。当条目被安全复制时，leader将该条目应用于其状态机，并将执行结果返回给客户端。如果follower崩溃或运行缓慢，或者如果网络数据包丢失，leader会无限期地重试AppendEntries RPC（即使它已经响应客户端），直到所有follower最终存储所有日志条目。
日志的组织形式如下图所示。每个日志条目都存储一个状态机命令以及一个term编号（leader收到该日志条目时的term编号）。日志条目中的term编号用于检测日志之间的不一致，每个日志条目也有一个整数索引。

leader决定日志条目何时能够安全地应用到状态机，这种安全的条目称为committed的条目。Raft保证committed的条目是持久的，并且最终将由所有可用的状态机执行。一旦创建条目的leader在大多数服务器上复制了该日志条目，就会提交日志条目，同时提交leader日志中的所有先前条目。leader需要跟踪它所提交条目的最高索引（如上图中的7），并将该索引包含在未来的AppendEntries RPC中，以便被其他服务器得知。一旦follower得知某条日志条目已提交，它就会将该条目应用到其本地状态机（按日志顺序）。
本文设计了Raft日志机制来保持不同服务器上日志之间的高度一致性。Raft维护以下属性成立：

• 如果不同日志中的两个条目具有相同的索引和term编号，那么它们存储相同的命令
• 如果不同日志中的两个条目具有相同的索引和term编号，则两个日志在该条目前面的所有条目都是相同的

leader在一个term中最多创建一个具有给定索引的日志条目，且日志条目永远不会改变它们的位置，故第一个属性会成立。第二个属性则由AppendEntries执行的简单一致性检查来保证成立。当leader发送一个AppendEntries RPC时，它会将新条目直接前驱条目的索引和term编号携带过去。如果接收到RPC的follower在其日志中没有找到该前驱条目，那么会拒绝接收新条目。这个简单的一致性检查保证了上述两个属性在新条目追加后依然成立。因此，当AppendEntries成功返回时，leader就会通过新条目知道follower的日志与自己的日志相同。
正常操作下，leader的日志和follower的日志均保持一致，故AppendEntries的一致性检查均能通过。但是，leader的崩溃可能导致日志的不一致（旧leader可能没有完全复制日志中的条目）。下图说明了follower日志与leader日志不同的几种可能不一致情况。

在Raft中，leader通过强迫follower复制leader的日志来处理不一致的情况。为了使follower日志与自己的日志一致，leader需要找到两个日志中最新的一致点，删除该点后follower的所有日志条目，并将该点后leader的所有条目发送给follower。具体实现上，leader为每一个follower维护了一个变量nextIndex，表示下一次发送给follower的条目索引，初始化为leader日志中的最高索引+1（如上图中的11）。如果leader与某个follower的日志不一致，那么下一次AppendEntries RPC将会失败，此时leader会递减nextIndex并重试RPC。最终nextIndex将指向最新一致点，RPC也将成功，这将覆盖follower中不一致的条目，并复制leader中的条目。
使用这种机制，新的leader在掌权时不需要采取任何特殊操作来恢复日志一致性。它只是开始正常操作，日志将自动收敛以响应一致性检查的失败。leader从不覆盖或删除自己日志中的条目。

5.4 Safety

前面描述了Raft如何选择leader和复制日志条目。然而，到目前为止描述的机制还不足以确保每个状态机均以相同的顺序执行完全相同的命令。例如，当leader提交多个日志条目时，follower可能不可用，然后它可以被选为leader并用新条目覆盖这些已提交的旧条目；因此，不同的状态机可能会执行不同的命令序列。
本节通过添加对哪些服务器可以被选为leader的限制来完成Raft算法。该限制确保任何给定term的leader都包含以前term已提交的所有条目。

5.4.1 Election restriction

Raft使用投票过程来阻止未包含所有提交条目的candidate赢得选举。candidate必须联系集群中的大多数服务器才能成为leader，如果candidate的日志至少与大多数服务器的日志一样up-to-date（下面有精确的定义），那么可以认为它保存了所有已提交的条目。RequestVote RPC实现了这一机制：RPC会包含candidate的日志信息，如果接收到该RPC的服务器认为自己的日志比candidate的日志更加up-to-date，那么该服务器不会给candidate投票。
Raft通过比较日志中最后一个条目的索引和term编号来确定两个日志中的哪一个更加up-to-date。如果日志的最后一个条目具有不同的term编号，那么具有较大term编号的日志更加up-to-date。如果日志以相同的term编号结束，那么哪个日志的条目更多，哪个就更加up-to-date。

5.4.2 Committing entries from previous terms

下图展示了一个问题，存在一个旧日志条目已经被复制到大多数机器上，但没有被commit，最终被后来的leader覆盖的情况。
一开始S1是leader，并且在term 2（a）追加了一个新日志条目，索引为2。在term 3（b）时，S1崩溃了，S5被选举为新的leader（投票来源于自己、S3和S4），然后接受了一个新日志条目，并追加到自己的日志上。在term 4（c）时，S5崩溃了，S1重启并被选举为新的leader，同时，继续copy它在term 2接收到的日志条目，而且已经copy到大多数服务器上了，但是还没来得及commit。在term 5时，如果S1崩溃了，就会出现如下图（d）的结果，S5会被选举为新的leader，并且将覆盖所有服务器的日志。

为了消除上述问题，Raft不通过计算条目的副本来提交之前term所接收到的日志条目。只有leader在当前term所接收到的日志条目才通过计算副本来提交；一旦以这种方式提交了当前term的条目，那么所有先前的条目都会间接提交。

5.5 Follower and candidate crashes

follower和candidate的崩溃比leader崩溃更容易处理，并且它们都以相同的方式处理。如果某个follower或candidate崩溃，那么发送给它的RequestVote和AppendEntries RPC将失败。Raft通过持续重试来处理这些失败；如果崩溃的服务器重新启动，那么RPC将成功完成。如果服务器在完成RPC后但在响应之前崩溃，那么它将在重新启动后再次收到相同的RPC。由于Raft的RPC是幂等的，所以这没有什么影响。例如，如果follower收到一个包含其日志中已经存在的日志条目的AppendEntries请求，它会忽略新请求中的条目。

5.6 Timing and availability

本文对Raft的要求之一是安全性不能取决于时间：系统不能仅仅因为某些事件发生得比预期的更快或更慢就产生不准确的结果。然而，可用性（系统及时响应客户端的能力）不可避免地取决于时间。例如，如果message交换比服务器崩溃的典型时间更长，candidate就不会赢得选举；没有稳定的leader，Raft就无法取得进展。
leader选举是Raft中时间最关键的方面。只要系统满足以下时间要求，Raft将能够选举和保持一个稳定的leader：
broadcastTime << electionTimeout << MTBF
其中，broadcastTime是服务器向集群中每台服务器并行发送RPC并接收它们响应所花费的平均时间；electionTimeout是5.2节描述的election timeout；MTBF是单个服务器故障之间的平均时间间隔（多久发生一次故障）。boardcastTime应该比electionTimeout少一个数量级，这样leader就可以在follower启动新的选举前，可靠地发送heartbeat信号，从而阻止follower启动新选举。electionTimeout也应该比MTBF少几个数量级，使得系统稳步进展，当leader崩溃时，系统将在election timeout期间不可用，希望这只代表很短的时间。
broadcastTime和MTBF是不确定的系统属性，而electionTimeout是可配置的。Raft的RPC通常需要将信息持久化到稳定存储中，因此broadcastTime可能在0.5毫秒到20毫秒之间，具体取决于存储技术。因此，electionTimeout可以在10毫秒到500毫秒之间进行配置。通常，服务器的MTBF为几个月或更长时间，很容易满足时序要求。