LB2-Tree: 키-밸류 SSD에 특화된 인덱스 구조

Abstract

키-밸류 SSD는 키-밸류 스토어 I/O 스토리지 스택을 구성함에 있어 새로운 패러다임을 제시한다. 키-밸류 SSD는 사용자에게 키-밸류 인터페이스를 제공하여 호스트 시스템 자원의 사용량을 크게 줄이지만 여러 한계점으로 인해 키-밸류 스토어를 대체할 수는 없다. 이 논문에서는 키-밸류 SSD의 특징들을 분석하고 이를 키-밸류 스토어의 대체제로 사용하기 어려운 이유를 설명한다. 또한, 이러한 분석들을 바탕으로 LB2-Tree라는 새로운 인덱스 구조를 제안한다. LB2-Tree는 기존 Copy-On-Write B+Tree에서 나타나는 문제점인 compaction과 cascading update를 키-밸류 SSD의 특성들을 활용해 해결한다. LB2-Tree는 특히 업데이트가 잦은 환경에서 CoW B+Tree에 비해 매우 높은 성능과 매우 낮은 쓰기량을 보인다.

Key-Value SSDs presents a new paradigm in constructing the Key-Value Store I/O storage stack. Key-Value SSDs provide users with a key-value interface, which significantly reduces the use of host system resources, but can not replace Key-Value stores due to multiple limitations. This paper analyzes the characteristics of Key-Value SSDs and explains why they can not be used as an alternative to Key-Value stores. Based on these analyses, this paper propose a new index structure called LB2-Tree. LB2-Tree is based on Copy-on-Write B+Tree and solves problems like compaction, high write amplification, high CPU overhead, and cascading updates by using the characteristics of a Key-Value SSDs. LB2-Tree shows high throughput and low write and read amplification compared to CoW B+tree, especially in update-intensive workloads.