raft算法

发表于 更新于 分类于 本文字数： 4k 阅读时长 ≈ 4 分钟

本文参考了：
https://www.infoq.cn/article/raft-paper （raft paper的中文翻译）
http://www.calvinneo.com/2019/03/12/raft-algorithm/

学习任何一个新知识点我们都要先问下自己这个主要是解决什么问题的，它的优点是在哪里。

前提

首先我们要知道这个算法里都有哪些角色：

  1. Leader： 领导者
  2. Candidate： 候选者
  3. Follower： 跟随者
  4. State Machine: 状态机（就是将本地日志里的内容按顺序进行，最终得到的结果应该是一样的）

这些角色都带有哪些属性呢？

  1. 共有的属性
  • currentTerm: 服务器当前的任期号（从 0 开始递增）
  • voteFor： 在当前任期内收到选票的候选人 id（如果没有就为 null）
  • log[]： 日志条目；每个条目包含状态机的要执行命令和从领导人处收到时的任期号
  • commitIndex：已知的被提交的最大日志条目的索引值（从 0 开始递增）
  • lastApplied： 被状态机执行的最大日志条目的索引值（从 0 开始递增）
  1. Leader专有状态
  • nextIndex[]： 对于每一个服务器，记录需要发给它的下一个日志条目的索引（初始化为领导人上一条日志的索引值 +1）
  • matchIndex[]： 对于每一个服务器，记录已经复制到该服务器的日志的最高索引值（从 0 开始递增）

那这个算法要处理哪些问题呢？

  1. Leader election（Leader选举）
  2. log replication （日志同步）
  3. safety （安全）
  4. memebership change （角色变更）

Leader election

首先在raft协议里，Leader同时只能是有一个的。

整体流程可以参考官方的示意图。整体流程就是如此，在投票中，大家都会先投票给自己，然后再广播出去，这样谁先发广播谁就有优势。

首先我们了解到这当中有2个rpc，一来一回。

RequestVoteRPC

  1. term：表示候选人的任期号。这个在一个集群内都是一直累加上去的，不会因为切换了Leader重新开始
  2. candidateId： 候选人的id
  3. lastLogIndex和lastLogTerm：表示候选人的最后日志条目的index和term

RequestVoteRPC Response

  1. term: 任期号
  2. voteGranted: 是否同意

那我们看下选举的过程是怎么样的：

  1. 递增自己的currentTerm
  2. 发送RequestVoteRPC给其他所有节点。

选举的原则

  1. 远端的term不能小于自己的term。（就是RequestVoteRPC里传递的term号不能小于自己当前的）
  2. 远端的lastLogTerm不能小于自己的lastLogTerm
  3. 如果远端的lastLogTerm和自己本地的一样。那么远端的lastLogIndex不能小于自己的lastLogIndex
  4. 看谁先发出Request(所有的节点默认会在150ms~300ms对外发布Request或者心跳)。所以在一个内网的情况下，这个很难会重合相等。因此在一个稳定的集群里，以上条件可能都是会通过的，最后就看谁快了。
  5. 选举需要获得(N/2+1)节点通过。
    这个就让我想起了路由里的OSPF的选举规则，这个协议的选举明显就会复杂很多，有各种各样的权重在进行控制。但是这种路由协议本身不存储数据本身，所以在数据同步上没有任何可定义的。而raft这个就会有很多的日志同步的部分。这个我们后面再说。

而这里为什么选举的原则会是这样，是因为有2个断言：

  1. 当Leader创建的某条日志条目被成功复制到过半数的服务器上时，Leader可以提交该条目。（commit）
  2. 如果两份日志最后的条目的term不同，那么term大的日志新。如果两份日志最后的条目term相同，那么日志长的那个就新。·

那就分几种情况:

  1. 自己成为Leader。给其他服务器发送空的AppendEntries RPC，表明自己已经成为了Leader了。
  2. 别人成为Leader，自己成为了Follower，然后开始同步Leader的日志。
  3. 选举失败, 那就再开始一次选举。

各种意外情况：

  1. 脑裂：一个raft协议的集群分裂成多个，由于需要一半以上的节点同意，所以这种情况下也会只有一个集群里有Leader存在，而别的集群就都是candidate, 一直到网络恢复后变成Follower。

log replication

这个是为了保证强一致性。一致性算法是在复制状态机的背景下提出来的。具有如下的特点：

  • 确保安全性（从来不会返回一个错误的结果），在所有的非拜占庭（Non-Byzantine）情况下，包括网络延迟、分区、丢包、冗余和乱序的情况下。
  • 高可用性，只要集群中的大部分机器都能运行，可以互相通信并且可以和客户端通信，这个集群就可用。因此，一般来说，一个拥有 5 台机器的集群可以容忍其中的 2 台的失败（fail）。服务器停止工作了我们就认为它失败（fail）了，没准一会当它们拥有稳定的存储时就能从中恢复过来，重新加入到集群中。
  • 不依赖时序保证一致性，时钟错误和极端情况下的消息延迟在最坏的情况下才会引起可用性问题。
  • 通常情况下，一条命令能够尽可能快的在大多数节点对一轮远程调用作出相应时完成，一少部分慢的机器不会影响系统的整体性能。

AppendEntries RPC格式

在raft协议里是使用AppendEntries RPC来进行通信的，它包含如下：

  1. term: 领导人的任期号
  2. LeaderId: 领导人的 id，为了其他服务器能重定向到客户端
  3. prevLogIndex: 最新日志之前的日志的索引值
  4. prevLogTerm: 最新日志之前的日志的领导人任期号
  5. entries[]: 将要存储的日志条目（表示 heartbeat 时为空，有时会为了效率发送超过一条）
  6. LeaderCommit: 领导人提交的日志条目索引值

跟投票一下，还有一个回复的RPC, 格式定义如下：

  1. term： 当前的任期号，用于领导人更新自己的任期号
  2. success： 如果其它服务器包含能够匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

Log Replication过程

在replication过程中， 一旦当前Leader创建的某条日志被成功的复制到过半数的服务器上时，这个Leader就可以提交该条目及自己日志中该条目之前的所有条目。即使这个条目是由其他Leader创建的。（因为所有的条目之前都是确认复制到过半的机器上了。）
Leader还通过AppendEntries中的LeaderCommit字段来告知Follower自己当前的提交位置。而Follower就根据在这个字段来进行本地提交，直到commitIndex的日志。

当Leader刚选举成功的时候，它是不知道各个Follower的日志相对于自己的情况的，因此默认nextIndex[]都为自己最后一条日志加一。但这样发出去的日志可能不被接受，因为如果Follower没有Leader的最后一条日志，那么它肯定不能匹配Leader发送的AppendEntriesRPC中的prevLogIndex和preLogTerm所标记，因此它会返回给Leader一个拒绝，此时Leader就会减少对应的nextIndex并重试。

从这个来看，所有的replication都是Leader主动进行发起的，因为只有Leader才知道自己是Leader当选举刚结束的时候。

当Follower和Leader不一致的时候，raft就强制Follower直接同步Leader的日志。同时Raft禁止提交一个较旧的term的条目，即使它已经被复制到大部分的节点。（但这种情况应该很难会发生，因为这种在选举的可能就不会被选为Leader）

下面我们列举了3种场景，基本可以模拟大部分的环境了。

  1. Log Replication过程已经提交后宕机，重新选举再复制。
    这个时候选举的话，由于S2和S3的lastLogIndex比S4和S5都要高，因此新的leader只能是S2和S3里的其中一个。已知5个服务器的集群只能最多宕机2台，因此S1，S2，S3里随意宕机哪台，最终选举新的leader也是剩下的那1台，不会是S4或者S5

  2. Log Replication过程还没提交，宕机，然后重新选举再复制。
    这个时候选举的话，由于B只有2个节点，因此重新选举的话S2,S3,S4,S5都有可能成为新的leader。我们假设S5成为了新leader。由于S5上已提交的状态是A，因此这个时候S5会同步自己的状态1到其他4个节点上。这样原先S1,S2上的状态B就丢失了。

  3. Log Replication过程还没提交，宕机，然后重新选举再复制，还没提交又宕机，又重新选举再进行复制。
    这个时候选举的话，由于状态A只有2个节点，因此重新选举的话S2,S3,S4,S5都有可能成为新的leader。我们假设S5成为了新leader。然后S5创建了新的状态C，同步到S4的时候就宕机了又。
    这个时候选举的话，状态B只有2个节点，状态C也只有2个节点，谁都没超过大多数，这时候虽然S4，S5会拒绝给S1,S2,S3节点投票，但是S1,S2也可以通过S1,S2,S3投票成为Leader，那这个时候S4,S5的状态C就丢失了。

Membership changes

在raft中当有新服务器，新配置加入到集群中，为了维护Leader与term一一对应的关系不被打破，会提供一个joint consensus的配置，这样就不会存在新老配置的问题了。

要求如下：

  1. 日志条目应当被复制到对应新旧配置两种配置的所有机器上。
  2. 两种配置中任意服务器都可以作为Leader。
  3. 选举和提交日志的共识必须同时经由两种配置的多数服务器同意。