架构师训练营 -Week 06 学习总结

发布于: 21 小时前

什么是Paxos算法?

Paxos算法是一种基于消息传递的分布式一致性算法,Paxos算法的目标就是让他们按照少数服从多数的方式,最终达成一致意见,用来解决分布式一致性问题,其他类似的有Raft、Zap等。

背景

1990年,Leslie Lamport在论文《The Part-Time Parliament》中提出Paxos算法。Lamport为了讲述这个算法,假想了一个叫做Paxos的希腊城邦进行选举的情景,这个算法也是因此而得名。在他的假想中,这个城邦要采用民主提议和投票的方式选出一个最终的决议,但由于城邦的居民没有人愿意把全部时间和精力放在这种事情上,所以他们只能不定时的来参加提议,不定时来了解提议、投票进展,不定时的表达自己的投票意见。由于论文使用故事的方式,没有使用数学证明,起初并没有得到重视。直到1998年该论文才被正式接受。后来2001年Lamport又重新组织了论文,发表了《Paxos Made Simple》,Paxos算法对与业界产生了很大的影响,对于其对分布式系统领域的卓越贡献,Lamport在2013年获得图灵奖。

角色及类型

Paxos中有三类角色Proposer(提议者 )、Acceptor(投票者)及Learner(学习者),一个节点可以担任多个角色。

  • Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

  • Acceptor:参与投票,回应Proposers的提案。收到Proposal后可以接受提案,若Proposal获得多数Acceptors的接受,则称该Proposal被批准。

  • Learner:不参与投票,从Proposers/Acceptors学习最新达成一致的提案(Value)

Paxos分为Basic Paxos和Multi Paxos两种类型,Basic Paxos多个人同时提议只能通过一个提议,Multi Paxos多个人同时提议可以同时通过多个提议。

流程

Paxos主要分为两个阶段,Prepare(准备)阶段和Accept(选举)阶段。

Proposer需要发出两次请求,Prepare请求和Propose请求。Acceptor根据其接送的请求信息,接受或者拒绝提案。

在准备阶段,Proposer 生成全局唯一且递增的Proposal ID,向 Paxos 集群的所有机器发送 Prepare请求,这里不携带value,只携带N即Proposal ID 。

Acceptor 收到 Prepare请求 后,判断:收到的Proposal ID 是否比之前已响应的所有提案的N大:

如果是,则:

(1) 在本地持久化 N,可记为Max_N。

(2) 回复请求,并带上已Accept的提案中N最大的value。

(3) 做出承诺:不会Accept任何小于Max_N的提案。

如果否:不回复或者回复Error。

在选举阶段

  1. Proposer 发送 Propose

经过一段时间后,Proposer 收到一些Acceptor的Promise承诺,有下列几种情况:

(1) 承诺数量大于一半的Acceptor数量,且所有的回复的value都为空,则Porposer发出Propose请求,并带上自己指定的value。

(2) 承诺数量大于一半的Acceptor数量,且有的回复value不为空,则Porposer发出Propose请求,并带上回复中Proposal ID最大的value(作为自己的提案内容)。

(3) 承诺数量小于等于一半的Acceptor数量,则尝试更新生成更大的Proposal ID,重新发起提案。

  1. Acceptor 应答 Accept

Accpetor 收到 Propose请求 后,判断:

(1) 收到的N大于等于Max_N,则回复提交成功,并持久化N和value。

(2) 收到的N小于Max_N,则不回复或者回复提交失败。

  1. Proposer 统计投票

经过一段时间后,Proposer 收集到一些 Accept 回复提交成功,有几种情况:

(1) 回复数量大于一半的Acceptor数量,则表示提交value成功。此时,可以发一个广播给所有Proposer、Learner,通知它们已commit的value。

(2) 回复数量小于等于一半的Acceptor数量或者收到一条提交失败的回复,则尝试更新生成更大的 Proposal ID,重新发起提案。

疑问

1. 为什么要多个Acceptor?单个有什么问题?

2. 为什么进而演进到两阶段?

3. 为什么发送 Propose请求还需要一个唯一递增ID,这个设计解决了什么问题?

4. 思想有了,Paxos算法怎么应用到实际工程中?

后面还需要深入研究,掌握它,最终编码实现这个算法,学习raft、zap,最终能够手写一个zookeeper。

用户头像

华乐彬

关注

还未添加个人签名 2019.03.13 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 -Week 06 学习总结