FaSST: Fast, Scalable and Simple Distributed Transactions with Two-sided (RDMA) Datagram RPCs

0x00 引言

FaSST也是一个利用RDMA实现的支持In-Memory事务的系统。FaSST的对比的对象比前面额度DrTM，与DrTM使用One-sided的RDMA操作加HTM实现的不同，FaSST认为，在类似这样的系统中，使用Two-sided Datagram来实现其中的一些操作能够获得更加好的性能，

... FaSST outperforms FaRM on the TATP benchmark by almost 2x while using close to half the hardware resources, and it outperforms DrTM+R on the SmallBank benchmark by around 1.7x without making data locality assumptions.

之前的利用RDMA实现的RPC或者是Key-Value之类系统，很多利用了One-sided的操作。而这篇Paper中提出了使用了RDMA的Two-sided (RDMA) Datagram能够带来的各种的优点，

• Datagram的使用使得每个CPU创建一个Datagram Queue Pairs(QP)，与其它的远程CPU核心进行通信，可以将这里需要维持的QPs保持在一个较小的数量，降低这里带来的开销。而其它的一些方式有一些QPs太多带来的可拓展性的问题，或者是共享一些QPs的时候处理锁的问题带来的锁的竞争，

  ... Providing exclusive access to QPs with connected transport, however, is not scalable: In a cluster with N machines and T threads per machine, doing so requires N ∗ T QPs at every machine, ... Sharing QPs reduces CPU efficiency because threads contend for locks, and the cache lines for QP buffers bounce between their CPU cores...
  

• 与Connected方式相比，Datagram的方式可以使用Doorbell Batching，也就是批量通知的方式来减少CPU的消耗。

0x01 RPC

使用Two-sided Datagram的方式来实现RCP一个要考虑的问题就是处理丢包的问题。虽然理论上这样的方式是可能丢包的，但是Paper中的测试表明，这个丢包的概率及其小，FaSST测试来超过50PB的数据都没有发现丢包的现象，所以FaSST这里采用的方式是在发现有丢包之后重启受影响的进程，emmm为什么这里这样就能处理了…… 。相比于FaRM，FaSST的设计早测试数据中实现了13.9倍的单核性能FaSST的RCP设计另外几点，

• Coroutine，FaSST使用协程的方式来实现，依次来掩盖网络的延迟。关于使用用户态协程之类在这样的环境下使用，在OSDI ’18上面也有一篇类似的Paper，里面的取得的效果是很好看的。FaSST则是直接使用了boost库线程的方案，这个Coroutine特性也可能会在C++20 or 23的时候被添加到C++标准库中。FaSST将协程分为Master和Worker。Worker负责处理运行应用的逻辑和发送RPC请求，而Master则负责轮询网络处理新达到的request or response。

• 在实现的优化上，FaSST也使用了一些批量请求和批量回复的处理方式。批量处理的话，一个批次里面的message FaSST限制它们的目的机器必须是同一台。批处理在这里不仅仅是平摊了每个RPC处理的开销，而且有利于利用前面的提到的RDMA的Doorbell Batching机制。

• Master协程会会记录每个Worker收到的回复，如果计数上面对不上，在超时的时间过后，Master协程就会去重启这个进程。Master的机制能够保存只有丢包的Worker会收到丢包的影响，而其它的Worker都可能正常提交它们的事务，这里使用的是等待一段时间的方法，

  ... Note that, before it is detected, a packet loss affects only the progress of one worker, i.e., other workers can successfully commit transactions until the loss is detected. This allows us to use a large value for timeout without affecting FaSST’s availability. We currently set timeout to one second.
  

• FaSST的RCP的一些限制就是还不能支持超过MTU的RPC请求，在FaSST测试的环境中为4KB，因此采取了一些措施来缓解这个限制。既是是这样，这里还是限制了后面事务实现的时候的记录的大小。

0x02 事务

和前面的HTM不同，FaSST的事务的实现没有采用2PL结合HTM实现的方式，而就是使用了锁。同样的，FaSST实现的memstore也是一个Hash Table。这里就是基于MICA实现的，MICA就是这个实验室之前的一个Key-Value Server的设计。这样看来，FaSST可以看作是在MICA的基础之上，通过添加基于RDMA Datagram的RPC，再加上一些事务的机制发展而来。同样地，记录中与事务相关的字段就是一个64bit的 Header。它包含了两个部分，一个是1bit的锁，另外一个是63bit的版本号。FaSST使用了一个基于OCC的并发控制协议，使用两阶段提交的机制来进行事务的提交，两阶段提交在FaSST的环境下面是很适合的。基于OCC的并发控制可能让FaSST收到一些OCC本身限制的一些影响。另外，FaSST同样支持副本，一般的操作在Primary副本上进行，操作会被同步到backup上面。

FaSST事务执行的流程如下，

• 执行这个事务的Worker称之为Coordinator，这个Coordinator先读取记录的Header和Key的值，这些数据的读取都会从Primary中读取。对于写集合里面的记录，会请求对数据加写锁。如果读集合 or 写集合(写集合一定在读集合中)中的数据记录有被加锁的，这个事务就得abort。FaSST的设计使得这些操作可以通过一个RPC完成，这里是和DrTM的机制对比。

• 在锁住了写集合之后，Coordinator需要检查读集合中的版本，如果从第一步到现在记录的锁状态或者是版本变化了的话，这个事务得abort。

• 在第二步成功了之后，事务就可以尝试提交，事务使用复制提交log到f+1个副本上面的方式来实现提交，这里可以容忍f个副本故障。这个log里面会包含写集合中的Key-Value的现象，以及它们取回的版本。

• 在写日志成功之后，向backup的副本请求一个RPC以在backup副本上面提交。这里会等待到backup副本返回确认，

  This wait ensures that backups process updates for a bucket in the same order as the primary. ... FaSST’s updates contain only one key-value item and are therefore smaller, but cannot be dropped.
  

• 在前面的操作完成之后，向Primary副本提交。Primary副本在收到这个RCP请求之后，会更新写集合中的版本信息，在对其进行解锁。到这里实际的修改才会完成。

FaSST提供的一些关于事务的API：

* AddToReadSet(K, *V) and AddToWriteSet(K, *V, mode) enqueue key K to be fetched for reading or writing, respectively.
* Execute() sends the execute phase-RPCs of the trans- action protocol.
* Commit() runs the commit protocol, including vali- dation, logging and replication, and returns the commit status. Abort() sends unlock messages for write set keys.

0x03 评估

这里的详细信息可以参看[1],

参考

1. FaSST: Fast, Scalable and Simple Distributed Transactions with Two-sided (RDMA) Datagram RPCs, OSDI’16.