基于SCM与SSD的混合高效键值存储系统研究

詹 玲，张艺文

1.文华学院 信息学部 计算机系，武汉 430074

2.华中科技大学 武汉光电国家研究中心，武汉 430074

随着信息时代的高速发展，各个领域数据都呈现爆发式增长[1]，同时人们对存储服务的要求越来越高，许多应用（如微信、微博、推特等）都要求以微秒级的读写延迟完成同步响应。因此，存储系统在容量和性能上都受到了前所未有的挑战。越来越多的各种新型存储设备（如固态存储、瓦记录存储和非易失性内存等）以及新型数据库被提出来，以满足日益增长的存储系统需求。

存储设备方面，固态硬盘（SSD）逐渐成熟并在某些对存储性能有着更高要求的场景替代HDD。SSD的数据存储原理不同于HDD，其内部使用的是非移动的闪存芯片进行数据存储而不是HDD 所使用的转动磁盘，节省了磁盘寻道时间，因此在性能上优于HDD。与此同时，存储级内存（Storage Class Memory，SCM）作为一种新型的存储设备逐渐人们的视野。SCM也被称为非易失性内存（Non-Volatile Memory，NVM），从物理存储介质上，主要有相变存储器（PCM）[2]、阻变存储器（ReRAM）[3]，除此之外还有Intel所开发的3D XPoint等。SCM拥有字节可寻址、高读写性能以及相对于DRAM 更高的容量等优异的特性，但是其写性能相对于DRAM仍有约100倍的差异[4]。Intel基于3D XPoint的SCM存储设备Intel Optane DC 已于2019 年正式向市场发布，可供实际使用。然而，由于目前SCM的单位存储价格高昂，因此在短时间内，通过配置少量SCM 提升系统性能，并通过SSD 提升存储容量以构建混合异构存储系统的方式是一个经济可行的方案。

存储系统方面，键值（Key-Value）存储作为NoSQL的一种，不同于传统的SQL数据库使用固定的表格模式以及SQL语句进行数据存储。KV存储接口定义更加简单并且数据结构组织更加灵活，能够根据不同应用场景选择不同数据结构以适应相应的存储需求。相关应用主要有Google 开发的分布式KV 存储系统BigTable[5]、单机KV 存储引 擎LevelDB[6]、Facebook 的Cassandra[7]、基于Hadoop 分布式文件系统的HBase[8]、基于LevelDB优化开发的RocksDB[9]、Yahoo 的PNUTS[10]以及Basho的Riak[11]等。

基于日志结构合并树（LSM-Tree）[12]的KV 存储系统因为其相对良好的读写性能，被用于许多写敏感负载的应用场景。KV存储引擎诸如LevelDB和RocksDB采用了LSM-Tree 的数据结构作为KV 存储引擎的基本数据结构。LSM-tree 通过将随机写合并为顺序写的方式保证了出色的写性能，其多层结构如图1所示，主要分为内存中的有序结构MemTable 和Immutable MemTable以及磁盘上的日志以及分层的SSTable。一个键值对的写入操作过程如下：首先键值对会被顺序写入日志，保证写入内存的键值对不会因为系统掉电而丢失；然后插入内存中基于跳表实现的有序数据结构MemTable中；当MemTable 的键值数达到其容量上限时，转换为只读的Immutable MemTable，并创建另一个MemTable来接收新写入的键值对；最后将不可变MemTable 通过compact构建SSTable并写入磁盘。

图1 LSM-Tree结构Fig.1 Structure of LSM-Tree

LSM-Tree 设计的目的主要是为了解决HDD 随机访问性能较低的问题，将随机访问转换成了顺序访问。但是这样的批量写的方式下，为了保证分层结构的有序引入了compact 操作来保证分层的有序性。compact 操作会将Li层的1 个SSTable 与Li+1的10 个SSTable（默认为10）读入内存，然后排序合并再写回磁盘，因此造成大量的数据IO。SCM 与SSD 由于采用基于电路的存储介质，存储设备性能相比于HDD有了极大提升，顺序访问与随机访问性能差异也大大降低，LSM-Tree 的compact 操作会影响新型存储设备性能的发挥，LSMTree 结构不再适用于基于SCM 与SSD 的系统。因此，基于新型存储设备设计KV 存储系统需要针对存储设备的特性，优化存储系统的数据组织方式以及数据结构的选择。

针对SCM和SSD的特点，本文设计了基于SCM与SSD的混合式高效键值存储系统（SCM and SSD Hybrid Key-Value store，SSHKV）。SSHKV 基于SCM 与SSD异构混合存储架构进行构建。首先，SSHKV在SCM中构建SCMHash用于存储元数据，利用SCM的字节寻址以及低访问延迟特性实现元数据的快速访问。其次，为了降低SSD 垃圾回收带来的数据迁移，SSHKV 采用了逻辑空间放大策略，通过放大逻辑空间以及重映射逻辑块，降低垃圾回收频率。最后，SSHKV基于半异步半同步式IO 模型实现，充分利用了现有系统多核的优势。经过测试，对比传统基于LSM-Tree 的LevelDB 实现随机写性能20倍的提升。

1 相关研究

为了解决LSM-Tree的读写放大问题，有许多的研究方案通过设计新的数据组织方案有效减小了读写放大。

Lu等人[13]提出了WiscKey，通过将KV存储中的key和value分离，key以LSM-Tree的形式存储，而value则以log 的方式管理，有效减少了因为value 参与LSM-Tree的数据合并引起的写放大，提升了系统性能。然而由于采用log存储value，因此带来了额外的垃圾回收的开销。Chan 等人[14]基于WiscKey 的工作进而提出了HashKV，将KV数据按照Hash进行分组，不同组之间通过统计信息确定GC时机，避免了WiscKey中直接GC整个log带来的写放大。同时根据数据的冷热，将value log分成了hot和cold两个log，进一步减少了对冷数据的GC开销。Yao等人[15]提出的Light-Weight Compaction Tree从另一个方向优化了LSM-Tree的读写放大问题，在compaction的时候LWC 不再将下一层的数据读出，而是直接将上一层的数据追加到下一层的Table，并通过更新元数据避免多段数据带来的读开销，从而提升整体的写性能。

在结合存储设备特性优化KV 存储系统方面也有很多研究，一类是基于SSD的优化，另一类是基于SCM构建多存储设备混合KV 存储系统。Kang 等人[16]以及Yang 等人[17]提出一种新型SSD 映射策略以及基于此的RocksDB 优化策略，名为multi-stream SSD[16-17]，该方法的主要切入点是减少GC（Garbage Collection）带来的开销从而提升访问效率。通过预测文件的生命周期从而将生命周期相近的文件通过同一个数据流写入同一NAND闪存块中，这样闪存块中的数据被删除的时间相近，就能够直接将这一个闪存块标记为无效并直接擦除，避免了有效页的拷贝过程，从而减少了GC过程中拷贝数据带来的开销以及带宽占用。刘峪竹等人[18]提出SSD 友好的键值存储系统SSDKV，该系统跳过了复杂的中间层，将上层应用程序与底层存储程序相结合，使用分段地址空间来对键值对数据进行存储，充分利用存储设备的特性来提升总体性能。为了能够充分利用SSD 内部的并行性，出现了Open-Channel SSD[19]，该SSD 使用了特殊的系统，将其内部闪存通道暴露给应用程序，而上层应用即可利用SSD 的多个通道来提高其并行性，通过优化I/O 请求的调度策略提高数据访问效率。Wang 等人[20]针对此提出了基于Open-Channel SSD 的KV 存储。Kannan 等人[21]与Kaiyrakhmet 等人[22]分别提出了NoveLSM 和SLM-DB，均为构建SCM 与SSD的混合KV存储系统，两者都认为SCM与SSD混合存储在今后一段时间内是有必要存在的。NoveLSM通过构建NVM MemTable，实现DRAM 与NVM Mem-Table的交互使用，减少因为MemTable满了而带来的系统请求处理中断，但是当数据量增大之后，下层的compaction 仍会造成较大的系统停顿。SLM-DB 基于SCM构建单层的KV存储，将原来多层的LSM-Tree结构改为只有一层，同时在SCM中新增一个全局的B+树进行索引，减少系统读放大。

这些研究工作中，大部分[10-17]是针对传统块设备（HDD 和SSD）优化LSM-Tree 的数据组织，其优化策略并不能直接应用于SCM 设备上。NoveLSM[18]与SLB-DB[19]针对SCM于SSD混合架构优化LSM-Tree，但是由于LSM-Tree 本身的写放大问题，使得它们并不能充分发挥SCM 的性能。本文针对SCM 与SSD 混合的存储架构，考虑了SCM与SSD的性能与容量特性，设计了新的键值存储结构SSHKV，充分发挥不同存储设备的优势，实现性能与容量的兼顾。

2 系统设计

2.1 总体结构

SSHKV系统总体架构如图2所示。SSHKV通过将键值存储中元数据信息存储到SCM 中，将数据部分以日志方式存储到SSD 中，实现性能与容量的兼顾。SCM 设备具有传统存储设备的掉电非易失特性，并且拥有接近于DRAM的访问速度。同时key作为元数据，数量较少而且会被频繁访问。因此，将键值对的key以及相关元数据存储到SCM设备中。对于value数据，由于其数量较大，并且并不是所有数据都会被频繁访问，因此将value 数据存储到SSD 中，能够更好地降低能耗以及存储成本。

图2 SSHKV总体结构Fig.2 Overall structure of SSHKV

对于每个到达系统的键值请求，key 数据直接写入SCM，由于SCM 具有非易失的特性，所以key 数据不用担心丢失。由于SSD 需要以块为单位进行写入，所以value 先写入内存中的缓冲区，此时在SCM 中的key 中记录Value 状态为In-Memory，等到缓冲区的大小超过SSD 的块大小之后再一并写入SSD 中的log，同时修改SCM 中的value 状态，并记录value 在valuelog 中的偏移。

2.2 SCM元数据存储

为了能够更好地利用SCM 的非易失、字节可寻址以及高带宽的特性，SCM 中的元数据以哈希的形式进行组织。元数据包含key值、value偏移、value的大小以及value所在位置等基本信息。为此SSHKV提出了SCMHash结构。

如图3 所示，SCMHash 将SCM 空间分成大小相等的slot用于存储元数据，每个slot对应一个key以及其相关的元数据。为了解决哈希冲突，SSHKV将SCM空间均分为两段，前半段为正常哈希空间，后半段作为冲突空间用于容纳所有发生哈希冲突的key。冲突空间基于bitmap 进行空间管理，当发生冲突的时候，选择冲突空间中未被使用的一个slot将元数据写入。

图3 SCMHash原理示意图Fig.3 Schematic design of SCMHash

为了对冲突空间中的元数据进行寻址，SCMHash定义了冲突链，将与哈希空间中同一个slot中所有发生冲突的key链接起来。冲突链中前一个key结构存储了下一个冲突key的slot地址，所有的key形成一个类似链表一样的结构。同时，存储slot地址也避免了在SCM中传统指针因为系统重启导致虚拟空间地址映射发生变化而无法访问原始数据的情况。如图3 的B 所示为一个冲突链的例子，key a～key b 即为一个冲突链，通过key a 可以获取key b 的地址。写入key b 时发生哈希冲突，则从冲突空间选择一个未被使用的slot作为新的key的存储空间，并写入这个key以及对应的value的元数据。然后在这个key的冲突链上最后一个key记录当前key的slot地址。

在SCMHash中进行查找的时候首先计算哈希值定位正常哈希空间中的起始key，然后则按照冲突链的顺序，逐一进行查找并比较key 是否相等，直到找到对应的key或者查找失败。

2.3 SSD逻辑空间放大管理方法

SSHKV 中的value 数据采用日志方式存储到SSD。SSHKV 采用基于Zone 的方式管理SSD 的空间。SSD空间被分成多个大小相等的Zone，这些Zone 由多个连续的SSD Block 组成。当需要写入value 数据的时候，SSHKV 分配一个空闲Zone 来容纳新写入的数据。当没有空闲Zone 时，则触发垃圾回收，选择部分Zone，迁移其中的有效数据并回收Zone的空间。

SSHKV使用的SSD空间是属于SSD提供给用户的逻辑空间，逻辑空间地址通过FTL层映射到一块物理空间地址上。通常的情况下，SSD逻辑地址空间大小等于SSD物理空间除掉部分内部保留空间。

如图4 是传统日志结构空间管理的示意图。一个Zone 中包含无效数据以及有效数据，此时逻辑空间已经写满，对于新的数据i 就无法写入，此时需要触发垃圾回收，将有效数据从old Zone 迁移到新分配的new Zone，然后在new Zone 写入数据i，最后释放old Zone的空间。

图4 传统日志结构空间管理Fig.4 Traditional log-structured space management

这种垃圾回收需要迁移有效数据，带来一定的写放大，而触发垃圾回收的主要原因是没有空闲逻辑空间。因此，本文设计了一种逻辑地址空间放大的管理策略，逻辑空间放大的策略是在保持物理地址空间不变的情况下，而将逻辑地址空间放大为物理空间的N倍的策略。该策略通过逻辑空间地址重映射，降低因为逻辑空间不够导致的应用层GC的频率，达到减少SSD垃圾回收开销的目的。

逻辑空间放大策略中，逻辑地址空间的Block 被标记为无效后，系统通过TRIM指令标记物理空间对应的Block为无效数据，SSD则会在内部GC的时候直接回收这些Block。逻辑空间进行写入的时候，由于逻辑空间大于物理空间，超出实际大小的逻辑空间直接映射到被回收的物理空间上，写入扩展Block的数据直接被映射到被回收的物理Block 上。由于逻辑空间的大小是原来的N倍，因此垃圾回收的次数降低了N倍，以此减少了因为垃圾回收而造成的数据迁移以及逻辑空间整理开销。

基于逻辑空间放大策略的SSD 空间布局如图5 所示，其中a、d、f 和g 数据块为无效数据，新插入数据为i。根据前面的分析，对于传统的日志结构存储，逻辑空间大小等于物理空间，此时逻辑空间消耗完，则数据i的插入会触发垃圾回收。在逻辑空间放大策略中，无效数据块a 可以直接擦除回收，然后通过重映射，可以直接将放大的逻辑空间映射到被回收的a 数据块占用的空间。此时可以直接写入数据i，避免了垃圾回收的发生。

图5 逻辑空间放大策略Fig.5 Logical space amplification strategy

逻辑空间放大倍数N的大小可以调节，当N为1的时候退化为没有逻辑空间放大的情况。另外，使用逻辑地址空间放大方法，实际存储的数据必须不能够超过物理空间的大小。

2.4 垃圾回收算法

SSHKV逻辑空间被划分为以块（Block）为基本单位的空间，多个Block组成一个区（Zone），逻辑空间以Block为单位进行写入，同时以Zone为单位进行垃圾回收。

垃圾回收的时候需要考虑有效数据迁移所带来的开销，为了尽可能降低这个开销减小对系统性能的影响，则需要尽可能减少对有效数据的迁移。垃圾回收过程如图6所示，当一个Zone被写满之后可以则加入待回收队列，在总的空间使用超过80%（可调节）之后触发垃圾回收进程回收无效空间。进行空间整理的时候首先选择无效数据最多的一个Zone 作为待回收Zone，然后分配一个新的Zone，依次读取Zone 内的有效数据到内存。当内存中的有效数据达到一个Block大小的时候，将内存中的数据写到新的Zone 内，同时修改对应的数据在SCM中的key记录的value地址。直到所有数据都回收完成之后回收整个待回收Zone的空间。

图6 垃圾回收过程Fig.6 Process of garbage collection

3 系统实现

如图7 所示，SSHKV 基于半异步半同步式IO 模型进行实现。基于该模型的SSHKV 总体分为三层：异步任务层、请求队列以及同步任务层。异步任务层以异步的方式从外部接收键值请求，然后根据哈希将键值散列到请求队列中等待同步层处理。同步任务层被划分成多个子系统，每个子系统以同步的方式处理每个键值请求。每个子系统维护一个请求队列。当请求队列中有待处理的键值请求的时候，子系统从请求队列中读出键值请求并进行处理。每个子系统同时管理一部分的SCM 元数据表以及SSD 的逻辑空间中的Zone，进行独立的空间分配与回收。每个子系统有一个后台事务线程和一个逻辑空间管理模块。后台事务线程在SSD 逻辑空间使用超过设定的阈值之后唤醒，开始以Zone 为单位进行垃圾回收，逻辑空间管理模块负责管理Block的分配与Zone的回收。

图7 基于半异步/半同步I/O实现的模型实现的SSHKVFig.7 Implementation of SSHKV based on half-sync/half-async I/O model

在系统调用上，SSHKV支持基本的键值操作，包括Put、Get、Scan 以及Delete。所有的操作在调用SSHKV的对应接口之后，会被包装成一个请求对象并插入到队列层中进行处理。后台事务线程探测到请求队列中有待处理请求的时候被唤醒，然后开始处理请求。对于更新请求（Put 或者Delete），则首先从哈希表中分配一个合适的位置，然后插入key 以及对应的元数据，然后将value 写入内存缓冲区中等待下刷，或者将对应的value数据标记为无效。当内存缓冲区中数据量超过阈值之后，在SSD 中分配一块区域，然后将内存缓冲区中的数据刷写到SSD 上。对于读请求（Read 或者Scan），首先从SCMHash中获取带查找key的元数据，然后再到内存缓冲区或者SSD上读取对应的value。当SSD空间使用量到达阈值之后，系统触发后台事物线程进行垃圾回收，按照2.3节的方式进行释放无效空间。

4 性能测试与结果分析

4.1 测试环境

实验基本测试配置如表1所示，测试使用Intel Xeon E5-2660 处理器，为了减少操作系统缓存对测试结果的影响，将内存大小限制为8 GB。存储设备方面，通过修改系统启动参数分配2 GB 内存用作模拟SCM 设备。SCM 设备通过EXT4-DAX 提供的mmap 内存映射的方式进行访问。SSD 设备以块设备文件的方式进行直接访问并管理其中的数据，避免了文件系统层的开销。

表1 测试环境Table 1 Testing environment

测试基于microbench，microbench测试移植于LevelDB的dbbench，保证对比测试时使用的测试工具一致。进行测试前，设置测试基本参数，key 的大小为16 Byte，value为4 KB，测试的时候首先随机/顺序写入2 500 000条KV项，总数据量约10 GB，默认底层同步执行线程数为4，逻辑空间放大5倍，即逻辑空间大小为60 GB，实际可用12 GB。具体配置参数如表2。

表2 测试参数配置Table 2 Testing parameter configuration

4.2 测试结果分析

4.2.1 基础性能测试

从图8（a）可以看到，在写测试上，SSHKV的随机写IOPS 接近LevelDB 随机写的20 倍。同时在顺序写IOPS 上也是LevelDB 的2 倍左右，并且SSHKV 的随机写IOPS与顺序写性能基本相等。对于随机写，SSHKV采用平面结构，数据以半同步半异步IO 的方式写入SSD，不存在后台的重新排序过程，同时SSHKV采用逻辑空间放大的管理策略，尽可能减少了空间垃圾回收带来的开销，因此在随机写上SSHKV 具有较大的优势。而LevelDB 采用的日志结构归并树来分层组织硬盘中的数据，数据通过compaction 操作逐层向下移动，由于compaction操作会进行大量数据读写造成读写放大，因此LevelDB 的随机写性能会受到较大的影响。顺序写测试中，LevelDB 在compaction 的时候因为SSTable 互相没有key range 重叠，因此只需要修改内存元数据完成对SSTable 的level 的修改，性能比随机写高。对于SSHKV，由于其采用半异步半同步IO的请求处理方式，同时使用多线程，因此能更加充分地利用SSD 的带宽，以此达到相对于LevelDB更好的性能。

图8 SSHKV与LevelDB基本性能对比Fig.8 Basic performance comparison of SSHKV and LevelDB

对于读测试，如图8（b）所示，SSHKV 随机读IOPS约为LevelDB 随机读的13 倍，但是顺序读IOPS 差于LevelDB，约为LevelDB的1/2。对于LevelDB，每次读取的时候需要逐层查找每个key，需要出发至少两次block读（读index block 以及filter block），而由于SSHKV 采用平面结构，每次读直接从内存SCM中直接查找key所在数据块的位置，因此固定只会读一个数据块大小，避免了LSM-Tree 结构的读放大，获得了更好的性能。对于顺序读，由于LevelDB的SSTable中数据有序存储，每次读取一个key之后后续的key已经被同时读到内存进行缓存，而SSHKV每一次读都是一次随机读，所以顺序读LevelDB拥有更好的性能。

4.2.2 Value大小敏感测试

对于不同value大小，选择64 Byte到64 KB的value，保持总数据量不变，测试不同value大小下的性能变化。

从图9（a）可以看到，对于不同value的写性能，SSHKV的写入速度随value大小的增加而增加，并在4 KB左右达到最大值，同时随机写于顺序写IOPS 始终维持接近的水平，主要是因为SSHKV 采用LOG 方式写数据，随机写也变成顺序写。LevelDB对于不同value大小的写IOPS基本保持均衡。

图9 不同Value的基本性能对比Fig.9 Basic performance comparison of different value sizes

对于读性能，如图9（b）所示，SSHKV与LevelDB的读IOPS 都随着value 大小的增加而降低，同时保持了LevelDB顺序读优于SSHKV的顺序读与随机读，LevelDB随机读IOPS 最低的规律。对于SSHKV，小于4 KB 的读IOPS差距不大，而超过4 KB之后读IOPS显著降低，主要是因为SSD 的访问粒度为page（一般为4 KB），当读取的value 小于page 大小的时候仍然需要读一个page，当value大于page的时候就需要读取多个page，因此value小于4 KB时，固定读一个page，性能接近，value超过4 KB 时IOPS 随着读数据块增加而降低。对于LevelDB 的读性能，value 越大意味着一次block 读能够读出来的key 越少，缓存效率更低，因此读性能随着value的增加而降低。

5 结束语

随着存储技术的不断发展，同时拥有memory 特性以及storage 特性的SCM 技术已经逐渐成熟并走向市场，传统的针对磁盘设计的LSM-Tree 结构不再适应于新的存储设备的特性，重新设计键值存储的结构已经迫在眉睫。

本文基于SCM与SSD构建了基于混合架构的键值存储系统SSHKV，通过使用SCM存储key以及value的元数据达到快速查找value 位置的目的，同时通过半异步半同步式I/O更好地利用SSD的高并行性的特点，以达到最大化的I/O 性能。同时通过逻辑空间放大策略，减少了SSD中有效数据的迁移，进一步加快了数据写入SSD，提升了SSHKV的性能。