Intro

이번 블로그 시리즈는 CMU 2019 Intro to database system에서 MVCC(Multiversion Concurrency Control) 부분에 대한 요약 정리로 진행하려고 합니다. 저도 대학교 때 같은 이름의 수업을 들었는데 저희 학교는 MVCC쪽은 많이 다루지 않았고 초점이 SQL 쿼리를 잘 작성하는데 더 많은 시간을 썼던 것 같습니다.
그래서 이 기회에 MVCC 복습할 겸, 관련된 부분을 강의를 듣게 되고 요약 정리 목적으로 이 글을 작성합니다.
CMU 강의로는 19번째 강의입니다.

들어가며

저번 블로그에서는 Optimistic Concurrency Protocol중 Basic TO, OCC, Partition-based TO에 대해서 알아보았습니다. 이 블로그에서는 드디어 MVCC에 대해서 알아볼겁니다. MVCC는 말 그래도 Concurrency Control이지 단순히 하나의 Concurrency Protocol이 아닙니다. MVCC를 구현하기 위해서 DBMS가 트랜스액션 및 디비 구현 자체가 고려되어야 합니다. 이 블로그에서는 MVCC란 무엇인지에 대해서 자세히 알아보도록 하겠습니다.

MVCC

MVCC란?

The DBMS maintains multiple physical versions
of a single logical object in the database:

1. When a txn writes to an object, the DBMS creates a new
   version of that object.
2. When a txn reads an object, it reads the newest version
   that existed when the txn started.

즉, MVCC를 요약하자면 "Writers don't block readers! Readers don't block writers" 입니다. Read-only txns can read a consistent snapshot without acquiring locks using timestamps to determine visibility. 즉, 앞에서 보았던 phantom read 등 여러 문제를 피할수 있습니다.

그렇다면 MVCC를 구현하는데 필요한 요소들은 어떻게 될까요?

1. Concurrency Control Protocol
2. Version Storage
3. Garbage Collection
4. Index Management

Concurrency Control Protocol

저희가 앞선 3개의 블로그를 통해서 공부한 바로 Concurrency Control Protocol 들이 바로 요기에 쓰입니다.

간단한게 짚고 넘어가자면 다음과 같습니다.

1. Timestamp Ordering
   → Assign txns timestamps that determine serial order.
2. Optimistic Concurrency Control
   → Three-phase protocol from last class.
   → Use private workspace for new versions.
3. Two-Phase Locking
   → Txns acquire appropriate lock on physical version before
   they can read/write a logical tuple

Version Storage

The DBMS uses the tuples’ pointer field to create a
version chain per logical tuple. This allows the DBMS to find the version that is visible to a particular txn at runtime. Indexes always point to the “head” of the chain. Different storage schemes determine where/what to store for each version.

Version Storage 방식은 다음과 같은 방식들이 있습니다.

1. Append-Only Storage
   → New versions are appended to the same table space.
2. Time-Travel Storage
   → Old versions are copied to separate table space.
3. Delta Storage
   → The original values of the modified attributes are copied
   into a separate delta record space.

Append-Only Storage

All of the physical versions of a logical
tuple are stored in the same table
space. The versions are mixed
together.
On every update, append a new
version of the tuple into an empty
space in the table.

이렇게 되면 각 tuple 마다 다른 version 들로 이루어진 linkedlist 가 생기게 되는데 linkedlist head를 어디에 두냐에 따라 다른 version chain ordering 방법이 생기게 됩니다.

1. Oldest-to-Newest(O2N): head가 가장 오래된 버젼입니다. 이러면 look-up때 chain을 traverse 해야되기는 합니다.

2. Newest-to-Oldest(N2O): head가 가장 새로운 버젼입니다. 이러면 매번 update때 index pointer를 새 head로 업데이트 해줘야 합니다.

Time-travel Storage

두 개의 table 을 가지고 있습니다(Main table vs Time-travel table)
Main table은 가장 최신값을 가지고 있는 table 이고 Time-travel table은 가장 최신을 포함한 모든 기록을 다 가지고 있는 table 입니다.

동작은 다음과 같이 두개의 step 으로 이루어집니다.
1. On every update, copy the current version to the timetravel table. Update pointers.
2. Overwrite master version in
the main table.
Update pointers

Delta Storage

두 개의 table 을 가지고 있습니다(Main table vs Delta Storage Segment)
Main table은 가장 최신값을 가지고 있는 table 이고 Deltag Storage Segment은 tuple의 어떤 데이터가 어떻게 update 되었는지를 기록하는 테이블입니다.

동작은 다음과 같습니다.
1. On every update, copy only the
values that were modified to the
delta storage and overwrite the
master version.

Garbage Collection

이번에는 Garbage Collecting에 대해서 알아보겠습니다.

Garbage Collecting이 필요한 이유? Storage를 무한정 쌓을수는 없기 때문
The DBMS needs to remove reclaimable physical
versions from the database over time.
1. No active txn in the DBMS can “see” that version (SI).
2. The version was created by an aborted txn.

그렇다면 여기서 질문은
1. How to look for expired versions?
2. How to decide when it is safe to reclaim memory?

방식은 크게 두가지가 있습니다.

1. Tuple-level
   1. Find old versions by examining tuples directly.
   1. Background Vacuuming vs Cooperative Cleaning
   1. Background Vacuuming: Separate thread(s) periodically
   scan the table and look for
   reclaimable versions. Works
   with any storage.
   2. Cooperative Cleaning:
   Worker threads identify
   reclaimable versions as they
   traverse version chain. Only
   works with O2N.
   
2. Transaction-level
   1. Each txn keeps track of its read/write set.
   The DBMS determines when all versions created
   by a finished txn are no longer visible.

Index Management

1. Primary Key Indexes: Primary key indexes point to version chain head.
   1. How often the DBMS has to update the pkey index
   depends on whether the system creates new versions
   when a tuple is updated.
   2. If a txn updates a tuple’s pkey attribute(s), then this is treated as an DELETE followed by an INSERT.

2. Secondary Key Indexes:

   1. Logical Pointers
      1. Use a fixed identifier per tuple that does not change.
      2. Requires an extra indirection layer.
      3. Primary Key vs. Tuple Id
   2. Physical Pointers: Use the physical address to the version chain head.

정리하며

실제로 MVCC들을 지원하는 여러 DBMS 들의 위 네가지(Protocol, Version Storage, Garbage Collection, Indexes)들 중 각자의 목적에 맞는 방법들을 택해서 사용하고 있습니다.

이걸로 나름 길었던 MVCC에 대해 알아보는 블로그 글 연재를 마치도록 하겠습니다. CMU 강의 뒷부분에 Distributed DB에 대한 부분이 있고 여기서 ACID중 Consistency가 어떻게 유지되는지 알아갈수 있는 방법이 있는데 이는 나중에 따로 조금 더 깊게 들어갈 주제라서 다른 블로그 시리즈로 다루어보도록 하겠습니다.

감사합니다!

Notes