Raft共识算法详解

Raft共识算法 一.背景

拜占庭将军问题是分布式领域最复杂、最严格的容错模型。但在日常工作中使用的分布式系统面对的问题不会那么复杂，更多的是计算机故障挂掉了，或者网络通信问题而没法传递信息，这种情况不考虑计算机之间互相发送恶意信息，极大简化了系统对容错的要求，最主要的是达到一致性。

所以将拜占庭将军问题根据常见的工作上的问题进行简化：假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？

对于这个简化后的问题，有许多解决方案，第一个被证明的共识算法是 Paxos，由拜占庭将军问题的作者 Leslie Lamport 在1990年提出，但因为 Paxos 难懂，难实现，所以斯坦福大学的教授Diego Ongaro 和 John Ousterhout在2014年发表了论文《In Search of an Understandable Consensus Algorithm》，其中提到了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行效率，但是更容易理解，也更容易被用在系统开发上。

二.概述

Raft实现一致性的机制是这样的：首先选择一个leader全权负责管理日志复制，leader从客户端接收log entries（日志条目），将它们复制给集群中的其它机器，然后负责告诉其它机器什么时候将日志应用于它们的状态机。举个例子，leader可以在无需询问其它server的情况下决定把新entries放在哪个位置，数据永远是从leader流向其它机器（leader的强一致性）。一个leader可以fail或者与其他机器失去连接，这种情形下会有新的leader被选举出来。

在任何时刻，每个server节点有三种状态：leader，candidate，follower。

leader：作为客户端的接收者，接收客户端发送的日志复制请求，并将日志信息复制到 follower 节点中，维持网络各个节点的账本状态。

candidate：在leader 选举阶段存在的状态，通过任期号term和票数进行领导人身份竞争，获胜者将成为下一任期的领导人。

follower：作为leader 节点发送日志复制请求的接收者，与leader节点通信，接收账本信息，并确认账本信息的有效性，完成日志信息的提交和存储。

正常运行时，只有一个leader，其余全是follower。follower是被动的：它们不主动提出请求，只是响应leader和candidate的请求。leader负责处理所有客户端请求（如果客户端先连接某个follower，该follower要负责把它重定向到leader）。candidate状态用于选举领导节点。下图展示了这些状态以及它们之间的转化:

Raft将时间分解成任意长度的terms，如下图所示：

terms有连续单调递增的编号，每个term开始于选举，这一阶段每个candidate都试图成为leader。如果一个candidate选举成功，它就在该term剩余周期内履行leader职责。在某种情形下，可能出现选票分散，没有选出leader的情况，这时新的term立即开始。Raft确保在任何term都只可能存在一个leader。term在Raft用作逻辑时钟，servers可以利用term判断一些过时的信息：比如过时的leader。每台server都存储当前term号，它随时间单调递增。term号可以在任何server通信时改变：如果某个server节点的当前term号小于其它servers，那么这台server必须更新它的term号，保持一致；如果一个candidate或者leader发现自己的term过期，则降级成follower；如果某个server节点收到一个过时的请求（拥有过时的term号），它会拒绝该请求。

Raft servers使用RPC交互，基本的一致性算法只需要两种RPC。RequestVote RPCs由candidate在选举阶段发起。AppendEntries RPCs在leader复制数据时发起，leader在和follower做心跳时也用该RPC。servers发起一个RPC，如果没得到响应，则需要不断重试。另外，发起RPC是并行的。

三.具体共识流程

raft算法大致可以划分为两个阶段，即Leader Selection和Log Relocation，同时使用强一致性来减少需要考虑的状态。

3.1 Leader Selection

Raft使用heartbeat（心跳机制）来触发选举。当server节点启动时，初始状态都是follower。每一个server都有一个定时器，超时时间为election timeout（时间长度一般为150ms~300ms），如果某server没有超时的情况下收到来自leader或者candidate的任何RPC，则定时器重启，如果超时，它就开始一次选举。leader给followers发RPC要么复制日志，要么就是用来告诉followers自己是leader，不用选举的心跳（告诉followers对状态机应用日志的消息夹杂在心跳中）。如果某个candidate获得了超过半数节点的选票（自己投了自己），它就赢得了选举成为新leader。

上述的具体过程如下：

➢ 初始状态下集群中的所有节点都处于 follower 状态。