Indexing for persistent key-value storage

Abstract

키-값 쌍(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)로 실제 구현되었으며, 현존하는 최신의 기법들과 비교 실험하였다. 본 학위 논문의 실험 결과에 따르면 제안된 기법들은 기존의 색인 시스템과 비교하여 의미 있는 성능 향상을 보여준다.