分布式一致性协议Raft的简单理解
2016-01-11
基本概念 #
Raft的三个模块 #
分布式一致性协议允许一组服务器节点像一个整体一样工作，允许其中一些节点出现故障也能继续工作下去。正式因为如此，一致性算法在构建大规模分布式软件系统扮演着十分重要角色。Paxos一直是分布式领域内一致性协议的代名词，但Paxos十分难以理解，绝大数实现基于Paxos进行修改才能应用到实际系统中，因此Paxos的具体实现具有不统一性。
在实现一致性功能的前提下，Raft的目标主要有两个：Raft的可理解性；使用Raft更容易构建实际的系统，构建的实际系统更具有确定性。 针对于这两个目标，Raft将一致性协议分解为3个模块：
- 领导者选举
- 日志复制
- 安全性
Raft集群节点状态 #
一个Raft集群包含若干个服务器节点，假设服务器节点数为n(通常为大于等于3的奇数)，整个系统容忍(n-1)/2个节点失效。 在任何时刻，集群中每个节点都处于如下三个状态之一：
- Leader(领导者)
- Follwer(追随者)
- Candidate(候选者)
下图是Raft集群节点三种状态的转换：
Raft采用的是Master-Slave模式，通过领导者选举步骤选出一个Leader，后续的日志复制和安全性都是由Leader来完成，简化了一致性维护问题。如果Leader失效，会通过领导者选举步骤选出新的Leader继续后续的过程。
正常情况下集群中只有一个Leader负责响应来自所有客户端的请求，其他节点都是Follower，处于Follower状态的节点都是被动接收RPC消息，从不会主动发送RPC消息。Candidate状态是Follower节点准备发起新的领导者选举前需要转化到的状态，是从Follower到Leader转化的中间状态。
任期(Term) #
Raft将整个Raft集群执行时间划分为若干个不同时间间隔的时间片段，每个时间片段被称为一个任期(Term)，每个Term以递增数字来标识。
每个任期由两个期间组成：选举期间(election)和常规操作期间(normal operation)。有的任期可能在选举期间内没有选出Leader而没有常规操作期间。 因此可以看出，每个任期都是由选举期间开始，在这个期间内若干个处于Candidate状态的节点试图竞争称为新的Leader，如果某个节点赢得选举，则将在这个任期内作为Leader，进入常规操作期。某些情况下，因为选票的分流，在选举期间内没有成功选出Leader，则会进入下一个任期。此外，Raft还需保证一个任期内最多有一个节点被选举为Leader。
Raft集群节点RPC通信 #
在Raft中，各服务器节点通过远程过程调用RPC进行通信，包含以下两种RPC：
- RequestVote(请求投票)：由Candidate节点在选举期间发起
- AppendEntries(附加条目)：由Leader发起，用来向Follower复制日志和提供心跳机制。
领导者选举 #
领导者选举的触发 #
Raft使用心跳机制来触发领导者选举过程。
当整个系统启动时，所有服务器节点都处于Follower状态，只要节点保持收到来自Leader或Candidate的RPC，将一直维持这个状态。
Leader周期性的向所有Followers发送心跳RPC(AppendEntries不包含log entry)来宣称其处于领导者地位。 如果某个Follower经过一定时间间隔(这个时间间隔被称为选举超时时间)没有收到任何心跳消息，则认为集群中的Leader已经不存在，于是将触发领导者选举过程。
在开始选举前，Follower将增加其Term编号并转化为Candidate状态，然后它会向集群中其他所有节点发送RequestVote RPC来给他自己投票。
选举过程理解 #
Candidate节点发出RequestVote RPC消息，之后一直处于Candidate状态，除非以下某一种情况发生：
- 它自己赢得了本次选举：这种情况表示该Candidate收到了大多数与其处于相同任期编号的选票，赢得这次选举称为Leader，之后需要向其他接地那发送心跳宣告并维护其Leader的地位。注意每个服务器节点做多会对一个任期编号投出一张票，按照先来先服务原则先到先得。
- 其他服务器节点宣称并确认是新的Leader：Candidate在等待投票的过程中可能会接收到新的RPC消息，如果这个RPC消息是另外一个服务器节点宣称其是新的Leader发出的，并且这个RPC里面的任期编号大于等于该Candidate自身的任期编号，则它会承认这个新的Leader有效，自己会转换为Follwer状态；否则会拒绝承认这个新的Leader，它自己会继续维持Candidate状态。
- 经过一段时间间隔，仍然没有新的Leader产生：即Candidate没有赢得选举也没有其他服务器节点赢得选举，出现这种情况有可能是因为多个Follower转换为Candidate状态，导致选票分流而没有得到多数选票。发生这种情况时，Candidate会超时并增加自身的任期编号后进入新一轮的选举过程。为了尽量减少这种情况的发生，Raft为每个节点采取随机超时时间，这样出现选票分流的概率会大大减小。
日志复制 #
当选出Leader之后，所有客户端请求都由Leader来负责响应。Leader收到客户端的请求的操作命令后，将这条指令作为新的日志条目(Log Entry)附加到日志的尾部，然后并行向集群中所有其他服务器节点发送AppendEntries RPC，让其他服务器节点复制这个日志条目。当其他服务器安全复制了这个日志条目后，Leader会将这个日志条目应用到其内部状态机，然后把请求执行结果返回给客户端。
日志的结构如下图所示：
每个日志条目(Log Entry)包含一个全局的日志索引(log index)来表示日志条目在日志中的位置(顺序)，另外包含请求操作命令本身，还包含Leader接收到操作命令时的任期编号。
Leader会决定哪些日志条目可以安全的应用到状态机上，这些条目被称作已经提交的条目(commit entries)，Raft保证这些已经提交的日志条目的持久化以及让所有服务器节点都按照相同的顺序执行这些操作命令。一般情况下，当大多数服务器节点都正确的在日志里存储了这个日志条目，则可以认为这个日志条目是可提交的。 上图中，日志索引为7及其之前的日志项目都是可提交的，因为5个服务器节点之中的3个已经正确的复制了这些日志条目。
安全性 #
通过前面的领导者选举和日志复制，Raft在大多数情况下都可以正常运行，但是在某些情况下还是无法做到完全的安全性保证，即无法保证每个服务器的状态机都能够按照相同顺序执行相同的操作命令。
为了达到真正的安全性，Raft增加了如下的约束条件：
- 要求只有其Log包含了所有已经提交的日志条目的服务器节点才有权没选举为新的Leader
- 对于新的Leader，只有他已经提交过当前任期的日志条目才被认为是真正的提交