[데이터베이스] 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

1. Lock-Based Protocols
2. Timestamp-Based Protocols
3. Validation-Based Protocols
4. Multiple Granularity
5. 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)

1. 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)

1. If TS(Ti) < R-timestamp(Q) ⇒ write 허용 x, Ti roll back
2. If TS(Ti) < W-timestamp(Q) ⇒ write 허용 x, Ti roll back
3. 이 외 ⇒ 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를 보장할 수 없다.