[Database] LOCK을 활용한 concurrency control 기법 + 2PL (two-phase locking)

Lock

여러 Transaction이 같은 데이터에 read / write를 한다면 예기치 못한 데이터 변경이 일어날 수 있다.

이를 막기 위해 데이터를 Lock이라는 장치를 설정하여, Lock을 취득하기 전까진 그 데이터의 read/write를 못하게 막을 수 있다.

 

Write Lock (Exclusive Lock)

• read / write(insert, modify, delete)할 때 사용한다.
• 다른 transaction이 같은 데이터를 read / write 하는 것을 허용하지 않는다.
• write 할 때만 사용하는 것은 아니다. 

Read Lock (Shared Lock)

• read 할 때 사용한다.
• 다른 transaction 같은 데이터를 read 하는 것은 허용한다.

Lock을 사용한 시나리오

상황

• Transaction 1과 Transaction 2이 있다.
• DB에 X = 10이라는 데이터가 있다.

write_lock + read_lock

1. Transaction 2는 read_lock(x)를 얻는다.
2. Transaction 1은 write_lock(x)를 획득하려 한다. 하지만 read_lock(x)이 끝날 때까지 기다려야 한다.
3. Transaction 2는 read(x) = 10을 수행하고, unlock(x) 한다.
4. Transaction 1은 write_lock(x)를 얻고 write(x)를 수행한다.
5. write(x) 후 unlock(x) 한다.

read_lock + read_lock

1. Transaction 2는 read_lock(x)를 얻는다.
2. Transaction 1은 read_lock(x)를 얻는다.
3. Transaction 1, 2는 read(x) = 10 을 동시에 수행하고, unlock 한다.

Lock을 사용해도 문제가 생기는 경우

상황

• Transaction 1과 Transaction 2이 있다.
• DB에 x = 100, y = 200이라는 데이터가 있다.
• Transaction 1은 x와 y의 합을 x에 저장하려 한다.
• Transaction 2는 x와 y의 합을 y에 저장하려 한다.
• Transaction 2가 먼저 수행하고, 1이 수행했을 때 결과는 x = 400, y = 300이다.

시나리오

1. Transaction 2가 read_lock(x)를 수행한다.
2. Transaction 2가 read(x) = 100을 수행하고 unlock(x)를 한다.
3. Transaction 1은 read_lock(y)를 수행한다.
4. Transaction 2는 write_lock(y)를 수행한다. 하지만 Transaction 1이 read_lock(y)를 갖고 있으므로 block 된다.
5. Transaction 1은 read(y) = 200을 수행하고 unlock(y)를 한다.
6. Transaction 2는 read(y) = 200을 수행한다.
7. Transaction 2는 read(y) = 200을 수행하고 unlock(y)를 한다.
8. Transaction 1은 write_lock(x)를 수행하고,  read(x) = 100 -> write(x = 300) -> unlock(x)를 수행한다.
9. 결과적으로 DB에 반영된 데이터는 x = 300, y = 300이다.

이 문제는, Transaction 2가 write를 하기 전에 read lock을 반납하여, Transaction 1이 Transaction 2가 데이터를 업데이트하기 전 데이터 y를 read_lock을 수행하여 읽었기 때문이다.

2PL Protocol (two-phase locking)

Transaction에서 모든 Locking Operation이 최초의 unLock Operation보다 먼저 수행되도록 하는 것이다.

각 phase는 두 가지 종류가 있다.

Expanding phase (growing phase)

lock을 취득하기만 하고 반환하지는 않는 phase

 

Shrinking phase (contracting phase)

lock을 반환만 하고 취득하지는 않는 phase

2PL을 사용한 위 이상한 문제 해결

상황

• Transaction 1과 Transaction 2이 있다.
• DB에 x = 100, y = 200이라는 데이터가 있다.
• Transaction 1은 x와 y의 합을 x에 저장하려 한다.
• Transaction 2는 x와 y의 합을 y에 저장하려 한다.
• Transaction 2가 먼저 수행하고, 1이 수행했을 때 결과는 x = 400, y = 300이다.

시나리오

1. Transaction 2가 read_lock(x)를 수행한다.
2. Transaction 2가 read(x) = 100을 수행하고 write_lock(y)를 한다.
3. Transaction 1은 read_lock(y)를 수행하려 하지만, Transaction 2가 write_lock를 수행하고 있으므로 block된다.
4. Transaction 2는 unlock(x)를 수행한다.
5. Transaction 2는 read(y) = 200을 수행하고 write(y = 300)을 수행한다.
6. Transaction 2는 unlock(y)를 한다.
7. Transaction 1은 Transaction 2가 write한 값인 y값을 읽기 위해 read(y) = 300을 수행한다.
8. Transaction 1은 read(x) = 100을 수행하고 write(x = 400)을 수행한다.
9. Transaction 1은 unlock(x)를 한다.
10. 결과적으로 DB에 반영된 데이터는 x = 400, y = 300이다.

위 1 ~ 2번 과정이 Transaction 2의 Expanding phase이고, 4 ~ 6이 Shrinking phase로 나눌 수 있다.

2PL과 DeadLock

하지만 2PL을 사용한 Transaction에는 DeadLock이 발생할 수 있다.

 

상황

• Transaction 1과 Transaction 2이 있다.
• DB에 x = 100, y = 200이라는 데이터가 있다.
• Transaction 1은 x와 y의 합을 x에 저장하려 한다.
• Transaction 2는 x와 y의 합을 y에 저장하려 한다.

시나리오

1. Transaction 2가 read_lock(x)을 수행한다.
2. Transaction 1은 read_lock(y)을 수행한다.
3. Transaction 1은 read(y) = 200 을 수행하고 write_lock(x)를 수행하려 한다.
4. 하지만 Transaction 2가 read_lock(x)를 갖고 있기 때문에, Transaction 1의 write_lock(x)는 block된다.
5. Transaction 2는 read(x)를 수행하고 write_lock(y)를 수행하려 한다.
6. 하지만 Transaction 1이 write_lock(x)를 수행하기 위해 대기하고 있어, Transaction 2의 write_lock(y)를 기다리게 된다.
7. 결국 서로가 Lock을 얻기 위해 기다리는 DeadLock 상태에 들어가게 된다.

2PL의 종류

Conservative 2PL

• 모든 Lock을 취득한 뒤 transaction을 시작하는 방법이다.
• 즉, 연산에 필요한 read_lcok, write_lock을 모두 쥐고나서 Transaction을 시작한다.
• 이러한 방법은 DeadLock이 발생하지 않는다.
• 하지만 실용적이지 못하다.

Strict 2PL(S2PL)

• Strict Schedule을 보장하는 2PL 방법이다. (Strict Schedule: 스케줄 내에서 어떤 transaction도 commit 되지 않은 transaction들이 write한 데이터는 읽지도 않고 쓰지도 않는 스케줄)
• Recoverability를 보장한다. (Recoverability: Rollback을 했을 때 문제가 발생하지 않는 속성) 
• Write-Lock을 commit / rollback 될 때 반환한다.

Strong Strict 2PL(SS2PL)

• Strict Schedule을 보장하는 2PL 방법이다.
• Recoverability를 보장한다. (Rollback을 했을 때 
• Read-Lock과 Write-Lock 모두 commit / rollback 될 때 반환한다.
• S2PL 보다 구현이 쉽다.
• 대신, Lock을 오래 쥐고 있어 다른 Transaction이 Lock을 필요로 할 때 오래 기다리게 된다.

Lock 호환성 문제와 MVCC (multiversion concurrency control)

아래 표처럼, read-lock 끼리는 동시에 Transaction이 진행될 수 있지만, 그 외에 상황에선 동시에 진행할 수 없다.

따라서 read-lock <-> write-lock 끼리라도 동시에 진행 가능하도록 나온 방법이 MVCC이다.

	read-lock	write-lock
read-lock	O	X
write-lock	X	X

참고

• https://youtu.be/0PScmeO3Fig?si=Lxg_djj1u4o7LKRq