Tidal-tree-Mem: Towards Read-Intensive Key-Value Stores with Tidal Structure Based on LSM-Tree

The log-structured merge-tree (LSM-tree) based key-value store has been widely adopted by many large-scale data storage applications for its excellent write performance. However, such write performance gains mainly come from scarifying read performance due to the leveled and log-structured intrinsic characteristics of the LSM-tree. Therefore, the critical challenge of the existing LSM-tree is how to improve the read efficiency by reducing read amplification. This paper for the first time proposes Tidal-tree-Mem, a novel data structure where data flows inside the LSM-tree like Tidal waves. First, a floating strategy is proposed to allow frequently accessed files at the bottom of the LSM-tree to move to higher positions, reducing read amplification. Second, a stretching strategy is proposed to vary the shape of the LSM-tree to adapt to workloads with different characteristics. To evaluate the performance of Tidal-tree-Mem, we conduct a series of experiments using standard benchmarks from YCSB. The experimental results show that Tidal-tree-Mem can effectively reduce read amplification and the overall latency by over 71.94% and 47.34%, respectively, compared with representative schemes.