键值存储引擎(key-value storage engine)在网络索引、电子商务、社交网络和云存储等现代数据密集型应用中发挥着越来越重要的作用,然而内部存储器和外部存储器的固有缺陷成为制约键值存储引擎的瓶颈。随着存储器技术的发展,出现了一类新型存储器——非易失存储器(non-volatile memory,简称NVM),非易失存储器既有内部存储器按字节寻址和低延迟的优点,又有外部存储器非易失和容量大的优点。研究基于NVM的键值存储引擎关键技术有望解决现有的键值存储引擎所面临的瓶颈问题。本文首先通过源码分析了基于外存的键值存储引擎Level DB的系统框架及运行机制,然后通过实验分析了Level DB的读延迟和写放大(write amplification),根据实验结果得出重要结论:一方面,SST文件引发的数据反序列化开销和顺序层次索引的维护开销在读延迟中占比很高;另一方面,文件分层的键值数据合并策略引发了很高的写放大,不仅降低了数据写入性能而且大幅缩短了NVM的使用寿命。根据此结论,本文从算法和工程上对Level DB进行了重新设计,实现了基于NVM的键值存储引擎Nova DB。这些改进主要包含:(1)用持久化索引替换SST文件和顺序层次索引,设计高效的搜索算法替换二分查找;(2)用索引与数据分离的键值数据(data compaction)合并策略替换文件分层的键值数据合并策略;(3)用持久化的原地更新(in-place update)方式和基于关键数据划分的故障恢复策略分别替换写时复制更新方式和日志技术。本文通过微基准测试(micro-benchmark)实验和宏基准测试(macro-benchmark)实验对比了Nova DB和Level DB。实验结果表明,Nova DB的数据写入性能最高约为Level DB的12倍;Nova DB的点查询性能最高约为Level DB的23倍;Nova DB的范围查询性能最高约为Level DB的33倍;Nova DB的写放大比例约为Level DB的5.2%;Nova DB的故障恢复速度约为Level DB的196倍。本文通过分析实验现象的成因验证了这些改进方案的有效性,最后总结适用于NVM的键值存储引擎技术方案。