PigPaxos 共识协议

Paxos是一个基本的共识协议，在很多论文中都有很好的研究和定义。然而，Paxos不是一个可扩展的协议。这意味着当集群中的节点数量超过一定数量时，Paxos的性能会下降。

这种性能瓶颈是由领导节点上的高通信量引起的。为了解决这个瓶颈，PigPaxos将通信过程与领导节点的共识过程解耦。

那么，究竟什么是PigPaxos？

PigPaxos是一个基于回合（round-based）的共识协议。领导从接受者组中随机选择节点，将其信息转发给其他接受者。这是通过使用一个基于中继/聚合的消息流来完成的。在图4中，我提到了追随者中的中继节点（我在图中把它们圈起来）。这些中继节点将向其组中的所有节点发送消息，并通过使用超时机制在同步通信中收集回复。与Paxos的所有节点相比，这限制了领导者与少数节点的通信。

PigPaxos类似于Paxos的故障模型，即节点仅通过停止而崩溃。然而，通信拓扑结构是不同的。在Paxos中，拓扑结构是一对一的通信模式，而在PigPaxos中，拓扑结构是一个基于树的模式，以减少领导者的信息交换瓶颈。这是共识协议中很好的优化。

领导者不向所有的追随者发送用户请求，而是将这些请求传送给一小部分中继节点（图4中的2个节点），这些节点将这些消息传播给其余的追随者。中继节点还充当收集追随者响应的通信的聚合器，并将综合结果传递给领导者（一个非常简单的通信逻辑）。

如图4所示，我们有三个阶段。第1阶段，第2阶段，第3阶段。由于稳定的领导者假设成立，PigPaxos将只对每个共识实例执行第二阶段，第三阶段的信息将被捎带到第二阶段。

第1阶段只执行一次，只要领导者是诚实的，它就可以运行。领导者挑选中继节点并试图用他的选票来领导他们。如果领导的选票比他们目前看到的大，中继节点就会接受。这对防止同时出现双重领导是有帮助的。另外，中继节点的轮换对于平衡所有追随者的通信负担和避免热点很重要。

PigPaxos的通信方式可以概括为：在收到领导者的消息后，中继节点作为普通追随者处理该消息，并将该消息转发给其中继组的其余节点。然后，在收到消息后，追随者向中继节点作出回应，就像他们直接向领导者作出回应一样。中继节点等待追随者的回应，并将其捎带到一个单一消息中。默认情况下，中继节点会等待组内所有追随者的回应。为了避免中继节点的响应出现失效，PigPaxos在中继节点采用了严格的超时。如果一些追随者在超时时间内没有回复，中继就会停止等待，并将目前收集到的所有回复回复给领导者。

PigPaxos的领导者必须从中继节点接收大部分的信息，而中继节点需要从其组内的所有追随者那里接收。如果中继节点和追随者都出现崩溃，超时机制将被触发，以防止违反有效性。
在PigPaxos中实现了许多优化，如动态中继组，每次有新的请求到系统时，领导者必须挑选不同的中继节点，部分响应收集，并改善读取。

图8说明了这三种协议在25个节点集群中的延迟和吞吐量性能。

图9说明了广域网通信中的PigPaxos与地理位置。每个区域代表一个单独的PigPaxos中继组，领导节点位于弗吉尼亚区域。在这个设置中，延迟被跨区域的距离所支配，因此，在低负载下，Paxos和PigPaxos之间的差异是无法观察到的。与局部地区的实验类似，PigPaxos在更高的吞吐量水平上保持低延迟。

图 10 展示了一个运行 Paxos 和 PigPaxos 的 5 节点集群，有 2 个中继组。 PigPaxos 可扩展到比 Paxos 更高的吞吐量，因为它与 fever 节点通信。 PigPaxos 只与两个节点对话，这正是 Paxos 需要联系多少个追随者才能达到多数法定人数，但 Paxos 仍然在每一轮中发送 4 条消息。

PigPaxos和Paxos用25个节点集群进行实验，其中PigPaxos使用3个中继组。为了衡量与有效载荷大小有关的性能和可扩展性，我们测量了每个系统在3个虚拟机上运行的150个客户产生的只写工作负载下的最大吞吐量。

图12a 显示了PigPaxos和Paxos在有效载荷大小为8至1280字节的情况下的最大吞吐量。虽然这两个协议表现出截然不同的性能水平，但随着有效载荷大小的增加，它们表现出类似的相对退化水平。图12b说明了归一化为最大观察值的吞吐量。

最后，该 paper 没有提到如果 leader 失败会发生什么。我猜新的 leader 会带着新的选票号码出现，如果追随者已经答应了前一个 leader 承诺他的 value ，那么新的 leader 就会学习这个价值，并且会承诺它。这正是Paxos在 leader 崩溃时的做法。