Title

Designing the Optimal LSM-tree-based Key-value Store Considering Limited System Resources

Alternative Title

제한된 시스템 자원을 고려한 최적의 LSM 트리 기반 키-값 저장소 설계

DGIST Authors

Junsu Im ; Sungjin Lee ; Hoon Sung Chwa

Advisor

이성진

Co-Advisor(s)

Hoon Sung Chwa

Issued Date

2025

Awarded Date

2025-02-01

Citation

Junsu Im. (2025). Designing the Optimal LSM-tree-based Key-value Store Considering Limited System Resources. doi: 10.22677/THESIS.200000828505

Type

Thesis

Description

LSM-tree, LSM-tree based key-value store, LSM-tree optimization, key-value SSD, Flash translate layer

Table Of Contents

I. Introduction 1
II. Background and Motivation 5
  2.1 Log-structured Merge-tree 5
    2.1.1 Tiering Compaction 5
    2.1.2 Leveling Compaction 6
  2.2 NAND-based Flash storage 8
    2.2.1 Logical-to-Physical Indexing in NAND Flash 8
    2.2.2 Memory-efficient Index Structures 9
    2.2.3 Creating PLR line segments from L2P pairs 10
    2.2.4 Impact of I/O Pattern and Fragmentation 12
  2.3 Key-value SSD 13
    2.3.1 Hash-based KV-SSD 14
    2.3.2 Performance Analysis of Hash-based KV-SSD 15
    2.3.3 LSM-Tree-based KV-SSD 16
    2.3.4 Hash vs LSM-Tree 17
  2.4 HTAP System 18
    2.4.1 LSM-tree in HTAP System 19
    2.4.2 Problems of Existing LSM-tree-based Database System 19
III. Challenges 21
  3.1 Challenges in implementing LSM-tree for an FTL 21
    3.1.1 LSM-tree for L2P Indexing 22
    3.1.2 Approximate Structures for L2P Indexing 22
    3.1.3 Naive Integration: Challenges and Solutions 24
  3.2 Challenges in implementing LSM-tree in a KV-SSD 28
    3.2.1 Performance Analysis 28
  3.3 Challenges in adopting LSM-tree-forest 32
IV. Solid State Drive Targeted Memory-Efficient Indexing for Universal I/O Patterns and Fragmentation Degrees 34
  4.1 Design and Implementation of AppL 34
    4.1.1 Organization and Operations 34
    4.1.2 FP-based Approximate Indexing 36
    4.1.3 Detailed derivation of Eq IV.1 38
    4.1.4 PLR-based Approximate Indexing 39
    4.1.5 LSM-tree Organization and Its Impacts 43
    4.1.6 Garbage Collection 45
    4.1.7 Crash Consistency and Concurrency 45
    4.1.8 Scaling with larger SSDs 47
    4.1.9 DRAM cache management 49
  4.2 Experiments 50
    4.2.1 Experimental Setup 50
    4.2.2 Performance Analysis 52
    4.2.3 Detailed Analysis 56
    4.2.4 Performance Analysis on Embedded Setup 59
    4.2.5 Scalability with Faster SSD 60
V. PinK: High-speed In-storage Key-value Store with Bounded Tails 63
  5.1 Design of PinK 63
    5.1.1 Overall Architecture 63
    5.1.2 Improving I/O Speed with Level Pinning 66
    5.1.3 Optimizing Search Path 68
    5.1.4 Speeding up Compaction 69
    5.1.5 Optimizing Garbage Collection 71
    5.1.6 Durability and Scalability Issues 75
  5.2 Design space of PinK 76
    5.2.1 Modeling PinK Write Overhead 76
    5.2.2 Extended Design Space of LSM-tree 78
  5.3 Experiments 80
    5.3.1 Experimental Setup 81
    5.3.2 Performance Analysis 83
    5.3.3 PinK design space analysis 90
    5.3.4 The Overhead of Flushing Dirty Meta Segments 92
VI. LSM-forest: planting multiple LSM-trees for HTAP workloads 94
  6.1 Design of LSM-forest 94
    6.1.1 DRAM resource sharing for LSM-forest 94
    6.1.2 Reducing I/O traffic 96
    6.1.3 Optimization for OLTP 100
  6.2 Evaluation 101
    6.2.1 Impact of global write-buffer 101
    6.2.2 Impact of PAX-SST 102
    6.2.3 Impact of level adjustment 103
  6.3 Discussion and related work 104
VII. Conclusions 105
References 108

URI

http://hdl.handle.net/20.500.11750/57992
http://dgist.dcollection.net/common/orgView/200000828505

DOI

10.22677/THESIS.200000828505

Degree

Doctor

Department

Department of Electrical Engineering and Computer Science

Publisher

DGIST

Show Full Item Record