MIT 6.824学习 raft论文

文章目录

• • raft 一种共识算法
  • • 1. Replicated state machines（复制状态机）
    • 2. Raft 共识算法
    • • 1.raft basics
      • 2.leader election
      • 3.log repliation
      • • log replication 开始
        • • 两条原则
        • 解决一致性的问题
      • 4.Safety
      • • 1.选举限制
        • 2.从之前的term提交entries
      • 5.Follower and candidate crashes
      • 6.Timing and availability
    • Cluster membership changes

raft 一种共识算法

读raft的论文报告 还要完成lab2 深入学习理解raft的过程

共识算法可以让一组机器一致的工作，并且在其中的一些机器发生错误的情况下还能正常工作，共识算法对构建一个大型的可靠的分布式系统非常重要

1. Replicated state machines（复制状态机）

复制状态机被用来在分布式系统中解决容错问题，

像图里面展示的，复制状态机通常会用一个复制的log实现。每个服务器都会存储一个log，log中存放一系列的命令。每个服务器的log中存放相同的命令，这样的话每一个服务器会执行相同顺序的命令，每个服务器的输出都是相通的。

---

保持log副本的一致性需要由共识算法来解决，服务器上的共识模型接受客户端的命令存放到自己的log中，并且和其他服务器上的共识模型进行沟通，保证所有服务器上的log都是一致的。即使有的服务器出现了错误，也需要正确运行。

2. Raft 共识算法

• raft 通过在一开始选举一个leader，然后把全部的log管理等等权限全都交给leader，这样可以简化系统操作
• raft的实现主要分为三个部分：= leader election，log replication，safety
• 构建raft的概括 论文也是放在一个大图里面
  
  
  
  

1.raft basics

• 一个raft集群有多个server，一般会有五个，这样的集群可以容忍有两个server出现错误。
• 每个server有三个可能的状态，分别是leader，follower，candidate。一般情况下一个集群有一个leader，其他的都是follower。

• follower不提出任何请求，他们只回应leadr和candidate的请求
• leader会处理所有client的请求，如果一个client联系了follower，那么这个请求会转给leader
• candidate是被用来选举下一个leader的状态

• raft 将时序分为terms，每个term的长度是任意的，terms用连续的整数来编号。每一个term都由一次选举开始，在选举中有一个或多个candidate申请成为leader，如果有一个candidate成功成为leader，那他就领导term的剩余部分。
• 会出现投票失败的情况，那么这一次term会在没有leader的情况下快速结束，并且开始下一个term。raft会保证每一次term都有一个leader。
• 每一个server都会保存当前的termnumber，这个term number会随时间增大，每个server的当前term在server进行交流时会进行交换。如果一个server的当前term比别的server落后一些，那么他会把他的当前term更新到最大。如果一个candidate或者leader发现他的当前term落后了，那么他会回退到follower状态。如果一个server收到了一个无效的termenumber，他会拒绝这个请求

• raftserver之间通过rpc来进行交流，一般只有两种方法RequestVote RPCs are initiated by
  candidates during elections (Section 5.2), and Append-
  Entries RPCs are initiated by leaders to replicate log entries
  and to provide a form of heartbeat (Section 5.3).

2.leader election

raft 的选举方法 选举再raft中非常重要，因为选举出的leader将会控制之后term的所有操作，包括和client进行交互，控制log entries的复制和传递

1. 什么时候开始选举

• 当初始化一个term时需要选举
• 当当前的leader fail或者失联的时候
• 当一次选举不成功需要重新选举

2. 如何进行选举

• 如果一个follower长时间没有收到leader的heartbeat信息，发生了超时，这时他会认为系统中没有leader了，这时一个follower就会将自己的状态转变为candadite。
• 包括所有之前就是candadite和后面转换到candadite的server，他们会并行的向其他server发送RequestVote RPCs，用来拉票，如果获得大部分票数就会宣布自己成为了leader
• 在拉票时，投票规则一般是先到先服务，就是每一个server会投给第一个先自己发送请求的candadite，当然如果自己处于candadite，他会投给自己
• 选举会发生失败，有可能没有获胜的server，因为如果所有的server都在同时发送拉票请求，那么票数就会分散，这样没有一个server可以获得大部分票数（这个通过随机设置election timeout，和随机设置server的开始投票时间来解决

3. candadite在选举中的操作

• 1.他自己成为了获胜者

当一个candadite获胜以后，他会向所有的server发送heartbeat，宣告自己的身份是leader

• 2.他输了，有别人获胜

这时是收到了其他server发来的heartbeat消息，这时他会比对消息中的term number，如果比自己的term number大或者一样，那么他会认可这个leader，但是如果比自己的term number要小，他会拒绝承认这个new leader

• 3.没有人获胜

开启下一轮投票选举，并且term number会增加

3.log repliation

看完论文以后对log replicate 过程的一些理解 可能有错误 需要继续学习

log replication 开始

• 1.当一个leader确定自己是leader以后，他就会开始工作了，那他第一件事就是接受client的请求，而一般这种请求中就会包含需要rsm执行的命令。
• 2.leader会把这些命令先存放到自己的log中，每一个log都会记录下他所在的term number，并且会有一个log index来确定他在log中的位置，然后通过AppendEntries RPCs来复制给其他的server。
• 3.当几乎所有的server都返回成功replicate的消息以后，他才会把命令提交给rsm并且把执行的结果返回给client，当leader决定一个log可以安全的提交给rsm后，这样的log被称为commited。
• 4.raft要保证所有commited的log都是持久的，并且都会被其他server提交给rsm，这需要leader来保证。在AppendEntries RPCs中有一个leaderCommit
  leader’s commitIndex 的参数，记录leader提交的最后一个log，每次这个消息发给follower，follower发现自己log entries中的某个log已经被commit了，那么它也将这个log提交给rsm。保持一致性

两条原则

下面是raft需要保证的两条规则

1. 如果不同日志中的两个条目具有相同的索引 和term，则他们存储的命令是相同的
2. 如果不同日志中的两个条目具有相同的索引 和term，则上述所有 条目的日志都是相同的

解决一致性的问题

• 1.在初始化没有entry的情况下 ，leader，follower都是一致的
• 2.在添加新的entry时需要保证一致性，我们需要对当前一致性进行检查，这个检查怎么进行呢，论文里面说是通过AppendEntries RPCs来做的一致性检查，在这个消息中要包含要添加的entry之前的刚被commiter的entry的log index 和term 在图二中就是这俩 I.prevLogIndex index of log entry immediately preceding new ones
  II. prevLogTerm term of prevLogIndex entry
  follower在收到消息以后要看对应位置的entry和leader所给的一致不一致，这就完成了一致性检查
• 3.一致性检查一般都会sucessful，但是如果leader在commit一个entry失败了，还没完成就crash了，那就有可能出现不一致，这种就需要解决
• 4.解决上面的问题也是leader的工作，还是用AppendEntries RPCs，在follower中找到不一致的点，并且这一点只以后的entry全部删除，将leader中这点之后的entry复制到follower中，leader从来都不会删除自己的log entry记录。这样的话就会重新一致。

4.Safety

• 之前的一些方法都没办法真正保证命令的执行顺序，也不能保证每个状态机都执行相同的命令，例如一个follower没有成功复制到当前leader执行的log entry，但是之后他被选举成为了leader，并且可能会把之前的log entry进行删除重写，这样就会出现错误，每个状态机就会出现运行不同的命令的情况。

1.选举限制

• 为了消除前面所说的错误，在选举过程中设置一些限制。具体来说就是raft保证，在选举过程中，只有包含所有其他follower包含的log entry的candadite才能成为leader，candadite在选举过程中要联络大部分的follower，如果candadite的log entry比所有的follower都要新，那么可以保证它包含所有的log entry，这个过程在拉票的时候实现，在拉票时里面会包含candadite的log entries，如果follower发现自己的比candadite的log entries要新，就会拒绝投票。raft通过比较最后一个log的index和term来决定谁的更新，如果他们的term不一样，那么谁的term大谁新，如果term一样，那么谁的term长谁新。

2.从之前的term提交entries

• 当一个leader在提交一个entry的时候挂了，那么新的leader就会尝试结束复制entry。但是leader不能很快的推断出之前的这个entry有没有被提交
• 为了解决这个问题，raft从来不使用计数的方法来判断之前的entries是否被提交，他只在判断当前的term时使用计数，这样延续下去的话可以间接保证之前的entry都被提交。
• raft中，leader重新复制之前term的log entry会保留之前的term号，这样可以更容易溯源entries

5.Follower and candidate crashes

• follower和candadite挂掉比leader挂掉好处理很多
• raft用无限重试来处理这些fail，当一个follower挂掉了，那么发给他的消息都会失败，但是一直发，等他重新启动以后，发给他的RequestVote and AppendEntries RPCs信息就会成功，如果收到的log entry他已经有了，那么他会忽略。

6.Timing and availability

• broadcastTime≪electionTimeout≪MTBF

• broadcastTime is the average time it takes a server to send RPCs in
  parallel to every server in the cluster and receive their responses;

• electionTime out is the election timeout described in Section 5.2; and

• MTBF is the average time between failures for a single server.

• the broadcast
  time may range from 0.5ms to 20ms, depending on
  storage technology. As a result, the election timeout is
  likely to be somewhere between 10ms and 500ms. Typical server MTBFs are several months or more, which easily
  satisfies the timing requirement

Cluster membership changes