TreeKV: efficient garbage collection and range query for key-value separated LSM-stores

Hao Luan

doi:10.1117/12.3035010

11 July 2024 TreeKV: efficient garbage collection and range query for key-value separated LSM-stores

Hao Luan

Proceedings Volume 13210, Third International Symposium on Computer Applications and Information Systems (ISCAIS 2024); 132101Z (2024) https://doi.org/10.1117/12.3035010
Event: Third International Symposium on Computer Applications and Information Systems (ISCAIS 2023), 2024, Wuhan, China

Abstract

LSM-tree is favored in write-intensive scenarios due to its sequential write feature, but it grapples with read and write amplification issues. A common solution is to store keys and values separately, with the LSM-tree holding only the key and value address, while the value is kept separately. However, this approach presents challenges in range query and garbage collection, necessitating multiple random reads and pointless data rewriting. To address these issues, we introduce TreeKV, a system that uses a specialized B+ tree for value storage, grouping values with adjacent keys together. This reduces random reads during range queries and eliminates unnecessary data rewriting during garbage collection. We also delve into crash recovery and minimal-blocking garbage collection implementation in TreeKV. Our comparison with existing key-value separated stores shows that TreeKV, while maintaining high read-write performance, enhances range query and garbage collection performance.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Hao Luan "TreeKV: efficient garbage collection and range query for key-value separated LSM-stores", Proc. SPIE 13210, Third International Symposium on Computer Applications and Information Systems (ISCAIS 2024), 132101Z (11 July 2024); https://doi.org/10.1117/12.3035010

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available