Lock-Based Protocol은 database system에서 여러 트랜잭션의 공유 자원에 대한 동시 접근을 제어하기 위한 방법 중 하나이다. 각 트랜잭셔은 공유 자원에 접근하기 위해서는 Lock을 획득해야한다. 이때 공유 자원에 대한 Lock 방식은 두 가지가 있다.
- Exclusive mode(X) : 공유 자원에 대한 WRITE, READ 연산이 가능하다. X-Lock은 lock-x 명령으로 요청할 수 있다.
- Shared mode(S) : 공유 자원에 대한 READ 연산만 가능하다.S-Lock은 lock-s 명령으로 요청할 수 있다.
※ concurrency-control-mananger : Lock 요청은 ccm에서 담당하고, 승인 혹은 거절을 통해 동시성 제어를 한다.
Lock-compatibility matrix
- 한 트랜잭션이 Shared lock을 가지고 있다면 어떤 트랜잭션도 Shared lock을 획득할 수 있다. -> Compatible
- 하지만 어떤 트랜잭션이 Exclusive lock을 가지고 있다면 다른 트랜잭션은 해당 공유자원에 대해 어떠한 lock도 획들할 수 없음.
Schedule with Lock Grants
다음 Lock을 요청하고 승인하는 과정까지 포함한 Schedule입니다. 각 트랜잭션은 공유자원을 사용하기 전에 ccm에 락을 요청하고 grant를 받아 사용합니다. 하지만 Lock-based protocol을 지켰다고 해서 해당 schedule이 serializable하다고 할 수 없습니다. T1의 write(A)와 T2의 read(A)가 conflict하기 때문입니다.
Two-Phase Locking Protocol
줄여서 2PL 프로토콜은 conflict-serializable schedule을 보장합니다.
Phase 1 : Growing Phase
- 트랜잭션은 Lock을 획득할 수 있습니다.
- 트랜잭션은 Lock을 놓을 수 없습니다.
Phase 2 : Shrinking Phase
- 트랜잭션은 Lock을 놓을 수 있습니다.
- 트랜잭션은 Lock을 획득할 수 없습니다.
즉 Phase 1에서는 Lock의 수가 증가하고, 트랜잭션이 마지막으로 lock을 얻는 지점인 lock points를 지나 Lock의 수가 감소하는 Phase 2에 진입합니다.
2PL Protocol을 적용하면 다음과 같이 T1에서 unlock(B), T2에서 unlock(A)은 아직 필요한 락을 얻지 못 했기 때문에 할 수 없다. 이 상황에서 T2에서 lock-S(B)를 요청하고 마찬가지로 T1에서 lock-X(A)를 요청하면 각 요청은 현재 lock-X(B)와 lock-S(A)가 걸려 있어 compatible 하지 않아서 CCM에서 Grant하지 못한다. 즉 T1 과 T2는 데드락에 빠진다.
2PL 프로토콜을 적용하면 데드락에 빠질 수는 있지만 해당 Scheudle을 conflict-serializable 하게 보장할 수 있다.
-
Strict 2PL : commit/abort 시점까지 모든 exclusive lock을 가지고 있어야 한다.
-
Rigorous 2PL : commit/abort 시점까지 모든 lock을 가지고 있어야 한다.
Deadlock(교착상태)
T3는 lock-X(B)를 가지고 있고 T4는 lock-S(B)를 가지고 있을 때, T3는 lock-X(A)를 T4는 lock-S(B)를 요청하면 각 요청은 compatible 하지 않기 때문에 grant 될 수 없다. 즉 다른 트랜잭션이 해당 lock을 놓아줄 때까지 기다려야 한다. 하지만 서로가 서로의 lock을 요청하고 있기 때문에 어느 한 트랜잭션이 rollback되지 않는한 진행이 불가능하다. 이러한 상태를 Deadlock이라고 한다.
Deadlock Handling
데드락이 발생했을 때 해결하는 방법에 대해서 알아보자.
Deadlock Prevention
-
Pre-Declaration
데드락 Prevention 프로토콜은 시스템이 절대로 데드락에 빠지지 않도록 한다. 방법은 트랜잭션을 실행하기전에 필요한 lock에 대한 정보를 모두 수집한다. 이렇게 수집한 정보를 바탕으로 데드락이 걸리지 않게 락을 제공한다. 하지만 이 방식은 실현성이 떨어진다. 왜냐하면 보통 트랜잭션의 필여한 락 정보는 런타임에 결정되기 때문에 사전에 락 정보를 얻는 것은 어렵다. -
wait-die (non-preemptive)
T1(Older Transaction) , T2(Younger Transaction)
이 방식은 오래된 트랜잭션은 기다리지만 젊은 트랜잭션은 기다리지 않고 죽는 것.
이렇게 해서 T1 -> T2 는 성립하지만 T1 < - T2는 성립하지 않기 때문에 데드락이 발생하지 않는다.
- T1이 만약 T2가 가지고 있는 락을 필요로 한다면 T2가 해당 락을 release할 때까지 기다린다.
- T2가 만약 T1이 가지고 있는 락을 필요로 한다면 T2는 기다리지 않고 바로 죽는다(roll back)
- 트랜잭션은 락을 얻기 전까지 몇 번 죽을 수 있음.
- wound-wait (preemptive)
T1(Older Transaction) , T2(Younger Transaction)
이 방식은 오래된 트랜잭션은 자신이 필요한 락이 젊은 트랜잭션이 가지고 있으면 젊은 트랜잭션을 죽이고(roll back) 해당 락을 얻는다.
T1 - > T2 성립 X , T1 < - T2 성립 O
- T1이 만약 T2가 가지고 있는 락을 필요로 한다면 T2를 ROLL BACK 시키고 해당 락을 얻는다.
- T2가 만약 T1이 가지고 있는 락을 필요로 한다면 해당 락을 T1이 놓을 때까지 기다린다.
- Wait-die 방식보다 roll back이 적게 발생한다.
wait - die와 wound - wait에서 중요한 것은 timestamp이다. timestamp는 자신이 얼마나 오래되었는지에 대해 기준이 된다. 이 때 각 방식에서 roll back된 트랜잭션은 새롭게 timestamp를 받는 것이 아니라 roll back 되기 전 기존에 timestamp를 유지한다. 따라서 roll back된 트랜잭셔은 자연스럽게 오래된 트랜잭션이 되고 자신이 요구하는 락은 얻을 수 있게 된다.(기아 문제 해결)
- Timeout-Based
정해진 시간동안 lock을 기다리다가, lock을 얻지 못하면 스스로 roll back하는 방식 -> 이 방식은 이론적으로 기아 발생 가능. 그리고 시스템상 잠깐 문제 생겨서 lock grant하는 데 오랜 걸린 것 뿐인데 데드락 걸린 줄 알고 roll back 할 수 도 있음 (live lock 이라고 함) -> Timeout interval을 잘 정해야함.
Deadlock Detection
Wait-for graph
- 정점 : 트랜잭션
- 간선 : Ti - > Tj , Ti 가 Tj가 가지고 있는 lock을 기다리는 상태
-> wait-for graph에서 사이클이 발생하면 데드락이 발생한 것. 시스템은 주기적으로 사이클을 검사함.
=> cost가 너무 비쌈. 동적으로 graph가 바뀌기 떄문에 node,edge 를 계속해서 삽입, 삭제 해야함.
Deadlock Recovery
데드락이 탐지되면 몇몇 트랜잭션은 victim으로 선정되어 roll back 될 것임. (데드락 cycle을 끊기 위해)
-> victim 정하는 것은 최소한의 코스트를 발생시키는 트랜잭션으로 정함
roll back 방식
1. Total roll back : 트랜잭션을 abort시키고 재시작
2. Partial roll back : 데드락이 발생 되기 전까지 roll back,
