本文共 2658 字,大约阅读时间需要 8 分钟。
Paxos是分布式的一致性协议,最重要的部分当然是这个一致性的证明。
在朴素Paxos协议中给出了3大条件,只要达到了这3大条件
可以证明,如果Paxos协议达成了一次成功的表决,那么这个表决具有一致性。
需要说明的是,这3大条件并不保证进行性,也就是说并不保证一定会达成成功的表决。
但是可以保证的是,如果达成了一个成功表决,那么这个表决具有一致性。
1.基本术语
(1)
ballot/B表决
decree法令 quorum法定人数集、多数派 Bdec某次表决的法令 Bqrm参与某次表决的牧师集合 Bvot参与某次表决的牧师中投赞成票的集合 Bbal某次表决的编号说明1:成功的表决
说一轮表决B是成功的,当且仅当Bqrm属于Bvot
即该轮表决中所有参与的牧师都投了赞成票说明2:表决的大小
B1 > B2 等价于 B1val > B2val,
但是这个下标并不反映实际表决发生的顺序。 即允许bal小的表决发生在bal大的之后(2)
要最终确定一个值需要多轮表决。
某次表决B 多轮表决构成的集合是βV表示一个投票
Vbal表示投票的编号 Vpst表示投票的牧师 Vvec表示投票的法令 V1<V2等价于,V1bal<V2bal Votes(β)表示所有在β中的投票 p表示一个牧师 b表示一个表决的编号 MaxVote(b,p,β)表示β中,由p投出的所有表决中,编号小于b 的投票中最大的投票v。 Q表示牧师集合 MaxVote(b,Q,β)表示,所有p属于Q中MaxVote(b,p,β)的最大值2.MaxVote(b,Q,β)
MaxVote(b,Q,β)的意义十分重要,是接下来要介绍的三大条件以及后面一致性证明的核心概念。
用一个例子来表述MaxVote(b,Q,β)的含义。
其中,最左边的#下面表示的是编号bal
然后decree表示的是需要表决的法令
接下来A、B、倒L、三角形、E表示所有可能来进行表决的牧师
每一行实际显示出的牧师就是Bqrm,牧师中的多数派
每一行被方框框住的牧师就是Bvot,Bqrm中实际在某次表决中投赞成票的牧师。
MaxVote(2,{A、B、倒L、三角形},β) bal == null
MaxVote(5,{A、B、倒L、E},β) bal == null
MaxVote(14,{B、三角形、E},β) bal == 2 ,其中关联牧师为三角形
MaxVote(27,{A、倒L、三角形},β) bal == 5 ,其中关联牧师为倒L
MaxVote(29,{B、倒L、三角形},β)bal == 27 ,其中关联牧师为倒L、三角形
3.三大条件
条件1:β中的每一轮表决,都有一个唯一的编号
条件2:β中任意两轮的B1qrm和B2qrm中,至少有一个公共的牧师成员 条件3:对于每一轮表决B,如果B的Bqrm中任何一个牧师在β中一个编号更小的表决中投过赞成票, 那么B的法令必须与所有更小轮表决中的最大那次的表决的法令相同条件2的笔记:
由于有公共假设,牧师如果没有出去旅游,就会来办公, 并且如果同时有超过总数量一半的牧师不来,就是无法确定一个法令。 所以条件2又可以表述为 任意一次的Bqrm都是超过牧师总数量的一半的。 即Bqrm始终要是总人数的多数派这次表决才能生效。 条件3的笔记: (1) 相对于条件1和2的好理解, 这个条件3仿佛是不知怎么样就出现的一个古怪约束。 然而这才是重头戏,要保证一致性,这个条件3是相当重要的。 (2) 假设本次表决编号N,现在有牧师1-k, 它们投过票的表决编号为N1-Nk, 条件3就是要保证,N1-Nk都小于N, 然后选出N1-Nk中最大的那个编号对应的表决的法令作为本次表决的法令这个条件结合MaxVote(b,Q,β)与上面的图更好理解一些。
三大条件更正式的表述如下:
4.引理与定理
(1)引理1
在3大条件被满足的情况下,如果β中的表决B是成功的,那么β中更大编号的表决和B有相同的法令。
(2)定理1
在3大条件被满足的情况下,任意两轮成功的表决,都是对相同法令的表决。
(3)定理2
在3大条件被满足的情况下,是有可能做出一次成功的表决的。
但不能保证一定会产生一轮成功的表决。 但至少表明在3大条件的基础上表决协议不会产生死锁。引理与定理的正式表述:
(1)引理1
(2)定理1
(3)定理2
思考:
(1)由定理1很容易理解如果产生了成功的表决,那么表决具有一致性。
因为所有成功的表决都是对相同的法令进行的表决。
(2)由引理1很容易证明定理1
因为所有不同的成功的表决的编号都是不同的,这一点由条件1保证。
那么假设成功表决中编号最大的表决时B,那么由引理1可知,任一成功的表决的法令都与B相同。
所以任一成功的表决的法令是相同的。
5.证明一致性
由4中的思考的(1)、(2)可知,证明朴素Paxos如果成功表决,那么其结果具有一致性的证明的关键是引理1的证明。
论文中采用的是反证法证明。
引理1说如果满足条件1-3,并且B是一次通过的表决,那么所有编号比Bbal大的表决的法令和Bdec相同。
假设:存在集合X,X为比B编号大,并且法令与Bdec不同的表决的集合。
进一步假设C是X中编号最小的一个表决。
通过一系列的推导,可以得出
MaxVote(Cbal,Cqrm,β)属于集合X 并且MaxVote(Cbal,Cqrm,β)bal < Cbal 这是矛盾的。我们令MaxVote(Cbal,Cqrm,β)=D 那么D属于集合X,并且Dbal < Cbal 但是我们之前的假设就是C是集合X中bal最小的。 所以矛盾。
那么假设不成立,那么命题引理1得证。
正式的推导:
说明:
步骤3.因为B是一次成功的投票,所以Bvot==Bqrm,又因为C也是一次β中的投票所以Cqrm也是多数派。
所以Bvot与上Cqrm == Bqrm与上Cqrm != 空集
步骤4.因为C是属于集合X的,而集合X的定义又是bal大于Bbal的,
并且MaxVote(Cbal,Cqrm,β)bal的定义是所有比Cbal小的里面最大的。
所以MaxVote(Cbal,Cqrm,β)bal大于等于Bbal
步骤5、6.由步骤4可知MaxVote(Cbal,Cqrm,β)bal >= Bbal
所以无论如何MaxVote不是nullVote,那么根据条件3就可以推出步骤6