대용량 LSM-tree 구조 기반의 key-value store에서 효율적인 메모리 사용을 위한 Hybrid Indexing 기법

국문 초록 (Abstract)

현재 LSM-tree 구조 기반의 KV store는 단일 indexing을 적용하는데, 옵션으로 지원되는 indexing 방식들은 각각 특정 메모리 크기에 국한되어 높은 성능을 보인다. 대표적으로 RocksDB는 full indexing과 partitioned indexing 2가지 indexing 옵션을 지원한다. Full indexing은 하나의 block으로 metadata를 관리하기 때문에 cache eviction될 확률이 낮아 메모리가 충분한 상황에서 높은 성능을 보인다. 반면, partitioned indexing은 metadata를 4KB 단위의 block으로 관리하여 메모리를 효율적으로 사용하기 때문에 메모리가 부족한 상황에서 높은 성능을 보인다. 기존 단일 indexing 방식은 이러한 각 indexing 기법들의 장점을 모두 활용하지 못한다.
이에 우리는 각 indexing들의 장점을 모두 활용하여 모든 메모리 크기에서 최고의 성능을 낼 수 있는 hybrid indexing을 제안한다. 이를 제안하기에 앞서 우리는 기존 partitioned indexing의 block read 횟수를 최적화한 unified partitioned indexing을 제안한다. 해당 기법은 filter와 index를 하나의 block으로 관리하여 block read 횟수를 최적화한 기법으로 메모리가 극심하게 부족한 상황에서 효과적이다. 이를 기반으로 SSTable 별로 full indexing과 unified partitioned indexing을 나누어 적용한다. 우리는 SSTable 별로 각 index type을 적용했을 때 발생하는 cost-benefit을 average get latency와 연관 지어 계산한다. 그리고 계산된 결과를 바탕으로 SSTable마다 높은 benefit을 보이는 index type을 적용한다.
우리는 RocksDB를 기반으로 hybrid indexing을 적용하였다. Hybrid indexing은 모든 메모리 크기 환경 및 접근 패턴에 따라 adaptive하게 indexing을 변경한다. 그 결과, YCSB에서 최대 55.31%, Mixgraph에서 56.22% 높은 읽기 성능을 보여주었다. 또한, write이 포함된 workload에서도 기존 성능과 비슷한 성능을 보여주었다. State-of-the art와의 비교 실험에서도 LSM-trie와 ElasticBF보다 높은 읽기 성능을 보여주었다.

다국어 초록 (Multilingual Abstract)

The current key-value (KV) store uses a structure called LSM-tree with a single indexing method. RocksDB, a popular system, supports two indexing options: full indexing and partitioned indexing. Full indexing works best with ample memory, as it manages data in a way that minimizes cache issues. Partitioned indexing, however, is efficient when memory is limited because it organizes data into smaller blocks for better memory usage.

The proposed solution involves a hybrid indexing approach that combines the strengths of both methods for better performance across various memory sizes. Initially, they suggest a unified partitioned indexing technique that optimizes block reads by managing filter and index data together, ideal for extremely limited memory scenarios. Then, they apply full and unified partitioned indexing separately for each data table, calculating the cost and benefit of applying each method to optimize the average get latency. This adaptive approach to indexing, called hybrid indexing, adjusts based on memory size and access patterns.

In tests using RocksDB, this hybrid indexing approach improved read performance significantly, with a 55.31% boost in YCSB and a 56.22% increase in Mixgraph. It also maintained similar performance levels for workloads involving write operations. Comparative experiments showed that this hybrid indexing outperformed other systems like LSM-trie and ElasticBF in read performance.

목차 (Table of Contents)

• 제1장 서론 1
• 제2장 배경지식 5
• 1. Log-Structured Merge Tree (LSM-tree) 5
• 2. Metadata of RocksDB 7
• 3. Indexing technique of RocksDB 8
• 제3장 연구 동기 . 10
• 제4장 디자인 및 구현 . 15
• 1. Unified partitioned indexing 16
• 1) Unified partitioned indexing 디자인 . 16
• 2) Performance of unified partitioned indexing . 17
• 2. Hybrid indexing . 18
• 1) Hybrid indexing 적용 단위 . 19
• 2) Indexing 기법에 따른 cost-benefit 분석 20
• 3) Get latency breakdown . 23
• 4) Hit ratio predictor . 26
• 5) 전체 동작 방식 28
• 6) 최적화 29
• 제5장 실험 및 결과 분석 . 30
• 1. 실험 환경 . 30
• 2. 실험 결과 . 31
• 1) Hybrid indexing read 성능 31
• 2) Hybrid indexing read/write/scan 성능 . 33
• 3) T_get과 실제 get latency 비교 . 34
• 4) State of the art와의 비교 . 35
• 제6장 관련 연구 37
• 제7장 결론 . 39