PBFT算法流程补充(一):视图变更、垃圾回收及状态机不确定性
时间: 2019-12-19来源:OSCHINA
前景提要
【围观】麒麟芯片遭打压成绝版,华为亿元投入又砸向了哪里?>>> 本文主要介绍PBFT算法的垃圾回收、视图变更机制及状态机不确定性问题的解决等。

1. 垃圾回收
本部分介绍PBFT算法的垃圾回收机制。

1.1 概述
本节介绍从本地日志中删除历史消息的机制。

对算法来说,为了保证安全性,每个副本节点需要保证如下两点:
对于每个请求来说,在被至少f+1个正常节点执行之前,所有相关的消息都必须记录在消息日志中;
同时,如果一条请求被执行,节点能够在视图变更中向其他节点证明这一点。

此外,如果某个副本节点缺失的一些消息正好已经被所有正常节点删除,则需要通过传输部分或全部的服务状态来使节点状态更新到最新。因此,节点需要某种方式来证明状态的正确性。

如果每执行一次操作,都生成一个状态证明,代价将会很大。因此可以每执行一定数量的请求后生成一次状态证明,例如:只要节点序号是某个值比如100的整数倍时,就生成一次,此时称这个状态为检查点。如果一个检查点带有相应的证明,我们则称其为稳定的检查点。

1.2 稳定检查点的生成
如上所述,一个带有证明的检查点被称为稳定的检查点,这种证明的生成过程如下:
1、副本节点i生成一个检查点之后,会组装检查点消息,并全网广播给其他所有副本节点,检查点消息格式如下:
<CHECKPOINT, n, d, i>,
这里n指的是生成目前最新状态的最后一条执行请求的序号,d是当前服务状态的摘要。

2、每个副本节点等待并收集 2f+1 个来自其它副本节点的检查点消息(有可能包括自己的),这些消息有相同的序号 n 和摘要 d。这 2f+1 个检查点消息就是该检查点的正确性证明。

一旦一个检查点成为稳定检查点后,节点将从本地消息日志中删除所有序号小于或等于n的请求所对应的预准备、准备和确认消息。同时,会删除所有更早的检查点和对应的检查点消息。

检查点的生成协议可以用来移动低水线 h 和高水线 H:
h的值就是最新稳定检查点所对应的稳定消息序号;
高水线 H = h+k,这里k要设置足够大,至少要大于检查点的生成周期,比如说:假如每隔100条请求生成检查点,k就可以取200。

2. 视图变更
PBFT算法运行过程中,如果主节点失效了,为了保持系统的活性(liveness),就需要用到视图变更协议。

2.1 视图变更的触发
由于主节点失效时,客户端最终会将请求发送到所有其他副本节点。每个节点收到客户端请求后,如果该请求没有执行过,副本节点判断自己是否为主节点,不是的话就会把请求转发给主节点,同时启动一个定时器(假如之前没有启动过的话)。

如果请求在定时器时间间隔内执行完,则节点会停止定时器(不过如果此时节点恰好在等待执行另外一个请求,则会重启定时器);否则,节点会尝试触发视图的变更,具体过程如下节所示。

2.2 视图变更协议
对于副本节点i来说,假设其当前所处的视图编号为 v ,经由视图变更协议,从视图 v 变更到 v+1。

视图变更过程中,节点将不再接受其他任何类型的消息,只接受 checkpoint, view-change, 和 new-view 消息。

视图变更过程如下:
1. 节点组装 VIEW-CHANGE 消息并广播给全网其他所有副本节点。
VIEW-CHANGE消息的格式如下:
<VIEW-CHANGE, v+1, n, C, P, i>
消息中的各字段含义如下:
v+1: 要变更到的目标视图编号;
n: 对应于节点已知的、最新的检查点 s 的请求序号;
C:包含 2f+1 个检查点消息的集合。这些检查点消息用于证明检查点 s 的正确性;
P:是一个集合,现在来解释一下其包含的信息。
对于任何一条客户端请求 m ,如果 m 在当前副本节点 i 上已经准备好, 即 prepared(m, v, n', i) 为 true, 并且 n' > n,那么根据定义,节点上已经存储了对应的预准备消息和 2f 个与之匹配的、有效的发自不同的节点的准备消息。这里,匹配的含义是:拥有相同的视图,消息序号以及 m 的摘要。我们把这些预准备
消息和准备消息组成的集合记为 。
P 就是所有 组成的集合。因此,P 包含了所有在副本节点上准备好的、序号大于 n 的请求的预准备和准备消息。在视图变更中,其提供的信息便于在新的视图中重新分配每条请求的消息序号。

2. 每个节点相继广播各自组装的 view-change 消息。同时,新视图中对应的新的主节点将收集来自其他副本节点的 view-change 消息。当其收集到 2f 个有效的 对应新视图 v+1 的 view-change 消息后,将组装并广播 new-view 消息,格式如下:
<NEW-VIEW, v+1, V, O>
其中,V是一个消息集合,包含所有有效的、对应于新视图 v+1 的 2f+1 个 view-change 消息(包括主节点自己组装的)。而 O 则是主节点为各 view-change 消息中包含的、符合要求的请求组装的预准备消息的集合。 O中的消息按如下方式组装:
首先,根据 V 中各条view-change 消息中包含的预准备和准备消息,主节点先找到最新的稳定检查点,将其对应的消息序号赋值给 min-s;然后从所有准备消息中找到最大的那个消息序号,将其赋值给 max-s;
然后,对于min-s 和 max-s 之间的每一个消息序号 n, 主节点为其组装位于视图 v+1 上的预准备消息,这分为两种情况:
a) 在 V 中存在某个或多个 view-change 消息, 它们的 P 集合中的某个集合元素包含的准备消息中包含有对应于序号 n 的消息。
此时,主节点组装的预准备消息如下:
<PRE-PREPARE, v+1, n, d>
其中,d 是V中特定请求消息的摘要,并且该请求在 V 中的一个最新视图上的预准备消息中被分配了序号 n 。
b) 另外一种情况,是 V 中不存在和 n 对应的准备消息。此时,主节点只是模拟为一个特殊的空请求(null request)组装一个预准备消息:
<PRE-PREPARE, v+1, n, D(null)>
其中,D(null) 为空请求的摘要。空请求和其他请求一样进行三阶段协议,但是其执行就是一个空操作(noop)。

3. 主节点广播 new-view 消息后,也会把 O 中的消息写入本地消息日志中。同时,如果主节点本地的最新稳定检查点的消息序号落后于 min-s 的话,则会将 min-s 对应的检查点的证明,也就是相应的检查点消息写入消息日志,并按之前介绍的垃圾回收机制删除所有的历史消息。

4. 此时,主节点正式变更到新视图 v+1, 开始接收消息。

5. 每个副本节点收到针对 v+1 视图的 new-view 消息后,会进行校验,是否满足以下条件:
签名正确;
其中包含的 view-change 消息是针对 v+1 视图,并且有效;
集合 O 中的信息正确、有效。节点判断有效与否的方法是进行类似于主节点生成 O 那样的计算。
如果校验通过,副本节点会将相关信息写入到本地日志中。 同时,针对 O 中的每一条预准备消息,组装并广播对应的准备消息,并且把准备消息写入到本地消息日志中。
此时,副本节点也如同主节点那样,进入到新视图 v+1 中。
之后,在新的视图中,针对所有序号位于 min-s 和 max-s 之间的请求,系统会重新运行三阶段协议。只不过对于每一个副本节点来说,如果当前确认的请求之前已经执行过的话,节点就不再执行该请求。每条被执行的请求,其相关信息会被存储在本地。节点根据这些信息确定请求的执行情况。

以上完成了对视图变更的介绍。

2.3 视图变更中节点的信息同步
视图变更时,由于 new-view 消息中并不包含原始的客户端请求,因此副本节点可能缺失某条客户端请求 m ,或者某个稳定的检查点。

此时节点可以从其他副本节点同步缺失的信息。例如,假如节点 i 缺失某个稳定检查点 s ,这个检查点在 V 中可以找到相应的证明,也就是 对应的 checkpoint 消息。由于总共有 2f+1个这样的消息,而错误节点最多 f个,因此至少有 f+1 个正常节点发送过这样的消息。因此,可以从这些正常节点获取到对应的检查点状态。

对于副本复制服务的状态来说,可以通过生成不同的检查点来划分状态。当节点需要同步状态时,只需按检查点来获取即可。这可以避免一次发送整个服务状态。

3. 关于状态机的不确定性
PBFT算法基于状态机副本复制服务,状态机要求每个节点的状态必须是确定性的。而大多数服务有时会有某种形式的不确定性。例如,对于网络文件系统而言,如果不基于状态机副本复制的话,文件的最后修改时间这个属性可以设置为服务器的本地时间。但如果是每个副本节点独自设置这个时间的话,就会导致各节点状态的不一致。

因此,需要相应机制来确保各节点使用相同的值。一般情况下,这个值不应该由客户端来决定,因为客户端拥有的信息并不完全。例如,多个客户端并发发送请求时,它们并不知晓其请求如何被排序。

可以由主节点来选取这个值,具体有两种方法:
1. 第一种方法适用于大多数服务,由主节点独立选取非确定的值。
主节点将该值和客户端请求拼接在一起,然后运行三阶段协议,确保所有正常节点就请求和该值的序号达成一致。这可以防止出现下列情况:
失效的主节点故意向不同的副本节点发送不同的值,从而使各个节点上的状态出现不一致。
对于这种方法来说,虽然所有正常节点使用相同的值,但这个由主节点发送的值可能是错误的。这种情况下,要求每个副本节点必须能够基于其状态来明确地判断该值的正确性,以及如何处理可能的错误值。

2. 第二种方法是该值的选取由各副本节点一起参与。这种方法要求在三阶段协议基础上额外增加一个阶段:主节点收集各副本节点发过来的、可验证来源的、共计 2f+1 个值,并把这些值和客户端请求拼接在一起,然后运行三阶段协议。 之后,每个副本节点基于这些值和各自的状态进行确定的计算,从而得到
所需选取的值。这种计算可以是类似于求中位数等。

相关阅读: PBFT算法流程

本文结束,下篇文章将分享PBFT算法流程补充(二),关注我们,第一时间获取分享!

科技资讯:

科技学院:

科技百科:

科技书籍:

网站大全:

软件大全:

热门排行