PBFG之视图更新

1 检查点

为了保证安全，除非消息中的请求至少已由f+1个无故障的副本节点执行，并且可以从视图更新中向其他节点证明，否则消息必须保留在副本节点日志中。另外，如果某些副本丢失了所有非故障副本节点丢弃的消息，则需要通过转移全部或部分服务状态来使消息更新。因此，副本也需要一些证明状态正确的证据。
在执行完所有操作之后生成这些证据的代价是昂贵的。相反，当执行的请求序列号可被某个常数(例如100)整除时，这些证据会定期生成。由执行完这些请求后根据状态机的状态产生的称为检查点，稳定的检查点就是该证据。
副本节点维护一些服务状态的逻辑拷贝:最新的稳定的检查点，零个或多个不稳定的检查点，还有当前状态。写时复制技术可以用于减少存储额外状态拷贝的空间负载。
作为证据的正确的检查点由以下步骤产生:

1. 当一个副本节点i生成了检查点，将会多播一个消息<CHECKPOINT,n,d,i>_s到其他副本节点。
   • n为状态中最新的被执行的请求序列号
   • d为状态的摘要
2. 每一个副本节点都会收集检查点信息，直到收集到2f+1个来自不同副本节点签名的具有相同序列号以及相同摘要d的消息
3. 将它们添加到日志中。这2f+1个消息即是证明该检查点正确的证明。
   具有证明的检查点即是稳定的检查点，副本节点将会抛弃所有的序列号小于或等于日志中所有pre-prepare,prepare,commit消息中序列号的消息。同时也会抛弃之前所有的检查点以及检查点消息。
   检查点协议用于推进低阈值标记和高阈值标记(限制可以接收多少消息)，低阈值h等于最新的稳定的检查点的序列号。高阈值H=h+k，其中k是足够大的数以至于副本节点不用一直等待检查点变为稳定的。例如，如果检查点包括接近100个请求，那么k可能为200.

2 视图更新过程

视图更新协议可以在系统中的primary虚假或崩溃时为系统提供活性。超时则会触发视图更新防止副本节点无限期地等待接收请求去执行。

• 如果副本接收到一个有效的请求并且还没有被执行，副本将会处于等待状态。
• 副本在接受到请求后并且计时器还没有处于运行时则会启动计时器。
• 当不再等待执行请求时，它将停止计时器，但如果此时正在等待执行其他请求，则将计时器重新启动。

1. 如果节点i在视图为v时计时器超时，该节点将会开始视图更新并且将视图变为v+1。停止接收信息(除了检查点，视图更新和新视图消息外)，并多播<VIEW-CHANGE,v+1,n,C,P,i>_s消息到所有副本节点。

   • n为节点i知道的最新的稳定检查点s的序列号。
   • C为一组2f+1个有效的检查点消息，它们证明检查点s的正确性
   • P是在节点i处的每个序列号高于n的请求消息m的prepared集合Pm的集合。
   • 每一个集合Pm包含2f个匹配的有效的pre-prepare消息(不包括与客户端相关的信息)，由不同的副本节点签名的具有相同视图，序列号，m的摘要的prepare消息。

2. 当primary:p在视图v+1时接收到2f个来自其他副本的视图为v+1的有效的VIEW-CHANGE消息后，将会多播一个<NEW-VIEW,v+1,V,O>_s消息到所有其他副本节点。

   • V为一个包含接收到的由primary发送的视图更改为v+1的有效的VIEW-CHANGE消息的集合。
   • O为一个pre-prepare消息的集合(不包含请求消息m),O通过以下内容计算:
     • primary决定关于V中最新的稳定的检查点的最小序列号min-s以及在V中的的prepare消息中最大的序列号max-s.
     • primary对每一个在min-s与max-s之间序列号n创建新的视图为v+1的pre-prepare消息。这里有两种情况:
       • 在P中至少有一个由一些在V中序列号为n的VIEW-CHANGE消息组成的集合。
       • 没有这样的集合

   在第一种情况下，primary创建新的消息<PRE-PREPARE,v+1,n,d>_s，这里的d为在V中序列号为n的高视图编号的pre-prepare消息的请求摘要。
   在第二种情况下，primary将会创建新的<PRE-PREPARE,v+1,n,d_null>_s消息，这里的d_null为指定的空的请求的摘要。空的请求在协议中和其他请求一样，只不过不进行执行。

3. 接下来primary添加O中的消息到日志中。如果min-s大于他的最新稳定的检查点的序列号，primary还在其日志中插入序列号为min-s的检查点的稳定性证明，并丢弃日志中的信息。这时候视图进入了v+1，在该点以后可以接收视图为v+1的消息。
4. 副本接收到关于视图为v+1的NEW-VIEW消息后，如果签名为正确的，且包含的内容对于视图是v+1是有效的，如果集合O是正确的(O的正确性通过与primary创建O时相同的计算过程进行验证).那么将该信息(正如primary描述的)添加到日志中。，多播在O中的prepare消息到其他所有副本中，并添加这些prepare消息到日志中，视图进入v+1。

5. 此后，正如三阶段提交协议过程，副本节点重新执行在min-s与max-s中的协议，但是避免重新执行客户端的请求(通过使用存储的关于最新的发送到每一个客户端的回复信息)。

副本可能会缺失某些请求消息m或者是稳定的检查点(由于没有发送NEW-VIEW消息)。这些缺失的信息可以从其他副本节点获取。
例如，副本i可以从一个副本节点(它的检查点信息已在V中确认正确性)获取缺失的检查点状态s.由于这些f+1个副本节点是正确的，副本节点i将总是获取s或者是最新的稳定检查点。通过对状态进行分区并为每个分区加上被修改的它的最后一个请求的序列号标记，可以避免发送整个检查点。要使副本为最新版本，只需将副本发送到过期的分区，而不是整个检查点。

PBFG之视图更新

原文：https://www.cnblogs.com/cbkj-xd/p/12175798.html