文档章节

paxos算法证明过程

乒乓狂魔
 乒乓狂魔
发布于 2016/11/16 08:41
字数 3384
阅读 1675
收藏 17

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。

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

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

乒乓狂魔微信公众号

© 著作权归作者所有

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

评论(1)

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

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

wangdy
2016/06/22
15
0
Raft 与 Paxos的区别

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

cloud-coder
2016/07/14
1K
0
加密数字货币和传统分布式系统共识机制

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

DBA@Robin
2017/12/27
0
0
Raft一致性算法

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

cccyb
2016/10/11
3
0
Paxos在大型系统中常见的应用场景

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

山哥
2012/03/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS:异步 - 面试惨案

为什么会写这篇文章,很明显不符合我的性格的东西,原因是前段时间参与了一个面试,对于很多程序员来说,面试时候多么的鸦雀无声,事后心里就有多么的千军万马。去掉最开始毕业干了一年的Jav...

xmqywx
今天
0
0
Win10 64位系统,PHP 扩展 curl插件

执行:1. 拷贝php安装目录下,libeay32.dll、ssleay32.dll 、 libssh2.dll 到 C:\windows\system32 目录。2. 拷贝php/ext目录下, php_curl.dll 到 C:\windows\system32 目录; 3. p...

放飞E梦想O
今天
0
0
谈谈神秘的ES6——(五)解构赋值【对象篇】

上一节课我们了解了有关数组的解构赋值相关内容,这节课,我们接着,来讲讲对象的解构赋值。 解构不仅可以用于数组,还可以用于对象。 let { foo, bar } = { foo: "aaa", bar: "bbb" };fo...

JandenMa
今天
1
0
OSChina 周一乱弹 —— 有人要给本汪介绍妹子啦

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享水木年华的单曲《中学时代》@小小编辑 手机党少年们想听歌,请使劲儿戳(这里) @须臾时光:夏天还在做最后的挣扎,但是晚上...

小小编辑
今天
18
5
centos7安装redis及开机启动

配置编译环境: sudo yum install gcc-c++ 下载源码: wget http://download.redis.io/releases/redis-3.2.8.tar.gz 解压源码: tar -zxvf redis-3.2.8.tar.gz 进入到解压目录: cd redis-3......

hotsmile
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部