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

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

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

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

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