Paper: An Empirical Evaluation of In-Memory Multi-Version Concurrency Control

Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10, 7 (March 2017), 781-792. (PDF)

요약

이 페이퍼는 인메모리 데이터베이스에서의 MVCC의 4가지 주요한 디자인 선택 – 동시성 제어 프로토콜, 버전 스토리지, 가비지 컬렉션, 인덱스 관리 – 을 설명하고, 각각의 디자인 선택을 Peloton DB에 구현한 후 OLTP 워크로드 하의 병목을 분석하고 있다.

공통적인 DBMS 메타데이터

  • 트랜잭션
    • 각각의 트랜잭션은 유일하고 단조증가하는 타임스탬프를 트랜잭션의 id로서 할당받는다.
  • 튜플
    • 각각의 버전은 4개의 메타데이터 필드를 가진다.
    • txn-id: 해당 버전에 대한 write lock을 표현하며, 0이라면 lock이 걸리지 않은 상태이고, 어떤 트랜잭션의 id가 기록되어 있다면, 그 트랜잭션에 의해 해당 버전이 write lock이 걸린 것을 나타낸다.
    • begin-ts, end-ts: 튜플 버전이 유효한 논리적인 시간 범위를 나타낸다. 처음에는 0으로 설정되고, 만약 어떤 튜플 버전이 삭제된다면 begin-ts는 INF가 된다.
    • pointer: 이전이나 이후의 튜플 버전을 가리키는 포인터로 버전들의 체인을 구성한다.

동시성 제어 프로토콜 (Concurrency Control Protocol)

  • Timestamp Ordering (MVTO)
    • 튜플을 읽은 마지막 트랜잭션의 id가 기록되는 read-ts라는 필드가 추가된다.
    • 어떤 트랜잭션이 쓰기를 위해 새로운 버전을 생성하려고 할 때, 그 트랜잭션 id가 마지막 버전의 read-ts보다 클 때만 이를 허용한다. 즉, 이미 새로운 트랜잭션에 의해서 읽힌 데이터를 과거의 트랜잭션이 갱신할 수 없는 액세스의 순서를 보장하고 있다.
  • Optimistic Concurrency Control (MVOCC)
    • 트랜잭션들이 서로 충돌할 가능성이 낮다고 가정하고, 액세스하려는 튜플에 대한 lock을 얻는 대신, 우선 튜플들에 액세스를 수행하고, 충돌이 없었는지를 검증하고, 마지막으로 결과를 쓰는 3개의 phase로 나뉘어 진행된다.
    • read phase: 읽기와 업데이트 작업이 이루어진다. 읽기는 begin-ts, end-ts에 해당하는 버전을 찾아 읽기가 이루어지고, 업데이트는 txn-id가 설정된 새로운 버전을 생성하는 방식으로 이루어진다.
    • validation phase: 트랜잭션에 대해서 commit 시점을 나타내는 새로운 타임스탬프를 부여하고, 트랜잭션 내에서 읽었던 튜플들이 어떤 트랜잭션에 의해서 업데이트 되었는지 확인한다. 만약 그렇다면 트랜잭션은 중지된다.
    • write phase: 트랜잭션에서 만들어진 새 버전들을 모두 DB에 쓰고, begin-ts를 commit 타임스탬프로, end-ts를 INF로 설정한다.
  • Two-phase Locking (MV2PL)
    • 모든 트랜잭션은 액세스를 하기 위해서 튜플의 현재 버전에 대한 lock을 얻는다.
    • write lock은 txn-id를 이용하고, read lock은 어떤 튜플에 대해 현재 읽기 액세스를 하고 있는 수를 나타내는 read-cnt라는 필드를 도입한다.
  • Serialization Certifier
    • 동시적으로 진행되는 트랜잭션들로부터 문제가 있는 구조를 찾아내기 위한 serialization graph를 유지하는 프로토콜이라고 하는데, 이 페이퍼에 기술된 설명만으로는 이해하기 어려웠다.

버전 스토리지 (Version Storage)

  • Append-only Storage
    • 튜플을 업데이트하기 위해서, 현재 버전의 내용을 새로운 버전으로 복제하고, 수정을 가한다.
    • 버전 체인을 구성하는 순서에 따라서, Oldest-to-Newest (O2N)과 Newest-to-Oldest (N2O)로 나뉜다.
      • O2N: 새로운 버전이 추가될 때마다 인덱스를 갱신하지 않아도 되는 이점이 있지만, 마지막 버전을 읽기 위해서 항상 버전 체인을 따라가야하는 단점이 있다. 따라서, 버전 체인을 짧게 유지하는 것이 관건이 된다.
      • N2O: 버전 체인을 따라가지 않아도 되는 장점이 있는 반면, 새 버전이 추가될 때 모든 인덱스도 업데이트해야하는 단점이 있다.
  • Time-Travel Storage
    • 마스터 버전은 메인 테이블에 저장하지만 오래된 버전들은 별도의 테이블에 저장한다.
    • 인덱스는 항상 마스터 버전을 가리키므로 새 버전이 추가되어도 변경이 필요없다.
  • Delta Storage
    • 마스터 버전은 메인 테이블에 유지하고, delta 버전들은 별도의 테이블에 유지한다.
    • 튜플의 일부만을 수정하는 UPDATE 작업에 이상적이다.
    • 여러 컬럼을 읽어야 할 경우, 모든 데이터를 얻기 위해서 버전 체인을 따라가야한다.

가비지 컬렉션 (Garbage Collection)

  • Tuple-level Garbage Collection
    • Background Vacuuming (VAC)
      • 만료된 버전을 찾기 위해서 백그라운드 쓰레드가 데이터베이스를 주기적으로 스캔하는 방식.
      • 마지막 스캔 이후로 변경되지 않은 튜플은 검사하지 않도록 하기 위한 비트맵을 통해 최적화를 할 수 있다.
    • Cooperative Cleaning (COOP)
      • 트랜잭션을 실행하는 동안 버전 체인을 따라가며 만료된 버전을 찾아내는 방식.
      • O2N append-only 스토리지에만 적용할 수 있다.
      • 트랜잭션이 액세스 하지 않는 튜플에 대해서는 GC가 불가능하므로 별도의 쓰레드로 GC를 수행할 필요가 있다.
  • Transaction-level Garbage Collection
    • 하나의 epoch이 끝나면 그 epoch에 속한 트랜잭션들이 생성한 버전들은 제거되어도 된다.
    • 트랜잭션 단위로 GC가 일어나므로 트랜잭션 단위의 스토리지 최적화가 가능하다.
    • 트랜잭션의 읽기/쓰기 액세스가 일어난 버전들을 추적하기 위한 비용이 발생한다.

인덱스 관리 (Index Management)

  • Logical Pointers
    • 튜플의 버전 변화에 따라 변화하지 않는 논리적인 식별자를 인덱스 엔트리에 사용한다.
    • 데이터베이스는 논리적인 식별자를 버전 체인의 head로 변환하기 위한 indirection layer를 필요로 한다.
    • Primary Key (PKey): 튜플의 primary key를 논리적인 식별자로 사용하거나,
    • Tuple Id (TupleId): 별도의 식별자를 발급하여 사용하는 방법이 있다.
  • Physical Pointers
    • 특정 버전의 물리적인 포인터를 인덱스 엔트리에서 사용하는 방법이다.
    • 어떤 튜플이 업데이트 될 때는, 모든 인덱스에 새로 생성된 버전을 추가해야한다.

디스커션

  • 일반적인 믿음과는 달리 동시성 제어 프로토콜 보다 버전 스토리지 방식이 인메모리 MVCC 데이터베이스의 scalability에 있어서 가장 중요한 부분이었다.
    • Delta storage 방식이 메모리 할당 방식과 상관없이 높은 성능을 보여주었다. 특히 튜플의 일부만이 수정될 때 효율적이고, 반면 테이블 스캔에 있어서는 낮은 성능을 보여주었다.
  • 워크로드에 알맞는 동시성 제어 프로토콜을 사용함으로써 성능을 개선할 수 있으나, 전반적으로 여러 워크로드에 대해서 MVTO가 좋은 성능을 보여주었다.
  • Transaction-level GC가 가장 좋은 성능을 보여주었다.
  • Logical pointer 방식이 높은 성능을 보여주었다.

내가 배운 것 & 생각한 것

  • 데이터베이스 마다 MVCC를 구현하는 방식 자체가 여러가지 디자인 결정에 따라 달라질 수 있고, 그에 따라 성능도 상당히 달라질 수 있느 점을 알았다.
  • MVCC에 대한 4가지의 디자인 결정과 각각마다 가능한 옵션에 대해서 비교적 상세히 이해할 수 있게 되었다.
  • 각각의 디자인 결정이 완전히 독립적인 것도 아니거니와, 캐시 레벨의 성능 최적화를 해야하는 인메모리 데이터베이스 특성상, 한번 결정한 디자인 선택을 구현 후 바꾸는 것은 매우 어려운 결정이 될 것이다. 자신의 데이터베이스를 구현한다면 그 데이터베이스가 앞으로 처리해야할 워크로드에 대해서 이해하고, 이에 적합한 디자인 결정하는 것이 매우 중요한 일인 것 같다.

Paper: Main Memory Database Systems: An Overview

H. Garcia-Molina and K. Salem. 1992. Main Memory Database Systems: An Overview. IEEE Trans. on Knowl. and Data Eng. 4, 6 (December 1992), 509-516. (PDF)

요약

1991-1992년에 쓰여진 이 페이퍼는 당시 인메모리 데이터베이스 시스템에 대한 연구들과 프로토타입 인메모리 데이터베이스들에 대한 서베이 페이퍼라고 할 수 있다.

Introduction

먼저 인메모리 데이터베이스 시스템에 대한 흔한 질문들에 대해서 답하고 있다.

전체 데이터가 메인 메모리에 들어갈 것이라 가정하는 것은 합당한가?

  • 어떤 애플리케이션의 경우에는 데이터의 크기가 메모리 용량의 증가보다 더 느린 속도로 증가할 수도 있고, 어떤 애플리케이션의 경우에는 실시간 제약이 있어서 반드시 메모리 상에 적재되어야 한다.
  • 하지만, 메모리에 적재될 수 있는 애플리케이션도 존재하므로, 이러한 경우, 하나 이상의 데이터베이스 시스템에 저장하고 가장 액세스 빈도가 높은 종류의 데이터를 인메모리 데이터베이스에 저장하는 것을 고려할 수 있고, 실제로도 IMS의 사례에서 이를 보여주고 있다.

인메모리 데이터베이스와 매우 커다란 캐시를 가진 디스크 기반 데이터베이스의 차이점은 무엇인가?

충분히 커다란 캐시를 가지고 있다면 데이터가 항상 메모리 상에 존재하겠지만, 메모리의 장점을 전부 활용하지는 못한다.

  • B-tree와 같이 디스크 액세스를 위해 설계된 인덱스 구조를 가진다.
  • 디스크에 존재할 수 있는 데이터를 액세스하기 위해서, 메모리 상의 데이터를 액세스할 때에도 버퍼 매니저를 사용해야 한다.

특수한 하드웨어를 도입함으로써 메인 메모리가 nonvolatile하다고 가정할 수 있는가?

  • 배터리가 들어간 메모리 보드, UPS 등을 통해서 더 나은 신뢰성을 제공할 수 있지만, 장애의 가능성을 0으로 줄여주지는 못한다.
  • 하지만, 신뢰성이 높아진다면 백업의 빈도 등을 줄여줌으로써 성능 개선에 기여할 수 있다.
  • 배터리가 들어간 메모리 보드나 UPS는, 디스크와 달리 신뢰성을 보장하기 위해 어떤 일을 해야하는 ‘active’한 컴포넌트이므로 장애의 가능성에 기여한다.
  • 백업 메커니즘의 성능이 인메모리 데이터베이스 시스템에 있어서 매우 중요할 것이다.

Impact of Memory Resident Data

Concurrency Control

  • 인메모리 데이터베이스에서 트랜잭션은 디스크 기반 데이터베이스에 비해서 짧아지므로 lock contention도 상대적으로 적을 것이다.
  • 따라서, 인메모리 데이터베이스의 경우 좀 더 큰 lock granularity를 선택할 수 있고, 이를 통해 동시성 관리의 비용이나 CPU cache flush의 비용을 크게 줄일 수 있다.
  • 하지만, 여전히 짧은 트랜잭션과 수명이 긴 트랜잭션이 동시에 수행될 수 있도록 하기 위한 방법이나 멀티프로세서 시스템을 활용하기 위한 방법은 필요하다.
  • 전통적인 데이터베이스에서 lock table 대신, 오브젝트 자체의 1-2 bit를 사용해서 lock을 구현할 수 있다.

Commit Processing

  • 메모리는 volatile하기 때문에 commit 전에 디스크에 로깅을 하는 것이 필요한데, 디스크 액세스는 인메모리 데이터베이스 시스템에서 커다란 성능 bottleneck을 유발할 수 있다.
    • 디스크에 비해 상대적으로 빠르고 작은 stable memory를 도입해서 로그의 일부를 저장할 수 있다. 트랜잭션과 별도로 stable memory에 쓰여진 로그를 디스크에 기록하는 프로세스가 존재할 수 있다.
    • Precommitting – 로그가 디스크에 쓰여지기 전에 트랜잭션의 lock들을 릴리즈하는 방식 – 을 사용해서, lock contention을 줄여 다른 트랜잭션의 응답시간을 개선할 수 있다.
    • Group commit – 복수의 트랜잭션의 로그들을 메모리에 모아뒀다가 한번에 디스크로 flush하는 방식 – 을 사용해서 로깅 bottleneck을 완화할 수 있다.

Access Methods

  • 인메모리 데이터베이스의 인덱스 구조를 위해 여러가지 형태의 해싱과 T-tree와 같은 트리들이 제안되고 있다.
  • 그러한 인덱스 구조들은 공통적으로, 데이터 자체가 아니라 데이터로의 포인터를 저장함으로써 메모리의 이점을 잘 활용하고 있다.

Data Representation

  • 튜플은 데이터로의 포인터 집합으로 표현될 수 있다.
  • 커다란 데이터가 반복적으로 나타난다면 중복 저장하지 않음으로써 공간 효율을 높일 수 있다.
  • 가변 길이 데이터를 포인터로 표현함으로써 데이터구조 디자인을 단순화할 수 있다.

Query Processing

  • 데이터에 대한 포인터 메커니즘을 이용해서 어떤 오퍼레이션을 매우 효율적으로 수행할 수 있다.
    • 예를 들어, 두 테이블을 하나의 attribute를 기준으로 join하려는 경우 그 데이터를 사용하는 튜플로의 포인터를 통해서 엄청나게 효율적으로 join을 수행할 수 있다.
  • 전통적인 데이터베이스에서는 디스크 액세스를 줄이려고 했지만, 인메모리 데이터베이스에서는 CPU 비용을 줄이는 것에 집중해야한다.

Recovery

  • 인메모리 데이터베이스에서는 트랜잭션들은 메모리 상의 데이터만을 이용하므로, 체크포인팅이나 복구가 디스크 상의 데이터를 액세스하는 유일한 이유다.
    • 따라서, 인메모리 데이터베이스에서는 체크포인팅에 최적화해서 매우 커다란 블럭 사이즈를 사용할 수 있다.
  • 복구할 때 많은 양의 데이터를 읽어들여야 하는 문제를 해소하기 위해서 필요한 데이터 블럭부터 로드하거나 여러 개의 디스크로부터 병렬적으로 로드하는 방법을 고려할 수 있다.

Systems

IBM에서 개발한 상용 제품인 Fast Path 이 외에 몇가지의 인메모리 데이터베이스 연구용 프로토타입들에 대해서 간단히 소개하고 있다.

내가 배운 것 & 생각한 것

  • 나도 품어왔던, 인메모리 데이터베이스에 대해서 가장 기본적인 질문들 – 특히, “충분히 많은 메모리 캐시를 가진 디스크 기반 DB를 쓰면 되잖아?” – 에 대해서 명확하게 답하고 있다.
  • 전통적인 데이터베이스 아키텍처 상의 각각의 모듈 또는 기능들에 대해서 인메모리 데이터베이스는 어떻게 다른지, 그리고 어떤 해결책을 고려할 수 있는지를 비교적 짧지만 매우 쉽게 이해할 수 있도록 쓰여져있다.
    • 인메모리 데이터베이스 시스템에서 고려해야할 빅 픽처를 이해하는 데 도움이 된다는 의미에서 도움이 되었다.
    • “OLTP Through the Looking Glass, and What We Found There” 리뷰에서 언급한 것과 마찬가지로, 구체적인 해결책에 대해서는 다양한 문맥에서 더 나은 진척들이 있기 때문에 이 페이퍼에 쓰여진 것만을 고려해서는 안된다.
  • 1992년 이후로 여러가지 변화 – 하드웨어의 발전, OS 및 프로그래밍 시스템의 발전, 인메모리 데이터베이스 분야의 연구 – 가 있었기 때문에, 몇몇은 현재 시점에서는 유효하지 않은 것 같다.
    • Optane DC Memory와 같은 non-volatile memory가 제품화되고 있으므로, 이제 ‘passive’한 메모리 하드웨어가 생겨났다고 할 수 있다.
    • 결국 many-core 시스템의 이점을 잘 활용하기 위해서는 여전히 lock granularity는 중요한 것 같다. 다만, 데이터베이스 lock granularity를 가진 KeyDB가 좋은 성능을 보여주는 것을 보면 완전히 틀린 말은 아니다.
    • optimistic concurrency control에 대해서는 많이 언급하지 않고 있다.
    • 이 페이퍼에서는 CPU 비용을 측정하는 것이 어렵다고 언급되어 있으나, 이후로 CPU 비용에 대해서 측정하는 방법이 많은 발전을 이루었다.