近年來,由于非結(jié)構(gòu)化數(shù)據(jù)比例的不斷提升以及數(shù)據(jù)密集型應(yīng)用場景的逐漸增加,越來越多的企業(yè)采用KV數(shù)據(jù)庫來支撐其上層應(yīng)用的數(shù)據(jù)存儲和訪問服務(wù)。但是隨著數(shù)據(jù)量和用戶訪問量的不斷增長,KV數(shù)據(jù)庫也面臨著來自性能方面的考驗。本文主要研究了基于LSM-tree的KV數(shù)據(jù)庫系統(tǒng)中讀寫性能優(yōu)化問題,具體包括減少系統(tǒng)的寫放大來提升系統(tǒng)的寫性能,減少布隆過濾器的誤報率來提升系統(tǒng)的讀性能以及針對數(shù)據(jù)頻繁更新場景進(jìn)行相關(guān)的優(yōu)化。本文主要研究內(nèi)容與貢獻(xiàn)如下:1)基于LSM-tree的KV數(shù)據(jù)庫寫性能優(yōu)化由于數(shù)據(jù)量以及寫密集型應(yīng)用場景的逐漸增多,越來越多的企業(yè)選擇基于LSM-tree的KV數(shù)據(jù)庫作為底層的存儲引擎。盡管LSM-tree具有出色的寫性能,但是面對日益增加的用戶寫請求,系統(tǒng)仍然需要不斷提升自身的寫性能。LSM-tree會定期對外存中的數(shù)據(jù)進(jìn)行排序整理,而這一操作會帶來嚴(yán)重的寫放大問題。一方面,寫放大問題會造成系統(tǒng)整體吞吐量的下降;另一方面,當(dāng)外存使用SSD時,嚴(yán)重的寫放大會大幅降低其使用壽命,進(jìn)而會影響系統(tǒng)的可靠性并帶來高昂的存儲開銷。因此減少寫放大可以節(jié)約出更多的I/O資源去服務(wù)用戶請求,并且還可以... 

【文章來源】：中國科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

【文章頁數(shù)】：101 頁

【學(xué)位級別】：博士

【部分圖文】：

圖１．１研宄內(nèi)容關(guān)系圖??

傳統(tǒng)的ＫＶ?jǐn)?shù)據(jù)庫，例如ＢｅｒｋｅｌｅｙＤＢ［４６］，往往采用Ｂ－ｔｒｅｅ來存儲和管理數(shù)??據(jù)。Ｂ－ｔｒｅｅ中的節(jié)點大小通常和外存的存儲單元大小相匹配。Ｂ－ｔｒｅｅ的節(jié)點可以??分為內(nèi)部節(jié)點和葉子節(jié)點兩個部分，如圖２．１所示。內(nèi)部節(jié)點用來存放索引信息，??而葉子節(jié)點存儲真正的數(shù)據(jù)（即Ｋｅｙ－Ｖａｌｕｅ對）。數(shù)據(jù)按照Ｋｅｙ的大小順序存放??在葉子節(jié)點中，葉子節(jié)點的位置以及葉子節(jié)點存儲的Ｋｅｙ的范圍信息都被保存??在內(nèi)部節(jié)點中。所以在查詢一個指定Ｋｅｙ對應(yīng)的Ｖａｌｕｅ值的時候，我們需要從??Ｂ－ｔｒｅｅ的根節(jié)點出發(fā)，自上而下進(jìn)行搜索，直至讀取到葉子節(jié)點。例如，在圖２．１中??查詢Ｋｅｙ＝７８對應(yīng)的Ｖａｌｕｅ值時，Ｂ－ｔｒｅｅ根據(jù)Ｋｅｙ值從根節(jié)點出發(fā)并通過索引信??息確定數(shù)據(jù)存儲的葉子節(jié)點。系統(tǒng)隨后將葉子節(jié)點讀入內(nèi)存，然后在內(nèi)存中查找??指定的Ｋｅｙ－Ｖａｌｕｅ對。因為在葉子節(jié)點內(nèi)部數(shù)據(jù)是按照Ｋｅｙ的大小進(jìn)行排布的，??所以在葉子節(jié)點中對指定的Ｋｅｙ使用二分查找。如果在葉子節(jié)點中找到需要查??詢的Ｋｅｙ時，系統(tǒng)會返回對應(yīng)的Ｖａｌｕｅ值，如果沒有找到則返回值為空。內(nèi)部節(jié)??點占用的存儲空間相對較小

?ｅｘｔｅｒｎａｌ?Ｓｔｏｒａｇｅ??｜?１?２?１?１?９?１０?ｉＲＴ?１８?１９?ｉｎ＾ｌｌ?６９?７８?９２?Ｈ?１０１?１０３?２３４１??圖２．１?Ｂ－ｔｒｅｅ結(jié)構(gòu)圖??傳統(tǒng)的ＫＶ?jǐn)?shù)據(jù)庫，例如ＢｅｒｋｅｌｅｙＤＢ［４６］，往往采用Ｂ－ｔｒｅｅ來存儲和管理數(shù)??據(jù)。Ｂ－ｔｒｅｅ中的節(jié)點大小通常和外存的存儲單元大小相匹配。Ｂ－ｔｒｅｅ的節(jié)點可以??分為內(nèi)部節(jié)點和葉子節(jié)點兩個部分，如圖２．１所示。內(nèi)部節(jié)點用來存放索引信息，??而葉子節(jié)點存儲真正的數(shù)據(jù)（即Ｋｅｙ－Ｖａｌｕｅ對）。數(shù)據(jù)按照Ｋｅｙ的大小順序存放??在葉子節(jié)點中，葉子節(jié)點的位置以及葉子節(jié)點存儲的Ｋｅｙ的范圍信息都被保存??在內(nèi)部節(jié)點中。所以在查詢一個指定Ｋｅｙ對應(yīng)的Ｖａｌｕｅ值的時候，我們需要從??Ｂ－ｔｒｅｅ的根節(jié)點出發(fā)，自上而下進(jìn)行搜索，直至讀取到葉子節(jié)點。例如，在圖２．１中??查詢Ｋｅｙ＝７８對應(yīng)的Ｖａｌｕｅ值時，Ｂ－ｔｒｅｅ根據(jù)Ｋｅｙ值從根節(jié)點出發(fā)并通過索引信??息確定數(shù)據(jù)存儲的葉子節(jié)點。系統(tǒng)隨后將葉子節(jié)點讀入內(nèi)存，然后在內(nèi)存中查找??指定的Ｋｅｙ－Ｖａｌｕｅ對。因為在葉子節(jié)點內(nèi)部數(shù)據(jù)是按照Ｋｅｙ的大小進(jìn)行排布的


本文編號：3353258