A Secondary Indexing Mechanism for LSM-based Storage Systems

What is it about?

Log-structured merge trees (LSM-trees) are widely adopted in modern storage systems for superior write performance on block devices. However, they are not adept at handling query operations and struggle to efficiently support secondary indexing, an indispensable technique in database systems. This paper presents Perseid, an efficient secondary indexing for LSM-based storage systems with emerging persistent memory (PM) devices. Besides leveraging the advantages of PM directly, Perseid is specially designed with consideration of the non-unique feature of secondary indexes and consistency among indexes in LSM-based storage systems. Perseid can enable LSM-based storage systems to achieve superior query and write performance.

Featured Image

Why is it important?

Secondary indexing is an indispensable technique in database systems since many real-world query requests are not based on primary keys. Though LSM-trees feature outstanding write performance, they introduce complexity when it comes to secondary indexing. On the other hand, though there is a considerable amount of research on PM-based indexes, they are not specially designed for secondary indexing. This paper revisits secondary indexing in LSM-based storage systems and proposes a more efficient design with persistent memory.