[데베시] 15강

Transactions

Concurrency

Seriealizability

 

Transaction

- 사용자가 DB에 접근하고 변경하는 행동의 series, DB 작업의 논리적 단위, DB를 일관된 상태(consistent state)로 바꾸는 작업(but transaction을 수행 중에는 consistency가 깨질 수 있음)

- 2가지 상태

   - Failure : transaction이 중단 -> 중단되면 transaction 이전의 일관된 상태로 rollback되어야 함

   - Success : commit -> commit된다면 transaction 이전의 상태로 돌아가면 안됨

- ACID

   - Atomicity : transaction은 원자적으로 변해야 함.

   - Consistency : transaction의 결과는 항상 consistent한 상태여야 함.

   - Isolation : DB 안에서는 transaction이 동시에 수행될 때 다른 트랜잭션에 의해 영향받으면 안됨.

   - Durability : transaction이 성공적으로 commited되면 결과는 영구적으로 저장되고 나중에 누실되면 안됨.

- DBMS는 각각의 transaction이 ACID를 만족하도록 보조하는 기술을 제공

 

Concurrency Control

- 동시에 돌아가는 Transaction이 상호 간섭받지 않도록(Isolation을 만족하도록)해주는 제어 과정

- 필요한 이유 : 둘 이상의 transaction이 동시에 같은 DB를 접근할 때 최소 1개라도 data를 변경하고 있다면 중간에 잘못된 결과가 생성될 수 있기 때문에 이를 방지해야 함.

 

발생될 수 있는 문제

- Lost update problem

T1는 balance를 10만큼 줄이고 싶고 T2는 100만큼 늘이고 싶음. -> 원하는 결과 : 190이 되어야 함.

transaction 중 먼저 시작된 쪽의 update가 누실됨.

문제 : 하나의 Transaction이 update가 끝나기 전에 해당 자원에 접근이 가능했다.

-> 해결 방법 : T2의 update가 끝날 때까지 T1이 read를 할 수 없게 막기.

 

- Uncommited dependency problem

T3는 balance를 10만큼 줄이고 싶고 T4는 100만큼 늘이려다 취소함. -> 원하는 결과 : 90이 되어야 함.

T4가 rollback 하기 전에 T3가 값을 읽어가서 잘못된 값이 read됨

문제 : 하나의 Transaction이 완료되기 전에 중간 결과를 다른 Transaction에서 볼 수 있다.

-> 해결 방법 : T4가 commit되거나 rollback되기 전까지는 T3가 수행되지 않도록 막기.

 

- Inconsistent analysis problem (= dirty read)

T5는 balx에서 balz로 10을 이체하고 싶고 T6은 balx, baly, balz를 합친 결과를 얻고 싶음. -> 원하는 T6의 결과 : 175가 되어야 함.

문제 : T5의 update가 끝나기 전과 이후에 T6가 값을 읽어옴.

-> 해결 방법 : 둘 중 하나를 먼저 실행

 

-> Conflict(동일한 자원의 읽기와 쓰기가 혼재된 상황)에서만 동시제어의 필요성이 있음.

 

Serializability

- concurrency control의 목적은 inference가 발생하지 않도록 transaction을 schedule하는 것

- Serial하게 transaction을 처리하게 되면 동시성과 병행처리 정도를 제한해서 성능이 저하됨.

- Schedule : 주어진 concurrent transactions의 read, write를 한 줄로 표현한 sequence

 

- Serial Schedule : 다른 transaction의 간섭이 없이 연속적으로 transaction이 동작되도록 하는 schedule(모든 transaction이 순차적으로 실행)

-> 주의 : Serial Schedule은 순서에 따라 항상 같은 결과가 나오지 않음 ex) Concurrent Transaction T1, T2, T3가 있을 때 <T1, T2, T3>와 <T3, T2, T1>의 결과가 다를 수 있음. -> 그러나 어떠한 결과가 나오더라도 serial schedule은 correct한 것으로 간주함.

 

- Nonserial Schedule : Concurrent transaction의 operation들이 interleaved된 schedule(중간에 다른 Transaction으로 왔다갔다 할 수 있는 schedule)

-> 동시 수행이 되기 때문에 성능은 좋지만 concurrency control이 없으면 상호 간섭이 생겨 문제 발생 가능.

 

-> Serializability의 목적 : 상호 간섭이 없는 Nonserial Schedule을 찾는 것.

-> 그러한 Schedule을 Serialsiable Schedule이라고 함.

 

- 두개의 Schedule s1과 s2가 equivalent하다면

   -> s2의 모든 read와 s1의 대응하는 read는 같은 값을 가져온다.

   -> 마지막으로 DB에 작성하는 값은 s1과 s2가 서로 같은 값이다.

serial schedule의 값은 다를 수 있다 -> 그래도 둘 다 맞다고 간주

serializable schedule의 예

위와 같은 순서로 진행한다면 s1의 serial schedule과 동일한 값이 나옴. -> s1의 serializable schedule이라고 할 수 있음.

nonserializable schedule의 예

s1과도 s2와도 다른 값을 출력하므로 nonserializable

 

read와 write의 순서가 중요함

-> 만약 두개의 transaction이 서로 완전히 분리된 data를 읽거나 쓴다면 아무런 conflict가 없음.

-> 같은 data를 접근하더라도 둘 다 read만 한다면 아무런 confict가 없음.

-> 하나의 transaction은 write를 하는데 동시에 최소한 다른 하나는 read를 하면 confict가 발생 -> 순서가 중요

 

Precedence Graph (조건 : 값을 쓸 때는 먼저 해당 값을 읽어온 다음에 그 old value를 기반으로 작성)

- 각각의 Transaction을 Node로 표현함

- arc Ti -> Tj (Ti와 Tj가 순서대로 오는 serial schedule과 equivalent)를 그린다면

   -> Ti가 read(x)를 하고 Tj가 바로 다음으로 write(x)를 함.

   -> Ti가 write(x)를 하고 Tj가 바로 다음으로 Ti가 write한 x값을 read(x)를 함.

-> 만약 위와 같은 조건으로 precedence graph를 그렸을 때 cycle이 존재하지 않는다면 해당 schedule은 serializable하다.

 

Concurrency Control Techniques

- serializable schedule로 수행할 수 있도록 컨트롤해주는 기법

- Two-phase locking protocol, Timestamp ordering technique, Optimistic technique

 

Locking (Two-phase locking protocol)

- Transaction이 read하거나 write할 때 해당 data item에 대해 lock을 거는 것.

- read lock을 걸면 다른 transaction이 write하는 것을 제한함. (다른 transaction이 read하는 것은 허용) -> shared lock

- write lock을 걸면 다른 transaction이 read하는 것을 제한함. (다른 transaction이 write하는 것도 불허) -> exclusive lock

- Lock Compatibility matrix

Basic rule for locking : read lock이 있으면 read 가능, update 불가 / write lock이 있으면 read & update 가능

일부 시스템은 read lock을 가지고 있을 때 write lock으로 등급을 올릴 수 있음.

 

Incorrect Locking Schedule

locking rule에 따라 잘 했는데 결과가 nonserializable schedule이 나옴.

lock을 했지만 결과는 serializable하지 않음. -> 문제점 : lock을 hold하는 기간이 너무 짧았다.

-> Serializability를 보장하기 위해선 lock을 걸고 unlock하는 시점에 대한 추가적인 규약이 필요.

 

Two-Phase Locking (2PL) Protocol

- Growing phase : lock을 거는 것만 허용되고 다른 lock을 푸는 것은 허용 X

- Shrinking phase : lock을 푸는 것만 허용되고 새롭게 lock을 거는 것은 허용 X

-> transaction이 2PL을 따른다면 모든 lock operation은 첫번째 unlock operation보다 앞쪽에 있다.

-> 어떤 schedule이 2PL protocol을 만족하는 transaction만 가지고 있다면 serializable하다. (주의 : 2PL을 만족하지 않는 serialiazable schedule도 있음.)

 

ex) 2PL을 통해 Lost Update Problem 예방

 자연스럽게 serializable schedule이 됨.

ex2) Uncommited Dependency Problem 예방

ex3) Incorrect Analysis 문제

 

2PL의 문제점 - Cascading Rollback

2PL을 모두 따르고 있더라도 맨 처음 Lock을 건 transaction이 rollback을 하면 그 이후에 실행된 모든 transaction도 rollback을 해줘야 함. (T11이후에 일어난 T12, T13은 T11에서 수정한 값에 종속적이 되므로)

 

-> Cascading Rollback을 해결하기 위해서는 Strict 2PL Protocol을 준수해야 함

Strict 2PL Protocol : Transaction이 Lock을 걸었으면 무조건 Transaction이 종료되어 commit을 하거나 rollback을 하고 난 후인 Transaction이 끝나기 직전에 모든 lock을 풀어야 함.

 

 

Deadlock

둘 이상의 Transaction이 서로가 가지고 있는 lock을 released되기 전에 서로 요청하면 무한히 기다려야 함.

T14는 balx에 대한 write_lock을 가진 상태에서 baly에 대한 write_lock을 요청 -> T15가 가지고 있으므로 대기

T15는 baly에 대한 write_lock을 가진 상태에서 balx에 대한 write_lock을 요청 -> T14가 가지고 있으므로 대기

-> 무한 대기 상태 발생

-> 해결 방법 : DBMS가 transaction을 감시하다 deadlock 상황을 감지하면 둘 중 하나를 abort함.

DBMS는 Deadlock을 허용하나 감지되면 한 쪽을 abort

-> wait-for graph(WFG)를 그려서 Ti -> Tj(Ti가 Tj의 item lock이 해제되길 기다리는 상황) 을 그렸을 때 해당 그래프에 cycle이 존재하면 그것은 Deadlock을 가지고 있다는 뜻 -> WFG를 탐지해서 Deadlock을 깨줌.