IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. X, NO. Y, JANUARY 2016 1
Building an Efficient Put-Intensive Key-Value
Store with Skip-tree
Yinliang Yue, Bingsheng He, Yuzhe Li, Weiping Wang
Abstract—Multi-component based Log-Structured Merge-tree (LSM-tree) has been becoming one of the mainstream indexes.
LSM-tree adopts component-by-component KV item flowing down mechanism to push each KV item from one smaller component
to the adjacent larger component during compaction procedures until the KV items reach the largest component. This process
incurs significant write amplification and limits the write throughput. In this paper, we propose one multi-component Skip-tree to
aggressively push the KV items to the non-adjacent larger components via skipping some components and then make the KV
items’ top-down move more efficient. We develop adaptive and reliable KV item movements among components. By reducing
the number of steps during the flowing process from memory-resident component to the disk-resident largest component, Skip-
tree can effectively reduce the write amplification and thus improve the system throughput. We design and implement one high
performance key-value store, named SkipStore, based on Skip-tree. The experiments demonstrate that SkipStore outperforms
the state-of-the-art open-sourced system RocksDB in Facebook by 66.5% under HDD and 61% under SSD.
Index Terms—Storage System, KV Store, LSM-tree, Compaction, Performance Optimization;
F
1 INTRODUCTION
In the recent years, latency-sensitive user interactive
internet applications increase gradually. These inter-
active internet applications, such as WeChat, Twit-
ter and Facebook, encourage users to produce and
share short messages and small-sized pictures with
simultaneously low read and write latency. Lots of
efforts have been done to improve either read perfor-
mance or write performance [1][4][6][23][27][37]. For
example, B-tree supports fast read access but poor up-
date performance[13]. On the contrary, log-structured
file system provides high sequential write perfor-
mance but unacceptable read access performance [33].
However, it is challenging and difficult to build one
massive storage system to simultaneously support
both high read and write performance. Multi-layer
hierarchical storage architecture has been widely used
to boost the read performance with speedy storage
devices and alleviate the disk read and write I/O
compete.
Although reads are also more than writes in most
internet-based applications, many reads are absorbed
by multi-level caches in the Internet architectures,
and writes become more dominant for the accesses
to the back-end storage systems[14][16][17][18][22].
Facebook [25] reveals that the popularity of photos
is highly dependent on content age, and the multi-
layer cache is extremely effective to intercept the
• Yinliang Yue is with Institute of Information Engineering, Chinese
Academy of Sciences, Beijing, China. E-mail: yueyinliang@iie.ac.cn.
• Bingsheng He is with National University of Singapore, Singapore.
• Yuzhe Li and Weiping Wang are with Institute of Information Engi-
neering, Chinese Academy of Sciences, Beijing, China.
reads. That is to say, 90.1% read requests are served
by multi-layer cache, while only 9.9% read requests
reach the back-end storage. On the other hand, more
write-intensive applications that ingest event logs are
becoming emerging, such as user clicks and mobile
device sensor readings [1].
Compared with relational databases, KV stores pose
simplified, easy-to-use interface and high scalability.
KV stores are suitable for latency-sensitive internet
services, and have been widely used in large-scale
data intensive internet applications [1]. In order to
simultaneously support increasing writes, low write
latency and range-based scan, LSM-tree [3] and its
variants including COLA [5], SAMT [6] and Hbase
[8] have been widely used in the current emerging
internet applications. LSM-tree is originally proposed
to manage the data in disk-resident storage and the
multi-layer disk-resident components are designed
to balance the performance of read and write I/Os.
Specifically, the newly written data are accessed with
a great probability in its initial life-cycle, and so
the LSM-tree employs component-by-component flow-
ing mechanism. That is to say, each KV item is pushed
from one smaller component to the adjacent larger
component during compaction procedures until it
reaches the largest component.
However, the LSM-tree is designed for embedded
storage, in which memory footprints are commonly
in small-size. Later, lots of researches have been done
to boost the read or write performance for large-scale
data management. For example, COLA [5] and FD-
tree [7] use forward pointers to improve the read
performance, while GTSSL [6] reinserts reads KV
items into upper components to expedite lookup.
In modern data centers, large-capacity memory is
This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TPDS.2016.2609912
Copyright (c) 2016 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
剩余13页未读，继续阅读
资源评论
