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

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

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

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

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