基于日志結(jié)構(gòu)合并樹的鍵值存儲系統(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 鍵值存儲結(jié)構(gòu)的自適應(yīng)優(yōu)化… …………………………………… 3
1.2.3 基于機器學(xué)習(xí)的鍵值存儲自動調(diào)優(yōu)… …………………………… 3
1.3 本書的主要研究工作… ………………………………………………… 3
1.4 本書的組織結(jié)構(gòu)… ……………………………………………………… 7
第2 章 鍵值存儲系統(tǒng)相關(guān)背景… …………………………………………… 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)結(jié)構(gòu)優(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)資源及負(fù)載的自適應(yīng)優(yōu)化… ……………………………… 23
2.4 基于機器學(xué)習(xí)的數(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 相關(guān)研究… ……………………………………………………… 31
3.3 底層驅(qū)動合并機制的設(shè)計與實現(xiàn)… ………………………………… 32
3.3.1 底層驅(qū)動合并機制整體設(shè)計… ………………………………… 33
3.3.2 底層驅(qū)動合并機制的實現(xiàn)… …………………………………… 38
基于日志結(jié)構(gòu)合并樹的鍵值存儲系統(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 本章小結(jié)… …………………………………………………………… 49
第4 章 面向資源負(fù)載自適應(yīng)LSM-tree 結(jié)構(gòu)的鍵值存儲優(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 鍵值存儲的自適應(yīng)模型… ……………………………………… 56
4.2.4 相關(guān)研究… ……………………………………………………… 57
4.3 自適應(yīng)LSM-tree 鍵值存儲系統(tǒng)ALDC-DB 的設(shè)計與實現(xiàn)… ……… 58
4.3.1 自適應(yīng)LSM-tree 結(jié)構(gòu)設(shè)計… …………………………………… 58
4.3.2 自適應(yīng)LSM-tree 結(jié)構(gòu)實現(xiàn)… …………………………………… 61
4.3.3 自適應(yīng)合并機制實現(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)部相關(guān)結(jié)構(gòu)性能評估… ……………………………………… 76
4.5 本章小結(jié)… …………………………………………………………… 80
第5 章 基于相關(guān)性的LSM-tree 鍵值存儲自動調(diào)優(yōu)……………………… 81
5.1 引言… ………………………………………………………………… 81
5.2 問題描述… …………………………………………………………… 83
5.2.1 自動調(diào)優(yōu)的時間開銷… ………………………………………… 84
5.2.2 鍵值存儲的結(jié)構(gòu)性優(yōu)化… ……………………………………… 84
5.2.3 相關(guān)研究… ……………………………………………………… 85
5.3 基于相關(guān)性的自動調(diào)優(yōu)系統(tǒng)XTuning 的設(shè)計與實現(xiàn)… …………… 87
5.3.1 XTuning 整體架構(gòu)設(shè)計…………………………………………… 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 結(jié)構(gòu)性優(yōu)化的實現(xiàn)… ………………………………… 97
5.4 實驗評估… …………………………………………………………… 99
5.4.1 實驗環(huán)境設(shè)置… ………………………………………………… 100
5.4.2 訓(xùn)練時間開銷評測… …………………………………………… 100
5.4.3 吞吐性能評測… ………………………………………………… 101
5.4.4 延遲影響評測… ………………………………………………… 102
5.4.5 鍵值存儲系統(tǒng)內(nèi)部I/O 評測分析………………………………… 103
5.5 本章小結(jié)… …………………………………………………………… 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 相關(guān)研究… ……………………………………………………… 109
6.3 基于LSM-tree 鍵值存儲系統(tǒng)的知識圖譜查詢加速系統(tǒng)… ………… 112
6.3.1 提升鄰域查詢性能… …………………………………………… 112
6.3.2 面向知識圖譜應(yīng)用的鍵值存儲引擎優(yōu)化… …………………… 113
6.3.3 面向分布式知識圖譜的Raft 優(yōu)化… …………………………… 115
6.4 實驗評估… …………………………………………………………… 116
6.4.1 實驗環(huán)境設(shè)置… ………………………………………………… 116
6.4.2 吞吐性能測試… ………………………………………………… 117
6.4.3 平均延遲性能測試… …………………………………………… 118
6.4.4 尾延遲性能測試… ……………………………………………… 119
基于日志結(jié)構(gòu)合并樹的鍵值存儲系統(tǒng)優(yōu)化研究
6.4.5 可擴(kuò)展性測試… ………………………………………………… 120
6.5 本章小結(jié)… …………………………………………………………… 121
第7 章 總結(jié)與展望… ……………………………………………………… 123
7.1 主要研究內(nèi)容與成果貢獻(xiàn)… ………………………………………… 123
7.2 未來的研究計劃… …………………………………………………… 126
參考文獻(xiàn)………………………………………………………………………… 127