in-memory databases

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