区块链raft是什么

区块链 --- 共识算法

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使用了一种称为两阶段的方法来更改集群成员身份。 因此，在这种方法中，集群在实现新的成员身份配置之前首先更改为中间状态（称为联合共识）。 联合共识使系统即使在配置之间进行转换时也可用于响应客户端请求，它的主要目的是提升分布式系统的可用性。

共识算法系列之一：私链的raft算法和联盟链的 pbft 算法

对数据顺序达成一致共识是很多共识算法要解决的本质问题

Fabic的pbft算法实现

现阶段的共识算法主要可以分成三大类：公链，联盟链和私链

私链，所有节点可信

联盟链，存在对等的不信任节点

私链：私链的共识算法即区块链这个概念还没普及时的传统分布式系统里的共识算法，比如 zookeeper 的 zab 协议，就是类 paxos 算法的一种。私链的适用环境一般是不考虑集群中存在作恶节点，只考虑因为系统或者网络原因导致的故障节点。

联盟链：联盟链中，经典的代表项目是 Hyperledger 组织下的 Fabric 项目， Fabric0.6 版本使用的就是 pbft 算法。联盟链的适用环境除了需要考虑集群中存在故障节点，还需要考虑集群中存在作恶节点。对于联盟链，每个新加入的节点都是需要验证和审核的。

公链：公链不仅需要考虑网络中存在故障节点，还需要考虑作恶节点，这一点和联盟链是类似的。和联盟链最大的区别就是，公链中的节点可以很自由的加入或者退出，不需要严格的验证和审核。

在公有链中用的最多的是pow算法和pos算法，这些算法都是参与者的利益直接相关，通过利益来制约节点诚实的工作，解决分布式系统中的拜占庭问题。拜占庭容错算法是一种状态机副本复制算法，通过节点间的多轮消息传递，网络内的所有诚实节点就可以达成一致的共识。

使用拜占庭容错算法不需要发行加密货币，但是只能用于私有链或者联盟链，需要对节点的加入进行权限控制；不能用于公有链，因为公有链中所有节点都可以随意加入退出，无法抵挡女巫攻击（sybil attack）

raft 算法包含三种角色，分别是：跟随者（ follower ），候选人（candidate ）和领导者（ leader ）。集群中的一个节点在某一时刻只能是这三种状态的其中一种，这三种角色是可以随着时间和条件的变化而互相转换的。

raft 算法主要有两个过程：一个过程是领导者选举，另一个过程是日志复制，其中日志复制过程会分记录日志和提交数据两个阶段。raft 算法支持最大的容错故障节点是（N-1）/2，其中 N 为 集群中总的节点数量。

国外有一个动画介绍raft算法介绍的很透彻，链接地址为： 。这个动画主要包含三部分内容，第一部分介绍简单版的领导者选举和日志复制的过程，第二部分内容介绍详细版的领导者选举和日志复制的过程，第三部分内容介绍的是如果遇到网络分区（脑裂），raft 算法是如何恢复网络一致的。

pbft 算法的提出主要是为了解决拜占庭将军问题

要让这个问题有解，有一个 十分重要的前提 ，那就是 信道必须是可靠的 。如果信道不能保证可靠，那么拜占庭问题无解。关于信道可靠问题，会引出两军问题。两军问题的结论是，在一个不可靠的通信链路上试图通过通信以达成一致是基本不可能或者十分困难的。

拜占庭将军问题最早是由 Leslie Lamport 与另外两人在 1982 年发表的论文《The Byzantine Generals Problem 》提出的， 他证明了在将军总数大于 3f ，背叛者为f 或者更少时，忠诚的将军可以达成命令上的一致，即 3f+1=n 。算法复杂度为 o（n^(f+1)) 。而 Miguel Castro (卡斯特罗)和 Barbara Liskov （利斯科夫）在1999年发表的论文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 算法，该算法容错数量也满足 3f+1=n ，算法复杂度为 o（n^2）。

首先我们先来思考一个问题，为什么 pbft 算法的最大容错节点数量是（n-1）/3，而 raft 算法的最大容错节点数量是（n-1）/2 ？

对于raft算法，raft算法的的容错只支持容错故障节点，不支持容错作恶节点。什么是故障节点呢？就是节点因为系统繁忙、宕机或者网络问题等其它异常情况导致的无响应，出现这种情况的节点就是故障节点。那什么是作恶节点呢？作恶节点除了可以故意对集群的其它节点的请求无响应之外，还可以故意发送错误的数据，或者给不同的其它节点发送不同的数据，使整个集群的节点最终无法达成共识，这种节点就是作恶节点。

raft 算法只支持容错故障节点，假设集群总节点数为n，故障节点为 f ，根据小数服从多数的原则，集群里正常节点只需要比 f 个节点再多一个节点，即 f+1 个节点，正确节点的数量就会比故障节点数量多，那么集群就能达成共识。因此 raft 算法支持的最大容错节点数量是（n-1）/2。

对于 pbft 算法，因为 pbft 算法的除了需要支持容错故障节点之外，还需要支持容错作恶节点。假设集群节点数为 N，有问题的节点为 f。有问题的节点中，可以既是故障节点，也可以是作恶节点，或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况：

第一种情况，f 个有问题节点既是故障节点，又是作恶节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是 （n-1）/2。

第二种情况，故障节点和作恶节点都是不同的节点。那么就会有 f 个问题节点和 f 个故障节点，当发现节点是问题节点后，会被集群排除在外，剩下 f 个故障节点，那么根据小数服从多数的原则，集群里正常节点只需要比f个节点再多一个节点，即 f+1 个节点，确节点的数量就会比故障节点数量多，那么集群就能达成共识。所以，所有类型的节点数量加起来就是 f+1 个正确节点，f个故障节点和f个问题节点，即 3f+1=n。

结合上述两种情况，因此 pbft 算法支持的最大容错节点数量是（n-1）/3

pbft 算法的基本流程主要有以下四步：

客户端发送请求给主节点

主节点广播请求给其它节点，节点执行 pbft 算法的三阶段共识流程。

节点处理完三阶段流程后，返回消息给客户端。

客户端收到来自 f+1 个节点的相同消息后，代表共识已经正确完成。

为什么收到 f+1 个节点的相同消息后就代表共识已经正确完成？从上一小节的推导里可知，无论是最好的情况还是最坏的情况，如果客户端收到 f+1 个节点的相同消息，那么就代表有足够多的正确节点已全部达成共识并处理完毕了。

3.算法核心三阶段流程

算法的核心三个阶段分别是 pre-prepare 阶段（预准备阶段），prepare 阶段（准备阶段）， commit 阶段（提交阶段）

流程的对比上，对于 leader 选举这块， raft 算法本质是谁快谁当选，而 pbft 算法是按编号依次轮流做主节点。对于共识过程和重选 leader 机制这块，为了更形象的描述这两个算法，接下来会把 raft 和 pbft 的共识过程比喻成一个团队是如何执行命令的过程，从这个角度去理解 raft 算法和 pbft 的区别。

一个团队一定会有一个老大和普通成员。对于 raft 算法，共识过程就是：只要老大还没挂，老大说什么，我们（团队普通成员）就做什么，坚决执行。那什么时候重新老大呢？只有当老大挂了才重选老大，不然生是老大的人，死是老大的鬼。

对于 pbft 算法，共识过程就是：老大向我发送命令时，当我认为老大的命令是有问题时，我会拒绝执行。就算我认为老大的命令是对的，我还会问下团队的其它成员老大的命令是否是对的，只有大多数人 （2f+1） 都认为老大的命令是对的时候，我才会去执行命令。那什么时候重选老大呢？老大挂了当然要重选，如果大多数人都认为老大不称职或者有问题时，我们也会重新选择老大。

四、结语

raft 算法和 pbft 算法是私链和联盟链中经典的共识算法，本文主要介绍了 raft 和 pbft 算法的流程和区别。 raft 和 pbft 算法有两点根本区别：

raft 算法从节点不会拒绝主节点的请求，而 pbft 算法从节点在某些情况下会拒绝主节点的请求 ;

raft 算法只能容错故障节点，并且最大容错节点数为 （n-1）/2 ，而 pbft 算法能容错故障节点和作恶节点，最大容错节点数为 （n-1）/3 。

pbft算法是通过投票来达成共识，可以很好的解决包括分叉等问题的同时提升效率。但仅仅比较适合于联盟链私有链，因为两两节点之间通信量是O(n^2)（通过优化可以减少通信量），一般来说不能应用于超过100个节点。

pbft有解的前提是 信道必须是可靠的 ，存在的问题是 可扩展性（scalability）差

部分来自：

区块链在设计上就是为了BFT

Quorum介绍（二）：Quorum共识

我们知道，公共区块链是一个开放的社区，任何人都能够成为一个节点加入网络，在网络中计算，提交交易到链上等，因此公链是没有信任基础的，所以公链的共识第一要义就是证明交易的合法性和真实性，防止恶意成员的捣乱，效率不是第一要义。

与公链的环境不同，有准入门槛的企业链或者联盟链链上的所有成员在加入时实际上是已经获得了某些认可和许可的，因此企业链/联盟链上的成员是有一定信任基础的。在企业级链上我们没有必要使用POW或者POS这种浪费算力或者低效的交易共识。

Quorum提供了多种共识供用户采用：

在讲Raft前，有必要提一下Paxos算法，Paxos算法是Leslie Lamport于1990年提出的基于消息传递的一致性算法。然而，由于算法难以理解，刚开始并没有得到很多人的重视。其后，作者在八年后，也就是1998年在ACM上正式发表，然而由于算法难以理解还是没有得到重视。而作者之后用更容易接受的方法重新发表了一篇论文《Paxos Made Simple》。

可见，Paxos算法是有多难理解，即便现在放到很多高校，依然很多学生、教授都反馈Paxos算法难以理解。同时，Paxos算法在实际应用实现的时候也是比较困难的。这也是为什么会有后来Raft算法的提出。

Raft是实现分布式共识的一种算法，主要用来管理日志复制的一致性。它和Paxos的功能是一样，但是相比于Paxos，Raft算法更容易理解、也更容易应用到实际的系统当中。而Raft算法也是联盟链采用比较多的共识算法。

Raft一共有三种角色状态：

每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout：

在分布式系统中，“时间同步”是一个很大的难题，因为每个机器可能由于所处的地理位置、机器环境等因素会不同程度造成时钟不一致，但是为了识别“过期信息”，时间信息必不可少。

Raft算法中就采用任期（Term）的概念，将时间切分为一个个的Term（同时每个节点自身也会本地维护currentTerm），可以认为是逻辑上的时间，如下图。

每一任期的开始都是一次领导人选举，一个或多个候选人（Candidate）会尝试成为领导（Leader）。如果一个人赢得选举，就会在该任期（Term）内剩余的时间担任领导人。在某些情况下，选票可能会被评分，有可能没有选出领导人（如t3），那么，将会开始另一任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最少要有一个领导人。

特殊情况的处理

在以太坊中节点本身并没有角色，因此在使用Raft共识时，我们称leader节点为挖矿节点：

Raft共识机制本身保证了同一时间点最多只有一个leader，因此用在以太坊模型下也只会有一个出块者，避免了同时出块或者算力浪费的情况。

在单笔交易(transaction)层级Quorum依然沿用了Ethereum的p2p传输机制，只有在块(block)层级才会使用Raft的传输机制。

其中需要注意到一点，在以太坊中一个节点收到块以后就会立刻记账，而在Quorum模型中，一个块的记录必须遵从Raft协议，每个节点从leader处收到块以后必须报告给leader确认收到以后，再由leader通知各个节点进行数据提交（记录）

在Quorum模型中新块的信息是很有可能和已有块的header信息不符的，最容易发生这种情况的就是选举人更替(挖矿节点更替)，具体描述如下：

假设有两个节点，node1和node2，node1是现有的leader，现有链的最新区块是0xbeda，它的父区块是0xacaa

对块“Extends”或者“No-op”的标记是在更上层完成的，并不由raft本身log记录机制实现。因为在raft内部，信息并不分为有效或无效，只有在区块链层面才会有有效区块和无效区块的含义。

需要注意的是，Quorum的这种记账机制和本身Ethereum的LVC（最长链机制）是完全不一样的

Quorum的出块频率默认是50ms一个块，可以通过 --raftblocktime 参数进行设置

投机性出块并不是以太坊Raft共识严格必须的核心机制之一，但是是提高出块效率的有效方式。

一个块从产生到实际被记录账本，走完整个raft流程实际上是需要耗费一定时间的。如果我们在上一个块被计入账本之后才开始产生下一个块，那么一笔交易想要成功被记录需要耗费较多的时间。

而在投机性(speculative minting)出块中，我们允许一个新块在它的父块被记录之前就产生。依次类推，在一段时间内，实际上会产生“投机链（speculative chain）”，在祖先块没有被记录进账本之前，一个一个新块已经依据先后关系组成了一条临时链片段，等待被记录。

对于已经被记录进投机块的交易，我们会在交易池中标记为“proposed transaction”

在之前我们说过，raft机制中是存在两个挖矿节点比赛出块和记账的可能的，因此，一条 speculative chain 中间的某一个块很有可能不会被记录到账本中。在这种情况下我们也会把交易池中的交易状态修改回来。( InvalidRaftOrdering event)

目前，Quorum并没有对speculative chain的长度做限制，但在它的未来规划中有讲这一点作为一个性能优化项加入开发进程，最后能够让一个挖矿节点即使在raft共识层没有连接上，它也可以离线一直出块，产生自己的speculative chain。

一条speculative chain有以下几个部分构成：

在块传输上我们使用etcd Raft默认的http传输，当然使用Ethereum的p2p传输也是可以的，但是Quorum团队在测试阶段发现，高负载的状态下，ETH p2p的性能没有raft p2p性能好。

Quorum使用50400端口作为Raft 传输层的默认监听端口，也可以通过 --raftport 参数自行设置。

一个集群默认的最大节点个数是25，可以通过 --maxpeers N 来设置，N是你的最大节点个数。

Quorum的IBFT其实就是PBFT，只不过摩根大通把它自己实现的PBFT叫做IBFT，所以IBFT的基本原理与PBFT是一样的，所不同的是,IBFT中把出块和共识的三阶段结合在了一起。

Istanbul BFT修改自PBFT算法，包括三个阶段： PRE-PREPARE 、 PREPARE 以及 COMMIT 。在 N 个节点的网络中，这个算法可以最多容忍 F 个出错节点，其中 N=3F+1 。

Istanbul BFT算法中的区块是确定的，意味着链没有分叉并且合法的区块一定是在链中。为了防止一个恶意节点生成不同的链，在把区块插入进链 之前 ，每一个validator必须把 2F + 1 个 COMMIT 签名放进区块头的 extraData 字段。因此，区块是可以自我验证的（因为有签名）并且轻客户端也支持。

然而动态的 extraData 也会造成区块的hash计算问题。因为一个区块可以被不同的validator验证，所以会有不同的签名，所以同一个区块会有不同的hash。解决的方案是，计算区块hash的时候把 COMMIT 签名排除在外。因此我们任然可以在保证block hash一致性的同时进行共识验证。

由于Ethereum POA共识在网上已经有大量介绍，笔者这里就不多做详细介绍，只对重要特点和POA的工作流程做大致梳理和介绍

深入了解区块链的共识机制及算法原理

所谓“共识机制”，是通过特殊节点的投票，在很短的时间内完成对交易的验证和确认；对一笔交易，如果利益不相干的若干个节点能够达成共识，我们就可以认为全网对此也能够达成共识。再通俗一点来讲，如果中国一名微博大V、美国一名虚拟币玩家、一名非洲留学生和一名欧洲旅行者互不相识，但他们都一致认为你是个好人，那么基本上就可以断定你这人还不坏。

要想整个区块链网络节点维持一份相同的数据，同时保证每个参与者的公平性，整个体系的所有参与者必须要有统一的协议，也就是我们这里要将的共识算法。比特币所有的节点都遵循统一的协议规范。协议规范（共识算法）由相关的共识规则组成，这些规则可以分为两个大的核心：工作量证明与最长链机制。所有规则（共识）的最终体现就是比特币的最长链。共识算法的目的就是保证比特币不停地在最长链条上运转，从而保证整个记账系统的一致性和可靠性。

区块链中的用户进行交易时不需要考虑对方的信用、不需要信任对方，也无需一个可信的中介机构或中央机构，只需要依据区块链协议即可实现交易。这种不需要可信第三方中介就可以顺利交易的前提是区块链的共识机制，即在互不了解、信任的市场环境中，参与交易的各节点出于对自身利益考虑，没有任何违规作弊的动机、行为，因此各节点会主动自觉遵守预先设定的规则，来判断每一笔交易的真实性和可靠性，并将检验通过的记录写入到区块链中。各节点的利益各不相同，逻辑上将它们没有合谋欺骗作弊的动机产生，而当网络中有的节点拥有公共信誉时，这一点尤为明显。区块链技术运用基于数学原理的共识算法，在节点之间建立“信任”网络，利用技术手段从而实现一种创新式的信用网络。

目前区款连行业内主流的共识算法机制包含：工作量证明机制、权益证明机制、股份授权证明机制和Pool验证池这四大类。

工作量证明机制即对于工作量的证明，是生成要加入到区块链中的一笔新的交易信息(即新区块)时必须满足的要求。在基于工作量证明机制构建的区块链网络中，节点通过计算随机哈希散列的数值解争夺记账权，求得正确的数值解以生成区块的能力是节点算力的具体表现。工作量证明机制具有完全去中心化的优点，在以工作量证明机制为共识的区块链中，节点可以自由进出。大家所熟知的比特币网络就应用工作量证明机制来生产新的货币。然而，由于工作量证明机制在比特币网络中的应用已经吸引了全球计算机大部分的算力，其他想尝试使用该机制的区块链应用很难获得同样规模的算力来维持自身的安全。同时，基于工作量证明机制的挖矿行为还造成了大量的资源浪费，达成共识所需要的周期也较长，因此该机制并不适合商业应用。

2012年，化名Sunny King的网友推出了Peercoin，该加密电子货币采用工作量证明机制发行新币，采用权益证明机制维护网络安全，这是权益证明机制在加密电子货币中的首次应用。与要求证明人执行一定量的计算工作不同，权益证明要求证明人提供一定数量加密货币的所有权即可。权益证明机制的运作方式是，当创造一个新区块时，矿工需要创建一个“币权”交易，交易会按照预先设定的比例把一些币发送给矿工本身。权益证明机制根据每个节点拥有代币的比例和时间，依据算法等比例地降低节点的挖矿难度，从而加快了寻找随机数的速度。这种共识机制可以缩短达成共识所需的时间，但本质上仍然需要网络中的节点进行挖矿运算。因此，PoS机制并没有从根本上解决PoW机制难以应用于商业领域的问题。

股份授权证明机制是一种新的保障网络安全的共识机制。它在尝试解决传统的PoW机制和PoS机制问题的同时，还能通过实施科技式的民主抵消中心化所带来的负面效应。

股份授权证明机制与董事会投票类似，该机制拥有一个内置的实时股权人投票系统，就像系统随时都在召开一个永不散场的股东大会，所有股东都在这里投票决定公司决策。基于DPoS机制建立的区块链的去中心化依赖于一定数量的代表，而非全体用户。在这样的区块链中，全体节点投票选举出一定数量的节点代表，由他们来代理全体节点确认区块、维持系统有序运行。同时，区块链中的全体节点具有随时罢免和任命代表的权力。如果必要，全体节点可以通过投票让现任节点代表失去代表资格，重新选举新的代表，实现实时的民主。

股份授权证明机制可以大大缩小参与验证和记账节点的数量，从而达到秒级的共识验证。然而，该共识机制仍然不能完美解决区块链在商业中的应用问题，因为该共识机制无法摆脱对于代币的依赖，而在很多商业应用中并不需要代币的存在。

Pool验证池基于传统的分布式一致性技术建立，并辅之以数据验证机制，是目前区块链中广泛使用的一种共识机制。

Pool验证池不需要依赖代币就可以工作，在成熟的分布式一致性算法(Pasox、Raft)基础之上，可以实现秒级共识验证，更适合有多方参与的多中心商业模式。不过，Pool验证池也存在一些不足，例如该共识机制能够实现的分布式程度不如PoW机制等

这里主要讲解区块链工作量证明机制的一些算法原理以及比特币网络是如何证明自己的工作量的，希望大家能够对共识算法有一个基本的认识。

工作量证明系统的主要特征是客户端要做一定难度的工作来得到一个结果，验证方则很容易通过结果来检查客户端是不是做了相应的工作。这种方案的一个核心特征是不对称性：工作对于请求方是适中中的，对于验证方是易于验证的。它与验证码不同，验证码是易于被人类解决而不是易于被计算机解决。

下图所示的为工作量证明流程。

举个例子，给个一个基本的字符创“hello，world！”，我们给出的工作量要求是，可以在这个字符创后面添加一个叫做nonce（随机数）的整数值，对变更后（添加nonce）的字符创进行SHA-256运算，如果得到的结果（一十六进制的形式表示）以“0000”开头的，则验证通过。为了达到这个工作量证明的目标，需要不停地递增nonce值，对得到的字符创进行SHA-256哈希运算。按照这个规则，需要经过4251次运算，才能找到前导为4个0的哈希散列。

通过这个示例我们对工作量证明机制有了一个初步的理解。有人或许认为如果工作量证明只是这样一个过程，那是不是只要记住nonce为4521使计算能通过验证就行了，当然不是了，这只是一个例子。

下面我们将输入简单的变更为”Hello,World!+整数值”，整数值取1~1000，也就是说将输入变成一个1~1000的数组：Hello,World!1；Hello,World!2；...；Hello,World!1000。然后对数组中的每一个输入依次进行上面的工作量证明—找到前导为4个0的哈希散列。

由于哈希值伪随机的特性，根据概率论的相关知识容易计算出，预计要进行2的16次方次数的尝试，才能得到前导为4个0的哈希散列。而统计一下刚刚进行的1000次计算的实际结果会发现，进行计算的平均次数为66958次，十分接近2的16次方（65536）。在这个例子中，数学期望的计算次数实际就是要求的“工作量”，重复进行多次的工作量证明会是一个符合统计学规律的概率事件。

统计输入的字符创与得到对应目标结果实际使用的计算次数如下：

对于比特币网络中的任何节点，如果想生成一个新的区块加入到区块链中，则必须解决出比特币网络出的这道谜题。这道题的关键要素是工作量证明函数、区块及难度值。工作量证明函数是这道题的计算方法，区块是这道题的输入数据，难度值决定了解这道题的所需要的计算量。

比特币网络中使用的工作量证明函数正是上文提及的SHA-256。区块其实就是在工作量证明环节产生的。旷工通过不停地构造区块数据，检验每次计算出的结果是否满足要求的工作量，从而判断该区块是不是符合网络难度。区块头即比特币工作量证明函数的输入数据。

难度值是矿工们挖掘的重要参考指标，它决定了旷工需要经过多少次哈希运算才能产生一个合法的区块。比特币网络大约每10分钟生成一个区块，如果在不同的全网算力条件下，新区块的产生基本都保持这个速度，难度值必须根据全网算力的变化进行调整。总的原则即为无论挖矿能力如何，使得网络始终保持10分钟产生一个新区块。

难度值的调整是在每个完整节点中独立自动发生的。每隔2016个区块，所有节点都会按照统一的格式自动调整难度值，这个公式是由最新产生的2016个区块的花费时长与期望时长（按每10分钟产生一个取款，则期望时长为20160分钟）比较得出来的，根据实际时长一期望时长的比值进行调整。也就是说，如果区块产生的速度比10分钟快，则增加难度值；反正，则降低难度值。用公式来表达如下：

新难度值=旧难度值*（20160分钟/过去2016个区块花费时长）。

工作量证明需要有一个目标值。比特币工作量证明的目标值（Target）的计算公式如下：

目标值=最大目标值/难度值，其中最大目标值为一个恒定值0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

目标值的大小与难度值成反比，比特币工作量证明的达成就是矿中计算出来的区块哈希值必须小于目标值。

我们也可以将比特币工作量的过程简单的理解成，通过不停变更区块头（即尝试不同nonce值）并将其作为输入，进行SHA-256哈希运算，找出一个有特定格式哈希值的过程（即要求有一定数量的前导0），而要求的前导0个数越多，难度越大。

可以把比特币将这道工作量证明谜题的步骤大致归纳如下：

该过程可以用下图表示：

比特币的工作量证明，就是我们俗称“挖矿”所做的主要工作。理解工作量证明机制，将为我们进一步理解比特币区块链的共识机制奠定基础。

raft算法是什么呢?

raft是一种更为简单方便易于理解的分布式算法，主要解决了分布式中的一致性问题，相比传统的Paxos算法，Raft将大量的计算问题分解成为了一些简单的相对独立的子问题，相比于传统的一致性算法Paxos，Raft有一些自己的独特的特性，比如增加了强领导性，优化了领导的选举过程，在成员发生变化之后依然能够很好的进行工作。

以下是文章部分内容的翻译，来自Github，由于字数限制只摘取了算法的核心部分，建议阅读原文，寻找一种易于理解的一致性算法。

raft的内容

一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。正因为如此，一致性算法在构建可信赖的大规模软件系统中扮演着重要的角色，在过去的10年里，Paxos算法统治着一致性算法这一领域，绝大多数的实现都是基于Paxos或者受其影响。

同时Paxos也成为了教学领域里讲解一致性问题时的示例，但是不幸的是，尽管有很多工作都在尝试降低它的复杂性，但是Paxos算法依然十分难以理解，并且，Paxos自身的算法结构需要进行大幅的修改才能够应用到实际的系统中，这些都导致了工业界和学术界都对Paxos算法感到十分头疼。

raft理解

这是一篇学习raft论文的总结，主要是对看论文过程中难以理解的几个问题的记录。系统性的讲解还是得看raft论文，论文原文是最好的材料。

引用论文中的第一句话--“Raft 是一种为了管理复制日志的一致性算法”。从两个角度来理解raft算法，第一部分是raft的基本规则，第二部分是raft的异常情况处理。下面放一张raft论文中的经典图来了解一下raft是怎么在一个系统中工作的。下图中一致性模块Consensus Module执行的就是raft算法，它保证拷贝到所有server上的每一条日志是一致的。State Machine状态机对应我们的业务逻辑，日志作为状态机的输入，输入一致就能保证输出是一致的。

基本规则

raft的工作模式是一个Leader和多个Follower模式，即我们通常说的领导者-追随者模式。这种模式下需要解决的第一个问题就是Leader的选举问题。其次是如何把日志从Leader复制到所有Follower上去。这里先不关心安全和可靠性，只理解raft运行起来基本规则。raft中的server有三种状态，除了已经提到的Leader和Follower状态外，还有Candidate状态，即竞选者状态。下面是这三种状态的转化过程。

1、Leader的选举过程

raft初始状态时所有server都处于Follower状态，并且随机睡眠一段时间，这个时间在0~1000ms之间。最先醒来的server A进入Candidate状态，Candidate状态的server A有权利发起投票，向其它所有server发出requst_vote请求，请求其它server给它投票成为Leader。当其它server收到request_vote请求后，将自己仅有的一票投给server A，同时继续保持Follower状态并重置选举计时器。当server A收到大多数（超过一半以上）server的投票后，就进入Leader状态，成为系统中仅有的Leader。raft系统中只有Leader才有权利接收并处理client请求，并向其它server发出添加日志请求来提交日志。

2、日志复制过程

Leader选举出来后，就可以开始处理客户端请求。Leader收到客户端请求后，将请求内容作为一条log日志添加到自己的log记录中，并向其它server发送append_entries(添加日志)请求。其它server收到append_entries请求后，判断该append请求满足接收条件（接收条件在后面安全保证问题3给出），如果满足条件就将其添加到本地的log中，并给Leader发送添加成功的response。Leader在收到大多数server添加成功的response后，就将该条log正式提交。提交后的log日志就意味着已经被raft系统接受，并能应用到状态机中了。

Leader具有绝对的日志复制权力，其它server上存在日志不全或者与Leader日志不一致的情况时，一切都以Leader上的日志为主，最终所有server上的日志都会复制成与Leader一致的状态。

以上就是raft允许的基本规则，如果不出现任何异常情况，那么只要上面两个过程就能使raft运行起来了。但是现实的系统不可能这么一帆风顺，总是有很多异常情况需要考虑。raft的复杂性就来源于对这些异常情况的考虑，下面一小节就以问答的方式来总结raft是怎么保证安全性的。

安全性保证

1、Leader选举过程中，如果有两个serverA和B同时醒来并发出request_vote请求怎么办？

由于在一次选举过程中，一个server最多只能投一票，这就保证了serverA和B不可能同时得到大多数（一半以上）的投票。如果A或者B中其一幸运地得到了大多数投票，就能顺利地成为Leader，raft系统正常运行下去。但是A和B可能刚好都得到一半的投票，两者都成为不了Leader。这时A和B继续保持Candidate状态，并且随机睡眠一段时间，等待进入到下一个选举周期。由于所有server都是随机选择睡眠时间，所以连续出现多个server竞选的概率很低。

2、Leader挂了后，如何选举出新的Leader？

Leader正常运作时，会周期性地发出append_entries请求。这个周期性的append_entries除了可以更新其它Follower的log信息，另外一个重要功能就是起到心跳作用。Follower收到append_entries后，就知道Leader还活着。如果Follower经过一个预定的时间(一般设为2000ms左右)都没有收到Leader的心跳，就认为Leader挂了。于是转入Candidate状态，开始发起投票竞选新的Leader。每个新的Leader产生后就是一个新的任期，每个任期都对应一个唯一的任期号term。这个term是单调递增的，用来唯一标识一个Leader的任期。投票开始时，Candidate将自己的term加1，并在request_vote中带上term；Follower只会接受任期号term比自己大的request_vote请求，并为之投票。这条规则保证了只有最新的Candidate才有可能成为Leader。

3、Follower在收到一条append_entries添加日志请求后，是否立即保存并将其应用到状态机中去？如果不是立即应用，那么由什么来决定该条日志生效的时间？

Follower在收到一条append_entries后，首先会检查这条append_entries的来源信息是否与本地保存的leader信息符合，包括leaderId和任期号term。检查合法后就将日志保存到本地log中，并给Leader回复添加log成功，但是不会立即将其应用到本地状态机。Leader收到大部分Follower添加log成功的回复后，就正式将这条日志commit提交。Leader在随后发出的心跳append_entires中会带上已经提交日志索引。Follower收到Leader发出的心跳append_entries后，就可以确认刚才的log已经被commit(提交)了，这个时候Follower才会把日志应用到本地状态机。下表即是append_entries请求的内容，其中leaderCommit即是Leader已经确认提交的最大日志索引。Follower在收到Leader发出的append_entries后即可以通过leaderCommit字段决定哪些日志可以应用到状态机。

4、假设有一个server A宕机了很长一段时间，它的日志已经落后很多。如果A重新上线，而且此时现有Leader挂掉，server A刚好竞选成为了Leader。按照日志都是由Leader复制给其它server的原则，server A会把其它Follower已经提交的日志给抹掉，而这违反了raft状态机安全特性，raft怎么解决这种异常情况？

所谓的状态机安全特性即是“如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志”。如果server在竞选Leader的过程中不加任何限制的话，携带旧日志的server也有可能竞选成为Leader，就必然存在覆盖之前Leader已经提交的日志可能性，从而违反状态机安全特性。raft的解决办法很简单，就是只有具有最新日志的server的才有资格去竞选当上Leader，具体是怎么做到的呢？首先任何server都还是有资格去发起request_vote请求去拉取投票的，request_vote中会带上server的日志信息，这些信息标明了server日志的新旧程度，如下表所示。

其它server收到request_vote后，判断如果lastLogTerm比自己的term大，那么就可以给它投票；lastLogTerm比自己的term小，就不给它投票。如果相等的话就比较lastLogIndex，lastLogIndex大的话日志就比较新，就给它投票。下图是raft日志格式，每条日志中不仅保存了日志内容，还保存了发送这条日志的Leader的任期号term。为什么要在日志里保存任期号term，由于任期号是全局单调递增且唯一的，所以根据任期号可以判断一条日志的新旧程度，为选举出具有最新日志的Leader提供依据。

5、存在如下图一种异常情况，server S5在时序(d)中覆盖了server S1在时序(c)中提交的index为2的日志，方框中的数字是日志的term。这违反了状态机的安全特性--“如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志”，raft要如何解决这个问题？

出现这个问题的根本原因是S1在时序(c) 的任期4内提交了一个之前任期2的log，这样S1提交的日志中最大的term仅仅是2，那么一些日志比较旧的server，比如S5(它最日志的term为 3)，就有机会成为leader，并覆盖S1提交的日志。解决办法就是S1在时序(c)的任期term4提交term2的旧日志时，旧日志必须附带在当前term 4的日志下一起提交。这样就把S1日志的最大term提高到了4，让那些日志比较旧的S5没有机会竞选成为Leader，也就不会用旧的日志覆盖已经提交的日志了。

简单点说，Leader如果要提交之前term的旧日志，那么必须要提交一条当前term的日志。提交一条当前term的日志相当于为那些旧的日志加了一把安全锁，让那些日志比较旧的server失去得到Leader的机会，从而不会修改那些之前term的旧日志。

怎么具体实现旧日志必须附带在当前term的日志下一起提交呢？在问题3中有给出append_entries请求中的字段，其中有两个字段preLogIndex和preLogTerm的作用没有提到，这两个字段就是为了保证Leader和Followers的历史日志完全一致而存在的。当Leader在提交一条新日志的时候，会带上新日志前一条日志的index和term，即preLogIndex和preLogTerm。Follower收到append_entries后，会检查preLogIndex和preLogTerm是否和自己当前最新那条日志的index和term对得上，如果对不上就会给Leader返回自己当前日志的index和term。Leader收到后就将Follower返回的index对应的日志以及对应的preLogIndex和preLogTerm发送给Follower。这个过程一直重复，直到Leader和Follower找到了第一个index和term能对得上的日志，然后Leader从这条日志开始拷贝给Follower。回答段首的问题，Leader在提交一条最新的日志时，Follow会检验之前的日志是否与Leader保持了一致，如果不一致会一直同步到与Leader一致后才添加最新的日志，这个机制就保证了Leader在提交最新日志时，也提交了之前旧的日志。

6、向raft系统中添加新机器时，由于配置信息不可能在各个系统上同时达到同步状态，总会有某些server先得到新机器的信息，有些server后得到新机器的信息。比如下图raft系统中新增加了server4和server5这两台机器。只有server3率先感知到了这两台机器的添加。这个时候如果进行选举，就有可能出现两个Leader选举成功。因为server3认为有3台server给它投了票，它就是Leader，而server1认为只要有2台server给它投票就是Leader了。raft怎么解决这个问题呢？

产生这个问题的根本原因是，raft系统中有一部分机器使用了旧的配置，如server1和server2，有一部分使用新的配置，如server3。解决这个问题的方法是添加一个中间配置(Cold, Cnew)，这个中间配置的内容是旧的配置表Cold和新的配置Cnew。还是拿上图中的例子来说明，这个时候server3收到添加机器的消息后，不是直接使用新的配置Cnew，而是使用(Cold, Cnew)来做决策。比如说server3在竞选Leader的时候，不仅需要得到Cold中的大部分投票，还要得到Cnew中的大部分投票才能成为Leader。这样就保证了server1和server2在使用Cold配置的情况下，还是只可能产生一个Leader。当所有server都获得了添加机器的消息后，再统一切换到Cnew。raft实现中，将Cold，(Cold,Cnew)以及Cnew都当成一条普通的日志。配置更改信息发送Leader后，由Leader先添加一条 (Cold, Cnew)日志，并同步给其它Follower。当这条日志(Cold, Cnew)提交后，再添加一条Cnew日志同步给其它Follower，通过Cnew日志将所有Follower的配置切换到最新。

有的raft实现采用了一种更加简单粗暴的方法来解决成员变化的问题。这个办法就是每次只更新一台机器的配置变化，收到配置变化的机器立马采用新的配置。这样的做法为什么能确保安全性呢？下面举例说明。比如说系统中原来有5台机器A,B,C,D,E，现在新加了一台机器F，A,B,C三台机器没有感知到F的加入，只有D,E两台机器感知到了F的加入。现在就有了两个旧机器集合X｛A, B, C, D, E}和新机器集合Y｛F｝。假设A和D同时进入Candidate状态去竞选Leader，其中D要想竞选成功，必须得有一半以上机器投票，即6/2+1=4台机器，就算Y集合中的F机器给D投了票，还得至少在集合X中得到3票；而A要想竞选成功，也必须得到5/2+1 = 3张票，由于A只知道集合X的存在，所以也必须从集合X中获得至少3票。而A和D不可能同时从集合X同时获得3票，所以A和D不可能同时竞选成为Leader，从而保证了安全性。可以使用更加形式化的数学公式来证明一次添加一台机器配置不会导致产生两个Leader，证明过程就暂时省略了。

raft论文中文翻译：

raft论文英文原址：

raft使用C语言实现：

raft成员变更过程分析：

以上内容为新媒号(sinv.com.cn)为大家提供！新媒号，坚持更新大家所需的区块链知识。希望您喜欢！