Improving LSM‐trie performance by parallel search. (3rd August 2020)

• Record Type: Journal Article
• Authors: Cheng, Wen; Guo, Tao; Zeng, Lingfang; Wang, Yang; Nagel, Lars; Süß, Tim; Brinkmann, André
• Is Part Of: Software, practice & experience. Volume 50:Number 10(2020)
• Page Start: 1952
• Page End: 1965
• Publication Date: 2020-08-03
• Subjects: key‐value storage -- LSM‐tree -- parallel search; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2875
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: LSM‐trie‐based key‐value (KV) store is often used to manage an ultralarge dataset in reality by introducing a number of sublevels at each level, its linear growth pattern can fairly reduce the write amplification in store operations. Although this design is effective for the write operation, the last level holds a large proportion of KV items, leading to the extreme imbalance of data distribution. Therefore, to support efficient read, we need to carefully consider this imbalance. On the other hand, to ensure that acquired data is latest, the LSM‐trie needs to search the dataset at different levels one by one, and this search method may take a lot of unnecessary time. When the number of items is ultralarge, the random lookup performance may be poor due to the imbalance data distribution. To address this issue, we improve the read performance of the LSM‐trie by changing its serial search to parallel search, using two threads to simultaneously search at the last level and other levels, respectively. Our experiment results show that the read performance of the LSM‐trie can be improved up to 98.35 % and on average 71.55 % .