背景

网上关于Raft的博文已经足够多了，这里只记录个人学习Raft协议中一些关键的地方。参考的资料是Raft和作者的PhD的Raft论文还有Raft的C++实现floyd。

Raft协议

Raft协议用来保证数据的一致性，它是根据Leadership的方法来完成日志的复制，Leader接受来自Client的数据，然后将数据复制到其他的Server，如果一个Leader失败或者断开连接，一个新的Leader将会选举出来。Raft基本上可以分为三个子问题:

  • Leader election
  • Log replication
  • Safety

Raft基本知识

先来介绍一些Raft的基本知识。首先，Raft算法中维护三种状态：Leader，Follower和Candidate。当具体操作时，集群中有一个Leader，剩下的节点均为Followers。Followers只响应来自Leader或者Candidate的请求，而Leader响应来自Client的请求，如果有Client请求发送至了Followers，会被转发至Leader。

Raft协议将一个Leader的任期称作一个Term，Term是任意长度的时间片，Term的Number是顺序递增的。

Raft协议通信主要使用两种类型的RPC:

  • AppendEntries RPC：复制Log和发送心跳
  • RequestVote RPC：Candidate发起投票

Leader election

Imgur

Raft协议利用心跳机制来触发选举，当集群中的Server启动时，它们都是Followers状态。当某一个Folloer到达了自己的Election timeout，它就会发起选举:

  • 自增Term的Number
  • 将自己的状态从Follower转为Candidate
  • 投票给自己
  • 发送RequestVote RPC给其他的所有节点

一个Candidate保持这种状态直到三种情况发生:

  • 它赢得了选举
  • 其他的Candidate节点赢得了选举
  • 没有任何Candidate节点赢得了选举

如果一个Candidate在一个Term内获得了超过半数的投票，它就赢得了选举，成为了这个Term任期内的Leader。每一个节点在一个Term内只能投票给一个Candidate，秉承先来先投的原则，并且Raft协议中每一个节点使用一个随机的限定区间的election timeout(150-300ms)。这两个规则确保了在大部分情况下只有一个Candidate可以赢得选举，保证分裂投票的最大可能的降低发生概率。当一个Candidate成为了Leader之后，它就会发送心跳包给其他节点防止开始新的选举。

Log replication

state_machine

  • Leade收到一条来自Client的命令，写入本地的Log，之后调用AppendEntries RPC并行的向所有Follow节点发送该Log
  • 当Leader发送一个AppendEntries RPC时，会包括新的Entry Log之前的那条Entry Log的Term和Index，Follower会根据前一条Entry Log的Term和Index做安全性的检查，如果没有发现该条Log，它会拒绝新的Entry Log。
  • 如果这条Entry Log被大部分节点接受，这条Log就会被Apply至状态机，这样的一条Log称为Committed。Leader将执行结果返回给Client。

Raft的Log replication要求保证一下性质:

  • 如果两个log entry有相同的index和term，那么它们存储相同的指令。
  • 如果两个log entry在两份不同的日志中，并且有相同的index和term，那么它们之前的log entry是完全相同的。

在某些意外情况下，比如Leader的崩溃退出，有可能导致Leader和Followers的日志不一致的情况，双方通过AppendEntries RPC来做一些一致性的检查:

  • Leader为所有的Followers维护一个nextIndex[]用来表示下一条需要发送给Follower的Log的Index，AppendEntries RPC会带一个新的Log和上一个Log的Index和Term。如果双方的Log不一致，AppendEntries RPC的一致性检查将会失败，Leader会减一次nextIndex然后重发AppendEntries RPC直到Follower和Leader的日志成功匹配。

Safety

Election restriction

发起投票的RequestVote RPC包括Candidate的日志信息: Index和Term，假如Follower的日志信息比Candidate，就会拒绝投票。Raft限制新的Leader拥有最大的Term和最新的Log信息。

Committing entries fron previous terms

Raft限制Leader只能对自己当前任期内的Term的Log做提交Commit。

Cluster membership changes

Raft配置信息变更中存在三个状态:

  • Cold即旧的配置信息生效的状态
  • Cold，new即新旧配置文件都生效的状态
  • Cnew即新的配置文件生效的状态

在Raft设计中，成员变更也是作为一条Log，Leader首先创建一条关于Cold,new的配置信息变更的Log，当被Cold配置中的大部分节点和Cnew配置中的大部分节点接受，然后再创建一条Cnew配置信息的Log，保证Cnew配置中的大部分节点接受。

配置信息中有三个子问题需要注意:

  • 当新的空节点加入集群后，它有可能长时间处在追赶Log的过程中，从而导致配置变更的Log无法生效。Raft为此引入了一个新的节点状态non-voting members(Leader发送日志给新的空节点，但它们不被考虑在大多数的条件范围内)，直到新的节点追上了集群，才开始做配置变更。
  • 目前整个集群的Leader可能不在新的配置文件中。在这种情况下，当Cnew配置信息变更Log被Committed之后，它会将自己的状态降为Follower.
  • 移除的节点干扰集群。因为这些节点无法收到心跳，所以超时之后会发起选举。因为发起选举前会自增Term，所以会造成现在集群内的Leader失效。为了防止这种情况，Raft限制当一个Follower节点会在收到来自Leader的选举超时周期内拒绝别的节点发来的RequestVote RPC。