MVCC 공부해보기 - 1

이동훈·2023년 1월 25일

데이터베이스

목록 보기

1/4

Intro

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

Transaction

먼저 우리가 잘 알고 있는 트랜스액션에 대해서 간단히 다시 정의하고 넘어갑시다. Transaction 이란 "A transaction is the execution of a sequence of
one or more operations (e.g., SQL queries) on a
database to perform some higher-level function." 로 정의할수 있습니다. 즉, 하나의 데이터베이스에 대해 여러 개의 operation 들의 묶음인 트랜스액션입니다. 조금 더 이론적으로 정의한다면 "A sequence of read and write operation"이라고 정의할수 있겠죠. 그리고 SQL에 관습적으로 트랜스액션은 BEGIN 으로 시작해서 COMMIT 혹은 ABORT 로 끝나게 됩니다.

ACID

여러개의 트랜스액션이 하나의 데이터베이스에 실행될때 가장 간단한 방법은 한번에 하나의 트랜스액션만 진행될수 있게(일종의 싱글스레드 느낌) 하는거지만 이렇게 하면 당연히 느립니다. 그리고 느린건 용납이 안되기 때문에 병렬적으로 여러개의 트랜스액션이 실행돌수 있는 방법을
생각해보죠. 먼저 방법론을 알아보기 전에 지켜야 할 원칙인 ACID 를 복습하고 갑시다.

Atomicity: All actions in the txn happen, or none happen

Consistency: If each txn is consistent and the DB
starts consistent, then it ends up consistent.

Isolation: Execution of one txn is isolated from
that of other txns

Durability: If a txn commits, its effects persist.

Constistency를 제외하고는 각각의 특성은 명확하게 이해됩니다. Consistency를 나중에 분산 데이터베이스를 알아볼때 자세히 다루고 여기에서는 가볍게 알고 넘어가도록 하죠.

A(Atomicity)

Logging(WAL)
Shadow Paging: DBMS makes copies of pages and txns make changes to those copies. Only when the txn commits is the page made visible to others.
(실제로 많이 쓰이지는 않는다. 왜냐하면 실제로 페이지에 대한 복사본을 만드는건 메모리적으로 비효율적이기 때문)

I(Isolation)

A concurrency control protocol is how the
DBMS decides the proper interleaving of
operations from multiple transactions.

Pessimistic: Don’t let problems arise in the first place.
Optimistic: Assume conflicts are rare, deal with them after they happen

여러 개의 트랜스액션이 동시에 실행될때 병렬적으로 처리하되 하나의 트랜스액션의 결과가 다른 트랜스액션의 영향을 받지 않게 각 트랜스액션들 안에서의 operation들의 순서들을 조율한는 방법

그럼 여기서 하나의 트랜스액션이 다른 트랜스액션에 의해 영향을 받지 않았는지를 어떻게 확인할까요?(How do we judge whether a schedule is correct?)

답은: If the schedule is equivalent to some serial
execution 입니다. 그렇다면 Serial Schedule이란 무엇일까요?

Serial Schedule: A schedule that does not interleave the actions of
different transactions.

Equivalent Schedules: For any database state, the effect of executing the first schedule is identical to the effect of executing the second schedule.

Serializable Schedule: A schedule that is equivalent to some serial execution of the transactions.

즉, 위에서 말한것처럼 트랜스액션이 다른 트랜스액션에 영향을 받지 않았을때를 Serial Schedule 이라 할수 있고 Equivalent Schedule은 여러개의 트랜스액션이 동시에 실행되고 있고 있지만 서로의 스케쥴에 영향을 끼치지 않는 스케쥴입니다. 즉, 우리가 하고 싶은 것들은 여러개의 트랜스액션들을 동시에 실행하면서 마치 Serial Schedule인것처럼 되게 하는것입니다.

그렇다면 병렬 처리라는것이 항상 가능할까요? 예를 들어 1번 트랜스액션이 A라는 row를 update한 후에 read하고 싶고 2번 트랜스액션이 같은 A를 지우고 싶어한다면 단순 병렬처리가 가능한 구조일까요? 당연히 아니겠죠. 이럴때는 순서가 정해져 있어야 하고 1번 혹은 2번 트랜스액션의 액션이 끝날때까지 기다릴수 있어야 합니다. 이런 병렬 처리가 되지 않는 Conflict는 크게 세 가지 종류가 있습니다.

Read-Write Conflicts (R-W): Unrepeatable reads(하나의 트랜스액션 안에서 read만 두 번 했는데 각각 값이 다른 경우)
Write-Read Conflicts (W-R): Dirty read(reading uncommitted data)
Write-Write Conflicts (W-W): Overwriting uncommitted data

위 Conflict들을 제어하기 위해서 아래와 같은 2가지 종류의 Serializability를 가지게 됩니다.
1. Conflict Serializability(대부분이 이거를 택한다)
2. View Serializability

Schedule S is conflict serializable if you are able to transform S into a serial schedule by swapping consecutive non-conflicting operations of different transactions.

여러개의 트랜스액션이 conflict 발생할때 이를 빠르게 알아차리는 방법: Precedence Graph(하나의 트랜스액션이 하나의 노드이고 conflict 가 발생하는 트랜스액션끼리 연결을 한다)