Chapter 18. Concurrency Control

한 줄 핵심: 동시 트랜잭션이 결과를 망치지 않게 하는 두 큰 접근 — (1) Lock 기반(2PL): 자물쇠를 “먼저 다 잠그고 그 다음 풀기만”(Two-Phase) 해서 conflict serializability를 보장하되 deadlock을 따로 처리하고, (2) Timestamp 기반(TSO): 도착 순서(타임스탬프)를 직렬화 순서로 강제하고 어기는 연산을 즉시 rollback해 deadlock을 원천 차단한다.

이 챕터가 답하는 핵심 질문

Q1. Lock이란 무엇이고, 락만 쓰면 왜 serializability가 안 되는가?

Q2. Two-Phase Locking(2PL)은 어떻게 직렬성을 보장하는가?

Q3. Recoverability와 cascade 방지를 위해 2PL을 어떻게 확장하는가? (Strict/Rigorous)

Q4. Lock conversion과 자동 락 획득은 무엇이고 왜 필요한가?

Q5. 락은 실제로 어떻게 구현되는가? (Lock manager / Lock table)

Q6. Deadlock을 어떻게 예방·탐지·복구하는가?

Q7. Timestamp 기반 프로토콜(TSO)은 어떻게 동작하는가?

Q8. TSO는 왜 옳고 어떤 한계가 있으며, Thomas’ Write Rule은 무엇인가?

Q1. Lock이란 무엇이고, 락만 쓰면 왜 serializability가 안 되는가?

A. Lock은 데이터 항목의 동시 접근을 통제하는 메커니즘이지만, 락을 너무 일찍 풀면 그 틈에 다른 트랜잭션이 “공사 중 중간 상태”를 봐서 serializability가 깨진다.

두 가지 락 모드

모드	요청	허용	비유
Exclusive (X)	`lock-X`	읽기 및 쓰기	화장실 — 한 명만
Shared (S)	`lock-S`	읽기만	열람실 책 — 여럿이 같이 읽기 OK

락 요청은 concurrency-control manager에게 보내며 granted(승인) 후에야 진행.

Lock-Compatibility Matrix

이미 걸린 락 \ 새 요청	S	X
S	true	false
X	false	false

요청 락이 다른 트랜잭션들이 든 락과 호환될 때만 승인. S락은 몇 개든 동시 가능(같이 읽기). 누군가 X락을 들면 다른 어떤 락도 불가. (읽기끼리는 충돌 없음, 쓰기가 끼면 순서에 따라 결과가 달라짐)

락만으로는 부족 — 직렬성 미보장

$T_{1}$ 이 $B := B - 50$ 쓰고 unlock(B)한 직후 $T_{2}$ 가 끼어들어 A(옛 값)와 B(새 값)를 읽어 display(A+B)하면, 50원 증발한 중간 상태를 본다 → 어떤 직렬 실행으로도 안 나오는 결과 = not serializable.

그래서 locking protocol(락 요청·해제 규칙 집합)이 필요. 프로토콜은 가능한 스케줄 집합을 제한해 serializability를 강제.

$S$ 가 프로토콜 따르는 트랜잭션들로 생성 가능하면 legal.
프로토콜이 serializability를 ensure = 그 프로토콜의 모든 legal 스케줄이 serializable.

Q2. Two-Phase Locking(2PL)은 어떻게 직렬성을 보장하는가?

A. 2PL은 락 사용을 “Growing(획득만) → Shrinking(해제만)” 두 단계로 강제해 conflict-serializable 스케줄을 보장한다. 트랜잭션들은 lock point 순서로 직렬화된다.

단계	할 수 있는 것	할 수 없는 것
Phase 1: Growing (성장기)	락 획득	락 해제
Phase 2: Shrinking (수축기)	락 해제	락 획득

락 개수가 시간축에서 산 모양이 된다. 한 번 풀면 그 뒤로 새 락 불가.

왜 직렬성이 보장되나 — lock point

마지막 락을 획득한 순간 = lock point. 2PL 하에선 트랜잭션들을 lock point 순서로 직렬화 가능함이 증명된다. 직관: lock point 시점에 트랜잭션은 만질 모든 데이터를 쥐고 있어, 충돌 트랜잭션은 그 전후로만 접근 가능 → 충돌이 한 방향으로 정렬 → precedence graph에 사이클 불가. 반대로 “풀었다 다시 잡기”를 허용하면 충돌 방향이 뒤섞여 사이클(비직렬성) 발생.

예시 (Fig 18.8 $T_{5}, T_{6}, T_{7}$ ): 각자 “다 잡고 → 풀기”를 지켜 legal하며 lock point 순서 $T_{5} \to T_{6} \to T_{7}$ 로 직렬화.

2PL 실제 진행 trace — 락을 잡고 푸는 과정 한 줄씩
$T_{1}$ (A→B 송금)과 $T_{2}$ (A를 읽어 출력)가 2PL을 따를 때, 시간순으로 각 트랜잭션이 무엇을 요청하고 시스템이 어떻게 응답하는지 따라가 보자.
시간   T1                         T2                    설명
─────────────────────────────────────────────────────────────────
t1   lock-X(A) ─ granted                            T1이 A 배타락 획득 [Growing]
t2   read(A); A:=A-50
t3                              lock-S(A) ─ WAIT     A에 X락 있음 → T2 대기!
t4   write(A)
t5   lock-X(B) ─ granted                            아직 Growing, 새 락 OK
t6   unlock(A) ──────────────────────────────────── ★ lock point 지남 [Shrinking 시작]
t7                              lock-S(A) ─ granted  A의 X락 풀려서 이제 승인
t8                              read(A)              T1이 갱신한 A=50을 읽음 ✓
t9   read(B); B:=B+50; write(B)
t10  unlock(B)                                       [Shrinking]
t11                             unlock(A)
핵심 관찰:

$T_{1}$ 은 t6에서 첫 unlock(A) 을 한 뒤로는 절대 새 락을 못 잡는다(Shrinking). 만약 여기서 다시 lock-X(C)를 시도하면 2PL 위반.

t3에서 $T_{2}$ 가 대기(WAIT) 했기 때문에, $T_{2}$ 는 $T_{1}$ 이 A를 다 고친 뒤(t8)에야 읽는다 → “공사 중 중간 상태”를 절대 못 본다 → serializable.

lock point 순서가 $T_{1}$ (t6) → $T_{2}$ (t7 이후) 이므로 직렬화 순서는 $⟨ T_{1}, T_{2} ⟩$ .

2PL도 deadlock은 못 막는다

2PL은 deadlock 자유를 보장하지 않는다. 둘 다 growing phase인 상태에서도 서로의 락을 기다리며 교착될 수 있다 (→ Q6).

Q3. Recoverability와 cascade 방지를 위해 2PL을 어떻게 확장하는가?

A. 기본 2PL은 직렬성만 보장하므로, 언제까지 락을 들고 있느냐를 강화한 Strict 2PL·Rigorous 2PL로 확장한다.

변형	규칙	보장
Strict 2PL	X락을 commit/abort까지 보유	recoverability + cascading rollback 방지
Rigorous 2PL	모든 락(S 포함)을 commit/abort까지 보유	트랜잭션이 commit 순서대로 직렬화

왜 X락을 끝까지?

X락을 commit 전 풀면 다른 트랜잭션이 uncommitted 값을 읽어가고, 원래 트랜잭션이 abort하면 연쇄 abort(cascading rollback). “도장 찍을(commit) 때까지 아무도 못 보게” 하면 연쇄가 원천 차단.

대부분 DBMS는 rigorous 2PL을 구현하면서 그냥 “two-phase locking”이라 부른다.

Q4. Lock conversion과 자동 락 획득은 무엇이고 왜 필요한가?

A. Lock conversion은 읽는 동안은 S락으로 공유하다 **쓰는 순간에만 X로 승격(upgrade)**해 동시성을 크게 높인다. 자동 락 획득은 read/write만 써도 시스템이 알아서 락을 잡아준다.

Lock Conversions

Growing: lock-S, lock-X, S→X (upgrade) 가능.
Shrinking: unlock-S, unlock-X, X→S (downgrade) 가능. (serializability 보장)

왜 필요한가 (Fig 18.9): $T_{8}$ 은 $a_{1} \dots a_{n}$ 다 읽고 합을 $a_{1}$ 에 씀, $T_{9}$ 는 $a_{1}, a_{2}$ 읽기만.

변환 없는 2PL: $T_{8}$ 이 처음부터 lock-X(a1) 필요 → $T_{9}$ 조차 접근 불가 → 동시 실행 불가.
변환 있는 2PL: $T_{8}$ 이 lock-S(a1)로 시작, 쓰기 직전 upgrade만 → 그 전엔 $T_{9}$ 가 자유롭게 읽음 → 동시 실행 가능.
Strict 2PL + conversions, Rigorous 2PL + conversions가 상용 DBMS에서 광범위 사용.

Automatic Acquisition of Locks

read(D): $T_{i}$ 가 D에 락 있으면 read; 없으면 다른 트랜잭션의 lock-X(D) 없어질 때까지 대기 후 lock-S(D) 부여 → read.
write(D): lock-X(D) 있으면 write; 없으면 다른 트랜잭션이 D에 어떤 락도 없을 때까지 대기 → lock-S 있으면 X로 upgrade, 없으면 lock-X 부여 → write.
모든 락은 commit/abort 후 해제(= rigorous).

Q5. 락은 실제로 어떻게 구현되는가?

A. Lock manager(별도 프로세스)가 메시지로 lock/unlock 요청을 받아 처리하고, 승인·대기 정보를 Lock table(데이터 항목으로 인덱싱된 인메모리 해시 테이블)에 기록한다.

Lock manager는 grant 메시지로 응답하거나, deadlock 시 rollback 요구 메시지를 보냄. 요청 트랜잭션은 응답까지 대기.
Lock table 운영: 항목별 요청 큐 유지(granted=진한 칸, waiting=연한 칸), 락 종류(S/X)도 기록. 새 요청은 큐 맨 뒤에 추가, 앞선 모든 락과 호환될 때만 즉시 승인. unlock 시 요청 삭제 후 뒤 대기 요청이 승인 가능한지 검사. abort 시 그 트랜잭션의 모든 요청 삭제(효율 위해 트랜잭션별 보유 락 리스트 유지).

Q6. Deadlock을 어떻게 예방·탐지·복구하는가?

A. 예방(prevention) = 애초에 못 생기게, 탐지(detection) = wait-for graph 사이클 검사, 복구(recovery) = victim 트랜잭션 rollback.

정의: 어떤 트랜잭션 집합의 모든 트랜잭션이 집합 내 다른 트랜잭션을 기다리면 deadlocked. 예: $T_{3}$ 이 B의 X락, $T_{4}$ 가 A의 S락을 들고 서로의 락을 기다림. (deadlock은 대부분 락킹 프로토콜에서 “필요악”. starvation도 가능 — X락 대기 중 S락이 줄줄이 통과하거나 같은 트랜잭션이 반복 rollback. manager 설계로 방지)

Prevention (예방)

전략	방법	직관
Pre-declaration	실행 전에 필요한 항목 전부 잠금	일부만 쥐고 기다리는 상황 자체가 없음
Graph-based	모든 항목에 partial ordering 부여, 그 순서대로만 잠금	모두 일방통행 → 마주보는 사이클 불가
Timeout 기반	정해진 시간만 대기, 초과 시 rollback	줄 안 줄면 포기하고 나중에

Timeout 특징: 구현 단순, deadlock도 결국 해소. 단 deadlock 아닌데 불필요 rollback 가능(적정 timeout 값 정하기 어려움), starvation 가능.

Detection (탐지) — Wait-for Graph

정점 = 트랜잭션, 간선 $T_{i} \to T_{j}$ = $T_{i}$ 가 $T_{j}$ 가 충돌 모드로 든 락을 대기.
핵심: deadlock ⟺ wait-for graph에 사이클. 주기적으로 탐지 알고리즘 실행.

wait-for graph로 deadlock 잡기 — 구체 예시
$T_{3}$ 은 B에 X락을 들고 A를 원하고, $T_{4}$ 는 A에 S락을 들고 B를 원한다. 시간순으로:
시간   T3                    T4                  상태
──────────────────────────────────────────────────────
t1   lock-X(B) ─ granted                       T3이 B 점유
t2                        lock-S(A) ─ granted   T4가 A 점유
t3   lock-S(A) ─ WAIT                           T3은 T4가 든 A를 기다림
t4                        lock-X(B) ─ WAIT      T4는 T3이 든 B를 기다림
                                                → 둘 다 영원히 대기!
wait-for graph (“누가 누구를 기다리나”):
     ┌──── A 기다림 ────▶
  ( T3 )              ( T4 )
     ◀──── B 기다림 ────┘
$T_{3} \to T_{4}$ (T3이 T4의 A를 기다림), $T_{4} \to T_{3}$ (T4가 T3의 B를 기다림). 사이클 발견 → deadlock! 탐지기는 둘 중 비용이 작은 쪽을 victim으로 골라 rollback해 사이클을 끊는다. (2PL은 이 상황을 못 막는다 — 둘 다 아직 Growing phase인데도 교착됐다.)

Recovery (복구)

사이클을 끊기 위해 비용 최소 트랜잭션을 victim으로 rollback.
되돌릴 범위: Total rollback(통째 abort·재시작) 또는 Partial rollback(다른 트랜잭션이 기다리는 락 해제 지점까지만).

Starvation 주의: 비용 위주면 같은 트랜잭션만 계속 victim → rollback 횟수를 비용에 포함(많이 희생됐으면 봐주기).

Q7. Timestamp 기반 프로토콜(TSO)은 어떻게 동작하는가?

A. 각 트랜잭션에 도착 순서대로 타임스탬프 TS( $T_{i}$ )(번호표)를 주고 timestamp order = serializability order로 강제한다. 항목마다 R-TS/W-TS를 두고 순서를 어기는 read/write는 즉시 rollback한다 — 기다림이 없으니 deadlock이 불가능.

타임스탬프: unique, 나중 트랜잭션일수록 큼 (시스템 시계 또는 논리 카운터).

각 항목 $Q$ 에 두 타임스탬프:

W-timestamp(Q): $Q$ 에 write 성공한 트랜잭션 중 최대 TS.
R-timestamp(Q): $Q$ 를 read 성공한 트랜잭션 중 최대 TS.

Read 규칙 ( $T_{i}$ 가 read(Q)):

$TS (T_{i}) < W-TS (Q)$ → 이미 덮어써진(미래 트랜잭션이 쓴) 값을 읽어야 함 → read 거부, rollback.
$TS (T_{i}) \geq W-TS (Q)$ → read 실행, $R-TS (Q) \leftarrow max (R-TS (Q), TS (T_{i}))$ .

Write 규칙 ( $T_{i}$ 가 write(Q)):

$TS (T_{i}) < R-TS (Q)$ → 만들려는 값을 이미 나중 트랜잭션이 “안 나올 것”이라 가정하고 읽어 감 → write 거부, rollback.
$TS (T_{i}) < W-TS (Q)$ → 낡은(obsolete) 값을 쓰려는 것 → write 거부, rollback.
그 외 → write 실행, $W-TS (Q) \leftarrow TS (T_{i})$ .

한 줄 요약

“내 번호보다 큰 번호가 다녀간 자리는 못 건드린다. 건드려야 하면 내가 죽고(rollback) 다시 태어난다.” — 기다림이 없어 deadlock 불가능.

TSO 규칙 위반으로 abort되는 과정 — TS 값 변화 추적

항목 $Q$ 의 초기 상태 R-TS(Q)=0, W-TS(Q)=0. 두 트랜잭션 $TS (T_{27}) = 27$ , $TS (T_{28}) = 28$ (번호가 클수록 나중 도착). 각 연산마다 규칙을 적용하고 타임스탬프를 갱신해 보자.

시간 연산 규칙 적용 결과 R-TS(Q) W-TS(Q)
시작 — — — 0 0
t1 $T_{27}$ : read(Q) $TS = 27 \geq$ W-TS=0 → OK read 성공 27 0
t2 $T_{28}$ : write(Q) $TS = 28 \geq$ R-TS=27, $\geq$ W-TS=0 → OK write 성공 27 28
t3 $T_{27}$ : write(Q) $TS = 27 <$ W-TS=28 → 규칙2 위반! write 거부 → $T_{27}$ rollback 27 28

왜 t3에서 죽는가: $T_{27}$ (번호 27)이 쓰려는 값은 직렬 순서상 $T_{28}$ (번호 28)보다 먼저 있어야 할 값이다. 그런데 t2에서 $T_{28}$ 이 이미 Q를 써 버렸다 → “내 번호보다 큰 번호가 이미 다녀간 자리”라 덮어쓰면 시간을 거스르게 된다. 그래서 $T_{27}$ 은 기다리지 않고 즉시 rollback하고 새 (더 큰) 타임스탬프를 받아 재시작한다.

☞ 2PL이라면 여기서 $T_{27}$ 이 대기했겠지만, TSO는 대기 없이 죽임 → 그래서 deadlock이 원천적으로 불가능하다.

시간	연산	규칙 적용	결과	R-TS(Q)	W-TS(Q)
시작	—	—	—	0	0
t1	$T_{27}$ : read(Q)	$TS = 27 \geq$ W-TS=0 → OK	read 성공	27	0
t2	$T_{28}$ : write(Q)	$TS = 28 \geq$ R-TS=27, $\geq$ W-TS=0 → OK	write 성공	27	28
t3	$T_{27}$ : write(Q)	$TS = 27 <$ W-TS=28 → 규칙2 위반!	write 거부 → $T_{27}$ rollback	27	28

Q8. TSO는 왜 옳고 어떤 한계가 있으며, Thomas’ Write Rule은 무엇인가?

A. TSO는 precedence graph 간선이 항상 “작은 TS → 큰 TS” 한 방향이라 사이클이 없어 항상 serializable하지만, recoverable·cascade-free가 아닐 수 있다. Thomas’ Write Rule은 낡은 write를 rollback 대신 무시해 동시성을 더 높인다.

정확성과 한계

정확성: 모든 간선이 “작은 TS → 큰 TS” 방향 → 사이클 불가 → 항상 conflict serializable.
장점: 기다림이 없으므로 deadlock 자유.
한계: cascade-free 아닐 수 있고 recoverable조차 아닐 수 있다(uncommitted 값 읽은 트랜잭션이 먼저 commit하는 경우 등).

Recoverability·Cascade Freedom 확보

해법	내용
Solution 1	모든 write를 처리 마지막에 몰아서 + 원자적 액션으로(쓰는 중 다른 트랜잭션 금지), abort 트랜잭션은 새 TS로 재시작
Solution 2	제한적 락킹: 데이터가 commit될 때까지 기다렸다 읽기
Solution 3	Commit dependency 추적으로 recoverability 보장

Thomas’ Write Rule

$T_{i}$ 가 write(Q) 시 $TS (T_{i}) < W-TS (Q)$ (이미 더 새 값이 있음)이면, 원래 TSO는 rollback하지만 Thomas’ Write Rule은 이 write를 그냥 무시(ignore)하고 $T_{i}$ 를 계속 진행. 나머지는 TSO와 동일.

왜 무시해도 되나

직렬 순서상 $T_{i}$ 의 write 결과는 어차피 곧 더 새 트랜잭션이 덮어쓸 값이고 그 사이 아무도 안 읽었다(읽었으면 R-TS 검사에서 걸림). “써 봤자 아무도 못 볼 낙서” → 건너뛰어도 결과 동일.

효과: 더 높은 동시성 — conflict-serializable은 아니지만 view-serializable한 일부 스케줄까지 허용.

2PL vs TSO 비교 정리

기준	Lock 기반 (2PL)	Timestamp 기반 (TSO)
순서 결정	lock point (실행 중 동적)	타임스탬프(도착 순서, 사전 고정)
충돌 시	대기(블로킹)	즉시 rollback(안 기다림)
Deadlock	발생 가능 → 예방/탐지/복구	불가능(대기 없음)
Recoverability·cascade	Strict/Rigorous 2PL로 해결	기본 TSO 미보장 → Solution 1~3
직렬성 원리	lock point 순서로 충돌 한 방향 정렬	간선이 항상 “작은 TS → 큰 TS”
실무	대부분 상용 DBMS (rigorous 2PL + conversion)	Thomas’ Write Rule 등 변형

이 슬라이드의 범위

Outline엔 Validation-Based, Multiple Granularity, Multiversion, Insert/Delete, Index Concurrency도 있으나, 강의는 Lock-Based와 Timestamp-Based만 다뤘다.

Juhyeon's Blog

탐색기

Ch18_Concurrency_Control

Chapter 18. Concurrency Control

Q1. Lock이란 무엇이고, 락만 쓰면 왜 serializability가 안 되는가?

두 가지 락 모드

Lock-Compatibility Matrix

락만으로는 부족 — 직렬성 미보장

Q2. Two-Phase Locking(2PL)은 어떻게 직렬성을 보장하는가?

Q3. Recoverability와 cascade 방지를 위해 2PL을 어떻게 확장하는가?

Q4. Lock conversion과 자동 락 획득은 무엇이고 왜 필요한가?

Lock Conversions

Automatic Acquisition of Locks

Q5. 락은 실제로 어떻게 구현되는가?

Q6. Deadlock을 어떻게 예방·탐지·복구하는가?

Prevention (예방)

Detection (탐지) — Wait-for Graph

Recovery (복구)

Q7. Timestamp 기반 프로토콜(TSO)은 어떻게 동작하는가?

Q8. TSO는 왜 옳고 어떤 한계가 있으며, Thomas’ Write Rule은 무엇인가?

정확성과 한계

Recoverability·Cascade Freedom 확보

Thomas’ Write Rule

2PL vs TSO 비교 정리

그래프 뷰

목차

Properties