raft论文学习-raft basics & leader election

raft算法是一个分布式一致性算法，用来替代Paxos算法，因为Paxos算法太晦涩难懂，基于Paxos成熟的工程实践非常少。在2013年，斯坦福大学的Diego Ongaro和John Ousterhout发表了论文In Search of an Understandable Consensus Algorithm，raft算法就此诞生。随后，在2014年Diego Ongaro的博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE中，对raft以及相关的一致性算法进行了系统的阐述。他们两人在设计raft算法时将可理解性放在了首位，在raft算法出现之后，出现多种语言的开源实现，像etcd中的raft是Go语言实现的。

In Search of an Understandable Consensus Algorithm论文中提到raft的核心有领导选举、日志复制、安全性和集群变更这几部分，每个部分内容不少，小编打算拆开来总结输出，本文是第一篇，主要讲论文中的raft basics和leader election两部分。

raft基础

• 一个raft集群包含多个节点，节点的数量为「奇数」个

答：不仅是raft，还有Zookeeper等分布式存储系统的节点个数都是奇数个，因为它们都是根据“少数服从多数”原则来达成一致。当集群中脑裂时，如果小集群的节点数相等，会造成没有大多数支持的局面，导致服务不可用。例如我们假定raft集群的节点数为偶数6，节点名称依次为node1,node2,node3,node4,node5和node6,当前集群中的leader节点为node1,当出现两个相同数量节点的网络分区，即每个分区有3个节点。如下图所示，分区1中由于日志复制节点无法满足绝大多数节点（4个及以上）导致无法commit，而分区2中无法选出新的leader节点，原因是候选者节点无法收到4个及以上节点的投票，直接导致服务不可用。如果集群中的节点是奇数个，不可能出现两分区中节点数相同的情况，只会存在要么node1所在分区是大多数节点区域，此时node1所在的分区可以继续正常运转，要么node1在少数节点区域，那么大多数节点分区会重新选出新的leader,也可以继续提供服务。

• raft节点是一个状态机，状态机一共有三种状态，每个节点处于leader/candidate/follower三种状态中的一个

答：raft集群中任意时刻最多只有一个leader节点，也就说集群中可以没有leader但不能有两个及以上的leader存在。raft协议通过约束条件保证集群中最多只有1个leader. 如果集群中没有leader，此时集群是无法提供服务的状态。在稳定（正常）状态下，集群中只有leader和follower角色，在非稳定状态即有选举竞选，此时集群中有candidate、follower和leader多种角色。

• 一次选举从开始到下一次新的选举开始对应一个任期，任期用连续的整数表示, 是单调递增的，raft把时间分割成了任意长度的任期。如果系统中没有选举，任期term是保持不变的。下图中有4个任期，蓝色表示处于选举过程中，是一个过渡状态，绿色表示系统中已有leader节点处于稳定状态，对应t3没有选举出leader，所以很快开始新的一轮选举term4.

答：任期的关键作用是解决leader的"脑裂“问题，假设集群中有5台机器，当前任期term为4，发生了网络分区，leader单独成为一个分区，其他4个node成为一个分区。由于其他4个follower收不到leader心跳消息，认为loader宕机了。4个follower会发起新一轮选举选出新leader, 此时term为5，开始向其他3个follower复制日志消息，很快网络分区恢复，之前的leader加入网络，此时网络出现了两个leader.但是当旧leader向其他follower节点发送数据时，follower发现日志里面的term=4比自己的term=5小，判断它为过期的leader,拒绝执行写入操作，同时告诉旧leader，你过期了。旧leader知道自己过期之后，自动回退成follower。从而保证了任意一个时刻只有一个leader是有效的。

5个节点构成的raft集群

leader发生网络分区

网络分区恢复

• raft算法规定了节点之间采用RPC进行通信，一致性算法只需要两种类型的RPC消息，为了在服务器之间传输快照增加了第三种类型的RPC。

答：RequestVote(请求投票) RPC: 发起请求投票RPC消息，从candidate节点广播发往其他节点。AppendEntries(追加日志)RPC,消息从leader节点发给follower节点， 用来复制日志和提供一种心跳机制。此外，为了在服务器之间传输快照增加了第三种类型的RPC，称它为快照RPC,用于传输快照数据。

leader选举

所有的节点在刚启动时都是follower角色，raft采用心跳机制触发选举。只要一个节点能够收到来自leader或candidate节点的RPC消息，就一直保持follower角色。leader会周期性的向所有follower节点发送心跳信息来捍卫自己的leader地位。心跳消息是一种不含有日志条目的AppendEntries RPC. 如果一个follower节点在一段选举超时的时间内没有收到任何消息，它就假定系统中没有leader, 然后开始进行选举尝试选出新的leader.

// 创建一个raft对象
func newRaft(c *Config) *raft {
 ...
 // 开始时都是follower角色
 r.becomeFollower(r.Term, None)
       ...
 return r
}

选举流程是这样的：

1. follower节点先增加自己当前的任期号并将状态切换到candidate状态
2. 给自己投一票
3. 并行地向集群中所有其他的节点发送投票请求(RequestVote RPC报文）
4. 保持candiate状态等待直接到遇到下面三种情况之一产生

4.1 情况1: 收到了节点回复中有过半的节点给”我“投票，这种情况”我“赢得了选举，将会切换到leader角色

4.2 情况2：收到了其他声称自己是leader的节点发送来的AppendEntries RPC，处理方法见下面的分析

4.3 情况3：一段时间内没有任何获胜者，处理方法见下面的分析

对于上面的情况4.1，对于一个candidate节点获得集群中过半的节点对自己的投票，它就赢得了选举并成为leader。例如对于有5个节点的集群，至少收到3个节点的投票才会成为leader. 在投票的时候有一些约束条件：

1. 同一任期同一个节点只会投票给一个candidate，如果收到有多个相同任期的candidate需要投票，只会投票给最早的那个，遵循先来先服务(first-come-first-served)的原则。
2. 成为leader需要获得过半节点的投票，确保了最多只有一个candidate能够赢得选举。
3. 当candidate赢得选举，成为leader之后，会向其他节点发送心跳信息来捍卫自己的地位并阻止新的选举。

对于上面的情况4.2，在等待投票期间，candidate可能会收到另一个声称自己是leader节点发送来的AppendEntries RPC消息，如果这个leader的任期号（在RPC消息中）不小于candidate当前的任期号，该candidate节点会承认leader的合法性自己退回到follower状态。如果RPC中的任期号比自己的小，该candidate会拒绝响应并继续保持candidate状态。

对于上面的情况4.3，即candidate没有赢得选举也没有输，这种情况发生在有多个follower节点同时成为candidate节点，导致选票被瓜分，以至于没有一个candidate赢得过半的投票。最后的结果是每个candidate都会超时，然后通过增加当前任期号来开始新一轮的选举。当然这种情况可能一直重复，导致无法选举出leader，所以raft采用随机选举超时时间的方法确保这种情况很少出现。就算发生也能够很快解决。为了阻止选票一开始被瓜分，选举超时时间从一个固定的范围【例如150-300毫秒】随机选择。这样可以把节点分散开以至于在大多数情况下只有一个节点会选举超时，然后该节点赢得选举并在其他节点之前发送心跳。这种机制也被用来解决选票被瓜分的情况，每个candidate在开始一次选举的时候会重置一个随机的选举超时时间，然后一直等到选举超时，这样减少了新的选举中再发送选票被瓜分的情况。

上面的内容可以结合https://raft.github.io/raftscope/index.html动画来学习，该动画模拟了5个节点的raft集群交互，可以对节点设置超时(timte out)、宕机(stop)等场景，然后观察对集群产生的效果。

In Search of an Understandable Consensus Algorithm[1]raft动画[2]

Reference

[1]

In Search of an Understandable Consensus Algorithm: https://raft.github.io/raft.pdf

[2]

raft动画: https://raft.github.io/raftscope/index.html