Workload-Adaptive Filtering in Storage Engines
Joshua Pan · Proceedings of the 2022 International Conference on Management of Data · 2022
Log-Structured Merge-Tree (LSM-tree) based storage engines power numerous applications from social media to machine learning, networks, and Blockchain. Today, storage engine performance deteriorates as data increases especially for skewed workloads due in a large part to inefficient filters. LSM-tree based storage engines rely on the effectiveness of filters to prune unneeded disk accesses. We present an adaptive filter that remembers frequent false positives to turn them into true negatives for future queries. The filter is tailored for integration in state-of-the-art storage engines, and we compare it against traditional workload agnostic filters. We show that our adaptive filter can provide up to 2x end-to-end throughput improvement.