Cited 0 time in webofscience Cited 0 time in scopus

A Delete-Aware Compaction Trigger Method for LSM-Tree Based Key-Value Stores

Title
A Delete-Aware Compaction Trigger Method for LSM-Tree Based Key-Value Stores
Translated Title
LSM-Tree 기반의 키-값 저장소를 위한 삭제 인지 컴팩션 트리거 방법
Authors
Ilseop Lee
DGIST Authors
Ilseop Lee; Jemin Lee; Min-Soo Kim
Advisor(s)
이제민
Co-Advisor(s)
Min-Soo Kim
Issue Date
2021
Available Date
2022-07-07
Degree Date
2021/02
Type
Thesis
Keywords
LSM-Tree,Compaction trigger
Abstract
LSM-tree based key-value stores show high performance in write-intensive workloads due to the out-of-place update structure. However, this structure requires additional storage space to store a lot of redundant data in database and results in high space amplification. In order to remove redundant data, most modern LSM-tree stores use a compaction triggered by the capacity in each level. But the size-based compaction trigger often occurs inadequate compaction frequency according to the workload, causing high write amplification and reduces overall performance. To address this, we introduce delete-aware compaction trigger which responds to the current workload’s deletion rates and reduces ineffi-cient compactions consisting of most valid records. We implemented Delete-Aware RocksDB on top of RocksDB, and we show that it outperforms by keeping low space amplification without write amplifica-tion cost compared to RocksDB. Furthermore, we show our system cooperated with Monkey, one of the state-of-the-art LSM-tree based key-value store, outperforms existing systems in terms of throughput.
Table Of Contents
Ⅰ. Introduction 1 1.1 Motivation 2 1.1.1 Lifecycle of a deletion record and inefficiency in a compaction 2 1.1.2 Maintaining low space amplification decreases overall performance 3 1.2 Research Goals and Thesis Structure 5 1.2.1 Goal 1: To make a compaction efficient according to the workload 5 1.2.2 Goal 2: To trigger a compaction at the proper time 5 1.2.3 Thesis Structure 5 ⅠⅠ. Background 6 2.1 LSM-Tree Basics 6 2.1.1 Memtable and SSTable 6 2.1.2 Compaction 8 2.1.3 Bloom Filter 9 2.2 Amplification Factors 10 2.2.1 Read Amplification 10 2.2.2 Write Amplification 10 2.2.3 Space Amplification 11 ⅠⅠⅠ. Implementation 12 3.1 Implementing Delete-Aware RocksDB 13 3.1.1 A delete-aware compaction trigger 13 3.1.2 Pre-remove strategy for redundant tombstones 16 3.1.3 Dynamic runtime adaptation 17 3.2 Extending db_bench 20 3.2.1 Flags 20 3.2.2 Configuration of Delete-Aware RocksDB 20 3.3 Cooperation with Monkey Method 21 ⅠV. Benchmarks 23 4.1 Experimental Setup 23 4.2 Throughput 24 4.3 The Number of Compactions and Space Amplification 25 V. Discussion 27 VI. Conclusion 28 References 29
URI
http://dgist.dcollection.net/common/orgView/200000364341
http://hdl.handle.net/20.500.11750/16691
DOI
10.22677/thesis.200000364341
Degree
Master
Department
Information and Communication Engineering
University
DGIST
Files:
Collection:
Department of Electrical Engineering and Computer ScienceThesesMaster


qrcode mendeley

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

BROWSE