摘要
分布式数据库对比集中式数据库有更高的可扩展性和性能。由于分布式数据库的复杂性，在实际应用过程中无法避免网络中断，丢包，节点宕机等软硬件故障。为了减轻故障问题对分布式数据库带来的影响，分布式数据库需要持续进行故障注入测试，即在系统正常运行过程中通过编码模拟主动触发故障问题，提高分布式数据库的可靠性以及验证系统内部容错机制的正确性。本文设计并实现了针对分布式数据库系统容错性问题的故障注入测试工具 AFTest。主要贡献为：
1. 轻量级的任务调度设计：同时支持手动提交测试案例和自动遍历已有情况下的事件组合情况。测试人员可以通过前端界面实时查询测试进度，历史记录以及被测试系统当前状态。后端任务调度程序能够定时生成测试案例并根据案例生成执行脚本，然后分配工作线程执行测试并记录相应的日志信息和测试过程中系统状态的变化。
2. 实现了一个故障注入框架：分析分布式数据库在现实应用过程中曾经出现的各类软硬件故障问题，通过编码模拟实现其中常见的多种软硬件故障问题以及 Cedar 特有的系统操作。模块化故障注入框架便于嵌入测试工具中使用。
3. 减少事件组合空间冗余问题：深度遍历所有故障组合事件，避免繁琐的测试案例编写，更高效快速地针对分布式数据库系统执行故障注入测试。通过减少状态空间的算法消除冗余测试案例，避免出现测试案例过于繁多的问题。
本文在开源的分布式数据库系统 Cedar 上进行了 AFTest 的故障注入测试。通过实验说明了 AFTest 的有效性，能够如实模拟各类分布式故障问题的发生。AFTest 在遍历所有事件组合情况下能够发现分布式数据库中潜在的复合型 bug，同时能减少冗余案例对测试过程的影响加快测试进度。
关键字：分布式数据库，故障注入测试，容错性，故障注入框架，数据库测试。
ABSTRACT
Distributed databases have higher scalability and performance than centralized databases. Due to the complexity of the distributed database, software and hardware failures such as network interruption, packet loss, and node downtime areunavoidable in the real world. The distributed databases should continue to perform fault injection testing, that is, proactive triggering of faults through coding simulation during normal system operation in order to reduce the loss caused by the failure problem to the distributed database, improve the reliability of the distributed database and verify the correctness of the fault tolerance protocol in the system. This thesis designs and implements a fault injection test toolAFTest for fault tolerance of distributed database systems. The main contributions are as follows:
1. Flexible task scheduling design: it supports manual submission of test cases and automatic traversal of existing event combinations at the same time.Testers can query the test progress, historyand real-time running status of thetested system in real time through the front-end interface. The back-end task scheduler can periodically generate test cases and generate execution scripts based on the cases, assign specified worker threads to execute the tests andrecordthe corresponding log information and system state changes during the test.
2. Implemented a fault injection framework: we first analyze the various types of software and hardware failure problems that have occurred in the distributed database in the actual application process. Then we implement a variety of software and hardware failure problems and Cedar's unique system operations through coding simulation.
3. Reduce state space explosion: we deeply traverse the combination of most fault events in order to avoid tedious test case writing and perform fault injection testing of distributed database systems more efficiently and quickly.
We then reduce redundant test cases through algorithms that reduce the state space to avoid problems with too many test cases.This dissertation conducted a fault injection test on the open source distributed database system Cedar with AFTest. This paper demonstrates the effectiveness of AFTest throughexperiments, whichcanrealisticallysimulate the occurrence ofvarious distributed fault problems. AFTest can find potential compound bugs in distributed databasesbytraversingallevent combinations, at thesametime it canreducetheimpact of redundant cases on the testing process and speed up the test progress.
Key words： Distributed Database, Fault Injection Testing, Fault Tolerance, Fault Injection Framework, Database Test。
第一章 绪论
1.1、 研究背景。
随着互联网技术发展至今，给用户带来极大便利的同时数据量也呈指数型递增，集中式数据库系统已经无法满足 TB 级增长的用户需求，更多用户选择了分布式数据库系统。分布式数据库系统的可扩展性能够通过大量廉价服务器提高性能，遍布各地的节点也能让用户访问更加快速，延迟更低，但也由于数据需要复制存储在多个节点中并在多个节点中执行事务操作，分布式数据库系统的复杂性远远超过了集中式数据库系统。即使存在诸如 Raft[1]、Paxos[2]等一致性协议确保数据一致性，副本备份[3][4]、领导者选举[5]、异地多活等容错性协议[6]确保分布式数据库系统理论上遇到故障时也能正常提供服务，但在实际应用过程中设计者难以实现完善的容错机制，不能完全保证分布式数据库系统的容错机制在真正发生故障问题时能够生效。例如亚马逊旗下的网络云服务（AWS）在 2019 年 8 月北弗吉尼亚的数据中心由于市电故障出现问题，同时亚马逊的备份措施没能成功保障该数据中心继续服务，结果导致部分亚马逊的弹性计算云（EC2）失效，损害了用户利益。其他使用较为广泛的分布式数据库系统，如 Cassandra[7]，Hbase[8]，Hadoop Distributed File System[9]，Zookeeper[10]它们为了确保用户更好的使用体验，都经过了完整的单元测试、功能测试、性能测试等必要测试流程。尽管如此我们依旧能在其开发页面上发现很多由于各种各样软硬件故障所引起的 bug，其中还存在影响整个系统导致停止服务的灾难性故障[11]。
因此对于分布式数据库系统[12][13]，其架构的复杂性导致了软硬件故障的发生是无可避免的[14][15]。这需要专门针对故障问题的测试工作来验证其容错能力，提高分布式数据库系统的可靠性和鲁棒性。传统测试工作更加注重于分布式数据库系统的性能和功能测试，较少或没能够完备考虑到系统异常状态的正确处理和容错机制。为了能够完善分布式数据库系统对于故障问题的容错机制并及时发现故障问题发生时系统的薄弱点，在测试过程中需要主动引发实际应用过程中可能出现的各类故障问题，诸如网络中断、丢包，节点宕机[16][17]等等，验证分布式数据库系统是否能在故障情况下提供正常服务，而这也就是故障注入测试的意义。
除此之外，研究表明[18]大部分分布式系统的故障问题都是通过多个事件以不同寻常的顺序发生导致系统逐渐转入不正常的运行状态，最后导致系统出现错误。分布式数据系统中事件组合情况非常繁多，过于庞大的状态空间导致遍历所有事件组合情况需要耗费测试人员大量时间和精力。因此在不影响测试效果的情况下有效减少事件组合数目也是故障注入测试值得考虑的问题。本文结合实际生产中的测试工作进行了相关故障注入测试工具的研究。
1.2. 研究工作。
分布式数据库系统的测试工作是繁重且持续性的，系统只要还有用户使用测试工作就不能停止，本文的研究工作就是为了更好地测试分布式数据库系统。对于系统的性能测试和功能测试往往都有固定的测试基准，这类模板可以大幅度减少测试工作量，但是故障注入测试目的是发现系统内部不易发现，潜在的复合型问题不能套用固定的测试方案，这需要测试人员对目标系统有非常深刻的理解，能够对系统的薄弱之处针对性地设计测试案例，验证系统的不足之处。相关测试案例编写需要根据系统的当前状态调整测试案例，这不仅耗费了大量测试人员的精力，更大幅度增加了测试过程所花费的时间。类似的测试工作更是依赖于测试人员编写的测试用例，如果测试人员对目标系统的了解不够全面，测试用例不能覆盖大部分系统薄弱点，即使通过测试也不能确保系统的可靠性。因此本文在深入研究了分布式系统中各种类型的故障问题分析和国内外现有的各类故障注入测试方法，并结合实际测试工作中遇到的问题设计了一个故障注入测试工具AFTest。它能够较全面的检查分布式数据库的容错性，减少测试工作量帮助测试人员更好地进行故障注入测试。本文主要的贡献在于：
1. 轻量级的任务调度设计：同时支持手动提交测试案例和自动遍历已有情况下的事件组合情况。测试人员可以通过前端界面实时查询测试进度，历史记录以及被测试系统的当前状态。后端任务调度程序能够定时生成测试案例并根据案例生成执行脚本，然后分配指定的工作线程执行测试并记录相应日志信息和测试过程中系统状态变化。
2. 实现了一个故障注入框架：通过编码模拟实现实际应用过程中常见的多种软硬件故障问题以及 Cedar 特有的系统操作。模块化故障注入框架，便于嵌入测试工具中使用。
3. 自动生成测试案例：深度遍历所有故障组合事件，避免繁琐的测试案例编写，更高效地进行分布式数据库系统的故障注入测试。
4. 减少事件组合空间冗余问题：根据测试案例中事件之间的特点，分析出导致相同测试结果的组合情况，避免测试冗余案例以及减少不必要事件发生顺序的重新排序，以此缩小事件组合空间加快测试速度。
本文在开源的分布式数据库系统 Cedar 上实现了上述故障注入测试工具AFTest。在实际应用中 AFTest 能够有效减少测试耗费的时间，更加快速地发现故障问题以及目标系统 Cedar 中潜在的复合型 bug。希望本文能为开发分布式数据库系统测试工具的研究者提供经验和参考。
【由于本篇文章为硕士论文，如需全文请点击底部下载全文链接】
1.3 文章结构
第二章 背景知识与相关工作
2.1 基本概念
2.1.1 容错性
2.1.2 故障注入测试
2.2 测试方法
2.2.1 Chaos Engineering
2.2.2 Jepsen
2.3 测试案例的构建
2.3.1 LDFI
2.3.2 模型检查
2.4 本章小结
第三章 目标系统架构和设计
3.1 Cedar 架构介绍
3.2 高可用设计
3.2.1 定时合并
3.2.2 更新节点的容错机制
3.3 故障问题
3.4 本章小结
第四章 测试任务调度
4.1 架构与实现
4.2 各组件功能设计与实现
4.2.1 Tracker 功能与实现
4.2.2 Worker 功能与实现
4.2.3 Schedule 功能与实现
4.2.4 Reporter 功能与实现
4.3 本章小结
第五章 故障注入框架
5.1 功能需求
5.2 架构设计与介绍
5.3 模拟故障类型
5.4 实验结果与分析
5.5 本章小结
第六章 消除冗余案例
6.1 问题描述
6.2 状态对称性
6.3 事件独立性
6.4 并行重排
6.5 实验结果与分析
6.6 本章小结
第七章 总结
分布式数据库系统的可扩展性能够通过大量廉价服务器提高性能并在多个地方部署节点降低用户访问的延迟，但也由于数据需要在多个节点中存储，事务操作涉及多个节点间一致性问题，相比集中式数据库分布式数据库系统的复杂性极大地上升。在实际应用过程中，分布式特性使得整个数据库系统无法避免故障问题的发生，即使理论上存在各类容错性协议保障分布式数据库系统在遭遇故障问题时能够及时恢复正常服务，但设计者不能够保证实际应用过程中容错机制的完备性和实现过程的正确性。因此为了提升分布式数据库系统的可靠性和正确性我们需要主动触发实际应用过程中可能发生的问题，通过故障注入测试验证数据库系统内部是否存在 bug。本文根据相关故障注入测试研究和实际测试经验，针对开源分布式数据库系统 Cedar 设计并实现了故障注入测试工具 AFTest。
本文首先从故障注入测试的基本概念出发，介绍了容错机制是如何保障分布式数据库面对故障问题时能够采取补救措施，并分析了分布式数据库中出现频率较高的几类软硬件故障问题，强调了故障注入测试的必要性。接着介绍了国内外较为流行的故障注入测试方法 Chaos Engineering 和 Jepsen 以及两者的优缺点。
除此之外，我们还介绍了构建故障注入测试案例的方法，主要分为随机式和启发式方法，并介绍了 LDFI 和模型检查这两种较为有代表性的案例构造方法。其次介绍 AFTest 所针对目标系统 Cedar 的整体架构以及 Cedar 内部为了提升可靠性和性能所制定的高可用机制。在分析了 Cedar 在实际应用过程中曾经出现的故障问题后针对这些问题进行测试能够更加完善 Cedar。
然后本文提出了故障注入测试工具 AFTest 的整体架构和组成。主要分成三个部分，测试任务调度、故障注入框架以及消除冗余案例的方法。其中测试任务调度包含了 AFTest 是如何进行测试案例的生成，分配，运行以及收集相关测试日志和系统运行产生的信息。主体可以分为前端用户界面和后端具体功能实现部分，前者负责启停测试和查询测试进度，后者通过 Tracker、Schedule、Worker、Reporter 等组件实现具体测试流程。
故障注入框架主要针对分布式数据库系统中常见问题和 Cedar 的特点提供模拟故障问题发生的功能。通过实验验证了故障注入框架能有效模拟产生各类故障问题，而且遍历所有故障事件组合能发现 Cedar 内部潜在的复合型问题。
最后提出了如何消除完全遍历故障事件组合引起的冗余测试案例。根据系统的状态独立性，能够减少导致相同测试结果的冗余事件组合；分析故障事件之间的独立性能够发现部分事件发生先后顺序的改变对结果没有任何的影响，减少事件组合不必要的重新排序。并通过实验验证了 AFTest 相比 DFS 和随机式的方法能有效减少不必要的冗余案例且更快速地发现系统内部潜在的 bug。
参考文献
