拜占庭容错机制

简介

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中作废这样的请求。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Golang学习-第一篇 Golang的简单介绍及Windows环境下安装、部署

序言 这是本人简书第一篇文章,写的不到位之处,希望各位看客们谅解。 本人一直从事.NET的开发工作,最近在学习Golang,所以想着之前学习的过程中都没怎么好好...

31350
来自专栏Golang语言社区

从websocket看go的应用

Go是互联网时代的通用编程语言。这样它就和命令行时代的C语言、图示界面时代的C++、以及互联网早期的Java语言等有不同的侧重。它强调保持自身的精巧和独立,从而...

39170
来自专栏Java帮帮-微信公众号-技术文章全总结

Web-第二十天 Redis学习【悟空教程】

rpm -e --nodeps java-1.6.0-openjdk-1.6.0.0-1.66.1.13.0.el6.i686

20350
来自专栏北京马哥教育

实用 Linux 命令行使用技巧集锦

最近在Quora上看到一个问答题目,关于在高效率Linux用户节省时间Tips。将该题目的回答进行学习总结,加上自己的一些经验,记录如下,方便自己和大家参考。 ...

37680
来自专栏腾讯云API

腾讯云 API 最佳实践: 善用幂等性

有些开发者问我云服务器“创建实例”接口有一个参数“ClientToken”不知道有什么作用。本文作一个简单的解答。

4.6K150
来自专栏逻辑熊猫带你玩Python

Python | Debugger和pdb,鸡肋否?

我们知道虽然入门级编程语言最好是C和Python,但是C和Python是有这本质的不同的,那就是C语言是编译型语言,而Python是解释型语言。

28120
来自专栏非著名程序员

Android Studio你不知道的调试技巧

? 写代码不可避免有Bug,通常情况下除了日志最直接的调试手段就是debug;那么你的调试技术停留在哪一阶段呢?仅仅是下个断点单步执行吗?或者你知道 Eval...

329100
来自专栏技术小黑屋

一个Android代码JIT友好度检测工具

利用周末的时间,写了一个检测Android代码JIT友好度的工具,取个名字为DroidJitChecker。希望可以帮助大家快速发现有坏味道的代码,并且及时修正...

12440
来自专栏Golang语言社区

从websocket看go的应用

Go是互联网时代的通用编程语言。这样它就和命令行时代的C语言、图示界面时代的C++、以及互联网早期的Java语言等有不同的侧重。它强调保持自身的精巧和独立,从而...

32060
来自专栏我和PYTHON有个约会

05.第一个Python程序

python作为一种编程语言,通过编写程序的方式来解决问题 python编写的程序,是文本文件,后缀名称为[.py]

11520

扫码关注云+社区

领取腾讯云代金券