Disco: A Compact Index for LSM-trees

• DOI: 10.1145/3709683
• Publication Date: 2025-02-11T20:45:06Z
• Authors: Wenshao Zhong; Chen Chen; Xingbo Wu; Jakob Eriksson

Many key-value stores and database systems use log-structured merge-trees (LSM-trees) as their storage engines because of excellent write performance. However, the read performance LSM-trees is suboptimal due to overlapping sorted runs. Most existing efforts rely on filters reduce unnecessary I/Os, but fundamentally do not help locate items often become bottleneck system. We identify that lack efficient index root cause subpar in LSM-trees. In this paper, we propose Disco: a compact for Disco indexes all keys an LSM-tree, so query does have search every run LSM-tree. It records key representations minimize number comparisons cache misses I/Os both point range queries. guarantees queries seeks issue at most one I/O underlying runs, achieving efficiency close B + -tree. improves upon REMIX's pioneering multi-run design with additional improve The are cost persisting disk small. Moreover, while traditional LSM-tree has choose more aggressive compaction policy slows down better performance, Disco-indexed can employ write-efficient still good Experimental results show save by up 220% over RocksDB maintaining writes.