平行区块链之共识篇：分布式一致性与Raft共识协议
普通服务器凭借优秀的性价比在互联网等行业得到了广泛的应用，但普通服务器也不得不面对2%-4%的年故障率[1]。一致性算法（Consensus Algorithm）是解决服务器不可靠问题的有效途径，即在这些不可靠主机之间复制状态需要采取一种机制，以保证每个主机的状态最终达成相同一致性状态，取得共识。
Raft是由Stanford大学的博士生Diego Ongaro设计的，他在2014年秋天正式发表了博士论文：“CONSENSUS: BRIDGING THEORY AND PRACTICE”[3]。这篇论文258页，可能是为了更便于别人阅读，他把Raft相关的部分摘了出来，形成了一篇十多页的文章：“In Search of an Understandable Consensus Algorithm”[4]，从题目就可以看出，把可理解性作为算法的主要目标。作为Paxos形式上等价的实现，Raft相对好理解得多，同时在可用性性能上也没有做任何妥协。本文作为Raft协议初探，重点讲解领导选举与日志复制两个部分，其他内容可参见论文。
一致性问题本质就是replicated state machines[5]，即所有结点都从同一个state出发，都经过同样的一些操作序列（log，日志），最后到达同样的state。其中保证各个节点执行相同的操作序列就是Raft算法所要实现的，即通过选举一个领导人，然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目，把日志条目复制到其他服务器上，并且当保证安全性的时候告诉其他的服务器应用日志条目到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。
图 1 ：复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。
领导选举
Parallel Blockchain一个 Raft 集群包含若干个服务器节点；通常是5个，这允许整个系统容忍2个节点的失效。在任何时刻，每一个服务器节点都处于这三个状态之一：Leader领导人、Follower跟随者或者Candidate候选人。
图 2：服务器状态。跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息，那么他就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导者。在一个任期内,领导人一直都会是领导人直到自己宕机了。
● 在通常情况下，系统中只有一个Leader并且其他的节点全部都是Follower。
● Follower都是被动的：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。领导人处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导人）。
● Candidate：当Follower在规定时间内没有收到Leader的心跳消息时，会作为Candidate发起重新选举。
就像一个民主社会，Leader由民众投票选出。刚开始没有Leader，所有集群中的参与者都是Follower，那么首先开启一轮大选，在大选期间所有群众都能参与竞选，这时所有群众的角色就变成了Candidate，民主投票选出Leader后就开始了这届Leader的任期，然后选举结束，所有除Leader的Candidate又变回Follower角色服从Leader领导。这里提到一个概念「任期」，用术语“Term”表达，不同于现实世界中Leader任期是固定的，Raft中Term是系统随机安排的。
Raft中领导选举的过程大概分为以下几步：
1. 最初的时候所有人都是Follower状态，或者是一个Leader而其他的节点全部都是Follower的状态，所有人都设置了自己的等待超时时间（Election Timeout，如150-300毫秒之间的随机数）；
2. 当一个Follower收不到Leader心跳消息，并且超过其初始设置的等待超时时间时，它就变成了Candidate，然后它会向所有其余节点发送请求投票的信息，如果节点在该轮竞选中没有投过票，就会给它投一票；
3. 如果一个节点收到了大多数的票（假设有N台服务器，N/2+1超过半数），它就会成为Leader；
4. 如果没有任何一方获得多数票，则标志此次选举失败，之后每个参与方随机休息一阵（Election Timeout）重新发起投票直到一方获得多数票。这里的关键就是随机timeout，最先从timeout中恢复发起投票的一方向还在timeout中的另外两方请求投票，这时它们就只能投给对方了，很快达成一致。
影响Raft选举成功率的几个时间相关参数
● RTT（Round Trip Time）：网络延时
● Heartbeat Timeout：心跳间隔
● Election Timeout：Leader与Followers间通信超时触发选举时间
●MTBF（Meantime Between Failure）：Servers连续常规故障时间间隔建议设置RTT<<Heartbeat Timeout<Election Timeout<<MTBF。
日志复制
Parallel Blockchain一旦一个Leader被选举出来，他就开始为客户端提供服务。客户端的每一个请求就是一个日志，都包含一条被复制状态机执行的指令。
1. 假设客户端发出增加一个日志的要求，设置v=3，如1；
2. Leader把这条指令作为一条新的日志条目附加到日志中去，然后并行的发起附加条目 RPCs 给其他的Follower，让他们复制这条日志条目，如2.1；
3. Leader接受Follower复制这条日志条目的反馈，如3.1；
4. 当Leader统计到收到大多数写日志的成功后就会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端，如4.1，这种日志条目被称为committed状态；
5. 然后在下一个心跳中，Leader会通知所有Follower更新committed日志，应用到各自的状态机中，如4.2。
每一个Follower都是属于被动接受的，如果所有的Follower认为自己的数据跟Leader不一样，那么就会把自己的数据全部清空，并且会与Leader进行强行同步，Raft可以保证的是选择出来的Leader一定是拥有最新数据的。所以原来的Follower即使数据不对也没关系，只要去与Leader做一次同步就好了。对于每个新的日志记录，重复上述过程。
如果在这一过程中，发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follower了，那么Leader只能正常更新它能访问的那些Follower，而大多数的Follower因为没有了Leader，他们重新选举一个候选者作为Leader，然后这个Leader作为代表与外界打交道，如果外界要求其添加新的日志，这个新的Leader就按上述步骤通知大多数Follower，如果这时网络故障修复了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算committed，都回滚，接受新的Leader的新的更新。
在分布式计算上，不同的计算机透过信息交换，尝试达成共识；但有时候，系统上协调计算机或成员计算机可能因系统错误并交换错的讯息，导致影响最终的系统一致性。也即，在系统不同的机器之间会传递错误的消息，这种情况即为拜占庭问题。Raft协议不能容忍拜占庭问题，但是能够在非拜占庭错误情况下，有网络延迟、分区、丢包、冗余和乱序等错误情况出现时，都可以保证其操作的正确性。
区块链目前一般分为“公有链”、“联盟链”以及“私有链”。公有链指全世界任何人都可读取的、任何人都能发送交易且交易能获得有效确认的、任何人都能参与其中，这是一个全开放、不可信环境。显而易见，Raft协议不适用，Raft在区块链领域的用武之地在于区块链另外的形式——联盟链或者私有链。
联盟链的特性就是半封闭半开放，有拜占庭容错的诉求但又不是那么强烈，私有链则是完全封闭生态的存储系统，所有节点都是可以信任的。
只要是非拜占庭容错场景下，Raft协议是可以作为区块链的共识算法基础的，例如：
● 腾讯可信区块链即 Trust SQL平台——企业级区块链，致力于提供企业级区块链基础设施、行业解决方案，采用的共识机制就是基于Raft改进的算法；
● 开源社区发布的量子链（Qtum系统），在基于Qtum的联盟链中，采用是Proof of Time 和 Raft协议结合的共识机制，为行业客户提供服务；
● 基于金融服务的私有链初创公司推出的Kadena，私有链平台，其共识机制就是基于Raft协议改进的。
目前，共识算法抽象化、模块化的趋势已经出现。通过将共识算法设计为可插拔、可替换的组件，用户在使用区块链时可以根据自身需要选择最合适的共识算法（例如Raft一流非拜占庭容错的共识算法），量身定制才能恰到好处。
Raft优缺点显而易见。Raft易理解、便于工程实现的一个算法，GitHub统计已有88个开源项目。Raft是一种强领导力的算法，在保证可靠性的同时也会聚集单点风险，吞吐量易受单节点限制，任意包含Leader的时刻，Leader拥有完全记账权，如果此Leader节点是恶意的，后果不堪设想。因此，实际应用中我们需要结合我们的场景综合选择。
参考文献
[1] Schroeder B, Gibson G A, Disk failures in the real world: what does an MTTF of 1,000,000 hours mean to you?[C] In Proc. FAST’07, USENIX Conference on File and Storage Technologies (2007), USENIX, pp. 1-16.
[2] Chandra T D, Griesemer R, Redstone J, Paxos made live: An engineering perspective[C], In Proc. PODC’07, ACM Symposium on Principles of Distributed Computing (2007), ACM, pp. 398-407.
[3] Ongaro D, Consensus: Bridging theory and practice[D]. Stanford University, 2014.
[4] Ongaro D, Ousterhout J K, In search of an understandable consensus algorithm[C], USENIX Annual Technical Conference. 2014: 305-319.
[5] Butterworth H E, Quelch P J, Replicated state machine: U.S. Patent 8,239,707[P]. 2012-8-7.
注：本文由中国科学院自动化研究所助理研究员倪晓春整理。
实用Raft动画演示网站分享：
http://thesecretlivesofdata.com/raft/
扫描上方二维码，关注公众号“平行区块链”，获取更多精彩内容！