不变秃,也要变强!

0%

PBFT

PBFT、DBFT在联盟链中使用。

最大容错数量

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

  1. 第一种情况,f 个有问题节点既是故障节点,又是作恶节点,那么根据小数服从多数的原则,集群里正常节点只需要比f个节点再多一个节点,即 f+1 个节点,确节点的数量就会比故障节点数量多,那么集群就能达成共识。也就是说这种情况支持的最大容错节点数量是 (n-1)/2。
  2. 第二种情况,故障节点和作恶节点都是不同的节点。那么就会有 f 个问题节点和 f 个故障节点,当发现节点是问题节点后,会被集群排除在外,剩下 f 个故障节点,那么根据小数服从多数的原则,集群里正常节点只需要比f个节点再多一个节点,即 f+1 个节点,确节点的数量就会比故障节点数量多,那么集群就能达成共识。

所以,所有类型的节点数量加起来就是 f+1 个正确节点,f个故障节点和f个问题节点,即 3f+1=n。结合上述两种情况,因此 pbft 算法支持的最大容错节点数量是(n-1)/3。

算法核心三阶段流程

下面介绍 pbft 算法的核心三阶段流程,如下图所示:

4B547A79-AB87-4B17-AD0B-5C126FF53CE1

算法的核心三个阶段分别是 pre-prepare 阶段(预准备阶段),prepare 阶段(准备阶段), commit 阶段(提交阶段)。图中的C代表客户端,0,1,2,3 代表节点的编号,打叉的3代表可能是故障节点或者是问题节点,这里表现的行为就是对其它节点的请求无响应。0 是主节点。整个过程大致是如下:

request

首先,客户端向主节点发起请求,主节点 0 收到客户端请求,会向其它节点发送 pre-prepare 消息,其它节点就收到了pre-prepare 消息,就开始了这个核心三阶段共识过程了。
Pre-prepare 阶段:节点收到 pre-prepare 消息后,会有两种选择,一种是接受,一种是不接受。什么时候才不接受主节点发来的 pre-prepare 消息呢?一种典型的情况就是如果一个节点接受到了一条 pre-pre 消息,消息里的 v 和 n 在之前收到里的消息是曾经出现过的,但是 d 和 m 却和之前的消息不一致,或者请求编号不在高低水位之间(高低水位的概念在下文会进行解释),这时候就会拒绝请求。拒绝的逻辑就是主节点不会发送两条具有相同的 v 和 n ,但 d 和 m 却不同的消息。

Prepare 阶段

节点同意请求后会向其它节点发送 prepare 消息。这里要注意一点,同一时刻不是只有一个节点在进行这个过程,可能有 n 个节点也在进行这个过程。因此节点是有可能收到其它节点发送的 prepare 消息的。在一定时间范围内,如果收到超过 2f 个不同节点的 prepare 消息,就代表 prepare 阶段已经完成。进入commit阶段。

Commit 阶段

向其它节点广播 commit 消息,同理,这个过程可能是有 n 个节点也在进行的。因此可能会收到其它节点发过来的 commit 消息,当收到 2f+1 个 commit 消息后(包括自己),代表大多数节点已经进入 commit 阶段,这一阶段已经达成共识,于是节点就会执行请求,写入数据。处理完毕后,节点会返回消息给客户端,

这就是 pbft 算法的全部流程。为了更清晰的展现 这个过程和一些细节,下面以流程图来表示这个过程:

D4262F5D-AC6C-4739-B927-37AB53B56D41

注解:
V:当前视图的编号。视图的编号是什么意思呢?比如当前主节点为 A,视图编号为 1,如果主节点换成 B,那么视图编号就为 2,这个概念和 raft 的 term 任期是很类似的。
N:当前请求的编号。主节点收到客户端的每个请求都以一个编号来标记。
M:消息的内容
d或D(m):消息内容的摘要
i: 节点的编号

checkpoint 、stable checkpoint和高低水位

checkpoint

checkpoint 就是当前节点处理的最新请求序号。前文已经提到主节点收到请求是会给请求记录编号的。比如一个节点正在共识的一个请求编号是101,那么对于这个节点,它的 checkpoint 就是101。

stable checkpoint (稳定检查点)

stable checkpoint 就是大部分节点 (2f+1) 已经共识完成的最大请求序号。比如系统有 4 个节点,三个节点都已经共识完了的请求编号是 213 ,那么这个 213 就是 stable checkpoint 了。那设置这个 stable checkpoint 有什么作用呢?最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求,但如果一直记录下去,数据会越来越大,所以应该有一个机制来实现对数据的删除。那怎么删呢?很简单,比如现在的稳定检查点是 213 ,那么代表 213 号之前的记录已经共识过的了,所以之前的记录就可以删掉了。

高低水位

下面以一个示意图来进行解释:

D39949FE-A730-4854-AA41-1187A8060FF7

图中A节点的当前请求编号是 1039,即checkpoint为1039,B节点的 checkpoint 为1133。当前系统 stable checkpoint 为 1034 。那么1034这个编号就是低水位,而高水位 H=低水位 h+L ,其中L是可以设定的数值。因此图中系统的高水位为 1034+100=1134。举个例子:如果 B 当前的 checkpoint 已经为 1133,而A的 checkpoint 还是 1039 ,假如有新请求给 B 处理时,B会选择等待(checkpoint最大为高水位-1),等到 A 节点也处理到和 B 差不多的请求编号时,比如 A 也处理到 1112 了,这时会有一个机制更新所有节点的 stabel checkpoint ,比如可以把 stabel checkpoint 设置成 1100(此时高水位为1200,B的checkpoint最大可以到1199) ,于是 B 又可以处理新的请求了。

ViewChange(视图更改)事件

当主节点挂了(超时无响应)或者从节点集体认为主节点是问题节点时,就会触发 ViewChange 事件, ViewChange 完成后,视图编号将会加 1 。下图展示 ViewChange 的三个阶段流程:

E43015AE-5197-4BAE-838C-3CC8A65689E3

如图所示, viewchange 会有三个阶段,分别是 view-change , view-change-ack 和 new-view 阶段。从节点认为主节点有问题时,会向其它节点发送 view-change 消息,当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到 2f 个其它节点的 view-change 消息,则证明有足够多人的节点认为主节点有问题,于是就会向其它节点广播 New-view 消息。注意:从节点不会发起 new-view 事件。对于主节点,发送 new-view 消息后会继续执行上个视图未处理完的请求,从 pre-prepare 阶段开始。其它节点验证 new-view 消息通过后,就会处理主节点发来的 pre-prepare 消息,这时执行的过程就是前面描述的 pbft 过程。到这时,正式进入 v+1 (视图编号加1)的时代了。
为了更清晰的展现 ViewChange 这个过程和一些细节,下面以流程图来表示这个过程:

410651B8-D182-4658-8B27-5081C5954E9A

上图里红色字体部分的 O 集合会包含哪些 pre-prepare 消息呢?假设 O 集合里消息的编号范围:(min~max),则 Min 为 V 集合最小的 stable checkpoint , Max 为 V 集合中最大序号的 prepare 消息。最后一步执行 O 集合里的 pre-preapare 消息,每条消息会有两种情况: 如果 max-min > 0,则产生消息 ;如果 max-min=0,则产生消息

与Raft比较

对比点 Raft PBFT
时间复杂度 O(n) O(n^2)
最大容错/故障节点数量 2f+1<=N 3f+1<=N
流程对比 谁快谁当leader 按编号依次做主节点

而对于算法通信复杂度,为什么 raft 是 o(n),而 pbft 是 o(n^2)呢?这里主要考虑算法的共识过程。
对于 raft 算法,核心共识过程是日志复制这个过程,这个过程分两个阶段,一个是日志记录,一个是提交数据。两个过程都只需要领导者发送消息给跟随者节点,跟随者节点返回消息给领导者节点即可完成,跟随者节点之间是无需沟通的。所以如果集群总节点数为 n,对于日志记录阶段,通信次数为 n-1,对于提交数据阶段,通信次数也为 n-1,总通信次数为 2n-2,因此raft算法复杂度为O(n)。
对于 pbft 算法,核心过程有三个阶段,分别是 pre-prepare (预准备)阶段,prepare (准备)阶段和 commit (提交)阶段。对于 pre-prepare 阶段,主节点广播 pre-prepare 消息给其它节点即可,因此通信次数为 n-1 ;对于 prepare 阶段,每个节点如果同意请求后,都需要向其它节点再 广播 parepare 消息,所以总的通信次数为 n(n-1),即 n^2-n ;对于 commit 阶段,每个节点如果达到 prepared 状态后,都需要向其它节点广播 commit 消息,所以总的通信次数也为 n(n-1) ,即 n^2-n 。所以总通信次数为 (n-1)+(n^2-n)+(n^2-n) ,即 2n^2-n-1 ,因此pbft算法复杂度为 O(n^2) 。

思考问题

为什么需要3阶段

为什么不能只有前2个阶段消息

这个问题的等价问题是:为什么Pre-prepare和Prepare消息,不能让非拜占庭节点达成一致?

Pre-prepare消息的目的是,主节点为请求m,分配了视图v和序号n,让至少f+1个非拜占庭节点对这个分配组合<m, v, n>达成一致,并且不存在<m', v, n>,即不存在有2个消息使用同一个v和n的情况。

Prepared状态可以证明非拜占庭节点在只有请求m使用<v, n>上达成一致。主节点本身是认可<m, v, n>的,所以副本只需要收集2f个Prepare消息,而不是2f+1个Prepare消息,就可以计算出至少f个副本节点是非拜占庭节点,它们认可m使用<v, n>,并且没有另外1个消息可以使用<v, n>

既然1个<v, n>只能对应1个请求m了,达到Prepared状态后,副本i执行请求m,不就达成一致了么?

并不能。Prepared是一个局部视角,不是全局一致,即副本i看到了非拜占庭节点认可了<m, v, n>,但整个系统包含3f+1个节点,异步的系统中,存在丢包、延时、拜占庭节点故意向部分节点发送Prepare等拜占庭行文,副本i无法确定,其他副本也达到Prepared状态。如果少于f个副本成为Prepared状态,然后执行了请求m,系统就出现了不一致。

所以,前2个阶段的消息,并不能让非拜占庭节点达成一致。

如果你了解2PC或者Paxos,我相信可以更容易理解上面的描述。2PC或Paxos,第一步只是用来锁定资源,第2步才是真正去Do Action。把Pre-prepare和Prepare理解为第一步,资源是<v, n>,只有第一步是达不成一致性的。

2个不变性

PBFT的论文提到了2个不变性,这2个不变性,用来证明PBFT如何让非拜占庭节点达成一致性

第1个不变性,它是由Pre-prepare和Prepare消息所共同确保的不变性:非拜占庭节点在同一个view内对请求的序号达成共识。关于这个不变性,已经在“为什么不能只有前2个阶段消息”中论述过。

介绍第2个不变性之前,需要介绍几个定义。

  • Prepared状态:副本i有Pre-prepare消息(与主节点通信),且收到2f个有效的Prepare消息。副本i达到Prepared状态,可以发送Commit消息,Commit消息的内容和Prepare消息内容相同,但消息类型和数字签名是不同的,所以可以区分。
  • committed-local:副本i已经是Prepared状态,并且收到了2f+1个Commit消息。
  • committed:至少f+1个非拜占庭节点已经是Prepared状态。

img

第2个不变性,如果副本i是committed-local,那么一定存在committed。

2f+1个Commit消息,去掉最多f个拜占庭节点伪造的消息,得出至少f+1个非拜占庭节点发送了Commit消息,即至少f+1个非拜占庭节点是Prepared状态。所以第2个不变性成立。

为什么3个阶段消息可以达成一致性

committed意味着有f+1个非拜占庭节点可以执行请求,而committed-local意味着,副本i看到了有f+1个非拜占庭节点可以执行请求,f+1个非拜占庭节点执行请求,也就达成了,让非拜占庭节点一致。

虽然我前面使用了2PC和Paxos做类比,但不意味着PBFT的Commit阶段就相当于,2PC和Paxos的第2步。因为2PC和Paxos处理的CFT场景,不存在拜占庭节点,它们的主节点充当了统计功能,统计有多少节点完成了第一步。PBFT中节点是存在拜占庭节点的,主节点并不是可靠(信)的,不能依赖主节点统计是否有f+1个非拜占庭节点达成了Prepared,而是每个节点各自统计,committed-local让节点看到了,系统一定可以达成一致,才去执行请求。

参考

共识算法之pbft与raft

为什么PBFT需要3个阶段消息

点击下方打赏按钮,获得支付宝二维码