Indexing key-value pairs on persistent storage has been one of important factors in a wide range of systems such as databases, NoSQL systems, file systems, and mobile devices. In most systems, since dealing with storage always has been identified as a bottleneck of the overall performance, the design and implementation of indexing schemes on storage are crucial factors for such systems to provide high throughput and low latency. Moreover, unlike in-memory indexing, there are several constraints on designing storage indexing due to several characteristics of block devices. To address those issues, B+-tree and its variants were proposed, and they have been successful index structures over the past few decades. Recently, however, due to rapid growth of social networking services and ubiquitous applications running on mobile devices, the amount of casual and unstructured data is increasing incredibly fast. There are lots of demands to index those kinds of data faster and more efficiently, but traditional indexing schemes can hardly meet the requirements due to various reasons.
First, both the performance and space overhead of tree-like structures rapidly get worse as the key length becomes longer. To address this issue, this dissertation proposes a new hybrid indexing approach called HB+-trie, which allows for efficient indexing and retrieval of arbitrary length string keys with relatively low disk accesses over tree-like structures, even though the keys are very long and randomly distributed in the key space. Second, the basic update-in-place scheme tends to experience the worst case write latency, thus it is unacceptable for the recent write-intensive key-value workloads. To achieve high write throughput, this dissertation extends and generalizes HB+-trie for append-only design, and presents ForestDB, a single node key-value storage system that employing append-only HB+-trie as its primary index structure. ForestDB uses a log-structured write buffer, which is similar to existing write-ahead logging approaches but does not require any further merge operations from the buffer to the main index. Accordingly, the overall write amplification is reduced without sacrificing the write throughput. Third, to reduce write amplification caused by wandering tree problem in append-only index structures, this dissertation suggests μ*-tree. μ*-tree stores all the nodes along the path from the root node to the leaf node into a single disk block in order to minimize the amount of disk writes. Furthermore, μ*-tree has an adaptive page layout scheme which dynamically adjusts the page layout for index nodes according to the workload characteristics on-the-fly. The proposed schemes have been implemented as stand-alone libraries, and evaluated in comparison with existing state-of-the-art approaches. The evaluation results in this dissertation demonstrate that the proposed schemes show significantly improved performance over legacy indexing systems.
키-값 쌍(key-value pair)을 영구 저장 장치(혹은 스토리지)에 색인하는 기법은 데이터베이스 시스템에서부터 NoSQL 시스템, 파일 시스템이나 휴대용 기기에 이르기까지 광범위한 시스템에서 중요 요소로 사용되어왔다. 대부분의 시스템에서 스토리지를 다루는 작업은 전체 성능에 있어 병목(bottleneck)으로 작용하기 때문에, 스토리지 위에서 동작하는 색인 기법의 설계나 구현은 해당 시스템이 고속 처리(high throughput) 및 낮은 지연 시간(low latency)을 지원할 수 있는지의 여부에 지대한 영향을 미친다. 게다가 블록 장치(block device)만의 고유 특성들로 인해 스토리지상의 색인 기법의 설계에는 메모리상에서의 색인 기법과는 달리 여러 가지 추가 제약 조건이 따른다. 이러한 문제들을 해결하기 위해 B+트리(B+tree)나 여러 변형들이 제안되어 지난 수십 년간 성공적으로 사용되어왔다. 하지만 최근에는 소셜 네트워킹 서비스(social networking service)나 휴대용 기기에 기반한 어플리케이션들의 폭발적 증가로 비정형 혹은 비격식적 데이터의 양이 빠른 속도로 늘어나고 있다. 그에 따라 이러한 데이터들을 효율적으로 빠르게 색인하고자 하는 수요 역시 함께 늘어나고 있는데, 기존의 색인 방법들은 여러 가지 한계로 인해 이러한 요구 조건들을 달성하기 어려운 단점이 있다.
첫째로, 트리 기반 색인 방법은 키(key)의 길이가 길어질수록 성능이 나빠지고 공간을 많이 차지하게 된다. 이러한 문제를 해결하기 위해, 본 학위 논문은 키의 길이가 매우 길고 균등 임의(uniform random)로 분포하여도 적은 디스크 접근만으로 기존 트리 기반 방식 대비 효율적인 색인이나 검색이 가능한 새로운 하이브리드(hybrid) 색인 기법을 제안하였으며, 이를 HB+트라이(HB+trie)라 명명하였다. 둘째로, 기본적인 update-in-place 방식은 많은 임의 쓰기(random write)로 인해 최악의 쓰기 지연 시간(write latency)을 보여주는 경향이 있는데, 따라서 이는 최근의 쓰기 집중적인(write-intensive) 키-쌍 워크로드(workload)에 적합하지 못하다. 이러한 고성능의 쓰기
처리량을 달성하기 위해, 본 학위 논문은 HB+트라이를 append-only 방식에 맞게 확장 및 일반화 하였으며, 해당 append-only HB+트라이를 주요 색인 기법으로 사용하는 단일 노드 키-값 쌍 저장 기법인 ForestDB를 제안하였다. ForestDB는 로그 구조(log-structured) 기반 쓰기 버퍼(write buffer)를 사용하는데, 이는 기존의 write-ahead logging 방식과 비슷하지만 버퍼 영역에서 메인 색인 영역으로의 추가 병합(merge) 명령이 필요 없다는 장점을 가지고 있다. 그에 따라 쓰기 처리 속도를 잃지 않으면서도 전체적인 쓰기 증폭(write amplification)을 줄이는 효과를 얻을 수 있다. 셋째로, append-only 색인 구조에서의 방랑 트리 문제(wandering tree problem)로 인한 쓰기 증폭 효과를 완화하기 위해 본 학위 논문은 μ*-트리를 제안하였다. μ*-트리는 디스크 쓰기량을 최소화하기 위해 루트 노드(root node)에서부터 리프 노드(leaf node)에 이르는 모든 노드들을 한 디스크 블록에 저장한다. 또한, μ*-트리는 적응적인 페이지 구획 기법(adaptive page layout scheme)을 사용하는데, 이는 워크로드의 실시간 변화에 따라 색인 노드들의 페이지 구획을 동적으로 재조정하는 기법이다. 본 학위 논문에서 제안된 기법들은 모두 독립된 라이브러리(library)로 실제 구현되었으며, 현존하는 최신의 기법들과 비교 실험하였다. 본 학위 논문의 실험 결과에 따르면 제안된 기법들은 기존의 색인 시스템과 비교하여 의미 있는 성능 향상을 보여준다.
