文档章节

paxos算法证明过程

乒乓狂魔
 乒乓狂魔
发布于 2016/11/16 08:41
字数 3384
阅读 1596
收藏 17
点赞 1
评论 1

paxos算法有运作过程和证明过程,运作过程比较清晰明了,但是证明过程就比较复杂了。

很多人能够看懂paxos算法的运行过程,分prepare过程和accept过程,但是总是对证明过程模模糊糊,或者在看证明过程时和运作过程相混淆,特别是下文中的P2c证明P2b的过程,可能会犯下拿运作过程当做已知条件来证明证明过程的错误。所以要想理解证明过程,必须先抛弃运作过程的认知,特别是下面的1-6点都是针对accept过程的,还不存在prepare过程,prepare过程是被逐步引导出来的。

一开始场景只有如下描述

proposer发出一个议案,可能被某些acceptor accept,只要被足够多的acceptor accept则意味着该议案被chosen,同时该议案的value被chosen

以及我们想要达到的目标:

只能有一个value能被chosen

议案和value的关系,多个议案可能包含同一个value。那么只有一个议案能被chosen还是多个?目前还是未知。

下面先来看第一个问题:足够多的

1 足够多的问题

这里我们可能不自觉的就说过半,但是感觉又说不上来为什么要过半

我们先来总结下过半:

  • 使用场景:在要求每个server只能认同一个结论,不能认同2个及其以上的结论的场景下达成一致的一个结论
  • 为什么:一旦过半的server认同结论A,则在上述场景下,不可能再出现过半的server认同结论B。如果出现了,说明必有一个server认同了结论A又认同了结论B,所以违反了上述场景要求,所以在上述场景下是不可能出现的。

所以只有在上述场景下才会采用过半来达成一致。而我们上述paxos的value被chosen就是这样的一个场景,一个server只能chosen一个value,不能chosen2个及其以上的value,所以上述的足够多就可以来使用过半

目前场景描述为:

发出一个议案,可能被某些acceptor accept,只要被过半的acceptor accept则意味着该议案被chosen,同时该议案的value被chosen

接下来就要对该场景进行细致的展开,先来说说acceptor的accept要求

2 acceptor的初始accept

引出了P1,如下

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

    一个acceptor必须accept它接收的第一个议案

P1就面临了一个抉择问题,一个acceptor还能不能accept其他议案?即acceptor是否允许accept多个议案?

  • 如果不能accept多个议案,则很可能无法形成过半,目前弃用。

    Raft则是只能accept一个议案,一旦无法形成多数,则开启下一轮的accept,通过随机延时来消除这种情况

  • 如果可以accept多个议案,又要保证我们的目标:只能有一个value被chosen。这就引出了如下P2要求来做到我们的目标

3 P2-对结果要求

P2要求如下:

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

    如果一个value为v的议案被chosen了,则更高的议案必须含有value v才能被chosen。

有了这个约束,我们就能保证在多个议案被chosen的情况下,只有一个value被chosen。

P2更像是对chosen一个议案的要求,如果要想实现它,必须把它落实在acceptor的accept上,那就引出了下面的P2a的要求

4 P2a-对acceptor的accept要求

  • P2a: If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v

    如果一个value为v的议案被chosen,那么每一个acceptor accept的更高议案是必须含有value v的

acceptor aceept的高议案都是含有value v的,则这些高议案被chosen的时候自然满足P2。

这时候P1是存在另一个问题。如当一个议案被chosen的过程中,server c由于网络原因没有收到上述议案的。之后议案被chosen,如果有另一个新的proposer发起了一个更高的议案同时带上一个不同的value v1,该议案发往server c(没有收到任何议案),根据P1,server c是必须要accept该议案的。也就是说在一个议案被chosen的情况下,该acceptor accept的更高议案的value却不是v,即和P2a是矛盾的。

为了同时保证P1和P2a,我们需要对P2a进一步的限制,就引出了P2b

5 P2b-对proposer提出议案的要求(结果上要求)

  • P2b:If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v

    如果一个value为v的议案被chosen,那么如果一个proposer要提出一个更高的议案,则该议案必须含有value v。

这样的话就杜绝了上述情况,在value v被chosen的情况下,proposer要想提出一个议案,必须采用之前已提交的value v,而不是使用自己的value v1。同时又保证了P2a。

P2b对proposer提出的议案做出了要求,但是这个议案怎么来(如怎么得到已经被chosen的value v)并没有说明,下面就引出了P2c,来详细描述proposer通过怎样的过程提出的议案满足上面的要求。

6 P2c-对proposer提出议案的要求(做法上要求)

  • 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 the acceptors in S

    要想提出一个议案号为n,value为v的议案,必须满足下面2个条件中的一个

    S是一个过半的acceptor集合,满足如下2个条件中的一个

    • a:S中的acceptor都没有accept任何小于n的议案(相当于初始时即acceptor还没开始accept议案,此时可以随意提议案)
    • b:S中的acceptor有accept的小于n的议案,则v是上述议案中编号最大的议案的value

比较难以理解的就是P2c给出的提出议案的方案如何能保证P2b。再来看看P2b要证明的是:在一个value为v的议案被chosen的情况下,保证新提出的议案必须含有value v,结合P2c对提出议案的要求,a条件被排除了(因为在P2b的条件下已经有议案被accept了),那就是说目前要在b条件下证明P2b。

即目前的证明题是:

如果一个议案号为m,value为v的议案被chosen了,在满足b的条件下,提出一个议案(n,v1),证明v1=v

这个证明可以用归纳法来证明。

  • 第一步:证明初值成立,如果n=m+1,则至少过半集合C中的acceptor中小于n的最大accept议案是m,m的value是v,根据b条件,S中必然有一个acceptor属于C,即S中必然有一个acceptor accept的最大议案就是m,m已经是最大议案,即S集合中最大accept议案必然是m,所以此时新议案选用的value就是m的value v。
  • 第二步:假设m到n-1的议案的value都是v(m之后的议案是否被chosen处于未知状态,至少m议案是被过半accept的),此时过半的集合C中的acceptor accept的最大议案必然落在[m,n-1]中,他们的value全部是v,根据b条件,S中必然有一个或者一些acceptor是属于C集合的,S和C之间公共的acceptor集合为C1,则C1集合具有上述C集合的特点,S中的acceptor accept的最大议案必然落在C1中,由于C1中m之后的议案的value全是v,则此时提出的新议案的value必然采用value v。

总上2步,P2c给出的这个提出议案的要求,必然能够满足P2b。

接下来的问题就是:一个proposer如何知道acceptor accept的最大议案的value呢?这就需要proposer先提前去探测下这个最大议案的value,即这时候才引出运作过程中的prepare过程。前面一直在说的是运作过程的accept过程。

7 引出prepare过程和P1a

一个proposer向所有的acceptor发送请求,包含要发送的议案号n,来得知他们当前accept的最大议案的value。该请求就被称为prepare请求

这些acceptor的议案可以分成2大部分:

  • 7.1 小于议案号n的议案

    又细分成2部分

    • 7.1.1 目前已经被accept的议案

    从中可以挑选出最大accept的议案的value,作为该proposer要提出的议案的value

    • 7.1.2 还未被accept的议案

    这部分议案是还未到达acceptor,proposer要做的就是不再这些议案全部到达被accept了之后再去选择其中最大议案的value,而是直接让acceptor保证:抛弃这一部分的议案,即承诺此后不再accept 小于n的议案了。从而简化对这部分议案的处理。

    这一部分约束就是对acceptor的accept约束的补充,即

    P1 a . An acceptor can accept a proposal numbered n if it has not responded to a prepare request having a number greater than n

    如果一个acceptor没有对大于n的议案的prepare请求进行响应的前提下,该acceptor才能accept议案n,否则就要拒绝议案n。

  • 7.2 大于议案号n的议案

    如果acceptor accept了大于n的议案,从中选举最大议案的value,作为该proposer要提出的议案的value(这一步其实是没有必要的,后面会优化这一步)

8 优化prepare

对于上述7.2的情况,即proposer一旦发出了一个prepare请求,议案编号为n,如果此时acceptor 已经accept了更大的议案,如n+1。

则由上述7.1.2可以得知,在收到n+1的议案的prepare的时候,已经做出了承诺,不再accept小于n+1的议案了,所以该proposer提出的编号为n的议案即使在prepare过程中得到了value,该议案在发给acceptor accept的时候,acceptor是拒绝accept的。

所以应该在prepare阶段就可以把它拒绝了,所以7.2进一步更改为:

  • 7.2 大于议案号n的议案

    直接拒绝proposer发送的议案号为n的prepare请求。

我们一直在说acceptor对于prepare有2个承诺一个应答,其实就是上述7的三个分支。

  • 7.1.1分支是应答
  • 7.1.2承诺不再accept小于n的议案
  • 7.2 承诺不再响应小于n的prepare请求

9 paxos的整体运作过程

  • Phase 1:

    • (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors

      一个proposer选择一个编号为n的议案,向所有的acceptor发送prepare请求

    • (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded,then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted

      如果acceptor已经响应的prepare请求中议案编号都比n小,则它承诺不再响应prepare请求或者accept请求中议案编号小于n的, 并且找出已经accept的最大议案的value返回给该proposer

      如果已响应的编号比n大,则直接忽略该prepare请求。

  • Phase 2:

    • (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals

      如果proposer收到了过半的acceptors响应,那么将提出一个议案(n,v),v就是上述所有acceptor响应中最大accept议案的value,或者是proposer自己的value。然后将该议案发送给所有的acceptor。

      这个请求叫做accept请求,这一步才是所谓发送议案请求,而前面的prepare请求更多的是一个构建出最终议案(n,v)的过程。

      如果没有收到过半响应,则增大议案编号,重新回到Phase 1阶段。

    • (b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n

      acceptor接收到编号为n的议案,如果acceptor还没有对大于n的议案的prepare请求响应过,则acceptor就accept该议案,否则拒绝。

10 base paxos和multi-paxos

上述过程全部说的是一轮paxos的执行过程最终选出一个议案达成一致性,属于base paxos,可以有多个proposer来提出议案,但是可能会造成很多冲突问题,所以又出来一种单proposer来提出议案,同时将base paxos的2阶段简化成1个阶段,即multi-paxos。

欢迎继续来讨论,越辩越清晰

欢迎关注微信公众号:乒乓狂魔

乒乓狂魔微信公众号

© 著作权归作者所有

共有 人打赏支持
乒乓狂魔
粉丝 971
博文 105
码字总数 271356
作品 0
长宁
程序员
加载中

评论(1)

y
yongs8888
要么干脆全中文,要么干脆全英文,要么干脆用严格的数学符号表达。
图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残...

wangdy ⋅ 2016/06/22 ⋅ 0

Raft 与 Paxos的区别

Raft Raft概述 Raft一致性算法用于保证在分布式的条件下,所有的节点可以执行相同的命令序列,并达到一致的状态。这类的问题可以归结为“Replicated state machines”问题。 Raft一致性算法的...

cloud-coder ⋅ 2016/07/14 ⋅ 0

加密数字货币和传统分布式系统共识机制

加密数字货币和传统分布式系统共识机制 DBA@Robin2017-12-271 阅读 数字货币加密 本文由币乎社区(bihu.com)内容支持计划奖励。 这是「区块链技术指北」的第 13 篇文章。 如果对我感兴趣,想...

DBA@Robin ⋅ 2017/12/27 ⋅ 0

Raft一致性算法

Why Not Paxos Paxos算法是 莱斯利·兰伯特(LeslieLamport,就是 LaTeX 中的”La”,此人现在在微软研究院)于1990年提出的一种基于消息传递的一致性算 法。由于算法难以理解起初并没有引起...

cccyb ⋅ 2016/10/11 ⋅ 0

Paxos在大型系统中常见的应用场景

在分布式算法领域,有个非常重要的算法叫Paxos, 它的重要性有多高呢,Google的Chubby [1]中提到 all working protocols for asynchronous consensus we have so far encountered have Paxos...

山哥 ⋅ 2012/03/19 ⋅ 0

Paxos算法在大型系统中常见的应用场景

在分布式算法领域,有个非常重要的算法叫Paxos, 它的重要性有多高呢,Google的Chubby [1]中提到 all working protocols for asynchronous consensus we have so far encountered have Paxos...

wikison ⋅ 2015/11/28 ⋅ 0

五:分布式事务一致性协议paxos的应用场景

1.应用场景 (1)分布式中的一致性 Paxos算法主要是解决一致性问题,关于“一致性”,在不同的场景有不同的解释: NoSQL领域:一致性更强调“能读到新写入的”,就是读写一致性 数据库领域:...

无信不立 ⋅ 2016/02/22 ⋅ 0

一:学习分布式-paxos算法

这段时间由于工作需要用到zookeeper,于是就看了一下大名鼎鼎的Paxos算法。 Paxos算法是分布式经典算法之一,在Leslie Lamport的论文《Paxos made simple》一文中,作者逐步加强最初一致性问...

四月李 ⋅ 2016/04/25 ⋅ 0

Paxos的通俗理解及其在数据库高可用上的使用

本文转自【Qunar技术沙龙】,经平台同意授权转载。 近期大家都在讨论Paxos算法,我看了很多网上的文章,总觉得有些晦涩难懂,经过一段时间研究,对Paxos有了一些理解,在这里总结一下,希望能...

蒲聪 ⋅ 2017/06/19 ⋅ 0

图解 Paxos 一致性协议

前言 Paxos 一致性协议可以说是一致性协议研究的起点,也以难以理解闻名。其实协议本身并没有多难理解,它的难理解性主要体现在:为何如此设计协议以及如何证明其正确性。本文尝试通过流程图...

openthings ⋅ 02/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

一篇文章学懂Shell脚本

Shell脚本,就是利用Shell的命令解释的功能,对一个纯文本的文件进行解析,然后执行这些功能,也可以说Shell脚本就是一系列命令的集合。 Shell可以直接使用在win/Unix/Linux上面,并且可以调用...

Jake_xun ⋅ 33分钟前 ⋅ 0

大数据工程师需要精通算法吗,要达到一个什么程度呢?

机器学习是人工智能的一个重要分支,而机器学习下最重要的就是算法,本文讲述归纳了入门级的几个机器学习算法,加大数据学习群:716581014一起加入AI技术大本营。 1、监督学习算法 这个算法由...

董黎明 ⋅ 今天 ⋅ 0

Kylin 对维度表的的要求

1.要具有数据一致性,主键值必须是唯一的;Kylin 会进行检查,如果有两行的主键值相同则会报错。 2.维度表越小越好,因为 Kylin 会将维度表加载到内存中供查询;过大的表不适合作为维度表,默...

无精疯 ⋅ 今天 ⋅ 0

58到家数据库30条军规解读

军规适用场景:并发量大、数据量大的互联网业务 军规:介绍内容 解读:讲解原因,解读比军规更重要 一、基础规范 (1)必须使用InnoDB存储引擎 解读:支持事务、行级锁、并发性能更好、CPU及...

kim_o ⋅ 今天 ⋅ 0

代码注释中顺序更改 文件读写换行

`package ssh; import com.xxx.common.log.LogFactory; import com.xxx.common.log.LoggerUtil; import org.apache.commons.lang3.StringUtils; import java.io.*; public class DirErgodic ......

林伟琨 ⋅ 今天 ⋅ 0

linux实用操作命令

参考 http://blog.csdn.net/qwe6112071/article/details/50806734 ls [选项] [目录名 | 列出相关目录下的所有目录和文件 -a 列出包括.a开头的隐藏文件的所有文件-A 同-a,但不列出"."和"...

简心 ⋅ 今天 ⋅ 0

preg_match处理中文符号 url编码方法

之前想过直接用符号来替换,但失败了,或者用其他方式,但有有些复杂,这个是一个新的思路,亲测可用 <?php$str='637朗逸·超速新风王(300)(白光)'; $str=iconv("UTF-8","GBK",$s...

大灰狼wow ⋅ 今天 ⋅ 0

DevOps 资讯 | PostgreSQL 的时代到来了吗 ?

PostgreSQL是对象-关系型数据库,BSD 许可证。拼读为"post-gress-Q-L"。 作者: Tony Baer 原文: Has the time finally come for PostgreSQL?(有删节) 近30年来 PostgreSQL 无疑是您从未听...

RiboseYim ⋅ 今天 ⋅ 0

github太慢

1:用浏览器访问 IPAddress.com or http://tool.chinaz.com 使用 IP Lookup 工具获得github.com和github.global.ssl.fastly.net域名的ip地址 2:/etc/hosts文件中添加如下格式(IP最好自己查一...

whoisliang ⋅ 今天 ⋅ 0

非阻塞同步之 CAS

为解决线程安全问题,互斥同步相当于以时间换空间。多线程情况下,只有一个线程可以访问同步代码。这种同步也叫阻塞同步(Blocking Synchronization). 这种同步属于一种悲观并发策略。认为只...

长安一梦 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部