Eris -- Coordination-Free Consistent Transactions

Eris: Coordination-Free Consistent Transactions Using In-Network Concurrency Control

0x00 引言

如果一个网络不会丢包也不会乱序，那么在这个网络上面的分布式共识问题，分布式并发控制等都是很容易实现的问题，然鹅这两点现在的网络都不能满足。Eris就尝试在对网络本身进行一些改造，来达到这样的效果，这篇Paper和OSDI‘16 上面的NOPaxos出自同一个实验室，它们使用的基本思路也是一致的，特别是OUM模型，

... it can process a large class of distributed transactions in a single round-trip from the client to the storage system without any explicit coordination between shards or replicas in the normal case. It provides atomicity, consistency, and fault tolerance with less than 10% overhead – achieving throughput 3.6–35× higher and latency 72–80% lower than a conventional design on standard benchmarks.

0x01 Groupcast and Multi-Sequenced Groupcast

事务在Eris中有两种类型。一种是独立事务，不支持与客户端交互，比如存储过程，这里和H-Store中使用的方法是类似的。另外一种就是通用事务，就是常见的使用Begin开启事务，中间执行一些操作，然后使用Commit后者Abort结束事务。 Eris也使用分层的设计，被分为三层，

最下面一层的是in-network concurrency control layer，使用新的网络原语来构建事务的一个一致性的顺序，但是不能保证消息可靠达到；
中间的一层为independent transaction layer，在下一层的基础之上添加可靠达到和原子性；
最上面的一层为general transaction layer ，提供一般事务之间的隔离性

为了处理In-Network并发控制，Eris引入了Groupcast和Multi-Sequenced Groupcast的概念。Groupcast是一种多播的拓展，是将消息发送到客户端指定的一个多播组，Multi-Sequenced Groupcast则是一种支持按序而不保证可靠的Groupcast。 Multi-Sequencing是NOPaxos中OUM的拓展，在NOPaxos中只使用了单一的一个序列，在应用到Eris这里的时候，有时候只需要将消息送达部分的参与者，而不是全部，以及只使用一个Sequence情况下丢包通知不好处理。这里使用多个Sequence是一个很直观的做法，但是这样会有一个问题，比如如果有两个事务T1 T2都被发送到分区A和B执行，在使用多个Sequence的时候，T1和T2到达A、B的顺序是不能保证的。所以Eris必须要保证这样情况下的顺序保证。Eris使用了multi-stamp来实现这种的顺序保证。Multi-Sequenced Groupcast就是满足Eris通讯要求的一种原语，除了前面的顺序保证外，还有另外的几个特点：1. 不可能，消息传达是否目的地是不能保证的，这里和OUM是一致的，2. 偏序，即任意两条消息接受者存在相同的时候，这两条消息必须保证顺序达到，3. 和OUM一样的丢消息通知的语义，对于发送的一个信息，其接受者会收到这个信息或者是在下一个多播信息之前这个信息被“丢”的通知，所有的进程没有收到这个信息和丢失通知。

  Multi-sequencing can thus establish an ordering relationship between messages with different sets of receivers. This is an important distinction with OUM, which only supports ordering within a single multicast group. Multi-sequencing requires an ordering relationship between any two messages that have some receiver in common, i.e.,R(m1) ∩ R(m2)􏰀 != empty.

Multi-Sequencing 设计与实现

网络层的Sequencer的设计和NOPaxos中的设计基本一致，也是基于SDN。这里一个新的概念就是multi-stamp，一个multi-stamp的格式为一组⟨group-id, sequence-num⟩。对于每一个目的组，每一个Sequencer都维持一个单独的计数器，在这个Sequencer接受到一个包之后，从Groupcast的Header找到对应的组(1个or多个)，确定对应的计数器，对这些计数器分别递增，然后将相关的编号的消息都写入到包的Header中。这里在Header包含所有的编号主要即使为了既能保证顺序和丢包探测，另外就是可以与其它的目的组协调，可以从其它的组获取丢失的消息。

和NOPaxos中类似，为了处理Sequencer故障的情况，Eris引入了epoch的概念，这个值会添加到Groupcast的Header中。Sequencer故障由SDN控制器处理，在SDN控制器怀疑一个Sequencer故障的时候，它会选择一个新的Sequencer，递增epoch的值。当一个机器收到一个比它之前知道的epoch高的消息之后，给Eirs回复NEW-EPOCH的通知，Eris这里和NOPaxos一样，也要在这样的情况做一些处理，在下一个epoch开始之前达从一致。

0x02 处理独立事务

对于每一个分区，Eris中和NOPaxos中Leader一个类似的角色就是Designated Learner (DL)，另外为了处理丢包通知DROP-NOTIFICATION和网络故障导致的NEW-EPOCH异常情况，Eris引入了Failure Coordinator (FC)，FC负责从丢包和网络故障中恢复一致性。FC使用一般的方法来实现多副本，Eris只有在出现异常的时候引入FC处理。一个Eris中的副本要保存这样的一些信息，

Replica:
• replica-id = ⟨shard-num, replica-num⟩
• status — one of Normal, ViewChange, EpochChange
• view-num — indicates which replica within the shard is believed to be the DL
• epoch-num — indicates which sequencer the replica is currently accepting transactions from
• log — independent transactions and NO-OPs in sequential order
• temp-drops — set of tuples of the form ⟨epoch-num,shard-num, sequence-num⟩, indicating which transactions the replica has tentatively agreed to disregard
• perm-drops — indicates which transactions the FC has committed as permanently dropped
• un-drops—indicates which transactions the FC has committed for processing

Eris由五个子协议组成，orz：正常处理、消息丢失处理、一个分区内处理DL改变、处理epoch改变以及同步，

正常处理，Eris通过Groupcast发送消息，副本处理之后恢复⟨REPLY, txn-index, view-num,result⟩，只有DL会实际执行这个事务，并附上结果。Eris在接受到包含DL在内的超过一半的副本的匹配的txn-index, view-num, 和 epoch-num之后就算处理完成。如果一个副本已经将这个事务的ID标记为perm-drops或者temp-drops，这个副本不能处理这个事务，为perm-drops则添加一个NOOP记录到日志中，temp-drops则需要等待。
消息丢失的时候是FC来协调处理。在副本收到丢消息的通知的时候，会请求FC，FChui尝试从其它副本补齐数据。根据情况协调这个事务是可以从其它节点恢复还是只能放弃，这个过程中事务会存在临时放弃or永久放弃这样的状态。具体的细节很多[1]。
一个分区内处理DL改变，这里使用了和Viewstamped Replication类似的方法。在这里选举DL的方法是很trvial的。在一个副本怀疑当前的DL故障之后，就发送VIEW-CHANGE给下一个的DL，下一个的DL在收到了超过半数的副本的消息之后即可。之后就是将各个副本的处理的进度“同步”，达到一个共识。另外这里也要注意处理perm-drops和temp-drops的事务的情况。

处理epoch改变，这里也主要是FC协调处理的，会设计到所有的分区。副本的NEW-EPOCH通知从网络从而来，收到这个通知之后副本会停止处理，然后向FC发送EPOCH-CHANGE-REQ消息。之后FC会向所有的副本请求需要的消息，每一个分区都要求收到超过半数的恢复，然后作出新epoch的决策，并使副本直接达成一致，

 For each shard, it takes the highest view-num it received and a log that contains all of the transactions the FC received which have that shard as a participant (with transactions the FC previously dropped being replaced by NO-OPs). It sends that state as a START-EPOCH message to all replicas, which adopt the new view-num and log, execute any new transactions, and clear their temp-drops, perm-drops, and un-drops.

同步，这里的作用和方法同NOPaxos中的是类似的。Eris中不保证所有的节点都有完整的消息(DL除外)，所以一个副本需要从其它节点拉取自己没有收到的信息。

0x03 通用事务

对于通用事务的处理方式，Eris采用了和Calvin类似的方法，称之为reconnaissance queries，

... That is, before sending the preliminary component of a general transaction, the client sends single-message, non-transactional reads to determine the full read/write sets. The preliminary transaction checks that the values returned by reconnaissance queries are still valid. If any have been changed, the general transaction will be aborted. Otherwise, the conclusory transaction can proceed as above.

对于客户端故障情况地处理，如果一个副本怀疑客户端已经故障，它可以单方面决定abort这个事务，通过发送一个Abort的指令作为一个独立的事务来处理。

0x04 评估

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

eris-perf

参考

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