Mitigating Durability-Induced Costs across DRAM-Resident and Persistent Memory?Based Key-Value Stores = DRAM 기반 및 PMEM 기반 키-밸류 스토어에서 내구성으로 인해 발생하는 비용 완화 기법

국문 초록 (Abstract)

인-메모리 키-밸류 스토어는 데이터를 디스크 기반 저장소가 아니라 메모리에 주로 저장하여 훨씬 낮은 지연 시간을 제공한다. 이러한 시스템은 캐시 서버나 실시간 처리 시스템과 같이 낮은 지연 시간이 요구되는 워크로드에서 주로 사용된다. 그러나 메모리의 데이터는 휘발성이기 때문에 시스템이 장애 또는 재시작될 경우 데이터가 손실될 수 있다.

데이터 내구성을 보장하기 위한 다양한 메커니즘이 존재하며, 본 논문에서는 두 가지 기법에 초점을 맞춘다. 첫 번째는 서비스 중단 없이 데이터를 체크포인트할 수 있는 fork 기반 체크포인트이다. 이 방식은 구현이 용이하며 주요 인-메모리 키-밸류 저장소에서 사용되고 있다. 그러나 체크포인트 도중에 copy-on-write로 인해 더 많은 메모리 용량을 요구할 수 있으며, 이를 대비하기 위해 시스템은 추가 메모리를 제공해야 한다.

체크포인트 과정에서 발생하는 메모리 오버헤드를 줄이기 위해, 본 논문은 메모리 덤프 기반 체크포인트를 확장한 MDC+를 제안한다. MDC+는 페이지 단위 덤핑과 힌트 기반 메모리 할당을 통해 체크포인트 동안의 메모리 사용량을 줄인다. 페이지 단위 덤핑은 데이터의 체크포인트 순서를 재조정하여 페이지를 더 빠르게 해제할 수 있도록 한다. 힌트 기반 메모리 할당은 데이터 특성에 따라 메모리를 그룹화함으로써 copy-on-write 오버헤드와 메모리 사용량을 줄인다. 그 결과, 쓰기 집약적 워크로드에서 체크포인트 시 키-밸류 스토어의 메모리 사용량을 58.5\% 감소시킨다.

두 번째 기법은 키-밸류 스토어의 데이터 내구성을 보장하기 위해 비휘발성 메모리(PMEM)를 사용하는 것이다. 비휘발성 메모리는 자체적으로 비휘발성이기 때문에 시스템이 장애를 일으켜도 데이터를 보존할 수 있다. 그러나 비휘발성 메모리의 성능 및 특성은 기존 휘발성 메모리와 다르다. 특히, PMEM에서의 랜덤 읽기(random read)는 높은 읽기 증폭(amplification)을 유발하여 키-밸류 스토어의 성능을 저하시킨다. 이는 여러 번의 읽기 연산을 포함하는 범위 쿼리(range query)의 처리량을 낮추는 원인이 된다.

범위 쿼리 성능을 향상시키기 위해, 본 논문은 비휘발성 메모리 기반 범위 쿼리를 효율적으로 처리하는 키-밸류 스토어인 StratoKV를 제안한다. StratoKV는 로그(log)와 부분 정렬 리스트(partially sorted list)로 구성된다. 로그는 지속성을 보장하고 PMEM의 랜덤 접근을 피하기 위해 DRAM 영역과 PMEM 영역으로 구성된다. 부분 정렬 리스트는 효율적인 범위 쿼리 처리를 제공한다. 또한, 로그와 리스트 간 데이터 이동 오버헤드를 줄이기 위해 batch eviction과 추가 최적화를 적용하였다. 그 결과, StratoKV는 범위 쿼리 처리량을 38\% 향상시킨다.

다국어 초록 (Multilingual Abstract)

In-memory key-value stores keep data primarily in memory rather than on disk-based storage. These systems are typically used for workloads that require low latency, such as cache servers or real-time processing systems. However, because data in memory is volatile without any additional mechanism, it is lost when the system crashes or restarts.

There are several mechanisms to ensure data durability. In this dissertation, we focus on two schemes. The first is fork-based checkpointing, which is used to checkpoint data without suspending the service. This scheme is easy to implement and is used in popular in-memory key-value stores. However, it may require additional memory capacity during checkpointing because of copy-on-write overhead, and the system needs to provide more memory to handle it.

To reduce memory overhead during checkpointing, we introduce MDC+, which is an extension of memory dump-based checkpointing. It reduces the memory footprint during checkpointing by page-level dumping and hint-based memory allocation. Page-level dumping reorders the checkpointing sequence of the data and facilitates early page release during checkpointing. Hint-based memory allocation reduces the amount of copy-on-write and memory footprint during checkpointing by grouping data by its characteristics. As a result, we reduce the memory footprint of the key-value store by 58.5% during checkpointing under write-intensive workloads.

The second is using persistent memory(PMEM) in a key-value store to ensure data durability. Because persistent memory itself is non-volatile, the data in the key-value store can be preserved even if the system crashes. However, the performance and characteristics of persistent memory are different from existing volatile memory. In particular, random reads in persistent memory cause read amplification and degrade the performance of the key-value store. This leads to poor throughput of range queries that include multiple read operations.

To improve range query performance, we introduce StratoKV, a key-value store for efficient range queries on persistent memory. StratoKV consists of logs and partially sorted lists. The logs consist of a DRAM part and a PMEM part to ensure persistence and avoid PMEM random access. The partially sorted lists provide efficient range query processing. To mitigate the overhead of data migration between the logs and lists, we use batch eviction and optimizations. As a result, StratoKV improves range query throughput by 38%.

목차 (Table of Contents)

• Abstract i
• Contents iii
• List of Figures vi
• List of Tables viii
• Chapter 1 Introduction 1
• 1.1 Durability as a Cost in Key-Value Stores 1
• 1.2 Durability via Checkpointing in In-Memory Key-Value Stores 2
• 1.3 Durability with Persistent Memory in Key-Value Stores 3
• 1.4 Problem Statement 4
• 1.5 Scope and Contributions 4
• Chapter 2 Background 6
• 2.1 Various Durability Schemes 6
• 2.2 Fork-based Checkpointing and Memory Allocation 7
• 2.2.1 Fork-based Checkpointing 7
• 2.2.2 Memory Allocation 9
• 2.3 Persistent Memory 10
• 2.3.1 Characteristics and Performance 10
• 2.3.2 PMEM-based Key-Value Store 12
• Chapter 3 Memory-Efficient Fork-based Checkpointing 14
• 3.1 Motivation 14
• 3.1.1 Limitations in Fork-based Checkpointing 14
• 3.1.2 Root Causes of Memory Footprint Issues 16
• 3.2 Design Overview 17
• 3.2.1 Key Techniques 17
• 3.2.2 Architecture Overview 19
• 3.3 Memory Dump-based Checkpointing 21
• 3.3.1 OS Support 21
• 3.3.2 Checkpointing and Restoring Process 24
• 3.4 Hint-based Segregated Memory Allocation 27
• 3.4.1 Characteristic-based Memory Classification 27
• 3.4.2 Hint-based Segregated Memory Allocator 28
• 3.5 Checkpointing Solutions and Implementation 29
• 3.5.1 Checkpointing Solutions 30
• 3.5.2 Implementation 32
• 3.6 Evaluation 33
• 3.6.1 Experimental Setup 33
• 3.6.2 Performance 35
• Chapter 4 High-Performance Key-Value Store for Efficient Range
• Queries on Persistent Memory 43
• 4.1 Motivation 43
• 4.2 Design and Implementation 46
• 4.2.1 Architecture Overview 47
• 4.2.2 Operations 51
• 4.2.3 Data Layout and Placement 52
• 4.2.4 Design Discussion 54
• 4.3 Optimization 55
• 4.3.1 Direct Insert 55
• 4.3.2 Batch Node Address Caching 56
• 4.3.3 Node Group Extension 57
• 4.4 Evaluation 58
• 4.4.1 Experimental Setup 58
• 4.4.2 Comparison with Other Schemes 60
• 4.4.3 Breakdown of StratoKV 64
• Chapter 5 Related Work 67
• Chapter 6 Conclusion 69
• 요약 79