如何解决区块链的分布式一致问题?
计算机/软件
0 254
0

区块链上用户如何达成共识。

收藏
2021-01-27 11:44 更新 空心人 •  1664
共 1 个回答
高赞 时间
0

Paxos算法解决分布式一致问题

Paxos中的节点角色

Proposer提案者

Proposer可以有很多个,Proposer提出Value。所谓Value,在工程中可以是任何操作。不同的Proposer可以提出不同的甚至矛盾的Value,例如某个Proposer提议“将变量X设置为1“,另一个Proposer提议“将变量X设置为2“,但是对同一轮Paxos过程,最多只有一个Value被批准。

Acceptor批准者

Acceptor有N个,Proposer提出的Value必须获得超过半数的Acceptor批准后才能通过。并且,Acceptor之间完全对等独立。

Acceptor批准者

Learner学习被批准的Value。所谓学习就是通过读取各个Proposer对Value的选择结果,如果某个Value被超过半数Acceptor通过,则Learner学习到了这个Value。这里类似议会机制,某个Value需要超过半数的Acceptor批准,Learner需要至少读取N/2+1个Acceptor的结果之后,能学习到一个通过的Value。 Paxos描述的就是在一个由多个Proposer和多个Acceptor构成的系统中,如何让多个Acceptor针对Proposer提出的多种提案达成一致的过程,而Learner只是“学习“最终被批准的提案。

Paxos中的约束条件

1.Acceptor必须接受它收到的第一个提案 2.如果一个提案的v值被大多数Acceptor接受过,那后续的所有被接受的提案之中也必须包含v值(v值可以理解为提案的内容,提案由一个或者多个v和提案编号组成) 3.如果某一轮Paxos协议批准了某个Value,则以后的各轮Paxos只能批准这个Value;每轮Paxos协议分为准备阶段和批准阶段,在这两个阶段Proposer和Acceptor有各自的处理流程

Paxos中的两个阶段

准备阶段

Proposer向网络内超过半数的Acceptor发送prepare消息;Acceptor正常情况下回复promise消息

批准阶段

有足够多Acceptor回复promise消息时,Proposer发送accept消息;正常情况下Acceptor回复accepted消息

Paxos中的选举过程

准备阶段

1.Proposer发送prepare请求。Proposer生成全局唯一且递增的ProposalID,向Paxos集群的所有机器发送Prepare 请求,这里不携带Value,只携带ProposalID。 2.Acceptor应答Prepare。收到Prepare请求后,判断:收到的ProposalID是否比之前已相应的所有提案的ProposalID大, 如果是,则: (1)在本地持久化ProposalID,可记为Max_ProposalID。 (2)回复请求,并带上已Accept的提案中ProposalID最大的Value(若此时还没有已Accept的提案,则返回的value是空) (3)做出承诺:不会Accept任何小于Max_ProposalID。的提案。 如果否:则不回复或者回复Error。

选举阶段

1.Proposer 发送Accept经过一段时间后,Proposer 收集一些Prepare回复,有下列几种情况: (1) 回复数量大于一半的Acceptor数量,且所有的回复Value都为空,则Proposer发出accept请求并带上自己指定的value (2) 回复数量大于一半的Acceptor数量,有的回复Value不为空,则proposer发出accept请求,并带上回复中ProposalID最大的value (3) 回复数量小于等于一半的Acceptor数量,则尝试更新生成更大的ProposalID 2. Acceptor应答accept,Acceptor收到Accept请求后判断: (1)收到的N大于等于Max_N(一般情况下是等于)。则回复提交成功,并持久化N和value (2)收到的N小于Max_N,则不回复或者回复提交失败 3. Proposer统计投票。经过一段时间后,Proposer收集到一些Acccept回复提交成功,有几种情况: (1)回复数量大于一半的Acceptor数量,则表示提交value成功。此时,可以发一个广播给所有Proposer、Learner,通知他们已commit的value (2)回复数量小于等于一半的Acceptor数量,则尝试更新生成更大的ProposalID。再转第一步进行 (3)收到一条提交失败的回复,则产生或更新生成更大的ProposalID再转第一步执行。

收藏
2021-01-27 12:22 更新 小眼的铁板烧 •  1814