Paper: Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems

Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD ’15). Association for Computing Machinery, New York, NY, USA, 677–689. DOI:https://doi.org/10.1145/2723372.2749436 (pdf)

요약

HyPer의 MVCC 구현에 관한 페이퍼.

많은 DBMS들이 MVCC를 구현하고 있지만, 대부분의 경우, 직렬성 (Serializability)을 보장하기 보다는 이보다 더 약한 격리 수준인 스냅샷 격리 (Snapshot Isolation; SI) 만을 보장하고 있다. 일반적으로 스냅샷 격리를 직렬적으로 만들기 위해서는 높은 비용이 필요한 것으로 알려져있는데, 이 페이퍼에서는 적은 비용으로 직렬성을 보장하는 MVCC 구현을 제안하고 있다.

이 구현의 기본적인 접근은 메인 테이블에는 최신 버전을 유지하고 in-place update를 하되, 새로운 버전으로부터 오래된 버전 순서대로 (newest-to-oldest) 연결된 버전 벡터를 통해 이전 버전에 대한 액세스를 제공한다.

흥미로운 것은 아직 커밋되지 않은 트랜잭션에 의해 추가되는 버전이다. 위의 그림에서 Ty는 아직 커밋되지 않은 트랜잭션의 ID로 커밋된 시간과 구분하기 위해서 263 이상의 매우 큰 값으로 할당된다. Ty 트랜잭션에 의해 메인 테이블에서는 ‘7’이라는 값이 in-place update되고, 이 값은 Ty 트랜잭션에게만 보이는 값이 된다. 한편, 버전 벡터의 Ty에 해당하는 항목에는 Ty와 Ty 트랜잭션이 일어나기 전의 값이 저장된다. 따라서, T5 이후에 시작된 (Ty 이외의) 트랜잭션에서는 Ty 트랜잭션이 생성한 버전으로부터 ‘8’이라는 값을 얻게된다.

커밋되지 않은 데이터를 가진, 즉 트랜잭션 ID를 가진 버전이 존재하는 레코드에 대해 쓰기 오퍼레이션을 하려는 트랜잭션은 바로 중지되고 롤백된다.

Serializability Validation

직렬성을 보장하기 위해서 트랜잭션에서 일어난 읽기 오퍼레이션들이 다른 트랙잭션에 의해 영향을 받지 않았음을 보장하기 위한 검증 단계 (validation phase)를 필요로 한다.

기존의 방식은 주어진 트랜잭션의 모든 읽기 오퍼레이션을 기록하고, 트랜잭션이 끝나기 전에 다시 한번 읽기 오퍼레이션을 모두 수행함으로써 다른 트랜잭션으로부터의 영향이 없었음을 검증하는데, 이는 스캔이 많은 워크로드에서 굉장히 높은 비용을 요구하게 된다.

이 시스템에서는 Precision Locking이라는 오래된 기법을 이용하는데, 기본적으로 읽기 오퍼레이션이 아니라 읽기 오퍼레이션의 조건 (predicate)들을 기록하고, 검증단계에서는 해당 트랜잭션의 라이프타임 동안 발생한 트랜잭션들의 쓰기 오퍼레이션들이 읽기 오퍼레이션들의 조건과 겹치는 지를 확인하는 방식이다.

검증할 트랜잭션의 라이프타임 동안 발생한 트랜잭션들을 효율적으로 찾기 위해서 최근의 트랜잭션 리스트를 유지하고, 이 트랜잭션에 함께 저장된 undo 레코드를 통해서 쓰기 오퍼레이션들을 확인할 수 있다.

Efficient Scanning

스캔을 할 때 레코드별로 버전 벡터가 존재하는지 여부를 체크하는 것을 피하기 위해, 일정한 범위의 레코드들마다 버전 벡터가 존재하는 레코드의 범위를 저장하고 (VersionedPositions), 이를 통해 버전 벡터가 존재하지 않는 범위에서는 더 빠르게 스캔할 수 있도록 도와주는 메커니즘을 가지고 있다. 불필요한 버전들은 계속 가비지 컬렉션에 의해 제거되므로, 소수의 레코드들만이 버전을 가지고 있는 것을 가정하고 있다.

Evaluation

  • VersionPositions를 통해서 약 5배 가량의 스캔 throughput 개선이 이루어졌다.
  • 스냅샷 격리 (SI)에 대비해 직렬성을 보장하는 레코드 레벨 조건 로깅이나 애튜리뷰트 레벨 조건 로깅은 약 5-7%의 비용만을 요구했다.

내가 배운 것 & 생각한 것

  • 낙관적인 동시성 제어를 사용하는 MVCC 구현, OLTP/OLAP 둘다에 최적화, LLVM을 이용한 코드 생성 등의 기능들이 상용화되는 인메모리 데이터베이스 구현에서 많이 보이고 있다.
  • Precision locking을 이용한 낙관적인 트랜잭션의 검증은 듣고나면 당연한 것 같지만, Hyper의 독특한 방식이라고 생각한다. 기존의 데이터베이스에서 반드시 이런 접근을 할 필요는 없었다고 생각하는데, 포인트 쿼리와 업데이트들 만으로 구성된 OLTP 트랜잭션이라면 읽기 집합 (read set)을 이용한 검증이 그리 비효율적이지는 않다고 생각된다. 대량의 스캔을 포함한 OLAP 트랜잭션에 대해서는 2번의 읽기를 하는 것만으로도 비용이 굉장히 높아지므로, 이것을 최근의 트랜잭션 리스트를 유지하는 비용 및 쓰기 집합 (write set)의 크기에 따른 성능 저하와 트레이드 오프한 것으로 볼 수 있는 것 같다.
  • 우리가 흔히 사용하는 데이터베이스에서는 스냅샷 격리를 사용하는 것이 보편적이고 그 이상은 비용효율적이지 않다는 선입견을 가지고 있었는데, 직렬성을 보장하면서도 충분히 좋은 성능을 보여주는 이 페이퍼를 본 후에 그러한 선입견을 깰 수 있었다.

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