Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/64377
Title: LSM-trie : an lSM-tree-based ultra-large key-value store for small data items
Authors: Wu, XB
Xu, YH
Shao, ZL 
Jiang, S
Issue Date: 2015
Publisher: USENIX Association
Source: Proceedings of the 2015 USENIX Annual Technical Conference (USENIC ATC ’15), Santa Clara, CA, USA, 8-10 July 2015, p. 71-82 How to cite?
Abstract: Key-value (KV) stores have become a backbone of large-scale applications in today's data centers. The data set of the store on a single server can grow to billions of KV items or many terabytes, while individual data items are often small (with their values as small as a couple of bytes). It is a daunting task to efficiently organize such an ultra-large KV store to support fast access. Current KV storage systems have one or more of the following inadequacies: (1) very high data write amplifications, (2) large index set, and (3) dramatic degradation of read performance with overspill index out of memory.
To address the issue, we propose LSM-trie, a KV storage system that substantially reduces metadata for locating KV items, reduces write amplification by an order of magnitude, and needs only two disk accesses with each KV read even when only less than 10% of metadata (Bloom filters) can be held in memory. To this end, LSM-trie constructs a trie, or a prefix tree, that stores data in a hierarchical structure and keeps reorganizing them using a compaction method much more efficient than that adopted for LSM-tree. Our experiments show that LSM-trie can improve write and read throughput of LevelDB, a state-of-the-art KV system, by up to 20 times and up to 10 times, respectively.
URI: http://hdl.handle.net/10397/64377
ISBN: 978-1-931971-225
Appears in Collections:Conference Paper

Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

5
Last Week
0
Last month
Checked on Jun 25, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.