Raft协议共识算法全解读

Raft协议算法曾经几乎垄断了一致性算法领域。在Raft协议诞生之前，Paxos是一致性协议的代名词。但是对于大多数人来说，Paxos算法太难以理解了，而且难以实现。因此斯坦福大学的两位教授Diego Ongaro和John Ousterhout决定设计一种更容易理解的一致性算法，最终在论文"In search of an Understandable Consensus Algorithm"中提出了Raft算法。

Raft最初是一个用于管理复制日志的共识算法，它是一个为真实世界应用建立的协议，主要注重协议的落地性和可理解性。Raft是在非拜占庭故障下达成共识的强一致协议。

在区块链系统中，使用Raft实现记账共识的过程可以描述如下：首先选举一个leader，接着赋予leader完全的权力管理记账。leader从客户端接收记账请求，完成记账操作，生成区块，并复制到其他记账节点。有了leader简化了记账操作的管理。例如，leader能够决定是否接受新的交易记录项而无需考虑其他的记账节点，leader可能失效或与其他节点失去联系，这时，系统就会选出新的leader。

在Raft中，每个结点会处于下面三种状态中的一种：

1.follower：所有结点都以follower的状态开始。如果没收到leader消息则会变成candidate状态

2.candidate：会向其他结点“拉选票”，如果得到大部分的票则成为leader。这个过程就叫做Leader选举(Leader Election)

3.leader：所有对系统的修改都会先经过leader。每个修改都会写一条日志(log entry)。leader收到修改请求后的过程如下，这个过程叫做日志复制(Log Replication)：

1）复制日志到所有follower结点(replicate entry)

2）大部分结点响应时才提交日志

3）通知所有follower结点日志已提交

4）所有follower也提交日志

现在整个系统处于一致的状态

Raft阶段主要分为两个，首先是leader选举过程，然后在选举出来的leader基础上进行正常操作，比如日志复制、记账等。

1.Leader Election

当follower在选举超时时间内未收到leader的心跳消息，则转换为candidate状态。为了避免选举冲突，这个超时时间是一个150~300ms之间的随机数。

一般而言，在Raft系统中：

1）任何一个服务器都可以成为一个候选者candidate，它向其他服务器follower发出要求选举自己的请求。

2）其他服务器同意了，发出OK。注意，如果在这个过程中，有一个follower宕机，没有收到请求选举的要求，此时候选者可以自己选自己，只要达到N/2+1的大多数票，候选人还是可以成为leader的。

3）这样这个候选者就成为了leader领导人，它可以向选民也就是follower发出指令，比如进行记账。

4）以后通过心跳进行记账的通知。

5）一旦这个leader崩溃了，那么follower中有一个成为候选者，并发出邀票选举。

6）follower同意后，其成为leader，继续承担记账等指导工作。

2.Log Replication

Raft的记账过程按以下步骤完成：

1）假设leader领导人已经选出，这时客户端发出增加一个日志的要求；

2）leader要求follower遵从他的指令，都将这个新的日志内容追加到他们各自日志中；

3）大多数follower服务器将交易记录写入账本后，确认追加成功，发出确认成功信息；

4）在下一个心跳中，leader会通知所有follower更新确认的项目。

对于每个新的交易记录，重复上述过程。

在这一过程中，若发生网络通信故障，使得leader不能访问大多数follower了，那么leader只能正常更新它能访问的那些follower服务器。而大多数的服务器follower因为没有了leader，他们将重新选举一个候选者作为leader，然后这个leader作为代表与外界打交道，如果外界要求其添加新的交易记录，这个新的leader就按上述步骤通知大多数follower。当网络通信恢复，原先的leader就变成follower，在失联阶段，这个老leader的任何更新都不能算确认，必须全部回滚，接收新的leader的新的更新。

Raft算法和Pbft算法是私链和联盟链中经典的共识算法，区块链从业者一定要学习和理解。另外，如UENC研发的的DPOW算法这类大幅度提升链上交易效率的共识算法也值得大家去学习。

—-

编译者/作者：通证时代Time

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。