鍵值存儲系統(tǒng),由于其簡單的數(shù)據(jù)模型,被廣泛應(yīng)用于社交網(wǎng)絡(luò)、電商、云計算基礎(chǔ)設(shè)施等場景下,是現(xiàn)代存儲系統(tǒng)的重要組成部分。其中比較重要一類系統(tǒng)是基于日志結(jié)構(gòu)合并樹（Log-structured Merge Tree,LSMT）的鍵值存儲系統(tǒng)。這類系統(tǒng)因為有著優(yōu)異的寫入能力,已被廣泛用在密集寫入的場景下。但是基于LSMT的鍵值存儲系統(tǒng),如LevelDB/RocksDB,還是存在著寫放大嚴重的問題,即實際寫入存儲設(shè)備的數(shù)據(jù)量要遠大于用戶請求寫入的數(shù)據(jù)量,浪費I O能力以及加速存儲設(shè)備損耗。學(xué)界也有不少關(guān)于降低寫放大的研究工作,如WiscKey、PebblesDB、LSM-Trie,但是這類工作大多都需要犧牲讀操作的性能。因此本文的首要研究目標是降低該類系統(tǒng)的寫放大。為此,本文提出SilkSt ore,一個寫優(yōu)化的鍵值存儲系統(tǒng),來嘗試解決這個問題。SilkStore的核心創(chuàng)新點在于設(shè)計了一個單層的LSMT結(jié)構(gòu)以及高效的合并策略,降低了由于傳統(tǒng)LS MT的多層設(shè)計以及合并算法導(dǎo)致的對鍵值的重復(fù)寫入。同時本文從理論角度分析了SilkStore相比于其他LSMT設(shè)計的優(yōu)劣勢。除此之外,現(xiàn)有的LSMT設(shè)... 

【文章來源】：浙江大學(xué)浙江省 211工程院校 985工程院校 教育部直屬院校

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

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

【部分圖文】：

原始LSMT合并示意圖[8]

浙江大學(xué)碩士學(xué)位論文第2章相關(guān)工作13圖2-2兩種LSMT合并策略示意圖[18]合并策略代價分析.為了理解兩種策略的優(yōu)缺點，我們可以針對不同合并策略配置下LSMT的讀寫IO次數(shù)做一個分析。為了簡化分析，我們假設(shè)存儲的鍵值對大小固定。我們定義為LSMT兩層之間的大小比例，并且假設(shè)有層。在實際應(yīng)用中，如果數(shù)據(jù)集中唯一鍵的數(shù)量不變，一般是一個固定值。我們采用頁面作為IO單位,記為一個頁面能容納的記錄數(shù)，為內(nèi)存表能容大的最大頁面數(shù)。因此內(nèi)存表能容納條鍵值記錄，第層最多能容納*條鍵值記錄。給定條記錄的數(shù)據(jù)集，則最后一層大約能存儲,-%,條記錄，因為最后一層比前一層大了倍。因此可以近似表示為7.#(0,-%,8。我們定義寫代價為寫入一條記錄的均攤IO代價。對于Leveling來說，每一層需要合并1次，才能填滿，并加入到下一層，因此一條記錄在一層內(nèi)平均情況下需要寫,"次。因為一個頁面含有條記錄，那么一條記錄在Leveling策略下總的寫代價為(,()。對于Tiering來說，多個SSTable在一層只被合并一次之后就被推到下一層去了，所以一條記錄在一層只需要被合并一次。類似的，Tiering策略下一條記錄總的寫代價為(1()。從這里可以看出Tiering的寫代價要比Leveling小T倍，更加適合多寫場景。我們定義讀代價為讀取一條鍵值記錄的IO次數(shù)。對于Leveling來說，讀代價為()；對于Tiering來說，讀代價為()。在實際應(yīng)用過程中，布隆過濾

浙江大學(xué)碩士學(xué)位論文第2章相關(guān)工作15圖2-3Tiering策略下的分區(qū)優(yōu)化[18]Tiering合并策略的分區(qū)優(yōu)化難點在于如何確定組的分區(qū)范圍，好的組分區(qū)應(yīng)該使得每個組大小接近。PebblesDB[12]采用了類似的Tiering合并策略，并且做了分區(qū)優(yōu)化。它提出用類似skip-list[20]基于概率性的思想來從插入的鍵中選擇出組的分區(qū)范圍，以此來達到組之間的數(shù)據(jù)量平衡。進一步的，PebblesDB利用現(xiàn)代SSD的高隨機IO能力,提出了用并行查詢來優(yōu)化范圍查詢，。2.2.4基于新型存儲硬件的LSMT寫放大優(yōu)化研究現(xiàn)狀目前SSD已經(jīng)漸漸成為數(shù)據(jù)中心存儲的主流，隨機讀IO已經(jīng)能趕上順序讀IO的帶寬吞吐，因此產(chǎn)生了一些新的設(shè)計。LSMT盡管在寫放大方面要優(yōu)于B+樹，但是合并策略的不同，寫放大還是會有比較大的差異。學(xué)界也有不少研究嘗試解決LSMT寫放大問題。WiscKey論文指出，一般來說LSMT存儲的值相比于鍵會大很多，并且這些值在合并的過程中需要被反復(fù)的讀取和寫入，因此造成大量的寫放大。WiscKey因此提出了鍵值分離的概念，如圖2-3所示，通過將值存儲在一個單獨的日志文件里，并且對這個日志文件按照鍵進行索引，即存儲<鍵，值在日志文件中的位置>到另外一顆索引用的LSMT中，以完成各類查詢操作，由此來降低寫放大。這樣的好處就是索引LSMT會比較小，寫放大大大降低。這種設(shè)計在查詢效率上也比較出色，因為SSD沒有HDD的尋道時間，并發(fā)隨機查詢基本能夠達到設(shè)備帶寬上限。


本文編號：3539990