Just say NO to Paxos Overhead: Replacing Consensus with Network Ordering

0x00 引言

Paxos是分布式共识里面重要的算法了。Paxos算法的变体也非常多。而NoPaxos的把一些算法的逻辑放到了网络上面，这里核心的概念的Ordered Unreliable Multicast(OUM)，即在数据中心网络实现有序但是不可靠的消息传输，并在此的基础之上实现NOPaxos(Network-Ordered Paxos)，是SOSP‘17 Eris论文的后续，其作者基本相同，

... NOPaxos on a testbed using our OpenFlow/Cavium prototype and demonstrate that it outperforms classic leader-based Paxos by 54% in latency and 4.7× in throughput. It simultaneously provides 42% better latency and 24% better throughput than latency- and throughput-optimized protocols respectively, circumventing a classic tradeoff.

0x01 顺序、可靠分离 & 多播

如果一个网络是可靠的、有序的，很显然实现分布式共识是很简单的。现在的复杂的分布式共识算法很大程度就是为了处理消息丢失、乱序的情况。但是Paper中认为提供一个可靠、有序的网络是很困难的，还有就是提供一个有序、不可靠的网络则简单很多，一个直观的方法就是赋予每一个信息一个Sequence Number，只处理按序到达的数据。NOPaxos的网络层同时Ordered Unreliable Multicast(OUM)，即不可靠的多播来将信息按序但是不可靠地将传输给一组的节点。OUM是一种异步的、不可靠的支持顺序多播和多播丢包探测的模型，它的这个几点的性质，

• 异步，即到达目的的延迟是不确定的，即可能是任意长的延迟；
• 不可靠，不保证信息最终到达目的地；
• 支持多播，且到达目的信息的顺序和发出的顺序是一致的；

• 丢包探测，对于发送的一个信息，1. 其接受者会收到这个信息或者是在下一个多播信息之前这个信息被“丢”的通知，2. 所有的进程没有收到这个信息和丢失通知；

  OUM的实现有两个部分，一个是网络中Sequencer和一个库libOUM。在libOUM中添加了另外的一个概念，对于一个OUM组(An OUM group is a set of receivers and is identified by an IP address)，保持了若干的Sessions。消息可以被连续的OUM的Sessions划分为组。这里要注意的是不能保证一个OUM Session在同一个时间点结束。在一个OUM Session结束的时候，任意数量的消息可以被丢 ，这个数量对于不同的节点还是不同的，每个信息收到的是一个前缀，

...  OUM sessions are not guaranteed to terminate at the same point in the message stream for each multicast receiver: an arbitrary number of messages at the end of an OUM session could be dropped without notification, and this number might differ for each multicast receiver. Thus, each multicast recipient receives a prefix of the messages assigned to each OUM session, where some messages are replaced with drop notifications.

另外OUM Session一般存在的时间是很长的，一般在网络设备出现故障的时候才会终止。这个时候应用会收到这个信息，应用需要保证在下一个Session开始之前保证相同的一致性。libOUM基本的接口，

0x03 OUM设计与实现

OUM的实现是NOPaxos的一个核心。OUM面向的环境是单个的数据中心，网络层的Sequencer使用SDN来实现，基本思路就是将数据包都发给一种Sequencer来统一给一个OUM组的数据包来编号。NOPaxos测试使用的数据中心网络拓扑为常见的FatTree，为例将数据先转发给指定的Sequencer，一个控制器会赋予这个OUM组一个特殊的IP地址(也可以看作是一个特殊的组播地址)，然后转发的逻辑使用SDN来实现。为了负载均衡，OUM会根据OUM组来分配Sequencer。下面的图是一个网络拓扑的示意图，数据先经过绿色的先到达Sequencer，编号之后广播给接受者。

Paper对比来几种Sequencer的实现，最终采用了Network Processor和OpenFlow结合的实现方式。OUM的实现中使用的是Sequencer是一个单点的设计，这里使用单点的设计简化了系统的设计。不够要处理这个Sequencer失效的问题。网络控制器会监控Sequencer的可用性，变得不可用的时候会更新网络的配置。在这个重新配置的周期内，一些多播的信息可能会没有被送达。另外，为了处理Sequencer变换，OUM还加入了一个单调递增的Session Number。

0x04 NOPaxos

NOPaxos主要包含了4个子部分：正常处理部分、Gap Agreement即处理收到丢包通知的情况、View Change即Leader改变or Session变得不可用的情况以及定时同步Logs。NOPaxos正常的处理流程是很直观的，这个远比Paxos的简单。基本流程就是客户端广播一个⟨REQUEST, op, request-id⟩的消息，一个副本收到这个消息之后，递增session-msg-num，并将op写入日志。如果当前的副本为Leader，则会执行op代表的操作。然后每个副本回复客户端REPLY, view-id, log-slot-num, request-id, result⟩，这里log-slot-num为op的索引，如果当前副本为Leader时候，会添加上结果，负责这个字段为空。客户端会等待副本对应消息的回复，当收到了view-id和log-slot-num都对应得上的f+1(一共2f个)个副本且包含了Leader的回复之后，即可认为这个操作已经完成。如果没有在一定时间内收到消息，将重试操作。

Gap Agreement

这部分即使如何处理丢包的情况。丢包的时候NOPaxos会从libOUM收到DROP-NOTIFICATION的消息。这里分两种情况处理，

• Leader收到丢包通知，它会在日志添加一个NOOP的记录，然后发送⟨GAP-COMMIT, log-slot⟩给其它的副本。一个副本收到Leader这个消息之后，覆盖or添加NOOP的日志到指定的位置，然后回复Leader ⟨GAP-COMMIT-REP, log-slot⟩的消息。在收到了f个副本(加上Leader一共f+1个)的消息回复之后回复客户端。这样可以有一个优化，就是先尝试从其它节点获取数据，失败的情况下在执行GAP-COMMIT的操作。
• 非Leader的副本收到丢失信息，可以直接从Leader获取。

View Change

这里为了处理Leader故障or网络故障(如Sequencer失效)的情况。NOPaxos的view ID使用⟨leader-num, session-num⟩的格式。一个副本在1. 它怀疑Leader已经失效、2. 收到一个Session终止的信息、3. 收到VIEW-CHANGE or VIEW-CHANGE-REQ的且带有更加高的 leader-num or session-num的信息的时候，副本选择合适的心的leader-num and/or session-num，并将状态改为ViewChange，且如果改变了session- num，重置session-msg-num为0。然后向其它副本发送⟨VIEW-CHANGE-REQ, view-id⟩消息给其它副本以及发送 ⟨VIEW-CHANGE, view-id, v′, session-msg-num, log⟩消息给Leader。

Paper中没有讨论选举新的Leader问题，应该就是使用一些trivial的方法。假设有Leader的时候， 当Leader收到包括自己在内的f+1个VIEW-CHANGE消息执行和并Log、设置view-id, session-msg-num等值以及向其它副本发送⟨START-VIEW, view-id, session-msg-num, log⟩的消息。副本收到了START-VIEW的消息、且view更大的时候，也要更新自己view-id, session-msg-num等值。然后就是执行listen(session-num, session-msg-num)调用，

... It then calls listen(session-num, session-msg-num) in libOUM. The replica sends REPLYs to clients for all new REQUESTs added to its log (executing them if the replica is the new leader). Finally, the replica sets its status to Normal and begins receiving messages from libOUM again.

另外的同步操作是周期性地在后台完成，将一个副本自己没有收到的信息从其它节点拉取。而NOPaxos的Recovery和 Reconfiguration的机制可以直接采用Viewstamped Replication使用的方式。

0x05 评估

这里具体的信息可以参看[1],

参考

1. Just say NO to Paxos Overhead: Replacing Consensus with Network Ordering, OSDI’16.
2. Eris: Coordination-Free Consistent Transactions Using In-Network Concurrency Control. SOSP ’17.