当前位置: 代码迷 >> 综合 >> 读书笔记——区块链原理、设计与应用(二)——Paxos、Raft、PBFT
  详细解决方案

读书笔记——区块链原理、设计与应用(二)——Paxos、Raft、PBFT

热度:84   发布时间:2024-02-02 14:30:08.0

共识算法

  • Paxos算法
    • 两阶段的提交
  • Raft 算法
    • 两阶段
  • 拜占庭问题与算法

Paxos问题指分布式系统中存在故障,但不存在恶意节点的场景(即消息可能丢失或重复,但无错误消息)下的共识达成问题。解决Paxos问题的算法主要有Paxos系列算法和Raft算法。

Paxos算法

算法的基本原理是将节点分为三种逻辑角色,在实现上同一个节点可以担任多个角色:
proposer(提案者):提交一个提案,等待大家批准为结案。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任。
acceptor(接受者):负责对提案进行投票,接受提案。往往由服务器担任。提议超过半数的接受者投票及被选中。
learner(学习者):获取批准结果,并可以帮忙传播,不参与投票过程。客户端和服务端都可担任。
算法需要满足safety和liveness两方面的约束要求。
safety约束:保证决议结果是对的,无歧义的,不会出现错误情况。

  • 只有是被proposers提出的提案才肯被最终批准;
  • 在一次执行中,只批准一个最终决议。被多数接受的结果成为决议。
    liveness约束:保证决议过程能在有限时间内完成。
  • 决议总会产生,并且学习者能获得被批准的决议。

基本思路类似两阶段提交:多个提案者先要争取到提案的权利(得到大多数接受者的支持);成功的提案者发送提案给所有人进行确认,得到大部分人确认的提案成为批准的结案。
下面,由简单情况逐步推广到一般情况来探讨算法过程。

  1. 单个提案者+多接受者

如果系统中限定只允许某个特定节点是提案者,那么共识结果很容易能达成(只有一个方案,要么达成,要么失败)。提案者只要收到了来自多数接受者的投票,即可认为通过,因为系统中不存在其他的提案。
但此时一旦提案者故障,则整个系统无法工作。

  1. 多个提案者+单个接受者

限定某个特定节点作为接受者。这种情况下,共识也很容易达成,接受者收到多个提案,选第一个提案作为决议,发送给其它提案者即可。
缺陷也是容易发生单点故障,包括接受者故障或首个提案者节点故障。
以上两种情形其实类似主从模式,虽然不那么可靠,但因为原理简单而被广泛采用。
当提案者和接受者都推广到多个的情形,会出现一些挑战。

3. 多个提案者+多个接受者

既然限定单提案者或单接受者都会出现故障,那么就得允许出现多个提案者和多个接受者。
一种情况是同一时间片段(如一个提案周期)内只有一个提案者,这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生,例如按照时间、序列、或者大家猜拳(出一个参数来比较)之类。考虑到分布式系统要处理的工作量很大,这个过程要尽量高效,满足这一条件的机制非常难设计。
另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案,怎么对他们进行区分呢?这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的,提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大(往往意味着是接受新提出的,因为旧提案者故障概率更大)的提案。
如何为提案分配序号呢?一种可能方案是每个节点的提案数字区间彼此隔离开,互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。
同时允许多个提案,意味着很可能单个提案人无法集齐足够多的投票;另一方面,提案者即便收到了多数接受者的投票,也不敢说就一定通过。因为在此过程中投票者无法获知其它投票人的结果,也无法确认提案人是否收到了自己的投票。因此,需要实现两个阶段的提交过程。

两阶段的提交

Paxos 里面对这两个阶段分别命名为准备(Prepare)和提交(Commit)。准备阶段通过锁来解决对哪个提案内容进行确认的问题,提交阶段解决大多数确认最终值的问题。

准备阶段:

? 提案者发送自己计划提交的提案的编号到多个接受者,试探是否可以锁定多数接受者的支持。
? 接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大,则返回自己已接受的提案值(如果还未接受过任何提案,则为空)给提案者,更新当前最大提案号,并说明不再接受小于最大提案号的提案。

提交阶段:

? 提案者如果收到大多数的回复(表示大部分人听到它的请求),则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案,说明锁定成功。则使用自己的提案内容;如果返回中有提案内容,则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复,则需要再次发出请求。
? 接受者收到接受消息后,如果发现提案号不小于已接受的最大提案号,则接受该提案,并更新接受的最大提案。
一旦多数接受者接受了共同的提案值,则形成决议,成为最终确认。

Raft 算法

Raft 算法面向对多个决策达成一致的问题,分解了领导者选举、日志复制和安全方面的考虑,并通过约束减少了不确定性的状态空间。
算法包括三种角色:领导者(Leader)、候选者(Candidate) 和 跟随者(Follower),决策前通过选举一个全局的领导者来简化后续的决策过程。领导者角色十分关键,决定日志(log)的提交。日志只能由领导者向跟随者单向复制。

两阶段

典型的过程包括两个主要阶段:
? Leader选举:开始所有节点都是跟随者,在随机超时发生后未收到来自Leader或候选者消息,则转变角色为候选者,提出选举请求。最近选举阶段(Term)中得票超过一半者被选为Leader;如果未选出,随机超时后进入新的阶段重试。领导者负责从客户端接收 log,并分发到其他节点;
? 同步日志:Leader会找到系统中日志最新的记录,并强制所有的跟随者来刷新到这个记录,数据的同步是单向的。
注:此处日志并非是指输出消息,而是各种事件的发生记录。

拜占庭问题与算法

PBFT算法采用密码学相关技术(RSA签名算法、消息验证编码和摘要)确保消息传递过程中不会被篡改和破坏。
算法的基本过程如下:

  • 首先通过轮换或随机算法选出某个节点为主节点,此后只要主节点不切换,则成为一个视图(view);
  • 在某个视图中,客户端将请求<REQUEST,operation,timestamp,client>发送给主节点,主节点负责广播请求到所有其他副本节点;
  • 所有节点处理完请求,将处理结果<RWPLY,view,timestamp,client,id_node,response>返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果,作为最终结果。

主节点的广播过程包括三个阶段的处理:预准备阶段、准备阶段和提交阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正确;准备和提交阶段则确保在不同视图之间的确认请求是保序的。