一致性算法Paxos-简单理解

概论

在分布式系统中，数据通常会存储多个副本，如何维持副本之间的一致性则是一个比较经典的问题。Paxos是一个比较经典的一致性算法，本文将对paxos进行简单的介绍。

Paxos算法以难以理解著称，因此后来也提出了一个更容易理解的算法Raft，在https://blog.csdn.net/qq_34924156/article/details/111589352这篇文章中有简单介绍。

Paxos算法

问题定义

一致性：

当前有一组process，每个process都能提出一个提案（value），因为这一组process需要执行相同的提案，因此需要从决策提案中选择一个执行。最终这一组process会执行被选择的这个提案。

转换到分布式存储，可以理解为有一组副本存储相同的数据，每个副本都能提出修改数据的建议，但是因为副本组需要维持副本数据相同，因此最终只有一个修改建议会被选择执行。

一致性协议的目标：

1. 选择一个提案（存在提案的话），并告知所有process被选择的提案。
2. 异步通信，允许消息的丢失或者重复，但是不会出现内容损坏的情况（即非拜占庭模型），允许机器故障等问题。

一致性的安全性：

1. 提案只有被提出后才能后选择
2. 只有一个提案被选择
3. 如果提案未被选择，那么process不会收到该提案被选择的消息。（即只会收到正确的被选择消息）

注：一致性算法没有特别精确的时间要求。

主要角色：提案者（proposer），批准者（acceptor），接收者（listener）。一个process可以担任多个角色。

提案的选择

基本原则：当有多数acceptor批准某一提案，提案就被选择。  

1. 一个acceptor只能批准一个提案。
2. 不能只选择一个acceptor是因为单个acceptor存在单点故障，如果该acceptor故障系统就不能继续运行了。

算法过程：

两阶段过程：

1. Proposer：选择一个议案编号n，向acceptor的多数派发送编号也为n的prepare请求。

    Acceptor：如果接收到的prepare请求的编号n大于它已经回应的任何prepare请求，它就回应已经批准的编号最高的议案（如果有的话），并承诺不再回应任何编号小于n的议案；

2. Proposer：如果收到了多数acceptor对prepare请求（编号为n）的回应，它就向这些acceptor发送议案{n, v}的accept请求，如果acceptor们回应说还没有批准过议案，那么v就是该proposer提出的议案，否则v是所有回应中编号最高的议案的决议。

    Acceptor：如果收到了议案{n, v}的accept请求，它就批准该议案，除非它已经回应了一个编号大于n的议案。Proposer可以提出多个议案，只要它遵循上面的算法。它可以在任何时刻放弃一个议案。（这不会破坏正确性，即使在议案被放弃后，议案的请求或者回应消息才到达目标）如果其它的proposer已经开始提出更高编号的议案，那么最好能放弃当前的议案。因此，如果acceptor忽略一个prepare或者accept请求（因为已经收到了更高编号的prepare请求），它应该告知proposer放弃议案。这是一个性能优化，而不影响正确性。

详细规则：（可以忽视，主要是算法过程的由来）

概念：议案={编号，提案}，其中编号唯一

1. Acceptor必须批准它接收到的第一个提案。（可以批准多个议案，但是要保证议案拥有相同提案）。

2. 如果一个议案{n, v}被选择，那么所有被选择的议案（编号更高）包含的决议都是v。

2.a 如果一个议案{n, v}被选择，那么任何acceptor批准的议案（编号更高）包含的决议都是v。

我们依然保证1来确认选择了某些议案。因为通信是异步的，在特殊情况下，某些acceptor c没有接收到过任何议案，它们可能会批准一个议案。设想一个新的proposer“醒来”并提出了一个更高编号的议案（包含不同的决议）。根据P1的要求，c应该批准这个议案，但是这违反了P2A。为了同时保证P1和P2A，我们需要2.b：

2.b 如果一个议案{n, v}被选择，那么此后，任何proposer提出的议案（编号更高）包含的决议都是v。

因为一个议案必须在被proposer提出后才能被acceptor批准，因此2.b包含了2.a，进而包含了2。

如何才能满足2.b呢，让我们来考虑如何证明它是成立的。我们假设某个议案{m, v}被选择，然后证明任何编号n>m的议案的提案都是v。对n归纳可以简化证明，根据条件：每个提出的议案（编号从m到n-1）的提案都是v，我们可以证明编号为n的议案的提案是v。对于选择的议案（编号为m），必定存在一个集合C（acceptor的多数派），C中的每个acceptor都批准了该议案。结合归纳假设，m被选择这一前提意味着：

C中的每个acceptor都批准了一个编号在m到n-1范围内的议案，并且议案的提案为v。

因为任何由多数派组成的集合S都至少包含C中的一个成员，我们可以得出结论：如果下面的不变性成立，那么编号为n的提案的决议就是v：

2.c 对于任意的v和n，如果议案{n, v}被提出，那么存在一个由acceptor的多数派组成的集合S，要么：S中没有acceptor批准过编号小于n的议案，要么：在S的任何acceptor批准的所有议案（编号小于n）中，v是编号最大的议案的提案。

通过保持2.c，我们就能满足2.b。

为了保持不变性2.c，准备提出议案（编号为n）的proposer必须知道所有编号小于n的议案中编号最大的那个，如果存在的话，它已经或将要被acceptor的某个多数派批准。获取已经批准的议案是简单的，但是预知将来可能批准的议案是困难的。Proposer并不做预测，而是假定不会有这样的情况。也就是说，proposer要求acceptor不能批准任何编号小于n的议案。这引出了下面提出议案的算法（两阶段提交）。

两阶段提交：

1. Prepare阶段：proposer选择一个新编号n，向某个acceptor集合中的所有成员发送请求，n是prepare请求的编号，也是下面acceptor请求的议案编号。Acceptor需要保证永不批准编号小于n的议案，同时响应它已经批准的所有编号小于n的议案中，编号最大的议案（如果存在的话）
2. 如果proposer收到了多数acceptor的回应，那么它就可以提出议案{n, v}，如果acceptor们回应说还没有批准过议案，那么v就是该proposer提出的议案，否则v是所有回应中编号最高的议案的决议。

2.c介绍了两阶段提交proposer的行为，对于acceptor，主要行为如下：

1.a acceptor可以批准一个编号为n的议案，当且仅当它没有回应过一个编号大于n的prepare请求。

1.a蕴含了1。

假设一个acceptor接收到一个编号为n的prepare请求，但是它已经回应了一个编号大于n的prepare请求。于是acceptor就没有必要回应这个prepare请求了，因为它不会批准这个编号为n的议案。它还可以忽略已经批准过的议案的prepare请求。

acceptor只需要保存它已经批准的最高编号的议案（包括编号和决议），以及它已经回应的所有prepare请求的最高编号。因为任何情况下，都需要保证P2C，acceptor必须记住这些信息，包括失效并重启之后。注意，proposer可以随意的抛弃一个议案——只要它永远不会使用相同的编号来提出另一个议案。

Learner获知结果：

Learner必须找到一个被多数acceptor批准的议案，才能知道一个决议被选择了。一个显而易见的算法就是，让每个acceptor在批准议案时通知所有的learner。于是learner可以尽快知道选择的决议，但是要求每个acceptor通知每个learner——需要的消息个数等于learner数和acceptor数的乘积。

基于非拜占庭假设，一个learner可以从另一个learner得知被选择的决议。我们可以让acceptor将批准情况回应给一个主Learner，它再把被选择的决议通知给其它的learner。这增加了一次额外的消息传递，也不可靠，因为主learner可能会失效，但是要求的消息个数仅是learner数和acceptor数的总和。

更一般的，可以有多个主Learner，每个都能通知其它所有的acceptor。主learner越多越可靠，但是通信代价会增加。

由于消息丢失，可能没有learner知道选择了一个决议。Learner可以向acceptor询问批准的议案，但是由于acceptor的失效，可能难以得知多数派是否批准了一个议案。这样，learner只能在新的议案被选择时才能知道acceptor选择的决议。如果learner需要知道是否已经选择了一个决议，它可以让proposer根据上面的算法提出一个议案【提出请求就有回应，并且新的提案的决议就是当前选择的决议】。

死锁与解决：

死锁：两个proposer轮流提出一系列编号递增的议案，但是都没有被选择。Propoer p选择议案的编号为n1，并结束阶段1。接着，另外一个proposer q选择了议案编号n2>n1，并结束阶段1。于是p在阶段2的accept请求将被忽略，因为acceptor已经承诺不再批准编号小于n2的议案。于是p再回到阶段1并选择了编号n3 > n2，这又导致q第二阶段的accept请求被忽略。

解决：选择一个主proposer，只有主proposer才能提出议案。如果主proposer和多数acceptor成功通信，并提出一个编号更高的议案，议案将被批准。如果它得知已经有编号更高的议案，它将放弃当前的议案，并最终能选择一个足够大的编号。

实现

1. 选出Leader：担任主proposer和主learner
2. Acceptor在发送响应前必须持久化存储该响应。
3. proposer都持久化保存它已经提出的编号最高的议案。
4. proposer从互不相交的集合中选择议案编号，保证两个不同的proposer永远不会提出相同编号的议案。如proposer i的议案编号选择序列为：5*j + i

Paxos进阶

PaxosLease

前文提到需要选出leader担任主proposer和主learner，PaxosLease便是用于选举leader的算法。

众多的Node中选择一个作为Master（即leader），如果该Master 一直 alive则无需选举，如果master crash，则其他的node进行选举下一个master。为了保证任何时刻最多只能有一个master，算法将选举master变成了分布式锁的问题。

完全靠锁来解决选举问题会存在死锁（如果一个Node拿到了锁，之后crash，那锁会导致无法释放）。因此设计Master只能在Lease有效期内访问锁定的资源，在Lease timeout后，其他Node可以继续竞争锁，这就从根本上避免了死锁。Master在拿到锁后，如果一直alive，可以向其他node”续租“锁，从而避免频繁的选举活动。

Multi-Paxos

paxos是对一个值达成一致，multi-paxos是运行多个paxos instance来对多个值达成一致，每个paxos instance对一个值达成一致。在一个支持多写并且强一致性的系统中，每个节点都可以接收客户端的写请求，生成redo日志然后开始一个paxos instance的prepare和accept过程。这里的问题是每条redo日志到底对应哪个paxos instance。

Multi Paxos基于Basic Paxos，将原来2-Phase过程简化为了1-Phase，从而加快了提交速度。Multi Paxos要求在各个Proposer中有唯一的Leader，并由这个Leader唯一地提交value给各Acceptor进行表决，在系统中仅有一个Leader进行value提交的情况下，Prepare的过程就可以被跳过，而Leader的选举则可以由Paxos Lease来完成。