关键词：
键值数据库
性能优化
范围查询
合并操作
自适应方法
摘要：
随着大数据技术和应用的快速发展,如何实现大数据的高效存取成为亟待解决的一个关键问题。基于日志结构合并树(Log-Structured Merge Tree,LSM-tree)的键值数据库(Key-Value Store)是当前实现大数据存储和管理的主要技术之一,诞生了 LevelDB、RocksDB等多个开源数据库系统。由于键值数据库系统具有接口简单、低延迟、高吞吐、可扩展性强等优点,被广泛地应用在各种大数据应用中,成为当前应对海量数据管理的重要手段。然而,由于LSM-tree固有的写缓存和分层结构特性,现有的键值数据库系统很难在多样化的大数据应用场景下都能够保持较高的读写性能。这是因为LSM-tree 本质上是一种写快读慢的存储结构,它通过将随机写转换为批量的顺序写提升系统的写性能。与此同时,这一设计也带来了查询性能差、读写放大、空间放大等问题。因此,优化基于LSM-tree的键值数据库系统性能,对于进一步促进键值数据库技术的发展和应用,具有十分重要的意义。本论文围绕基于LSM-tree的键值数据库系统存在的问题,重点研究了键值数据库系统查询性能优化、写优化、负载自适应以及对新型非易失内存的适配等问题,旨在进一步优化键值数据库系统的读写性能和自适应能力,为未来键值数据库技术的发展提供参考。总体而言,本论文的主要工作和贡献可总结为以下几个方面:(1)提出了一个优化键值查询的高性能布隆过滤器RoBF:布隆过滤器(Bloom Filters)是现有的键值数据库系统用以优化查询性能的主要技术之一。然而,已有的布隆过滤器难以有效处理范围查询。针对这一问题,本文提出了一种可以同时支持点查询和范围查询的新型布隆过滤器:RoBF(Range-query-oriented Bloom Filters)。RoBF采用了新的差异化前缀设计,通过动态配置前缀长度来适应查询负载。论文提出了一种基于统计信息的过滤器参数优化算法,能够根据范围查询的密集程度来动态改变布隆过滤器的前缀设置,从而能够在保证时间性能的同时降低空间代价。我们在100GB数据集上与RocksDB进行了实验对比。结果表明,RoBF的混合查询性能在最好情况下比RocksDB提升了 30倍。(2)提出并实现了一个基于自适应合并策略的键值数据库系统B+LSM:合并(Compaction)机制是键值数据库系统中的关键操作,对系统性能有着极大的影响。现有的键值数据库系统采用的Leveling Compaction和Tiering Compaction机制各有优缺点:Leveling Compaction的查询性能较高,空间放大较小,但写放大严重,写性能较差;Tiering Compaction的写放大较低,写性能较好,但查询性能差,空间放大严重。因此,Leveling和Tiering Compaction都难以满足不同的负载要求。针对这一问题,本文提出了一种节点容量可以自适应调整的合并策略:Bundle Compaction,并实现了一个新的键值数据库系统B+LSM。B+LSM采用一种类似B+-tree的结构替换了传统LSM-tree的层次结构,每个树节点的大小可以随着负载的变化而动态调整,从而实现读写性能的平衡。B+LSM提出了一种BCU节点容量的自适应调整机制,使得系统可以同时利用Leveling和Tiering Compaction的优点。我们实现了 B+LSM并与多个键值数据库系统(包括LevelDB,RocksDB,PebblesDB和L2SM)进行了对比。在YCSB负载上的实验结果表明B+LSM在运行时间、I/O代价、空间放大等多个指标上均优于对比系统。(3)提出并实现了一个面向大内存的键值数据库系统OMDB:现有的键值数据库系统通常采用内存层和磁盘层两层存储结构,并且严格区分读缓存和写缓存。这种结构需要频繁地将内存数据刷到磁盘,在大内存环境下会带来长时间的写入阻塞。而且读缓存会由于频繁的写操作而失效,导致热数据无法长久存储在内存,使得读性能下降。针对这些问题,本论文提出了一个新的键值数据库系统OMDB。OMDB首先提出了一种新的存储结构OM-tree,采用索引节点和数据节点实现了数据的水平分区存储,从而将数据刷盘的开销均摊到分区,降低写磁盘时的I/O压力。其次,OMDB通过节点重构使得缓存能够在读密集情况下尽量作为读缓存,而在写密集情况下尽量作为写缓存,从而提高缓存的效率和系统的读写性能,实现了对负载的自适应。最后,为了防止由日志锁定带来的磁盘资源过量消耗从而影响性能,我们在OMDB中提出了一种基于日志流的垃圾回收算法,保证了 OMDB中的内存表的自由操作,避免系统读写操作被日志长时间阻塞。我们在YCSB负载上对比了 OMDB的多个版本和RocksDB的性能。结果表明,OMDB可
