一个基于日志结构的非易失性内存键值存储系统

游理通 王振杰 黄林鹏

(上海交通大学计算机科学与工程系 上海 200240) (litong.you@sjtu.edu.cn)

近年来，随着大规模数据分析处理、数据密集型计算等技术的兴起和发展，内存计算也成为了更加重要的基础技术.这些技术都依赖于快速大容量的存储.除常见的磁盘、SSD和DRAM外，非易失存储器(non-volatile memory，NVM)技术正在快速发展，例如相变存储器(phase-change memory，PCM)[1]、自旋矩存储器(spin-torque transfer ram，STT-RAM)[2]和阻变存储器(resistive ram，ReRAM)[3]等.这类存储介质所共有的特点包括可字节寻址能力、接近DRAM的读写延迟以及数据的可持久性能力.DRAM和NVM可以抽象为统一的主存储空间，这种新的混合内存架构为建造更高速有效的大容量持久性存储系统(如文件系统、数据库等)带来了新的机遇.

在软件技术方面，以LevelDB[4]，Dynamo[5]为代表的键值存储系统已经是业界使用的主流系统，这类存储系统在非结构化数据存储方面有很好的性能优势.现有较为成熟的键值存储系统都是针对磁盘或SSD进行优化设计实现的，它们依靠文件系统来存储数据，并进一步支持数据持久化.此外，针对非易失内存已有一些文件系统(如HMFS[6-7]，PMFS[8]，NOVA[9]，Octopus[10])，但是依靠文件系统来存储数据，需要执行文件系统的代码，并且操作系统也要进行用户态和内核态之间的切换，这些都会带来一定的开销.由于非易失性内存的延时接近于DRAM，这种用户态/内核态切换开销对存储系统的性能的影响是不能忽略的.在基于DRAM内存存储系统方面，键值存储也是研究热点，如在实际中被广泛应用的Memcached[11]、性能非常好的MICA[12]，但针对DRAM设计的系统无法顾及到非易失性内存的特性，如NVM的读写延时的差异、DRAM与NVM访问速度差异等.因此，综合DRAM和NVM各自特点开发新型的系统需要新的设计思路和实践.

在使用NVM设计存储系统时，传统的基于文件系统和基于磁盘、DRAM或SSD的键值存储系统存在4个问题：

1) DRAM和NVM混合架构下内存分配困难.针对DRAM设计的键值存储系统未考虑到非易失性内存的特性，如非易失性内存的读写延时的差异、DRAM与非易失性内存访问速度差异等因素.

2) 现有键值存储系统数据一致性保障机制性能开销较大，且未充分利用NVM的非易失特性.传统架构中，多数系统只基于DRAM设计并维护一个数据日志，所有数据都是以写日志的方式进行组织，这样导致的一致性维护开销较大，NVM的特性很难被充分利用.

3) 垃圾回收复杂.NVM具有读写不对称的特性，因此NVM设备使用一段时间后需要垃圾回收.在日志结构的存储系统中，数据的更新采用写时复制的方式进行，旧数据保留在原始位置，形成空间碎片，不能被有效地重新利用.使用NVM设备进行垃圾回收时，需要整合内存碎片，整个过程复杂耗时.

4) NVM设备的并发性能难以得到充分的利用.传统键值存储系统针对DRAM设计并发机制，这种情况下，频繁的读写操作会限制NVM的性能.

基于以上4点考虑，本文提出一个基于日志结构和非易失性内存构建键值存储系统的方法，并以PCM为代表的存储类内存(storage class memory，SCM)为存储介质实现一个键值存储系统TinyKV，其充分考虑了键值数据工作负载等特性以及非易失性内存的特点，采用日志结构技术最大化非易失性内存的吞吐性能，并提供可扩展能力和数据一致性保证.

本文的主要贡献总结有3个方面：

1) 存储系统功能分区与索引结构的设计.通过对非易失性内存的抽象，只需要用户重新定义并实现与设备有关的数据结构，就可使用存储系统，从而实现存储系统与设备模型的解耦.通过针对键值数据特性的分析，设计与实现Hash表的结构，使用地址连续的数据结构高效充分利用缓存，使用Hash表对所有的数据对象进行索引.对整个设备空间进行功能分区，确定并记录各区域的范围功能.

2) 非易失性内存分配器的实现.结合非易失性内存的功能分区，设计多层次的非易失性内存分配器，通过不同层次的功能分离，在不同层次使用不同的数据结构，实现一个能够充分结合非易失性内存和DRAM优势的内存分配器.

3) 存储系统垃圾回收算法的设计与实现.存储系统垃圾回收算法以块为单位对日志中的剩余空间进行回收.通过存储功能区的块状态能够生成垃圾回收算法所需数据结构，把这个数据结构存放到DRAM中，以提高系统运行效率并减少对NVM的占用.

1 相关工作

键值存储系统是传统的关系型数据库的简化形式，通过去除不必要的特性，键值存储系统可提升自身性能，降低数据间的耦合度.

1.1 传统键值存储系统

LevelDB是Google开发的一套针对块设备进行优化的存储系统，其核心使用了日志结构合并树(log-structured merge tree，LSM-Tree)[13]的数据结构.LevelDB的优点是写操作性能很强，缺点是读操作性能表现不佳且容易造成严重的写放大.MICA是一个具有很强扩展能力的内存键值存储系统，通过Hash索引结构把所有的键进行分区，每个处理器核心负责一个分区的读写工作.MICA的内存分配器使用了非严格的循环日志结构的分配方式，并对垃圾回收工作进行了新的解释.在MICA提供的存储模式中，它使用类似于分离适配(segregated fit)的方式管理内存，具有较高的内存空间使用率.当内存碎片较多时，MICA可能满足不了大内存的需求.PebblesDB[14]介绍了一种基于碎片化的日志结构合并树(fragmented log-structured merge trees，FLSM)的键值存储系统，其通过设计新型数据结构FLSM，降低了传统基于LSM-Tree的键值存储系统写放大严重的问题，有效地提高了系统整体的读写性能.

1.2 基于非易失性内存的键值存储系统

Echo[15]是一个针对非易失性内存设计的持久性键值存储系统.它利用DRAM和非易失性内存的两级存储结构，把数据缓存到每个线程的DRAM中.每个工作线程可以把数据提交到主线程的队列里，由主线程负责把DRAM中的数据存储到非易失性内存的存储系统中，当读写比较频繁时，可能会有多个主线程同时运行.它通过快照隔离的方式保证数据一致性，并假设计算机硬件可以提供数据持久化的帮助.UDORN[16]是一个基于NVM的持久化内存键值存储数据库的新型设计框架，在UDORN中，NVM上的持久数据库被用来完成常规内存数据库和持久化存储图像的功能.在运行时期间，持久性数据库被映射到进程地址空间，这些操作通过相应的地址空间直接在NVM上执行.与传统基于NVM Library的Redis系统相比，应用UDORN的Redis获得了6倍的性能提升.NVMKV[17]是一个闪存感知键值存储器，它依靠闪存转换层(flash translation layer, FTL)[18]功能在关键值存储处实现最少的数据管理，还有一些针对非易失性存储器优化的键值系统.NVMcached[19]是非易失性存储器的键值缓存，它尝试通过使用校验和来剔除损坏的数据以避免大多数缓存溢出.它充当后备缓存，并且任何丢失的键值对象都需要被重新插入其中.HiKV[20]在NVM与DRAM的混合内存架构中构建混合索引，利用Hash索引和B+树索引的特性，提供更有效的键值操作，以保持其固有的快速索引搜索能力，避免长时间NVM写入以保持2个索引的一致性.此外，HiKV将差异并发方案应用于混合索引，并采用有序写入一致性来确保崩溃一致性.LibreKV[21]使用静态Hash表和动态Hash表来实现系统性能和内存利用率之间的平衡.其采用基于校验和的一致性机制来保证数据一致性和永久存储在NVM上.与传统的键值存储系统相比，LibreKV独立工作，不依赖于底层文件系统，简化了读写I/O操作.NVHT[22-23]是一个基于Hash表结构设计的键值存储系统，它针对NVM进行了多项优化，包括非易失指针结构的设计、NVM数据一致性的undo日志解决方案以及结合磨损均衡(wear-leveling)算法的内存分配器设计.

1.3 基于非易失性内存的文件系统

目前许多文件系统的研究工作都致力于在NVM上提供不同的抽象，Mnemosyne[24]，NV-Heaps[25]和NVML[26]提供了通用编程接口和持久性内存和事务机制以实现故障恢复；PMFS，NOVA和Octopus是针对非易失性内存优化的文件系统，它们允许通过POSIX文件接口对传统的基于文件的内存进行访问.PMFS使用具有不同CPU指令的多粒度原子更新和用于元数据一致性的细粒度日志记录以及用于数据一致性的写入时复制.SIMFS[27]是一个基于NVM的可持续内存文件系统，其充分利用了文件访问路径上的内存映射硬件.SIMFS利用一个新型设计框架：文件虚拟地址空间(file virtual address space)，进行文件读写操作处理.在这个框架内，当文件被打开时，其文件虚拟地址空间会被嵌入所对应的进程虚拟地址空间，之后的文件访问由内存映射硬件处理.

2 TinyKV系统架构

本文提出了一个基于非易失性内存的键值存储系统TinyKV.其充分考虑了键值系统对象数据比较小并且大小分布比较集中等特性，对存储系统进行优化设计，通过日志结构的内存管理方式对非易失性内存的磨损均衡也起到了一定的帮助作用.

TinyKV的整体架构如图1所示.为了支持高并发的数据服务, TinyKV允许多个线程同时访问键值对象.为减少线程间的资源干扰，TinyKV为每个工作线程设置一个单独的分配器及数据日志.这些分配器被放在DRAM上以支持快速分配.所有线程共享一个全局Hash表来索引键值对象.Hash表使用动态分配的数组来解决Hash冲突.使用数组而不是列表可以通过CPU的硬件预取来加速针对键值对象的访问.TinyKV通过全局静态Hash表来索引数据，并提供插入、读取和删除3个应用接口来管理数据.

Fig.2 TinyKV memory layout图2 TinyKV非易失性内存功能分区

Fig.1 Architecture of TinyKV图1 TinyKV架构图

在内存分配器设计中，TinyKV中的每个线程都有自己的内存分配器，这可以减少同步原语引起的开销.TinyKV使用多级内存分配模型来有效地管理内存，并使用原子写操作保证每一个数据元素的写操作是一次独立的事务，从而保证操作的原子性[8,28]，整个存储空间首先采取分块的方式进行管理，然后把分配的块按功能进行划分.

TinyKV日志和Hash表都存储在NVM中.日志是用来保障系统的数据一致性.它首先将键值对象添加到日志记录中;然后才将它们插入到Hash表中，以完成真正的持久化过程.TinyKV可以在故障恢复时扫描日志元数据信息来了解日志空间的使用情况.

此外，TinyKV在NVM中存储系统全局静态Hash表和动态链.传统的动态Hash表的大小根据记录的数量适度增长和收缩，当Hash表需要扩容时，这个过程会导致一定的时间与空间开销.根据对Facebook负载数据特点的分析[29]，可以得知键值数据的大小分布比较集中并且比较小，例如存储SYS(系统数据)的键(key)的大小有90%小于40 B，值(value)的大小有80%在500 B左右.TinyKV根据设备空间的大小，估算预测出整个设备能够容纳多少键值对象.根据对象数目计算Hash表的初始大小，通过大Hash表减小了载荷因子，使Hash表产生冲突的可能性减少，减少Hash表扩容的次数，以规划合适大小的Hash表空间给数据对象.凭借这一手段，TinyKV可以使用静态Hash表作为存储数据的索引.为了减少静态分配的Hash表的大小，系统设定Hash表存储区的基本组成单位是大小为64 b的字.每个字包含一个指向键值对象或Hash表链的指针.TinyKV所维护的全局Hash表，在没有Hash冲突发生时直接访问键值对象，而当冲突发生时，它则将动态数组分配为数组链.

3 TinyKV设计与实现

本节主要介绍TinyKV的设计考虑和具体的实现技术.首先，我们介绍TinyKV的存储区功能布局；接下来介绍一种支持并发并且缓存友好的Hash表,是TinyKV设计的重点；然后介绍内存分配器的详细设计与TinyKV多线程中的应用；最后，给出TinyKV的垃圾回收算法.

3.1 存储区功能布局

图2是TinyKV对非易失性内存的功能分区.类似于操作系统，所有的内存空间以块为基本管理单位，然后把这些块根据不同功能进行划分.每个块的大小是2 MB，每个块只允许存储一种类型的信息，如Hash表的数组链或键值对象.存储数据的块使用顺序写的方式，存储Hash表的块使用随机写的方式.

1) 超级块区(super block)记录了TinyKV的参数信息和对功能区的划分，如存储空间的大小、块的大小、块的数量、各个分区的起始块编号和块数目.这些内容在第1次创建时确定并且不能被修改，它只会在TinyKV启动时被读取.

2) 系统状态区(check point)记录了TinyKV的运行状态的数据结构，如上次启动时间、上次运行时的线程个数、每个线程日志所在的块编号、Hash表大小、空闲块数等.每次系统启动都会产生一个新的状态，这些状态保留在一个循环数组中.在系统启动时，TinyKV会读取最新的状态信息，了解Hash表是否经过了扩容，扫描每个线程日志以保证数据的一致性，最后产生一条新的状态信息，新的状态信息可能会覆盖最旧的状态信息.

3) 块状态区(block information table)描述了非易失性内存的每一个块的信息.块状态区中的元素包含与其对应块的信息，例如键值对象或数组链的数量、是否为空闲块以及块修改的时间.系统将设置一个链表把所有的空闲块链接起来，如果当前块为空闲状态，那么它将被链接至链表中.为了减少块状态区对内存的占有率，一些存储区域将会被复用，并将块被访问时的状态信息只存留在DRAM中.每个块状态大小为8 B，每个块的大小为2 MB，其对存储内存的占有率为8/221=0.000 4%.

4) Hash表区(Hash table)是TinyKV的索引结构，每个桶包含指向键值对象的指针、一个标志位记录是否有线程在修改这个桶以及桶里对象的个数等信息.当桶中包含多个对象时，它的指针是一个数组，这个数组包含了所有属于这个桶的键值对象的地址.在TinyKV中的存储地址都是一个48 b的无符号整数，它是对象所在位置相对于内存起始地址的偏移量，运行时地址可以通过存储地址加上内存起始地址的偏移量得到，Hash表的大小是2N，这样可以根据位运算来计算键值对象将要插入的位置.

5) 保留内存区(reserved memory)紧跟在Hash表后面，通过它可以很方便地对Hash表扩容.当数据存储区内存不足时，它还可以用来存储数据对象.对Hash表扩容是从保留内存区的块从前向后分配空间，当用来存储数据对象时，保留内存区的块从后向前开始分配.

6)数据存储区(data area)是为了存储键值对象，或者包含键值对象地址的数组.数据存储区的每个块只存储一种类型的数据.当存储区域的内存不足时，可以向保留内存区申请空间.

3.2 静态并发、缓存友好的Hash表

图3展示了TinyKV的Hash表结构.在图的最左边是Hash表区域的结构，可以将其看成一个数组.最右边是TinyKV存储的键值对象.中间是为了解决Hash冲突而动态分配的数组(称为数组链)，这些数组里存储的是键值对象的地址.TinyKV通过计算出key的Hash值找到对应的桶，然后根据桶里的内容确定键值对象或者数组链的地址.如果桶里只有一个键值对象，那么它包含的是键值对象的地址；如果桶里有多个对象，为了解决冲突，它包含的地址是数组链的地址，数组链则包含相应对象数据的地址.

Fig.3 TinyKV Hash table structure图3 TinyKV Hash表结构图

为了减少Hash表区域的大小，TinyKV对桶的大小做了限制，其定义如图4所示.Hash表中每个存储桶是大小为64 b的字.其中，has_writer表示是否有线程在修改这个桶.TinyKV允许多个线程进行读操作的同时，最多有一个线程可以修改同一个桶，它由原子操作设置或清除.在并发访问key-value的模式下，读事务的顺序具有一定的随机性，如果一个线程A修改key1的同时，另一个线程B进行读key1，它保证线程B读到的数据是新数据或是修改前数据，但如果线程A在修改key1之后继续读取key1，其读取的数据是新数据.每个写线程在访问任一个桶的同时，它必须检查has_writer是否为0.如果为0，它把has_writer置1，然后再访问该桶；如果为1，它就等待.为了保证只有一个线程可以修改同一个桶，必须对has_writer进行保护.TinyKV使用CAS原语保证互斥，它相当于一个自旋锁的作用，读线程是不需要读写这个锁的.TinyKV还使用了事务机制，保证写操作是原子操作，从而保证读的数据只能是修改前或修改后的数据，从而可以保证读操作的一致性.

Fig.4 Definition of TinyKV Hash table图4 TinyKV Hash表的定义

第3个字段reserved表示位于存储桶中的键值对象的数量.version是对桶分裂次数的统计.当Hash表进行扩容时，会有一个变量记录它扩容的次数.每次对Hash表进行扩容，在Hash表里的桶就会产生一次分裂.当它到达最大值或者保留内存区剩余资源不足时，扩容操作会失败.nr_objects表示桶里包含的数据对象个数，每个桶最多容纳255个元素.nvm_addr是非易失内存内的一个对象的地址.当nr_objects=1时，它指向一个键值对象；当nr_objects>1时，它指向一个数组链，数组链包含键值对象的地址.

Fig.5 Layout of a chain element图5 数组链数据结构图

数组链是一个动态分配的数组，其大小与起始地址均为cache_line的整数倍，它的内存是从数据存储区分配的.数组中的每个元素指向一个键值对象.元素的数据格式如图5所示.每个元素大小是64 b，其中低48 b的nvm_addr存储键值对象的地址，高16 b的tag是对key进行数字描述，它可以用key的Hash值高16 b来表示.在访问键值进行匹配时，需要对key的内容进行逐一匹配.当TinyKV进行查找时，它会先匹配tag，然后再根据nvm_addr访问键值对象.若2个键值对象具有相同的tag，再继续对其nvm_addr进行对比，直至找到所需对象数据.2个不同的key具有相同tag的概率是1216=0.001 5%.故首先比较Hash值高16 b的tag，将会极大地减少了读取匹配字符串的次数.

为了遍历一个链表，CPU要先把数据从内存中加载到高速缓存中，因为链表是结点不连续的存储结构，CPU访问内存的次数是不确定的，使用地址连续的数组，可以将CPU访问内存的次数降到最少.若硬件预取生效，会进一步降低CPU访问内存的次数.TinyKV没有明确对桶中的元素数量进行限制，当桶中元素数超出原始设定大小，TinyKV从数据存储区分配一个新的数组，其大小为原始数组的大小与一个cache_line之和，分配完毕后，将原始数组的数据复制到新的数组中，并把相应的桶的nvm_addr设置为新数组的地址，虽然这可能会造成某些桶元素较多，但这个问题可以通过现有的比较成熟的Rehash机制来解决[30].

3.3 内存分配器

TinyKV对NVM进行分块管理，其优势是支持高并发分配.如果对整块NVM进行统一管理，则NVM块元数据信息只有一份，则每一次NVM分配都将会锁定整块NVM空间的元数据，而不能同时分配多块NVM区域给多个用户，因此，键值对象不可跨块存储.系统采用分块管理后，每块NVM空间有自己独立的元数据信息，从而可以并发地进行修改.基于对Facebook负载数据特点的分析，可以得知，一般的键值对象所占用空间较小，内存分配器只需分配一个块，即可满足键值对象的存储空间要求.由于分配内存过大或过小都会造成较大的瓶颈，分块过大，每个块内的数据元素较多，难以支持高并发的访问；分块过小，块元数据所占的空间开销较大.因此，TinyKV将分配的块的大小限制在2 MB以内(块的大小).当块空间不足时，需要重新分配新块，旧块剩余空间可以继续用于分配给之后存储的较小数据元素，这样虽然会造成一定程度上的内存碎片，但由于键值对象本身所占用空间较小，所以内存分配过程中空间浪费情况不是很严重.

TinyKV中的每个线程都有自己的内存分配器，这可以减少由同步原语引起的开销.TinyKV使用多级内存分配模型来有效地管理内存.如图6所示，TinyKV的内存分配器采用3层结构进行描述，一方面能够独立定义各层的功能，另一方面各个层次的结构可以根据需要放在DRAM或非易失性内存中.第1层为块管理层，它保留一个空的内存块池，分配和释放块；第2层是日志分配层，每个线程都有各自的日志分配器.分配器在分配新日志时需要底层的块，如果块变空，它会将块释放到底层；第3层是对象分配层，该层是为链或键值对象分配内存的对象分配器，这些对象分配器无法重复使用日志尾部之前的空间，只能利用来自日志尾部的内存.因此，在删除键值对象时，日志中存在许多不可复用的碎片.为了复用这些内存碎片，分配器需要执行垃圾收集.垃圾收集机制将被废弃的日志中的一些尚在使用的键值对象移动到新的日志中，并将废弃日志块释放到块管理层.

Fig.6 NVM memory allocators图6 NVM内存分配器

TinyKV内存分配器的3层结构详细描述如下：

1) 块管理层.它负责整个非易失性内存的块区域内存分配管理.它的主要数据结构是由块状态区的数组组成，所以对它的修改要保存到非易失性内存中.所有线程共享一个块管理层，它负责记录块的类型、块内有效数据的大小、自由链表的维护等.它提供的功能有：分配块、释放块、修改块状态.由于块管理层的数据结构可以由所有线程同时修改，所以需要一种同步机制保证数据的一致性，TinyKV使用CAS操作来替代互斥锁中以提高并发的性能.

2) 日志管理层.一个日志最大的大小是一个块的大小.每个线程都有一个独立的日志分配器，日志分配器所维护的数据只能被所有者线程进行修改，所以不需要互斥锁进行数据同步.由于数据存储区存储键值对象和数组链对象2种数据，所以日志也有2种类型，一种是键值数据日志，另一种是数组链对象日志.在系统状态区有记录各个线程正在使用的日志的块编号的信息.

3) 对象管理层.它在日志尾部为键值对象或者数组链分配内存空间.这些对象分配器，无法重复使用日志尾部之前的空间，只能利用来自日志尾部的内存.因此，在删除键值对象时，日志中存在许多不可复用的内存碎片.为了重用这些内存碎片，分配器需要执行垃圾回收.垃圾回收机制将被废弃的日志中的一些尚在使用的键值对象移动到新的日志中，并将废弃日志块释放到块管理层.

对于每个块，块信息表(block information table，BIT)中都有一个记录块使用情况的元素.对于写操作密集型工作负载，块使用情况经常发生变化.为了减少对NVM的写操作次数，日志分配器将块区域信息复制到DRAM，因此块使用的更新情况保存在DRAM中.当块区域存储达到上限时，日志分配器将块信息转存到NVM，并使用clwb或clflushopt指令将相关日志数据持久保存至NVM，并要求内存池中新的块区域启动新日志.分配内存时，TinyKV使用Lock-Free的更新操作.由于每个线程日志，没有多个线程将键值对象附加到同一个日志中；但是，当2个工作线程想要删除同一个日志中的键值对象时，块使用信息会被这2个线程同时修改.所以块信息数据的更新操作必须是原子的，以此保证一致性.

3.4 多线程应用

TinyKV可以通过多线程技术对系统处理用户请求的能力进行扩展.在多线程编程中一个最常见的问题是数据同步，比较常用的数据同步技术有互斥锁、条件变量以及读写锁等.一般来说，当发生数据竞争时，锁的使用会带来较大的系统开销.例如futex会在可能发生数据竞争时，使应用程序发生用户态和内核态的转换.由于TinyKV的数据更新使用的日志结构，所以数据竞争的情况是不会发生的.但由于Hash表的数据是原地更新，因此要对Hash表的结构进行数据同步操作，对Hash表的每个桶进行锁保护.

TinyKV实现了一种允许多个读者和一个写者同时对一个桶的数据进行访问的操作.它对读者不加约束，而写者在修改桶里的数据时，需要申请写锁.由于TinyKV的数组链存储的是指向键值对象的地址，每个地址是48 b的，而CPU对数据对齐的64 b字的更新是原子的.当一个写者与多个读者同时对一个key进行访问时，读者看到的要么是写者更新后的数据，要么是写者更新前的数据.

由于TinyKV的日志结构，若未立即删除旧的数据，不会出现悬垂指针.与锁相关的信息可以放在DRAM中，也可以放在非易失性内存中.如果将它们放到DRAM中，可以提高运行效率，但是当Hash表很大时，将占用大量的DRAM.如果将它们放入到非易失内存中，加锁信息可能会持久存储到NVM中，下次系统启动时，需要检测并释放所有存储的加锁信息，因为存储加锁信息没有意义.

3.5 垃圾回收算法

在日志结构的存储系统中，回收被删除对象空间的有效方法是垃圾回收算法，垃圾回收算法的时机和策略对性能的影响同样重要.TinyKV使用垃圾收集线程来回收键值对象或链式数组被删除时累积在日志中的空闲内存.TinyKV启动后，线程扫描BIT以了解块的使用情况，然后使用与LFS[31]类似的成本收益方法来选择废弃的日志.根据日志中的可用空间量和日志的修改时间选择需要废弃的日志.对于每个所选日志，垃圾收集线程都会扫描存储在日志中的键值对象，将活动对象复制到新日志并将其重新插入到TinyKV中，然后它将被废弃的日志内存空间释放到内存池中，使得其所占用的内存可用于新日志.

TinyKV的垃圾回收算法，包括存储系统内垃圾的产生及特点、影响垃圾回收性能的因素、垃圾回收的时机以及垃圾回收算法.在TinyKV中，当数据更新时，新数据被追加至日志的尾部，而旧数据的引用在Hash表中被替代，使得旧数据成为失效数据，因此产生了垃圾数据.为了减少垃圾回收的代价，有效数据的占比越小越好.随着时间的推移，旧日志中的数据被修改的可能性越大，从而有效的数据量越来越少.TinyKV触发垃圾回收时机有2个：1)当日志内的有效数据为零时；2)当TinyKV中剩余块不足10%时.当日志内有效数据为零时，块在代价很小的情况下立即被回收，回收的块被插入到剩余块的链表尾部.在第2种情况下，TinyKV扫描整个块状态表，根据块的有效数据量和块上次被修改时间计算花费收益比[30]，根据收益比的数值建立一个最小堆.针对那些日志内有效数据为零的块，TinyKV的垃圾回收机制可以对其进行异步回收，从而提升垃圾回收的效率.由于在回收的过程中，回收块中的有效数据非常少，因此TinyKV的垃圾回收效率较高.

在扫描全局块状态表，建立起最小堆后，选择堆顶的块，把其中的有效数据移动到垃圾回收线程自己的日志中.垃圾回收算法通过扫描被选中块的所有数据对象，计算对象的Hash值，通过Hash表进行查询数据对象是否还被引用.如果正在被引用，说明它是有效数据；否则说明它是垃圾对象.由于日志是不允许修改的，并且数据对象不能使用反向指针指向引用它的桶或数组链，故在数据被修改或删除时，TinyKV不能通过标记来记录数据修改或删除的信息，所以在扫描时不能单纯依靠数据本身识别它是否为有效数据.最后更新Hash表中关于更新被移动数据的索引信息的操作，流程大致与插入操作相似，不同点在于要比较Hash表中的关于这个数据对象的索引信息是否相同.若不同，说明在垃圾回收的过程中，这个数据对象已经被其他线程进行了修改，那么被移动的对象即可删除；若相同，把索引信息更新到数据对象所在的当前位置.

3.6 数据持久化

目前一种比较有效的方式是把非易失内存和DRAM一样映射成写回的方式(write-back)，通过特殊的CPU指令来保证修改的数据能够最终到达非易失性内存中.clflush是比较传统的刷新高速缓存行的方式，它把数据从高速缓存中写回内存中并使高速缓存行失效，多个clflush的顺序是固定的；clflushopt是对非易失性内存进行优化而提出的指令，会使高速缓存行失效，但这个指令是无序的.通常情况下，clflushopt的性能比clflush要好，适用于在比较大的数据中使用.clwb同样是对非易失性内存进行优化而提出的指令，不同于clflushopt的是它不会使高速缓存行失效.不过，这些指令不能保证数据能够到达非易失性内存上，必须使用内存屏障原语(sfence)明确地表示要等待这些指令的完成.在TinyKV中，只有当日志满时，才会使用clflushopt或clflush对整个日志的数据持久化；当修改一个数据对象时，持久化必要的元数据信息，同时计算存储数据的校验码，以便在系统恢复时能够回退到一致状态.

当TinyKV正常关闭时，为了快速恢复数据，TinyKV会将所有当前活动日志和一些数据结构(例如分配器)转移至NVM.在TinyKV异常关闭的情况下(例如系统崩溃)，TinyKV必须恢复到一致状态，并通过扫描数据日志来重建一些数据结构，这个过程较为迅速.TinyKV快速恢复的过程具体描述为：1)检测TinyKV日志的大小，正常情况下，TinyKV日志的大小不会大于块的大小；2)当日志已满时，日志中的键值对象通过内存分配器将数据持久化保存到NVM，但可能会存在尚未来得及回收的日志；3)TinyKV为每个可能的未回收的日志启动一个恢复线程，其会扫描其日志中的所有键值对象，记录第1个损坏对象，将日志的尾部设置为该对象的地址，并将剩余对象故障前的旧地址压入恢复堆栈；4)通过恢复线程，所有堆栈中的对象将会回滚至故障前状态.

4 实验与结果

4.1 实验环境

实验设备如表1所示，本次实验中，实验所用的计算机是Dell-R730，操作系统内核版本是Linux 2.6.32.机器装备了2个10核的CPU，其型号参数是Intel®Xeon E5-2650-V3，2.3 GHz，Ivy Bridge EP.每个CPU的L3缓存是25 MB，每个核的L2缓存是10×256 KB.机器上装备了128 GB的DDR3 DRAM，使用DRAM模拟NVM.

Table 1 Experiment Configuration表1 实验环境配置

1) 对比系统.本次实验对TinyKV,LevelDB和Masstree[32]的性能做了比较.LevelDB需要文件系统存储数据，我们在内存中创建一个文件系统，并把LevelDB的数据文件存放到这个文件系统中.Masstree是一个键值内存存储系统，使用B+树作为系统的索引结构，类Trie的数据结构对B+树进行连接.为了减少数据访问的延迟，它大量采用了数据预取技术.

2) 测试数据集.本次数据采用的数据集是用YCSB[33]性能测试工具集生成的.数据集的类型和大小等信息如表2所示.数据集的类型根据数据的分布特征可分为2种：均匀(uniform)分布和偏斜(skewed)分布.均匀分布的数据是等概率随机生成的；偏斜分布的数据是根据Zipfian分布生成的，其数据分布的特征是某些数据比大多数数据的出现次数要高很多.根据大小和数据分布，我们生成了4个数据集，其特点如表2所示:

Table 2 Workload Figures表2 测试数据集特征

4.2 读写性能

本节将对比各系统单线程的读写性能.对于每一类型的数据集合，在进行写性能测试时，每一次测试，我们都重新建立一个存储系统，通过持续不断地插入数据，得出实验结果.在进行读性能测试时，所有的存储系统都预先存储了6 400万个数据，通过连续地进行数据查询，得出实验结果.系统的单线程写性能测试结果如图7所示：

Fig.7 Single thread write throughput图7 写性能测试

在TinyKV-flush模式中，TinyKV通过clflush和内存屏障原语对元数据进行持久化.在一个日志空间写满时，对整个日志的数据进行持久化，针对未来得及持久化的日志内的数据，依靠系统恢复时检错并回滚到一致性状态.在TinyKV-noflush模式中，不使用刷新高速缓存的指令进行数据持久化.通过对比2种模式的实验结果揭示数据持久化对系统性能的影响.在测试LevelDB和Masstree时，我们不使用相关指令对数据进行持久化操作.在TinyKV-noflush模式下，TinyKV的写性能优于LevelDB和Masstree.当进行数据持久化操作时，即在TinyKV-flush模式中，TinyKV的系统写性能有很大的损失.在数据对象比较小时，吞吐量减少了40%左右;在数据对象比较大时，吞吐量减少了20%左右.

我们比较在TinyKV-flush模式下的TinyKV和LevelDB,Masstree.如图7所示，在均匀分布的数据集上TinyKV的性能比LevelDB和Masstree要好.在小数据对象的数据集测试中，TinyKV的吞吐量是LevelDB的10倍，是Masstree的2.6倍；在大数据对象的数据集测试中，TinyKV的吞吐量是LevelDB的30倍，是Masstree的7倍.通过大小数据对象的测试性能差异，可以看出TinyKV的索引结构是比较有效率的.另一方面，如图7所示，在偏斜分布的数据集上，当数据对象比较小时，TinyKV的写性能要比Masstree要小，这是数据持久化带来的负面影响.在偏斜分布的数据集中，由于某些数据出现的次数要比大部分数据要多，所以如果能对这些数据做缓存则系统的性能会有很大的提升.这是系统在偏斜分布数据集测试性能比均匀分布数据集优异的原因.但TinyKV使用刷新高速缓存的指令做数据持久化时，会与Hash表和数据链有关的高速缓存行失效.这样，对TinyKV来说，偏斜分布数据集上的数据空间局域性荡然无存.如果使用clwb替代clflush，这种情况或许能得到改善.

图8展示了TinyKV,Masstree以及LevelDB的读性能.读性能测试不涉及数据的持久化过程，故TinyKV的运行模式是TinyKV-flush.如同Masstree一样，TinyKV追加一个与key相关联的value的指针.当存储系统中不存在key时，返回一个空指针.在不同的数据集上，TinyKV的性能都比其他系统要好.正如系统的写测试的实验结果，这些系统在偏斜分布数据集的测试性能比均匀分布数据集的测试性能更加优异.

Fig.8 Single thread read throughput图8 读性能测试

4.3 并发性能

在TinyKV系统中，数据查询不需要加锁，当不对系统的数据进行修改时，CPU的高速缓存不会由于缓存一致性而失效，系统多线程查询性能良好.

图9展示了不同系统在小对象均匀分布的数据集上的多线程写性能.可以看出TinyKV和Masstree的扩展性比较好.LevelDB的曲线比较平缓，其吞吐量基本维持在0.02 Mops左右；Masstree在单线程时它的吞吐量是0.11 Mops，当使用10个线程时，它的吞吐量也达到了0.21 Mops.TinyKV在单线程时的吞吐量是2.1 Mops，在4线程时它的吞吐量达到了5.4 Mops，在10线程时它的吞吐量达到了6.7 Mops.这一方面得益于TinyKV每个线程使用了专有的日志及Hash表的桶有独立的写锁，另一方面随着线程的增多，写锁资源的竞争会激烈.

Fig.9 Write throughput of multi-threads图9 多线程性能测试

现有的基于NVM的键值存储系统依赖于一些主流的索引数据结构，如B树、RB树等，并在数据更新时保证这些数据结构的一致性.NVTree，FPTree工作是针对B+树做了并发一致性方面的工作，在范围查询方面，B+树可以表现出更高的性能.TinyKV采用Hash索引方式是为了保证系统的轻量级特性：支持高吞吐率的PUT/GET操作，这在一定程度上牺牲了范围检索的性能.

一些键值存储系统，如MICA，HiKV等，同样采用了Hash结构的键值索引方式.但是它们与TinyKV的设计理念不同：MICA是一种高速内存键值数据库，但没有结合NVM去保证数据持久性.因此，若要支持持久性，现有的MICA需依赖于传统的技术方案：写日志到磁盘或定期做检查点.这会导致以页(4 KB)为单位的数据同步产生严重的I/O开销.HiKV使用一种混合索引结构，既支持Hash索引也支持B+树索引.这使得HiKV可以支持复杂的负载数据处理，例如范围检索+特定数据集合.然而，在简单的负载数据处理上，TinyKV仍旧更有优势.这得益于TinyKV全局Hash的索引结构设计，以及多线程并发机制的支持.

由于时间原因和硬件条件的限制，例如：MICA对服务器和客户端均做了一定程度的硬件假设，如NUMA结构支持、多核支持等；HiKV暂时不开源，复现工作需要较多时间.因此，我们没有展开实验进行说明，敬请谅解.

5 总 结

本文设计并实现一种基于日志结构的非易失性内存键值存储系统TinyKV，采用分块技术对非易失性内存进行划分，以块为单位对存储空间进行管理；使用日志结构的数据修改方式，既满足数据一致性的存储要求又能提高存储空间的利用率；通过设计多日志的存储结构，减少多线程的竞争，提高系统扩展能力；设计多级的内存分配器，在底层进行块管理，中间层进行日志管理，上层进行DRAM数据对象空间分配；实现了一个高效的Hash表作为存储系统的索引结构，它通过估算Hash表的大小分配比较大的初始空间，从而减少Hash表的冲突概率并减少Hash表的扩容次数；使用动态数组作为解决Hash冲突的存储方式，对Hash表实现了允许多读单写的读写方式；在垃圾回收算法中，通过扫描块状态表在DRAM中构建运行时需要的数据信息，避免把垃圾回收算法产生的数据存储到非易失性内存中.实验测试结果证明，TinyKV具有良好的吞吐性能和扩展能力，在使用均匀分布的小对象数据集进行多线程写性能测试时，TinyKV单线程的吞吐量为2.1 Mops，4线程的吞吐量为5.4 Mops，TinyKV的吞吐量是LevelDB的10倍，是Masstree的2.6倍；在大对象数据集测试中，TinyKV的吞吐量是LevelDB的30倍，是Masstree的7倍.