大数据技术的蓬勃发展,需要对海量数据进行高效保存和处理,从而对存储系统提出更高性能需求。基于日志结构合并树(Log-Structured Merge-Tree)实现的键值存储系统,在处理写请求时能够将小颗粒的随机写聚集成大颗粒的连续写从而充分利用外存设备带宽,因此具有高吞吐能力并被广泛应用在大规模存储环境中。近年来,计算机硬件技术也在快速发展。在计算方面,多核处理器和高并行专用处理器已经普及;在存储方面,新型非易失性存储器与DRAM内存的性能鸿沟不断缩减,以及支持并发IO的闪存固态盘已得到广泛部署并逐渐取代机械硬盘。面对日益庞大的海量数据和新型硬件的特性,基于传统硬件资源设计的日志结构合并树键值存储系统在新应用环境中面临巨大挑战。针对上述形势,需要对日志结构合并树键值存储系统从处理逻辑、存储过程、和存储介质等方面重新审视并综合优化以适应大规模数据对高性能存储的迫切需求。国内外学术界和工业界也在这方面进行多维度研究,包括定制化日志结构合并树以优化特定负载下的性能、更改日志结构合并树合并策略以减少写放大、设计面向闪存固态盘或者其他非易失存储器的日志结构合并树等。本文研究工作着重从日志结构合并树的内存缓冲结构、IO存取过程、模型设计这三个方面分析其在部署和研究工作中面临的关键问题,进而提出有效解决方案。首先,日志结构合并树使用一块内存区域作为新数据缓冲区,当前键值存储系统对此缓冲区的数据通常使用跳表结构进行保存和索引。在新型非易失性外存储器与DRAM内存的性能鸿沟不断缩减的趋势下,缓冲区跳表结构由于处于读写请求处理的关键路径,其性能对基于日志结构合并树存储系统的发展至关重要。目前的跳表有概率型和确定型两种,前者维护代价小但是索引结构不稳定,而后者反之。基于此,提出在搜索过程中按需创建索引节点的新型跳表结构Bod Skip以提高内存缓冲区结构的性能。Bod Skip根据遍历步数确定是否需要创建索引节点而非凭借随机概率,因此支持生成稳定索引。同时,索引节点按照历史搜索信息生成,避免因创建无价值索引产生的额外开销。在加入新节点时,Bod Skip只涉及对新节点前后两个相邻节点的更新,因此在并发操作上具有优势。其次,日志结构合并树键值存储系统的主流实现方式依托传统基于“应用/文件系统/块设备”的多层存储处理栈,并通过文件系统将日志结构合并树管理的数据持久化保存在块设备上。然而,文件系统层的引入严重影响日志结构合并树对外存设备带宽的利用。通过深入分析三个典型文件系统在存储日志结构合并树时所产生数据的IO特征,发现外存设备带宽无法得到有效利用的原因在于文件系统会产生尺寸小但数量多的额外IO。以实验证实和量化了文件系统层所引起IO在机械硬盘和固态盘上的性能代价后,据此提出日志结构合并树直接存储技术并实现原型系统LDS。直接存储技术的原理是使用日志结构合并树结构管理外存空间以完全消除文件系统层引入的IO开销。最后,基于日志结构合并树实现或衍生的键值存储系统种类众多,但是缺乏一个分类体系,使得部署和研究工作面临着低效以及难以进行准确评估的问题。针对此问题,全面分析并归纳包含日志结构合并树在内的多阶合并结构的根本特征,提出“树/森林”分类模型,并在此基础上进一步探索多阶合并结构仍然存在的设计空间,提出一种基于森林模型的高性能键值存储系统Sifr DB。“树/森林”分类模型的提出突破日志结构合并树概念的局限性,从原理上解释了已有键值存储系统性能偏好的根源。根据该模型对基于不同类型多阶合并结构的键值存储系统进行了严格区分,使得在部署和进行相关研究工作时对模型或系统在选择和认识上有章可循。Sifr DB在实现上吸收了各自模型优点的同时又避免了其缺点,并能够无缝运行于所提出的LDS系统上获得直接存储的收益。另外,在Sifr DB中设计了一种高效的并行搜索算法解决森林模型较为突出的读降级问题,该算法充分利用固态盘的内部并行性显著提高了查询性能。总而言之,本文研究工作全面审视传统日志结构合并树键值存储系统的整体架构和数据处理过程,分析关键性能问题并提出最大化挖掘硬件潜力的优化方法,实现应用逻辑和硬件特性有效结合以全面提升日志结构合并树键值存储系统在大规模存储环境中的性能。