`
kenby
  • 浏览: 723758 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Paxos算法

 
阅读更多

分布式系统的核心问题是数据一致性,解决一致性有很多算法,而 Paxos 算法

无疑是最著名的,Google 工程师曾说,所有一致性算法都可以归结为 Paxos 算法

的一个特列。可见,很有必要学习 Paxos 算法。

 

Paxos 算法是由 Lamport 提出来的,他得论文 Paxos made simple 是最好的

学习资料。我在阅读的过程中遇到很多困难,文中的一些逻辑推论隐藏得比较深,

需要反复研读,这里对算法的描述就不写了,只是记录一些个人的理解。

 

论文首先指出一致性最核心的要求是,Only a single value is chosen,就是说,

协商的结果,最终只能确定一个值,不能选多个值。后面的一些条例都是为了满足

这个要求。

 

我们规定,每个 acceptor 最多只能 accept  一个 value,如果存在一个 acceptor

的多数派,其中每个 acceptor 都 accept 了同一个 value 时,该 value就能被 chosen ,

这里多数派,我的理解是超过一半的 acceptor。所以说,一个 value 要想被 chosen,必须有超过一半

的 acceptor 支持(accept)它。由于每个 acceptor 最多只能投一票,因此不可能存在两个 value

它们的支持率均超过 50%,最终只能有一个 value 获胜。这就保证了 Only a single value is chosen.

 

一致性问题产生的原因是多个 proposer 可能提出各种不同的 value,导致系统不知道选择哪个 value,

有一个特例,如果只有一个 proposer 提出 value,显然就不存在一致性问题,这个时候,必须选择这个

唯一的 value。考虑只有一个 proposer 提出 value的情况,该 proposer 向所有 acceptor 发出 proposal,

由于没有其他的 proposal,所以每个 acceptor 会而且只会收到唯一的 proposal,如前所说,这个 proposal

理应被 chosen,但是要想它被chosen,就要求多数派的 acceptor 都支持(accept)此 proposal。于是有了准则 P1:

 

P1. An acceptor must accept the first proposal that it receives.

 

说的是,对于第一个 receive 到的 proposal, acceptor 必须无条件 accept。

有了这个准则,就可以保证形成一个多数派的 acceptor 来支持这个唯一的 proposal。于是在只有一个

proposer 提出 value 时,该 value 必将被 chosen。

 

准则 P1 只是为了满足上面提到的特列,即只有一个 proposer 的时候,而如果有多个 proposer,准则 P1 就

不一定能保证一致性了。考虑两个 proposer 分别提出 value1 和 value2,如果 value1 和 value2 各得到

一半的 acceptor 支持,这样两者都不能形成一个多数派,就无法确定获胜者了。

 

为了形成多数派,解决的办法是允许 acceptor 投多张票,即让 acceptor 可以同时支持多个 proposal。

但这样又会产生一个问题,可能两个proposal 都形成了多数派,比如 proposal1 获得超过一半的 acceptor 支

持,proposal2也获得了超过一半的 acceptor 支持,那到底选哪个 proposal 呢,其实我们的要求是确定一个

value 出来,只要 proposal1 和proposal2都具有相同的 value,就能保证 only a single value is chosen。

 

所以我们允许多个 proposal 被 chosen,即多个 proposal 同时获得超过一半 acceptor 的支持,但是要求

这些 proposal 都具有相同的 value。 如何保证这点呢,看准则 P2

 

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen

      has value v

 

为了区分 proposal,我们给每个 proposal 一个唯一的编号,这样 proposal 由编号和 value 组成,可简单表示

为 <n, value>,其中 n 就是编号。

 

准则 P2 说的是,如果 <n, v> 被 chosen,则要求其他被 chosen 的,而且编号比 n 大的 proposal 的 value

也是 v。比如这几个proposal <n, v>, <n1, v1>, <n2, v2>, <n3, v3> 都被 chosen,而且有 n < n1 < n2 < n3。

根据准则P2, <n, v> 被 chosen,要求 v1 == v, v2 == v, v3 == v。 于是保证了所有被 chosen 的 proposal

的 value 都是 v。

 

准则 P2 是对 chosen 的结果做要求,为了得到这样的结果,我们需要在算法运行过程中对 acceptor 做要求。

于是有了准则 P2a,P2a 蕴含着 P2

 

P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted

        by any acceptor has value v.

 

说的是,如果 <n, v> 被 chosen,则要求任何被 acceptor 支持(accept)的,而且编号比 n 大的 proposal

的 value 也是 v。 这一条准则保证了所有 acceptor 支持的 proposal 都具有相同的 value。进而所有被 chosen

的 proposal 具有相同的 value,所以说,P2a 蕴含 P2。

 

准则 P2a 有一个漏洞,假设 <n, v> 被 chosen,说明 <n, v> 得到了大多数 acceptor 的支持,但由于网络原因,

可能某个 acceptor a,没有收到任何 proposal,网络恢复的时候,恰好 a 收到一个编号更高的 proposal <m, v1>,

其中 m > n, v1 与 v 不相同,根据准则 P1, a 必须支持 <m, v1>,而 <m, v1> 与 <n, v> 的 value 是不相同的,

这就违反了 P2a。所以 P1 和 P2a 不能很好的配合,我们需要寻找一个更合适的准则来与 P1 配合,共同保证一致性。

于是出现准则 P2b。

 

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by

        any proposer has value v.

 

说的是,如果 <n, v> 被 chosen, 则要求任何 proposer 提出的,编号比 n 大的 proposal 的 value 也是 v。

这一条准则要求所有 proposer 提出的 proposal 都具有相同的 value。

 

准则 P2b 非常严格,因为它从源头上要求各个 proposal 具有相同的 value。但是做到这点不容易,必须对

proposer 做严格要求,绝不允许proposer 随意提出 proposal, proposer 提出一个 proposal前,得先看看该

proposal 是否满足条件,如果不满足,则不允许 proposer 提出 proposal。于是出现了准则 P2c:

 

P2c. For any v and n, if a proposal with value v and number n is issued, then there is a

       set S consisting of a majority of acceptors such that either (a) no acceptor in S has

       accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered

       proposal among all proposals numbered less than n accepted by acceptors in S.

 

P2c 说明了在何种条件下,proposer 才能提出 proposal <n, v>。只要满足两个条件中的任意一个,就可以提出

proposal。

 

条件1说的是, 如果大多数 acceptor 都没有 accept 过任何 proposal,根据 P1, 也可以理解为

大多数 acceptor 都没有 receive 到任何 proposal,就允许该 proposal 提出,而且 proposal 的值

可以是任意的。比如一个多数派 acceptor,其中每个 acceptor 都没有 receive 到 proposal,这个时候

proposer 把 <n, v> 发送给多数派 acceptor,根据 P1,多数派中每个 acceptor 都无条件 accept 此 proposal。

然后 <n, v> 被 chosen,满足一致性的要求:Only a single value is chosen。

 

条件2说的是,先取得大多数 acceptor accept过的,编号最大的 proposal 的 value,记为 v1,

如果 v 和 v1 相同,就允许该 proposal 提出。

 

P2C 可以保证一致性,可以用递推证明,P2C 的两个条件恰好对应证明过程的初始状态和递推状态:

最开始,所有 acceptor 都没有 accept 过任何 proposal,根据 P2C的条件1,proposer 可以

提出任何 proposal <n, v>, 而且都会被 chosen。然后另一个 proposer 也想提出 proposal <n1, v1>,

由于这个时候不满足条件1,我们看能否满足条件2,先取得大多数 acceptor accept 过的,编号最大的

proposal,即为 <n, v>,然后看 v1 和 v 是否相等,如果相等,就可以提出 <n1, v1>。当 <n1, v1> 被

chosen 后,Since v1 is equal to v, The chosen value is still v. 同理后续提出的 proposal 的 value

都是 v,最后算法完成,The chosen value is v, 保证了 Only a single value is chosen。

 

分享到:
评论

相关推荐

    云计算:C++实现的可直接运行paxos算法

    **云计算中的Paxos算法** Paxos算法是一种在分布式系统中解决一致性问题的经典协议,由Leslie Lamport提出。它的主要目标是在存在网络延迟、消息丢失或重复、节点故障等不可靠因素的情况下,确保一组分布式节点能够...

    Paxos算法中文翻译

    Paxos算法是一种在异步分布式系统中实现共识(Consensus)的算法,由Leslie Lamport提出。它能够确保系统中的多个节点即使在某些节点出现故障时,也能就某个值(例如一个操作请求)达成一致意见。Paxos算法的核心...

    Paxos算法.pdf

    ### Paxos算法详解与Zookeeper应用 #### 一、Paxos算法概述 Paxos算法是一种用于解决分布式系统中一致性问题的经典算法。该算法由Leslie Lamport于1990年提出,并逐渐成为分布式一致性算法领域的核心理论之一。在...

    人工智能-项目实践-多线程-Paxos算法的多线程实现.zip

    **Paxos算法详解** Paxos算法是Leslie Lamport提出的一种分布式一致性协议,它在分布式系统中解决了一个核心问题:如何在一个网络环境中保证多个节点间的数据一致性,即使在网络存在延迟、消息丢失或重复、节点故障...

    面向云计算基础课程的Paxos算法教学设计研究.pdf

    通过详细阐述Paxos算法的工作原理,并设计具体的教学案例,该教学方案在实际教学实践中获得了良好的教学效果,加深了学生对Paxos算法工作原理的理解。 Paxos算法是由莱斯利·兰伯特(Leslie Lamport)提出的一种...

    基于Paxos算法的ATS数据分布式存储模型.pdf

    为了深入理解基于Paxos算法的ATS数据分布式存储模型,我们首先需要探讨相关的概念和技术背景。 Paxos算法是一种解决分布式系统中一致性问题的算法,由莱斯利·兰伯特(Leslie Lamport)提出。在分布式系统中,多个...

    paxos 算法解释

    **Paxos算法详解** Paxos算法是分布式系统中的一种一致性协议,由Leslie Lamport提出,旨在解决在存在网络延迟、消息丢失或重复、节点故障等不确定因素的环境中,如何让分布式系统的多个节点就某个值达成一致。...

    cheap-paxos.pdf_Paxos算法_

    这篇名为"cheap-paxos.pdf"的论文深入探讨了Paxos算法的一个变种——廉价Paxos(Cheap Paxos),它在保持Paxos算法基本性质的同时,优化了性能,降低了复杂性,尤其适用于大规模分布式系统。 Paxos算法最初由Leslie...

    paxos 算法 分析

    很不错的paxos算法分析文档,值得一看,虽不能深入研究,但是可以初步了解!

    paxos算法学习.docx

    **Paxos算法详解** Paxos算法,以其创始人Leslie Lamport的灵感来源——希腊小岛Paxos命名,是一种解决分布式系统中一致性问题的关键算法。在Paxos算法中,Lamport构建了一个虚拟的希腊城邦,通过模拟岛上的议会...

    深入理解 paxos 算法 PDF

    ### 深入理解Paxos算法 #### 引言 在分布式系统领域,一致性算法是确保多个节点间数据同步的基础。其中,Paxos算法因其简洁性和有效性而备受推崇,成为了众多分布式系统设计的核心。本文旨在深入探讨Paxos算法的...

    Paxos算法介绍1

    ### Paxos算法详解 #### 一、Paxos算法概览与背景 Paxos算法是一种用于解决分布式系统中一致性问题的重要算法,由莱斯利·兰伯特(Leslie Lamport)在1990年提出。该算法旨在解决在分布式系统中,即使面对节点故障...

    paxos算法及其实际实现

    Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有效的。 背景介绍编辑 播报 Paxos 算法解决的...

    一种基于Paxos算法的高可用分布式锁服务系统.pdf

    根据给定文件的内容,本知识点将专注于分布式系统中的Paxos算法,高可用性、一致性问题以及分布式锁服务系统的设计与实现。 1. 分布式系统与Paxos算法:分布式系统由多个分布在网络中的节点组成,它们通过通信和...

    zookeeper基于paxos算法的资料。

    Paxos算法是一种解决分布式系统中一致性问题的算法,它的主要目标是在网络通信不可靠的情况下,确保集群中的节点能就某个提案达成一致。在Zookeeper中,Paxos算法被用来选举 Leader 和维护集群的状态一致性。Paxos...

    基于消息传递的Paxos算法研究

    基于消息传递的Paxos算法是一种用于解决分布式系统中一致性问题的共识算法。Paxos算法由Leslie Lamport提出,旨在在分布式系统中达成一致意见,即便是在有节点失效的情况下。它被广泛应用在分布式计算系统中,以保证...

    微信PaxosStore:深入浅出Paxos算法协议-InfoQ1

    【微信PaxosStore:深入浅出Paxos算法协议】 Paxos算法是由Leslie Lamport提出的分布式一致性协议,其目标是确保在一个可能存在网络延迟、消息丢失或重复、节点故障的分布式系统中,所有节点能够就某个值达成一致。...

    paxos 算法推导中文版

    Paxos 算法是一种经典的分布式一致性...Paxos算法虽然复杂,但它是解决分布式一致性问题的基础,对后来的Raft、ZAB等一致性算法产生了深远影响。理解并应用Paxos算法,对于构建大规模、高可用的分布式系统至关重要。

    Paxos算法(参考).doc

    Paxos算法是一种分布式一致性算法,由Leslie Lamport提出,主要用于解决分布式系统中节点间的一致性问题,确保即使在存在网络延迟、故障或消息丢失的情况下,也能达成一致的决策。它在Google的Chubby、MegaStore、...

Global site tag (gtag.js) - Google Analytics