{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T16:07:40Z","timestamp":1747152460773,"version":"3.40.5"},"reference-count":30,"publisher":"Wiley","issue":"10","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61472153","61672513","61572377"],"award-info":[{"award-number":["61472153","61672513","61572377"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Summary<\/jats:title><jats:p>LSM\u2010trie\u2010based key\u2010value (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\u2010trie 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\u2010trie by changing its <jats:italic>serial search<\/jats:italic> to <jats:italic>parallel search<\/jats:italic>, 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\u2010trie can be improved up to <jats:styled-content>98.35<jats:italic>%<\/jats:italic><\/jats:styled-content> and on average <jats:styled-content>71.55<jats:italic>%<\/jats:italic><\/jats:styled-content>.<\/jats:p>","DOI":"10.1002\/spe.2875","type":"journal-article","created":{"date-parts":[[2020,8,4]],"date-time":"2020-08-04T04:14:15Z","timestamp":1596514455000},"page":"1952-1965","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improving LSM\u2010trie performance by parallel search"],"prefix":"10.1002","volume":"50","author":[{"given":"Wen","family":"Cheng","sequence":"first","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology  Wuhan China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Guo","sequence":"additional","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology  Wuhan China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lingfang","family":"Zeng","sequence":"additional","affiliation":[{"name":"Wuhan National Laboratory for Optoelectronics Huazhong University of Science and Technology  Wuhan China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9438-6060","authenticated-orcid":false,"given":"Yang","family":"Wang","sequence":"additional","affiliation":[{"name":"Shenzhen Institutes of Advanced Technology Chinese Academy of Sciences  Shenzhen China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Nagel","sequence":"additional","affiliation":[{"name":"Department of Computer Science Loughborough University  Loughborough UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"S\u00fc\u00df","sequence":"additional","affiliation":[{"name":"Department of Computer Science Johannes Gutenberg\u2010University Mainz  Mainz Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Brinkmann","sequence":"additional","affiliation":[{"name":"Department of Computer Science Johannes Gutenberg\u2010University Mainz  Mainz Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"e_1_2_7_2_1","unstructured":"ChangF DeanJ GhemawatS et al. Bigtable: distributed storage system for structured data. Paper presented at: Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI);2006."},{"volume-title":"LevelDB: A Fast and Lightweight Key\/Value Database Library By Google","year":"2013","author":"Dean Jeff","key":"e_1_2_7_3_1"},{"key":"e_1_2_7_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4302-3052-6"},{"key":"e_1_2_7_5_1","doi-asserted-by":"crossref","unstructured":"DebnathB SenguptaS LiJ. SkimpyStash: RAM space skimpy key\u2010value store on flash\u2010based storage. Paper presented at: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD);2011:25\u201036.","DOI":"10.1145\/1989323.1989327"},{"key":"e_1_2_7_6_1","unstructured":"DebnathB SenguptaS LiJ. FlashStore: high throughput persistent key\u2010value store. Paper presented at: Proceedings of the 36th International Conference on Very Large Databases (VLDB);2010."},{"key":"e_1_2_7_7_1","doi-asserted-by":"crossref","unstructured":"DeCandiaG HastorunD JampaniM et al. Dynamo: Amazon's highly available key\u2010value store. Paper presented at: Proceedings of the 21st ACM SIGOPS Symposium on Operating Systems Principles (SOSP);2007:205\u2010220; ACM; Stevenson Washington DC.","DOI":"10.1145\/1323293.1294281"},{"key":"e_1_2_7_8_1","doi-asserted-by":"crossref","unstructured":"ArmstrongTG PonnekantiV BorthakurD CallaghanM. LinkBench: a database benchmark based on the Facebook social graph. Paper presented at: Proceedings of the ACM International Conference on Management of Data (SIGMOD);2013:1185\u20101196; ACM; New York NY.","DOI":"10.1145\/2463676.2465296"},{"volume-title":"Under the Hood: Building and Open\u2010Sourcing RocksDB","year":"2013","author":"Borthakur Dhruba","key":"e_1_2_7_9_1"},{"key":"e_1_2_7_10_1","doi-asserted-by":"crossref","unstructured":"LaiC JiangS YangL et al. Atlas: baidus key\u2010value storage system for cloud data. Paper presented at: Proceedings of the 31st International Conference on Massive Storage Systems and Technology (MSST);2015; Santa Clara California.","DOI":"10.1109\/MSST.2015.7208288"},{"key":"e_1_2_7_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_7_12_1","doi-asserted-by":"crossref","unstructured":"SearsR RamakrishnanR. bLSM: a general purpose log structured merge tree. Paper presented at: Proceedings of the 2012 ACM International Conference on Management of Data (SIGMOD);2012:217\u2010228.","DOI":"10.1145\/2213836.2213862"},{"key":"e_1_2_7_13_1","unstructured":"ShettyP SpillaneR MalpaniR AndrewsB SeysterJ ZadokE. Building workload\u2010independent storage with VT\u2010trees. Paper presented at: Proceedings of the 11th USENIX Symposium on File and Storage Technologies(FAST);2013."},{"volume-title":"A Fork of LevelDB Intended to Meet the Needs of HyperDex While Remaining Compatible with LevelDB","year":"2014","author":"HyperLevelDB","key":"e_1_2_7_14_1"},{"key":"e_1_2_7_15_1","doi-asserted-by":"crossref","unstructured":"Golan\u2010GuetaGuy BortnikovEdward HillelEshcar KeidarIdit. Scaling Concurrent Log\u2010Structured Data Stores. Paper presented at: Proceedings of the 10th European Conference on Computer Systems (EuroSys);2015.","DOI":"10.1145\/2741948.2741973"},{"key":"e_1_2_7_16_1","doi-asserted-by":"crossref","unstructured":"BalmauO GuerraouiR TrigonakisV ZablotchiI. FloDB: unlocking memory in persistent key\u2010value stores. Paper presented at: Proceedings of the 12th European Conference on Computer Systems (EuroSys);2017:80\u201094.","DOI":"10.1145\/3064176.3064193"},{"key":"e_1_2_7_17_1","unstructured":"LuL PillaiTS Arpaci\u2010DusseauAC Arpaci\u2010DusseauRH. WiscKey: separating keys from values in SSD\u2010conscious storage. Paper presented at: Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST);2016:133\u2010148."},{"key":"e_1_2_7_18_1","unstructured":"WuXingbo XuYuehai ShaoZili JiangSong. LSM\u2010trie: an LSM\u2010tree\u2010based ultra\u2010large key\u2010value store for small data. Paper presented at: Proceedings of the USENIX Annual Technical Conference (ATC);2015."},{"key":"e_1_2_7_19_1","first-page":"496","volume-title":"DISTIL: A Distributed In\u2010Memory Data Processing System for Location\u2010Based Services","author":"Patrou M","year":"2018"},{"key":"e_1_2_7_20_1","first-page":"118","volume-title":"Toward Efficient Processing of Spatio\u2010Temporal Workloads in a Distributed In\u2010Memory System","author":"Memarzia P","year":"2019"},{"key":"e_1_2_7_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2016.2541168"},{"key":"e_1_2_7_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_7_23_1","doi-asserted-by":"crossref","unstructured":"LimH FanB AndersenDG KaminskyM. SILT: a memory\u2010efficient high\u2010performance key\u2010value store. Paper presented at: Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP);2011:1\u201013; ACM; Cascais Portugal.","DOI":"10.1145\/2043556.2043558"},{"key":"e_1_2_7_24_1","doi-asserted-by":"crossref","unstructured":"AndersenD. G. FranklinJ. KaminskyM. PhanishayeeA. TanL. VasudevanV.. FAWN: a fast array of wimpy nodes. Paper presented at: Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP);2009:1\u201014.","DOI":"10.1145\/1629575.1629577"},{"key":"e_1_2_7_25_1","unstructured":"AnandA MuthukrishnanC KappesS AkellaA NathS. Cheap and large CAMs for high\u2010performance dataintensive networked systems. Paper presented at: Proceedings of the 7th Symposium on Networked Systems Design and Implementation (NSDI);2010; San Jose California."},{"key":"e_1_2_7_26_1","unstructured":"BuchsbaumAL GoldwasserM VenkatasubramanianS WestbrookJR. On external memory graph traversal. Paper presented at: Proceedings of the 11th Annual ACM\u2010SIAM Symposium on Discrete Algorithms (SODA);2000:859\u2010860."},{"key":"e_1_2_7_27_1","doi-asserted-by":"crossref","unstructured":"BenderMA Farach\u2010ColtonM FinemanJT FogelY KuszmaulB NelsonJ. Cache\u2010oblivious streaming B\u2010trees. Paper presented at: Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA);2007:81\u201092.","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_7_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2015.2435779"},{"key":"e_1_2_7_29_1","doi-asserted-by":"crossref","unstructured":"ShenZ ChenF JiaY ShaoZ. DIDACache: a deep integration of device and application for flash based key\u2010value caching. Paper presented at: Proceedings of the 14th USENIX Conference on File and Storage Technologies (FAST);2017:391\u2010405.","DOI":"10.1145\/3203410"},{"key":"e_1_2_7_30_1","first-page":"121","volume-title":"Cuckoo Hashing","author":"Pagh R","year":"2001"},{"key":"e_1_2_7_31_1","doi-asserted-by":"crossref","unstructured":"CooperBF SilbersteinA TamE RamakrishnanR SearsR. Benchmarking cloud serving systems with YCSB. Paper presented at: Proceedings of the 1st ACM Symposium on Cloud Computing;2010:143\u2010154; New York NY.","DOI":"10.1145\/1807128.1807152"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.2875","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.2875","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1002\/spe.2875","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.2875","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T18:13:23Z","timestamp":1693937603000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.2875"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":30,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["10.1002\/spe.2875"],"URL":"https:\/\/doi.org\/10.1002\/spe.2875","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"type":"print","value":"0038-0644"},{"type":"electronic","value":"1097-024X"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"2019-11-02","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-05","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-08-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}