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

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

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

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

【部分圖文】：

原始LSMT合并示意圖[8]

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

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


本文編號(hào)：3539990