题目: LSM-trie: Building an Ultra-Large Key-Value Store for Small Data

时间:2015年7月20日上午10:00

地点:东五楼210

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.

In this talk, the speakers will present 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 re-organizing them using a compaction method much more efficient than that adopted for LSM-tree. 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.

Bio:

Dr. Song Jiang is an associate professor of the ECE department at Wayne State University. He received his B.S and M.S from the University of Science and Technology of China, and his Ph.D in computer science at the College of William and Mary in 2004. He is a recipient of 2009 US National Science Foundation (NSF) CAREER award. He has been on many conference program committees and proposal review panels. He has been involved in projects at Facebook and Baidu as a collaborator for providing high-quality Internet-wide services based on big data, resulting in significant publications at top-tier conferences.

Dr. Jiang’s research has generated substantial impact on the industry. Several of his proposed algorithms on memory and storage management have been officially adopted in mainstream systems including Linux kernel, NetBSD kernel, and storage engine of MySQL. For more info, please visit his homepage at http://www.ece.eng.wayne.edu/~sjiang.