关键词：
数据库系统
日志结构合并树
更新密集型负载
垃圾回收机制
混合负载
键值分离
负载均衡
AI4DB
摘要：
存储模型是线上系统稳定运行的基础,为各种关键性应用业务提供了高效存储和检索功能,是数据库管理系统中不可或缺的组成部分。而随着移动互联网、云计算产业、物联网等行业的快速迭代,数据存储正以指数级增长。这一现象给数据库系统中的存储模型带来了巨大的挑战。基于日志结构合并树(Log-Structured Merge-Tree,LSM-tree)实现的存储模型采用了异步更新(Out-of-place Update)方式和层次存储管理结构,能够将处理写请求的小颗粒随机写聚集成大颗粒连续写从而充分利用持久化存储硬件的带宽,因此具有高吞吐能力和高空间利用率并被广泛应用在各种数据库系统的存储模型中。随着业务的不断更新迭代,应用负载也向多样化的趋势发展,数据库系统面临的工作负载也逐渐变得复杂化和多样化。而日志结构合并树作为一种写优化的数据结构,在面对数据库系统的复杂和多样化负载时,现有的研究工作仍然存在一些不足且拥有进一步优化的空间。首先,日志结构合并树的异步更新方式让数据库系统在处理更新操作时存在更多可能性。更新操作产生的大量无效的旧版本数据在磁盘空间利用率、读写性能上都产生了较大影响,而现有的垃圾回收机制决定了日志结构合并树不能立即将其从系统中剔除。另一方面,数据库系统通常将增量存储或者全量存储作为系统唯一的更新操作的数据存储方式,如何细粒度地为每个更新操作选择合适的更新方式也值得研究。其次,日志结构合并树中频繁地触发合并操作会让系统的写性能存在较大的波动,而现有的优化手段通常是以牺牲查询性能为代价提升系统的写性能。因此,在保证稳定的写性能的前提下,提升日志结构合并树的范围查询性能是数据库系统的主要优化目标。最后,随着数据量的爆发式增长,单机的存储系统架构逐渐向分布式架构发展。在持续批量摄入数据的高并发场景中,基于日志结构合并树实现的分布式数据库系统面临的主要问题是各个存储节点承担的合并压力不同,导致应用不能充分利用分布式系统的高吞吐和高并行性的能力来完成数据摄入任务。尽管已有的一些负载均衡算法能够在一定程度上减少合并负载不均衡的现象,但是这些方法通常考虑的影响因素比较单一,不能够适用各种不均衡场景。因此,无论是在单机架构还是分布式架构下,数据库系统中的日志结构合并树在各种不同类型的工作负载下的性能仍然值得进一步研究和探索。基于上述三个关键问题,本文的主要工作和贡献总结如下:(1)针对日志结构合并树中的更新操作引起的垃圾回收问题以及更新操作如何选择更新方式问题,本文提出了快速的垃圾回收机制以及设计了一种自适应更新选择策略。首先,为了减少大量无效的旧版本数据在磁盘中的存活时间,本文设计了快速的垃圾回收机制。该机制将垃圾回收中识别无效的旧版本数据和删除旧版本数据两部分工作分开,为系统在控制写放大、空间放大等问题上提供了灵活性。并且能够保证每条被逻辑删除的数据能够只经历一次合并操作就能被永久地删除。另一方面,对于更新操作是否选择增量存储还是全量存储的方式,本文设计了一种自适应判断机制。该机制能够根据每个更新操作的特征选择合适的更新方式,从而在系统的写放大和读放大方面做到很好的权衡。(2)针对在混合负载中读写性能存在相互制约的问题,本文基于键值分离技术设计了读写均衡的键值数据库TargetedKV。为维护稳定高效的写入性能的同时不降低范围查询的性能,本文首先在SSTable层面采用键值存储分离方案。该方案支持在日志结构合并树重新组织数据时只维护磁盘组件的每层Key完全有序,维护Value部分有序,从而实现较低的写放大的同时满足范围查询的延迟需求。此外,本文还将磁盘组件的数据按照主键顺序分成多个数据分区,利用查询负载的局部性特征来指导合并操作,从而能够快速将某一范围的数据聚集在少数文件中,进一步提升范围查询的性能。(3)针对基于日志结构合并树实现的分布式数据库系统中存在的合并负载不均衡问题,本文提出了一个基于机器学习的均衡框架LeaBalancer。分布式数据库系统通常采用范围分区的方式实现水平扩展功能,而本文考虑到影响每个范围分区数据合并效率的各种因素,并通过机器学习方法将这些因素融合在一起来预测每个数据分区完成数据合并的时间。基于预测结果,本文分别设计了单节点调度策略和多节点之间的调度策略。通过两层调度方案,LeaBalancer可以在尽量少迁移数据的情况下完成节点之间的合并负载的均衡。综上所述,本文深入研究了数据库系统中基于日志结构合并树实现的存储模型在垃圾回收、范围查询、负载均衡等方面的研究工作存在的不足,并且基于不同场景特点提出了三种优化方案。前面两个工作主要解决单机架构下键值数据库的读写性能均衡问题以及更新操作引起的垃圾回收和更新数据存储问题。而最后一个工作主要探讨分布式架构下的日志结构合并树的合并负载不均衡问题,并给出了相应的调度方案。基于
