[Database] 동시성 제어

📕 목차

1. Concurrency Control 목적
2. Concurrency Control 종류
3. Locking
4. Multiple Granularity Locking
5. Deadlock Handling
6. Other Concurrency Controls

---

1. Concurrency Control 목적

 

📌 Purpose

• 동시에 실행되는 Transaction 제어
• Database 일관성(Serializability) 유지
• Concurrency Control이 없을 경우 문제점
  • Lost Update
  • Dirty Read
  • Unrepeatable Read
  • Phantom Read

 

📌 Lost Update

• 누가 쓴 걸 덮어써서 데이터가 손실됨

 

📌 Dirty Read

• 잘못된 데이터를 읽음

 

📌 Unrepeatable Read

• 하나의 트랜잭션 내에서 읽을 때마다 데이터가 바뀜

 

📌 Phantom Read

• 트랜잭션에서 수행한 작업에 의해 레코드가 보였다가 안 보였다 하는 현상

 

📌 Transaction Isolation 4 Level

• READ UNCOMMITTED
  • Phantome read, Unrepeatable read, Dirty read 허용
• READ COMMITTED
  • Phantom read, Unrepeatable read만 허용 (Oracle Default)
• REPEATABLE READ
  • Phantom read만 허용
• SERIALIZABLE
  • 모두 허용 안 함

 

🔧 설정

• SQL> `SET Transaction Isolation Level Serializable;`
• Oracle에서는 read committed와 serializable만 허용

 

🟡 예시

 

---

2. Concurrency Control 종류

 

📌 Rules

• 동시에 실행되는 Transaction 정확성 유지
• Transaction 동시 실행은 순차 실행보다 좋은 성능 보장

 

📌 Type

• Locking
• Timestamp Ordering
• Optimistic Concurrency Control

 

---

3. Locking

 

📌 Concept

• data에 대한 access 권한
• 데이터에 접근하기 전에 Lock을 얻은 Transaction만이 data access

 

✒️ Lock Modes

요청\보유	S	X
S	OK	Not OK
X	Not OK	Not OK

• Shared (S) Lock: 데이터를 read할 때 사용
• Exclusive (X) Lock: 데이터를 write할 때 사용

 

📌 Locking Rule

(좌) 기아 상태 발생 문제 (S가 대기 중인 X 새치기) / (우) 작업 완료 전 Lock 해제 시 문제

1. Lock 획득 시점
   • well-formed: data access하기 전 Lock 요청
   • Locking은 필연적으로 교착 상태가 발생
   • Conflict mode의 Lock이 이미 걸려 있을 경우
     • Lock이 해제될 때까지 대기 → Deadlock 발생 가능
     • 여러 Transaction이 대기 중일 때 → Starvation 발생 가능
2. Unlock 시점
   • data access한 후, Unlock하는 경우
     • Lost Update, Dirty Read, Unrepeatable Read 가능
   • two-phase rule: Transaction 완료할 때까지 보유

 

📌 Two Phase Locking (2PL)

• def. Unlock을 한 후 Lock 요청 불가
  • Growing Phase: Lock 요청 단계
  • Shrinking Phase: Unlock 단계
• Conservative 2PL: End of Transaction 단계에서 한 번에 모든 Lock 해제

 

📌 Concurrent Schedule - Locking

 

---

4. Multiple Granularity Locking

 

📌 Concept

• Lock (Lock Granularity)
  • Fine granularity: concurrency ↑, overhead↑
  • Coarse granularity: concurrency↓, overhead↓
• Multiple Granularity Locking (MGL) : 다단계 Locking
  • 낮은 Overhead와 높은 동시성 목적
  • Explicit Locking: 명시적 락 ⇒ target만 lock
  • Implicit Locking: 묵시적 락 ⇒ 연관된 모든 record에 lock
  • Intention Locking: 의도적 락 ⇒ 하위에 Lock이 걸리면, 상위 계층에 표시

 

🤔 Table 단위보다 Record 단위로 Lock을 거는 게 반드시 합리적인가?

• 10,000개의 record를 읽을 때, 10,000개의 lock이 걸리는 overhead가 발생한다.
• 어느 계층에 lock을 걸든, concurrency와 overhead가 비례 관계임을 잊지 말자

 

📌 Intention Mode

글자가 왜 기울어져 있냐구..? 이 때 졸았거든..

• Intention Shared (IS) Mode
  • 하위 레벨에서 Explicit S mode의 lock 보유
• Intention Exclusive (IX) Mode
  • 하위 레벨에서 Explicit X mode의 lock 보유
• Shared and Intention Exclusive (SIX) Mode
  • Explicit S mode의 lock 보유
  • 하위 레벨에서 Explicit X mode의 lock 보유

 

📌 Compatibility Matrix of MGL

요청 \ 보유	IS	IX	S	SIX	X
IS	✅	✅	✅	✅	❌
IX	✅	✅	❌	❌	❌
S	✅	❌	✅	❌	❌
SIX	✅	❌	❌	❌	❌
X	❌	❌	❌	❌	❌

 

 

📌 Locking Protocol of MGL

• Lock & Unlock 순서
  • Lock: Root → Leaf
  • Unlock: Leaf → Root
• Lock Mode
  • Explicit S lock을 요청할 노드의 모든 상위 노드: IS
  • Explicit X lock을 요청할 노드의 모든 상위 노드: IX
  • SIX lock을 요청할 노드의 모든 상위 노드: IX

 

📌 Examples

다중 단위크기 로킹(Multiple Granularity Locking) 기법에서 3계층 단위 크기의 예시이다.

위 기법의 동작에 대한 아래 질문에 답하라.

 

1️⃣ 트랜잭션1이 레코드 P4를 읽기 위해 획득해야 하는 Lock을 차례대로 나열하라

• IS(DB) → IS(F2) → S(P4)

 

2️⃣ 트랜잭션 2가 테이블 F2의 모든 레코드들을 수정하기 위해 획득해야 하는 Lock을 차례대로 나열하라

• IX(DB) → X(F2)

 

3️⃣ 트랜잭션 1,2가 동시 실행될 때, 충돌이 발생하는 Lock을 답하라

• T1의 IS(F2)와 T2의 X(F2) 충돌

 

🟡 Senario

• Read record R
  • IS(DB) → IS(R을 포함한 File) → S(R)
• Update record R
  • IX(DB) → IX(R을 포함한 File) → X(R)
• Read File F
  • IS(DB) → S(F)
• Read File F & Update 특정 record
  • IX(DB) → SIX(F) → X(갱신할 Record)
• 전체 DB를 single user용으로 사용
  • X(DB)

 

---

5. Deadlock Handling

 

📌 해결 방법

• Deadlock Prevention
• Deadlock Detection and Resolution

 

📌 Deadlock Prevention

• def. Deadlock이 발생할 가능성을 봉쇄
• 종류
  • 방법1. 모든 Lock을 한 번에 요청 → 거부될 경우 모두 해제
  • 방법2. 데이터에 순서 부여 → 순서대로 Lock 요청
  • 선점: wait-die, wound-wait

 

🟡 wait-die, wound-wait

 

• wait-die
  • new는 old를 기다리지 못 하게 막는다.
  • new는 Lock을 요청할 때마다, 얻지 못 하면 죽는다.
  • new가 먼저 Lock을 얻으면, old는 대기한다.
  • 구현이 쉬운 방법
• wound-wait
  • new가 old를 기다린다.
  • new가 먼저 Lock을 얻으면, old가 Lock 요청 시 죽여버린다. (섬뜩)

 

📌 Deadlock Detection

• Wait-For Graph: G = (V, E)
  • V: Transaction의 Set
  • E: \(T_{w}\)가 \(T_{h}\)를 기다릴 시, Set of \(T_{w}\) → \(T_{h}\)
• Deadlock Detection & Resolution
  • Deadlock 조건: WFG에 Cycle 발생
  • Resolution
    • victim transaction 선택
    • victim transaction의 rollback
    • starvation 발생 여부

 

---

6. Other Concurrency Controls

 

📌 Timestamp Ordering

• 트랜잭션과 데이터에 Timestamp 할당 (TS, R, W)
• 트랜잭션의 순서로 Data access
• 순서 만족 못 할 경우, 트랜잭션 철회

 

📌 Optimistic Concurrency Control

• 트랜잭션들 간에 충돌이 없다고 가정 (낙관적)
  • Local data에 대해 트랜잭션 실행 후, 검증 (lock도 안 걸고 진행)
  • 검증 결과 충돌 발생 시, rollback
  • 충돌이 발생하지 않으면 실행결과 저장
• 대부분 트랜잭션이 read-only라면 최선의 선택