简介

在分布式系统中，一个经典的问题是如何高效、可靠的保证运行集群中各个节点数据保持一致。Paxos算法是解决该问题中最广为人知的算法，它由Lamport提出，但由于其描述的较为晦涩，同时存在多处省略，在实现过程中往往有很多细节难于处理，在工程中存在许多类似而又不统一的实现。ZooKeeper使用的Zab算法实际上和Paxos存在很多地方的不同。
Raft算法是由Stanford教授提出为了帮助学生理解的同步算法，它和Paxos算法类似，能保证集群数据的强一致性，但它的概念相比Paxos更少，也更便于理解，论文在这里，结合youtube上的教学视频一同观看效果更佳。

现状

当前已经存在许多知名开源系统基于Raft，如Etcd, Consul等。同时还有些系统如SeaWeedFS, InfluxDB采用内嵌的形式实现了Raft协议。
我也简单的基于Goraft，基于leveldb实现了简单示例性质的强一致存储系统。

算法目标

在讲述Raft算法之前，我们首先讨论一致性算法的要求，它包括以下四个方面：

1. 算法需要能够承受各种类型的错误。
2. 一半以上的节点能运行集群能够正常运作
3. 每个操作只要一半以上的节点成功执行就算成功
4. 不能依赖于任何外部时序

实现

Raft协议基于复制状态机（replicated state machine），即一组server从相同的初始状态起，按相同的顺序执行相同的命令，最终会达到一直的状态，如下图所示，一组server记录相同的操作日志，并以相同的顺序应用到状态机。

它将一致性问题进行分解为“集群选举”和“复制日志”两个部分。 集群选举过程是为了从集群中会选出唯一的leader负责服务客户端的请求。而复制日志过程，是为了保证所有server的状态和最终达到跟leader一致。

集群选举

集群节点类型

集群中节点有三种类型，分别为: Leader, Follower, Candidate。 在初始时，大家都为Follower。通过选举产生集群的Leader。

• 在任何时刻，集群只有一个Leader。Leader负责接收所有用户请求，并通过”复制日志”方式同步给Follower。

• Follower以被动的方式运行，只负责响应请求，而不主动发出请求。

• Candidate状态是集群选举开始后，希望变成Leader节点的临时状态。

集群选举过程

Leader定时向Follower发送心跳信息，当某个Follower长期未接受到Leader的心跳信息，Follower将发动新一轮的Leader选举，这时它会做两件事情。

1. Follower变换其状态为Candidate
2. 将当前的Term+1，发起投票请求。

对于每一轮选举(对应一个Term)，每个节点只能投一次票。 节点收到投票请求后，将比较请求中的Term与自身的Term。此时有三种情况：

1. 请求的Term与当前Term相同
   节点此轮还未投过票，此时将返回同意请求。
   节点此轮已经投过票，不做回应
2. 请求的Term大于当前Term
   表明节点已经落后，更新节点的Term，返回voteGranted = True
3. 请求的Term小于当前Term
   不做回应

Candidate对于投票的反馈

1. 当前节点被选为新的Leader
   当节点收到超过一半节点的投票，确定其是新的Leader。此时将状态更新为Leader，发送新一轮心跳请求，告知其他节点Leader已经产生。
2. 收到来自Leader的数据写入请求，且term >= 当前节点的term
   更新Term为请求反馈的Term，变更状态为Follower
3. 投票超时仍没有收到超过一半的确认
   递增Term，等待一段时间，开始新一轮的选举

数据同步

Leader收到用户请求后，会将用户请求写入操作日志中的同时，将数据复制给其他节点，当收到满足条件的反馈后，标记写入成功，返回结果给用户。

对于每个用户插入请求，系统将以记录的形式进行存储，其形式如下图。

每个记录分为三个部分：

Term-RecordId-UserData

Term是系统的逻辑时间，每一次集群选举都将产生新的逻辑时间。每个节点都将维护Term值，系统可使用它隔离过期无效的数据和Leader，详细可参考后文集群选举过程。
RecordId是自增长的。每插入一条记录，id+1。当产生新的逻辑时间后，RecordId归0

上图为，集群中数据的可能存储状态。在执行数据插入时，流程如下：

1. 用户发送数据给Leader
2. Leader写入记录到本地
3. Leader向Follower发出数据插入请求
4. 当超过一半以上的Follower返回成功，Leader标示该记录Commited，返回成功给用户
5. Leader告知所有Follower记录Commmited， Follower收到后，标示记录Commited。
   如果4,5过程中当Follower未能及时响应, Leader将不断重试

记录Commited

当记录一旦被标示为Commited，系统将保证如下两个事实：

1. 对于今后所有时刻，所有节点在该位置将保存同样的记录。
2. 在此记录之前的所有记录已经同步完成

有了以上两个性质，一旦数据Commited之后，系统将保证至少有一半以上的节点和Leader有着同样的Commited数据。

Follower接收记录请求

为了保证Commited性质，Follower接收到插入记录请求时，将检查该条记录之前的所有记录是否已经Commited，如果不是，将拒绝该请求，并返回待同步数据的起始位置。

详细设计

插入请求接口

AppendEntries(term, leaderID, prevLogIndex, prevLogTerm, entries[], commitedIndex) -> (term, sucess)

prevLogIndex和prevLogTerm用于告知Follower其最后提交的记录
当prevLogIndex和term小于Follower时，表明此Leader已经过期，存在新的Leader，Follower将拒绝该请求，Old Leader收到该请求后变换其状态为Follower。
CommitedIndex用于告知Follower此次请求记录的提交Index。

投票请求接口

RequestVote(candidateId, term, lastLogIndex, lastLogTerm) -> (term, voteGranted)

节点将会检查当前Term，与log的信息。
log信息是为了保证拥有最新记录的节点才能选成Leader。
当节点的log记录大于投票请求提供的，节点将无视投票请求

节点保存的状态

currentTerm 标记当前所处阶段
voteFor 当前阶段投票的LeaderId，如果未投则为空
log[] 日志记录信息

客户端

超时重试机制

客户端发送请求给Leader，如果请求超过指定时间没有返回，发送请求给集群中任意一个其它节点，并更新Leader。

避免重复提交

当Leader已经提交了记录后，在返回给用户结果之前Crash了，此时用户将认为记录插入失败，会进行重试。这将会导致记录重复提交。
为了避免这个问题，

客户在提交记录之前将首先生成uuid，连同数据传给Leader。
Leader在插入记录之前，将首先检查uuid是否已经出现过。如果是，则直接返回成功

配置更改

配置的更改(节点的增加和删除)，以及配置不可能同时应用于所有节点，将导致系统中不同节点对于一半以上的理解不一致，从而形成系统的错误。

上图展示的是原集群有三个节点，新加入两个节点后导致的集群分裂问题。对于1,2节点它们还是老的配置，这时它们两人认为集群是正常运作的，并持续向外提供服务。而对于345，它们形成了新的集群。从而导致有两个集群都向外提供服务。

两阶段配置更改

为了解决集群分裂问题，Raft将配置的更改，同样事做用户数据的插入，Leader将配置文件同步到其它节点。系统采用两阶段提交的办法，先让节点从old状态变成old+new状态，再从old+new状态变成new状态。

1. 提交新配置到集群Leader，Leader复制数据到其它节点，自身也变为old+new状态。新节点直接变成new状态。
2. 老节点收到新的配置后，将状态变更成old+new的中间状态。
3. 当Leader收到超过一半以上old+new变更成功通知以及一半以上新节点new状态，操作成功。

如果Leader不发生宕机此方法显然是正确的，我们来看如果在变更时Leader出现宕机时系统的行为。系统有如下的要求

1. 成为old+new的节点需要征得至少一半以上old节点和一半以上old+new节点，配置更改才算成功。
2. old节点只需征得一半以上old节点配置即可更改成功。

在此条件下，Leader宕机时，虽然旧配置和新配置节点都可能成为新的Leader，但又确保了系统不会发生分裂。

---

配置更改的问题

1. 新的集群节点可能不包含数据
   新的节点加入集群时，需要首先追上Leader的数据。这里可以标记新节点为一个新的状态，它同步数据，但不参与投票。
   疑问：论文中提到，新节点追上Leader数据才能开始配置更改过程

   但是如何在不停机的情况下追上Leader这个问题却未提及。