FOEDUS: OLTP Engine for a Thousand Cores and NVRAM

0x00 引言

FOEDUS是一种同时使用DRAM和NVRAM的内存数据库。FOEDUS的一个核心的idea是Dual Page。一个Dual Page指针指向两个逻辑上相等的数据Page，一个可变的版本保存到DRAM中，叫做Volatile Page，它可能为NULL。另外一个不可变的版本保存NVRAM中，叫做Snapshot Page。另外在FOEDUS中，所有的信息都保存在Page中，

... In all remote-ness settings, FOEDUS performs 2.4x faster than SILO on 240 cores and 2x faster on 60 cores. FOEDUS is less affected by transactional logging, too. Whether FOEDUS writes out logs to tmpfs or NVRAM, it only issues a few large sequential writes for each epoch, thus the latency has almost no impact.

0x01 基本架构

FOEDUS是一个多版本的数据，使用的并发控制协议为OCC的一种变体，基本就是在Silo使用的OCC上改进而来。FOEDUS使用Master-Trees作为主要的数据结构，Master-Trees为Masstree和Foster Btree的结合体。为了更好地利用NVRAM，FOEDUS使用了Stratified Snapshots的方法。另外FOEDUS也使用于Silo很类似的Logging方式来保证持久化。

0x02 日志和事务提交

FOEDUS使用和Silo很类似的Logging方式。FOEDUS的工作线程将日志数据写入log-buffer，之后会被日志线程写入到日志文件中。FOEDUS使用的是逻辑日志。FOEDUS使用的事务提交协议也是从Silo的改进而来，主要的改动就是为了适应NVRAM的应用。由于FOEDUS中两种Page的存在，在一些情况下FOEDUS会删除一个和NVRAM相同的DRAM中的Page。在这样的操作之后，一个事务可能只会看到Snapshot Page，从而基于这个Page添加一个新的Volatile Page。在一些情况下，这个可能导致违反serializability(另外一个事务读取了Snapshot Page)。

为了解决这个问题，FOEDUS在read-set和write-set之外增加了pointer-set。当一个可序列化事务由于一个Dual Page没有Volatile Page得去使用Snapshot Page时，将这个Volatile Page指针的地址加入到pointer-set中，在后面验证操作的时候发现这个Dual Page有了Volatile Page，就会abort事务。在一般情况下，一个执行事务的这个pointer-set都比较小。

0x03 Stratified Snapshots

FOEDUS中Stratified Snapshots是一种DRAM和NVRAM配合使用的一种方式。Stratified Snapshots是一系列的快照，是一系列的原因是这些快照是Log Gleaner(日志收集器)从日志文件构造的，但不是一次性构造的，这种工作方式在大型的数据中很有意义。Log Gleaner会周期性的收集事务的日志，然后使用类似map-reduce处理方式从中构建出Snapshot Page，顺序写入NVRAM。这些新的Snapshot Page可以将DRAM中的Volatile Page替换，从而减少DRAM的使用，也达到了DRAM和NVRAM配合使用的目的。这里可以看出，FOEDUS中NVRAM的Page并不是简单的DRAM中的Page写入到NVRAM中而来的。

• 每一个会被分配一个分区。另外分区的方式考虑到了NUMA之类的一些特性，它会根据一些访问的统计信息去试图将Snapshot Page保存在最频繁访问的节点上面，以减少远程访问的开销；

• Log Mapper。Mapper的任务就是初步处理日志数据，它会先读取一定量的数量，然后根据Key排序，在使用每个分区的边界的Key将这些数据划分，在发送给对应的Reducer,

  It first reserves space to copy into the reducer’s buffer by atomically modifying the state of the reducer’s buffer. It then copies the entire bucket (usually MBs) into the reserved space by single write, which is much more effcient than issuing many writes especially in a remote node... Finally, the mapper atomically modifies the state of reducer’s buffer to announce the completion of the copying.
  

• Log Reducer，一个Reducer维持了两个Buffer，这里就是一种双Buffer的机制。Mapper写入目前的Buffer，在满了的时候Reducer转换一些当前使用的Buffer。Buffer中的数据会被Reducer写入一个文件之中。在Mapper都完成工作的时候，Reducer将会将前面得到的数据执行归并排序(sorted by storages, keys,and then serialization order)。排好序就方便之后的使用。

• FOEDUS通过这里批量处理的方式构建出新的Snapshot Pages，Log Gleaner然后会合并这些Pages，然后它会将一些元数据写入到一个快照元数据文件中。

• 在前面的操作完成之后，Log Gleaner回去尝试将在这个处理过程中没有修改的Volatile Pages替换为NVRAM中的Snapshot Page。当一个Volatile Page覆盖的Key的范围和一个Snapshot Page完全相同是，它们是可以替换的。这里在Reducer的阶段会去处理两种Page对应的情况，安排好Snapshot Page覆盖的Key的范围。但在处理的过程中Valatile Page又会有变化。在可以替换的情况下，一个Volatile Page对应的Snaphot Page的指针会被设置到对应的Daul Ponter上面。

• 在添加了Snapshot Page的指针之后，FOEDUS使用锁定新事务执行的方式来Drop掉Volatile Pointers，

  ...that this does not mean the entire log gleaner is a stop-the-world operation. Dropping volatile pointers based on an already-constructed snapshot is an instantaneous in-memory operation that finishes in milliseconds. In the case of TPC-C experiments, it takes only 70 milliseconds even after gleaning all data (initial data population).
  

• 另外，FOEDUS在DRAM中保存了两个Page Pool。一个就是服务于Volatile Page，一个用于Snapshot在DRAM中的缓存，这个缓存在一些情况下也是有用的，也可以避免一些重复的IO请求。

Crash Recovery

在FOEDUS中，Snapshot Page的设计和生成的方式简化了FOEDUS恢复的设计。FOEDUS只需要在合适的位置启动Log Gleaner即可。

0x04 评估

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

参考

1. FOEDUS: OLTP Engine for a Thousand Cores and NVRAM，SIGMOD’15.