LSM-trie : an lSM-tree-based ultra-large key-value store for small data items

X.B. Wu, Y.H. Xu, Zili Shao, S. Jiang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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.
Original languageEnglish
Title of host publication[Missing Source Name from PIRA]
PublisherUSENIX Association
Number of pages12
ISBN (Print)9781931971225
Publication statusPublished - 2015
EventUSENIX Annual Technical Conference [USENIX ATC] -
Duration: 1 Jan 2015 → …


ConferenceUSENIX Annual Technical Conference [USENIX ATC]
Period1/01/15 → …


Dive into the research topics of 'LSM-trie : an lSM-tree-based ultra-large key-value store for small data items'. Together they form a unique fingerprint.

Cite this