

首页  思维导图  详情



一致性协议

2020-10-12 00:59:07   0  举报





仅支持查看

AI智能生成

一致性协议

zookeeper

模版推荐

作者其他创作

大纲/内容

一致性协议

Paxos

按公示问题数可分为

Basic Paxos

Muti Paxos

为了提高效率

角色

Proposer

Acceptor

Learner

推导过程

1.  如果只有1个Proposer会有什么问题？

Q: Proposer宕机的话，整个服务不可用。

2.  那如果多Proposer和多Acceptor如何选定一个Value？

P1:一个Acceptor必须接受他收到的第一个提案

Q: 不同的Proposer分别提出不同的value

P1a:一个提案被选定需要半数以上的Acceptor

暗示：一个Acceptor必须能够接受不止一个提案！

提案=value已不满足，需要重新设计，提案=[提案编号+value]

P2:如果某个value为v的提案被chosen，那么每个编号更高的被选定的提案，value也必须是v

P2a:如果某个value为v的提案被chosen，那么每个编号更高的被Acceptor接受的提案，value也必须是v

对Acceptor接收的提案约束

P2b:如果某个value为v的提案被chosen，那么之后任何Proposer提出编号更高的提案value也必须是v

对Proposer提出提案的约束

Q如何保证？ A-P2c

P2c:对于任意N和V，如果提案[N,V]被提出，那么存在一个半数以上的Acceptor集合S，满足以下2个条件中的一个:①S中的每个Acceptor没有接受过编号小于N的提案；②S中接受过的最大编号的提案value为V

paxos算法证明过程

如何保证Paxos算法的活性？

通过选取主Proposer，只有主Proposer才能提出提案

算法流程

阶段1. Prepare请求

a. Proposer 选择一个提案编号 N，然后向半数以上的Acceptor 发送编号为 N 的 Prepare 请求。

b.如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该Acceptor 承诺不再接受任何编号小于 N 的提案。

阶段2. Acceptor确认

a.如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value ，如果响应中不包含任何提案，那么V 就由 Proposer 自己决定。

b.如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案

ZAB

在Leader选举时节点状态

LOOKING

Leader选举阶段

OBSERVING

不参与投票

FOLLOWING

参与投票

LEADING

ZAB协议的四个阶段

1. 选举阶段