基于日志結構合并樹的鍵值存儲系統(tǒng)優(yōu)化研究

第1 章 緒論… ………………………………………………………………… 1
1.1 研究背景與意義… ……………………………………………………… 1
1.2 鍵值存儲系統(tǒng)面臨的挑戰(zhàn)… …………………………………………… 2
1.2.1 鍵值存儲與新硬件的適配優(yōu)化… ………………………………… 2
1.2.2 鍵值存儲結構的自適應優(yōu)化… …………………………………… 3
1.2.3 基于機器學習的鍵值存儲自動調(diào)優(yōu)… …………………………… 3
1.3 本書的主要研究工作… ………………………………………………… 3
1.4 本書的組織結構… ……………………………………………………… 7
第2 章 鍵值存儲系統(tǒng)相關背景… …………………………………………… 8
2.1 基于LSM-tree 的鍵值存儲系統(tǒng)介紹… ………………………………… 8
2.1.1 LSM-tree 鍵值存儲系統(tǒng)的基本概念… …………………………… 9
2.1.2 LSM-tree 鍵值存儲系統(tǒng)存在的性能問題… …………………… 10
2.2 面向新硬件的鍵值存儲系統(tǒng)結構優(yōu)化… …………………………… 13
2.2.1 新型高密度磁盤的LSM-tree 鍵值存儲優(yōu)化… ………………… 15
2.2.2 面向固態(tài)磁盤SSD 的LSM-tree 鍵值存儲優(yōu)化… ……………… 17
2.2.3 面向非易失性內(nèi)存的LSM-tree 鍵值存儲優(yōu)化… ……………… 18
2.3 面向動態(tài)資源及負載的自適應優(yōu)化… ……………………………… 23
2.4 基于機器學習的數(shù)據(jù)庫系統(tǒng)性能自動優(yōu)化… ……………………… 24
第3 章 面向新型存儲硬件的LSM-tree 合并機制優(yōu)化…………………… 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 底層驅(qū)動合并機制的設計與實現(xiàn)… ………………………………… 32
3.3.1 底層驅(qū)動合并機制整體設計… ………………………………… 33
3.3.2 底層驅(qū)動合并機制的實現(xiàn)… …………………………………… 38
基于日志結構合并樹的鍵值存儲系統(tǒng)優(yōu)化研究
3.4 實驗評估… …………………………………………………………… 42
3.4.1 實驗測試環(huán)境配置… …………………………………………… 42
3.4.2 吞吐性能測試… ………………………………………………… 43
3.4.3 合并機制空間開銷性能測試… ………………………………… 46
3.4.4 降低延遲影響測試… …………………………………………… 48
3.5 本章小結… …………………………………………………………… 49
第4 章 面向資源負載自適應LSM-tree 結構的鍵值存儲優(yōu)化…………… 51
4.1 引言… ………………………………………………………………… 51
4.2 問題描述… …………………………………………………………… 53
4.2.1 LSM-tree 形態(tài)對系統(tǒng)性能的影響… …………………………… 54
4.2.2 LSM-tree 合并機制對系統(tǒng)性能的影響… ……………………… 55
4.2.3 鍵值存儲的自適應模型… ……………………………………… 56
4.2.4 相關研究… ……………………………………………………… 57
4.3 自適應LSM-tree 鍵值存儲系統(tǒng)ALDC-DB 的設計與實現(xiàn)… ……… 58
4.3.1 自適應LSM-tree 結構設計… …………………………………… 58
4.3.2 自適應LSM-tree 結構實現(xiàn)… …………………………………… 61
4.3.3 自適應合并機制實現(xiàn)… ………………………………………… 64
4.4 實驗評估… …………………………………………………………… 70
4.4.1 實驗環(huán)境配置… ………………………………………………… 70
4.4.2 吞吐性能評估… ………………………………………………… 71
4.4.3 延遲影響性能評估… …………………………………………… 75
4.4.4 內(nèi)部相關結構性能評估… ……………………………………… 76
4.5 本章小結… …………………………………………………………… 80
第5 章 基于相關性的LSM-tree 鍵值存儲自動調(diào)優(yōu)……………………… 81
5.1 引言… ………………………………………………………………… 81
5.2 問題描述… …………………………………………………………… 83
5.2.1 自動調(diào)優(yōu)的時間開銷… ………………………………………… 84
5.2.2 鍵值存儲的結構性優(yōu)化… ……………………………………… 84
5.2.3 相關研究… ……………………………………………………… 85
5.3 基于相關性的自動調(diào)優(yōu)系統(tǒng)XTuning 的設計與實現(xiàn)… …………… 87
5.3.1 XTuning 整體架構設計…………………………………………… 87
5.3.2 內(nèi)部專家規(guī)則模塊實現(xiàn)… ……………………………………… 88
5.3.3 外部專家規(guī)則模塊實現(xiàn)… ……………………………………… 92
5.3.4 基于專家規(guī)則的調(diào)優(yōu)算法PEKT………………………………… 95
5.3.5 LSM-tree 結構性優(yōu)化的實現(xiàn)… ………………………………… 97
5.4 實驗評估… …………………………………………………………… 99
5.4.1 實驗環(huán)境設置… ………………………………………………… 100
5.4.2 訓練時間開銷評測… …………………………………………… 100
5.4.3 吞吐性能評測… ………………………………………………… 101
5.4.4 延遲影響評測… ………………………………………………… 102
5.4.5 鍵值存儲系統(tǒng)內(nèi)部I/O 評測分析………………………………… 103
5.5 本章小結… …………………………………………………………… 105
第6 章 基于LSM-tree 鍵值存儲的知識圖譜系統(tǒng)優(yōu)化…………………… 107
6.1 引言… ………………………………………………………………… 107
6.2 問題描述… …………………………………………………………… 108
6.2.1 鄰域查詢性能… ………………………………………………… 108
6.2.2 基于NVM 的圖譜加速優(yōu)化……………………………………… 108
6.2.3 相關研究… ……………………………………………………… 109
6.3 基于LSM-tree 鍵值存儲系統(tǒng)的知識圖譜查詢加速系統(tǒng)… ………… 112
6.3.1 提升鄰域查詢性能… …………………………………………… 112
6.3.2 面向知識圖譜應用的鍵值存儲引擎優(yōu)化… …………………… 113
6.3.3 面向分布式知識圖譜的Raft 優(yōu)化… …………………………… 115
6.4 實驗評估… …………………………………………………………… 116
6.4.1 實驗環(huán)境設置… ………………………………………………… 116
6.4.2 吞吐性能測試… ………………………………………………… 117
6.4.3 平均延遲性能測試… …………………………………………… 118
6.4.4 尾延遲性能測試… ……………………………………………… 119
基于日志結構合并樹的鍵值存儲系統(tǒng)優(yōu)化研究
6.4.5 可擴展性測試… ………………………………………………… 120
6.5 本章小結… …………………………………………………………… 121
第7 章 總結與展望… ……………………………………………………… 123
7.1 主要研究內(nèi)容與成果貢獻… ………………………………………… 123
7.2 未來的研究計劃… …………………………………………………… 126
參考文獻………………………………………………………………………… 127