非易失性数据库系统存储与恢复方法
摘要
非易失性内存的出现从根本上改变了数据库管理系统的内存和持久存储的架构。这些新型NVM设备具有堪比DRAM的速度，但是写到NVM设备后这些数据就具备了持久性。因为现现有的数据库管理系统基于内存是易失的这样的条件下，所以并不能充分利用这项技术。通过NVM，传统数据库管理系统的很多部件都将变得不再必要，并且会降低数据库的性能。
为了更好的理解这些问题，基于不同存储管理架构下我们实现了三种引擎，并对其进行测试：（1）本地更新；（2）copy on write update；（3）基于日志的更新。针对这三种情况，提出了适配NVM的变种，以充分利用NVM的持久性和字节寻址特性。实验表明这些存储架构可以提升5.5倍的性能并减少磨损量2倍以上。NVM适配的恢复协议，允许这些存储引擎重启时立即恢复。
引言
计算机的发展趋势影响着OLTP应用的发展。数据库管理系统时这些应用之中关键部分。优化数据库性能非常重要。从存储器上读写数据的快慢影响着数据库性能。
数据库管理系统也需要处理易失和非易失存储设备之间的权衡利弊。为了断电后仍可以保存数据，数据库系统需要将数据写到非易失设备上，例如SSD或HDD。这些设备只支持以块为单位的慢速批量传输。和非易失设备不同，数据库管理系统可快速从易失的DRAM上读写数据，但是一旦断电，这些数据就会丢失。
另外，有一些固有的物理限制阻止DRAM容量扩展超出今天的水平。即使预留数据不经常使用，也需要阶段性将他刷写，所以使用大量DRAM时也会消耗大量电量。研究表明，DRAM消耗的电量占整个server消耗的40%。
虽然基于flash的SSD具有更大的存储容量，比DRAM消耗的电量更少，但是他还有其他问题。例如，SSD比DRAM速度更慢，仅支持基于block的访问。这就意味着，即使仅仅更新了一个字节的数据也需要将整个block（通常是4K）刷写下去。对于OLTP系统进行大量小规模写的场景来说，这是有问题的。因为这些设备每个地址只支持有限次数的写。减小SSD的尺寸同样会减小他的可靠性并增加干扰效应。电池支持的DRAM缓存等“权益之计”解决方案有助于缓解性能差异，但不能解决这些其他问题。
非易失性内存提供了两种存储介质。NVM是一类技术的统称：相变内存、忆阻器、STT-MRAM等。表1比较了NVM和其他存储技术的特性比较。
然而，如何在数据库管理系统里面充分利用这项新技术还不明朗。NVM几方面特性使得现有的数据库管理系统架构不再适合他们。例如面向磁盘的数据库管理系统：Oracle、DB2、MySQL都是基于块设备的管理系统。这些系统在内存中维护tuples的blocks，并最大化顺序读写。面向内存的数据库管理系统，例如VoltDB、MemSQL，通过某些部件克服DRAM的易失兴。这些部件面对字节寻址并快速随机读写的NVM来说，不再是必要的。
本文针对单NVM存储架构，评估了不同OLTP数据库管理系统的存储和恢复方法。完成三种存储引擎架构：基于日志的本地更新；无日志的copy-on-write更新；基于日志的更新。然后对此三种方法进行优化以充分利用NVM。本文使用基于硬件的模拟器和易失性的CPU CACHE。分析表明，NVM优化方法性能提升了5.5倍并减小了一半NVM写。同时，本地更新的NVM优化方法是最理想的方法，具有最小的开销、设备磨损最小、允许几乎瞬间重启。
本文的工作使用单层的存储架构。现在通过NV-DIMM替换DRAM成为可能，并无需更改现有存储架构即可运行NVM-only数据库管理系统。本文的结构：section 2：讨论NVM，为什么数据库管理系统的存储架构需要重新评估。Section 3：介绍测试的数据库管理系统及本文开发的存储引擎。Section 4：介绍基于NVM的优化方法。Section 5：测试及评估。Section 6：最近工作总结。
背景
下面综述出现的NVM技术并讨论本论文使用的硬件模拟平台。
动机
有两类关系型数据库架构：面向磁盘和面向内存。前者例如IBM的R系统，内存中更新，将更新的记录刷写到磁盘；后者如IBM的IMS/VS，在内存中更新，通过硬盘保证持久性。保证所有改动都持久化的需求影响着这两种架构的设计。依赖于随机访问的速度对数据存储布局进行优化。之前研究表明，OLTP工作负载的数据移动是相当大的。
NVM技术，例如phase change内存和memristors，通过字节寻址和低延迟的loads和stores指令避免这些转换和传输的消耗。这就意味着NVM可用到内存数据库中。但是和DRAM不同，写到NVM就持久化了，因此重启后或者崩溃重启后不需重新加载数据库就可直接访问tuple。
NVM的优点显而易见，在OLTP数据库中充分利用他们非常重要。之前的研究表明，磁盘和内存数据库使用NVM达到的性能差不多，由于记录日志的消耗。这是因为，当前传统数据库都假设内存时易失的，因此需要将数据在持久设备上备份。因此从根本上了解不同存储和恢复方法的特点。
本文部署了三个存储引擎：in-place update引擎；copy-on-write update引擎和log-structured update引擎。每个引擎都支持主键和二级索引。
NVM-aware memory allocator
数据库系统的NVM-aware memory allocator需要满足两个重要条件：第一，提供持久机制确保更改的数据到达NVM后是持久的。这就非常必要，因为事务更改的数据在提交时，很可能人人在易失的CPU cache中。如果断电，这些数据很可能会丢失。分配器需调用特定的API提供持久性机制。首先，通过CLFLUSH指令写回cache line中数据，然后发起SFENCE指令确保来自CPU cache的数据持久。另外，这个数据很可能仍然在内存控制器中，断电后也可能会丢失。从这里开始，我们将上述的持久性机制称为sync原语。
第二个条件，提供一个命名机制，即使系统重启后，指向内存位置的指针也是有效的。分配器需要确保映射内存后的虚拟地址不变。这样，指向NVM的地址在操作系统或数据库重启后，仍然不变。将这个指针称为非易失指针。
NVM的分配器基于开源NVM开发库libpmem。直接将NVM映射到地址空间，和文件系统API不同，访问这样的区域，不需要拷贝数据到用户buffer。操作系统重启后，分配器回收未持久的内存，重新存储内部元数据到一个一致性状态。恢复机制仅在操作系统重启时启用，数据库重启不需，因为分配器会处理所有应用的内存。
测试的数据库
In-place update引擎（InP）
该存储引擎任何时候只有一个版本记录。当事务更新一个字段值时直接覆盖原有记录。这是最有效的更新方法，存储引擎更新记录前不会拷贝一份记录，只有更改字段变动，其他字段不动。基于VoltDB存储引擎进行修改，这是一个面向内存的数据库，不用维护免息磁盘数据库的buffer pool等。InP存储引擎使用STX B tree作为索引。
存储：该存储引擎架构如上图所示。表的存储区域分为两个pool，一个是固定大小的blocks，一个是可变长度的blocks。每个block包含一系列slot集。以固定大小的slots存储表的元组。这就确保元组字节对齐，能够很方便计算出记录偏移。表大于8字节的字段存储到变长slot中，slot的8字节地址存储到tuple的字段域中。
这些block中的元组无序。对于每个表，数据库维护这一个空闲元组slot链表，当一个事务删除tuple时，被删除元组的slot添加到这个pool中。当事务插入一个元组时，首先检查表的pool是否有空闲slot。若pool为空，分配固定导向的block。该存储引擎同样通过分配器几口维护索引并将他们存储到内存。
恢复：上次checkpoint后的事务数据未持久化，需要文件系统中的WAL进行恢复。WAL包括事务ID、表ID、记录ID、新老记录。
最知名的恢复协议是ARIES。存储引擎周期性执行checkpoint，减少恢复延迟及日志占用的空间。我们实验中，首先定位到checkpoint位置，然后回放WAL。我们不对索引进行WAL记录，索引损坏时，恢复后可重建。
copy-on-write update引擎（CoW）
该存储引擎更新前先拷贝记录，更新拷贝的记录。不需要记录WAL。使用不同的director访问数据库中不同版本。最长见的为IBM的R系统的shadow paging。数据库维护这两个查询director：当前director和dirty director。当前director总是指向记录最新版本，只对已提交的事务有影响。为确保事务隔离性，存储引擎维护一个master record，指向当前director。
脏director指向活跃事务正在更改的记录版本。Copy版本被更改成功后，更新脏director指向tuple的新版本。事务提交时，存储引擎自动更新master record指向脏director。存储引擎维护内部page cache确保内存中的热数据页。
CoW使用LMDB的copy-on-write B tree完成shadow paging。
存储：在文件系统中存储directors。元组以HDD/SDD优化的格式存储。每个database独立存储，master record在文件中固定位置。支持二级索引。
即使更新元组一个字段，也需要创建元组的备份。存储引擎需要追踪元组的不同版本，这样才能够回收不用版本记录的空间。该存储引擎具有很大的写放大现象，增加了NVM设备的磨损，缩短了使用寿命。
恢复：如果master record更新前数据库崩溃，重启后脏director之前的更新不可见。因此该存储引擎没有恢复流程。当数据库恢复到在线时，master record指向当前director确保一致性。异步回收脏director，只包含未提交事务的更新。
Log-structured update引擎（Log）
最后一个存储引擎使用log-structured协议。这种方法来自log-structured文件系统，数据库系统中称为log-structured merge（LSM）树。LSM树由一组runs数据集合组成。每个run包含有序元组集合。Runs驻留在易失性内存（MemTable）或持久设备(SSTables)。通过批量更新MemTable即周期性持久化减小写放大。基于LevelDB进行修改。
存储：该存储引擎使用leveled LSM树。MemTable中数据存储在最上层，SSTable位于下一层。MemTable内容重启后丢失。维护一个WAL日志。首先在WAL中记录更新，然后应用到MemTable。日志中包含事务ID、表ID、元组ID、新旧值。为减小IO消耗，批量组提交刷新日志。
在写密集负载中执行很高效，会带来读放大。
恢复：使用WAL恢复。先回放，然后删除未提交的事务，将MemTable恢复到一致性状态。
NVM-aware存储引擎
前述的存储引擎都是基于DRAM和HDD/SDD两层存储级。这些存储设备具有不同的硬件限制和性能特性。非易失性存储设备比DRAM有几个数量级的读写延迟。数据库以块为单位访问非易失设备，而DRAM以字节访问。顺序和随机写性能差距比较大。
In-place update引擎（NVM-InP）
仅仅在WAL中记录tuple的非易失指针。指针和指向的tuple都存储在NVM。可以通过指针访问tuple无需回放。将B tree存储到NVM，重启后无需重建，立即可访问。
存储：表2概述了执行不同操作的步骤。引擎分别使用固定大小和可变长度的slot来存储元组和非内联字段（non-inlined fields）。要在系统重启后回收由未提交事务插入的元组和非内联字段的存储空间，NVM-InP引擎在每个slot的头部保存持久化状态。slot可以处于三种状态之一:未分配、已分配但未持久化以及分配并持久化。系统重新启动后，分配但未持久化的slot将转回未分配状态。
NVM-InP引擎将WAL作为非易失链表存储。它使用原子写的方式将新条目附加到链表中。每个条目都包含事务ID，要修改的表，元组ID以及指向更改操作的指针。这些更改包括用于插入操作的元组指针和用于非内联字段上的更新操作的字段指针。在更新插槽状态为持久化之前，引擎会先持久化此条目。如果不能确保这个顺序，那么在系统重新启动后引擎不能回收未提交事务所消耗的存储空间，从而导致非易失性内存泄漏。在事务的所有更改都安全地保留后，引擎会截断日志。
引擎使用分配器接口维护非易失性B 树实现主索引和二级索引。我们修改了STX B 树库，以便改变索引内部结构的所有操作都是原子的。例如，向B 树节点添加条目时，不是按排序顺序插入key，而是将条目附加到节点中的条目列表。
恢复：系统重新启动后，已提交事务的效果会被持久化，因为NVM-InP引擎在提交时立即保留事务所做的更改。因此，引擎在恢复期间不需要重放日志。但未提交事务的更改可能存在于数据库中，因为内存控制器可以随时刷新包含对NVM所做更改的高速缓存行。NVM-InP引擎因此需要使用WAL来撤消这些事务。
为了回滚（undo）插入操作，引擎使用WAL条目中记录的指针释放元组的存储空间，然后删除索引中与元组关联的条目。在更新操作的情况下，引擎使用before image恢复元组的状态。如果after image包含非内联元组字段，则引擎释放这些字段占用的内存。对于删除操作，它只需要更新索引以指向原始元组。为了正确处理事务回滚和DBMS恢复，NVM-InP引擎只有在确定它们不再需要时才释放由元组或非内联字段占用的存储空间。由于此恢复协议不包括重做（redo）过程，因此NVM-InP引擎的恢复延迟较短，仅取决于未提交事务的数量。
copy-on-write update引擎（NVM-CoW）
NVM-CoW引擎直接持久化元组副本，并且仅在脏目录中记录非易失性元组指针。最后，它使用分配器提供的轻量级持久性机制来在copy-on-write B 树中持久化更改。
存储：元组的存储区域分布在固定大小和可变长度数据的独立池中。引擎保持两个池中每个插槽的持久化状态，类似于NVM-InP引擎。NVM-CoW引擎使用分配器接口存储非易失性copy-on-write B 树的当前和脏目录。我们修改了LMDB中的B 树，以更细的粒度处理修改以利用NVM的字节寻址能力。引擎使用分配器接口维护主记录以支持有效的更新。当系统重新启动时，引擎可以安全地使用主记录访问当前目录，因为该目录保证处于一致状态。这是因为数据结构是只追加（append-only）的，存储在当前目录中的数据永远不会被覆盖。
恢复：由于NVM-CoW引擎不会覆盖提交的数据，因此它没有恢复过程。当系统重新启动时，它首先访问主记录（master record）以定位当前目录。之后，它可以开始处理交易。故障时产生的脏目录占用的存储空间由NVM分配器异步回收。
Log-structured update引擎（NVM-Log）
日志引擎批量缓存MemTable中的所有写，以减少随机访问持久存储[50,43]。但是，这种方法的好处对于仅包含NVM的存储层次结构来说并不明显，因为顺序访问和随机访问之间的性能差距较小。我们在第3.3节中描述的原始日志结构引擎中，周期性地将MemTable刷新到文件系统并压缩SSTable以限制读取放大会带来显著的开销。与NVM-InP引擎类似，NVM-Log引擎会将事务执行的所有更改存储在NVM上的WAL上。
我们的NVM-Log引擎避免了MemTable和WAL中的数据重复，因为它只记录指向WAL中元组的非易失性指针。它不会将MemTable作为SSTable刷新到文件系统，而只是将MemTable标记为不可变，并启动一个新的MemTable。这个不可变的MemTable在物理上以与可变MemTable以相同的方式存储在NVM上。唯一的区别是引擎不会写入不可变的MemTables。我们还修改了压缩过程（compaction）以合并一组MemTable并生成一个新的更大的MemTable。NVM-Log引擎使用NVM-aware恢复协议，其恢复延迟低于传统恢复协议。
存储：NVM-Log引擎使用LSM来存储数据库。树的每个级别都包含一个有序的数据。与日志引擎相似，此引擎首先将所有由事务执行的更改存储在作为LSM树最高级别的MemTable中。更改包括插入操作的元组内容，更新操作的更新字段和删除操作的逻辑删除标记。当MemTable的大小超过阈值时，NVM-Log引擎将其标记为不可变（immutable），并启动一个新的MemTable。我们修改了引擎用来限制读取放大的定期压缩逻辑，合并一组不可变的MemTable并创建一个新的MemTable。引擎为每个不可变的MemTable构造一个布隆过滤器，以尽量减少不必要的索引查找。
与Log引擎类似，NVM-Log引擎也维护一个WAL。但WAL的目的不是重建MemTable，而是从MemTable中撤销（undo）未提交事务的影响。表2显示了NVM-Log引擎执行的操作的概况。与NVM-InP引擎类似，这个新引擎还是将WAL作为非易失性链表条目存储。当事务插入元组时，引擎首先将元组刷新到NVM，并将非易失性元组指针记录在WAL条目中。然后它将持久化日志条目并将该元组标记为持久化状态。最后，它在MemTable索引中添加一个条目。事务提交后，引擎会截断相关日志条目，因为记录在MemTable中的更改已经是持久化的。它的日志记录开销比Log引擎低，因为它记录的数据较少并使用分配器接口维护WAL。引擎使用第4.1节中描述的非易失性B 树作为MemTable索引。因此，重新启动时不需要重建索引。
恢复：事务提交时，事务执行的所有更改都会保留在内存组件中。在恢复期间，NVM-Log引擎只需撤消MemTable上未提交事务的影响。同时它的恢复延迟低于Log引擎，因为它不再需要重建MemTable。
