分布式一致性Paxos算法推导过程

qazw2424 · 发表于 2020-6-29 19:47:23

不定时会记录一点狗头带薪赖皮水论文的结果。
Paxos和Raft不同的是，Paxos的设计是从正确性结论反推到实现方式的（而raft是从状态复制机开始打补丁，更好用更工程，但是推导相对更没意思），在这里记录一下这个推导过程。

首先，对于分布式一致性问题，共识算法可以表示为如下约束：

1.只有被提出（propose）的值才可能被最终选定（chosen）
2.只有一个值会被最终选定
3.进程只会获知到已经确认被最终选定的值

在Paxos中，通常进程有三个身份：Proposer、Acceptor和Learner，单个进程的身份不唯一。
在一次执行过程中，为了保证约束2，一个被Proposer提出的提案（Proposal，包括提案编号和值）必须被半数以上的Acceptor接受，并且每个Acceptor只能接受一个值。
为了一次运行必须有值被接受，我们提出一个算法约束：

P1：Acceptor必须接受它收到的第一个Proposal。

这样会产生一个问题，如果多个Proposer同时提出提案，很可能会因为没有提案被超过一半的Acceptor导致无法达成一致。因此，Acceptor必须能接受多个提案，不同的提案由不同的编号进行区分，当某个提案被超过一半的Acceptor接受后，这个提案就被选定了。
不过，如果允许Acceptor接受多个提案，就有可能出现最终选定多个不同值的情况，这违背了约束3，为了保证约束，Paxos进一步提出：

P2：如果值为value的提案被选定，则任何被选定的具有更高编号的提案的值也一定为value

只要我们的算法同时满足约束p1和p2，也就保证了满足分布式一致性问题的共识算法的约束。
此时进一步延伸P2：

P2a：如果值为value的提案被选定，则对于所有的Acceptor，它们接受的任何具有更高编号的提案的值也一定为value

如果满足P2a，显然满足P2，但是P2a依然存在问题，因为Acceptor可能并不知道之前被选定的提案，导致这个Acceptor在接受这个提案的多数派中，因此进一步延伸P2a：

P2b：如果值为value的提案被选定，则对所有的Proposer，它们提出的所有具有更高编号的提案的值也一定为value

为了满足P2b，更进一步的：

P2c：为完成提了出值为value且编号为n的提案，必须存在一个包括超过一半Acceptor的集合S，对于以下条件：
（1）没有任何集合内的Acceptor曾经接受过编号比n小的提案
（2）value和集合内的Acceptor曾经接受过的编号最大且小于n的提案值一致
集合S满足条件（1）或（2）。

满足P2c即是满足P2b即是满足P2a即是满足P2，为了满足P2c，Paxos提出了Proposer的执行流程：

1.Proposer选择一个新的编号n，向超过一半的Acceptor发送请求消息，Acceptor回复：a.承诺不会接受编号比n小的提案，b.它所接受过的编号比n小的最大提案（可能不存在）。这个流程称为Prepare，该请求为Prepare请求。
2.如果Proposer收到超过一半的Acceptor的回复，他就可以提出提案，提案的值为收到的回复中编号最大的提案的值，如果没有这样的值，则提案的值可以为任意值。
3.向收到回复的Acceptor发送Accept请求，请求对方接受提出的提案。

显然，这个流程完全满足P2c的约束，但是多个Proposer同时运行时，可能出现没有任何一个提案被接受，编号递增交替完成第一步的情况，这种情况称为“活锁”，此处可以通过选主算法，选出一个主Proposer来全权负责提出提案来解决（工程上存在很多解决方案，例如Raft的选主方案）。并且即使是出现活锁，也是满足分布式一致性问题共识算法约束的。

考虑Acceptor的执行流程，对约束P1进行延伸：

P1a：Acceptor可以接受编号为n的提案当且仅当它没有回复过一个具有更大编号的Prepare消息

显然，满足P1a即是满足P1，为了满足P1a，Paxos提出了Acceptor的执行流程：

1.当收到一个Prepare请求时，如果其编号大于之前所收到的Prepare请求，则回复。
2.当收到Accept请求时，当且仅当它没有回复过一个具有更大编号的Prepare，接受该提案并回复。

以上的Paxos流程满足了P1a和P2c约束，即是满足了分布式一致性问题共识算法约束。

		自动登录	找回密码
密码			开始流浪*

[科学] 分布式一致性Paxos算法推导过程

已有 0 人打赏作者