Raft项目总结

raft作为相当有效的分布式算法的一个实现，较paxos更容易理解，也更加简便。本文将阐述raft相关的知识点，从而对raft算法有更深刻的理解。

前置知识：

• go

选主策略

raft与paxos算法类似，都需要通过选主来保证一致性。但较paxos选主而言很明显，raft简化了选主过程。

计时器与状态改变
在raft中，每个节点都需要维护一个计时器。当计时器到时间后，便需要改变自身状态，开始一轮选举。状态有Follower，Candidate，Leader三种，所有节点最初默认为Follower。在计时结束后，进入选举，成为Candidate。若收到大多数票，选举成功，则成为Follower。若选举被中断，比如收到了任期更高的节点发来的信息，则转换为Follower。

对于计时器而言，每次重置都会增加一个随机延迟，这是为了减少选举中的冲突，如同一时期许多节点都开始选举。这样的办法提高了选举安全性的保证，即同一时间只会选出一个Leader。

投票
投票是原论文中相当详细的一部分，论文中列出的表很好地诠释了投票的进行过程，并且详细介绍了参数，这里给出一个投票RPC结构体的实现。

type RequestVoteArgs struct {
	Term         int
	CandidateID  int
	LastLogIndex int
	LastLogTerm  int
}


type RequestVoteReply struct {
	Term        int
	VoteGranted bool
}

与论文中保持一致，在征求投票参数中，Term表示自己的任期，ID用于标识自己，LastLogIndex与LastLogTerm涉及到后续的日志复制，是用来在任期相同时候来标识哪个结点更新的，从而更好选出Leader。
返回值中，Term用于Candidate更新自己任期，如遇到任期更高的可以直接变成Follower，VoteGranted则用于表示是否投票。

进入选举之后，首先增加自己的Term，然后进行征求投票，向其他节点发送RPC请求，得到响应并且处理。任期是得到投票的关键。只有在当前节点与节点网络中过半节点一样新，才会被选举为Leader。这为后续的日志一致性提供了保证。

获得半数以上票则当选，非常自然而然地保证了选举Leader的唯一性。当无法获得半数以上投票时候，要么在接受其他节点信息的时候转变身份，要么计时器到期，进入新的选举。

心跳机制
心跳机制是用于维护Leader地位的机制。当一个节点转变为Leader之后，会定期向其他节点发送空请求，使得其他节点能及时重置自己的计时器，避免进入选举状态。心跳机制也可以用于恢复之前失去连接的节点。如果心跳能够接通，则可以将之前的节点转换状态为Follower。

对于选举，更多的细节可以参考原论文。此处只是给出基本原理。

日志复制

作为分布式系统，日志的一致性是必须要保证的一点。Raft实现日志复制的方法也不难理解。

日志表示 下面是单个日志的具体项的Go实现。实际存储使用切片即可。

type Log struct {
	Command interface{}
	Term    int
}

可以看出，日志不光包含朴素的指令信息，还包含日期信息，这是raft系统最主要的辨别日志的方法。当一个日志的任期与日志所在的位置（即Index索引）完全相同时候，才能认为是相同的。这也是用于主从日志保证一致性的策略。

日志一致性
上面描述的日志的表示，这里我们将描述如何应用日志特性。

首先，日志只能从Leader接收，并且只能由Leader发向Follower。我们将日志区分为两种状态：未提交的，与已经 提交的。我们要确认的一致性，便是每个节点的committed的日志的一致性。

首先要确认的是，一条日志，只有存在于节点网络的过半节点中才会被提交，这意味着由网络隔离所导致的孤立节点网络中的日志可能会被多个机存储，但只要机器数量少于一半，则绝不会被提交。其次，就像之前所说，当Candidate与过半节点一样新的时候才会保证被选为Leader，这意味着Leader总是拥有最新最全的日志。由于消息传递的单向性，只能由Leader向Follower，因此Follower所能提交的日志总是Leader日志的一部分，这也保证了一致性。

在Leader内部会维护一个matchIndex与nextIndex，前者表示节点已经与本机匹配了的日志，后者表示下一个将要传递给该机器的日志索引。在选出新Leader时候，前者会被初始化为0,后者被初始化为本机日志长度减1。在本地日志与Leader发过来的日志对不上时候（这里的对不上，就是任期号与位置对不上），Leader便会改变该机器的nextIndex值，使其减少，直至对的上为止。当日志对上之后，Leader可以采用批量传递的方法，一次传递多个log，来提高效率，并且覆盖该节点的日志。传递日志数量取决与nextIndex的维护方式。每当日志复制完成，都会更新两个列表的值。最后，根据matchIndex值，可以得到一个已经确认复制完成的的列表。就我个人而言，我选择了根据该列表中位数的方法来确认该提交的日志。

同样，本文只是粗略概括，详细的一致性证明可以参考原论文的描述。

日志压缩

日志无法无限地增长，因而我们需要压缩技术。在raft中，我们使用快照的方法来进行压缩。

快照技术
快照技术理解并不困难，本质上便是合并已经提交的日志，对状态机进行合并，仅仅保留日志内最后一个任期与最后一个索引。

在实现上来说，通常每个服务器都是独立地建立快照，而不是由Leader统一创建。后者的开销与io效率更为低下。Leader偶尔也需要向落后的Follower发送快照来保证一致性，虽然开销看似很大，但在实际使用过程中，Follower的正常工作保持更新，会很少需要这些开销，因此这种开销是可接受的。

总结

raft作为面向理解的算法，解决了paxos晦涩难懂的缺点，理解上并不困难，在实际工程运用中也相当实用。我自己亲手实现了个raft，由于一些代码规范的原因没有过多展示，但确实感觉对于分布式的理解更为增进了一步。