Skip to content

Latest commit

 

History

History
73 lines (43 loc) · 6.49 KB

PBFT.md

File metadata and controls

73 lines (43 loc) · 6.49 KB
Raw

共识机制 - 实用拜占庭容错(PBFT)

Raft是用在可信环境下的共识算法, 在有不可信节点的环境下, 即拜占庭将军问题, 需用其他的共识算法. 本文介绍的是PBFT(实用拜占庭容错算法),可以在保证活性和安全性 (liveness & safety)的前提下提供了(n-1)/3的容错性, 并大幅度降低了拜占庭算法的复杂度, 使其在实际系统应用中变的可行.

模型定义

PBFT是一种状态机副本复制算法(state machine replication), 状态机在分布式系统的不同节点进行副本复制. 整个系统共同维护一个状态,所有服务器采取一致的行动.

同所有的状态机副本复制技术一样, PBFT对每个副本节点提出了两个限定条件：

  • 所有节点必须是确定性的. 也就是说, 在给定状态和参数相同的情况下, 操作执行的结果必须相同；

  • 所有节点必须从相同的状态开始执行.

在这两个限定条件下, 即使失效的副本节点存在, PBFT算法对所有非失效副本节点的请求执行总顺序达成一致, 从而保证安全性.

拜占庭系统目前普遍采用的假设条件包括:-

  • 拜占庭节点(服务器和客户端)的行为可以是任意的,拜占庭节点之间可以共谋;
  • 节点之间的错误是不相关的.(错误节点不能超过f)
  • 节点之间通过异步网络连接,网络中的消息可能丢失,乱序到达,延时到达;
  • 服务器之间传递的信息,第三方可以知晓,但是不能窜改、伪造信息的内容和验证信息的完整性.这一点可通过非对称加密技术实现

算法流程

pbft_flow

PBFT是基于消息传递的一致性算法, 算法经过三个阶段达成一致性. 上图为最少集群节点数下的共识流程, 其N=4, f=1. 0为leader, 同时节点3为拜占庭节点, 该节点不响应或发出任何消息.

  1. 选出某个节点为主节点, 此后只要主节点不切换, 则成为一个视图
  2. 请求阶段：客户端向主节点发送请求.
  3. 预准备阶段：主节点分配一个提案编号n给收到的请求, 然后向所有备份节点广播预准备消息, 预准备消息的格式为<<PRE-PREPARE,v,n,d>,m>, 这里v是视图编号, m是客户端发送的请求消息, d是请求消息m的摘要.
  4. 准备阶段：备份节点i接受了预准备消息<<PRE-PREPARE,v,n,d>,m>, 则进入准备阶段. 在准备阶段的同时, 该节点向所有副本节点发送准备消息<PREPARE,v,n,d,i>, 并且将预准备消息和准备消息写入自己的消息日志.
  5. 确认阶段：副本节点收到2f个从不同副本节点发来一致的准备消息, 一共2f+1个一致的准备消息确认了消息的正确性, 然后按照序号n依次执行请求.

预准备阶段和准备阶段确保所有正常节点对同一个视图中的请求序号达成一致.

  • 如果发生view change, 会丢弃prepare阶段的请求

准备和确认两个阶段用来确保在不同的视图之间的确认请求是严格排序的, 并且确认了这是大多数节点认可的操作.

  • 此时如果发生view change, 不会丢弃确认阶段的请求
  • 新View会继续之前commit阶段的请求, 不会再重新进入pre-prepare和prepare阶段

为什么预防f个拜占庭节点需要3f + 1个节点

首先拜占庭节点的行为是不响应或响应错误信息的. 假设我们有N个节点, 我们不能等N的消息后, 再做判断, 因为有可能f个节点不响应. 合理做法是在接受到N - f的消息后就进行判断. 在极端情况下, 缺失的f个消息全是非拜占庭节点的, 只是传输的慢些. 也就是说N -f 的消息里,最多可能有f个错误消息, 为了保证正确性, 收到的正确消息个数必须大于错误消息(f), 正确消息的个数至少为(f+1) ,也就是(N - f) = f + (f+1), N= 3f + 1.

检查点协议

为了解决两个问题:

  1. 拜占庭系统每执行一个请求,服务器需要记录日志.如果日志得不到及时的清理,就会导致系统资源被大量的日志所占用,影响系统性能及可用性. 需要删除无异议消息记录.
  2. 如果一些副本节点错过部分消息, 但是这些消息已经被所有正常副本节点删除了, 这就需要通过传输部分或者全部服务状态实现该副本节点的同步.

处理日志主要解决的问题就是区分哪些日志可以清理,哪些日志仍然需要保留.如果一个请求已经被 f+1 台非拜占庭服务器执行,并且某一服务器 i 能够向其他的服务器证明这一点,那么 i 就可以将关于这个请求的日志删除.

如何证明呢? 目前,普遍采用的方式是服务器每执行一定数量的请求,就将自己的状态发送给所有的服务器并且执行一次该协议,请求执行后得到的状态称作检查点. 如果某台服务器接收到 2f+1 台服务器的状态,那么其中一致的部分就是至少有 f+1 非拜占庭服务器经历过的状态, 这2f+1个消息就是这个检查点的正确性证明,, 具有证明的检查点称为稳定检查点. 因此,稳定检查点之前的日志就可以删除,同时将自己状态更新至较新状态.

检查点协议可以用来更新水线 (watermark)的高低值 (h和H), 这两个高低值限定了可以被接受的消息. 水线的低值h与最近稳定检查点的序列号相同, 而水线的高值H=h+k, k需要足够大才能使副本不至于为了等待稳定检查点而停顿. 加入检查点每100个请求产生一次, k的取值可以是200.

视图切换

视图变更协议在主节点失效的时候仍然保证系统的活性. 主要有两种方式触发

  • 备用节点一定时间内都收不到主节点发来的nullRequest
  • 备用节点收到主节点的消息, 发现消息异常, 例如同一个请求编号给了我不同的请求

视图更换协议需要解决的问题是如何保证已经被非拜占庭服务器执行的请求不被更改.由于系统达成一 致性之后至少有 f+1 台非拜占庭服务器执行了请求,所以目前采用的方法是:由新的主节点收集至少 2f+1 台服 务器的状态信息,这些状态信息中一定包含所有执行过的请求;然后,新主节点将这些状态信息发送给所有的服务器,服务器按照相同的原则将在上一个主节点完成的请求同步一遍.同步之后,所有的节点都处于相同的状态,这时就可以开始执行新的请求.

参考:

https://www.jianshu.com/p/fb5edf031afd

范捷,易乐天,舒继武.拜占庭系统技术研究综述.软件学报,2013,24(6):1346−1360. http://www.jos.org.cn/1000-9825/4395.htm