11. 동시성 제어
11. 동시성 제어¶
학습 목표¶
- 동시성 제어가 데이터베이스 정확성에 필수적인 이유 이해
- 잠금 기반 프로토콜 마스터: 공유/배타 잠금, 2단계 잠금 및 변형들
- 데드락 분석 및 처리: 감지, 방지, 타임아웃 전략
- 잠금 세분도와 다중 세분도 잠금을 위한 의도 잠금 이해
- 타임스탬프 기반 프로토콜과 Thomas의 쓰기 규칙 학습
- 다중 버전 동시성 제어(MVCC)와 그 구현 이해
- 낙관적 동시성 제어(OCC)를 비관적 방법과 비교
1. 동시성 제어의 필요성¶
동시성을 허용하는 이유?¶
현대 데이터베이스 시스템은 수천 개의 동시 트랜잭션을 처리한다. 동시성이 없으면:
각각 10ms 소요되는 1000개 트랜잭션의 직렬 실행:
총 시간 = 1000 × 10ms = 10초
100개 동시 트랜잭션:
I/O 대기와 계산을 겹침
총 시간 ≈ 100ms (+ 오버헤드)
동시성의 이점: - 향상된 처리량(Throughput): 초당 더 많은 트랜잭션 - 감소된 응답 시간: 짧은 트랜잭션이 긴 트랜잭션 뒤에서 기다리지 않음 - 더 나은 자원 활용: 다른 트랜잭션이 I/O를 기다리는 동안 CPU가 작동
제어 없이 무엇이 잘못될 수 있는가?¶
동시성 제어 없이, 인터리빙된 실행은 각 트랜잭션이 개별적으로 정확하더라도 잘못된 결과를 생성할 수 있다.
손실된 업데이트 문제:
T₁: read(A) = 100 A = A - 10 = 90 write(A) = 90
T₂: read(A) = 100 A = A + 20 = 120 write(A) = 120
타임라인:
T₁: read(A)=100 ───────────── write(A)=90
T₂: read(A)=100 ──────────────── write(A)=120
결과: A = 120
기대: A = 110 (두 업데이트 모두 적용)
T₁의 업데이트가 손실됨!
일관되지 않은 읽기 문제:
불변식: A + B = 200 (초기 A=100, B=100)
T₁: read(A)=100 A=A-50=50 write(A)=50 ──── read(B)=100 B=B+50=150 write(B)=150
T₂: read(A)=50 read(B)=100 → A+B = 150 ≠ 200!
T₂가 T₁의 업데이트 후에 A를 읽지만 T₁의 업데이트 전에 B를 읽음 → 일관되지 않은 뷰
동시성 제어의 역할¶
동시성 제어 서브시스템은 트랜잭션의 동시 실행이 어떤 직렬 실행과 동등하도록 (직렬화 가능성) 보장하면서, 동시성 정도를 최대화한다.
┌──────────────────────┐
트랜잭션 ────→ │ 동시성 제어 │ ────→ 직렬화 가능 스케줄
T₁, T₂, T₃ │ 서브시스템 │ (정확한 결과)
│ - 잠금 │
│ - 타임스탬프 │
│ - MVCC │
└──────────────────────┘
2. 잠금 기반 프로토콜¶
2.1 잠금 유형¶
가장 기본적인 동시성 제어 메커니즘은 데이터 항목에 대한 잠금(Locks)을 사용한다.
공유 잠금(Shared Lock, S-lock): - 데이터 항목 읽기를 위해 획득 - 여러 트랜잭션이 동일한 항목에 대해 동시에 S-잠금을 보유할 수 있음 - 읽기 잠금이라고도 함
배타 잠금(Exclusive Lock, X-lock): - 데이터 항목 쓰기(수정)를 위해 획득 - 한 번에 하나의 트랜잭션만 항목에 대해 X-잠금을 보유할 수 있음 - 다른 트랜잭션은 항목에 대해 어떤 잠금(S 또는 X)도 동시에 보유할 수 없음 - 쓰기 잠금이라고도 함
잠금 호환성 행렬:
요청된 잠금
┌─────┬─────┐
│ S │ X │
┌────┼─────┼─────┤
보유 │ S │ Yes │ No │
잠금 ├────┼─────┼─────┤
│ X │ No │ No │
└────┴─────┴─────┘
S + S = 호환 (둘 다 진행 가능)
S + X = 비호환 (대기해야 함)
X + S = 비호환 (대기해야 함)
X + X = 비호환 (대기해야 함)
잠금 연산:
- lock-S(X) 또는 S(X): 항목 X에 대한 공유 잠금 요청
- lock-X(X) 또는 X(X): 항목 X에 대한 배타 잠금 요청
- unlock(X) 또는 U(X): 항목 X에 대한 잠금 해제
2.2 잠금 프로토콜 예¶
T₁ (A에서 B로 $50 이체): T₂ (A + B 읽기):
lock-X(A) lock-S(A) ← BLOCKED (T₁이 A에 X 보유)
read(A) = 100
A = A - 50
write(A) = 50
lock-X(B)
read(B) = 200
B = B + 50
write(B) = 250
unlock(A) lock-S(A) ← 이제 승인
unlock(B) read(A) = 50
lock-S(B)
read(B) = 250
print(A+B) = 300 ← 정확!
unlock(A)
unlock(B)
2.3 기본 잠금의 문제¶
접근 전에 잠금을 획득하고 사용 후에 해제하는 것만으로는 직렬화 가능성에 충분하지 않다:
잘못된 프로토콜 (잠금, 사용, 즉시 잠금 해제):
T₁: lock-X(A) read(A) write(A) unlock(A) lock-X(B) read(B) write(B) unlock(B)
T₂: lock-S(A) read(A) lock-S(B)
↑ BLOCKED (T₁이 X(B) 보유)
타임라인:
T₁: X(A) r(A) w(A) U(A) ──── X(B) r(B) w(B) U(B)
T₂: S(A) r(A) ────── S(B) r(B)
T₂가 T₁의 업데이트 후에 A를 읽지만 T₁의 업데이트 전에 B를 읽음.
T₂가 일관되지 않은 상태를 봄. 직렬화 가능하지 않음.
문제: T₁이 A의 잠금을 너무 일찍 해제함.
이것이 2단계 잠금을 동기화한다.
3. 2단계 잠금 (2PL)¶
3.1 기본 2단계 잠금¶
트랜잭션이 2단계 잠금(Two-Phase Locking, 2PL) 프로토콜을 따르는 경우, 모든 잠금 연산이 첫 번째 잠금 해제 연산보다 선행한다.
단계 1: 성장 단계 단계 2: 축소 단계
(잠금 획득, 해제 없음) (잠금 해제, 획득 없음)
보유된
잠금 수
^
│ ╱╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
│ ╱ ╲
└──────┬──────────┬──→ 시간
성장 잠금 축소
단계 포인트 단계
규칙: 1. 트랜잭션은 성장 단계에서 잠금을 획득할 수 있음 2. 트랜잭션이 잠금을 해제하면, 축소 단계에 들어감 3. 축소 단계에서는 새로운 잠금을 획득할 수 없음
정리: 스케줄의 모든 트랜잭션이 2PL 프로토콜을 따르면, 스케줄은 충돌 직렬화 가능하다.
증명 스케치: "잠금 포인트" (트랜잭션이 모든 잠금을 획득한 순간)가 직렬화 순서를 정의한다. T_i의 잠금 포인트가 T_j의 잠금 포인트보다 선행하면, T_i가 동등한 직렬 스케줄에서 T_j보다 먼저 나타난다. 이 순서는 충돌하는 연산이 잠금 호환성 규칙을 존중하기 때문에 일관적이다.
3.2 예: 2PL 실행¶
T₁ (2PL): T₂ (2PL):
lock-X(A)
read(A) lock-S(B)
A = A - 50 read(B)
write(A) lock-S(A) ← BLOCKED (T₁이 X(A) 보유)
lock-X(B)
read(B) ← 잠금 포인트 T₁
B = B + 50
write(B)
unlock(A) lock-S(A) ← 이제 승인 (축소 단계)
unlock(B) read(A)
← 잠금 포인트 T₂
unlock(A)
unlock(B)
직렬화 순서: T₁ before T₂ (T₁의 잠금 포인트가 더 이름)
T₂가 T₁의 완전한 이체 후 데이터베이스를 봄. 정확!
3.3 문제: 기본 2PL 하의 연쇄 롤백¶
기본 2PL은 직렬화 가능성을 보장하지만 복구 가능성은 보장하지 않는다:
T₁ (2PL): T₂:
lock-X(A)
read(A)
write(A)
unlock(A) ← 축소 단계: A 해제
lock-S(A)
read(A) ← T₁의 커밋되지 않은 데이터를 읽음!
...
ABORT ← T₁ 실패!
T₂가 T₁이 쓴 값을 읽었는데, 이제 중단되었음.
T₂도 롤백되어야 함 → 연쇄 롤백
3.4 엄격한 2단계 잠금 (Strict 2PL)¶
엄격한 2PL은 규칙을 추가한다: 모든 배타(X) 잠금은 트랜잭션이 커밋하거나 중단할 때까지 유지된다.
엄격한 2PL:
보유된
잠금 수
^
│ S-잠금은 X-잠금은
│ 해제될 수 있음 커밋/중단 시 해제
│ │ │
│ ╱╲ │
│ ╱ ╲─── ─── ─── ─── ─┤
│ ╱ S-잠금 │
│ ╱ 해제됨 │
│ ╱ ╲ │
│ ╱ ╲ │
└───────────────────┬──────→ 시간
커밋/중단
특성: - 충돌 직렬화 가능 (2PL에서 상속) - 엄격한 스케줄 (X-잠금된 항목에 대한 연쇄 롤백 없음) - 실제로 가장 일반적으로 사용됨
3.5 엄밀한 2단계 잠금 (Rigorous 2PL)¶
엄밀한 2PL은 모든 잠금(S와 X 모두)을 커밋 또는 중단까지 유지한다.
엄밀한 2PL:
보유된
잠금 수
^
│
│ ╱──────────────────────┤
│ ╱ │
│ ╱ 모든 잠금이 │
│ ╱ 커밋/중단까지 유지 │
│╱ │
└───────────────────┬──────→ 시간
커밋/중단
특성: - 충돌 직렬화 가능 - 엄격하고 연쇄 없음 - 직렬화 순서 = 커밋 순서 (추론하기 쉬움) - 구현하기 가장 간단한 프로토콜 - 대부분의 데이터베이스 시스템이 사용하는 잠금 프로토콜
3.6 2PL 변형 비교¶
| 변형 | S-잠금 해제 | X-잠금 해제 | 보장 |
|---|---|---|---|
| 기본 2PL | 잠금 포인트 후 | 잠금 포인트 후 | 충돌 직렬화 가능 |
| 엄격한 2PL | 잠금 포인트 후 | 커밋/중단 시 | + 엄격 (쓰기로부터 연쇄 없음) |
| 엄밀한 2PL | 커밋/중단 시 | 커밋/중단 시 | + 엄격 + 연쇄 없음 |
4. 데드락¶
4.1 데드락이란?¶
데드락(Deadlock)은 두 개 이상의 트랜잭션이 서로 잠금을 해제하기를 기다릴 때 발생하며, 순환 대기를 생성한다.
데드락 시나리오:
T₁: lock-X(A) ───── lock-X(B) ← BLOCKED (T₂가 X(B) 보유)
T₂: lock-X(B) ───── lock-X(A) ← BLOCKED (T₁이 X(A) 보유)
T₁이 T₂가 B를 해제하기를 기다림
T₂가 T₁이 A를 해제하기를 기다림
둘 다 진행할 수 없음 → 데드락
대기-포(Wait-For) 그래프:
T₁ ──기다림──→ T₂
↑ │
└──기다림──────┘
사이클 → 데드락!
4.2 데드락 감지¶
대기-포 그래프(Wait-For Graph, WFG):
- 노드는 트랜잭션을 나타냄
- 간선 T_i → T_j는 T_i가 T_j가 잠금을 해제하기를 기다리고 있음을 의미
- WFG의 사이클은 데드락을 나타냄
감지 알고리즘:
DETECT-DEADLOCK():
대기-포 그래프 G 유지
주기적으로 (또는 각 잠금 대기 시):
if G가 사이클 포함:
사이클에서 희생자 트랜잭션 선택
희생자 중단
잠금 해제 (사이클 깨짐)
희생자 선택 기준: 1. 가장 젊은 트랜잭션 (재실행할 작업이 가장 적음) 2. 잠금이 가장 적은 트랜잭션 (방해가 가장 적음) 3. 완료에 가장 가까운 트랜잭션 (이미 수행한 작업이 가장 많음 -- 낭비를 피하기 위해 선호되기도 함) 4. 우선순위가 가장 낮은 트랜잭션 (응용 프로그램 정의)
기아 방지: 동일한 트랜잭션이 반복적으로 희생자로 선택되지 않도록 보장. 일반적인 접근: 각 중단 후 우선순위 증가.
예:
4개 트랜잭션이 있는 대기-포 그래프:
T₁ → T₂ → T₃ → T₁ (T₁, T₂, T₃를 포함하는 사이클)
↗
T₄ ─┘ (T₄는 T₃를 기다리지만 사이클에 없음)
T₁, T₂, T₃ 중 데드락 감지.
희생자 선택 (예: 가장 젊으면 T₁).
T₁ 중단 → 잠금 해제 → T₃ 진행 가능 → T₂ 진행 가능 → T₄ 진행 가능.
4.3 데드락 방지¶
데드락이 발생한 후 감지하는 대신, 발생하지 않도록 방지할 수 있다.
Wait-Die 방식 (비선점형):
T_i가 T_j가 보유한 잠금을 요청할 때:
If T_i가 T_j보다 오래됨 (T_i가 더 이른 타임스탬프):
T_i가 대기 (오래된 것이 젊은 것을 기다림)
Else:
T_i가 죽음 (젊은 것이 롤백되고 재시작됨)
(T_i는 기아를 피하기 위해 원래 타임스탬프로 재시작됨)
기억법: "오래된 것 대기, 젊은 것 죽음"
예:
T₁ (ts=100, 더 오래됨) T₂ (ts=200, 더 젊음)가 보유한 잠금 요청
→ T₁ 대기 (오래된 것이 젊은 것을 기다림)
T₂ (ts=200, 더 젊음) T₁ (ts=100, 더 오래됨)이 보유한 잠금 요청
→ T₂ 죽음 (젊은 것이 죽고, 롤백됨)
Wound-Wait 방식 (선점형):
T_i가 T_j가 보유한 잠금을 요청할 때:
If T_i가 T_j보다 오래됨:
T_i가 T_j를 상처 입힘 (T_j가 롤백되도록 강제, T_i가 잠금을 가짐)
Else:
T_i가 대기 (젊은 것이 오래된 것을 기다림)
기억법: "오래된 것 상처 입힘, 젊은 것 대기"
예:
T₁ (ts=100, 더 오래됨) T₂ (ts=200, 더 젊음)가 보유한 잠금 요청
→ T₁이 T₂를 상처 입힘 (T₂가 롤백됨, T₁이 잠금을 가짐)
T₂ (ts=200, 더 젊음) T₁ (ts=100, 더 오래됨)이 보유한 잠금 요청
→ T₂ 대기 (젊은 것이 오래된 것을 기다림)
비교:
| 방식 | 더 오래된 것이 더 젊은 것에게 요청 | 더 젊은 것이 더 오래된 것에게 요청 |
|---|---|---|
| Wait-Die | 더 오래된 것 대기 | 더 젊은 것 죽음 (롤백됨) |
| Wound-Wait | 더 오래된 것이 더 젊은 것 상처 입힘 (선점) | 더 젊은 것 대기 |
두 방식 모두 데드락이 없다 왜냐하면 전체 순서를 강제하기 때문: Wait-Die에서, 트랜잭션은 더 젊은 것만 기다림; Wound-Wait에서, 트랜잭션은 더 오래된 것만 기다림. 둘 다 순환 대기를 허용하지 않음.
기아: 두 방식 모두 중단된 트랜잭션을 원래 타임스탬프로 재시작하므로, 점점 "오래되어" 결국 성공함.
4.4 타임아웃 기반 접근¶
단순하고 실용적인 접근: 트랜잭션이 타임아웃 임계값보다 오래 잠금을 기다리면, 데드락을 가정하고 중단한다.
LOCK-WITH-TIMEOUT(item, lock_type, timeout):
start_time = current_time()
while lock is not grantable:
if current_time() - start_time > timeout:
ABORT transaction // 데드락 가정
wait(short_interval)
grant lock
장점: - 구현이 간단 - 대기-포 그래프를 유지하는 오버헤드 없음 - 실제로 잘 작동 (대부분의 데드락이 빠르게 해결됨)
단점: - 실제로 데드락이 아닌 트랜잭션을 중단할 수 있음 (단지 느릴 뿐) - 타임아웃이 너무 짧으면: 불필요한 중단 - 타임아웃이 너무 길면: 실제 데드락이 너무 오래 지속
실제로: 대부분의 데이터베이스 시스템은 타임아웃(첫 번째 방어선)과 대기-포 그래프 감지(정확성)의 조합을 사용한다.
4.5 실제 데드락¶
-- PostgreSQL: 대기-포 그래프로 데드락 감지
-- 기본 deadlock_timeout = 1s
SET deadlock_timeout = '1s';
-- 세션 1:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- 그 다음 시도:
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
-- 세션 2가 id=2에 잠금을 보유하면 BLOCKED
-- 세션 2:
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;
-- 그 다음 시도:
UPDATE accounts SET balance = balance + 50 WHERE id = 1;
-- 세션 1이 id=1에 잠금을 보유하면 BLOCKED
-- deadlock_timeout 후: PostgreSQL이 데드락 감지
-- ERROR: deadlock detected
-- 한 세션이 중단되고, 다른 세션이 진행
5. 잠금 세분도¶
5.1 세분도 스펙트럼¶
잠금은 데이터 계층의 다른 수준에서 적용될 수 있다:
세분도 계층:
데이터베이스 ──→ 가장 조잡 (동시성 가장 낮음, 오버헤드 가장 낮음)
│
스키마
│
테이블
│
페이지 (블록)
│
행 (튜플) ──→ 가장 세밀 (동시성 가장 높음, 오버헤드 가장 높음)
│
필드 (속성) ──→ 실제로 거의 사용 안 됨
트레이드오프:
| 세밀한 세분도 (행) | 조잡한 세분도 (테이블) |
|---|---|
| 높은 동시성 | 낮은 동시성 |
| 높은 오버헤드 (많은 잠금) | 낮은 오버헤드 (적은 잠금) |
| OLTP에 최적 | 배치/분석에 최적 |
5.2 의도 잠금¶
다중 세분도 잠금(Multi-Granularity Locking, MGR)을 지원하려면, 의도 잠금(Intention Locks)이 필요하다. 조잡한 항목에 대한 의도 잠금은 더 세밀한 잠금이 하위 항목에 존재함(또는 요청될 것임)을 나타낸다.
의도 잠금을 포함한 잠금 유형:
| 잠금 | 의미 |
|---|---|
| IS (Intention Shared) | 일부 하위 항목이 S-잠금을 가지거나 가질 것임 |
| IX (Intention Exclusive) | 일부 하위 항목이 X-잠금을 가지거나 가질 것임 |
| S (Shared) | 이 노드와 모든 하위 항목에 공유 잠금 |
| X (Exclusive) | 이 노드와 모든 하위 항목에 배타 잠금 |
| SIX (Shared + Intention Exclusive) | 이 노드에 S-잠금, 일부 하위 항목에 IX |
5.3 의도 잠금을 포함한 호환성 행렬¶
요청된 잠금
┌─────┬─────┬─────┬─────┬─────┐
│ IS │ IX │ S │ SIX │ X │
┌────┼─────┼─────┼─────┼─────┼─────┤
│ IS │ Yes │ Yes │ Yes │ Yes │ No │
├────┼─────┼─────┼─────┼─────┼─────┤
보유 │ IX │ Yes │ Yes │ No │ No │ No │
잠금 ├────┼─────┼─────┼─────┼─────┼─────┤
│ S │ Yes │ No │ Yes │ No │ No │
├────┼─────┼─────┼─────┼─────┼─────┤
│SIX │ Yes │ No │ No │ No │ No │
├────┼─────┼─────┼─────┼─────┼─────┤
│ X │ No │ No │ No │ No │ No │
└────┴─────┴─────┴─────┴─────┴─────┘
5.4 다중 세분도 잠금 프로토콜¶
어떤 수준에서든 노드를 잠그려면:
LOCK-NODE(node, lock_type):
// 단계 1: 모든 조상에 의도 잠금 획득
for each ancestor from root down to parent of node:
if lock_type is S or IS:
acquire IS lock on ancestor
if lock_type is X, IX, or SIX:
acquire IX lock on ancestor
// 단계 2: 노드에 실제 잠금 획득
acquire lock_type on node
예: 트랜잭션 T₁이 테이블 T의 행 R₁을 읽고, 트랜잭션 T₂가 테이블 T의 행 R₂를 씀:
데이터베이스
┌───┴───┐
IS(T₁) IX(T₂)
│ │
테이블 T
┌───┴───┐
IS(T₁) IX(T₂)
│ │
페이지 P1 페이지 P2
IS(T₁) IX(T₂)
│ │
행 R1 행 R2
S(T₁) X(T₂)
T₁과 T₂가 다른 행에서 작동 → 어떤 수준에서도 충돌 없음 → 동시 실행!
예: 트랜잭션 T₃가 전체 테이블 T를 배타 접근으로 잠그려 함:
T₃가 테이블 T에 X-잠금 요청.
기존 잠금과의 호환성 확인:
- 테이블 T의 IS(T₁): IS가 X와 호환? → 아니오!
- 테이블 T의 IX(T₂): IX가 X와 호환? → 아니오!
T₃는 T₁과 T₂가 의도 잠금을 해제할 때까지 기다려야 함.
의도 잠금이 T₃가 행 수준 작업이 진행 중인 동안
테이블 수준 X-잠금을 얻는 것을 방지함.
5.5 SIX 잠금¶
SIX (Shared + Intention Exclusive) 잠금은 트랜잭션이 전체 테이블을 읽지만 몇 개의 행만 쓸 필요가 있을 때 유용하다.
SIX 없이:
옵션 1: 테이블에 S-잠금 (모든 쓰기자를 차단)
옵션 2: 테이블에 IX-잠금 + 각 행에 S-잠금 (비쌈, 많은 잠금)
SIX와 함께:
테이블에 SIX-잠금:
- S 구성요소: 전체 테이블 읽기
- IX 구성요소: 특정 행에 X-잠금 허용
예:
트랜잭션: "급여 < 30000인 직원의 급여 업데이트"
employees 테이블에 SIX-잠금:
- S: 급여 < 30000인 행을 찾기 위해 모든 행 읽기
- IX → X: 일치하는 특정 행에 씀
5.6 잠금 확대¶
트랜잭션이 너무 많은 세밀한 잠금을 획득하면, 시스템이 더 조잡한 세분도로 확대할 수 있다:
잠금 확대:
T₁이 테이블 T에 5000개의 행 수준 S-잠금을 가짐
→ 시스템이 단일 테이블 수준 S-잠금으로 확대
→ 모든 5000개 행 잠금 해제
→ 잠금 관리자의 메모리 사용 감소
임계값은 시스템마다 다름:
- SQL Server: ~테이블당 5000개 잠금
- Oracle: 잠금 확대 사용 안 함 (다른 접근 사용)
트레이드오프: 확대는 잠금 오버헤드를 줄이지만 동시성을 감소시킴 (다른 트랜잭션이 테이블 수준 잠금에 의해 차단될 수 있음).
6. 타임스탬프 기반 프로토콜¶
6.1 기본 타임스탬프 순서¶
잠금 대신, 각 트랜잭션 T_i는 시작 시 고유 타임스탬프 TS(T_i)를 할당받는다. 프로토콜은 충돌하는 연산이 타임스탬프 순서로 실행되도록 보장한다.
데이터 항목 메타데이터:
- W-timestamp(Q): Q를 성공적으로 쓴 트랜잭션의 가장 큰 타임스탬프
- R-timestamp(Q): Q를 성공적으로 읽은 트랜잭션의 가장 큰 타임스탬프
프로토콜:
트랜잭션 T_i가 데이터 항목 Q를 읽기 원함:
if TS(T_i) < W-timestamp(Q):
// T_i가 이미 더 젊은 트랜잭션에 의해 덮어쓰여진
// 값을 읽으려 함 → T_i가 "너무 늦음"
거부: T_i를 롤백하고 새 타임스탬프로 재시작
else:
읽기 허용
R-timestamp(Q) = max(R-timestamp(Q), TS(T_i))
트랜잭션 T_i가 데이터 항목 Q를 쓰기 원함:
if TS(T_i) < R-timestamp(Q):
// 더 젊은 트랜잭션이 이미 오래된 값을 읽음
// T_i의 쓰기가 그 읽기를 무효화할 것임 → 거부
거부: T_i를 롤백하고 새 타임스탬프로 재시작
if TS(T_i) < W-timestamp(Q):
// 더 젊은 트랜잭션이 이미 더 새로운 값을 씀
// T_i의 쓰기가 "구식"
거부: T_i를 롤백하고 새 타임스탬프로 재시작
else:
쓰기 허용
W-timestamp(Q) = TS(T_i)
특성: - 충돌 직렬화 가능성 보장 (직렬화 순서 = 타임스탬프 순서) - 데드락 없음 (트랜잭션이 기다리지 않음; 대신 롤백됨) - 연쇄 롤백 발생 가능 (기본 버전) - 잠금보다 중단률이 높음 (비관적 vs. 낙관적 트레이드오프)
6.2 예: 타임스탬프 순서¶
TS(T₁) = 100, TS(T₂) = 200
초기: W-ts(A) = 0, R-ts(A) = 0, W-ts(B) = 0, R-ts(B) = 0
T₁: read(A)
TS(T₁)=100 ≥ W-ts(A)=0 → 허용
R-ts(A) = max(0, 100) = 100
T₂: read(A)
TS(T₂)=200 ≥ W-ts(A)=0 → 허용
R-ts(A) = max(100, 200) = 200
T₁: write(A)
TS(T₁)=100 < R-ts(A)=200 → 거부!
(더 젊은 T₂가 이미 A를 읽음. T₁의 쓰기가
T₂의 읽기를 무효화할 것임.)
T₁이 롤백되고 새 타임스탬프로 재시작됨.
6.3 Thomas의 쓰기 규칙¶
쓰기에 대한 기본 타임스탬프 순서의 최적화:
트랜잭션 T_i가 데이터 항목 Q를 쓰기 원함:
if TS(T_i) < R-timestamp(Q):
거부 (기본 TO와 동일)
if TS(T_i) < W-timestamp(Q):
// 기본 TO에서: 거부
// Thomas의 쓰기 규칙: 쓰기를 무시 (건너뜀!)
// 이유? 더 젊은 트랜잭션이 이미 더 새로운 값을 씀.
// T_i의 쓰기가 어차피 덮어쓰여질 것임.
// 이것은 안전함 왜냐하면 미래 트랜잭션이 T_i의 값을 보지 않을 것이기 때문.
else:
쓰기 허용
W-timestamp(Q) = TS(T_i)
예:
TS(T₁) = 100, TS(T₂) = 200
T₂: write(A) → W-ts(A) = 200
T₁: write(A) → TS(T₁)=100 < W-ts(A)=200
기본 TO: T₁ 롤백
Thomas의 쓰기 규칙: T₁의 쓰기 건너뜀 (어차피 T₂에 의해 덮어쓰여질 것임)
T₁ 정상 진행
주의: Thomas의 쓰기 규칙은 뷰 직렬화 가능하지만 충돌 직렬화 가능하지 않을 수 있는 스케줄을 허용한다 (쓰기를 효과적으로 재정렬하기 때문).
7. 다중 버전 동시성 제어 (MVCC)¶
7.1 개념¶
MVCC는 각 데이터 항목의 여러 버전을 유지한다. 각 쓰기는 오래된 값을 덮어쓰는 대신 새 버전을 생성한다. 읽기는 오래된 버전에 접근할 수 있으므로, 읽기자가 쓰기자를 차단하지 않고 그 반대도 마찬가지다.
MVCC 버전:
데이터 항목 A:
버전 1: value=100, T₁이 타임스탬프 100에 씀
버전 2: value=150, T₃가 타임스탬프 150에 씀
버전 3: value=200, T₅가 타임스탬프 200에 씀
T₂ (타임스탬프 120): 버전 1 읽음 (value=100)
→ 타임스탬프 ≤ 120인 최신 버전
T₄ (타임스탬프 180): 버전 2 읽음 (value=150)
→ 타임스탬프 ≤ 180인 최신 버전
7.2 MVCC 읽기와 쓰기 규칙¶
트랜잭션 T_i가 데이터 항목 Q를 읽음:
버전 Q_k 찾기, 여기서:
- W-timestamp(Q_k) ≤ TS(T_i)
- W-timestamp(Q_k)가 그런 가장 큰 타임스탬프
Q_k의 값 반환
트랜잭션 T_i가 데이터 항목 Q를 씀:
버전 Q_k 찾기, 여기서:
- W-timestamp(Q_k) ≤ TS(T_i) (가장 가까운 오래된 버전)
Q_j를 Q_k 바로 다음 W-timestamp를 가진 버전이라 하자
if TS(T_i) < R-timestamp(Q_k):
거부 (더 젊은 트랜잭션이 Q_k를 읽고 그것이 변경되지 않기를 기대)
else:
W-timestamp = TS(T_i)인 새 버전 Q_i 생성
7.3 MVCC 이점과 비용¶
이점: - 읽기자가 쓰기자를 차단하지 않음: 읽기가 항상 적절한 버전을 찾음 - 쓰기자가 읽기자를 차단하지 않음: 오래된 버전이 동시 읽기자에게 사용 가능하게 유지됨 - 일관된 스냅샷: 각 트랜잭션이 일관된 시점 뷰를 봄 - 감소된 경합: 읽기 중심 워크로드에 대한 주요 성능 개선
비용: - 저장 오버헤드: 각 데이터 항목의 여러 버전 - 가비지 수집: 오래된 버전을 정리해야 함 (PostgreSQL의 vacuum) - 버전 탐색: 올바른 버전을 찾는 데 시간이 걸림 (특히 많은 버전이 있을 때)
7.4 PostgreSQL의 MVCC¶
PostgreSQL은 각 튜플(행 버전)에 xmin과 xmax 필드를 사용하여 MVCC를 구현한다:
튜플 헤더 필드:
┌────────┬────────┬───────────┬──────────┐
│ xmin │ xmax │ ctid │ data │
│ (생성자│(삭제자│(물리적 │ │
│ 트랜잭션│ 트랜잭션│ 위치) │ │
│ ID) │ ID) │ │ │
└────────┴────────┴───────────┴──────────┘
xmin: 이 버전을 생성한 트랜잭션 ID
xmax: 이 버전을 삭제/업데이트한 트랜잭션 ID (라이브면 0)
ctid: 다음 버전의 물리적 위치 (업데이트용)
PostgreSQL에서 UPDATE가 작동하는 방식:
UPDATE 전:
┌──────────┬──────────┬───────────────────┐
│ xmin=100 │ xmax=0 │ name='Alice' │ ← 현재 버전
└──────────┴──────────┴───────────────────┘
트랜잭션 200이 실행: UPDATE emp SET name='ALICE' WHERE id=1;
UPDATE 후:
┌──────────┬──────────┬───────────────────┐
│ xmin=100 │ xmax=200 │ name='Alice' │ ← 오래된 버전 (죽은 튜플)
└──────────┴──────────┴───────────────────┘
┌──────────┬──────────┬───────────────────┐
│ xmin=200 │ xmax=0 │ name='ALICE' │ ← 새 버전
└──────────┴──────────┴───────────────────┘
트랜잭션 150 (200 전에 시작): name='Alice' 봄 (xmin=100, xmax=200>150)
트랜잭션 250 (200 후에 시작): name='ALICE' 봄 (xmin=200≤250, xmax=0)
가시성 규칙 (간소화):
튜플이 트랜잭션 T에 보이는 경우:
1. xmin이 커밋되고 xmin ≤ snapshot_of(T)
2. xmax = 0 (삭제 안 됨) 또는 xmax > snapshot_of(T) (T의 스냅샷 후 삭제됨)
VACUUM: PostgreSQL의 가비지 수집기가 더 이상 어떤 활성 트랜잭션에도 보이지 않는 죽은 튜플을 제거한다.
-- 수동 vacuum
VACUUM employees;
-- 분석과 함께 vacuum (통계도 업데이트)
VACUUM ANALYZE employees;
-- 죽은 튜플 보기
SELECT relname, n_dead_tup, n_live_tup
FROM pg_stat_user_tables
WHERE relname = 'employees';
7.5 MySQL InnoDB의 MVCC¶
InnoDB는 MVCC 데이터를 다르게 저장한다:
InnoDB MVCC:
- 클러스터드 인덱스가 최신 버전 저장
- 오래된 버전은 UNDO LOG (롤백 세그먼트)에 저장
- 각 행은 숨겨진 컬럼 보유: DB_TRX_ID, DB_ROLL_PTR
┌────────────────────────────────────────┐
│ 클러스터드 인덱스 (최신 버전) │
│ DB_TRX_ID=200 │ DB_ROLL_PTR=ptr1 │
│ name='ALICE' │
└────────────────────────┬───────────────┘
│ (롤백 포인터 따라가기)
▼
┌────────────────────────────────────────┐
│ Undo Log (이전 버전) │
│ DB_TRX_ID=100 │ DB_ROLL_PTR=null │
│ name='Alice' │
└────────────────────────────────────────┘
PostgreSQL과의 주요 차이: - PostgreSQL: 힙에 새 버전, 오래된 버전이 죽은 튜플이 됨 - InnoDB: 클러스터드 인덱스에 최신 버전, 오래된 버전은 undo log에 - InnoDB 접근: 힙 블로트 적음, 하지만 undo log가 커질 수 있음
8. 낙관적 동시성 제어 (OCC)¶
8.1 개념¶
낙관적 동시성 제어 (또는 검증 기반 프로토콜)는 충돌이 드물다고 가정하고 트랜잭션이 자유롭게 실행하도록 하며, 커밋 시점에만 정확성을 검증한다.
비관적 (잠금):
"충돌이 발생하지 않도록 방지"
접근 전에 잠금 → 안전 보장 → 대기/차단 가능
낙관적 (OCC):
"충돌이 없다고 가정, 마지막에 확인"
자유롭게 실행 → 커밋 시 검증 → 충돌 감지되면 중단
8.2 세 단계¶
각 트랜잭션은 세 단계를 거친다:
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ 단계 1: │ │ 단계 2: │ │ 단계 3: │
│ 읽기 │ → │ 검증 │ → │ 쓰기 │
│ │ │ │ │ │
│ DB에서 읽기 │ │ 충돌 │ │ 쓰기를 │
│ 쓰기는 │ │ 확인 │ │ 데이터베이스에│
│ 개인 작업 │ │ 다른 │ │ 적용 │
│ 영역으로 │ │ 트랜잭션과 │ │ │
└──────────────┘ └──────────────┘ └──────────────┘
단계 1 -- 읽기 단계: - 모든 읽기는 데이터베이스에서 옴 - 모든 쓰기는 개인 작업 영역으로 (데이터베이스가 아님) - 잠금이 획득되지 않음
단계 2 -- 검증 단계: - 트랜잭션의 읽기와 쓰기가 다른 동시 트랜잭션과 충돌하는지 확인 - 검증 성공하면, 쓰기 단계로 진행 - 검증 실패하면, 중단하고 재시작
단계 3 -- 쓰기 단계: - 개인 작업 영역의 변경사항을 데이터베이스에 적용 - 이 단계는 원자적으로 수행됨 (짧은 잠금 사용)
8.3 검증 규칙¶
각 트랜잭션 T_i는 검증 단계 시작 시 타임스탬프를 할당받는다. TS(T_i)를 이 타임스탬프라 하자.
T_i의 검증을 위해, TS(T_j) < TS(T_i) (T_j가 먼저 검증됨)인 모든 트랜잭션 T_j에 대해 확인:
VALIDATE(T_i):
for each T_j where TS(T_j) < TS(T_i):
// 조건 1: T_j가 T_i가 읽기 단계 시작 전에 세 단계 모두 완료
if T_j completed write phase before T_i started read phase:
OK (전혀 겹치지 않음)
// 조건 2: T_j가 T_i가 쓰기 단계 시작 전에 쓰기 단계 완료,
// 그리고 T_j의 쓰기 집합이 T_i의 읽기 집합과 교차하지 않음
else if T_j completed write phase before T_i started validation:
if WriteSet(T_j) ∩ ReadSet(T_i) == ∅:
OK
else:
FAIL → T_i 중단
// 조건 3: T_j가 아직 쓰기 단계 완료 안 함
// 그리고 T_j의 쓰기 집합이 T_i의 읽기나 쓰기 집합과 교차하지 않음
else:
if WriteSet(T_j) ∩ ReadSet(T_i) == ∅
AND WriteSet(T_j) ∩ WriteSet(T_i) == ∅:
OK
else:
FAIL → T_i 중단
return VALID
8.4 예: OCC 검증¶
T₁: ReadSet = {A, B}, WriteSet = {A}
T₂: ReadSet = {B, C}, WriteSet = {C}
타임라인:
T₁: ──읽기──┤──검증(ts=1)──┤──쓰기──┤
T₂: ────읽기────┤──검증(ts=2)──┤──쓰기──┤
T₂를 T₁에 대해 검증 (TS(T₁)=1 < TS(T₂)=2):
T₁이 T₂가 검증 시작하기 전에 쓰기 완료? → 예 (조건 2)
WriteSet(T₁) ∩ ReadSet(T₂) = {A} ∩ {B, C} = ∅ → 충돌 없음!
T₂ 유효 ✓
대신 WriteSet(T₁) = {B}이면:
WriteSet(T₁) ∩ ReadSet(T₂) = {B} ∩ {B, C} = {B} → 충돌!
T₂ 무효 → 중단하고 재시작
8.5 OCC를 사용해야 할 때¶
OCC가 이상적인 경우: - 충돌이 드물 (대부분 읽기 전용 워크로드) - 트랜잭션이 짧음 (검증 오버헤드가 작업에 비해 작음) - 높은 경합이 잠금으로 과도한 차단을 일으킬 것
OCC가 나쁜 경우: - 충돌이 빈번 (높은 중단률이 작업 낭비) - 트랜잭션이 김 (중단 후 재실행 비용이 높음) - 쓰기 중심 워크로드 (많은 충돌)
실제 사용: - Google의 Spanner가 읽기-쓰기 트랜잭션에 OCC 변형 사용 - 많은 웹 응용 프로그램이 "낙관적 잠금" 패턴 사용 (버전 번호)
# 응용 프로그램 수준 낙관적 잠금 패턴:
# 단계 1: 버전과 함께 레코드 읽기
row = db.execute("SELECT *, version FROM products WHERE id = ?", [product_id])
old_version = row.version
# 단계 2: 새 값 계산 (응용 프로그램 코드에서)
new_price = compute_new_price(row)
# 단계 3: 버전 확인과 함께 쓰기
result = db.execute(
"UPDATE products SET price = ?, version = version + 1 "
"WHERE id = ? AND version = ?",
[new_price, product_id, old_version]
)
# 단계 4: 업데이트 성공 확인
if result.rows_affected == 0:
# 버전 변경됨 → 다른 사람이 수정 → 재시도
raise ConflictError("동시 수정 감지됨")
9. 동시성 제어 방법 비교¶
9.1 요약 표¶
| 방법 | 접근 | 데드락 | 연쇄 | 최적 용도 |
|---|---|---|---|---|
| 기본 2PL | 비관적 (잠금) | 가능 | 가능 | 범용 |
| 엄격한 2PL | 비관적 (잠금) | 가능 | 아니오 (쓰기) | 대부분의 OLTP 시스템 |
| 엄밀한 2PL | 비관적 (잠금) | 가능 | 아니오 | 단순성이 중요할 때 |
| 타임스탬프 순서 | 낙관적 (타임스탬프) | 불가능 | 가능 | 낮은 충돌 워크로드 |
| Thomas의 쓰기 규칙 | 낙관적 (타임스탬프) | 불가능 | 가능 | 쓰기 중심, 낮은 충돌 |
| MVCC | 다중 버전 | 구현에 따름 | 아니오 (스냅샷 통해) | 읽기 중심, 혼합 |
| OCC (검증) | 낙관적 (검증) | 불가능 | 아니오 | 대부분 읽기, 짧은 트랜잭션 |
9.2 결정 가이드¶
시작
│
├─ 워크로드가 읽기 중심?
│ ├─ 예 → MVCC (PostgreSQL, Oracle 스타일)
│ └─ 아니오 → 계속
│
├─ 충돌이 드물?
│ ├─ 예 → OCC 또는 타임스탬프 순서
│ └─ 아니오 → 계속
│
├─ 범위 쿼리 / 술어 잠금 필요?
│ ├─ 예 → 인덱스 범위 잠금을 포함한 2PL
│ └─ 아니오 → 계속
│
├─ 엄격한 복구 가능성 필요?
│ ├─ 예 → 엄격한 2PL 또는 엄밀한 2PL
│ └─ 아니오 → 기본 2PL로 충분할 수 있음
│
└─ 분산 시스템?
├─ 예 → MVCC + 분산 타임스탬프 (Spanner)
└─ 아니오 → 엄격한 2PL이 안전한 기본값
9.3 실제 시스템이 사용하는 것¶
| 데이터베이스 | 주요 방법 |
|---|---|
| PostgreSQL | MVCC (힙 기반) + Serializable용 SSI |
| MySQL InnoDB | MVCC (undo log) + Serializable용 넥스트 키 잠금 |
| Oracle | MVCC (undo 테이블스페이스) + 행 수준 잠금 |
| SQL Server | 잠금 기반 (기본) + MVCC (SNAPSHOT 격리 선택) |
| CockroachDB | MVCC + SSI (기본적으로 직렬화 가능) |
| Google Spanner | MVCC + TrueTime + 2PL (외부 일관성) |
10. 연습문제¶
개념적 질문¶
연습문제 1: 공유(S)와 배타(X) 잠금의 차이를 설명하라. 왜 여러 S-잠금이 동일한 데이터 항목에 공존할 수 있지만 여러 X-잠금은 안 되는가?
연습문제 2: 트랜잭션 T가 2PL을 따르지만 모든 잠금을 맨 처음(모든 읽기나 쓰기 전)에 획득하고 맨 마지막(마지막 연산 후)에 모두 해제한다. T가 엄격한 2PL을 따르는가? 엄밀한 2PL은? 둘 다? 설명하라.
연습문제 3: Wait-Die와 Wound-Wait 데드락 방지 방식을 비교하라. 각각에 대해, 어떤 트랜잭션이 우선권을 얻는지와 기아가 왜 피해지는지 설명하라.
잠금 기반 프로토콜 문제¶
연습문제 4: 세 트랜잭션을 고려하라:
T₁: read(A), write(A), read(B), write(B)
T₂: read(B), write(B)
T₃: read(A), read(B)
(a) T₁과 T₃가 동시에 진행할 수 있지만 T₂가 대기해야 하는 엄격한 2PL 하의 가능한 실행을 보여라. (b) 2PL 하에서 T₁과 T₂ 사이에 데드락이 발생할 수 있는가? 그렇다면, 시나리오를 보여라.
연습문제 5: 다음 잠금 요청이 순서대로 도착한다고 고려하라:
T₁: lock-S(A)
T₂: lock-X(B)
T₃: lock-S(A)
T₁: lock-X(B) → wait (T₂가 X(B) 보유)
T₂: lock-S(A) → ?
T₃: lock-X(A) → ?
(a) 각 단계에서 무슨 일이 일어나는가? (b) 데드락이 있는가? 그렇다면, 대기-포 그래프의 사이클을 식별하라. (c) Wait-Die가 이를 어떻게 해결하는가 (TS(T₁) < TS(T₂) < TS(T₃) 가정)?
연습문제 6: 다중 세분도 잠금 시스템에서, 트랜잭션 T₁이 테이블 A의 행을 읽고 테이블 B의 특정 행을 배타적으로 업데이트하려 한다. 트랜잭션 T₂가 전체 테이블 B를 읽으려 한다. 각 트랜잭션이 획득해야 하는 의도 잠금을 보여주고 동시에 실행할 수 있는지 결정하라.
타임스탬프와 MVCC 문제¶
연습문제 7: TS(T₁)=100, TS(T₂)=150, TS(T₃)=200이 주어졌다. 초기 타임스탬프: W-ts(A)=0, R-ts(A)=0, W-ts(B)=0, R-ts(B)=0.
기본 타임스탬프 순서를 사용하여 다음 연산을 실행하라. 각 연산에 대해, 허용되는지 또는 거부되는지 명시하고, 타임스탬프를 업데이트하라.
T₂: read(A)
T₃: read(A)
T₁: write(A) ← 무슨 일이 일어나는가?
T₂: write(A)
T₃: read(B)
T₂: write(B) ← 무슨 일이 일어나는가?
T₁: read(B) ← 무슨 일이 일어나는가?
이제 Thomas의 쓰기 규칙을 사용하여 연습문제를 반복하라. 어떤 연산이 다른 결과를 가지는가?
연습문제 8: PostgreSQL의 MVCC 구현에서, 다음이 단계별로 무슨 일이 일어나는지 설명하라: 1. 트랜잭션 T₁ (txid=100)이 행을 삽입 2. 트랜잭션 T₂ (txid=150)가 테이블을 읽음 3. 트랜잭션 T₁이 커밋 4. 트랜잭션 T₃ (txid=200)가 테이블을 읽음 5. 트랜잭션 T₂가 테이블을 다시 읽음
각 트랜잭션이 각 단계에서 무엇을 보는가? READ COMMITTED와 REPEATABLE READ 격리 수준 모두를 고려하라.
OCC 문제¶
연습문제 9: 세 트랜잭션이 OCC 하에서 실행된다:
T₁: ReadSet={A,B}, WriteSet={A} Start: t=0, Validate: t=5
T₂: ReadSet={B,C}, WriteSet={B} Start: t=1, Validate: t=6
T₃: ReadSet={A,C}, WriteSet={C} Start: t=2, Validate: t=7
(a) T₂를 T₁에 대해 검증하라. 통과하는가? (b) T₃를 T₁과 T₂에 대해 검증하라. 통과하는가? (c) T₁의 WriteSet이 {A} 대신 {B}이면, 어떤 검증이 변경되는가?
분석과 설계¶
연습문제 10: 은행 응용 프로그램이 다음 트랜잭션 유형을 가진다: - 잔액 조회 (하나의 계좌 읽기): 트랜잭션의 60% - 이체 (두 계좌 쓰기): 트랜잭션의 30% - 월말 보고서 (모든 계좌 읽기): 트랜잭션의 10%
어떤 동시성 제어 방식 (엄격한 2PL, MVCC, 또는 OCC)를 추천하는가? 처리량, 응답 시간, 각 트랜잭션 유형의 특성을 고려하여 답을 정당화하라.
연습문제 11: PostgreSQL의 MVCC가 VACUUM을 필요로 하는 이유를 설명하라. VACUUM이 절대 실행되지 않으면 어떤 일이 일어나는가? 누락되거나 느린 VACUUM 프로세스의 증상은 무엇인가 (테이블 블로트, 트랜잭션 ID 랩어라운드)?
연습문제 12: Google Spanner는 TrueTime (GPS + 원자 시계)을 사용하여 트랜잭션에 전역적으로 일관된 타임스탬프를 할당한다. 일반 시계 동기화(NTP)가 전역 분산 MVCC 시스템에 왜 충분하지 않은지 설명하라. TrueTime이 NTP가 보장할 수 없는 어떤 속성을 제공하는가?