Paxos 一致性算法原理剖析(-)
算法目标
对于一个一致性算法需要保证如下几点:
- 只有被提出的提案才可以被选定
- 所有提案,只有一个会被选定
- 进程可以获取的提案,一定是被选定的提案
原理推导过程
对于提案的整体原理推到,需要介绍如下角色:
- acceptor 用来同意提案
- proposer 用来提议提案
推导过程
如下是算法的整体推导过程
-
考虑到消息提交的失败和丢失。引出规则P1:
P1. acceptor 必须 accept 他收到的第一个提议
P1的提出,引发了一个问题, 当多个proposers,提出不同提案的时候,无法满足有超过一半的acceptor accept 提案。即便是2个提案,也无法保证会有超过一半的acceptor支持其中一个。
- 由此,一个acceptor 必须可以 accept 多个提案
当然,为了防止奇异,每个提案会被分配一个单调递增的编号,这样一个提案就由number和value组成。
-
现在每个acceptor都可以accept多个提案,同样我们可以允许多个提案被选定,但一定保证被选定的提案有相同的value,由此引出了P2
P2. 如果一个提案的(value=v)被选定,那么所有被选定的编号高于这个提案的value都要等于v
P2的提出保证了在提案选定后的结果,即一定是只有一个value=v的提案最终被选定,
P2a . 如果提案(number=m, value=v)被选定,那么任何number高于m且被任何acceptor accept的提案的value=v即便 P2a 的条件看上去很奇怪,但是这样确实可以保证value=v的提案是最终确定提案。
-
同时,考虑P1,如果一个proposer提出了一个value!=v的提案,且提给了一个没有accept任何提案的acceptor,这个acceptor需要accept这个提案。由此引出 P2b
P2b. 如果提案(number=m, value=v)被选定,那么所有number>m的提案的value必须是v
由此,我们发现,只要满足了 P2b 那么P2就满足了
-
那么我们如何保证number>m的提案value=v那?由此引出 P2c ,
设n>m,且number∈[m, n-1]的value=v,存在一个acceptor数量大于一半的集合C accept value=v的提案(这个假设只是使得更好的理解下面的条件)
P2c. 如果提案(numnber=n, value=v)可以被提出,那么一定存在acceptor数量超过半数的集合S,满足a或者b
- a) S中的所有acceptor没有accept任何number < n的提案
- b) 所有在S中的acceptor accept的number <= n的提案中,value = v是number最大的
P2c 的提出实际是在约束proposer如何提出一个提案, P2c 的规则只是为了保证 P2b 中number > n的提案的value = v
a其实是b的一种特殊情况,即当number = n的提案提出时,S中的acceptor还没有accept任何number < n的提案
因为集合S和C必有交集(交集意味着必有至少一个acceptor同时属于两个集合),且n是提案中编号最大的提案,所以n的提案value = v
如果提案(numnber=n, value=v)被提出,在S中n并不是编号最大的(由于并发网络等原因导致先提出的提案后到达了acceptor),那么acceptor会accept这个提案(一个acceptor可以accept多个提案)
这就导致在提案还未被确定的情况下,有多个同时待确定的提案都满足被确定的条件(超过半数的acceptor同意该提案),这不满足算法本身要求一个提案被选定的要求。
至此,我们找到了一种如何提案的方法。 P2c 的设计旨在考虑到,对于一个proposer,预测未来那个value会被选成功是困难的,但已知现有的选举状况是简单的。
proposer提案
为了满足 P2c ,我们规定proposer按照如下方式提案:
- (prepare request)proposer选择编号n,然后向acceptor发送请求,要求acceptor满足如下条件:
- 不会accept number < n的提案
- acceptor accept的提案number < n中number最大的提案
- (accept request)如果proposer收到了超过一半的acceptor的response,proposer会提案response中编号最大的提案的value,如果response中没有已经accept的提案,proposer可以提案任意的value
这里的两个阶段proposer通信的acceptor可以不是同一个集合。这里也是考虑到网络的原因,acceptor可以随时宕机等等原因。
acceptor 选取提案
acceptor会接收到两种请求,prepare request和 accept request。acceptor可以忽略掉任何的请求。
即便是这个acceptor没有收到之前proposer的prepare request,acceptor仍然可以选择处理这个proposer提出的accept request。
至此,整个算法都已阐述啦~
文章参考
本文参考: Leslie Lamport的文章Paxos Made Simple(01 Nov 2001)