2021-08-06 15:52

共识科普 | 什么是Quorum机制与PBFT

实用性拜占庭容错算法(Practical Byzantine Fault Tolerance,PBFT),是一种在信道可靠的情况下解决拜占庭将军问题的实用方法。拜占庭将军问题最早由Leslie Lamport等人在1982年发表的论文[1]提出,论文中证明了在将军总数n大于3f,背叛者为f或者更少时,忠诚的将军可以达成命令上的一致,即3f+1<=n,算法复杂度为O(n^(f+1))。随后Miguel Castro和Barbara Liskov在1999年发表的论文[2]中首次提出PBFT算法,该算法容错数量也满足3f+1<=n,算法复杂度降低到了O(n^2)。

如果对于PBFT共识算法有所了解,对节点总数n与容错上限f的关系可能会比较熟悉:在系统内最多存在f个错误节点的前提下,系统内总节点数量n应该满足n>3f,在推进共识过程中则需要收集一定数目的投票,才能完成认证过程。在本节当中,我们将首先讨论这些数值间关系该如何得出。

--Quorum机制--

在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是在同一时刻,一个数据对象的多份拷贝只能用于读或者写。为了保持数据冗余与一致性,需要对应的投票机制进行维持,这就是Quorum机制。区块链作为一种分布式系统,同样也需要该机制进行集群维护。

为了更好地理解Quorum机制,我们先来了解一种与之类似,但是更加极端的投票机制——WARO机制(Write All Read One)。使用WARO机制维护节点总数为n的集群时,节点执行写操作的“票数”应当为n,而读操作时的“票数”可以设置为1。也就是说,在执行写入时,需要保证全部节点完成写入操作才可视该操作为完成,否则会写入失败;相应地,在执行读操作时,只需要读取一个节点的状态,就可以对该系统状态进行确认。可以看到,在使用WARO机制的集群中,写操作的执行非常脆弱:只要有一个节点执行写入失败,那么这次操作就无法完成。不过,虽然牺牲了写操作健壮性,但是,在WARO机制下,对于该集群执行读操作会非常容易。

Quorum机制[3]就是对读写操作的折衷考虑,对于同一份数据对象的每一份拷贝,不会被超过两个访问对象读写,并且权衡读写时的集合大小要求。在一个分布式集群当中,每一份数据拷贝对象都被赋予了一票。假设:

  • 系统中有V票,这就意味着一个数据对象有V份冗余拷贝;
  • 对于每一个读操作,获得的票数必须不小于最小读票数R(read quorum)才可以成功读取;
  • 对于每个写操作,获得的票数必须不小于最小写票数W(write quorum)才可以成功写入。

此时,为了维持集群一致性,V、R、W应满足不等关系,R+W>V且W>V/2。其中,R+W>V保证了一个数据不会被同时读或写。当一个写操作请求传入,它必须要获得W票,而剩下的数量是V-W不足R,因此不会再处理读请求。同理,当读请求已经获得了R票,写请求就无法被处理。W>V/2,保证了数据的串行修改,也就是说,一份数据的冗余拷贝不可能同时被两个写请求修改。

对于集群中的共识节点,在推进共识算法时,参与共识的节点会同时对集群进行读写操作。为了平衡读写操作对于集合大小的要求,每个节点的R与W取同样大小,记为Q。当集群中总共存在n个节点,并且其中最多出现f个错误节点的情况下,我们该如何计算n、f、Q之间的关系呢?接下来,我们将从最简单的CFT场景出发,逐步探索如何在BFT场景中得到这些数值取值之间的关系。

▲CFT

CFT(Crash Fault Tolerance),表示系统中的节点只会出现宕机(Crash)这种错误行为,任何节点不会主动发出错误消息。当我们在讨论共识算法可靠性时,通常会关注算法两种基本性质:活性(liveness)安全性(safety)。在计算Q的大小时,同样也可以从这两个角度出发进行考虑。

对于活性与安全性,有一种比较直观的描述方式:

  • something eventually happens[4],某个事件最终会发生
  • something good eventually happens[4],这个最终会发生的事件合理

从活性角度出发,我们的集群需要能够持续运行下去,不会由于某些节点的错误导致无法继续共识。从安全性角度出发,我们的集群在共识推进的过程中,能够持续获得某个合理的结果,对于分布式系统来说,这种“合理”的结果,其最基本的要求就是集群整体状态的一致性。

于是,在CFT场景下,对于Q数值的确定就变得简单明确:

  • 活性:由于我们需要保证集群能够持续运行,所以,在任何场景下都要保证有获取到Q票的可能性,从而为集合读写数据。由于集群中最多会有f个节点发生宕机,所以为了保证能获取到Q票,该值的大小需要满足:Q<=n-f。
  • 安全性:由于我们需要保证集群不发生分歧,所以,按照Quorum机制的基本要求,需要满足在上一节当中提到的两个不等式,将Q作为最小读集合与最小写集合带入该组不等式,此时,Q满足不等关系,Q+Q>n且Q>n/2,因此,该值的大小需要满足:Q>n/2。

▲BFT

BFT(Byzantine Fault Tolerance),表示集群中的错误节点不仅可能会发生宕机,也可能存在恶意行为,即拜占庭(Byzantine)行为,例如主动进行状态分叉。在这种情况下,对于集群整体而言,只有n-f个节点的状态可靠,当我们收集到Q个投票时,其中也只有Q-f个投票来自可靠的节点。因此,在安全性方面,BFT场景下需要保证状态可靠的节点之间不会发生分歧,因此得到以下两种关系:

  • 活性:依然只需要保证每时每刻都有获取Q票的可能性,因此,Q<=n-f。
  • 安全性:对于全部保证正确的节点(总数n-f)不会发生分歧,此时,应当满足不等关系,(Q-f)+(Q-f)>n-f且(Q-f)>(n-f)/2,因此,此时Q的大小需要满足的关系为,Q>(n+f)/2。

▲节点总数与容错上限

对于节点总数n与容错上限f,在PBFT论文当中给出的解释[1]:由于存在f个节点可能发生宕机,因此我们至少需要在收到n-f条消息时进行响应,而对于我们收到的来自n-f个节点的消息,由于其中最多可能存在f条消息来自于不可靠的拜占庭节点,因此需要满足n-f-f>f,所以,n>3f

简单来说,PBFT的作者从集群活性与安全性出发,得到了节点总数与容错上限之间的关系。上一节中,我们也是从活性与安全性角度,获得了n、f与Q的关系,在这里也可以用来推导n与f的关系:为了同时满足活性与安全性的要求,Q需要满足不等关系,Q<=n-f且Q>(n+f)/2,因此,可以得到n与f之间的不等关系,(n+f)/2n>3f

(通过类似的方式,也可以得到CFT场景中n与f的关系,n>2f。)


--PBFT与RBFT --


在理解BFT场景中n、f、Q的关系后,接下来进入到PBFT的介绍。在此之前,简单提一下SMR(State Machine Replication)复制状态机[5]。在该模型当中,对于不同的状态机,如果从同样的初始状态出发,按照同样的顺序输入同样的指令集,那么它们得到的最终结果总会一致。对于共识算法而言,其只需要保证“按照同样的顺序输入同样的指令”,即可在各个状态机上获得同样的状态。而PBFT就是对指令执行顺序的共识。

那么,PBFT是如何保证指令执行顺序的一致性呢?PBFT集群为主从结构,由主节点提出提案,并通过集群中各个节点间的交互进行验证,从而使得每个正确节点遵循同样的顺序对指令集进行执行。在这个交互过程中,就需要使用Quorum机制保证集群整体状态的一致性。下面我们将对PBFT进行详细介绍。

▲两阶段共识

相比较常见的“三阶段“概念(pre-preapre、prepare、commit),将PBFT视为一种两阶段共识协议或许更能体现每个阶段的目的:提案阶段(pre-prepare与prepare)和提交阶段(commit)。在每个阶段中,各个节点都需要收集来自Q个节点一致的投票后,才会进入到下一个阶段。为了更方便讨论,这里将讨论节点总数为3f+1时的场景,此时,读写集票数Q为2f+1

1) 提案阶段

在该阶段中,由主节点发送pre-prepare发起共识,由从节点发送prepare对主节点的提案进行确认。主节点在收到客户端的请求后,会主动向其它节点广播pre-prepare消息

  • v为当前视图
  • n为主节点分配的请求序号
  • D(m)为消息摘要
  • m为消息本身

从节点在收到pre-prepare消息之后,会对该消息进行合法性验证,若通过验证,那么该节点就会进入pre-prepared状态,表示该请求在从节点处通过合法性验证。否则,从节点会拒绝该请求,并触发视图切换流程。当从节点进入到pre-prepared状态后,会向其它节点广播prepare消息,

  • i为当前节点标识序号

其他节点收到消息后,如果该请求已经在当前节点进入pre-prepared状态,并且收到2f条来自不同节点对应的prepare消息(包含自身),从而进入到prepared状态,提案阶段完成。此时,有2f+1个节点认可将序号n分配给消息m,这就意味着,该共识集群已经将序号n分配给消息m。

2) 提交阶段

当请求在当前节点进入prepared状态后,本节点会向其它节点广播commit消息。如果该请求已经在当前节点达到prepared状态,并且收到2f+1条来自不同节点对应的commit消息(包含自身),那么该请求就会进入到committed状态,并可以进行执行。此时,有2f+1个节点已经得知共识集群已经将序号n分配给消息m。执行完毕后,节点会将执行结果反馈给客户端进行后续判断。

▲检查点机制

PBFT共识算法在运行过程中,会产生大量的共识数据,因此需要执行合理的垃圾回收机制,及时清理多余的共识数据。为了达成这个目的,PBFT算法设计了checkpoint流程,用于进行垃圾回收。

checkpoint即检查点,这是检查集群是否进入稳定状态的流程。在进行检查时,节点广播checkpoint消息

  • n为当前请求序号
  • d为消息执行后获得的摘要
  • i为当前节点表示

当节点收到来自不同节点的2f+1条有相同的checkpoint消息后,即可认为,当前集群对于序号n进入了稳定检查点(stable checkpoint)。此时,将不再需要stable checkpoint之前的共识数据,可以对其进行清理。不过,如果为了进行垃圾回收而频繁执行checkpoint,那么将会对系统运行带来明显负担。所以,PBFT为checkpoint流程设计了执行间隔,设定每执行k个请求后,节点就主动发起一次checkpoint,来获取最新的stable checkpoint。

除此之外,PBFT引入了高低水位(high/low watermarks)的概念,用于辅助进行垃圾回收。在共识进行的过程中,由于节点之间的性能差距,可能会出现节点间运行速率差异过大的情况。部分节点执行的序号可能会领先于其他节点,导致于领先节点的共识数据长时间得不到清理,造成内存占用过大的问题,而高低水位的作用就是对集群整体的运行速率进行限制,从而限制了节点的共识数据大小。

高低水位系统中,低水位记为h,通常指的是最近一次的stable checkpoint对应的高度。高水位记为H,计算方式为H=h+L,L代表了共识缓存数据的最大限度,通常为checkpoint间隔K的整数倍。当节点产生的checkpoint达到到stable checkpoint状态时,节点将更新低水位h。在执行到最高水位H时,如果低水位h没有被更新,节点会暂停执行序号更大的请求,等待其他节点的执行,待低水位h更新后重新开始执行更大序号的请求。

▲视图变更

当主节点超时无响应或者从节点集体认为主节点是问题节点时,就会触发视图变更(view-change)。视图变更完成后,视图编号将会加1,随之主节点也会切换到下一个节点。如图所示,节点0发生异常触发视图变更流程,变更完成后,节点1成为新的主节点。

当视图变更发生时,节点会主动进入到新视图v+1中,并广播view-change消息,请求进行主节点切换。此时,共识集群需要保证,在旧视图中已经完成共识的请求能够在新视图中得到保留。因此,在视图变更请求中,一般需要附加部分旧视图中的共识日志,节点广播的请求为

  • i为发送者节点的身份标识
  • v+1表示请求进入的新视图
  • h为当前节点最近一次的稳定检查点的高度
  • C:当前节点已经执行过的检查点的集合,数据按照的方式进行存储,表示当前节点已经执行过序号为n摘要为d的checkpoint检查,并发送过相应的共识消息。
  • P:在当前节点已经达成prepared状态的请求的集合,即,当前节点已经针对该请求收到了1条pre-prepare消息与2f条prepare消息。在集合P中,数据按照的方式进行存储,表示在视图v中,摘要为d序号为n的请求已经进入了prepared状态。由于请求已经达成了prepared状态,说明至少有2f+1个节点拥有并且认可该请求,只差commit阶段即可完成一致性确认,因此,在新的视图中,这一部分消息可以直接使用原本的序号,无需分配新序号。
  • Q:在当前节点已经达成pre-prepared状态的请求的集合,即,当前节点已经针对该请求发送过对应的pre-prepare或prepare消息。在集合Q中,数据同样按照的方式进行存储。由于请求已经进入pre-prepared状态,表示该请求已经被当前节点认可。

但是,视图v+1对应的新主节点P在收到其他节点发送的view-change消息后,无法确认view-change消息是否拜占庭节点发出的,也就无法保证一定使用正确的消息进行决策。PBFT通过view-change-ack消息让所有节点对所有它收到的view-change消息进行检查和确认,然后将确认的结果发送给P。主节点P统计view-change-ack消息,可以辨别哪些view-change是正确的,哪些是拜占庭节点发出的。

节点在对view-change消息进行确认时,会对其中的P、Q集合进行检查,要求集合中的请求消息小于等于视图v,若满足要求,就会发送view-change-ack消息

  • i为发送ack消息的节点标识
  • j为要确认的view-change消息的发送者标识
  • d为要确认的view-change消息的摘要

不同于一般消息的广播,这里不再使用数字签名标识消息的发送方,而是采用会话密钥保证当前节点与主节点通信的可信,从而帮助主节点判定view-change消息的可信性。

新的主节点P维护了一个集合S,用来存放验证正确的view-change消息。当P获取到一条view-change消息以及合计2f-1条对应的view-change-ack消息时,就会将这条view-change消息加入到集合S。当集合S的大小达到2f+1时,证明有足够多的非拜占庭节点发起视图变更。主节点P会按照收到的view-change消息,产生new-view消息并广播,

  • V:视图变更验证集合,按照的方式进行存储,表示节点i发送的view-change消息摘要为d,均与集合S中的消息相对应,其他节点可以使用该集合中的摘要以及节点标识,确认本次视图变更的合法性。
  • X:包含稳定检查点以及选入新视图的请求。新的主节点P会按照集合中S的view-change消息进行计算,根据其中的C、P、Q集合,确定最大稳定检查点以及需要保留到新视图中的请求,并将其写入集合X中,具体选定过程相对繁琐,如果有兴趣,读者可以参阅原始论文[6]。

▲改进空间与RBFT

RBFT(Robust Byzantine Fault Tolerance),是趣链科技基于PBFT为企业级联盟链平台研发的高鲁棒性共识算法。相比较PBFT来说,我们在共识消息处理、节点状态恢复、集群动态维护等多方面进行了优化改良,使得RBFT共识算法能够应对更复杂多样的实际场景。

1) 交易池

包括RBFT在内,许多共识算法的工业实现中,都设计了独立的交易池模块。在收到交易后,将交易本身存放在交易池里,并通过交易池对交易进行共享,使得各个共识节点都能获得共享的交易。在共识的过程中,只需对交易哈希进行共识即可。

在处理较大交易时,交易池对于共识的稳定性有不错的提升。将交易池与共识算法本身进行解耦,也更方便通过交易池实现更多的功能特性,比如交易去重。

2) 主动恢复

在PBFT中,当节点借由checkpoint或view-change发现自身的低水位落后,即稳定检查点落后时,落后节点就会触发相应的恢复过程,以拉取该稳定检查点之前的数据。这样的落后恢复机制有一些不足:一方面,该恢复流程的触发是被动的,需要在checkpoint过程或者触发view-change完成时才能触发落后恢复;另一方面,对于落后节点来说,如果通过checkpoint发现自身稳定检查点落后时,落后节点只能恢复到最新的稳定检查点,而无法获得该检查点后落后的共识消息,可能一直无法真正参与到共识当中。

在RBFT中,我们设计了主动的节点恢复机制:一方面,该恢复机制可以主动触发,更快地帮助落后节点进行恢复;另一方面,在恢复到最新的稳定检查点基础之上,我们设计了水位间的恢复机制,从而使得落后节点能够获取到最新的共识消息,更快地参与到正常共识流程。

3) 集群动态维护

Raft作为一种广泛应用在工程中的共识算法,其重要优势之一,就是能够动态完成集群成员变更。而PBFT没有给出集群成员动态变更方案,在实际应用中存在不足。在RBFT中,我们设计了一种动态变更集群成员的方案,使得不需要停启集群整体的情况下,就可以对集群成员进行增删。

新增或删除节点时,由管理员向集群发交易创建操作节点的提案,并等待其他管理员投票,投票通过后由创建提案的管理员再次向集群发执行提案配置交易,执行时会更改集群配置。

对于共识部分,当处理执行提案配置交易时,集群中的节点将进入配置变更状态,不再打包其他交易。主节点将该交易单独打包生成配置包,并对该配置包进行共识。当该配置包完成共识,它将被执行并生成配置区块。为了保证改配置区块不可回滚,共识层将等待改配置包的执行结果,确定集群中已经对于该配置包所在高度形成稳定检查点,才会解除节点的配置状态,继续进行其他交易的打包。

对于集群不同的配置状态,我们通过世代(epoch)进行区分。不同世代拥有其独立的编号,该编号为单调递增的,每次执行完成一笔执行提案配置交易,将会对世代编号进行更新。对于集群中不同的节点,如果它们处于同一个世代下,则可以进行正常的信息交互。否则,节点之间只能进行状态恢复相关消息的交互。由于配置变更的信息已经被写入链上,因此,我们可以通过直接同步区块的方式为落后节点进行配置更新。通过上一节所说的主动恢复协议,世代落后的节点可以获取到最新的状态,并通过直接同步区块的方式恢复至最新的稳定检查点,同时完成节点世代与配置状态的恢复。

通过这样的动态变更集群成员的方式,使得集群配置维护更加可靠与便捷,并且可以为动态修改更多配置信息提供了可能。

作者简介

王广任 趣链科技基础平台部共识算法研究小组

参考文献

[1] Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.

[2] Castro M, Liskov B. Practical Byzantine fault tolerance[C]//OSDI.1999, 99(1999): 173-186.

[3] https://en.wikipedia.org/wiki/Quorum _ (distributed_computing)

[4] Owicki S, Lamport L. Proving liveness properties of concurrent programs[J]. ACM Transactions on Programming Languages and Systems (TOPLAS), 1982, 4(3): 455-495.

[5] Fred B. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Comput. Surv., 22(4):299–319, 1990.

[6] Castro M, Liskov B. Practical Byzantine fault tolerance andproactive recovery[J]. ACM Transactions on Computer Systems (TOCS), 2002,20(4): 398-461.

本文链接:https://www.8btc.com/media/6670755
转载请注明文章出处

评论
登录 账号发表你的看法,还没有账号?立即免费 注册
下载
分享
阅读
评论
点赞
上一篇
下一篇