共识算法特性

⑴ 详解分布式共识（一致性）算法Raft

所谓分布式共识（consensus），与 CAP理论 中的一致性（consistency）其实是异曲同工，就是在分布式系统中，所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法，它与一致性协议这个词也经常互相通用。

当今最着名的共识算法就是Paxos算法。它由Leslie Lamport在1990年提出，很长时间以来都是一致性的事实标准。但是它有两个不小的缺点：难以理解和证明，难以在实际工程中实现。Google Chubby的工程师就曾有以下的评论：

于是2014年，来自斯坦福的两位大佬Diego Ongaro与John Ousterhout通过论文 《In Search of an Understandable Consensus Algorithm》 提出了一个新的共识算法Raft。从题目就可以看出，Raft的特点就是容易理解，在此基础上也容易实现，因此在real world中，它的应用也比Paxos要广泛，比较有名的如etcd、Ku等。

Raft为了达到易懂易用的目标，主要做了两件事：一是分解问题（decomposition），即将复杂的分布式共识问题拆分为 领导选举 （leader election）、 日志复制 （log replication）和 安全性 （safety）三个子问题，并分别解决；二是压缩状态空间（state space rection），相对于Paxos算法而言施加了更合理的限制，减少因为系统状态过多而产生的不确定性。

下面先简要介绍共识算法的基础——复制状态机，然后就来按顺序研究Raft是如何解决三个子问题的。

在共识算法中，所有服务器节点都会包含一个有限状态自动机，名为复制状态机（replicated state machine）。每个节点都维护着一个复制日志（replicated logs）的队列，复制状态机会按序输入并执行该队列中的请求，执行状态转换并输出结果。可见，如果能保证各个节点中日志的一致性，那么所有节点状态机的状态转换和输出也就都一致。共识算法就是为了保障这种一致性的，下图示出简单的复制状态机及其相关架构。

根据分布式系统的 Quorum机制 与NRW算法，集群中半数以上节点可用时，就能正确处理分布式事务，因此Raft集群几乎都使用奇数节点，可以防止脑裂并避免浪费资源。采用ZAB协议的ZooKeeper集群也是如此。

在Raft集群中，任意节点同一时刻只能处于领导者（leader）、跟随者（follower）、候选者（candidate）三种状态之一。下图示出节点状态的转移规则。

可见，集群建立时所有节点都是跟随节点。如果在一定时间过后发现没有领导节点，就会切换到候选状态，发起选举。得到多数票的候选者就会成为领导节点。如果候选节点或当前领导节点发现了更新的领导者，就会主动退回跟随状态。

领导节点全权负责管理复制日志，也就是从客户端接收请求，复制到跟随节点，并告诉跟随节点何时可以处理这些请求。如果领导节点故障或断开连接，就会重新进行选举。可见，领导节点的存在大大简化了共识算法的设计。

在上面的图中出现了任期（term）这个词。领导者并不是一直“在位”的，工作一段时间之后，就会选举出新的领导者来接替它。

由上图可见，蓝色表示选举时间段，绿色表示选举出的领导者在位的时间段，这两者合起来即称作一个任期，其计数值是自增的。任期的值就可以在逻辑上充当时间戳，每个节点都会保存一份自己所见的最新任期值，称为currentTerm。另外，如果因为票数相同，没能选出领导，就会立即再发起新的选举。

如果一个或多个跟随节点在选举超时（election timeout）内没有收到领导节点的心跳（一个名为AppendEntries的RPC消息，本意是做日志复制用途，但此时不携带日志数据），就会发起选举流程：

根据其他节点回复的消息，会出现如下三种结果：

获得多数票的节点只要当选，就会立即给其他所有节点发送AppendEntries，避免再次选举。另外，在同一任期内，每个节点只能投一票，并且先到先得（first-come-first-served），也就是会把票投给RequestVote消息第一个到达的那个节点。

至于上面的第三种情况，也就是所谓“split vote”现象，容易在很多跟随者变成候选者时出现，因为没有节点能得到多数票，选举有可能无限继续下去。所以，Raft设置的选举超时并不是完全一样的，而是有些许随机性，来尽量使得投票能够集中到那些较“快”的节点上。

领导节点选举出来后，集群就可以开始处理客户端请求了。前面已经说过，每个节点都维护着一个复制日志的队列，它们的格式如下图所示。

可见，日志由一个个按序排列的entry组成。每个entry内包含有请求的数据，还有该entry产生时的领导任期值。在论文中，每个节点上的日志队列用一个数组log[]表示。

当客户端发来请求时，领导节点首先将其加入自己的日志队列，再并行地发送AppendEntries RPC消息给所有跟随节点。领导节点收到来自多数跟随者的回复之后，就认为该请求可以提交了（见图中的commited entries）。然后，领导节点将请求应用（apply）到复制状态机，并通知跟随节点也这样做。这两步做完后，就不会再回滚。
这种从提交到应用的方式与最基础的一致性协议——两阶段提交（2PC）有些相似，但Raft只需要多数节点的确认，并不需要全部节点都可用。

注意在上图中，领导节点和4个跟随节点的日志并不完全相同，这可能是由于跟随节点反应慢、网络状况差等原因。领导节点会不断地重试发送AppendEntries，直到所有节点上的日志达到最终一致，而不实现强一致性。这就是CAP理论中在保证P的情况下，C与A无法兼得的体现。

日志复制的过程仍然遗留了一个问题：如果领导或者跟随节点发生异常情况而崩溃，如何保证日志的最终一致性？它属于下面的安全性问题中的一部分，稍后会解答它。

安全性是施加在领导选举、日志复制两个解决方案上的约束，用于保证在异常情况下Raft算法仍然有效，不能破坏一致性，也不能返回错误的结果。所有分布式算法都应保障安全性，在其基础上再保证活性（liveness）。

Raft协议的安全性保障有5种，分别是：选举安全性（election safety）、领导者只追加（leader append-only）、日志匹配（log matching）、领导者完全性（leader completeness）、状态机安全性（state machine safety） 。下面分别来看。

选举安全性是指每个任期内只允许选出最多一个领导。如果集群中有多于一个领导，就发生了脑裂（split brain）。根据“领导选举”一节中的描述，Raft能够保证选举安全，因为：

在讲解日志复制时，我们可以明显地看出，客户端发出的请求都是插入领导者日志队列的尾部，没有修改或删除的操作。这样可以使领导者的行为尽量简单化，使之没有任何不确定的行为，同时也作为下一节要说的日志匹配的基础。

日志匹配的具体描述如下。
如果两个节点的日志队列中，两个entry具有相同的下标和任期值，那么：

第一点自然由上一节的“领导者只追加”特性来保证，而第二点则由AppendEntries RPC消息的一个简单机制来保证：每条AppendEntries都会包含最新entry之前那个entry的下标与任期值，如果跟随节点在对应下标找不到对应任期的日志，就会拒绝接受并告知领导节点。

有了日志匹配特性，就可以解决日志复制中那个遗留问题了。假设由于节点崩溃，跟随节点的日志出现了多种异常情况，如下图。

注意图中不是6个跟随节点，而是6种可能的情况。比如a和b是丢失了entry，c和d是有多余的未提交entry，e和f则是既有丢失又有冗余。这时领导节点就会找到两个日志队列中最近一条匹配的日志点，将该点之后跟随节点的所有日志都删除，然后将自己的这部分日志复制给它。例如对于上图中的情况e来说，最近一条匹配的日志下标为5，那么5之后的所有entry都会被删除，被替换成领导者的日志。

领导者完全性是指，如果有一条日志在某个任期被提交了，那么它一定会出现在所有任期更大的领导者日志里。这也是由两点来决定的：

根据这两个描述，每次选举出的领导节点一定包含有最新的日志，因此只存在跟随节点从领导节点更新日志的情况，而不会反过来，这也使得一致性逻辑更加简化，并且为下面的状态机安全性提供保证。

状态机安全性是说，如果一个节点已经向其复制状态机应用了一条日志中的请求，那么对于其他节点的同一下标的日志，不能应用不同的请求。这句话就很拗口了，因此我们来看一种意外的情况。

这里就有问题了，在时刻c的日志与新领导者的日志发生了冲突，此时状态机是不安全的。
为了解决该问题，Raft不允许领导者在当选后提交“前任”的日志，而是通过日志匹配原则，在处理“现任”日志时将之前的日志一同提交。具体方法是：在领导者任期开始时，立刻提交一条空的日志，所以上图中时刻c的情况不会发生，而是像时刻e一样先提交任期4的日志，连带提交任期2的日志。就算此时S1再崩溃，S5也不会重新被选举了。

如果想要更直观地理解Raft，建议参考 这里 ，是一个用动画来描述该算法的网页，形象生动。

⑵ 简评三个基于VRF的共识算法

上交所技术公司  朱立

Algorand、Dfinity和Ouroboros Praos三个共识算法（Dfinity虽然是项目名，这里用来称呼其共识算法也应无不妥）近期较受关注，而且都是基于VRF(Verifiable Random Function) 设计，可以对照学习。Algorand的版本很多，以下单指  1607.01341v9 ，暂称其为Algorand'（笔者手中另有Algorand的 最新版本 ，其中已对下文提及的几处问题完成了修正，可与本文参看）。

一、VRF的共性

VRF的意义很好理解——用以完成出块人（群）的随机选择。为此，VRF的返回值应尽力难以预测。先看Algorand'和Dfinity的套路是怎么做的：大体上是先将前一个随机数（最初的随机数却是协议给定的）和某种代表高度、轮次的变量进行组合，用某种私钥对之进行签名（或者是先签名再组合），最后哈希一下得出最新的随机数。这样产生的随机数旁人很容易验证其合乎算法，"V"就这样得到了；而哈希返回值又是随机分布的，“R”也因此得到保证。在此过程中，为降低操纵结果的可能性，有两个注意事项： A) 签名算法应当具有唯一性，也就是用同一把私钥对同样的信息进行签名，只有一个合法签名可以通过验证——普通的非对称加解密算法一般不具备这个属性，如SM2。如果用的签名算法没有这种uniqueness属性，那在生成新随机数的时候就存在通过反复多次尝试签名以挑出最有利者的余地，会降低安全性。 B) 避免在生成新随机数时将当前块的数据作为随机性来源之一，比如引用本块交易列表的merkle root值等等，因为这样做会给出块人尝试变更打包交易顺序、尝试打包不同交易以产生最有利的新随机数的余地。在设计和检视新的共识算法时，以上两个注意事项是要特别留意的。

考察一下VRF的返回结果应该如何运用。目前所见用法中，VRF的返回结果可以用来公开完成节点或节点群体的选择，也可以私密地完成选择。以Dfinity为例，它是利用mod操作来唯一、公开地确定一个Group。Algorand'、Ouroboros Praos是私密选择的范例，大致套路是对VRF的最新返回值，配上轮次等变量后用私钥进行签名并哈希，如果哈希值小于某个阈值，节点就可以私密地知道自己被选中。这种方法很可能在网络节点数较多时的表现会更稳定，否则幸运儿个数上下波动会较大，进而影响协议表现，包括空块和分叉。

二、简评强同步假设版本的Algorand'

私密选择提供了较强的抗击定点攻击的能力，但由于幸运儿的总数对于任何一个幸运儿都是不能预知的，也因此给后续共识算法的设计和区块链的优化带来了困难。Algorand‘采用了很强的同步网络假设（同步网络假设下的共识算法当然容易做一些），要求预先知道网络消息传播时间的上限：在固定时间内完成对固定比例的用户的网络传播。比如要知道，1KB消息，在1秒钟内完成全网95%的传播，而1MB消息需要1.5分钟完成全网95%的传播。但这个传输上限应该如何选择？ 通过一段时间的统计结果再乘以一个系数这种经验统计？只能说“感觉上可以”，但如果要严谨和安全，Algorand‘算法应该补充证明即使在遭遇DDOS或互联网拥堵的情况下消息传播严重超限后算法仍然能够保证安全——然而这个证明是缺失的。作为对照，Ouroboros Praos公开承认之前在同步网络假设下设计的Ouroboros协议在异步网络条件下会出错，所以才又做了Ouroboros Praos；新版本的Algorand承认在弱同步网络时会在不同的块上达成共识（后续网络恢复强同步时分叉可以得到解决）云云，这些都可资参考。

即使我们暂且认可Algorand'算法可以通过设定一个很大的传播时间上限来回应上述问题，但随之而来的是此时可以看出此算法缺乏一个非常好的特性：Responsiveness。这个特性指的是：若一个协议被设计为在一个较大的传播时间上限DELTA下工作，但若实际传播时间是较小的delta，则协议的实际推进步调将只和delta有关，这种协议被称为Responsive的。具有Responsive特性的共识算法再配以同步网络假设会非常理想——出于安全，上限可以设置很大，然而协议执行速度只和当时网络条件有关。Algorand'并不具有这种特性。平均而言，Algorand'完成共识所需的消息传送次数是11轮，每轮如果要确保安全，完成共识的时间就会很长，单个分区的吞吐量就不会太高。当然，架构设计涉及很多取舍，最终评价一个算法好还是不好还是要回到初心——准备拿来实现的目标是什么。上述分析只是尝试客观地指出Algorand'算法的几个少为人知的固有特征，供读者自行评估。

三、简评Dfinity的可扩展性问题

私密选择并且立即上任的做法，也给系统分片带来了极大挑战。Dfinity是明确要做分片(Sharding)的，所以必须直面挑战。可扩展性问题非常复杂，完整解决这个问题需要通盘考虑网络、存储、计算三方面的可扩展性——时下大多数区块链3.0项目只注意到计算的分片和可扩展性，忽略了其余二者，从而不可能真正实现理想的扩展。由于公链节点网络带宽的制约，计算合约所需的数据通常很难迅速地从一个节点拷贝到另一节点，所以就算用VRF实现了飘忽来去的出块节点选择，存储节点是没法同样飘逸如风的。明显的选择有那么几个：全部节点存储全部数据，不同节点静态地分配用来存储不同分区。前者的可扩展性很差，对于后者而言，如果出块节点漂浮不定且出块节点还需要完成合约运算，就意味着基于P2P网络来回远程访问存储，性能多半急剧下降；动态决定的出块节点只完成排序共识，计算能力和存储捆绑，通过静态分区提供可扩展性，可能是合理的应对。然而，最可恨的就是“然而”二字——即使如此，系统还存在一处对存储和网络构成压力的所在：最终用户提交的待打包交易。普通公链（先不考虑EOS那种）的带宽有限，如果用户提交的待打包交易必须粗放型地全网泛滥传播，那现有网络带宽可以提供多少TPS？如果出块节点是静态分区或者至少提前一段时间公开知晓，事情尚有回旋余地；如果出块节点是如此飘忽不定，而且直到最后一刻也只有这些节点自己知道，那无论是用户还是出块节点候选人看起来最直接的应对之道就是全网泛滥传播全部待打包交易、保存全部待打包交易，这样带宽和存储仍然成为系统瓶颈。

所以这里碰到的，本质上还是安全、可扩展性、去中心化的不可能三角。

四、简评Ouroboros Praos

BM怼 Ouroboros的文字已经流传广泛。BM的话当然有些明显是不对的，比如Ouroboros的DPOS是指"Dynamic [stake distribution] POS"而不是BM的Delegate POS，但其关于Pareto分布的评论则值得玩味。如果我们仔细浏览后出的Ouroboros Praos，可以发现协议的安全假设和安全证明完全没有考虑经济博弈因素，因此洋洋洒洒的证明很可能会不得要领而错过真正需要防护的方向——毕竟一直以来POS/DPOS这些协议的血管里面流淌的就是基于经济博弈和人性进行设计的血液。最明显的例子是在forward secure signature的实现方法上，协议目前的设计是要求每个好的节点自觉主动地安全删除用过的私钥，而完全没有考虑近乎零的私钥保存成本如何面对bribe attack的诱惑，然而这却是值得考虑的。除了形式化证明之外，Ouroboros Praos本身并没有太多值得关注的协议特征，总体上就是用VRF抽签结合POS算法并针对某些安全假设进行了形式化证明，其做事的态度是非常值得赞赏的。

五、总结

这几个算法本身颇有创意，也很值得学习。与此同时，在看过以太坊CASPER目前披露的分区技术后，笔者的体会是：区块链3.0的竞争才刚刚开始，从以太坊团队的技术路线看，他们的技术考量和选择要比很多宣称要超越以太坊的团队来得深刻和全面。如果当真要超越以太坊，还是应该先从理解以太坊开始。

顺便感谢趣链邱炜伟博士对本文的贡献！

⑶ 共识算法（分布式下的一致性算法)

共识算法（分布式下的一致性算法)

业务场景：

达到的效果：可以保证在过半节点正常的情况下，所有的写入操作不会丢失。

Zab协议并不保证强一致性，也不是弱一致性，而是在一定限度内的强一致性慎轿山。

缺点：

缺点：

区块链1.0时代：比特币，作用就是去中心化的货币，无国界的货币，并且可以匿名性的洗钱
区块链2.0时代：代表以太坊，引入了智能合约的概念，发挥其 去中心化和不可篡改的特性，可以实现类似于 追溯、拍卖、投票等业务场景。

区块链技术的实用价值：
无国界虚拟货币：比如比特币

模拟一个拍卖（盲拍）的业务场景（发布一个智能合约）：
https://solidity.readthedocs.io/en/latest/solidity-by-example.html#simple-open-auction

普通拍卖可能存在的问题：

商家A对一件商品公开自己要拍卖，智能合约在规定的时间会开始接收竞拍（参与竞拍的人需要支付保证金（以太币）），在竞拍结束之后，价格最高的人会完成支付，帆空其它的买家的保证金会全额退回。
然后成功竞拍者可以线下去找卖家，证明自己的身份，然后获得竞拍品

优点：

工作量证明（ PoW ）通过计算一个数值（ nonce ），使得拼揍上交易数据后内容的 Hash 值满足规定的上限。在节点成功找到满足的Hash值之后，会马上对全网进行广播打包区块，网络的节点收到广播打包区块，会立刻对其进行验证

举个例子，给定的一个基本的字符串”Hello, world!”，我们给出的工作量要求是，可以在这个字符串后面添加一个叫做nonce的整数值，对变更后（添加nonce)的字符串进行SHA256哈希运算，
如果得到的哈希结果（以16进制的形式表示）是以”0000”开头的，则验证通过。为了达到这个工作量证明的目标。我们需要不停的递增nonce值，对得到的新字符串进行SHA256哈希运算。
按照这个规则，我们需要经过4251次计算才能找到恰好前4位为0的哈希散列。计算完之后，然后广播到临近的节点，临近的节点会先验算交易是否合法（金额是否异常），再验证hash值是否满足要求，都满足的话，就会把这个数据块添加到自己的账本中。

优点：

缺点：

计算难度值会因为 股东持有的 币龄而降低，为挖矿无形之中提升了壁垒，股东更容易算出结果值（难度更低），从而避免过度的算力竞争，节省电力，提升系统的稳定性。
因为从人性的角度，股东更不愿意让不安全的现象发生（比如攻击主链)，因为会造成信用降低，从而自己的矿币贬值。让股东拥有更多的记账权，让主链更安全宽中。

扩展可以参考我之前写过的zab专栏博客
https://www.jianshu.com/nb/32551354

⑷ 区块链 --- 共识算法

PoW算法是一种防止分布式服务资源被滥用、拒绝服务攻击的机制。它要求节点进行适量消耗时间和资源的复杂运算，并且其运算结果能被其他节点快速验算，以耗用时间、能源做担保，以确保服务与资源被真正的需求所使用。

PoW算法中最基本的技术原理是使用哈希算法。假设求哈希值Hash(r)，若原始数据为r（raw），则运算结果为R（Result）。

R = Hash(r)

哈希函数Hash()的特性是，对于任意输入值r，得出结果R，并且无法从R反推回r。当输入的原始数据r变动1比特时，其结果R值完全改变。在比特币的PoW算法中，引入算法难度d和随机值n，得到以下公式：

Rd = Hash(r+n)

该公式要求在填入随机值n的情况下，计算结果Rd的前d字节必须为0。由于哈希函数结果的未知性，每个矿工都要做大量运算之后，才能得出正确结果，而算出结果广播给全网之后，其他节点只需要进行一次哈希运算即可校验。PoW算法就是采用这种方式让计算消耗资源，而校验仅需一次。

 

PoS算法要求节点验证者必须质押一定的资金才有挖矿打包资格，并且区域链系统在选定打包节点时使用随机的方式，当节点质押的资金越多时，其被选定打包区块的概率越大。

POS模式下，每个币每天产生1币龄，比如你持有100个币，总共持有了30天，那么，此时你的币龄就为3000。这个时候，如果你验证了一个POS区块，你的币龄就会被清空为0，同时从区块中获得相对应的数字货币利息。

节点通过PoS算法出块的过程如下：普通的节点要成为出块节点，首先要进行资产的质押，当轮到自己出块时，打包区块，然后向全网广播，其他验证节点将会校验区块的合法性。

 

DPoS算法和PoS算法相似，也采用股份和权益质押。

但不同的是，DPoS算法采用委托质押的方式，类似于用全民选举代表的方式选出N个超级节点记账出块。

选民把自己的选票投给某个节点，如果某个节点当选记账节点，那么该记账节点往往在获取出块奖励后，可以采用任意方式来回报自己的选民。

这N个记账节点将轮流出块，并且节点之间相互监督，如果其作恶，那么会被扣除质押金。

通过信任少量的诚信节点，可以去除区块签名过程中不必要的步骤，提高了交易的速度。
 

拜占庭问题：

拜占庭是古代东罗马帝国的首都，为了防御在每块封地都驻扎一支由单个将军带领的军队，将军之间只能靠信差传递消息。在战争时，所有将军必须达成共识，决定是否共同开战。

但是，在军队内可能有叛徒，这些人将影响将军们达成共识。拜占庭将军问题是指在已知有将军是叛徒的情况下，剩余的将军如何达成一致决策的问题。

BFT：

BFT即拜占庭容错，拜占庭容错技术是一类分布式计算领域的容错技术。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或中断以及遭到恶意攻击等原因，计算机和网络可能出现不可预料的行为。拜占庭容错技术被设计用来处理这些异常行为，并满足所要解决的问题的规范要求。

拜占庭容错系统 ：

发生故障的节点被称为 拜占庭节点 ，而正常的节点即为 非拜占庭节点 。

假设分布式系统拥有n台节点，并假设整个系统拜占庭节点不超过m台（n ≥ 3m + 1），拜占庭容错系统需要满足如下两个条件：

另外，拜占庭容错系统需要达成如下两个指标：

PBFT即实用拜占庭容错算法，解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是O(n^2)，使得在实际系统应用中可以解决拜占庭容错问题
 

PBFT是一种状态机副本复制算法，所有的副本在一个视图（view）轮换的过程中操作，主节点通过视图编号以及节点数集合来确定，即：主节点 p = v mod |R|。v：视图编号，|R|节点个数，p：主节点编号。

PBFT算法的共识过程如下：客户端（Client）发起消息请求（request），并广播转发至每一个副本节点（Replica），由其中一个主节点（Leader）发起提案消息pre-prepare，并广播。其他节点获取原始消息，在校验完成后发送prepare消息。每个节点收到2f+1个prepare消息，即认为已经准备完毕，并发送commit消息。当节点收到2f+1个commit消息，客户端收到f+1个相同的reply消息时，说明客户端发起的请求已经达成全网共识。

具体流程如下 ：

客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。

主节点收到客户端的请求，需要进行以下交验：

a. 客户端请求消息签名是否正确。

非法请求丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条<<PRE-PREPARE, v, n, d>, m>消息给其他副本节点。v：视图编号，d客户端消息摘要，m消息内容。<PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H]，具体原因参见 垃圾回收 章节。

副本节点i收到主节点的PRE-PREPARE消息，需要进行以下交验：

a. 主节点PRE-PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。正确请求，副本节点i向其他节点包括主节点发送一条<PREPARE, v, n, d, i>消息, v, n, d, m与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。<PREPARE, v, n, d, i>进行副本节点i的签名。记录PRE-PREPARE和PREPARE消息到log中，用于View Change过程中恢复未完成的请求操作。

主节点和副本节点收到PREPARE消息，需要进行以下交验：

a. 副本节点PREPARE消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. n是否在区间[h, H]内。

d. d是否和当前已收到PRE-PPREPARE中的d相同

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息，则向其他节点包括主节点发送一条<COMMIT, v, n, d, i>消息，v, n, d, i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进行副本节点i的签名。记录COMMIT消息到日志中，用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。

主节点和副本节点收到COMMIT消息，需要进行以下交验：

a. 副本节点COMMIT消息签名是否正确。

b. 当前副本节点是否已经收到了同一视图v下的n。

c. d与m的摘要是否一致。

d. n是否在区间[h, H]内。

非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息，说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。
 

如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。

如果主节点掉线或者作恶不广播客户端的请求，客户端设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线，发起View Change协议。

View Change协议 ：

副本节点向其他节点广播<VIEW-CHANGE, v+1, n, C , P , i>消息。n是最新的stable checkpoint的编号， C 是 2f+1验证过的CheckPoint消息集合， P 是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

当主节点p = v + 1 mod |R|收到 2f 个有效的VIEW-CHANGE消息后，向其他节点广播<NEW-VIEW, v+1, V , O >消息。 V 是有效的VIEW-CHANGE消息集合。 O 是主节点重新发起的未经完成的PRE-PREPARE消息集合。PRE-PREPARE消息集合的选取规则：

副本节点收到主节点的NEW-VIEW消息，验证有效性，有效的话，进入v+1状态，并且开始 O 中的PRE-PREPARE消息处理流程。
 

在上述算法流程中，为了确保在View Change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后副本节点需要把之前该请求的记录消息清除掉。

最简单的做法是在Reply消息后，再执行一次当前状态的共识同步，这样做的成本比较高，因此可以在执行完多条请求K（例如：100条）后执行一次状态同步。这个状态同步消息就是CheckPoint消息。

副本节点i发送<CheckPoint, n, d, i>给其他节点，n是当前节点所保留的最后一个视图请求编号，d是对当前状态的一个摘要，该CheckPoint消息记录到log中。如果副本节点i收到了2f+1个验证过的CheckPoint消息，则清除先前日志中的消息，并以n作为当前一个stable checkpoint。

这是理想情况，实际上当副本节点i向其他节点发出CheckPoint消息后，其他节点还没有完成K条请求，所以不会立即对i的请求作出响应，它还会按照自己的节奏，向前行进，但此时发出的CheckPoint并未形成stable。

为了防止i的处理请求过快，设置一个上文提到的 高低水位区间[h, H] 来解决这个问题。低水位h等于上一个stable checkpoint的编号，高水位H = h + L，其中L是我们指定的数值，等于checkpoint周期处理请求数K的整数倍，可以设置为L = 2K。当副本节点i处理请求超过高水位H时，此时就会停止脚步，等待stable checkpoint发生变化，再继续前进。
 

在区块链场景中，一般适合于对强一致性有要求的私有链和联盟链场景。例如，在IBM主导的区块链超级账本项目中，PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。
 

 

Raft基于领导者驱动的共识模型，其中将选举一位杰出的领导者(Leader)，而该Leader将完全负责管理集群，Leader负责管理Raft集群的所有节点之间的复制日志。
 

下图中，将在启动过程中选择集群的Leader（S1），并为来自客户端的所有命令/请求提供服务。 Raft集群中的所有节点都维护一个分布式日志（复制日志）以存储和提交由客户端发出的命令（日志条目）。 Leader接受来自客户端的日志条目，并在Raft集群中的所有关注者（S2，S3，S4，S5）之间复制它们。

在Raft集群中，需要满足最少数量的节点才能提供预期的级别共识保证， 这也称为法定人数。 在Raft集群中执行操作所需的最少投票数为 (N / 2 +1) ，其中N是组中成员总数，即 投票至少超过一半 ，这也就是为什么集群节点通常为奇数的原因。 因此，在上面的示例中，我们至少需要3个节点才能具有共识保证。

如果法定仲裁节点由于任何原因不可用，也就是投票没有超过半数，则此次协商没有达成一致，并且无法提交新日志。

 

数据存储：Tidb/TiKV

日志：阿里巴巴的 DLedger

服务发现：Consul& etcd

集群调度：HashiCorp Nomad
 

只能容纳故障节点(CFT)，不容纳作恶节点

顺序投票，只能串行apply，因此高并发场景下性能差
 

Raft通过解决围绕Leader选举的三个主要子问题，管理分布式日志和算法的安全性功能来解决分布式共识问题。

当我们启动一个新的Raft集群或某个领导者不可用时，将通过集群中所有成员节点之间协商来选举一个新的领导者。 因此，在给定的实例中，Raft集群的节点可以处于以下任何状态: 追随者(Follower)，候选人(Candidate)或领导者(Leader)。

系统刚开始启动的时候，所有节点都是follower，在一段时间内如果它们没有收到Leader的心跳信号，follower就会转化为Candidate；

如果某个Candidate节点收到大多数节点的票，则这个Candidate就可以转化为Leader，其余的Candidate节点都会回到Follower状态；

一旦一个Leader发现系统中存在一个Leader节点比自己拥有更高的任期(Term)，它就会转换为Follower。

Raft使用基于心跳的RPC机制来检测何时开始新的选举。 在正常期间， Leader 会定期向所有可用的 Follower 发送心跳消息（实际中可能把日志和心跳一起发过去）。 因此，其他节点以 Follower 状态启动，只要它从当前 Leader 那里收到周期性的心跳，就一直保持在 Follower 状态。

当 Follower 达到其超时时间时，它将通过以下方式启动选举程序：

根据 Candidate 从集群中其他节点收到的响应，可以得出选举的三个结果。

共识算法的实现一般是基于复制状态机（Replicated state machines），何为 复制状态机 ：

简单来说： 相同的初识状态 + 相同的输入 = 相同的结束状态 。不同节点要以相同且确定性的函数来处理输入，而不要引入一下不确定的值，比如本地时间等。使用replicated log是一个很不错的注意，log具有持久化、保序的特点，是大多数分布式系统的基石。

有了Leader之后，客户端所有并发的请求可以在Leader这边形成一个有序的日志（状态）序列，以此来表示这些请求的先后处理顺序。Leader然后将自己的日志序列发送Follower，保持整个系统的全局一致性。注意并不是强一致性，而是 最终一致性 。

日志由有序编号（log index）的日志条目组成。每个日志条目包含它被创建时的任期号（term），和日志中包含的数据组成，日志包含的数据可以为任何类型，从简单类型到区块链的区块。每个日志条目可以用[ term, index, data]序列对表示，其中term表示任期， index表示索引号，data表示日志数据。

Leader 尝试在集群中的大多数节点上执行复制命令。 如果复制成功，则将命令提交给集群，并将响应发送回客户端。类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要超过一半节点同意（处于工作状态）即可。

leader 、 follower 都可能crash，那么 follower 维护的日志与 leader 相比可能出现以下情况

当出现了leader与follower不一致的情况，leader强制follower复制自己的log， Leader会从后往前试 ，每次AppendEntries失败后尝试前一个日志条目（递减nextIndex值）， 直到成功找到每个Follower的日志一致位置点（基于上述的两条保证），然后向后逐条覆盖Followers在该位置之后的条目 。所以丢失的或者多出来的条目可能会持续多个任期。
 

要求候选人的日志至少与其他节点一样最新。如果不是，则跟随者节点将不投票给候选者。

意味着每个提交的条目都必须存在于这些服务器中的至少一个中。如果候选人的日志至少与该多数日志中的其他日志一样最新，则它将保存所有已提交的条目，避免了日志回滚事件的发生。

即任一任期内最多一个leader被选出。这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：

因此， 某一任期内一定只有一个leader 。
 

当集群中节点的状态发生变化（集群配置发生变化）时，系统容易受到系统故障。 因此，为防止这种情况，Raft使用了一种称为两阶段的方法来更改集群成员身份。 因此，在这种方法中，集群在实现新的成员身份配置之前首先更改为中间状态（称为联合共识）。 联合共识使系统即使在配置之间进行转换时也可用于响应客户端请求，它的主要目的是提升分布式系统的可用性。