基于LSM--tree鍵值系統(tǒng)讀性能優(yōu)化.pdf

1、鍵值系統(tǒng)主要用于為數(shù)據(jù)密集型應(yīng)用提供存儲(chǔ)服務(wù)，系統(tǒng)采用的主流架構(gòu)為L(zhǎng)SM-tree。LSM-tree將鍵值對(duì)存儲(chǔ)在固定大小的文件內(nèi)，稱(chēng)這些文件為SSTable，SSTable被進(jìn)一步組織在LSM-tree的分層結(jié)構(gòu)中。系統(tǒng)在執(zhí)行讀操作時(shí)，需要發(fā)出多個(gè)I/O請(qǐng)求對(duì)不同層的SSTable進(jìn)行檢查，直到獲取目標(biāo)鍵值對(duì)，過(guò)多I/O請(qǐng)求導(dǎo)致讀性能較差。為提高讀性能，鍵值系統(tǒng)為每個(gè)SSTable配置一個(gè)布隆過(guò)濾器，但是布隆過(guò)濾器的誤報(bào)同樣會(huì)引發(fā)額外

2、的I/O請(qǐng)求。且現(xiàn)有設(shè)計(jì)對(duì)系統(tǒng)內(nèi)所有布隆過(guò)濾器采用統(tǒng)一設(shè)定，也不能對(duì)布隆過(guò)濾器誤報(bào)率進(jìn)行動(dòng)態(tài)調(diào)整，其統(tǒng)一降低誤報(bào)率的辦法將會(huì)給系統(tǒng)環(huán)境帶來(lái)巨大內(nèi)存開(kāi)銷(xiāo)。
　　為提高讀性能，減少布隆過(guò)濾器技術(shù)的內(nèi)存空間使用量，本文提出彈性布隆過(guò)濾器機(jī)制(Elastic Bloom Filter，ElasticBF)。ElasticBF為每個(gè)SSTable構(gòu)建多個(gè)占用空間小的布隆過(guò)濾器，對(duì)這些小過(guò)濾器進(jìn)行組合可以得到不同誤報(bào)率。ElasticBF根據(jù)

3、各SSTable訪(fǎng)問(wèn)頻率差異，動(dòng)態(tài)的為每個(gè)SSTable加載小過(guò)濾器，實(shí)現(xiàn)了運(yùn)行時(shí)誤報(bào)率彈性可調(diào)節(jié)的彈性布隆過(guò)濾器機(jī)制。為給每個(gè)SSTable加載合適數(shù)量的小過(guò)濾器，我們以最大程度降低布隆過(guò)濾器誤報(bào)引發(fā)的I/O請(qǐng)求為目標(biāo)，基于各SSTable的訪(fǎng)問(wèn)頻率，設(shè)計(jì)了一套完整的過(guò)濾器調(diào)整規(guī)則。并且為了使過(guò)濾器的動(dòng)態(tài)調(diào)整開(kāi)銷(xiāo)較小，我們擴(kuò)展了多級(jí)隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)，使用多級(jí)隊(duì)列對(duì)布隆過(guò)濾器進(jìn)行管理。因此，ElasticBF能夠動(dòng)態(tài)調(diào)節(jié)每個(gè)SSTabl

4、e布隆過(guò)濾器的誤報(bào)率和內(nèi)存使用量，使得其在內(nèi)存使用總量保持不變情況下，大大減少（實(shí)驗(yàn)中最高可達(dá)67％）讀操作中因布隆過(guò)濾器誤報(bào)引發(fā)的I/O請(qǐng)求，從而提高讀性能。我們?cè)贚evelDB的基礎(chǔ)上實(shí)現(xiàn)了ElasticBF，并在服務(wù)器上進(jìn)行了性能測(cè)試。實(shí)驗(yàn)結(jié)果顯示，ElasticBF讀吞吐量最高是LevelDB的2.24倍，且基本沒(méi)有對(duì)寫(xiě)性能造成損失。
　　在ElasticBF集成到系統(tǒng)的過(guò)程中，我們進(jìn)一步研究了小過(guò)濾器的配置方案，以提高系