论文部分内容阅读
键值存储系统是当前数据中心的主要存储技术，具有高性能、高可用和高扩展性的特点，能够满足大数据环境下的数据存储需求。另外，非易失性内存(Non-Volatile Memory，NVM)是一种新型存储设备，具有数据非易失、高存储密度、高性能和高并发等特点。新型NVM设备的出现，也为研究更高效的键值存储系统带来了机遇与挑战。
基于日志结构合并树(Log-StructuredMerged-Tree，LSM树)的键值存储系统是针对硬盘设计的，存在严重的读写放大问题，未能充分利用NVM设备特性。另外，在NVM的相关研究中，基于基数树(Radix树)的索引结构比B树类的索引结构具有更好的性能，但是存在严重的空间浪费问题。针对以上两个问题，提出了一种新型混合树索引结构HybridTree，HybridTree采用Radix树和B+树的组合结构，整体上呈现分层结构：上层由类似Radix树的前缀索引节点组成，通过插入键的前缀进行索引来加速数据定位，并提供多线程支持；下层通过变长自适应的B+树节点来组织键值数据，减轻节点稀疏造成的空间浪费问题，在利用NVM设备特性保障系统高性能的同时，有效提高索引结构的空间利用率。最后，利用NVM的CPU直接访问及可字节寻址特征，基于HybridTree设计了一种高性能的NVM键值存储系统HybridKV，通过直接在NVM上存储HybridTree，避免了LSM树分层结构带来的读写放大问题。
HybridKV系统原型基于开源LevelDB实现，并在真实的NVM设备(Intel Optane DC Persistent Memory)上对HybridTree和HybridKV进行了测试与性能评估。测试结果表明HybridTree的随机写性能是Fast&Fair的1.20~1.62倍，是NV-Tree的1.11~1.52倍，较WORT的空间占用减少了54%左右。HybridKV系统的随机写性能最高可达LevelDB的7.5倍，RocksDB的3.23倍；另外随机读性能最高超过了NoveLSM的7倍。
基于日志结构合并树(Log-StructuredMerged-Tree，LSM树)的键值存储系统是针对硬盘设计的，存在严重的读写放大问题，未能充分利用NVM设备特性。另外，在NVM的相关研究中，基于基数树(Radix树)的索引结构比B树类的索引结构具有更好的性能，但是存在严重的空间浪费问题。针对以上两个问题，提出了一种新型混合树索引结构HybridTree，HybridTree采用Radix树和B+树的组合结构，整体上呈现分层结构：上层由类似Radix树的前缀索引节点组成，通过插入键的前缀进行索引来加速数据定位，并提供多线程支持；下层通过变长自适应的B+树节点来组织键值数据，减轻节点稀疏造成的空间浪费问题，在利用NVM设备特性保障系统高性能的同时，有效提高索引结构的空间利用率。最后，利用NVM的CPU直接访问及可字节寻址特征，基于HybridTree设计了一种高性能的NVM键值存储系统HybridKV，通过直接在NVM上存储HybridTree，避免了LSM树分层结构带来的读写放大问题。
HybridKV系统原型基于开源LevelDB实现，并在真实的NVM设备(Intel Optane DC Persistent Memory)上对HybridTree和HybridKV进行了测试与性能评估。测试结果表明HybridTree的随机写性能是Fast&Fair的1.20~1.62倍，是NV-Tree的1.11~1.52倍，较WORT的空间占用减少了54%左右。HybridKV系统的随机写性能最高可达LevelDB的7.5倍，RocksDB的3.23倍；另外随机读性能最高超过了NoveLSM的7倍。