搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库

Paxos原理

HunterPan 2018-11-28
举报

Pre预备

Paxos算法基础是分布式中一致性协议基础,但相比Zab,Raft来说,Paxos难理解,且不适合工程实现,现有的Paxos产品都是优化的Paxos--multi-Paxos。

学习资料推荐<Paxos Made Simple>

算法中包含三类角色:Proposer 提案者、Acceptor接受者(裁判)、Learners学习者,一个进程可充当多个角色。

Paxos消息:Proposal,包含一个ProposalId+Value

Paxos其实是一个对value的学习过程,系统中每个Proposer都可以提出Proposal,如果保证系统达成一致选择出一个唯一的Proposal是Paxos的目的。达成一致的标准是:quorum 集群超半数的Acceptor接受一个Proposal

算法推理过程

算法描述其实很简单,但如果理解和证明推理Paxos正确性其实是很难的。网上的资料也大都是从问题出手一步一步加条件推理出Paxos的条件和流程的。这里根据Paxos made simple来学习的。

1 开始提出目的:

假设一些进程可提出value,集群内有算法保证所有提出的value只有一个被选中,并且进程可以获取该value。这句话隐藏的表达的意思:

没有value提出,那么也没有value被选中

只能选中提出的value

只能选择一个value

进程只能获取被选中的value
2.选择一个value

单个Acceptor会引起系统故障,所以集群内有多个Acceptor,并且value被大多数接受这就要求满足要求

P1. acceptor必须接收第一个它收到的proposal

这个条件很简单的说明:假设系统只有一个Proposer ,只提出了一个Proposal。要想达到目的,要求了acceptor必须接受第一个。

但是引出的问题呢:假设集群内提出了多个Proposal,都没有一个被大多说接受,那么达不到我们的目标 选择一个value(被大多数接受)。这里也有说明了我们只说唯一value被接受,但没说唯一Proposal被接受,Proposal=num+value,所以可以接受多个Proposal,但value要一样。于是进行加强约束:

P2.如果一个value为v的proposal被选中,那么所有被选中的higher-numbered proposal都具有value v

为达到P2,必须满足

P2_a.如果一个value为v的proposal被选中,那么每一个被任何acceptor所接受的high-numbered proposal都有value v

系统还有问题:假设一个proposal可能被一些特定的,没有接受过任何proposal的acceptor选中,根据P1 该acceptor 必须接受这个proposal,但可能违背了P2_a,这个proposal有可能提出不同的value。为了加强P2_a 必须满足

P2_b.如果一个value为v的proposal被选中,那么之后每个proposer发出的high-numbered proposal都有value v

要求每个Proposer提出的更高的序号的proposal必须是同一个value。那么如何满足P2_b呢?

可以归纳证明出结论:

P2_c.对于任意的v和n,如果有一个value为v,number为n的proposal被发出了,那么就存在一个由majority个acceptor组成的集合S。要么(a)S中没有一个acceptor接受过number小于n的proposal,要么(b)v是S中的acceptor接受过的number小于n的最高number的proposal的value

满足P2_c就可以满足P2_b,要求了一个Proposor想要提出更高的n的poposal,必须满足n的proposal的v必须是获取已经或者将要被大多数接受的number小于n的proposal的value,对于已经被接受的的proposal的很简单给出v,对于将要被大多说接受的proposal比较困难,所以就抛弃对未来的预测,要求acceptor不接受number小于n的proposal。 意思简单来说如果n-1还在进行中(还没被大多数接受),此时n开始提出proposal,如果n-1提出的value和n不一样,这就很难预测n提出n-1的value,为避免情况,那些接受了n的acceptor拒绝接受n-1。

最终的提出propsal的算法如下:两个步骤

1、一个proposer选择了一个新的proposal number n并且给一些acceptor集合的每个成员发送了一个请求,并希望它们回复:
(1)、承诺再也不接受number小于n的proposal
(2)、如果已经接受了最高number小于n的proposal,返回proposal的value
我们将这样的请求称为number为n的prepare request
2、如果proposer接受了来自一个majority对于请求的回复,那么它就可以发送一个number为n,value为v的proposal。其中v要么是返回的最高number的proposal的value,如果没有proposal返回,那么proposer随意选择一个值。
proposer将proposal发送给一些acceptor的集合,请求它们接受。(这里的acceptor的集合不一定要和回复初始请求的acceptor的集合是同一个集合)我们将这样的请求称之为accept request。

从提出proposal结论来看acceptor接收到两种proposal的消息,prepare request和accept request。acceptor可以忽略这两种消息来告诉proposor提出的议案是否被通过,为达到最终只有一个value选中,我们讨论acceptor如何回复消息。原则是总允许对prepare request进行回复。可以对一个accept request进行回复,代表接受一个proposal

P1_a.acceptor可以接受number为n的proposal,如果它之前没有回复任何number大于n的prepare request

P1_a包含了P1

假设一个acceptor已经接收过number大于n的proposal,对于等于小于n的proposal一概拒绝,可以忽略相应。对于同样的propsal也选择忽略。

假设一个acceptor已经接收number为n的proposal,那么大于n的prepare request的响应 为了满足P2_c要求返回number为n的proposal的value。为了防止故障发生而导致意外,要求acceptor必须可以恢复以前接收过的proposal。

P1_b.acceptor接受过number为n的proposal后,忽略小于n的prepare request,相应大于n的prepare request的值为number为n的proposal的value


结合提出proposal的过程和acceptor接收过程我们最终得出Paxos的算法过程:
Phase 1.(a)proposer选择一个proposal number n,然后向一个majority发送number为n的prepare request。

(b)如果一个acceptor接受了一个number为n的prepare request,并且n大于任何它已经回复的prepare request的number,那么它将承诺不再接受任何number小于n的proposal,并且回复已经接受的最高number的proposal(如果有的话)。

Phase 2.(a)如果proposer接受了来自majority对它的prepare request的回复,那么接下来它将给这些acceptor发送一个number为n,value为v的proposal作为accept request。其中v是收到的回复中最高number的proposal的value,或者如果回复中没有proposal的话,就可以是它自己选的任意值。

(b)如果acceptor收到一个number为n的accept request,如果它没有对number大于n的prepare request进行过回复,那么就接受该accept reque

两阶段过程。一个proposer可以生成多个proposal,只要它能满足算法的要求。它也可以在协议的任意时刻放弃proposal。

如何Leaner学习

当选举出proposal后,Leaner角色如何学习到呢?

最简单办法:每个acceptor在接受了一个proposal之后向所有的learner发送这个proposal。这能让learner尽快地找到被选中的value,但这需要acceptor对每个learner进行回复——回复的数量为acceptor和learner数量的乘积

选择一个主Leaner,其他的Leaner从主Leaner学习:每个acceptor在接受了一个proposal之后向主learner发送这个proposal,其他Leaner从主Leaner学习到。通信数减少很多,缺点单点

折中,选择部分Leaner集群:每个acceptor在接受了一个proposal之后向该集群learner发送这个proposal,其他Leaner从集群Leaner学习到

优化与实现

在实际开发中,如果每一个Paxos客户都请求一个Paxos实例,都要进行两次prepare request 和 accept request过程,性能不佳,而且是线性执行。所以工程化的paxos都是Multi-Paxos,实现是在Proposor中选择出一个Leader作为leader Proposor,这个Leader Proposor不再进行prePare request,而只进行acceptor request,而且可以做到批量发出acceptor request,从而提高吞吐量。选举Leader很简单。当然还有实现Master形式来优化。


参考:

1  Paxos Made Simple https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf

2 Paxos Made Simple译文 https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf

3 分析 https://www.cnblogs.com/linbingdong/p/6253479.html

4 multi-paxos https://zhuanlan.zhihu.com/p/21466932?refer=lynncui

5 master选举 https://zhuanlan.zhihu.com/p/21540239

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《Paxos原理》的版权归原作者「HunterPan」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注HunterPan微信公众号

HunterPan微信公众号:gh_6bcc969b87ed

HunterPan

手机扫描上方二维码即可关注HunterPan微信公众号

HunterPan最新文章

精品公众号随机推荐

举报