关键词：
数据库系统
事务处理
隔离级别
并发控制协议
负载生成
正确性验证
代码缺陷发现
摘要：
数据库系统旨在提供一种有效、安全、一致和可靠的数据存储和检索方式。随着互联网的不断发展与普及,特别是移动互联网的兴起,数据规模呈现爆炸式增长的趋势,数据处理的需求也变得愈发多样化和复杂化。根据数据处理的需求可以大致分为以下三类数据库工作负载,在线交易处理(Online Transaction Processing,OLTP)、在线分析处理(Online Analytical Processing,OLAP)和混合工作负载(Hybrid Transactional/Analytical Processing,HTAP)。现实世界日益变化的数据处理需求驱动着数据库系统的设计和实现不断地发生演进和革新,数据库系统的内部实现代码也随之不断更新和迭代。在代码快速更新和迭代的过程中,完善数据库系统的正确性是数据库系统研发生态的关键环节,实现错误的数据库系统会给真实生产应用带来严重的后果。
数据库系统的隔离级别是用于在并行事务处理的过程中保证数据一致性和完整性的重要功能,错误的隔离级别实现会破坏数据库中数据的正确性。因此,探索一个面向数据库系统隔离级别的正确性评测方法具有重要研究意义。具体来说,研究隔离级别的正确性评测方法需要解决以下两个研究问题。第一,评测负载生成方法,生成有效评测隔离级别的工作负载,并输入到被测试的数据库系统;第二,隔离级别正确性验证方法,校验被测试数据库系统是否按照隔离级别的定义处理工作负载。然而,已有数据库系统的隔离级别评测方法缺乏一种有效、非冗余、定制化的隔离级别评测负载生成方法,也无法以一种通用、黑盒、高效的方式完成隔离级别的正确性验证任务。因此,围绕着数据库系统的隔离级别评测任务,本文针对上述两个问题进行深入的研究,主要工作和贡献总结如下:
(1)OLTP数据库的隔离级别评测负载生成问题。隔离级别定义了存在数据访问冲突的事务之间的隔离程度。为了评测隔离级别,需要生成具有数据访问冲突的工作负载。然而,一个事务预期访问的数据可能会被其他并行事务修改,这可能导致该事务无法访问数据,从而无法参与冲突的形成。为了解决这一挑战,本文提出了一种轻量级方法,用于镜像数据状态,以确保每个生成的事务能够访问预期的数据,从而参与冲突的形成。其次,如果两个工作负载中数据访问冲突具有相似性,意味着它们对于评测隔离级别具有类似的效果。为了提高效率,需要尽可能生成具有不同冲突关系的工作负载。已有的研究方法是基于所有历史负载来搜索一个大于差异性阈值的新负载。然而,随着历史负载的增加,搜索的成本会显著增加。为了应对该挑战,本文提出两种负载编辑方法分别单调地演化负载中事务数量和冲突密度,以不依赖于历史负载的方式生成一系列具有一定差异性的负载。最后,在数据库系统中存在多种多样的隔离级别,数据库开发者往往通过禁止某些非可串行化异常的方式来定义隔离级别。因此,一种在工作负载中定制异常的方法是迫切需要的,以便检查系统是否按照隔离级别的定义禁止异常。然而,非确定性的并发控制协议使得数据访问的冲突关系无法预测,这阻碍了特定异常的形成。为了克服这一挑战,本文设计了一种可定制异常的工作负载生成方法,通过注入特定操作并编排事务执行顺序,以确定性地形成异常。实验效果表明本文提出的面向隔离级别的评测负载生成方法具有高效性、有效性和可扩展性。
(2)OLTP数据库的隔离级别正确性验证问题。现有的正确性验证方法可以分为面向内核的方法和面向工作负载的方法。第一种方法需要修改内核代码,不适用于闭源的系统。第二种方法依赖于简单的工作负载,不适用于更加复杂的工作负载。为了实现一种不依赖于内核和负载的验证方法,本文提出在客户端收集负载轨迹进行验证的方法。具体而言,负载轨迹包含了每个操作的执行时间区间,用于推断操作的执行顺序和事务之间的依赖关系,这种方法不仅对工作负载不敏感,也可适用于任意一个数据库系统。其次,数据库系统中存在多样化的隔离级别,这增加了通用验证方法的设计难度。为了解决该问题,本文将隔离级别的实现归纳为四种经典机制,包括一致性读取、第一写者优先、串行化见证者、互相排斥,这四种机制实现了典型商用数据库系统中所有的隔离级别。最后,与隔离级别相关的错误可能导致数据出现损坏,并且可能会被恶意攻击者利用。因此,为了尽早修复错误和降低数据损坏的风险,有必要及时验证在数据库上执行的每个事务。然而,现代数据库系统高吞吐的事务处理能力对隔离级别验证的效率提出了严峻的挑战。为了高效地验证隔离级别,本文首先设计一个两级流水线策略对运行负载产生的海量流式负载轨迹进行排序。基于排序后的负载轨迹,本文提出机制镜像的验证方法,该验证方法直接模拟数据库系统内部的并发控制协议,从而加快验证的效率。实验结果表明,上述方法在验证时间上的性能优于现有方法,最高可达到114倍。
(3)HTAP数据库的隔
