[데이터베이스] Chapter 18. Concurrency Control
Reference
1. Database System Concepts-Abraham Silberschatz, Henry Korth, S. Sudarshan
2. Database System class by Professor Yon Dohn Chung, Department of Computer Science and Engineering, Korea University
중요한 내용 위주로 요약 & 정리하였습니다.
Topic
- Lock-Based Protocols
- Timestamp-Based Protocols
- Validation-Based Protocols
- Multiple Granularity
- Multiversion Schemes - snapshot isolation
18.1 Lock-Based Protocols
Lock
- Shared lock: T1이 shared lock을 얻었다면, 다른 T들은 read할 수는 있으나, write할 수는 없다.
- Exclusive lock: T1이 excludsive lock을 얻었다면, 다른 T들은 read와 write할 수 없다.
Schedule With Lock Grants
Deadlock
**lock-S(B)**로 인해서 T4는 T3가 B에 대한 lock을 해제할 때까지 기다리게 되고, **lock-X(A)**로 인해서 T3는 T4가 A에 대한 lock을 해제할 때까지 기다리게 된다.
⇒ 두 트랜잭션 모두 더이상 진행하지 못한다. (deadlock)
⇒ roll back해야 한다.
Two-Phase Locking (2PL) protocol
- Growing Phase : lock을 얻는 과정, lock 해제는 불가능하며 모두 승인된 이후에만 해제 가능
- Shrinking Phase : lock을 해제하는 과정, lock 획득은 불가능
⇒ Serializability는 보장 ⇒ cascadomg rollback이 일어날 수 있다. ⇒ deadlock이 일어날 수 있다.
이를 확장시키면
(1) Strict two-phase locking
- 트랜잭션은 commit과 abort 되기 전까지는 모두 exclusive lock을 들고 있어야 한다.
- 즉, X는 commit, abort될 때까지 해제 불가능, S는 가능
- cascading roll back 방지, but deadlock은 방지 못함
(2) Rigorous two-phase locking
- 트랜잭션은 commit된 순서로 serialized될 수 있다.
- 대부분의 DBMS에서 사용
⇒ Locking protocol로 인해서 스케줄은 legal하고, serializablity를 보장한다.
Lock Conversion
- Upgrade: S → X
- Downgrade: X → S
2PL with Lock Conversions
Implementation of Locking
- lock manager가 각 process에 구현되어있다.
- 각 트랜잭션은 lock, unlock 요청을 lock manager에게 보내고 응답이 올 때까지 대기한다.
- lock manager는 각 요청에 대해서 lock grant message를 보낸다.
- lock manager는 lock table 자료 구조를 유지한다.
lock table
- 진한 사각형은 granted lock, 연한 사각형은 요청을 대기 중인 lock이다.
- 새로운 요청이 추가되면, 각 data item의 큐에 삽입된다.
- unlock 요청은 해당 grant 요청을 삭제하고 최신 요청 중 granted될 수 있는 지 확인한다.
- 트랜잭션이 abort되면, 해당 트랜잭션의 모든 waiting, granted 요청이 삭제된다.
Graph-Based Protocols
Tree protocol
⇒ conflict serializability 를 보장한다.
- 장점: deadlock-free, rollback이 필요하지 않는다.
- 단점: recoverability 와 cascade freedom을 보장하지 않는다. 트랜잭션이 사용하지 않는 data에 lock을 걸 수도 있다.(조상) → concurrency 감소
18.2 Deadlock Handling
⇒ deadlock 조건: Mutual Exclusion, Hold & Wait, Circular wait, Non-preemption
Deadlock prevention
(1) Pre-declaration
- 각 트랜잭션이 수행 전에 모든 data에 대해서 lock을 획득해야 한다.
(2) Resource ordering
- 자원을 ordering하고, 그 순서에 따라서 트랜잭션이 lock을 걸 수 있다.
Deadlock avoidance
(1) [wait-die scheme] non-preemptive
- 우선 순위가 낮으면 스스로 die, 높으면 기다린다.
- 일반적으로 older 트랜잭션이 우선 순위가 높다.
(2) [wound-wait scheme] preemptive
- 우선 순위가 높으면 강제로 죽이고 선점. 낮으면 기다린다.
⇒ 두 scheme 모두 older 트랜잭션이 newer보다 우선 순위가 높도록 하여 starvation을 피해야 한다.
Timeout-Based Schemes
- 각 트랜잭션에 특정 시간이 정해져있고, 시간이 지나면 roll back된다.
- deadlock이 발생되더라도 일정 시간 지나면 해결됨
- 단점은, deadlock이 없더라도 트랜잭션이 roll back될 수 있다.
- Starvation이 발생 가능
Deadlock Detection
- Wait-for graph : Ti → Tj = Ti는 Tj가 들고 있는 lock을 기다림
- wait-for graph에 cycle이 있으면 deadlock이 존재한다.
Deadlock Recovery
deadlock이 탐지되면, deadlock cycle을 부수기 위해서 일부 트랜잭션은 roll back된다. (victim)
- Total rollback: 트랜잭션을 abort하고 재시작
- Partial rollback: victim 트랜잭션을 필요한 만큼만 rollback한다.
- starvation 방지: 오래된 트랜잭션은 victim이 되지 않도록 한다.
18.3 Multiple Granularity
lock을 잡는 크기와 concurrency는 반비례하다.
Granularity of locking
- Fine granularity(lower in tree) : high concurrency, high locking overhead
- Coarse granularity(higher in tree) : low concurrency, low locking overhead
<포함 관계를 표현>
database → area → file → record
Intention Lock Modes
(1) Intention-shared (IS)
lower level tree에 **S**가 있음을 알림
(2) Intention-exclusive (IX)
lower level tree에 S 혹은 **X**가 있음을 알림
(3) Shared and Intention-exclusive (SIX) : S and IX
subtree 에 모두 S를 걸고, update할 record가 나오면 X로 바꿈
- 작은 단위의 granul이 lock을 잡을 때, 미리 상위 granul에게 알리는 것 ⇒ Intention lock
- Intention lock은 여러 개 걸릴 수 있다.
- S lock을 거는 사실을 상위 granul에게 알리면서 내려온다.(Top-down)
- lock 해제 시 bottom-up으로 해제하면서 올라온다.
Compatibility Matrix with Intention Lock Modes
Rules
18.5 Timestamp-Based Protocols
- 각 트랜잭션이 system에 진입 시 unique한 timestamp TS(Ti) 를 부여한다.
- 먼저 들어올 수록 우선 순위가 높다.
- time-stamp order = serializability order
Timestamp-Ordering Protocol
- W-timestamp(Q) : 특정 data (Q)를 wirte 한 트랜잭션의 TS값(write한 시간이 아니다)
- R-timestamp(Q) : 특정 data (Q)를 read 한 트랜잭션의 TS값
Read(Q)
- If TS(Ti) ≤ W-timestamp(Q) ⇒ read 허용 x, Ti는 roll back
마지막으로 Q에 write한 T의 TS값보다 Ti가 늦게 왔는데 그것을 read한다면 덮어써진 Q를 읽는 것과 같아 order가 꼬이기 때문이다. 2. If TS(Ti) ≥ W-timestamp(Q) ⇒ read 허용 o
R-timestamp(Q) = max(R-timestamp(Q), TS(Ti)) 마지막으로 read한 T의 TS값과 비교하여 큰 값으로 설정한다.
Write(Q)
- If TS(Ti) < R-timestamp(Q) ⇒ write 허용 x, Ti roll back
- If TS(Ti) < W-timestamp(Q) ⇒ write 허용 x, Ti roll back
- 이 외 ⇒ write 실행, W-timestamp(Q) = TS(Ti)
Example
Correctness of Timestamp-ordering Protocol
- TSO는 conflict serializability를 보장한다.
- deadlock free 보장
- cascade-free, recoverable 보장 X
Thomas’ Write Rule
Ti가 Q에 write 하려고 할 때,
- if TS(Ti) < W-timestamp(Q) ⇒ BTO(base timestamp ordering)에서는 Ti가 rollback 되어야 하지만, roll back 대신 {write} operation을 그냥 무시한다.
- 그 외에는 BTO와 동일하다.
- concurrency 증가
18.6 Validation-Based Protocol
(1) Read and execution phase
Ti는 오직 temporary local variable에 write 가능
(2) Validation phase
Ti 가 validation test를 진행하여 local variable이 serializability를 해치지 않으면서 wirte될 수 있는지 검사한다.
(3) Write Phase
Ti가 검증되면, database에 update를 반영하고 그렇지 않다면 Ti를 roll back한다.
18.7 Multiversion Concurrency Control
Multiversion Schemes
- write의 결과로 새로운 version의 data item을 만든다.
- timestamp로 각 version을 label
- read(Q)에 문제가 생겼을 때 적적할 version을 선택한다.
Snapshot Isolation
- 각 트랜잭션에 database state의 snapshot을 준다.
- Read 는 snapshot에서 이뤄짐
- Write 는 locally하게 이뤄짐 (First Commiter wins)
- 먼저 commit한 트랜잭션을 제외하고는 모두 roll back한다.
- 하지만 lock을 모든 concurrent 트랜잭션이 끝날 때까지 들고 있어야 한다.
- update가 손실되는 것과 같이 이상 현상이 발생 가능
⇒ Serializable Snapshot Isolation (SSI) 사용
Benefits of SI
- Read가 block되지 않는다.
- Read committed와 비슷하다.
- dirty read X
- lost update X
- non-repeatable read X
단점 : serializability를 보장할 수 없다.
