Let’s Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems
这篇论文主要讲述了在NVM设备出现后，原有的面向DRAM和磁盘设计的DBMS系统如何更加优雅的利用NVM设备所带来的优势，并通过现在DBMS系统中常用的三种引擎来探讨了如何通过NVM设备来讲它们的数据存储和故障恢复模式变得更好，并选取了对应引擎的工程实现产品加以验证。具体的三种引擎为：
(1)In-place Updates (InP)，VoltDB
(2)Copy-on-Write Updates (CoW)，IBM’s System R
(3)Log-structured Updates (Log)，LevelDB
作者提出，原有的DBMS的架构中，DBMS主要负责处理易失性设备（DRAM）和非易失性设备（SSD/HDD）之间的trade-off，DRAM设备能带来更快的访问速度，但同时也要承担断电丢失数据的风险，因此需要将数据写入SSD/HDD中进行持久化。新的NVM设备兼具DRAM和SSD两者的特性，相对DRAM来说具备相同的按字节读取的访问模式，以及接近DRAM的访问速度，且具备更加大的存储容量，但成本更加低廉。相对SSD/HDD，提供更加快的访问速度，并且消除了随机访问和顺序访问速度的差异。 NVM设备具备多种形态，例如：phase-change memory（PCM）, memristors（RRAM）, 以及 STT-MRAM（MRAM），下图展示了各个形态的NVM设备访问性能：
在本篇论文中，作者使用了一种Intel所提供的NVM Hardware Emulator来将内存模拟为NVM设备，通过限制DRAM的读写速率和带宽来模拟NVM设备。通过两种不同的接口访问NVM设备：
- Allocator Interface:通过模拟器将内存模拟为NVM设备，并提供POSIX malloc的访问接口
- Filesystem Interface:通过模拟器将内存模拟为NVM卷设备，提供文件系统的访问接口
NVM的出现颠覆了现有的DBMS架构设计，原有的架构需要做出一些改动，来适应新NVM带来的新的特性，作者基于这三种引擎对Storage和Recovery过程进行了深入的研究，并设计了在NVM设备上的新引擎，以提升三种引擎在NVM设备上的性能。新的基于NVM设备的引擎为：
(1)In-place updates with logging (NVM-InP)
(2)Copy-on-write updates without logging (NVM-CoW)
(3)Log-structured Updates (NVM-Log)
作者分别对原有的架构方案进行了深层次的剖析，并针对其各自的特性，设计了在NVM设备上的新架构，以最大化利用NVM设备的性能。原有架构方从Storage和Recovery两个方面进行了深入的分析，具体如下：
In-Place Updates Engine (InP)
InP引擎的数据只有一个版本，写入之后的读取和更新都发生在同一个位置，在Inp中，索引结构都采用了STX B+tree库。
InP引擎选取了VoletDB作为实验对象。
(1)Storage
如图a所示，即为Inp的数据存储结构，所有的表数据被分为了两个独立的pool，定长数据Pool（Fixed-Sized Blocks Pool），可变长数据Pool（Variable-Size Blocks Pool），每个Block由多个slot组成，每个slot大小为8字节，数据小于8字节时，数据存储在定长数据Pool中。当大于8字节时，将存储在可变长数据Pool中，并且在定长数据Pool中记录其在变长数据Pool中的位置。
DBMS管理所有的未分配的slot，当有新的Insert操作后，会去Block Look-Up Table中查找是否有空余的slot，如果有则通过Allocator来分配，当有Delete操作时，Allocator会将slot归还至Pool中，并且Allocator还负责管理在内存中的索引信息。
(2)Recovery
如图a右边部分所示，在InP引擎中，对数据的写入和更新操作要包含在一个事务访问中，在事务过程中和一次checkpoint发生之前，都需要保证把修改操作写入至WAL log中，且该条log包含唯一的事务ID，表名，修改的Block ID，以及该Block修改前后的镜像等数据。InP引擎的Recovery遵循**ARIES **协议，DBMS会周期的进行checkpoint机制，每次进程重启会优先加载checkpoint，然后才会回放WAL log。
Copy-on-Write Updates Engine (CoW)
CoW引擎的特点是不会修改原有的数据，每当发生数据更新操作时，都会Copy一个原数据的副本，并对这个副本进行修改，在事务提交后，会将修改后的数据置为最新数据。为此，CoW设计了两个不同的目录来方便查找：
- The current directory
- The dirty directory
The current directory中保存了最新版本的数据，The dirty directory中保存的是当前事务修改之后的数据，当事务执行完成并提交之后，数据库引擎会将当前最新的数据指向修改后的数据。
Cow引擎选取了IBM的System R作为实验对象，其使用了**LMDB’s copy-on-write B+trees **来实现更加快速的数据副本创建过程。
(1)Storage
如图b所示，CoW引擎的数据存储在文件系统中，每个表的数据以独立文件的形式存储在SSD/HDD中，且每条记录都是连续的，在文件的固定偏移量位置会存储该数据库的主记录，主记录指向了最新的数据版本。CoW引擎存在一个很大的缺陷，即每当数据的修改只是修改了该数据的子集，但也需要将整个元组记录进行拷贝，创建元组的副本。而且引擎还需要维护不同版本的数据到B+Tree的索引，在对于没有索引的数据需要异步进行清除以释放存储空间。这些机制会带来大量的写放大，增加了NVM设备的磨损，会缩短NVM设备的寿命。
(2)Recovery 因为CoW引擎的机制并不需要记录WAL log，当DBMS发生进程Down时，如果出现事务还未提交的情况，即主记录还未发生切换到The dirty directory上，在Recovery时只需要恢复主记录指向的The current directory即可，至于The dirty directory 中的数据，会有异步的线程对其完成回收操作。
Log-structured Updates Engine (Log)
Log引擎使用LSM Tree作为其数据结构，在数据写入过程中，会优先记录WAL log，然后将数据写入至内存的Memtable中，MemTable会周期的Flush至磁盘生成sstable，并清除已经Flush的Memtable在WAL log中的记录。
Log引擎选取了Google的LevelDB作为实验对象。
(1)Storage
图c展示了Log引擎的架构，Log 引擎使用了level LSM Tree作为其数据结构，最新的数据修改优先写入至MemTable中，并在其到达一定的大小阈值时，Log引擎会将其作为一个不可变的SSTable Flush到文件系统中，并为之构造Bloom Filter来加速其查询效率。数据从最顶层的Memtable开始，随着时间的推移存储在LSM Tree的下部的sstable中，下一级level的大小是上一级的K倍，K是LSM Tree的增长因子。系统发生重启时，内存中的MemTable的数据将会丢失，所以需要记录WAL log以保证数据的安全性，为了提升WAL log的写效率，通常会采用多条事务合并组提交的方式来刷写WAL Log。Log引擎非常适用于写密集型的场景，即写多读少的场景，因为LSM Tree的结构大大减少了对磁盘的随机写入，在内存中的MemTable中将其转换成了对磁盘的顺序写操作。但Log引擎也存在他的缺点，即有过多的读写放大，因为其需要查询所有Bloom Filter命中的文件，为减少读放大带来的开销，需要周期的对SSTable进行Compaction操作，但会带来更多的写放大。Log引擎的Delete操作也只是追加一个删除标识到LSM Tree中，读取会优先读取到删除标识，真正的物理删除也需要在Compaction阶段才能完成，并释放磁盘的物理空间。
(2)Recovery
在进程发生重启之后，Log引擎会加载其WAL log，完成对数据的回放工作，对于已经完成事务提交的记录，需要写入内存中重新生成MemTable，对于没有完成事物提交的记录，则跳过。
基于NVM设备设计的新方案为，也从从Storage和Recovery两个方面分别进行了优化，具体如下：
In-Place Updates Engine (NVM-InP)
在传统的InP引擎中，最大的问题是在WAL log和数据存储区域存在大量的数据重复，一份数据即要写入WAL log用于做数据Recovery，同时也要保存在数据存储区域中。
因此为了解决这一问题，作者设计了NVM-InP引擎，该引擎在处理数据写入操作时，并不是把原有的数据拷贝至WAL log中，而是在WAL log中记录了一个不会因断电而丢失的指针来指向数据（NVM设备），因为NVM中保存的数据不会因断电而丢失，故而当DBMS发生重启时，只需要通过指针来访问到数据元组即可。并且将使用非易失性B+trees 来存储索引，从而避免在重启时索引的重建工作。
(1)Storage
如图a所示，即为NVM-InP引擎的架构，该引擎同样包含了定长数据Pool（Fixed-Sized Blocks Pool），可变长数据Pool（Variable-Size Blocks Pool），每个Block由多个slot构成，每个slot具有三种状态，分别是：
- 未分配状态
- 分配未持久化状态
- 持久化状态
当系统发生重启时，分配未持久化状态的slot将转变为未分配状态。
在NVM-InP引擎中，WAL log为一个非易失性链表，追加新元素操作是原子的，每条log中包含了唯一的事务ID，表修改信息，元组块ID，以及指向改变操作的指针。NVM-InP引擎需要保证在数据写入slot之前优先写成功WAl log 的指针，如果不能保证这一点，会导致系统重启时无法清除未Commit的slot数据，因此会导致NVM设备的空间浪费，在确保所有的修改都持久化之后，将会对WAL log进行清除。
NVM-InP引擎还支持通过non- volatile B+trees 来实现主键索引和二级索引，因为NVM的特性，在系统重新启动时也省略了重建索引的步骤，提升了启动效率。作者还修改了STX B +树库，将改变索引内部结构的所有操作都修改为原子的，以保证系统重启时索引的一致性。
(2)Recovery
因为NVM-InP引擎在事务提交时会直接修改原数据，因此在Recovery阶段并不需要回放log，但需要从WAL log中撤销那些未Commit的数据。例如：针对未Commit的写入操作，会通过WAL log中的指针释放其占用的slot空间，并清除对应的索引数据；针对未Commit的更新操作，引擎会重新加载元组先前状态的镜像，恢复原数据状态；针对未Commit的删除操作，只需要更新索引指向原数据元组。
NVM-InP引擎的Recovery速度之和未提交事务的个数有关，未提交事务越少，则速度越快，反之亦然。
Copy-on-Write Updates Engine (NVM-CoW)
原有的CoW引擎最大的问题在于每当只是修改了一个Block的子集时，依然要拷贝整个Block，当事务提交之后，还需要将主记录指向修改后的The dirty directory，这些操作都需要通过操作系统内核的VFS来实现，会损耗很多性能，因为涉及到大量的内核态到用户态之间的数据拷贝。
NVM-CoW引擎为了解决这个问题，主要有话了三个部分，具体为：
- 使用了非易失性的copy-on-write B+tree
- 直接持久化拷贝后的元组副本，并且在The dirty directory中保存非易失性指针
- 用更轻量级的持久化机制来持久化copy-on-write B+tree中的更新操作
(1)Storage
图b描绘了NVM-CoW引擎的结构。元组数据的存储区域被划分为了类似于InP引擎中的定长数据Pool（Fixed-Sized Blocks Pool）和可变长数据Pool（Variable-Size Blocks Pool），并也将其划分为了Block和多个slot的模式。NVM-CoW引擎使用非易失性copy-on-write B+tree来保存The current directory和The dirty directory。作者修改了LMDB中的B+Tree，利用NVM的按字节访问的特点精细化了B+Tree的数据修改。当事务更新元组时，NVM-CoW引擎首先拷贝副本，并且修改副本的值，然后在The dirty directory中保存指向该副本的非易失性指针，同时还支持合并多个事务进行批量执行的模式来降低对NVM设备的访问频次，然后接下来将会持久化The dirty directory中的数据，最后原子更新主记录并指向The dirty directory。NVM-CoW引擎通过内存屏障来保证在系统重启时，只有已经提交的事务才具备可见性。
(2)Recovery
因为NVM-CoW引擎从来不会覆盖已提交的数据，所以并不存在Recovery机制，当系统发生重启时，只需要将主记录指向The current directory即可，会有异步的线程会清理The dirty directory的数据来释放NVM设备的存储空间。
Log-structured Updates Engine (NVM-Log)
原有的Log引擎先写入内存中的MemTable，到达一定的阈值后再Flush至磁盘，因为磁盘的顺序写入性能要远高于随机写入性能，但这一点再NVM设备上不再非常适用，因为NVM设备的顺序访问和随机访问的性能相差无几，所以不需要再做这样一层缓存操作了。原有的Log引擎周期Flush MemTable到磁盘上，并生成SSTable，并对其进行Compaction操作，这些操作会带来大量的读放大而产生大量的性能开销。与NVM-InP引擎类似，NVM-Log引擎需要为数据修改操作在NVM设备上记录WAL log。
NVM-Log引擎避免了数据在MemTable和WAL log中重复写入的空间浪费，现在只需要在WAL log中保存一个指向真实数据修改的指针即可。相比之前的Flush MemTable操作，现在只需要将存储在NVM设备上的MemTable置为不可改变的状态，并且作者还修改了Compaction算法让多个MemTable能合并为一个大的MemTable。同时NVM-Log引擎适用NVM-aware协议来减少Recovery的时延。
(1)Storage
如图c所示，即为NVM-Log引擎的架构，其使用了LSM Tree作为其数据库的存储结构。事务对数据的修改首先在MemTable中执行所有的更改操作，包括写入，更新，删除等操作。当MemTable的大小超过一定的阈值后，会将其转化为一个不可变的状态，并创建一个新的MemTable提供写服务，并为之生成Bloom Filter来提高查询效率，作者还修改了Compaction算法，限制了周期Compaction的频率，能让更多的MemTable参加每次的Compaction，以降低读放大带来的开销。
与Log引擎相类似，NVM-Log引擎也需要维护WAL log，但不同的是，NVM-Log引擎的WAL log不是用来在进程重启时重建MemTable的，而是为了撤销未提交的事务带来的数据影响。在数据写入时，会将WAL log中创建一个指向MemTable的非易失性指针，在事务提交之后，会清除WAL log中的记录。NVM-Log引擎还使用了非易失性B+Tree来作为MemTable的索引，因为NVM设备的特性，在进程发生重启时，也不需要重建索引。
(2)Recovery
在NVM-Log引擎中，当一个事务提交之后，就代表着对数据的修改已经持久化至NVM设备中，因此在Recovery阶段中，只需要执行undo操作来将那些未完成事务提交的数据从MemTable中清除，相比原有的Log引擎重建MemTable的过程下率提升了很多。
总的来说，针对NVM设备在三种不同的引擎上所做的修改来看，总结为以下几点：
- 通过WAL log中的非易失性指针来减少数据重复存储
- 利用NVM设备特性避免索引的重新加载
- 利用NVM设备特性建立更加轻量级的持久化数据结构
Benchmarks
通过使用YCSB对6类引擎做了测试分析，分别在以下场景下做了测试：
- Read-Only: 100% reads
- Read-Heavy: 90% reads, 10% updates
- Balanced: 50% reads, 50% updates
- Write-Heavy: 10% reads, 90% updates
并且作者修改了YCSB的测试程序，并设计了两种不同的skew数据访问来控制其数据访问热度：
- Low Skew: 50% of the transactions access 20% of the tuples
- High Skew: 90% of the transactions access 10% of the tuples
测试结果如下图所示：
从上图来看，在使用了NVM设备后，整体的性能提升还是较为明显的，无论是在高延迟还是低延迟状态下，改造后的引擎在NVM设备上发挥了更大的性能优势。