共识机制之Raft-掘金网

在区块链的共识机制中，适用于联盟链（许可链）及私有链的主要有PBFT、Raft、Paxos，今次就理解一下Raft。

历史

Raft 的出现很大程度是基于 Paxos 算法难以理解和实现。

1990年，Leslie Lamport （还记得早前我在上一篇文章讲述共识机制PBFT 中提及过的作者Leslie Lamport 吗？没错，也是他）提出了一种基于消息传递的一致性算法－Paxos，但由于当时大家都难以理解这个算法的思想和在实际中难以实现，所以大家都没太大兴趣。

1998年，Leslie Lamport 将这个算法在ACM上正式发表，同样因为太难理解和实现，亦没有得到重视，随后，作者有见及此，换了一个角度重新发表一篇论文《Paxos Made Simple》，大家才开始逐渐理解Paxos 算法，但Paxos 仍属于一种”理论”，距离实现还需要基于Paxos 做一些扩展才能在实际中应用。

就正因为 Paxos 的难以理解和实现，导致了后来 Raft 的出现。

2013年，两位Stanford University的教授发表了一篇题为《In search of an Understandable Consensus Algorithm (Extended Version)》（寻找一种易于理解的一致性算法），这被认为是一种简易版的Paxos，性能和功能都与Paxos一样，同时易于理解和实现，这就是Raft出现的原因。

定义（概念）

Raft 是用于实现分散式系统的一种容易理解的共识机制，主要用来管理日志复制的一致性。

Raft 的核心思想很简单：

如果在分散式系统中多个数据库的初始状态一致，只要之后进行的操作顺序一致，就能保证之后的执行结果一致。

试想像一下，假设把三个数据库想像成是你面前的三本账本，只要每次在第一本账本上写上了一笔记录时，同时将这笔记录同样地写在另外两本账本上，那么这三本账本的数据始终是一样的。

Raft 取代复杂难懂的Paxos算法，并且证明可以提供与Paxos相同的容错性以及性能，并且更容易应用到实际系统中。

Raft 集群中，伺服器的三种角色

而在一个Raft集群（Raft cluster）中，至少包含5个伺服器，允许系统有2个故障伺服器，在系统初始时，每个伺服器都处于追随者的状态。而每个伺服器将会是这三种角色其中一个：

领袖（Leader）：正常状态下只有一个领袖，其他都是追随者，它会负责处理所有来自外部Client的请求及进行日志复制（日志复制是单向的，即领袖发送给追随者），先就是负责”出块”的节点。

候选人（Candidate）：由追随者向领袖转换的中间状态，等待被选举为领袖。

追随者（Follower）：它是被动的节点，对来自Client和候选人的请求做出响应。如果收到外部Client的请求，就会将请求会被转发给领袖。

而这三种角色在条件满足下可以互相转换，而在正常情况下只会有一个领袖，其他都是追随者。而领袖会负责所有外部的请求。

Raft 内三个重要概念

Replicated State Machine 状态复制机

Raft 一个节点上，

(1)一致性模组（Consensus Module，也就是分散式共识机制）接收到了来自Client的命令；

(2)把接收到的命令写入到日志中，该节点和其他节点通过一致性模块进行通信确保每个日志最终包含相同的命令序列；

(3)一旦这些日志的命令被正确复制，每个节点的状态机（State Machine）都会按照相同的序列去执行他们，从而最终得到一致的状态，再将达成共识的结果返回给Client。

处理过程大致如下：

2. Term 任期

在分散式系统中，由于每个节点之间可能会由于自身设置、地理环境的不同而导致该节点的时钟并不一致，各节点为了识别”过期”的信息，一致同步的时间戳就显得相当重要了。

Raft采用了 Term任期的概念，将时间逻辑分段，就像这样

解释一下，每个任期开始时，都是一次领袖选举（Leader Election），一个或多个候选人（Candidate）会尝试成为领袖（Leader）。如果一个人赢得选举，就会在该任期（Term）内剩余的时间担任领袖，负责”出块”。在某些情况下，选票可能会被评分，有可能没有选出领袖（例如t3），那么，将会开始另一任期，并且立即开始下一次选举。

Raft 算法保证在给定的一个任期最少要有一个领袖。那么，是如何保证的呢？

3. 心跳（Heartbeat）和选举超时机制（Election Timeout）

Raft算法中，设有心跳（Heartbeat）和选举超时（Election Timeout ）互相配合控制领袖选举，以保证在给定的一个任期内最少会有一个领袖。

心跳（Heartbeat）一旦选出了领袖节点之后，这个节点会向其他所有节点发送空的AppendEntries RPC（即心跳HeartBeat），而其他节点收到后，角色就会由变为追随者，同时重置选举定时器，而领袖节点在空闲的时间内会重复发送以防止选举超时。

选举超时（Election Timeout）如果追随者的节点在150ms~300ms（在这范围内随机设定）内没有收到领袖的心跳RPC，就会认为领袖节点失效，随即展开新一轮选举，选出新的领袖。

运作流程

为了更好地了解Raft 这个共识机制，个人强烈建议先把这段动画解说完整看一下，简单清晰，容易理解。

http://thesecretlivesofdata.com/raft/

Raft 将Paxos 概念简化，并将复杂概念分解成三个子过程，令人更容易了解：

1. 领袖选举（Leader Election）

争议不息QuadrigaCX 交易所创办人或被开棺验尸

去年12月，加拿大最大的比特币交易所QuadrigaCX 创办人Gerald Cotten 猝逝，随即引起一番争议；事情的最新进展是：Gerald Cotten 或被验尸，以确认其身份。 Gerald Cotten于去年逝世后，欠下客户

开始时，所有节点都是以追随者的角色启动，同时启动选举计时器（150ms~300ms 时间随机，降低冲突机率）；

如果当一个节点（左下）发现选举定时器超时，一直都没有收到来自领袖节点的心跳RPC，则该节点就会成为候选人，并且一直处于该状态，直至下面三种情况发生：

该候选人节点嬴得选举；
其他节点嬴得选举；
在一段时间后没有任何一个节点嬴得选举（随即进入下一轮的选举，并随机设置选举定时器时间）；

同时，这个节点成为候选人后，就会向其他节点发送投票请求（Request Vote），如果得过半数以上节点的同意，就会成为领袖Leader 节点；但如果仍未选出领袖，则进入下一个任期，重新选举。

完成选举后，这个领袖节点就会定时向其他节点发送心跳RPC，即向他们表示”我仍然正常运行”，同时重置这些节点的选举定时器；

2.日志复制（Log Replication）

外部的Client 向 Leader 提交指令（SET 5），Leader 收到命令后，将命令追加到本地日志中。此时，这个命令处于”uncommitted” 状态，复制状态机不会执行该命令。

然后，Leader将命令（SET 5）并发复制给其他节点，并等待其他其他节点将命令写入到日志中，如果此时有些节点失败或者比较慢，Leader 节点会一直重试，知道所有节点都保存了命令到日志中。Leader节点就提交命令（即被状态机执行命令，SET 5），并将结果返回给 Client 。

Leader 节点在提交命令后，下一次的心跳RPC 中就带有通知其他节点提交命令的消息，其他节点收到Leader 的消息后，就将命令应用到状态机中（State Machine），最终每个节点的日志都保持了一致性。

3.安全性（Safety）

领袖选举及日志复制这两个部份仍不能保证每一个状态机能按照相同的顺序执行同样的指令。假设当领袖提交了若干日志条目的同时一个追随者可能宕机了（失效），之后它又被选为了领袖，接着用新的日志条目覆盖掉了旧的日志，最后，不同的状态机可能执行不同的命令序列，导致各节点间的日志不一致。

而为了解决这个问题，Raft算法通过在领袖选举阶段增加一个限制来完善了Raft算法。这个限制能保证，对于固定任期，任何领袖都拥有之前任期提交的全部日志命令。Raft算法通过投票的方式来阻止那些没有包含全部日志命令的节点赢得选举。

所以，可理解为

日志的流向只有由领袖到追随者，并且领袖不能覆盖日志；
日志不是最新的，没有全部日志的节点不能成为候选人；

而一个候选人节点要嬴得选举，成为领袖，就必须跟系统中大部份的节点进行通信，意味着候选人的日志要与大多数节点上的日志相同。而Raft 亦提供了RequestVote RPC 实现这个限制。

RequestVote RPC：候选人在选举期间发起，RPC中包括候选人的日志信息，如果它自己的日志比候选人的日志要新，那么它会拒绝候选人的投票请求；

说起RPC 还有两种：

AppendEntries RPC：由领袖节点发起的一种心跳RPC，日志复制也在该命令中完成。

InstallSnapshot RPC：领袖节点用来发送快照给太落后的追随者。

然而，怎样判断两个节点中的日志内容哪个比较新呢？Raft 算法通过比较日志中最后一个命令的索引（Index）和任期编号（Term）判断哪一个节点的日志内容比较新。

如果两个日志的任期编号不同，任期编号大的日志内容较新

如果两个日志的任期编号相同，内容长的日志则被认为较新

如果一个任期内，假设领袖节点突然无法连接网络，没有及时发送心跳RPC给其他追随者，这些追随者将会重新选举一个领袖，继续领袖的责任，如果后来原来的领袖节点能够成功连接网络，它的角色将会变为追随者，而不是领袖，而且在它在断开连接的这段时间，它任何的更新都不能确认，都会全部回滚，然后，作为一个追随者接收新的领袖节点的更新，不断重复。

目前市场上的应用

热门的Hyperledger Fabric 超级账本、国内开源的FISCO BCOS 中等的区块链系统中，Raft, PBFT等一些共识机制被设计成可插拔的模组。

而ETCD 则是将Raft 算法实作成一个Library，可以让其他应用快速地应用Raft 算法，它的目标是构建一个高可用的分散式键值（Key-Value）数据库。

优缺点

优点

1.易于理解，容易实现

Paxos 算法难以理解，Raft 将整个算法清楚分成两部份，并利用日志的连续性做了简化，从本质上来说，流程及描述清晰，比起Paxos 来说更容易实现和理解。

2. 简化Paxos，效率相同

Raft 就相当于Multi-Paxos，而且和Paxos 算法一样高效，Raft 将Leader 选举、日志复制、安全性等关键元素分离，并采用更强的一致性以减少必须考虑状态的数量。

缺点

1. Raft 只适用联盟链（许可链）或私有链

2. 无法进行拜占庭容错的缺陷

总结

Raft 共识机制相对于Paxos 来说，却是在概念上简化了不少，将集群中Leader 角色的地位强化了，而且流程和描述清晰，令大家更容易理解和实现，而且在安全性及效率可以与Paxos 相同，目前也作为市场上大部份联盟链（许可链）平台可选的共识机制之一，但缺陷却是去中心化较弱，只适用于联盟链（许可链）或私有链，不过，共识机制就是这样，没有一个能适用于所有应用场景的共识机制，需要在去中心化、安全性、出块效率之间作出取舍，没有最好，只有最适用。

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。