拜占庭容错机制

简介

Client会发送一系列请求给各个replicas节点来执行相应的操作，BFT算法保证所有正常的replicas节点执行相同序列的操作。因为所有的replicas节点都是deterministic，而且初始状态都相同，根据状态机原理（state machine replication），这些replicas会产生相同的结果状态。当Client收到f+1个replicas节点返回的结果时，如果这些结果都一样，因为BFT算法确保了最多有f个replicas出现问题，所以至少有一个replicas是正确的，那么Client收到的这些结果都是正确的。

但是state machine replication的难点在于确保正常replicas节点都以相同的序列执行同样的一些请求，尤其是如何来面对拜占庭故障。PBFT会融合primary-backup 和 quorum replication 两种技术来序列化请求。

primary-backup

这个机制下有一个叫view的概念，在一个view里，一个replica会是主节点（primary），其余的replicas都叫备份节点（backups）。主节点负责将来自Client的请求给排好序，然后按序发送给备份节点们。但是主节点可能会是faulty的：它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性，并能通过timeout机制检测到主节点是否已经宕掉。当出现这些异常情况时，这些备份节点就会触发view change协议来选举出新的主节点。

quorums有两个重要的属性：

Intersection： 任意两个quorums至少有一个共同的并且正确的replica Availability: 总是存在一个没有faulty replicas的quorum 如果一个replica把信息写给一个quorum，并让该quorum来存储信息，在收到每一个quorum中的成员的确认反馈后，那么我们可以认为该replica的信息已经被可靠的保存在了这个分布式系统中。这是强的约束，当然还有一个weak certificates：就是至少f+1个节点来共同存取信息，这样至少有一个正确的replica存到了这份信息。

我们先来约定一些符合：

R是所有replicas的集合，每一个replica用一个整数来表示，依次为：

{ 0, …, |R - 1 }


简单起见，我们定义

|R = 3f + 1 
f 是最大可容忍的faulty节点

另外我们将一个view中的primary节点定义为replica p，

p = v mod |R 
v 是view的编号，从0开始一直连续下去，这样可以理解为从replica 0 到 replica |R-1 依次当primary节点，当每一次view change发生时。

我们定义一个quorum为至少包含2f+1个replicas的集合。

The Client

一个Client会将请求

⟨REQUEST,o,t,c⟩ 其中o表示具体的操作，t表示timestamp，给每一个请求加上时间戳，这样后来的请求会有高于前面的时间戳

replicas会接收请求，如果他们验证了条请求，就会将它写入到自己的log中。在共识算法保证下每个replica完成对该请求的执行后直接将回复返回给client：

⟨REPLY,v,t,c,i,r⟩ v是当前的view序号，t就是对应请求的时间戳，i是replica节点的编号，r是执行结果

我们上面提到过weak certificate，在这里，client也会等待这个weak certificate：即有f+1个replicas回复，并且它们的回复拥有相同的 t 和 r，由于至多有f个faulty replicas，所以确保了回复是合法的。我们叫这个weak certificate为 reply certificate。

每一个replica会与每一个处于active状态的client共享一份秘钥。秘钥所占据空间较少，加上会限制active client的数量，所以不必担心以后出现的扩展性问题。

Normal Case Operation

我们采用三阶段协议来广播请求给replicas：pre-prepare, prepare, commit。 （1）pre-prepare阶段：

主节点收到客户端请求，给请求编号，并发送pre-pre类型信息给其他从节点。

image.png

从1节点收到pre-pre类型信息，如果同意这个请求的编号，如果同意就进入prepare阶段

（2）Prepare阶段：

从1节点同意主节点请求的编号，将发送prepare类型消息给主节点和其他两个从节点。如果不发，表示不同意。

image.png

图：从1节点发prepare信息给其他节点

从1节点如果收到另外两个从节点都发出的同意主节点分配的编号的prepare类型的消息，则表示从1节点的状态为prepared,该节点会拥有一个prepared认证证书。

为了防止viewchange导致主节点给请求分配的编号失效，引入commit阶段。

（3）commit阶段

从1节点进入prepared状态后，将发送一条COMMIT类型信息给其它所有节点告诉他们它有一个prepared认证证书了。

image.png

图：从1节点发commit类型信息给其他节点

如果从1节点收到2f+1条commit信息，证明从1节点已经进入commited状态。

只通过这一个节点，我们就能认为客户端的请求在需要的节点中都到达了prepared状态，每一个需要的节点都同意了主节点分配的编号。当一个请求在某个节点中到达commited状态后，该请求就会被该节点执行。

Garbage Collection

分布式系统的复杂性在于要考虑到各种各样的意外和蓄意破坏，你要制定出一套有效的法律来约束这个系统里可能发生的一切行为，并没有完美的分布式系统存在。 当replica执行完请求时，需要把之前记录的该请求的信息清除掉。但是不能这样轻易的去清除，其中包含的prepared certificate可能会在后面用得上。所以要有种机智来保证何时可以清除。 其实很简单，每执行完一条请求，该节点会再一次发出广播，就是否可以清除信息在全网达成一致。更好的方案是，我们一连执行了K条请求，在第K条请求执行完时，向全网发起广播，告诉大家它已经将这K条执行完毕，要是大家反馈说这K条我们也执行完毕了，那就可以删除这K条的信息了，接下来再执行K条，完成后再发起一次广播，即每隔K条发起一次全网共识，这个概念叫checkpoint，每隔K条去征求一下大家的意见，要是获得了大多数的认同（a quorum certificate with 2 f + 1 CHECKPOINT messages (including its own)），就形成了一个 stable checkpoint（记录在第K条的编号），我们也说该replica拥有了一个stable certificate就可以删除这K条请求的信息了。 这是理想的情况，实际上当replica i向全网发出checkpoint共识后，其他节点可能并没有那么快也执行完这K条请求，所以replica i不会立即得到响应，它还要继续自己的步伐，那这个checkpoint在它那里就不是stable的。那这个步伐快的replica可能会越来越快，可能会把大家拉的越来越远，这时我们来看一下上面提到的高低水位的作用。对该replica来说，它的低水位h等于它上一个stable checkpoint的编号，高水位H=h+L，L是我们指定的数值，它一般是checkpoint周期K的常数倍（这个常数是比较小的， 比如2倍），这样即使该replica步伐很快，它处理的请求编号达到高水位H后也得停一停自己的脚步，直到它的stable checkpoint发生变化，它才能继续向前。

View Changes

当主节点挂掉后就触发了view change协议。我们需要确保在新的view中如何来延续上一个view最终的状态，比如给这时来的新请求的编号，还有如何处理上一个view还没来得及完全处理好的请求。

Data Structures

所以我们需要记录上一个view里发生什么。 有两个集合P和Q，replica i 的P存着 i 在上一 view 中达到prepared状态的请求的一些信息，有了P，在新的view中，replica i就会明白接下来处于prepared状态的请求不能与上一个view中处于prepared状态的请求的编号相同。Q是记录在上一个view里到达pre-prepared状态的请求的一些信息。

View-Change Messages

我们来看一下Fig 2， 当备份节点 i 怀疑 view v中的主节点出问题（比如是坏节点）后，它会进入 view v+1，并广播一条VIEW-CHANGE信息给所有的replicas，其中包含该replica i最新的stable checkpoint的编号，还有 replica i上存的每一个checkpoint的编号和digest的集合，还有上面所说的该replica的P和Q两个集合。

View-Change-Ack Messages

replicas 会收集VIEW-CHANGE信息并发送ACK确认给 view v+1 中的主节点 。新的主节点收集了VIEW-CHANGE和VIEW-CHANGE-ACK（包含自己的信息），它会将VIEW-CHANGE存在一个集合S中。主节点需要选出一个checkpoint作为新view处理请求的起始状态。它会从checkpoint的集合中选出编号最大（假设编号为h）的checkpoint。接下来，主节点会从h开始依次选取h到h+L（L就是normal case阶段我们提到的设置值）之间的编号n对应的请求在新的view中进行pre-prepare，如果一条请求在上一个view中到达了committed状态，主节点就选取这个请求开始在新的view中进行三阶段。之所以选取committed的请求，是因为上面我们提到增加COMMIT阶段为了across view来考虑的，处于committed状态的请求的编号在新的view中是有效的，可以继续使用。但是如果选取的请求在上一view中并没有被一个quorum给prepare，那它的编号n有可能是不被一个quorum给同意的，我们选择在新的view中作废这样的请求。