[데이터베이스] 데드락과 팬텀현상을 해결 위한 동시성 제어 프로토콜의 종류 (deadlock, 교착상태, Phantom, Granularity)

[데이터베이스] 데드락과 팬텀현상을 해결 위한 동시성 제어 프로토콜의 종류 (deadlock, 교착상태, Phantom, Granularity) - Index Locking, Next-Key Locking Protocol

코딩하는 동현 2025. 6. 6. 02:50

Deadlock Handling

Deadlock이란 transaction들의 집합에서 각 transaction이 집합 내의 다른 transaction을 기다리고 있는 상황이다. 이러한 deadlock 상황을 처리하는 방법에는 prevention, detection, recovery가 있다.

Deadlock Prevention

Deadlock prevention protocol은 시스템이 deadlock 상태에 절대 진입하지 않도록 보장하는 기법들이다.

1. Pre-declaration 방식

각 transaction이 실행을 시작하기 전에 필요한 모든 data item들을 미리 lock하는 방법이다.

2. Graph-based Protocol

모든 data item에 partial ordering을 부과하고, transaction이 오직 그 순서대로만 data item을 lock할 수 있도록 하는 방법이다.

3. Wait-die Scheme (Non-preemptive)

오래된 transaction은 새로운 transaction이 data item을 release할 때까지 기다릴 수 있다
새로운 transaction은 오래된 transaction을 절대 기다리지 않고 대신 rollback된다
Transaction이 lock을 획득하기 전에 여러 번 die할 수 있다

4. Wound-wait Scheme (Preemptive)

오래된 transaction이 새로운 transaction을 wound(강제 rollback)시킨다
새로운 transaction은 오래된 transaction을 기다릴 수 있다
Wait-die보다 rollback이 적다

두 방식 모두에서 rollback된 transaction은 원래의 timestamp로 재시작되며, 오래된 transaction이 새로운 것보다 우선권을 가져 starvation이 방지된다.

5. Timeout-based Schemes

Transaction이 정해진 시간 동안만 lock을 기다리고, 시간이 초과되면 rollback되는 방법이다. 구현이 간단하지만 deadlock이 없는 상황에서도 불필요하게 rollback이 발생할 수 있고, 적절한 timeout 값을 결정하기 어렵다.

Deadlock Detection

Wait-for Graph

Vertex: transaction들
Edge: Ti가 Tj가 conflicting mode로 보유한 lock을 기다리는 경우 Ti → Tj
Wait-for graph에 cycle이 있으면 deadlock이 발생한 것이다

주기적으로 deadlock detection algorithm을 호출하여 cycle을 찾는다.

Deadlock Recovery

Deadlock이 감지되면 일부 transaction을 victim으로 선택하여 rollback시켜 deadlock cycle을 깬다.

Victim 선택

최소 cost를 발생시킬 transaction을 victim으로 선택한다.

Rollback 방식

Total rollback: Transaction을 abort하고 재시작
Partial rollback: Cycle 내의 다른 transaction이 기다리는 lock을 release할 때까지만 rollback

Starvation이 발생할 수 있으며, 이를 해결하기 위해 deadlock set에서 가장 오래된 transaction은 victim으로 선택하지 않는 방법이 있다.

Multiple Granularity

Data item들이 다양한 크기를 가질 수 있도록 하고 data granularity의 hierarchy를 정의한다.

작은 granularity는 큰 것들 안에 nested된다.

Transaction이 tree의 node를 명시적으로 lock하면, 그 node의 모든 descendant들도 같은 mode로 암시적으로 lock된다.

Granularity 특성

Fine granularity (tree의 하위)

높은 concurrency, 높은 locking overhead
부모 노드를 락하고 하위 노드로 진입하고 락하고, 부모 락을 해제하는 등이 반복되므로 높은 오버헤드를 가진다.
그러나 하위 노드 락을 했을때 다른 노드들은 영향을 안받기 때문에 병렬 수준이 높다.

Coarse granularity (tree의 상위)

낮은 locking overhead, 낮은 concurrency
부모 노드를 락하는 방식이어서 오버헤드가 낮지만, 그 부모의 하위 노드는 다른 트랜잭션이 접근 못한다.

Intention Lock Modes

S와 X lock mode 외에 multiple granularity를 위한 추가적인 lock mode들이 있다:

IS (Intention-Shared): Tree의 하위 level에서 shared lock만으로 명시적 locking이 이루어짐을 나타낸다
IX (Intention-Exclusive): 하위 level에서 exclusive 또는 shared lock으로 명시적 locking이 이루어짐을 나타낸다
SIX (Shared and Intention-Exclusive): 해당 node를 root로 하는 subtree가 shared mode로 명시적으로 lock되고, 하위 level에서 exclusive-mode lock으로 명시적 locking이 이루어짐을 나타낸다

Intention lock은 모든 descendant node를 확인하지 않고도 상위 level node를 S 또는 X mode로 lock할 수 있게 한다.

Lock compatibility matrix

Multiple Granularity Locking Scheme

Transaction Ti가 node Q를 lock하는 규칙들이다:

Lock compatibility matrix를 준수해야 한다
Tree의 root를 먼저 lock해야 하며, 어떤 mode로든 lock할 수 있다
Node Q를 S 또는 IS mode로 lock하려면 Q의 parent가 IX 또는 IS mode로 lock되어 있어야 한다
1. 부모에 IS 또는 IX 락이 이미 걸려 있으면,“내가 하위(자식) 노드에서 읽기(또는 쓰기) 작업을 하려는 의도가 있다”는 신호가 된다.
Node Q를 X, SIX, 또는 IX mode로 lock하려면 Q의 parent가 IX 또는 SIX mode로 lock되어 있어야 한다
1. 부모에 IX 또는 SIX 락이 있으면, “내가 하위 노드에서 쓰기 작업을 하려는 의도가 있다”는 것을 명확히 표시한다.
Ti는 이전에 어떤 node도 unlock하지 않은 경우에만 node를 lock할 수 있다 (two-phase)
1. 이 규칙은 Two-Phase Locking(2PL) 프로토콜을 따르기 위한 것이다.
Ti는 Q의 children 중 어느 것도 현재 lock되어 있지 않은 경우에만 node Q를 unlock할 수 있다
1. 만약 자식에 락이 남아 있는데 부모 락을 풀면, 상위 노드의 보호 없이 하위 노드에서 작업이 진행되어 동시성/일관성 문제가 발생할 수 있다.

Lock은 root-to-leaf 순서로 획득되고, leaf-to-root 순서로 release된다.

특정 level에서 너무 많은 lock이 있는 경우 상위 granularity의 S 또는 X lock으로 전환하는 lock granularity escalation이 가능하다.

Insert/Delete Operations and Predicate Reads(range 쿼리)

Insert/Delete Operations의 Locking 규칙

Item이 delete되기 전에 exclusive lock을 획득해야 한다. Database에 새로운 tuple을 insert하는 transaction은 자동으로 해당 tuple에 대해 X-mode lock을 부여받는다.

이러한 규칙들은 다음을 보장한다:

Read/write가 delete와 conflict한다
Insert된 tuple은 insert한 transaction이 commit할 때까지 다른 transaction들이 접근할 수 없다 -> 접근 시 팬텀read 현상이 일어난다.

Phantom Phenomenon

동일한 쿼리를 반복했을 때, 트랜잭션 도중에 다른 트랜잭션의 삽입으로 인해 결과 행의 개수가 달라지는 현상이다

Phantom phenomenon의 예시이다. Transaction T1이 relation의 predicate read(또는 scan)을 수행한다:

select count(*)
from instructor
where dept_name = 'Physics'

Transaction T2가 T1이 활성화되어 있지만 predicate read 이후에 tuple을 insert한다:

insert into instructor values ('11111', 'Feynman', 'Physics', 94000)

이 두 transaction은 공통된 tuple에 접근하지 않음에도 불구하고 개념적으로 conflict한다.

Tuple lock만 사용하면 non-serializable schedule이 발생할 수 있다. 예를 들어, scan transaction은 새로운 instructor를 보지 못하지만 update transaction이 작성한 다른 tuple을 읽을 수 있다.

Update에서도 발생할 수 있다. 예를 들어 Wu의 department를 Finance에서 Physics로 update하는 경우이다.

Handling Phantoms

Data level에서 conflict가 존재한다.

Predicate read 또는 relation scanning을 수행하는 transaction은 relation이 포함하는 tuple들에 대한 정보를 읽고 있다.

Tuple을 insert/delete/update하는 transaction은 같은 정보를 update한다.

해결방법

Relation과 data item을 연결하여 relation이 포함하는 tuple들에 대한 정보를 나타낸다:

Relation을 scanning하는 transaction들은 data item에 shared lock을 획득한다
Tuple을 insert하거나 delete하는 transaction들은 data item에 exclusive lock을 획득한다

이 protocol은 insertion/deletion에 대해 매우 낮은 concurrency를 제공한다.

Index Locking Protocol

Phantom을 방지하기 위한 index locking protocol이다:

모든 relation은 최소 하나의 index를 가져야 한다
Transaction은 relation의 하나 이상의 index를 통해 tuple을 찾은 후에만 접근할 수 있다
Lookup을 수행하는 transaction Ti는 접근하는 모든 index leaf node를 S-mode로 lock해야 한다 (Leaf node가 index lookup을 만족하는 tuple을 포함하지 않더라도 마찬가지이다)
Relation r에서 tuple ti를 insert, update, delete하는 transaction Ti는:
- r의 모든 index를 update해야 한다
- Insert/update/delete에 영향받는 모든 index leaf node에 exclusive lock을 획득해야 한다
Two-phase locking protocol의 규칙을 준수해야 한다

검색 범위에 해당하는 모든 인덱스 리프 노드에 락을 걸면, 다른 트랜잭션이 그 범위에 새로운 행을 삽입하거나 삭제할 수 없다.
따라서 첫 번째 쿼리와 두 번째 쿼리의 결과가 항상 같으므로 phantom phenomenon이 발생하지 않음을 보장한다.

Next-Key Locking Protocol

Index-locking protocol은 phantom을 방지하기 위해 전체 leaf node를 lock하기 때문에 많은 insert가 있는 경우 concurrency가 떨어질 수 있다.

이를 키값을 기준으로 락을 거는 방식으로 해결한 것이다..

Next-key Locking Protocol의 특징: 더 높은 concurrency를 제공한다

Index lookup을 만족하는 모든 value들을 lock한다 (lookup value와 일치하거나 lookup range에 포함되는 값들)
Index에서 next key value도 lock한다
Insert/delete의 경우에도 마찬가지이다
Lock mode: lookup의 경우 S, insert/delete/update의 경우 X
Insert, delete, update와 query conflict의 detection을 보장한다

제시된 B+-tree leaf node 예시에서 query predicate 7 ≤ X ≤ 16에 대해:

조건을 만족하는 값들(8, 11, 14)에 S-lock이 설정된다
Next key value인 18에도 lock이 설정된다
(i) 15를 insert하는 경우: 14와 18 사이에 삽입되므로 기존 lock과 conflict가 발생한다
(ii) 7을 insert하는 경우: 5와 8 사이에 삽입되므로 8에 설정된 lock과 conflict가 발생한다

검색 조건에 해당하는 값과 그 다음 값 사이의 갭까지 락을 걸기 때문에, 이 갭에 새로운 행이 삽입되는 것도 방지되므로 새로운 팬텀 행”의 등장을 막을 수 있다.

인덱스 기반 락킹이면 3~14를 담은 리프노드와 18~55페이지 리프노드, 즉 키1가 아닌 페이지 단위로 락킹을 하므로 동시성이 더 낮은 것이다.