前言

上一次分享了CAP 定理，我们了解到在有网路分区（Partition）的情况下，我们只能在一致性（Consistency）与可用性（Availability）之间二择一，更进一步地说，我们其实是在光谱的两端— 强一致性（Strong Consistency）与最终一致性（Eventually Consistency）之间做选择。

在最终一致性上，我们通常会听到很多方法论，像是上篇提到的读时修复（Read Repair）、写时修复（Write Repair）、反熵（Anti-Entropy）等等；不过在强一致性上，我们比较常听到某论文发表的强一致性演算法，原因是强一致性要有合理的数学佐证，大家才会相信，除此之外，还需要经过大规模的落地验证，大家才会对其效能认可，因此被广泛运用在商业上的强一致性算法比较少，经典常见的像是  Paxos、ZooKeeper的  ZAB、Raft  等等。

在开始之前，如果还没读过上一篇《分散式架构的限制理论— CAP定理》的，建议可以先阅读理解分散式系统的限制。由于强一致性在某些场景是必须要被保证的，像是金融支付、票务系统等等，所以这篇会介绍强一致性系列的算法。

Paxos 共识演算法家族

若要说到共识演算法，那一定会提及Paxos，原因是Paxos刚被提出时缺少工程面的实作细节，比较像个理论框架，导致后面有实作细节的算法看起来都像Paxos，甚至有人会说「这世界只有一种共识演算法，那就是Paxos」。这里暂时不会展开Paxos的细节，因为Paxos算法是出名的难，导致后来作者Lamport甚至还自己出了《Paxos Made Simple》来解释自己的算法，不过这里提及Paxos是因为Paxos的重要性在于它有严谨的数学证明，如果真的想理解Paxos，建议可以先理解Paxos家族的其他演算法，像是本篇要提到的Raft，最后如果对于Paxos在工程端的实作有兴趣的，可以参考Google团队对Paxos的实战总结《Paxos Made Live — An Engineering Perspective》。

共识演算法分类— BFT vs. CFT

从解决的问题类型来看，共识演算法分成两种，分别是拜占庭容错演算法（Byzantine Fault Tolerance, BFT）与故障容错演算法（Crash Fault Tolerance, CFT）。拜占庭容错演算法主要在解决如果有节点作恶的情况下，如何同步集群的状态，常见的拜占庭容错演算法有  PBFT；故障容错演算法主要都在处理节点故障或是遇到网路问题时，如何让整个集群的状态维持一致，常见的故障容错演算法有  ZAB、Raft  等等。

虽然拜占庭问题（Byzantine Generals’ Problem）跟拜占庭容错演算法PBFT被提出的时间都相当早，但可以说是到了区块链出现，才找到大规模的应用场景，而大部分企业内部应用的，还是属于故障容错演算法，像是Google透过Paxos达成共识的分布式锁系统—  Chubby，而今天我们要介绍的就是常见于企业内部的共识机制— Raft。

Raft 共识机制

Raft是Diego Ongaro在Stanford念博班时的博士论文，在2013年与他的指导教授John Ousterhout一同撰写《In Search of an Understandable Consensus Algorithm》，并在2014年的  USENIX Annual Technical Conference  上获得Best Paper Award 。

从论文名称就可以看出作者们有多想表达其他共识机制不好理解，一个好理解的算法最大的优点就是，在工程面上不容易出错，这也导致了2013年后的新系统如果需要强一致性，通常会优先考虑Raft，像是2013年的  etcd、InfluxDB、2014年的  Consul、IPFS  以及2015年的  CockroachDB  等等；在联盟链链里，通常也会把Raft当共识演算法的选择之一，像是  Corda、Quorum  以及1.4.1版后的  Fabric，虽然Raft不是拜占庭容错演算法，但在大家可以互相信任彼此的情况下，联盟链还是可以以Raft为共识机制。好理解的另一个优势就是实作的人相当多，所以可以找到相当多的参考，甚至是作者参与实作的版本，大家上GitHub搜寻  Paxos  及  Raft，就会发现两者光是在Repostiory数量就有近3倍的差距。

接下来我会介绍Raft演算法的细节，会从节点记录的内容—状态（State）、任期（Term）、日志（Log）及资料状态机（State Machine）开始，接着说明两大模组—领导者选举（Leader Election）及日志复制（Log Replication）。这篇只探讨理论，之后有机会的话，我会再写一篇探讨  Hashicorp Raft  原始码的文章。

节点状态（State）

在Raft里面，节点有三种状态，分别是—领导者（Leader）、候选人（Candidate）及跟随者（Follower）。Raft属于强领导者模型（Strong Leader），所以一个Raft集群中只能存在一个领导者，其他节点会以领导者为尊，领导者说什么就是什么，这也导致了Raft只能做到故障容错（CFT），而无法处理拜占庭容错（BFT）。

任期（Term）

任期听起来是只有领导者才需要的东西，没错，但是Raft 为了做到故障容错，在集群里面的任一个节点都有可能在领导者故障后成为候选人，并参与领导者选举，所以每个节点都要知道现在的任期。

任期是一个严格递增的数字，Raft是强领导者模型，所以一个任期内至多只会有一个领导者，只有有领导者在的时间，才能对外提供服务。以下图为例，每个任期一开始都是领导者选举（蓝色区段），后面是集群可以对外服务的时间（绿色区段），每一个任期只有在领导者故障后，集群才会发起下一次的选举，所以每次任期的时间长度不固定，也有可能发生领导者选举失败的任期（如t3），代表该任期没有领导者，所以直接进行下一轮的领导者选举。

任期（Term）。图片修改自 In Search of an Understandable Consensus Algorithm。

日志（Log）

日志由索引（Index）、任期（Term）及指令（Command）组成，索引一样是个严格递增的数字，任期在这里代表在哪个任期记录的日志，指令代表要做什么操作。以下图为例，红色框框圈起来的代表「日志索引4 发生在任期2，指令是把x 设定成2」。

资料状态机（State Machine）

State Machine的中文翻译应该是状态机，但这里我们用资料状态机比较好跟节点状态区分。Raft透过日志记录使用者发送的指令，但写进日志只是一个记录，并不代表资料的状态真的改变了，在日志复制那节，我会再说明从新增日志到改变资料状态的条件，但这里我们先知道新增日志跟改变资料状态是两回事。

上一篇有提到CP 模型通常会用两阶段提交（Two-Phase Commit, 2PC），这也是为什么Raft 要把日志跟资料状态机分开的原因，写进日志是第一阶段，改变资料状态机是第二阶段。以下图为例，假设每次新增日志都达成改变资料状态的条件，那资料的状态也会随着日志里的指令而改变。

什么是区块链?区块链与比特币的关系

加密货币的日益普及，引起了主流群体对区块链技术及其可能性的兴趣。区块链越来越多地被用作一个通用术语，大多数人把它与比特币联系在一起，比特币是利用这种技术创造的一种

领导者选举（Leader Election）

上面我们有提到节点有三种状态— 跟随者（Follower）、候选人（Candidate）以及领导者（Leader），以下我们就依据不同的节点状态及每个状态可能会遇到的事件，来理解Raft领导者选举的机制。

跟随者（Follower）

每个节点刚启动时都是跟随者，跟随者会维护领导者心跳信息的计时器（Timer），依据计时器倒数的结果，会有下面两种可能：

• 继续当跟随者：计时器倒数为0 前，收到领导者心跳信息（Heartbeat）或是候选人投票请求讯息（RequestVote RPC），节点会重置倒数钟继续当跟随者（如下图节点B 跟C ）。
• 成为候选人：计时器倒数为0 时，都没收到领导者心跳信息，也没有收到其他候选人的讯息，跟随者判定现在集群里没有领导者而发起选举，变成候选人。节点从跟随者变成候选人时会把自己的任期（Term）加一，并投自己一票（如下图节点A）。上面有提到一个任期最多只会有一个领导者，所以节点在发起选举时把任期加一，代表节点认为上个任期已经结束了，进入下一个任期。

候选人（Candidate）

节点成为候选人后会立即向每个节点发出投票请求（RequestVote RPC），并维护一个选举超时（Election Timeout）的计时器，依据投票结果，会有下面三种情况：

• 成为领导者：只要候选人获得超过半数的票数，候选人就会把自己的状态改成领导者（如下图节点A），并开始对其他节点发送心跳信息。
• 退回跟随者：候选人在选举期间发现已经有同任期的领导者，或者是更高任期的领导者时，把自己的状态改回跟随者。
• 选举超时（Election timeout）：当候选人的倒数钟倒数为0 时，自己没办法变成领导者，也没有接到其他领导者的心跳信息，此时节点会判定这次选举失败，开始下一次的选举，候选人会把自己的任期加一，代表新任期的开始，同时把自己的票数重置为1，最后向其他节点再次发送投票请求。

领导者（Leader）

节点在担任领导者期间，会持续向其他节点发送心跳信息，防止其他节点举办选举，但集群也可能因为分区（Partition）而有两个领导者，当分区恢复后，其中一位领导者发现另一位领导者任期比他高时，任期低的领导者会退回跟随者，让集群恢复只有一位领导者的状态。

投票原则

上面是节点在三种状态下可能会遇到的情况，接下来说明节点遇到投票请求（RequestVote RPC）时，会怎么投票：

• 任期高的不投给任期低，日志索引高的不投给日志索引低的节点，这点是为了确保只有日志最完整的节点可以成为领导者。
• 若候选人满足上一点，节点会优先投给最早发送投票请求的候选人。
• 每个节点在一个任期内，只能投一张票。

日志复制（Log Replication）

上面有提到从写进日志（Log）到改变资料状态机（State Machine）是有条件的，这一节会说明Raft如何进行日志复制，并改变资料状态机。由于Raft是强领导者模型，所以也只有领导者可以接收客户端的写入请求进行处理，领导者收到客户端的请求后，会把客户端的指令写进日志，接下来进行发送日志复制请求（AppendEntries RPC）给其他节点，只要领导者收到超过半数的成功回覆，领导者就会执行这条日志的指令（Command），改变自己的资料状态机，并回覆成功给客户端。

上述情况是个理想的情况，但现实中可能因为各种问题，造成每个Follower的日志不一致（如下图）。Raft在日志复制请求（AppendEntries RPC）的设计上，不允许直接复制最新的日志，而跳过中间尚未复制的日志。如下图领导者如果发送索引8的日志复制请求给第一个跟随者，这个跟随者目前最新的日志只有到索引5，所以会拒绝领导者的请求，此时领导者会继续发送索引7的日志复制请求给第一个跟随者，跟随者一样会拒绝，直到领导者发送索引6的日志复制请求给第一个跟随者时，跟随者才会接受，并从索引6开始重新同步到索引8。

所以如果Raft 集群要对外服务，则至少要有一半以上的节点有完备的日志记录时，才可以对外服务，因为没有完备日志记录的节点，就无法对最新写进日志的要求回覆成功。

Raft 设计巧思

说完了Raft 运作的机制，我们回过头来看Raft 设计上的两个巧思— 选举超时时间随机、两阶段提交优化以及分区容错。

超时时间随机（Randomized timeout）

从跟随者到候选人的GIF 可以发现，每个节点的计时器倒数的时间是不一样的，所以有的节点比较快变成候选人，有的则还在倒数，这样的设计是为了避免节点们同时发起投票，导致票数分散，进而造成选举失败，大家还记得上面有说，每个选举任期只有在有领导者之后才能对外服务，所以Raft 要尽量保证选举可以成功，另外为了避免节点频繁发起选举，Raft 论文建议把超时设定在150–300ms 之间。

两阶段提交优化

在上一篇我们有提到，两阶段提交应该要在集群都完成执行阶段（Commit Phase）后，才回覆给客户端，不过在Raft 里面，只有领导者完成了执行阶段就回覆给客户端了，所以等于省略的一半的讯息传播，这是Raft 的一个优化。

不过大家一定会想，那跟随者们怎么知道什么时候可以进行执行阶段？大家还记得我们前面提到的心跳信息吗？其实心跳信息也是日志复制请求信息（AppendEntries RPC），而日志请求信息里面会带  leaderCommit，代表领导者目前最新进入执行阶段的日志索引（Index），所以领导者在传播心跳信息时，不仅是通知跟随者们不要发起选举，同时也在进行日志复制以及同步资料状态机（State Machine）的状态，借此降低过多的信息量。

分区容错（Partition Tolerance）

大家经过上一篇后，一定会好奇Raft怎么处理分区容错的问题，以下面的GIF为例，Raft集群再发生分区后，确实可能产生两个领导者，导致脑裂的问题，不过我们上面有提到，日志复制只有在大多数节点成功响应之后，领导者才会回传成功给客户端，所以不管分区怎么切，至多只会有一个分区有超过一半的节点，因此也只有一个领导者可以继续对外服务，其他的领导者即使接到客户端的请求，也只能回覆失败。

总结

上一篇我们提到，两阶段提交可以让集群内大多数节点的状态维持一致，达到强一致性，Raft对经典的两阶段提交做了优化，让达成强一致性的流程更为简单；在拜占庭容错算法  PBFT  里，则是把两阶段提交提升为三阶段提交，透过改变流程避免部分节点作恶，造成无法共识。

希望经过这篇文章，可以让读者理解Raft 演算法的运作方式，Raft 在2014 年发表后就迅速获得许多系统采用的其中一个原因就是好理解，另一个原因是Raft 在实作上完美的与系统解耦（Decouple），让系统可以基于Raft 做开发，其他共识机制像是Zookeeper 的ZAB，在发表之初就是为了Zookeeper 服务的，所以其他系统比较难基于ZAB 之上做开发。

Raft在线上有许多教材及各种语言的实作版本，大家如果有想进一步了解，很推荐直接看论文，如果大家觉得直接看论文太刺激的话，也可以看作者在伊利诺大学（University of Illinois Urbana -Champaign）亲自讲解Raft的影片，最后如果想深入原始码研究的话，可以研究  Hashicorp  的版本，原因是这个版本已经被应用在各大系统如  Consul、IPFS  及  InfluxDB。

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

区块链是什么？区块链重要性在哪？

随着近几年的发展，区块链俨然已经成为了显学，市场和大众也可以区分区块链加密货币有所不同。区块链是技术与新的数据处理逻辑，而加密货币则是由区块链所产生的金融产物。