[Database Systems] Transactions, Concurrency Control

Transactions

DB의 컨텐츠에 접근하거나 변경하기 위해 사용자 또는 애플리케이션에 의해 수행되는 일련의 Action

Transaction은 다음과 같은 두 가지의 결과를 낳을 수 있다.

1. Failure: Transaction 실패 시, 이전 상태로 회복

2. Success: Transaction 성공 시, 새로운 Consistent State로 전환

 

Properties of Transactions (ACID Properties)

Atomicity: Transaction안에 있는 모든 action이 성공하거나, 성공하지 않아야 함

Consistency: Transaction은 DB가 기존 Consistent State -> 새로운 Consistent State가 되게 함

Isolation: 한 Transaction은 다른 Transaction에 의해 영향을 받지 않는다.

Durability: Commit된 Transaction의 효과는 영구적이고, Commit 되어 남게 된 효과는 이후의 어떤 실패로 인해 없어지지 않는다.

 

DBMS의 Concurrency Control과 Recovery Facilities는 각각의 Transaction이 이러한 속성을 보존하도록 한다.

 

Concurrency Control

Transaction이 동시에 발생하 되, 서로 간섭하지 않도록 하는 과정. ACID중 Isolation 속성을 보존한다.

Concurrency Control은 여러 Transaction이 발생할 때, 적어도 하나는 DB에 있는 데이터를 업데이트 하려고 할 때, 그리고 Serial하게 Transaction을 수행했을 때의 결과와 Interleaving 했을 때 결과가 서로 다를 경우 필요하다.

 

Lost Update Problem

T1을 수행하고, T2를 Serial하게 수행했을 경우 bal_x의 값은 190이 된다. 하지만 위와 같이 Interleaving했을 경우 T2가 Update한 정보가 Lost된다.

T2의 업데이트가 완료될 때 까지 T1가 수행되지 않도록 하여 문제를 해결할 수 있다.

Uncommitted Dependency Problem

T3이 T4가 commit하지 않은 정보에 Dependency를 가지는 경우이다. 

T4가 Commit되거나 Abort될 때 까지 T3가 수행되지 않도록 하여 문제를 해결할 수 있다.

Inconsistent Analysis Problem

T5에서 bal_x를 10차감 시킨 결과를 T6에서 sum에 반영하려 했지만 bal_x를 차감한 결과가 적용되지 않은 상태에서 sum에 반영하여 문제가 발생한다.

T5가 완료되기 전 까지 T6이 bal_x와 bal_z에 접근하지 못하도록 하여 문제를 해결할 수 있다.

 

Serializability

Concurrency control의 목적은 Transaction간 상호 간섭이 없도록 Transaction에 있는 action들의 순서를 정하는 것이다.

Transaction 각각을 Serial하게 수행하면 결과는 문제가 없으나, 동시성/병렬성이 떨어진다.

Schedule: Concurrent한 Transaction에 있는 Action들을 나열한 것

Serial Schedule: Transaction에 있는 Action들이 다른 Transaction에 있는 Action들과 Interleaving되지 않도록 하면서 나열한 것. 여러 경우의 수의 결과가 다르라도 모두 옳다고 가정한다.

Nonserial Schedule: Interleaving되는 Transaction들에 있는 Action들을 나열한 것. 

Serializability의 목적은 Transaction들이 서로 간섭하지 않으면서 동시에 실행되게 하는 Nonserial Schedule을 찾는 것이다. 즉 어떠한 Serial Schedule과 결과가 동등한 Nonserial Schedule을 찾는 것이다. 그러한 Schedule을 Serializable하다고 한다.

두 Schedule S1와 S2가 있다고 하자. S2의 각 read가 접근하는 값이 이에 대응되는 S1의 각 read가 접근하는 값과 같고, 최종적으로 DB에 쓰여지는 S1의 write와 S2의 write가 서로 같다면 두 Schedule은 동등하다고 한다.

위의 Nonserial Schedule은 S1와 동등하다.

위의 Nonserial Schedule은 S1, S2 어느것에도 동등하지 않다.

 

두 Transaction이 서로 다른 Item에 대하여 read와 write를 하는 경우와 둘 다 read만 하는 경우에는 Conflict가 없다. 하지만 서로 같은 Item에 대하여 read와 write를 하는 경우에는 conflict가 발생한다.

Serializability를 검사하기 위해서 Precedence Graph를 그릴 수 있는데, 어떤 Item X에 대하여 T_i가 read를 수행 후 T_j가 write를 수행하거나, T_i가 write를 수행 후 T_j가 read를 수행하면 T_i -> T_j로 표시할 수 있다. 이는 이와 동등한 Serial Schedule에서 T_i가 T_j보다 먼저 수행되어야 함을 의미한다.  Precedence Graph에 Cycle이 존재하지 않는다면 그 Schedule은 Serializable하다.

 

Locking

Read Lock : 다른 Transaction에서 특정 Item에 대해 Write를 못하게 하는 것.

Write Lock : 다른 Transaction에서 특정 Item에 대해 Read & Write를 못하게 하는 것.

Locking을 사용했음에도 Schedule은 Serializable하지 않다. 그 이유는 Lock을 너무 일찍 해제하였고 해제 되자 마자 Item에 접근하여 문제가 생긴 것이다. 곱셈을 하고 덧셈/뺄셈 한것과 덧셈/뺄셈을 하고 곱셈을 하면 값이 다를 수 밖에 없다. 이를 해결하기 위한 방식이 Two-Phase Locking Protocol이다.

 

Two-Phase Locking (2PL) Protocol

Growing Phase: Lock을 잡는 Phase

Shrinking Phase: Lock를 푸는 Phase

한 Transaction의 모든 Locking은 첫번째(최초의) Unlocking보다 먼저 수행된다.

2PL을 따르는 모든 Schedule은 Serializable하다.

2PL을 따르지 않는 Schedule도 Serializable할 수는 있다.

 

Example

 

Cascading Rollback

T11이 Abort됨에 따라서 이에 의존하고 있는 T12이 Rollback되고 T12에 의존하는 T13도 Rollback되는 현상

이 현상은 Strict 2PL Protocol로 해결 가능하다.

Strict 2PL Protocol: Transaction이 끝남과 거의 동시에 Lock을 해제 (commit, rollback 직후에 unlock)

 

Deadlock

두 개 이상의 Transaction이 서로 상대쪽이 사용중인 것을 사용하기 위해 기다리며 아무것도 진행하지 못하고 있는 상황. DBMS의 Deadlock detection으로 두 Transaction 중 하나를 종료시킨다.

Deadlock detection은 Deadlock을 Wait-for Graph(WFG)로 탐지한다. T_i -> T_j라면 T_i가 T_j의 unlcok을 기다리는 상황이다. 만약 WFG에 Cycle이 존재하면 Deadlock이 존재하는 것이다.