x=10이라는 데이터가 있을 경우 다음과 같은 작업을 진행할 경우 잘못된 동작을 일으킬 수 있다.
| transaction1 | transaction2 |
|---|---|
| write(x=20) | write(x=90) |
이런 잘못된 동작을 해결하기위해 Lock을 사용할 수 있다.
Write Lock (Exclusive Lock)
다른 transaction이 같은 데이터를 데이터를 read/write하는 것을 허용하지 않는다.
| transaction1 | transaction2 |
|---|---|
| write_lock(x) | |
| write_lock(x) | |
| write(x=20) | |
| unlock(x) | |
| write(x=90) | |
| unlock |
- transaction1에서 lock을 획득
- transaction2는 trancation1에서 unlock을 할때까지 대기
- transaction1에서 write를 수행한 후 unlock (lock을 반납)
- transaction2는 반납된 lock을 획득하게되고 write를 수행한 후 unlock
Read Lock (Shared Lock)
다른 transaction이 같은 데이터를 read하는 것을 허용한다.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| read_lock(x) | |
| read(x) | read(x) |
하지만 하나의 transaction에서 read를 수행할 경우 다른 transaction에서는 write를 할 수 없다.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| write_lock(x) | |
| read(x) | |
| unlock(x) | |
| write(x=20) | |
| unlock(x) |
Lock의 이상 현상
먼저 x=100, y=200이라고 할 때 다음 작업을 수행한다고 해보자.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| read(x) | |
| unlock(x) | |
| write_lock(y) | |
| read(y) | |
| write(y=x+y) | |
| unlock(y) | |
| read_lock(y) | |
| read(y) | |
| unlock(y) | |
| write_lock(x) | |
| read(x) | |
| write(x=x+y) | |
| unlock(x) |
위 작업은 serial schedule이며 결과로 x=400, y=300이 나온다.
이제 nonserial schedule로 수행할때 문제가 발생할 수 있는 예시를 확인해보자.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| read(x) => 100 | |
| unlock(x) | |
| read_lock(y) | |
| write_lock(y) | |
| read(y) => 200 | |
| unlock(y) | |
| read(y) => 200 | |
| write(y=300) | |
| unlock(y) | |
| write_lock(x) | |
| read(x) => 100 | |
| write(x=300) | |
| unlock(x) |
결과는 serial schedule과 다르게 x=300, y=300이 나온다. transaction1에서 update된 y를 read하지 못해서 일어나는 문제이다.
이 문제를 해결하기위해서는 transaction2에서 unlock(x)와 write_lock(y)의 순서를 바꿀 수 있다. 따라서 다음과 같이 변경되면 정상적으로 serial schedule과 결과가 같게 나오게된다.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| read(x) => 100 | |
| write_lock(y) | |
| read_lock(y) | |
| unlock(x) | |
| read(y) => 200 | |
| write(y=300) | |
| unlock(y) | |
| read(y) => 200 | |
| unlock(y) | |
| write_lock(x) | |
| read(x) => 100 | |
| write(x=300) | |
| unlock(x) |
이렇게 모든 locking operation이 최초의 unlock operation보다 먼저 수행되는 것을 2PL protocol(two-phase locking)이라고 한다.
2PL Protocol (two-phase locking)
2PL Protocol은 lock을 획득하기만 하는 phase인 Expanding phase(growing phase)와 lock을 반환만하는 phase인 Shrinking phase(contracting phase)로 나누어진다.
| transaction |
|---|
| read_lock(x) |
| read(x) |
| write_lock(y) |
| read(y) |
| write_lock(z) |
| unlock(x) |
| read(z) |
| write(y=x+y+z) |
| unlock(y) |
| write(z=2*x) |
| unlock(z) |
위 작업에서 read_lock(x) ~ write_lock(z)가 Expanding phase(growing phase)이고 unlock(x) ~ unlock(z)가 Shrinking phase(contracting phase)이다.
Conservative 2PL
모든 lock을 획득한 뒤 transaction을 시작하는 형태를 가지며 deadlock이 발생하지 않는다. 하지만 모든 lock을 획득하기때문에 transaction이 시작하기 어려워질 수 있어 실용적이지 않다.
| transaction |
|---|
| read_lock(x) |
| write_lock(y) |
| write_lock(z) |
| read(x) |
| unlock(x) |
| read(y) |
| read(z) |
| write(y=x+y+z) |
| unlock(y) |
| write(z=2*x) |
| unlock(z) |
Strict 2PL (S2PL)
strict schedule(commit되었을때만 read/write를 할 수 있는 schedule)을 보장하는 2PL이며 recoverability도 보장한다. 다음과 같이 write-lock을 commit/rollback될 때 반환하는 형태이다.
| transaction |
|---|
| read_lock(x) |
| read(x) |
| write_lock(y) |
| read(y) |
| write_lock(z) |
| unlock(x) |
| read(z) |
| write(y=x+y+z) |
| write(z=2*x) |
| commit |
| unlock(y) |
| unlock(z) |
Strong Strict 2PL (SS2PL, rigorous 2PL)
S2PL과 마찬가지로 strict schedule과 recoverability를 보장한다. 그리고 S2PL과의 차이는 write-lock 뿐만 아니라 read-lock도 commit/rollback될 때 반환한다는 것이다.
| transaction |
|---|
| read_lock(x) |
| read(x) |
| write_lock(y) |
| read(y) |
| write_lock(z) |
| read(z) |
| write(y=x+y+z) |
| write(z=2*x) |
| commit |
| unlock(x) |
| unlock(y) |
| unlock(z) |
S2PL보다 구현이 쉽다는 장점이 있지만 lock을 가지고 있는 시간이 더 늘어나기 때문에 다른 transaction이 기다리는 시간도 늘어나게된다.
Deadlock
x=100, y=200일 때 다음 작업을 수행한다고 해보자.
| transaction1 | transaction2 |
|---|---|
| read_lock(x) | |
| read_lock(y) | |
| read(y) => 200 | |
| write_lock(x) | |
| read(x) => 100 | |
| write_lock(y) |
- transaction1에서 write_lock(x)는 transaction2의 read_lock(x)에서 lock 반환을 기다린다.
- transaction2에서 write_lock(y)는 transaction1의 read_lock(y)에서 lock 반환을 기다린다.
이렇게 서로의 lock을 기다리게되면서 deadlock이 발생하게 된다. deadlock을 해결하기위해서 deadlock prevention, deadlock detection & recover 방법을 사용할 수 있다.
Deadlock Prevention
- Predeclaration: 각 트랜잭션 시작 전 모든 데이터를 lock
- Graph-based: 데이터를 항상 전해진 순서로 lock
- Wait-die: 오래된 트랜잭션은 기다리고 새로운 트랜잭션은 Rollback
- Wound-wait: 오래된 트랜잭션이 새로운 트랜잭션을 Rollback
- Timeout-based: 정해진 시간동안만 wait하고 넘어가면 Rollback
Deadlock Detection
Cycle이 일어나는지 검사한 후 recovery를 수행한다. recovery는 전체 rollback하거나 최소의 비용을 가지는 트랜잭션을 rollback 시킨다.
NOTE
write-lock의 경우 다른 transaction에서 block(기다림)이 되어 전체 처리량이 좋지 않다. 이를 위해 MVCC(multiversion concurrency control)이 나타나게 되었다.