데이터베이스 : 병행 제어(Concurrency Control) #2 (로킹, 2PLP, MVCC)

앞선 글에서 직렬 스케줄과 비직렬 스케줄에 대해 알아보면서 끝마쳤습니다.

그런데 모든 스케줄에 대하여 직렬 가능성 검사를 하는 것에는 한계가 있다고 했었죠?

이 때, 직렬 가능성을 검사하지 않고도 해당 스케줄의 직렬 가능성을 보장할 수 있는 방법을 바로 병행 제어(Concurrency Control)라고 합니다.

 

병행 제어에는 여러 가지 방법이 존재하는데,

① Locking, ② 2PL, ③ Timestamp, ④ MVCC, ⑤ 낙관적 검증 등 다섯가지 방법이 있습니다.

---

로킹(Locking)과 2PL(2 Phase Locking)

---

로킹은 트랜잭션을 잠궈서 접근을 막는 기법입니다.

로킹에는 다음과 같은 로킹 규약이 따라옵니다.

1. 트랜잭션 T가 read(x)나 write(x) 연산을 하려면 반드시 먼저 lock(x) 연산을 실행해야 함
2. 트랜잭션 T가 실행한 lock(x)에 대해서는 T가 모든 실행을 종료하기 전에 반드시 unlock(x) 연산 을 실행해야 함
3. 트랜잭션 T는 다른 트랜잭션에 의해 이미 lock이 걸려 있는 x에 대해 다시 lock(x)를 실행시키지 못 함
4. 트랜잭션 T는 x에 lock을 자기가 걸어 놓지 않았다면 unlock(x)를 실행시키지 못 함

위의 그림을 보면 read(x)나 write(x) 연산을 lock(x)와 unlock(x)가 감싸고 있는 형태가 보입니다.

또 T1이 x에 lock을 걸어놓은 상태라면, T2는 x에 대하여 lock을 걸 수 없죠.

마지막으로 T1이 x에 걸은 lock은 T1 자신밖에 풀지 못합니다.

 

한편 로킹에는 두 가지 모드가 존재하는데,

read 연산만 허용하는 lock-S(Shared lock),

read와 write 모두 불허하는 lock-X(Exclusive lock) 가 있습니다.

다음의 스케줄이 주어졌습니다.

로킹을 사용한 스케줄의 결과값이 <T1, T2>나 <T2, T1> 그 무엇과도 일치하지 않네요!

이렇게 로킹을 사용해도 직렬 가능하지 않은 스케줄이 있습니다.

그렇다면 이런 스케줄은 어떻게 직렬 스케줄로 만들 수 있을까요?

---

2PL(2 Phase Locking)은 lock을 두 번 중첩시키는 로킹입니다.

2PL에는 확장 단계(growing phase)와 축소 단계(shrinking phase)가 존재하는데,

확장 단계에서는 lock만 수행하며, 축소 단계에선 unlock만 수행합니다.

그림과 같이 lock → lock → unlock → unlock 의 과정을 거치는 것이 2PL이라 할 수 있습니다.

또한 2PL을 쓰는 프로토콜을 2PLP(2 Phase Locking Protocol)라고 합니다.

스케줄 내 모든 트랜잭션이 2PLP라면 그 스케줄은 직렬 가능한 스케줄이 됩니다.

 

다음의 스케줄을 볼까요?

위의 스케줄에서 T1, T2는 모두 2PLP로 직렬 가능한 스케줄이 됩니다.

단, T2는 T1에서 unlock(x)를 할 때까지 x에 접근하지 못하므로 시간이 더 걸릴 수 있습니다.

 

다른 스케줄을 보겠습니다.

이 스케줄은 T1은 그냥 로킹이고, T2만 2PLP인 스케줄입니다.

이 스케줄은 직렬 가능성을 보장하지 못하고, 실제로 직렬 불가능한 스케줄입니다.

 

또 다른 스케줄입니다.

이 스케줄은 T1, T2 모두 그냥 로킹이므로 직렬 가능성을 보장하지 못하지만,

실제로 직렬 가능 스케줄입니다.

2PLP는 직렬 가능을 위한 충분조건이지, 필요조건이 아님을 알 수 있습니다.

그렇다면 이 스케줄을 2PLP를 지키는 스케줄로 바꾸면 어떻게 될까요?

바로 처음에 봤던 그 스케줄이 됩니다.

 

한편 2PLP도 로킹처럼 두 가지 변형이 존재합니다.

엄밀(strict) 2PLP와 엄격(rigourous) 2PLP 이죠.

엄밀(strict) 2PLP는 lock-X에 한하여 그 트랜잭션이 완료할 때까지 unlock하지 않고 유지됩니다.

완료하지 않은 트랜잭션에 의해 기록된 모든 데이터는 그 트랜잭션이 완료할 때 까지 lock-X 모드로 로킹되므로, 다른 트랜잭션이 그 데이터를 read조차 못하게 만들어버리죠.

이로 인해 연쇄 복귀(cascading rollback) 문제가 일어나지 않습니다.

 

엄격(rigourous) 2PLP는 lock-X, lock-S, 일반 lock 모두 해당 트랜잭션이 완료할 때까지 unlock하지 않고 유지되므로, 엄밀 2PLP보다 더 제한적이면서 느립니다.

엄격 2PLP에선 트랜잭션들이 완료하는 순서로 스케줄을 직렬화 할 수 있게 됩니다.

 

대부분의 상용 DBMS에선 엄밀 혹은 엄격 2PLP를 사용합니다.

---

앞서 로킹과 2PLP에서는 한 아이템만 로킹하는 것을 예로 들었는데,

더 큰 단위에서도 로킹이 가능하며 이를 다중 단위 로킹(multiple granularity locking)이라고 합니다.

LOCK TABLES student READ;
UNLOCK TABLES;
LOCK TABLES student WRITE;
UNLOCK TABLES;
-- 테이블 단위 로킹 (Table-level locking)

START TRANSACTION; 
SELECT * FROM student WHERE id=1234 FOR UPDATE; 
COMMIT;
START TRANSACTION; 
SELECT * FROM student WHERE id=1234 LOCK IN SHARE MODE;
COMMIT;
-- row 단위 로킹 (Row-level locking)

이렇게 테이블이나 row 단위로 로킹이 가능합니다.

여기서 Row-level locking은 id=1234인 row에 한하여 로킹을 하는 경우로, 다음 그림과 같습니다.

---

교착 상태(Deadlock)

---

교착 상태(Deadlock)란 모든 트랜잭션이 실행을 전혀 못하고 무한정 기다리는 상태입니다.

아래의 그림에서 T1과 T2는 서로의 unlock을 기다리느라 실행되지 못하고 있죠.

교착상태의 해결책으로는 예방, 회피, 탐지가 있습니다.

예방(prevention) : 트랜잭션을 실행시키기 전에 교착 상태 발생이 불가능 하게 만드는 방법
회피(avoidance) : 자원을 할당할 때마다 교착 상태가 일어나지 않도록 실시간 알고리즘을 사용하여 검사
탐지(detection) : 교착 상태가 일단 일어난 뒤에 교착 상태 발생 조건의 하나를 제거

교착상태를 예방하려면 트랜잭션 실행 전 필요한 데이터 아이템을 모두 lock 하면 되는데,

여기서 일련의 문제점이 발생합니다.

- 데이터 아이템의 활용도 감소 ← 데이터 아이템이 모두 한꺼번에 lock되기 때문

- 기아 문제 (Starvation)

기아 문제란, 한 트랜잭션이 X라는 아이템을 쓰려고 lock 해버리면,

다른 트랜잭션은 X가 unlock될 때까지 무한정 기다려야 하는 문제입니다.

---

교착상태의 회피는 타임스탬프를 이용하여 진행할 수 있고, 두 가지 기법이 있습니다.

1. wait-die 기법
2. wound-wait 기법
3. 요구 거부(rejection)

wait-die 기법과 wound-wait 기법은 고참 트랜잭션과 신참 트랜잭션 사이에 벌어지는 일인데, 군대에 빗대어 설명할 수 있습니다.

신참이 화장실을 사용중이라고 합시다. 트랜잭션으로 비교하면 아이템을 사용하는 중이죠.

wait-die 기법에선 고참이 화장실을 기다리는 천사 선임이라서, 고참이 Starvation을 겪습니다.

반면 wound-wait 기법에선 고참이 신참보고 빨리 나오라고 하는 소위 꼽창이네요,

이 경우에는 신참이 Starvation을 겪습니다.

 

트랜잭션으로 다시 설명하자면,

wait-die 기법은 고참 트랜잭션이 신참 트랜잭션을 기다리고,

고참 트랜잭션이 가지고 있는 데이터를 신참이 요구하면 고참이 복귀한 뒤 재실행합니다.

이 때 불필요한 복귀가 자주 일어날 가능성이 있습니다.

wound-wait 기법은 고참 트랜잭션이 신참 트랜잭션을 기다리지 않고,

신참 트랜잭션이 가지고 있는 데이터를 고참이 요구하면 신참이 복귀한 뒤 재실행합니다.

즉, 신참 트랜잭션은 고참이 아이템을 쓸 때까지 기다리기만 하면 됩니다. 

wound-wait 기법에서는 불필요한 복귀가 비교적 덜 일어납니다.

 

요구 거부는 교착상태를 유발하는 요구가 발생하면 해당 요구를 거부하여 교착상태를 회피합니다.

lock 수행 불가시 해당 lock 요구를 거부하여 트랜잭션에 복귀 후 재시작합니다.

이 때 불필요한 복귀나 재시작이 발생할 수 있습니다.

---

교착상태 방지가 보장되지 않을 때(이미 교착상태 발생), 교착상태 탐지 기법이 필요합니다.

교착상태가 발생했을 때 취소할 트랜잭션을 선택하여 rollback 하는 방식으로 회복이 진행되죠.

이 때 같은 트랜잭션이 계속해서 취소되면 Starvation을 겪어 트랜잭션이 완료되지 못합니다.

---

MVCC(Multi Version Concurrency Control)

---

앞서 wait-die와 wound-wait 기법을 설명할 때 화장실에 빗대어 설명했죠?

MVCC(Multi Version Concurrency Control)는 여러 칸의 화장실을 만들어줍니다.

위의 그림에서 10023(고참 트랜잭션)이 아이템 X를 SELECT 하려 합니다.

정상적으로 진행되다가, 도중에 10024(신참 트랜잭션)도 X에 접근을 하죠.

이 때 고참 트랜잭션은 Undo Log에서 Old Image를 불러와 누가 접근하던 계속 진행합니다.

 

MVCC에서도 아래와 같은 문제점이 발생합니다.

- UNDO Log가 쌓임 → 저장공간을 더 차지

- Snapshot too old 문제 발생

 

<틀린 점이 있다면 지적 부탁드립니다. 감사합니다.>