인 메모리 MVCC 데이터베이스를 위한 효율적인 버전 자료구조에 대한 연구

Abstract

MVCC(Multi-Version Concurrency Control)을 사용하는 데이터베이스는 업데이트 등의 작업에서 레코드에 대한 버전이 생성되고 이렇게 생성된 버전들은 읽기 작업 시 트랜잭션별 레코드에 대해 유효한 내용을 읽을 수 있도록 한다. 최근 HTAP 워크로드에 대한 대응을 위해 읽기 작업의 성능을 향상시키기 위한 연구는 계속되고 있으나 그러한 연구의 주된 목적은 최신 레코드를 읽는 작업의 개선 혹은 최신 레코드 스캔 성능의 개선 등 최신 레코드를 빠르게 읽는 것에 집중하고 있다. MVCC 데이터베이스에서 버전 관리의 개선을 위해 연구되는 주된 사항은 GC(Garbage Collection)이며, 이는 단순히 버전 관리 개선만을 위한 것이 아니라 공간 사용의 효율을 위한 것이기도 하다. 하지만 GC의 개선만으로 버전 관리 및 탐색의 효율성을 높이는 것은 한계가 있으며, 결국 현재 대중적으로 버전 관리를 위해 사용되는 단방향 연결 리스트를 이용한 버전 관리는 읽기 작업 중 버전 탐색 성능 향상 측면에서 개선이 필요한 상황이다.

이 논문에서는 MVCC 데이터베이스에서의 버전 탐색에 대해 알아보고 MVCC 데이터베이스에서 일반적으로 버전 관리를 위해 사용하는 자료구조인 단방향 연결 리스트를 대체하여 버전 자료구조로 사용할 수 있는 세 가지 대안인 스킵 리스트, b+ 트리, 레드-블랙 트리에 대해 알아보고 해당 자료구조들을 오픈 소스 인 메모리 MVCC 데이터베이스에 버전 관리를 위한 자료구조로 실제 구현하여 버전 관리 성능을 확인 및 분석한다. 특히 기존 단방향 연결 리스트에서 스캔 작업 시 55초가 소요되었으나 논문에서 제안하는 세 가지 자료구조로 버전 관리를 하였을 때 스캔 작업이 약 3 밀리초까지 개선되는 모습을 확인할 수 있었다. 이 외에도 여러 실험들을 통해 세 가지 자료구조 중 어떤 자료구조가 버전 관리를 효율적으로 할 수 있는지 알아본다.; DBMS using MVCC(Multi-Version Concurrency Control) generate versions for records, such as updates, and these generated versions allow read operations to read valid content of record for transactions. Recent studies have been underway to improve the performance of read operations to respond to HTAP workloads, but the main purpose of such studies is to quickly read the latest records, such as improving point lookup or improving the scanning performance of the latest records. In the MVCC DBMS, the main issue studied for the improvement of version management is the GC(Garbage Collection), which is not just for the improvement of version management, but also for the efficiency of space usage. However, there is a limit to increasing the efficiency of version management and version navigating just by improving GC, and eventually, versioning using a singly linked list currently used for versioning needs to be improved in terms of improving version lookup performance during read operations.

In this paper, we discuss version lookup mechanism in MVCC DBMS, and the three alternatives, skip lists, b+ tree, and red-black tree that can be used as a version data structure by replacing singly linked list which is generally used for version management in MVCC DBMS. And the corresponding data structures are actually implemented as a data structure for version management in open source in-memory MVCC DBMS to analyze and discuss version management performance. In particular, the scan operation took 55 seconds from the existing singly linked list, but when version control was performed with the three data structures proposed in the paper, the scan operation could be seen to be improved to about 3 milliseconds. In addition, various experiments will be conducted to find out which of the three data structures can efficiently manage versions.