Concurrency Control

실제 DBMS에서는 미리 정해진 프로토콜을 통해 동시성을 제어한다. 다음은 대표적인 동시성 제어 프로토콜이다.

• Lock-Based Protocols(Pessimistic Concurrency Control)
• Timestamp-Based Protocols
• Validation-Based Protocols(Optimistic Concurrency Control)

Lock-Based Protocols

Lock-Based Protocols은 데이터마다 lock을 설정하여 동시성을 제어하는 방법으로, 각 트랜잭션은 데이터에 대한 lock을 얻어야만 데이터에 접근할 수 있다.

LBP에서 사용하는 락의 종류는 Exclusive Lock(lock-X)과 Shared Lock(lock-S) 두 가지이다. Xlock은 해당 데이터를 독점하는 락으로 read와 write모두 가능한 반면, Slock은 데이터를 공유할 수 있는 락으로 read만 가능하다. 만약 둘 이상의 트랜잭션이 동일한 데이터에 대해 락을 요청한다면 요청하는 락의 종류에따라 락을 얻거나 얻지 못할 수 있는데, 이 관계를 나타낸 것이 Lock-compatibility matrix(Lock 호환성 매트릭스)이다.

위 표에 따르면 하나의 데이터에 대해 여러 트랜잭션이 Slock을 얻는 것은 허용하지만, 한 트랜잭션이 Xlock을 요청한 경우 다른 트랜잭션들은 어떠한 락도 얻을 수 없다.

각 트랜잭션은 데이터를 사용하기 전에 Concurrency Manager에게 락을 요청하고, 해당 데이터에 대한 락을 얻으면 데이터에 접근할 수 있다. 이후 작업을 마치면 Concurrency Manager에게 락을 반납한다.

하지만 이 방법만으로는 아직 Serializabiliy를 보장하긴 어렵다. 위의 스케줄을 보면 T1과 T2가 LBP를 잘 지키고 있지만 T1의 write(B)와 T2의 read(B), T1의 write(A)와 T2의 read(A)가 각각 충돌관계이기 때문에 이 스케줄을 Serializable하지 않다.

Deadlock

Locking Protocol을 사용하다보면 기대하지 않았던 상황이 발생할 수 있다. Deadlock(교착상태)은 그 중 한 경우로, 서로 다른 두 트랜잭션이 상대방이 락을 가진 데이터에 락을 요청하는 경우 발생한다.

위 스케줄을 보면 T3는 B에 대한 Xlock을 가지고 있고 T4는 A에 대한 Slock을 가지고 있다. 이 상황에서 T4는 B에 대한 Slock을 요청하고 T3는 A에 대한 Xlock을 요청하지만 둘중 한 트랜잭션이 자신이 가지고 있는 락을 놓지 않으면 양쪽 모두 락을 획득할 수 없으므로 스케줄이 진행될 수 없다. 대부분의 locking protocol들은 Deadlock이 발생할 가능성이 있는데, 일단 Deadlock이 발생했다면 외부의 개입없이는 진행되지 않으므로 Deadlock을 인지했다면 적절한 조치(롤백)를 취해야 한다.

Starvation

Starvation 역시 Concurrency Manager가 잘못 설계되면 발생할 수 있는 문제로, 특정 트랜잭션이 계속 락을 획득하지 못하는 상황을 의미한다. Starvartion이 발생하는 한 예시로 위의 그림에서 T1이 A에 대한 Slock을 가지고있고 T2가 A에 대한 Xlock을 얻기위해 기다리는 상황에서 T3가 Slock을 요청하면 Concurrency Manager는 이를 승인한다. 이후 T1이 락을 반납해도 T3가 Slock을 가지고 있기 때문에 T3는 락을 얻지 못하고 계속 기다려야 한다. 다른 예시로는 한 트랜잭션이 Deadlock으로 인해 반복해서 롤백되는 경우에도 Starvation이 발생할 수 있다.

Starvation은 Concurrency Manager가 잘못 설계되었을 때 발생할 수 있으므로, Concurrency Manager는 이를 방지할 수 있도록 적절히 설계되어야 한다.

Two-Phase Locking Protocol

동시성 제어를 위해 DBMS는 Serializabiliy를 보장하는 프로토콜을 사용하여 트랜잭션을 처리해야 하는데, 위의 프로토콜 만으로는 이를 보장하지 않는다. 따라서 Serializabiliy를 보장하기 위해 대부분의 DBMS는 Two-Phase Locking Protocol(2PL protocol)을 사용한다.

2PL 프로토콜은 트랜잭션이 락을 얻기만 하고 놓지 않는 Growing Phase와 락을 놓기만 하고 요청하지 않는 Shrinking Phase로 이루어져있다. 하지만 2PL 프로토콜을 사용해도 locking프로토콜을 사용하지 않는 이상 deadlock은 피할 수 없다.

Basic 2PL은 트랜잭션의 Serializabiliy만을 보장하는데, 추가로 Recoverability를 보장하기 위해서는 Strict 2PL과 Rigorous 2PL을 사용한다.

• Strict 2PL : 다른 트랜잭션이 dirty data를 얻는 것을 방지하기 위해 commit/rollback시점까지 xlock을 가지고있어야 하는 프로토콜(Cascadeless). Concurrency가 줄어든다는 단점이 있음
• Rigorous 2PL : Strict 2PL보다 강한 제약이 있는 프로토콜로, commit/rollback시점까지 모든 종류의 락을 가지고있어야 하는 프로토콜. 이 프로토콜을 따르는 트랜잭션들은 커밋순서로 직렬화할 수 있음

대부분의 상용 DBMS는 Rigorous 2PL을 사용한다.

2PL프로토콜의 중요한 특징으로, 2PL프로토콜은 Seralizability를 보장하지만 모든 Serializable schdule이 2PL프로토콜을 따르지는 않는다는 점이다. 즉, 2PL을 따르지 않아도 serializable할 수 있지만 DBMS에서는 serializability를 보장하기 위해 2PL을 사용한다. 따라서 2PL을 따르는 트랜잭션들로 구성된 스케줄은 legal하다.

Lock Conversions

Lock Conversions은 2PL의 변형된 방법으로 Growing Phase에 slock을 xlock으로 upgrade할 수 있고, 반대로 Shrinking Phase에서는 xlock을 slock으로 downgrade할 수 있는 규칙이 추가된다. Lock Conversions역시 2PL과 마찬가지로 Serializability를 보장한다.

Locking protocol을 따르는 모든 트랜잭션은 read/write연산 전에 해당 데이터에 대해 적절한 lock을 가지고 있어야 한다. 비록 트랜잭션이 명시적으로 lock을 요청하지 않더라도 Concurrency Manager는 트랜잭션이 read/write작업을 할 때 해당 데이터의 락의 상태를 확인하고 트랜잭션에게 적절한 락을 부여하거나 업그레이드해 주어야 한다. 또한 모든 락은 트랜잭션이 commit/abort된 후에 release되어야 한다.

Deadlock Handling

Lock Based Protocol에서 deadlock은 피할 수 없는 문제이므로, DBMS는 이에 대응하기 위한 적절한 방법을 마련해야 한다. 대표적으로는 데드락이 발생하지 못하도록 막는 Deadlock Prevention기법과 데드락이 발생한 것을 탐지하는 Deadlock Detection기법이 있다.

Deadlock Prevention

Deadlock Prevention은 DBMS가 절대 데드락에 빠지지 않도록 보장하는 프로토콜로 여러가지 방법이 있다. 그중 가장 기본적인 방법은 아래와 같다.

• Pre-declaration : 트랜잭션 시작 전에 필요한 모든 락을 얻고 시작하는 방법
• Graph-based protocol : 데이터에 접근하는 트랜잭션의 순서를 미리 정해놓고, 이 순서대로 락을 부여하는 방법

두가지 방법 모두 데드락을 방지할 수는 있지만 효율이 좋지 않아 잘 사용하지는 않는다.

Wait-Die

모든 트랜잭션은 실행시점에 시스템으로부터 타임스탬프를 받고, 이 시간을 기준으로 older 트랜잭션과 younger 트랜잭션으로 나뉜다. Wait-Die전략은 Non-preemptive한 방법으로 다음과 같은 특징이 있다.

• older transaction은 younger transacrion이 가지고 있는 락을 얻기 위해서 younger transacrion이 락을 놓을 때까지 기다린다(wait).
• younger transacrion은 older transaction이 가지고 있는 락이 필요하다면 기다리지 않고 롤백하여 자신이 가진 락을 놓는다(die).

이 방법은 older transaction이 younger transaction을 기다릴 수는 있지만 그 반대는 불가능 하기 때문에 Precedence graph에 cycle이 생길 수 없으므로 deadlock이 발생하지 않는다. 또한 younger transaction은 롤백 이후 새로 타임스탬프를 받지 않고 기존의 타임스탬프를 사용하여 시간이 지나 older transaction이 되면 롤백되지 않고 락을 얻을 수 있다. 하지만 이 방법은 트랜잭션이 락을 얻기 위해 여러번 롤백될 수 있다는 단점이 있다.

Wound-Wait

Wound-Wait전략 역시 older transacrion이 우선순위를 가지지만 Wait-Die전략과 달리 Preemptive한 방법으로 아래와 같은 특징이 있다.

• older transaction은 younger transaction이 가지고 있는 락을 얻기 위해 younger transaction을 롤백시키고 락을 빼앗아온다(wound).
• younger transaction은 older transaction이 가지고 있는 락을 얻기 위해서 older transaction이 락을 놓을 때까지 기다린다(wait).

이 방법은 Wait-Die와 반대로 younger transaction이 older transaction을 기다리지만, older transaction이 younger transaction을 기다리지는 않기 때문에 Precedence graph에 cycle이 생기지 않아 deadlock이 발생하지 않는다. 또한 위와 마찬가지로 younger transaction은 시간이 지나 older transaction이 되어 기다리지 않고 락을 얻을 수 있다.

Wait-Die와 Wound-Wait전략 모두 older transaction이 우선순위를 가지고 younger transaction은 시간이 지나 older transaction이 되기 때문에 starvation이 발생하지 않는다.

Timeout-Based

Timeout-Based전략은 간단한 구현으로 deadlock을 피할 수 있기 때문에 대부분의 DBMS에서 채택하는 방법으로, 다음과 같은 특징이 있다.

• 각 트랜잭션은 특정시간동안만 락을 기다리고, 해당 시간을 넘기면 롤백된다.

이 방법은 deadlock이 발생하더라도 일정 시간이 지나면 트랜잭션이 롤백되면서 deadlock이 해소된다. 하지만 timeout의 간격을 정하기 어렵고 starvation이 발생할 수 있으며, 불필요한 롤백이 발생할 수 있다는 단점이 있다.

Deadlock Detection

Deadlock Detection은 런타임에 동적으로 deadlock이 발생하는지 검사하는 방법으로 Wait-for graph를 만들어 주기적으로 cycle이 발생하는지 검사한다. 만약 deadlock이 발생하였다면 몇몇 트랜잭션(victim)을 롤백시켜 deadlock을 해소한다. 이때 victim은 롤백으로 낭비되는 비용이 가작 적은 트랜잭션을 선택한다. victim으로 선택된 트랜잭션을 롤백할 때에는 트랜잭션 전체를 롤백하고 다시시작(Total rollback)하거나 락을 놓기 위해 필요한 부분만 롤백(Partial rollback)할 수 있다. 하지만 이 방법은 동일한 트랜잭션이 반복해서 victim으로 선택되면 starvation이 발생할 수 있고, 동적으로 그래프를 만들고 탐색하기 때문에 비용이 커서 잘 사용하지 않는다.