分布式一致性算法08:PBFT

一、概述
上一节说了OM算法,但OM算法效率太低了,在实际工程上几乎无法使用。
1999年,Miguel Castro和Barbara Liskov提出了PBFT(Practical Byzantine Fault Tolerance)算法,大幅提高拜占庭容错算法的效率和实用性。
PBFT算法更好的平衡了效率和容错能力,在n个节点的网络中,同样可以允许的故障的节点数可以达到f =(n-1)/3个。

二、PBFT算法的工作原理
PBFT算法主要包括三个阶段:预准备(Pre-Prepare)、准备(Prepare)和提交(Commit)。
PBFT算法的复杂度为O(n^2),虽然消息数量还是很多,所以不适合大规模的网络,但比OM算法已经有大幅提升。

1、发起请求
客户端向主节点发起请求。

2、预准备阶段(Pre-Prepare)
主节点(Primary Node)收到消息后,为其分配一个视图消息编号vid,并广播预准备消息给所有副本节点。
广播消息格式为(Pre-Prepare,视图编号v,视图消息编号vid,请求内容msg,请求内容摘要msg-hash,时间有效区间T,主节点签名sign)

3、准备阶段(Prepare)
副本节点接收到Pre-Prepare预准备消息后,进行验证:
a、消息签名不正确,不通过
b、通过v和vid判断是否有相同编号消息,但不同内容的消息,不通过
c、超出时间有效期间T,不通过
d、msg与msg-hash不一致,不通过
e、通过
消息验证通过后,副本节点进入准备阶段,并进行消息广播
广播消息格式为(Prepare,视图编号v,视图消息编号vid,请求内容msg,请求内容摘要msg-hash,时间有效区间T,副本消息签名sign)

4、提交阶段(Commit)
每个节点在收到Prepare准备消息后,进行验证:
a、消息签名不正确,不通过
b、通过v和vid判断是否有相同编号消息,但不同内容的消息,不通过
c、超出时间有效期间T,不通过
d、msg与msg-hash与之前Pre-Prepare不一致,不通过
e、通过
每个节点在接收到足够数量的提交消息(通常是2f+1个)后,进入Commit阶段,并进行消息广播
广播消息格式为(Commit,视图编号v,视图消息编号vid,请求内容msg,请求内容摘要msg-hash,时间有效区间T,节点消息签名sign)

5、回复阶段
每个节点在收到Commit提交消息后,进行验证:
a、消息签名不正确,不通过
b、通过v和vid判断是否有相同编号消息,但不同内容的消息,不通过
c、超出时间有效期间T,不通过
d、msg与msg-hash与之前Prepare不一致,不通过
e、通过
节点收到(2f+1)条相同结果的Commit消息后,确认请求已成功执行,返回给客户端。

客户端收到(f+1)条相同结果的消息后,得到最终结果。
这里设置为f+1,因为节点最多收到f条一样的错误消息,不可能收到f+1条错误的消息。

三、主节点选举
如果主节点出现了异常,或则主节点故意作恶,PBFT是无法达成一致的。
此时,就要通过视图变更(View Change,类似于主节点任期的概念),选择新的主节点。

1、故障检测
当遇到以下情况时,备份节点会触发视图变更:
主节点,在约定时间内不响应客户端及备份节点请求
备份节点发送了准备消息后,在约定的时间内未接收到来自其他节点的2f个相同的准备消息。
备份节点发送了提交消息后,在约定的时间内未接收到来自其他节点的2f个相同的提交消息。
备份节点接收到异常消息,比如视图值、序号和已接受的消息相同,但内容摘要不同。

2、发起变更消息
触发视图变更的节点会向其他节点广播视图变更消息(View-Change消息)
这个消息包含了当前视图号v+1、序列号n(最后一个稳定的检查点的序列号)、以及已经准备好的消息集合P。

3、收集变更消息
其他节点在收到视图变更消息后,会检查消息的有效性。
如果消息有效,节点会记录该消息到本地日志中,并启动一个定时器,等待接收2f+1个视图变更消息来确认视图变更的成功。

4、选举主节点
当一个节点接收到2f+1个视图变更消息后,它会确认视图变更成功,并通过预定规则开始选举新的主节点:
(v + 1) mod |R|,其中v为当前视图的值,|R|为节点数选出下一个视图的主节点
节点启用新的视图号v+1,并将选举结果,广播通知其他节点。

5、广播NEW-VIEW消息
新的主节点接收到2f个其他节点的视图变更消息后,会广播一个NEW-VIEW消息,这个消息包含了上一个视图中所有未确认的请求信息。

6、处理未确认的请求
在新的视图中,副本节点需要处理在旧视图中未能达成一致的那些请求。
一旦新主节点广播了新视图消息,副本节点将执行这些请求,并进入提交阶段。

7、变更完毕,恢复正常

Leave a Reply

Your email address will not be published. Required fields are marked *

*