Raft 可视化网站：raft.github.io

Raft 是一种用于替代 Paxos 的共识算法。Raft 这一名字来源于"Reliable, Replicated, Redundant, And Fault-Tolerant"（可靠、可复制、可冗余、可容错）的字母缩写。

基础知识

节点类型

一个 Raft 集群包括若干节点（服务器），每个节点都处于以下三个状态中的一个：

  • Follower(追随者) ：节点的初始状态，响应 Leader 的日志同步请求，把客户端请求的事务转发给 Leader

  • Candidate(候选者) ：Follower 到 Leader 的中间状态。当 Follower 认为 Leader 下线后，会尝试申请为新的 Leader，此时状态转换为 Candidate 发起投票，若获得超过半数投票则转换为 Leader

  • Leader(领导者) ：负责日志的同步，处理来自客户端的请求，发送心跳包到 Follower

Raft 节点的状态转换图

Raft刚启动的时候，所有节点初始状态都是Follower，每一个节点都设置了一个随机的超时时间，这个时间一般是在150毫秒到300毫秒之间。超时时间内如果没有收到Leader的请求则转换为Candidate角色并发起Leader选举。如果Candidate收到了多数节点的选票则转换为Leader；如果在发起选举期间发现已经有Leader了，或者收到更高任期的请求则转换为Follower。Leader在收到更高任期的请求后转换为Follower。

Term（任期）

Raft 算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

  • 每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号；

  • 如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值；

  • 如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower；

  • 如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求。

日志

entry ：每一个事件成为 entry，只有 Leader 可以创建 entry。entry 的内容<term, index, cmd> ，其中 cmd 是可以应用到状态机的操作。

log ：由 entry 构成的数组，每一个 entry 都有一个表明自己在 log 中的 index。只有 Leader 才可以改变其他节点的 log。entry 总是先被 Leader 添加到自己的 log 数组中，然后再发起共识请求，获得同意后才会被 Leader 提交给状态机。Follower 只能从 Leader 获取新日志和当前的 commitIndex，然后把对应的 entry 应用到自己的状态机汇总。

Leader 选举

Raft 使用心跳（heartbeat）触发Leader选举。当服务器启动时，初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat，就会等待一段随机的时间后发起一次Leader选举。

Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送投票请求。结果有以下三种情况：

  • 赢得了超过半数的选票，成功选举为 Leader；

  • 收到了 Leader 的消息，表示有其他服务器已经抢先当选 Leader，退回为 Follower；

  • 没有节点赢得超过半数选票，Leader 选举失败，继续下一轮选举。

选举出 Leader 后，Leader 定期向所有 Follower 发送心跳信息以维持统治。若 Follower 超时未收到 Leader 的心跳则认为 Leader 下线，发起 Leader 选举。

Raft 保证选举出的 Leader 一定有最新的已提交的日志

日志同步

Leader选出后，就开始接收客户端的请求。Leader把请求作为日志条目（Log entries）加入到它的日志中，然后并行的向其他服务器发起 AppendEntries RPC 复制日志条目。当这条日志被复制到大多数服务器上，Leader将这条日志应用到它的状态机并向客户端返回执行结果。

Raft算法保证所有committed的日志都是持久化的。日志需要在大多数节点上持久化之后再响应给客户端，这意味着每个Follower节点收到Append Entry请求后需要持久化到日志之后再响应给Leader，且最终会被所有的状态机执行。

日志组织形式如上图，每个日志条目中包含可执行的指令、和日志被创建时的任期号，日志条目也包含了自己在日志中的位置，即index。一旦一个日志条目存在于大多数节点，那么该日志条目是committed的。

Raft 日志同步保证如下两点：

  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。

  • 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。

第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目，同时该条目在日志中的位置也从来不会改变。

第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时，Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志，它就会拒绝新的日志条目。

两条规则合并起来的含义：两个日志LogA、LogB，如果LogA[i].index=LogB[i].index且LogA[i].term=LogB[i].term，那么LogA[i]=LogB[i]，且对于任何k < i的日志条目，LogA[k]=LogB[k]都成立。

安全性（safety）

安全性是用于保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader commit Log时变得不可用了，稍后可能该Follower又会被选举为Leader，这时新Leader可能会用新的Log覆盖先前已committed的Log，这就是导致节点执行不同序列；Safety就是用于保证选举出来的Leader一定包含先前committed Log的机制。

  • 选举安全性（Election Safety）

  • 每个Term只能选举出一个Leader

  • Leader完整性（Leader Completeness）

完整性是指 Leader 日志的完整性，当 Log 在 Term1 被 Commit 后，那么以后Term2、Term3、Term4…等的 Leader 必须包含该 Log。Raft 在选举阶段就使用 Term 的判断用于保证完整性：当请求投票的该 Candidate 的 Term 较大或 Term 相同 Index 更大则投票，否则拒绝该请求。