vertical paxos和主备复制
Vertical paxos and primary-backup replication
介绍
建立在容易发生故障的商用组件的大规模分布式存储系统越来越受欢迎。故障在这些大型分布式系统中很常见，而复制通常是数据可靠性的解决方案。共识算法和传统的复制协议的系统中仍然存在较大的鸿沟：共识算法主要用于维护全局的配置信息，而不用于实际的数据复制。
这种差距并非偶然：定义经典共识算法的抽象模型，不能完全捕捉真实分布式系统的需求。在经典的共识问题中，单个复制组维护固定的n个程序，其中最多f个可以失败。事实上，分布式系统由大量重叠的副本组组成，每个副本组负责维护系统数据的一个子集。每个特定的副本组只部署少量的服务器。当副本出现故障时，在其他导致永久数据丢失之前，立即启动用新的副本替换他们。整个系统有大量的服务器，便于重新配置和部署新的副本。
我们桥接了俩个算法之间的gap，使用新的算法我们叫它vertical paxos，这是由paxos算法衍生出来的。vertical paxos允许配置来修改单个共识决策中的配置，使用来自辅助配置主机的重新配置指令。配置主可以使用普通paxos复制状态机的方法来实现。在实践中，对于维护系统中许多副本组的配置，这样的主服务器是很自然的。主节点只有在重新配置的时候才会被调用，这种情况通常不应该发生，因此单个主服务器可以为许多独立的副本组提供服务。
我们的处理对于主备方法有特殊的意义。经典的主备复制协议，使用f+1个服务器来容忍f个故障。为了绕过解决共识问题所需的2f+1进程的下限，主备协议必须要么使用外部服务，比如我们的配置主，要么对故障做出更严格的假设。据我们所知，以前没有基于外部服务的主备协议具有严格的正确证明。我们的俩个vertical paxos算法导出了俩个可证明正确的主备协议。一个是对现有协议的严格制定，第二种是新的变体，可以在实践中使用。
从paxos到vertical paxos
类似经典的paxos，vertical paxos通过执行一系列逻辑上独立的共识算法实例，实例i选择第i个状态机命令。不同实例的操作可通过显式索引明确区分，但由于异步性，这些操作在时间上可能相互交错。
这里有四个规则：客户端提交要添加到完全有序的命令序列中的命令。learners实现了状态机：它们在学习在每个实例中选择什么命令并按顺序执行。leader和acceptor执行已经达成一致决定的协议。特定的接受者被称为quorums，任何俩个群体一定有一个非空的交集。这组接受者机器法定人数结构称为共识配置。一个客户端发送请求到任何一个可用的leader。一个流程可以扮演多个角色。
为了确保容错性，当原有领导者（leader）无法及时推进进程时，必须激活新的领导者。与经典Paxos算法相同，每个共识实例（consensus instance）的执行可能包含多次领导者激活过程，每次激活都试图达成决议。出于历史原因，这些领导者激活过程被称为投票轮次（ballots）；每个投票轮次都具有唯一编号。复制状态机的执行过程既横向体现为一系列共识实例的推进，又纵向表现为投票轮次编号的递增。
共识算法的核心是拥有新的选票的leader执行的协议。与经典Paxos算法相同，新领导者（leader）必须为所有实例（instances）确认是否存在在编号更低的投票轮次（ballots）中已被选定的命令（command）。同时新的leader必须阻止票数较少的选票选择任何进一步的命令。leader会尝试确保那些已有命令被提出但可能未被选定的实力中，最终选定某个命令。对于那些没有提出命令的实例，它可以提出一个新的。如果有法定人数的投票者在投票中承认该命令，则投票中选则该命令。稍后投票的leader也可以类似地查询过去提出的命令，并通过联系法定人数的接受者来阻止新的命令。在标准的paxos中，有新选票的leader执行以下操作。
阶段1：领导者（leader）与接受者（acceptors）进行一轮消息交换。当收到多数接受者（quorum）的回复后，领导者将获知每个实例（instance）的以下两种情况之一：
- 可能已被选定的命令（command）c；
- 尚无任何命令被选定。
在此过程中，领导者还会获得接受者的承诺——不再响应任何编号更低投票轮次（lower-numbered ballots）的提案（该机制用于应对异步系统中可能随时到达的过时提案）。
阶段2：对于情况1的实例，领导者向接受者重新提交命令c；对于情况2的实例，领导者则按客户端请求提交新命令。
接受者会接受、存储并确认领导者的提案，除非已收到更高编号投票轮次（higher-numbered ballot）的领导者指令要求忽略当前轮次。
vertical paxos从俩个方向泛化了传统的paxos算法。vertical paxos允许将不同的配置与每张选票关联。独立的辅助配置主决定并维护从号码到选票的映射。因为配置是垂直运行的，横跨选票和号码。
在Vertical Paxos协议中，新的ballot由configuration master发起，该主节点负责选定ballot编号、leader以及配置。Vertical Paxos的两个阶段运行机制如下：
第一阶段中，leader不仅需要与新ballot配置中的读仲裁组（read quorum）通信，还需与编号更小的ballot配置中的读仲裁组交互。通过这种方式，leader既能获知所有在低编号ballot中已达成一致的命令（chosen commands），同时也能阻止这些低编号ballot对新命令的继续提交。
第二阶段与标准Paxos协议基本一致，不同之处在于leader只需与当前ballot配置中的写仲裁组（write quorum）进行通信。
当某个旧配置中所有可能被选定的命令（存储在其接受者上的）都被更高编号投票轮次的接受者所知晓时，该旧配置即告失效，其读取仲裁组也不再被联络。这一过程通过状态转移机制实现：领导者会读取较低编号投票轮次的读取仲裁组所存储的命令，并将这些可能被选定的命令写入新投票轮次的写入仲裁组。垂直Paxos算法的两种变体主要区别在于，在状态转移过程中何时认定某个配置处于活跃状态。
垂直Paxos II算法确保任意时刻仅存在一个活跃配置。新当选的领导者会启动从当前活跃配置到新配置的状态转移流程，仅当状态转移完成后，才会请求主节点激活新配置。
该算法的领导者协议基于经典Paxos领导者协议进行如下调整：第一阶段中，领导者联络当前活跃投票轮次中的读取仲裁组接受者；第二阶段则被拆分为多个子阶段执行。
A：每当领导者获知某个实例中可能存在已选定的命令c时，会在协议第二阶段将该命令c提交给写入仲裁组的接受者。
B：当所有相关实例的第二阶段均完成后，领导者将请求主节点激活新的投票轮次编号（及新配置）。
C：对于其他未选定任何命令的实例，领导者将等待客户端提交的下一个命令，并在协议第二阶段提出该值。
在Vertical Paxos I中，主节点会立即激活新配置。该配置将保持活跃状态，直至主节点收到领导者通知——表明该配置的状态已转移至更高编号投票轮次的接受者。这种设计允许多个配置同时处于活跃状态。当启动新投票轮次时，主节点会向新任领导者通报当前所有活跃配置。
vertical paxos和主备复制
Vertical Paxos最具研究价值的场景是：当任意单个接受者即可构成读取仲裁组，而写入仲裁组必须包含所有接受者时。这种配置仅需f+1个接受者即可实现f容错。更巧妙的是，我们可以将领导者设为接受者之一，并在重新配置时从当前接受者中选举新领导者。此时，新领导者自身就构成前一投票轮次的完整读取仲裁组，能够独立完成协议第一阶段的所有操作。这意味着在Vertical Paxos II中，唯一需要的状态转移仅发生在领导者与新增接受者之间。若将领导者设为主节点，其他接受者作为备份节点，便构成了传统的主备系统。
与大多数主备协议（如Vertical Paxos II所体现的）类似，这类系统通常维持单一活跃配置，并要求在重新配置前完成状态转移。实际系统中，状态转移往往涉及海量数据复制，代价高昂。Vertical Paxos I通过允许多个配置同时活跃，成功实现状态转移与配置更新的解耦——新配置可立即激活以处理请求，而状态数据则从旧配置异步迁移。