Detail View

  Department of Electrical Engineering and Computer Science Theses Ph.D.

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

Citations

WEB OF SCIENCE

Citations

SCOPUS

Metadata Downloads

XML
Excel
DC Field Value Language
dc.contributor.advisor 이성진 -
dc.contributor.author Junsu Im -
dc.date.accessioned 2025-02-28T21:01:19Z -
dc.date.available 2025-02-28T21:01:19Z -
dc.date.issued 2025 -
dc.identifier.uri http://hdl.handle.net/20.500.11750/57992 -
dc.identifier.uri http://dgist.dcollection.net/common/orgView/200000828505 -
dc.description LSM-tree, LSM-tree based key-value store, LSM-tree optimization, key-value SSD, Flash translate layer -
dc.description.tableofcontents 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		 -
dc.format.extent 123 -
dc.language eng -
dc.publisher DGIST -
dc.title Designing the Optimal LSM-tree-based Key-value Store Considering Limited System Resources -
dc.title.alternative 제한된 시스템 자원을 고려한 최적의 LSM 트리 기반 키-값 저장소 설계 -
dc.type Thesis -
dc.identifier.doi 10.22677/THESIS.200000828505 -
dc.description.degree Doctor -
dc.contributor.department Department of Electrical Engineering and Computer Science -
dc.identifier.bibliographicCitation Junsu Im. (2025). Designing the Optimal LSM-tree-based Key-value Store Considering Limited System Resources. doi: 10.22677/THESIS.200000828505 -
dc.contributor.coadvisor Hoon Sung Chwa -
dc.date.awarded 2025-02-01 -
dc.publisher.location Daegu -
dc.description.database dCollection -
dc.citation XT.ID 임76 202502 -
dc.date.accepted 2025-01-20 -
dc.contributor.alternativeDepartment 전기전자컴퓨터공학과 -
dc.subject.keyword LSM-tree, LSM-tree based key-value store, LSM-tree optimization, key-value SSD, Flash translate layer -
dc.contributor.affiliatedAuthor Junsu Im -
dc.contributor.affiliatedAuthor Sungjin Lee -
dc.contributor.affiliatedAuthor Hoon Sung Chwa -
dc.contributor.alternativeName 임준수 -
dc.contributor.alternativeName Sungjin Lee -
dc.contributor.alternativeName 좌훈승 -
dc.rights.embargoReleaseDate 2028-02-29 -
Show Simple Item Record

File Downloads

  • There are no files associated with this item.

공유

qrcode
공유하기

Total Views & Downloads

???jsp.display-item.statistics.view???: , ???jsp.display-item.statistics.download???: