3. 基础Raft算法

本章介绍了Raft算法。我们努力将Raft算法设计的更容易理解；第一部分描述了我们的可理解性设计方法。接下来的部分描述了Raft算法本身，并包括了我们为可理解性所做的设计抉择。

3.1 为可理解而设计

我们在设计Raft算法时有几个目标：它必须为系统建设提供一个完整和实用的算法基础，从而显著减少开发人员所需的设计工作；它必须在所有条件下都是安全的，在典型操作条件下可用；它必须对常规的操作保持高效。但我们最重要的目标，也是最困难的挑战，是可Raft算法的可理解性。必须使得大量读者能够轻松地理解该算法。此外，必须能够直观的指导开发者进行算法的工程化开发，以便系统构建者能够实现面对问题时所采取的不可避免的算法扩展。

在Raft的设计中，我们不得不面临在多种可行方法中的抉择。在这些情况下，我们基于可理解性来评估替代方案：评估解释每种替代方案有多难(例如，它的状态空间有多复杂，它有复杂的隐含内容/信息？)，并试图评估读者要完全理解Raft算法及其隐含的信息会有多容易呢？

我们认识到，这种分析具有高度的主观性，虽然如此，我们还是使用了两种可行的技术来进行评估。第一种是问题解构（将一个大问题分解成多个小问题），例如我们将Raft算法整体上拆分成了Leader Election、Log Replication和Safety三个部分。第二个方法是通过减少需要考虑的状态来减少状态机的状态空间，尽可能使得共识算法具有有条理并且消除其中的不确定性。具体来说，Raft算法不容许日志中具有空洞（空洞就是在某个条目上没有相应的内容，而后面的条目却有内容，这是Paxos算法的一个缺点），而且Raft算法限制了日志产生不一致的可能性（通过Leader选举的限制以及只有Leader作为主数据源的限制，保证了Follower之间不会存在日志内容的互相传输，只要与Leader保持一致就好，减少了各个服务器上日志不一致的可能性）。虽然我们极力的避免算法中的不确定性，但是有的时候我们也通过这种不确定性来增强算法的可理解性（这就是以可理解性为首要目标的表现），例如，随机的方法引入了不确定性，但是这可以减少状态空间（通过随机的方法来避免处理系统中出现的需要处理多种可能的问题，如在Leader选举的时候，不同的Candidate通过超时来进行下一轮选举的发起，这样避免了Raft算法来处理每个算法无法胜选的情况）。

3.2 Raft概览

Raft算法是一种管理第2.1节所述形式的日志副本的算法。图3.1总结了算法以供参考，图3.2列出了算法的关键属性；本章其余部分分段讨论。

Raft首先选择一个服务器作为Leader，然后让领导者完全负责管理系统中的日志副本。Leader接受从客户端Client获取的日志条目（Log Entry），在其他服务器上复制它们，并告诉服务器何时将日志条目应用到其状态机是安全的。通过Leader管理这种方式简化日志副本的管理。例如，Leader可以在不咨询其他服务器的情况下决定在日志中放置新条目，并且数据以简单的方式从头Leader流到其他服务器（Follower或者Candidate）。Leader可能发生故障或与其他服务器断开，在这种情况下，一个新的Leader会被选出来。

通过基于Leader的方法，Raft算法将共识问题分解为三个相对独立的子问题：

• Leader Election（Leader选举）：当集群刚启动时，或者当前Leader失效时，集群中必须有一个新Leader会被选出来；

• Log Replication（日支复制）：Leader必须接收Client发出的log entry（log entry存储Client发出的请求/命令，这里将log entry等同于Client的请求/命令），并且要将这个log entry在集群中的其它服务器上进行副本的备份，强制其它服务器上的log以Leader上的Log为准；

• Safety（安全性保障）：Raft算法最重要的安全性就是状态及安全性（如图3.2所示），如果系统中有任意一个服务器已经apply一个log entry到自己的状态机中，那么其它服务器不会在相同的log index处apply不同的log entry（这个是由Raft算法通过Log一致性来保证的，具体的证明在文章后面）。这个保证由一个算法中提出的一个在Leader选举是的额外的限制条件来保障（详见第3.4小节）。

在介绍了Raft共识算法之后，本章讨论了可用性问题和系统中计时的作用（第3.9节），以及在服务器之间Leader转换的可选扩展（第3.10节）。

Raft算法相关特性

图3.2的说明：
Raft算法的关键性质：
(1)Election Safety（Leader选举的安全性，所谓的安全性就是系统中不会发生不该发生的事情）：在某一个特定Term（这里就叫任期吧）内，最多有一个Leader能够被选出（那么不该发生的事就是一个任期内有多个Leader被选出，在Raft算法中，这是不会发生的）；
(2)Leader Append-Only（仅追加）：一个Leader仅仅会在它自己的Log追加Entry，绝不会删除或者覆盖已有的Entry（这是Raft算法能够实现单向数据同步的保证，试想，如果Leader的Log内容可以随便的改动，Follower不敢从Leader同步，因为不知道同步过后会不会又变了。而且，这个属性的基础来自于Raft算法有一个保障，那就是当选的Leader的Log一定是最完整、最新的，详细算法会在后面内容中叙述并证明）；
(3)Log Matching（Log匹配）：如果某两个服务器节点中的Log Entry有相同的Term以及Index，那么这两个节点的Log在Index之前的所有Entry内容一定相同；
(4)Leader Completeness（Leader完整性）：如果某个Log Entry已经在某个Term（任期）被commit，那么这个Log Entry一定会存在于以后所有任期的Leader的Log中；
(5)State Machine Safety（状态机安全性）：如果某个服务器已经在其状态机中Apply某个Log Entry，那么其它的服务器绝不会在相同的Log Index上Apply其它的Log Entry。也就是说，在所有状态机的Log上，只要是相同的Index，其对应的Entry的内容一定是一样的。

image.png

图3-1给出了Raft算法中关键的元素、操作以及原则，因为整张图太大，下面切分这个大图为4个小图来说明。

image.png

图3-1 State（状态）
1.Persistent state on all servers(在所有服务器上持久化State)
（在回复RPC请求前更新本地持久化存储内容）

• currentTerm，这台服务器已知的最新的Term，集群启动时默认为0，后面单调递增；
• votedFor，
• log[]，每个服务的log，每个log有若干个log entry，每个log entry就是一个客户端的请求/命令，这个请求/命令将在服务器的状态机上apply，这个log的每一个entry还会对应一个Term，就是这个log entry所属的Leader的任期，Log的索引初始值是1；
  2.Volatile state on all servers（每个服务器所具有的不稳定状态）（不稳定就是说可以丢失，比如宕机丢失）
• commitIndex，这个服务器已知的，已经被commit的，最新的（也就是最大的）log entry的index，初始值为0，单调递增；
• lastApplied，这个服务器在自己的状态机上apply的最大的log entry的index，初始值为0，单调递增；
  3.Volatile state on Leaders（Leader节点上的不稳定状态）
  （在选举后重新初始化）
• nextIndex[]，对于每一个服务器，Leader服务器节点都会保存自己下一次需要发给每一个其它服务器的Log Entry的index，Leader胜选后会进行初始化，初始化的值是这个Leader最新的Log Entry的index+1；
• matchIndex[]，对于每一个服务器，Leader服务器节点会保存其它服务器已经replicate的最新的log entry的index，初始值是0，单调递增；</pre>

<center style="box-sizing: border-box; margin-top: 0px; margin-bottom: 0px; color: rgb(192, 192, 192); text-decoration: underline;">图3.2-2 RequestVote RPC</center>

image.png

2. RequestVote请求，这是一个RPC请求

（candidate调用该请求来收集选票）

• Arguments（参数）

  • term，candidate的任期Term；

  • cadidateId，candidate的ID；

  • lastLogIndex，candidate的log里面最新的log entry的index；

  • lastLogTerm，candidate的log里面最新的log entry所归属的任期Term。

• Results（返回结果）

  • term，任期，回复这个RPC请求时，响应的那台服务器当前所处的任期Term；

  • voteGranted，投赞成票，当这个结果参数为true的时候，说明这个投票者同意选举该candidate为下一任Leader，反之，则是拒绝。

• Receiver implementation（该RPC接收者的处理逻辑）

  • 如果接收到该RPC请求的服务器当前所处的任期Term大于candidate的RequestVote请求中携带的term这个参数，那么说明candidate的发起的请求晚于当前的Leader，或者当前已经有新Leader被选出了，又或者这是一个延迟收到的请求，那么这个服务器将会回复false（也就是在Results的返回值中携带voteGranted=false）以示拒绝candidate的本次选举请求；

  • 如果接收到该RPC请求的服务器当前存储的voteFor里面是空或者是某个candidateID，而且这个candidate的log和当前这个服务器的log一样新或者比当前服务器的log还新，那么这个服务器就会投票给这个candidate。（这个log的新旧比较就是根据最新的log entry的index来比较的）。

image.png

3.AppendEntries RPC，这是一个RPC请求，用于Leader向Followe同步log entry，Leader通过这个RPC请求要求Follower追加log entry以实现log的同步

（被Leader调用以用于进行log entry的备份，这个请求也会肩负心跳检查的功能）

• Arguments（参数）

  • term，任期，这个Leader所属的任期Term；

  • LeaderId，Leader服务器的ID，当前Leader的ID，Follower可以根据Leader的ID将用户请求转发给正确的Leader；

  • prevLogIndex，紧接在新log entry之前的那个log entry的index；就是待插入的log entry之前的那个log entry的index；

  • entries[]，需要在某个Follower服务器上同步的log entry的集合（如果为空，这个RPC请求仅仅作为心跳检测来用，这里面可以携带多个log entry，以提升log entry的复制效率）；

• Results（返回值）

  • term，任期，接收到这个RPC请求的服务器当前所在的任期，用于给Leader更新自身相关的信息，如Leader存储的关于这个Follower的信息；

  • success，成功标志，如果接收到这个RPC请求的服务器当前的prevLogIndex和prevLogTerm与这个RPC消息中携带的匹配，那么返回true；否则，返回false；

• Receiver implementation（该RPC接收者的处理逻辑）

  • 如果接收到该RPC请求的服务器当前所处的任期Term大于Leader的AppendEntries这个RPC请求中携带的term这个参数，那么说明这个Leader已经是无效的Leader，则会回复false，表示拒绝更新log entry；

  • 如果接收到该RPC请求的服务器当前的prevLogIndex和prevLogTerm与这个RPC消息中携带的不匹配，则说明这次log entry更新不合适，这个服务器也会拒绝更新，并回复false；

  • 如果接收到该RPC请求的服务器当前的prevLogIndex和prevLogTerm与这个RPC消息中携带的匹配，但是相应的log entry已经有内容了，那么就删除当前的log entry，用RPC消息中的log entry更新相应log entry；（这儿就体现了在Raft中，log entry的内容以Leader的为准）

  • 如果接收到该RPC请求的服务器当前的log entry为空，那就直接更新（用这个RPC中的entries[]的内容）；

  • 如果接收到该RPC请求的服务器当前的commitIndex小于Leader的leaderCommit（个人猜测：整理的LeaderCommit没有在RPC消息中携带，是不是根据entries[]这个参数推导出来？），那个这个服务器就要保存当前已经commit的log entry的index，也就是自己的commitIndex，commitIndex选取leaderCommit和本地最新的log entry的index之间的最小值（这儿有个疑问，这个服务器什么时候会commit这些log entry呢？）。“这里的疑问等看完后面的内容再更新”

为了说明prevLogIndex和prevLogTerm比较的方案，请看下图。

image.png

图中的Leader和Follower的任期都是3，Leader里面的log entry比Follower的新，所以Leader需要发送AppendEntries请求以使Follower同步这些log entry。这是，RPC请求内的prevLogIndex和prevLogTerm分别为i-1和3，当Follower接收到这个RPC请求时，其当前的log entry的index=i-1，任期为3，与RPC消息中的prevLogIndex和prevLogTerm匹配，那么Follower就可以使用entries[]里面的log entry来填充自己的i到n。如果Follower的最新的log entry的index（这里暂时成为FollowerIndex）不等于i-1，这里又分成两种情况，第一种，FollowerIndex<prevLogIndex，说明这个Follower的log还有缺失，那这个Follower会回复false，Leader会重新更新prevLogIndex、prevLogTerm以及entries[]并再次发起AppendEntries请求（后面的章节会详细介绍）；第二章情况，FollowerIndex>prevLogIndex，说明Follower已经同步了prevLogIndex和prevLogTerm后面的log entry，但是，后面的log entry的内容是不是和RPC请求中相同？而且prevLogIndex和prevLogTerm这个log entry里面的内容是不是与Leader的相同？“这里的疑问等看完后面的内容再更新”

image.png

4. Rules for Servers，集群中服务器需要遵守的规则

• 所有服务器需要遵守的规则

  • 如果commitIndex>lastApplied，那么lastApplied增加（这里应该是一个一个增加），并将log[lastApplied]这个log entry在状态机上执行；

  • 如果RPC请求或者相应的回复中携带的term T>currentTerm，那么设置当前的term，也就是currentTerm=T，并立即更换角色为Follower；

• Follower服务器需要遵守的规则

  • 必须回复candidate或者Leader发出的RPC请求；

  • 如果在预设的超时时间内没有收到Leader发出的AppendEntries请求或者未回复candidate发出的RequestVote请求，那么立即变换成candidate角色；

• Candidate服务器需要遵守的规则

  • 一旦成为candidate，那就立即发起选举请求：

    • 增加term；

    • 给自己投票；

    • 重置选举计时器；

    • 发送RequestVote请求给其它服务器；

  • 如果收到了大部分其它服务器的赞成票，那么就变成了Leader；

  • 如果收到了新Leader发送的AppendEntries请求，变成Follower；（这里判断Leader是不是新Leader就是根据自己的Term和AppendEntries请求中的term进行比较）

  • 如果选举超时，重新发起选举请求；

• Leader服务器需要遵守的规则

  • 获选后，先发送空的AppendEntries消息来通知胜选消除，然后通过发送AppendEntries消息来维持心跳，即使没有log entry需要同步也要定期发送维持Leader的地位；

  • 当收到client的command请求时，先把command保存到本地的log entry中，当本息的状态机apply这条command后再回复client（这里本地的状态机的apply的条件应该是集群中大部分的Follower已经正确保存了这个command）；

  • 如果最后一个log entry的index大于某个Follower的nextIndex，那么就向这个Follower发送AppendEntries消息，消息中携带从nextIndex开始到最后一个log entry的index的内容；

    • 如果AppendEntries收到Follower的回复并有success=true，说明Follower成功备份了相应的log，那么更新本地存储的关于这个Follower的nextIndex和matchIndex的信息；

    • 如果AppendEntries收到Follower的回复并有success=false，说明Follower无法成功备份相应的log，那么Leader就要减小nextIndex并重试；

  • 如果存在N>commitIndex，而且大部分的Follower的matchIndex[i]>=N，而且log[N].term=currentTerm，那么设置commitIndex=N；（大部分的Follower都commit了某些日志后，那么Leader就可以认为这些log已经安全的存储了并被Apply，那么Leader就可以安全的认为这些log已经被Commit并在自己的本地信息更新已经commit的日志的信息，即commitIndex）

<< 上一章：Raft算法的目的
下一章：Raft算法基础 >>