基于日志结构合并树的键值存储系统优化研究

　　第1 章 绪论… ………………………………………………………………… 1
　　1.1 研究背景与意义… ……………………………………………………… 1
　　1.2 键值存储系统面临的挑战… …………………………………………… 2
　　1.2.1 键值存储与新硬件的适配优化… ………………………………… 2
　　1.2.2 键值存储结构的自适应优化… …………………………………… 3
　　1.2.3 基于机器学习的键值存储自动调优… …………………………… 3
　　1.3 本书的主要研究工作… ………………………………………………… 3
　　1.4 本书的组织结构… ……………………………………………………… 7
　　第2 章 键值存储系统相关背景… …………………………………………… 8
　　2.1 基于LSM-tree 的键值存储系统介绍… ………………………………… 8
　　2.1.1 LSM-tree 键值存储系统的基本概念… …………………………… 9
　　2.1.2 LSM-tree 键值存储系统存在的性能问题… …………………… 10
　　2.2 面向新硬件的键值存储系统结构优化… …………………………… 13
　　2.2.1 新型高密度磁盘的LSM-tree 键值存储优化… ………………… 15
　　2.2.2 面向固态磁盘SSD 的LSM-tree 键值存储优化… ……………… 17
　　2.2.3 面向非易失性内存的LSM-tree 键值存储优化… ……………… 18
　　2.3 面向动态资源及负载的自适应优化… ……………………………… 23
　　2.4 基于机器学习的数据库系统性能自动优化… ……………………… 24
　　第3 章 面向新型存储硬件的LSM-tree 合并机制优化…………………… 27
　　3.1 引言… ………………………………………………………………… 27
　　3.2 问题描述… …………………………………………………………… 28
　　3.2.1 LSM-tree 的写放大问题… ……………………………………… 29
　　3.2.2 LSM-tree 性能抖动延迟问题… ………………………………… 30
　　3.2.3 相关研究… ……………………………………………………… 31
　　3.3 底层驱动合并机制的设计与实现… ………………………………… 32
　　3.3.1 底层驱动合并机制整体设计… ………………………………… 33
　　3.3.2 底层驱动合并机制的实现… …………………………………… 38
　　基于日志结构合并树的键值存储系统优化研究
　　3.4 实验评估… …………………………………………………………… 42
　　3.4.1 实验测试环境配置… …………………………………………… 42
　　3.4.2 吞吐性能测试… ………………………………………………… 43
　　3.4.3 合并机制空间开销性能测试… ………………………………… 46
　　3.4.4 降低延迟影响测试… …………………………………………… 48
　　3.5 本章小结… …………………………………………………………… 49
　　第4 章 面向资源负载自适应LSM-tree 结构的键值存储优化…………… 51
　　4.1 引言… ………………………………………………………………… 51
　　4.2 问题描述… …………………………………………………………… 53
　　4.2.1 LSM-tree 形态对系统性能的影响… …………………………… 54
　　4.2.2 LSM-tree 合并机制对系统性能的影响… ……………………… 55
　　4.2.3 键值存储的自适应模型… ……………………………………… 56
　　4.2.4 相关研究… ……………………………………………………… 57
　　4.3 自适应LSM-tree 键值存储系统ALDC-DB 的设计与实现… ……… 58
　　4.3.1 自适应LSM-tree 结构设计… …………………………………… 58
　　4.3.2 自适应LSM-tree 结构实现… …………………………………… 61
　　4.3.3 自适应合并机制实现… ………………………………………… 64
　　4.4 实验评估… …………………………………………………………… 70
　　4.4.1 实验环境配置… ………………………………………………… 70
　　4.4.2 吞吐性能评估… ………………………………………………… 71
　　4.4.3 延迟影响性能评估… …………………………………………… 75
　　4.4.4 内部相关结构性能评估… ……………………………………… 76
　　4.5 本章小结… …………………………………………………………… 80
　　第5 章 基于相关性的LSM-tree 键值存储自动调优……………………… 81
　　5.1 引言… ………………………………………………………………… 81
　　5.2 问题描述… …………………………………………………………… 83
　　5.2.1 自动调优的时间开销… ………………………………………… 84
　　5.2.2 键值存储的结构性优化… ……………………………………… 84
　　5.2.3 相关研究… ……………………………………………………… 85
　　5.3 基于相关性的自动调优系统XTuning 的设计与实现… …………… 87
　　5.3.1 XTuning 整体架构设计…………………………………………… 87
　　5.3.2 内部专家规则模块实现… ……………………………………… 88
　　5.3.3 外部专家规则模块实现… ……………………………………… 92
　　5.3.4 基于专家规则的调优算法PEKT………………………………… 95
　　5.3.5 LSM-tree 结构性优化的实现… ………………………………… 97
　　5.4 实验评估… …………………………………………………………… 99
　　5.4.1 实验环境设置… ………………………………………………… 100
　　5.4.2 训练时间开销评测… …………………………………………… 100
　　5.4.3 吞吐性能评测… ………………………………………………… 101
　　5.4.4 延迟影响评测… ………………………………………………… 102
　　5.4.5 键值存储系统内部I/O 评测分析………………………………… 103
　　5.5 本章小结… …………………………………………………………… 105
　　第6 章 基于LSM-tree 键值存储的知识图谱系统优化…………………… 107
　　6.1 引言… ………………………………………………………………… 107
　　6.2 问题描述… …………………………………………………………… 108
　　6.2.1 邻域查询性能… ………………………………………………… 108
　　6.2.2 基于NVM 的图谱加速优化……………………………………… 108
　　6.2.3 相关研究… ……………………………………………………… 109
　　6.3 基于LSM-tree 键值存储系统的知识图谱查询加速系统… ………… 112
　　6.3.1 提升邻域查询性能… …………………………………………… 112
　　6.3.2 面向知识图谱应用的键值存储引擎优化… …………………… 113
　　6.3.3 面向分布式知识图谱的Raft 优化… …………………………… 115
　　6.4 实验评估… …………………………………………………………… 116
　　6.4.1 实验环境设置… ………………………………………………… 116
　　6.4.2 吞吐性能测试… ………………………………………………… 117
　　6.4.3 平均延迟性能测试… …………………………………………… 118
　　6.4.4 尾延迟性能测试… ……………………………………………… 119
　　基于日志结构合并树的键值存储系统优化研究
　　6.4.5 可扩展性测试… ………………………………………………… 120
　　6.5 本章小结… …………………………………………………………… 121
　　第7 章 总结与展望… ……………………………………………………… 123
　　7.1 主要研究内容与成果贡献… ………………………………………… 123
　　7.2 未来的研究计划… …………………………………………………… 126
　　参考文献………………………………………………………………………… 127

　　柴艳峰，太原科技大学讲师，毕业于中国人民大学计算机应用技术专业，工学博士，主要研究方向为数据库、新型存储硬件和键值存储等系统的设计与优化研究。

　　本书主要介绍基于日志结构合并树LSM-tree 的键值存储系统的性能优化，具体包括：面向新型存储硬件的键值存储结构优化，面向资源负载自适应LSM-tree 结构的键值存储优化，基于强化学习相关性的LSM-tree 键值存储自动调优，面向知识图谱应用的LSM-tree 键值存储优化。本书可使读者对键值存储结构引擎有初步了解，并且掌握LSM-tree 存储引擎的实现和优化思路。