Paxos

Paxos是分布式领域的宗师Lamport提出的基于消息传递、失败容忍的分布式一致性算法。

Google Chubby的作者Mike Burrows说过，世界上只有一种一致性算法，那就是Paxos，可见Paxos在分布式领域的重要性。

接下来我们就基于<<Paxos Made Simple>>这篇论文来学习一下Paxos算法。

在该论文中，介绍的实际上是Base Paxos算法：假设有一组进程可以提议值，那么通过Base Paxos，在这些被提议的值中只会有一个值被选中，这组进程就这个值达到一致。

很重要的一点，Base Paxos只能选中一个值。

Base Paxos需要保证：

  • 如果没有值被提出，就不会有值被选中，不能无中生有
  • 最终只能有一个值被选中，否则就脑裂了
  • 任意一个进程不能学习到未被选中的值
系统中的角色

在Paxos算法中，存在三种角色的agents：proposers，acceptors，learners。在具体实现中，一个进程可能同时充当所有角色。

  • proposers：向acceptors提议某个值
  • acceptors：对proposers提出的值进行投票
  • leaders：学习最后被选中的值

我们假设：

  • agents可以以任意速度运行，可能停止或者重启；因为agents可能会重启，因此需要能够持久化一些关键信息，并在重启之后能够恢复。
  • agents可以通过发送消息来进行通信。消息可以任意长，可以重复或者丢失，但是不能被篡改。

也就是，这是一个异步的、非拜占庭模型。

算法推导

为了能够在多个进程中选中一个值，最简单的方法是只有一个acceptor agent，只要选中其第一个接收到的提议的值。然而，这样就存在单点故障，无法实现失败容忍了。只要这个agent挂了，那么系统就无法工作了。

因此，需要同时存在多个acceptor。一个acceptor可以接受它接收到的提议值。当一个提议值被大多数acceptor接受时，那么这个提议值就被选中。

A proposer sends a proposed value to a set of acceptors. An acceptor may accepte the proposed value. The value is chosen when a large enough set of acceptors have accepted it.

这里的大多数，也就是majority应该是多少呢？假设有N个acceptor，那么应该至少需要 N/2+1。这样在N个acceptor中，任意两个majority会有一个公共的acceptor。如果一个acceptor只能接受一个值，那么就可以确保不会有超过一个提议值被选中。

不考虑节点故障或者消息丢失的情况下，我们想要即使只有一个proposer发表提案，系统最终都能够选中一个值，因此要求满足条件 P1：

P1：acceptors必须接受他接收到的第一个提案

然而，同一时间可能会有多个proposer同时发起提议，每个acceptor可能接收到不同的值，按照条件 P1，每个acceptor都接受他们第一个收到的值，从而导致没有一个提议值被majority的acceptors接受，进而导致最终没有值被选中。

选票瓜分是客端存在的，而为了能够达到最终有一个提案被majority接受，因此一个acceptor应该能够接受超过一个提案，当然，这肯定是有条件的，不能随便接受。

首先规定，每次propose提议一个值的时候，都要生成一个全局唯一且可比较的编号。因此，一个proposer发表的提案，实际上包含了一个唯一编号和提议值。有了这个唯一编号之后，我们就可以有效的区分不同的提案了，我们可以通过<number, value>唯一标识一个提案。

一个生成编号的可行方案：

In a system with n replicas, assign each replica r a unique id ir between 0 and n-1. Replica r picks the smallest sequence number s larger than any it has seen, such that s mod n = ir.

如果集群成员需要变更，则 unique id 可以使用素数替代。

每次proposer在生成一个编号的时候，都要确保新的编号大于它当前所看见的最大编号。我们可以通过比较提案的编号来判断提案的新旧，更高编号的提案被认为更新。

一个提议值被选中，只有当对应的提案被大多数acceptor所接受，也就是对应的提案被选中。

在paxos中，允许多个提案被选中，但是必须保证这些提案都具有相同的提议值，也就是具有相同的value。

这时候，为了保证所有被选中的提案具有相同的值，需要保证条件 P2 成立：

P2：如果一个包含值 v 的提案被选中，那么所有被选中的具有更高编号的提案也包含值 v

因为提案的编号是全局可比较的，该条件保证了关键的安全性：只有一个值被选中。

为了被选中，一个提案至少需要被一个acceptor接受，因此，可以通过满足条件 P2a 来满足条件 P2：

P2a：如果一个具有值v的提案被选中，那么任意一个accptor接受的更高编号的提案要包含值v

条件 P1 仍然需要维护，以确保能够有提案被选中。

可能当一个值被选中时，某个acceptor还没有接收过任何提案，比如在此期间该acceptor重启了，刚好错过了proposer的请求；这时候如果该acceptor收到了一个具有更高编号但是包含了一个不同值的提案，这时候根据条件 P1，acceptor需要接受这个值，从而违反了条件 P2a。为了同时满足 P1和 P2a，需要增强条件 P2a 为 P2b：

P2b：如果一个包含值v的提案被选中，那么任意proposer提出的更高编号的提案需要包含值v

因为提案被接受之前需要先被提出，因此满足 P2b 也就满足 P2a，也就满足了P2。

要发现如何满足 P2b，我们可以尝试证明在什么条件下该条件成立。

我们假设一个提案<m, v>已经被选中了，现在需要证明任何具有大于m的编号n的提案也具有值v。

我们通过在n上使用归纳法来简化证明。我们首先引入额外的归纳假设，每个编号在[m, n-1]的提案都具有值v。

因为编号m的提案被选中，因此，必定存在集合C，包含acceptors的majority，集合C中的每个acceptor都接受该提案。

结合该条件以及归纳假设，我们假设m被选中，则意味着：

集合C中的每个acceptor都曾经接受过一个编号在[m,n-1]的提案，并且每个被任意acceptor接受的编号在[m,n-1]的提案都有值v。

Every acceptor in C has accepted a proposal with number in m ..(n − 1), and every proposal with number in m ..(n − 1) accepted by any acceptor has value v.

acceptors中的任意majority组成的集合S，至少与集合C有一个公共的成员，我们可以通过维护条件 P2c，来推断出编号n的提案具有值v这个结论：

P2c：对于一个具有任意编号n和值v的提案被提议，那么存在集合S是acceptors中的majority，要么满足： a)S中没有acceptor接受过提案编号小于n的提案，即当前还没有编号小于 n的提案被选中；或者满足： b)v是S中的所有acceptors接受的所有编号小于n的提案中编号最高的那个提案的值，这个提案可能现在已经被选中了，也有可能还没有被选中，但是将来可能被选中。

由此，我们可以通过维护条件 P2c，来满足条件 P2b。

为了维护不变式 P2c，一个proposer在提议编号为n的提案之前，必须先了解整个系统中，当前编号小于n的提案中具有最高编号的，并且已经被选中或者将被选中的提案。了解已经被接受的提案很容易，但是要预测将会被接受的提案很困难。

替代试图去预测未来，paxos选择了在提议一个值的时候，使用两阶段提交的方式。

proposer在提议一个编号为n的提案之前，需要先向acceptors发起一个prepare请求：请求acceptor不要接受编号小于n的提案。具体如下：

  1. proposer选择一个新的提案编号n，然后向acceptor集合发送prepare请求：

    a). 要求承诺不再接受编号小于n的的提案

    b). 如果之前曾经接受过编号小于n的提案，则返回这些提案（指编号小于n的提案）中编号最大的那个提案

  2. 如果proposer接收到了acceptors中的majority的响应，则可以提议一个新的编号为n的提案，如果这些响应中有包含acceptor已经接受的提案，则新的提案的值为这些返回的提案中编号最大的那个提案的值，否则该proposer可以自己决定一个值。

proposer通过向acceptor集合发送请求来提议一个提案，该请求要求这些acceptor接受该提案，因此称作accept请求。发送prepare请求的目标acceptor集合不需要与发送accept请求的目标集合相同。

​可以看到，acceptor可以接受两种请求：prepare请求和accept请求。acceptor可以忽略任何一种请求（本身由于网络的不稳定，请求或者响应消息本身就可能丢失），并不会影响协议的安全性。

因为引入了prepare请求，P1 条件需要进行修订：

P1a：一个acceptor在接受一个编号为n的提案时，要求其没有响应过编号大于n的prepare请求

我们假设所有提案的编号是唯一的，那么现在我们就有一个完整的算法，来满足在多个实例之间确定一个值的算法了。

这里可以对prepare请求进行优化，如果一个acceptor在收到一个编号为n的prepare请求时，已经响应过一个具有更高编号的prepare请求，根据承诺这个acceptor不会再接受编号为n的提案了，因此这个时候可以忽略掉该次prepare请求。acceptor还可以忽略掉它已经接受的提案的prepare请求。

通过这种优化，acceptor只需要记住它曾经接受的最高编号的提案以及它已经响应的最高编号的prepare请求的编号。为了维护条件 P2c ，因此 acceptor 必须将这些信息持久化保存，并且再重启之后能够恢复。请注意，proposer可以放弃任何一个提案并完全忘记它，只要它不尝试发布另一个具有相同编号的提案。

最终的算法分为两阶段：

阶段一：

  1. proposer选择一个编号n，然后向aceptors中的majority发送prepare请求
  2. 当acceptor接收到该编号为n的prepare请求，如果编号n大于所有它已经响应过的prepare请求的编号，那么它响应这次prepare请求，承诺不会接受任何编号小于n的提案，并在返回中携带它已经接受过的编号最高的提案（如果有的话）。

阶段二：

  1. 如果proposer的编号为n的prepare请求得到了acceptors中的majority的响应，那么它可以发送一个accetpt请求给acceptors的majority，该请求提议的提案编号为n，值为所有响应中编号最高的提案的值，如果所有响应都不包含提案，说明还没有提案被选中，并且由于majority of acceptors对编号为n的prepare请求的承诺，这时候不会有编号小于n的提案被选中，proposer可以自己确定一个要提议的值。
  2. 如果一个acceptor接收到了一个编号为n的accept请求，如果它还没有响应过一个编号大于n的prepare请求，则接受该提案。

proposer可以多次提议，也可以在提议中途丢弃某个提案。如果一个提案已经过时（有更高的编号被提议），acceptor可以通知proposer丢弃该提案，然后重新提议一个编号更高的提案。

活锁问题

如果有多个proposer同时在提议，第一个提交了编号为n的提案，第二个提交了编号n+1的提案，导致前一个n的提案被废弃，然后重新提交了n+2的提案，导致n+1的提案被废弃。。。这样一直下去，会导致活锁，系统最终无法选中一个值。

FLP Impossibility已经证明了:

no completely asynchronous consensus protocol can tolerate even a single unannounced process death.

我们可以参考raft的选主过程，每次proposer在下一次提议新的提案时，先等待一个随机的时间间隔，这样就可以有效改善活锁问题了。

学习选中的值

前面说过，在paxos协议中有三中角色的agent，这里还有learner没有提及。

learner需要学习系统中被选中的值。为了学习被选中的值，learner需要知道被大多数acceptor接受的提案。

一种直观的做法是，可以让acceptor每次接受一个提案时，就通知所有的learner。假如系统有m个acceptor，n个learner，那么正常情况下一个提案会有m*n个请求被发送出去。

另一种做法是，因为是非拜占庭模型，消息不会被篡改。可以让所有的acceptor只通知一个learner，然后当这个learner发现一个提案被选中时，就通知其他的learner，这只需要m+n个请求。然而这就存在单点故障了。

更通常的做法是，acceptor通知一部分learner，然后这部分learner再去通知其余的learner。

Multi Paxos

Base Paxos只能用于在多个进程中就一个值达到一致性，而这肯定是不符合我们的现实需求的。

通常我们会对数据进行分片和多副本存储。

分片的主要目的是为了解决单机的性能瓶颈，从而实现水平扩展，正所谓性能不够机器来凑。

而多副本存储则是为了保证数据安全，防止单点故障。如果每个分片采用单副本存储，如果某台机器故障了，比如磁盘损坏了，那么上面的数据就丢失了。因为我们需要对每个分片进行多副本存储。

那么，如果保证同一个分片的多个副本之间的数据一致性呢？

在<<Paxos Made Simple>>中，作者提出了确定性状态机(deterministric state machine)。

对于一个确定性状态机，从一个确定的状态输入相同的命令（也叫做日志），会进入另一个确定的状态。
对于一组确定性状态机，只要执行相同序列的命令，最终都会处于一致的状态。

将每个存储服务实现为确定性状态机，只要保证他们执行相同序列的命令，就可以保证多个副本之间的一致性。

现在，为了保证副本之间的一致性，我们只需要保证这些副本执行一致的命令序列就可以了。

我们可以将每个命令看成是一个日志。对于对序列中的每个日志，可以通过一个BasePaxos实例来确定。也就是，序列中第i个日志，就由第i个BasePaxos实例来确定。

然而，每个BasePaxos实例，都需要发送prepare和accept请求。这里可以做一个优化，如果一个proposer提议了一个日志被选中，那么后续可以继续由该proposer提议，并且跳过prepare阶段，直接发送accept请求，并且保持提案中的编号n不变。而为了能够对这些日志进行区分，需要额外引入一个日志序列号。也就是日志和它的序列号组成提案的value。

这种优化是安全的，即使同时存在多个proposer发起提议，也不过是退化成BasePaxos。

也就是，当一个proposer提议成功，可以将他看成是leader，并且定期向其他proposer发送心跳，这些proposer在本地维护leader的租期定时器，在该期间不允许发起提议，并且接收到的客户端请求转发到当前leader。而即使同时存在多个leader，也不过是退化成BasePaxos，根据前面的推导，该算法是安全的。

与raft协议进行对比，multiPaxos中提案的编号和日志的序列号，不就对应raft中的term和日志的index吗？只不过raft是强leader，只允许leader同步日志，从而保证日志的index是连续的，这更便于日志的查询和复制。而multiPaxos的日志序列号则允许空洞存在。

根据CAP理论，一个分布式系统不能同时满足：

  • C：强一致性，每次读请求都可以获取到最新的写入，通常指的是线性一致性
  • A：可用性，每个请求都可以接收到非错误的返回（不需要保证总是可以读取到最新的写入）
  • P：分区容忍性，即使节点之间通信的任意数量的消息丢失或者延时，系统都可以正常运行。

当设计分布式系统时，三者只能择其二。因为网络分区总是客观存在的，因此P是无法舍弃的，只能在CP和AP之间做选择。

根据Paxos和raft的原理，通过这些协议实现的分布式存储系统，通常都是CP系统。

参考