여러 트랜잭션이 동시에 달려도
직렬화 가능하게 만드는 법

두 가지 Lock 모드

Shared (S) — 공유 lock

읽기(read)만 가능. lock-S(Q)로 요청. 여러 트랜잭션이 같은 항목에 동시에 S lock을 보유할 수 있다.

Exclusive (X) — 배타 lock

읽기(read)와 쓰기(write) 모두 가능. lock-X(Q)로 요청. 한 트랜잭션이 X lock을 보유하면 다른 어떤 lock도 불가.

동시성 제어 관리자(CC manager)가 lock 요청을 받아 허가(grant)하거나 대기시킨다.

왜 단순 locking으로는 부족한가

필요할 때 lock 걸고 끝나면 바로 unlock(unlock을 일찍)하는 단순 locking은 직렬가능성(serializability)을 보장하지 못한다. 한 트랜잭션이 unlock한 직후 다른 트랜잭션이 끼어들어 비직렬 스케줄이 만들어질 수 있기 때문. → 그래서 2PL이 필요하다(다음 절).

두 단계

Growing phase (성장)

lock을 획득(O)할 수 있고 해제(X)는 할 수 없다.

Shrinking phase (수축)

lock을 해제(O)할 수 있고 획득(X)은 할 수 없다.

Lock point

마지막 lock을 획득한 지점(= growing의 끝). lock point 순서로 트랜잭션이 직렬화된다.

강화된 변형

Strict 2PL

모든 X lock을 commit/abort 시점까지 유지. → cascadeless(연쇄 롤백 없음).

Rigorous 2PL

모든 lock(S, X)을 commit까지 유지. commit 순서로 직렬화 → recoverable + cascadeless. 대부분의 상용 DB가 채택.

2PL은 직렬가능성의 충분조건이지 필요조건은 아니다 — 2PL이 아니어도 conflict-serializable한 스케줄이 존재한다.

정의와 예

트랜잭션 집합 안의 모든 트랜잭션이 서로가 보유한 lock을 기다린다.

// 교착 예시
T3: lock-X(B)... write(B)  → 이제 lock-X(A) 대기
T4: lock-S(A)... read(A)   → 이제 lock-S(B) 대기
// T3는 A를(T4 보유), T4는 B를(T3 보유) 기다림 → 순환!

locking의 necessary evil(피할 수 없는 부작용). Starvation(기아)도 발생 가능.

Deadlock prevention (예방)

• ① Pre-declaration — 실행 전에 필요한 모든 항목을 한꺼번에 lock.
• ② Partial ordering — 데이터 항목에 순서를 정하고 그 순서대로만 lock(graph-based).
• ③ Timestamp 기반 — Wait-Die / Wound-Wait (아래 시뮬레이터).
• ④ Timeout — 일정 시간만 대기 후 rollback. 간단하나 불필요한 rollback·starvation 가능.

Wait-for graph 구성 & cycle 탐지 (DFS)

정점=트랜잭션, 간선 Ti → Tj = "Ti가 Tj가 보유한 lock을 기다림". Ti의 lock 요청이 Tj가 보유한 lock과 충돌해 대기에 들어갈 때 간선을 추가하고, lock을 허가/해제하면 간선을 제거한다. cycle ⟺ deadlock.

// 주기적(periodic) cycle detection — DFS 3색
function hasCycle(G):
  color[v] = WHITE  // 모든 정점
  for v in G:
    if color[v] == WHITE:
      if dfs(v): return true
  return false

function dfs(u):
  color[u] = GRAY        // 재귀 스택 위
  for w in adj[u]:
    if color[w] == GRAY: return true  // back-edge=cycle
    if color[w] == WHITE and dfs(w): return true
  color[u] = BLACK       // 완료
  return false

호출 주기는 trade-off: 너무 자주=오버헤드↑, 너무 드물게=탐지 지연(불필요한 대기·잠재 starvation)↑. 보통 고정 주기 또는 대기 트랜잭션 수에 따라 호출.

Victim selection (희생자 선택) 비용함수

cycle이 발견되면 cycle을 깨기 위해 최소 비용(minimum cost) 트랜잭션을 골라 rollback한다. 비용 추정 요소:

• ① 남은 작업 / 경과 시간 — 이미 한 일과 끝까지 남은 일이 적을수록 rollback 비용↓.
• ② 사용·보유한 데이터 항목 수 (보유 lock 수).
• ③ 완료에 더 필요한 항목 수.
• ④ rollback에 연루되는 트랜잭션 수 (cascading).

Rollback 범위 & starvation 방지

• Total rollback(abort 후 재시작) vs partial rollback(cycle을 깰 만큼만 되돌림).
• Starvation 방지: 같은 트랜잭션이 반복해서 victim이 되면 영원히 진행 못 함 → 비용함수에 rollback 횟수(rollback count)를 포함시켜, 일정 횟수를 넘으면 victim 후보에서 제외(가장 오래된 트랜잭션 보호).

계층(hierarchy)과 trade-off

DB > File > Table > Page > Record 의 트리. 어떤 노드를 lock하면 그 자손(descendant)이 같은 모드로 implicit하게 lock된다.

• Fine granularity(작은 단위, 예: record): 동시성↑, lock 오버헤드↑.
• Coarse granularity(큰 단위, 예: DB): 동시성↓, 오버헤드↓.

Intention locks (의도 lock)

IS

하위(descendant)에 S lock을 걸 의도가 있음.

IX

하위에 S 또는 X lock을 걸 의도가 있음.

SIX

이 subtree 전체를 S + 하위 일부에 X (= S + IX).

Graph-based protocol

데이터 항목 집합에 부분순서(partial order)를 부여한다 — 방향 비순환 그래프(database graph, DAG). "di → dj 이면 d_i·d_j 둘 다 접근하는 트랜잭션은 반드시 d_i를 먼저 접근한다"는 사전 지식(prior knowledge)을 활용한다.

Tree protocol은 이 그래프가 트리(rooted tree)인 가장 단순한 경우다.

Tree protocol 규칙

• ① X-lock만 사용한다(이 단순형은 exclusive lock만).
• ② 첫 lock은 임의의 노드에 걸 수 있다.
• ③ 이후 노드 Q를 lock하려면 Q의 부모(parent)를 현재 Ti가 lock하고 있어야 한다.
• ④ 언제든(at any time) unlock 할 수 있다(2PL의 shrinking 제약 없음).
• ⑤ 한 번 unlock한 노드는 같은 트랜잭션이 다시 lock할 수 없다(re-lock 금지).

문제

T1: SELECT count(*) FROM instructor
    WHERE dept = 'Physics';   -- predicate read
T2: INSERT instructor(..., dept='Physics');
    -- 같은 튜플을 건드린 적 없지만
    -- T1의 "조건 집합"을 바꿈 → conflict!

기존 튜플에 tuple lock만 걸어서는 막을 수 없다 → non-serializable.

해결: Index locking & Next-key

• 모든 relation은 최소 하나의 index를 가진다고 가정.
• Index locking: lookup은 해당 index leaf node를 S-lock, insert/delete는 X-lock (2PL 준수).
• Next-key locking: lookup 조건을 만족하는 값 + 그 다음 키 값(next key)까지 함께 lock → 사이에 끼어드는 insert를 차단하면서 동시성↑.

정의

TS(Ti)

트랜잭션 Ti가 시스템에 진입할 때 부여되는 고유 timestamp. 나중 트랜잭션이 strictly larger(logical counter도 가능).

W-timestamp(Q)

Q에 성공적으로 write한 트랜잭션들의 TS 중 최댓값.

R-timestamp(Q)

Q를 성공적으로 read한 트랜잭션들의 TS 중 최댓값.

목표: timestamp 순서 = 직렬화 순서.

규칙(rules)

3 단계 (3 phases)

① Read & execution

DB에서 read하고 연산 수행. write는 DB가 아닌 local 변수에만 한다.

② Validation

다른 트랜잭션과 충돌하는지 검증 테스트(validation test)를 수행.

③ Write

통과하면 local 변수를 DB에 반영, 실패하면 rollback.

3 timestamp

StartTS(Ti)

read 단계 시작 시각.

ValidationTS(Ti)

validation 단계 진입 시각. 이 값이 직렬화 순서 TS(Ti).

FinishTS(Ti)

write 단계 완료 시각.

commit time을 직렬화 순서로 삼는다. 충돌이 낮으면 동시성↑.

버전과 가시성

하나의 논리적 객체가 여러 물리적 버전을 가진다. 각 버전은 begin-TS, end-TS를 갖는다.

• Writers don't block readers / readers don't block writers.
• write-write 충돌 시 상대가 commit할 때까지 wait.

MV2PL 보충

update 트랜잭션은 rigorous 2PL로 동작(read=최신 committed). 새 버전 TS=∞로 만들고 commit 시 ts-counter+1로 확정하며 카운터 증가. read-only 트랜잭션은 버전을 통해 lock 없이 읽는다.

버전과 timestamp

각 데이터 항목 Q는 버전열 Q1, Q2, …, Qk를 가진다. 각 버전 Q_i는:

content

Q_i가 담은 값.

W-timestamp(Q_i)

이 버전을 만든 트랜잭션의 TS.

R-timestamp(Q_i)

이 버전을 읽은 트랜잭션들의 TS 중 최댓값.

규칙(rules) — Ti, TS=TS(Ti)

동작과 장점

• 트랜잭션은 시작 시점의 일관된 스냅샷(consistent snapshot)을 읽는다(no torn writes).
• First-committer-wins: 같은 객체를 두 트랜잭션이 update하면 늦게 commit하는 쪽이 abort.
• 장점: read가 절대 차단되지 않음, read committed급 성능, dirty read·non-repeatable read 없음.

단점: serializability 깨짐

SI는 강력하지만 완전한 직렬가능성은 보장하지 않는다. first-committer-wins는 같은 객체에 대한 충돌만 잡는다. 서로 다른 객체를 쓰면 못 잡는다 → Write Skew.

문제 → 발상

SI는 Write Skew로 직렬성이 깨진다. 직렬성 위반은 항상 트랜잭션 충돌 그래프(serialization graph)의 cycle인데, SI 하에서 발생하는 cycle에는 반드시 두 개의 연속된 rw-antidependency 간선이 들어 있음이 알려져 있다(Adya, Fekete et al.).

rw-antidependency
(읽기-쓰기 반의존)

Ti가 어떤 데이터를 읽은 뒤, Tj가 같은 데이터의 새 버전을 쓰는데, Tj의 write가 Ti의 read 이후에 와서 Ti가 그 새 값을 못 본 관계. 표기 Ti --rw--> Tj.

Dangerous structure & pivot

SSI는 실행 중 in/out rw-간선 플래그를 추적한다. 한 트랜잭션 T_pivot이 들어오는 rw-간선과 나가는 rw-간선을 동시에 가지면 — 즉

이 dangerous structure가 탐지되면 cycle 가능성이 있으므로, 세 트랜잭션 중 하나를 abort(보통 pivot 또는 더 나중 것)한다. 실제 cycle이 아닐 수도 있어 → false-positive abort가 발생할 수 있는 보수적(conservative) 방식.

OLTP vs OLAP 일관성 요구

• OLTP(짧은 갱신 트랜잭션 多): 정확성이 중요 → 강한 격리(보통 RC/RR, 자금 이체 등은 직렬성). 동시성 throughput이 핵심.
• OLAP / 리포팅(대규모 read-only 분석): 약간의 비일관성을 감수하고 read-only · 낮은 격리(또는 스냅샷)로 lock 경합을 피한다.

격리수준 ↔ 동시성 trade-off

격리수준을 낮추면 허용 이상현상(dirty/non-repeatable read, phantom)↑·동시성↑·오버헤드↓. 높이면 정확성↑·동시성↓.

2PL이 보장하는 것 / 못 하는 것

• 보장: conflict serializability(기본 2PL). Strict/Rigorous는 추가로 recoverable·cascadeless.
• 못 함: deadlock-free가 아니다(별도 prevention/detection 필요). 또한 phantom은 tuple lock만으로는 못 막아 index/next-key locking이 필요.

즉 "2PL을 쓰면 끝"이 아니라, deadlock 처리·phantom 방지를 함께 갖춰야 실용적 격리가 완성된다.

Lock 기반 (Part 1)

• 호환성: S–S만 true, X는 모두 false.
• 2PL = Growing/Shrinking, lock point 순서 직렬화. Strict(X→commit), Rigorous(all→commit).
• upgrade=Growing, downgrade=Shrinking. 2PL은 deadlock-free 아님.
• Wait-Die(younger die, non-preemptive) / Wound-Wait(older wound, preemptive). wait-for graph cycle=deadlock.
• Intention 5×5, record X엔 IX 경로. Phantom→index/next-key locking.

Timestamp·검증·다중버전 (Part 2·3)

• TSO: READ TS<W-TS 거부 / WRITE TS<R-TS·TS<W-TS 거부. Thomas: obsolete write 무시.
• TSO는 serializable·deadlock-free, recoverable은 보장X.
• OCC: read→validation→write, TS=ValidationTS.
• MVCC 가시성: begin-TS ≤ TS(Ti) < end-TS, reader/writer 비차단.
• SI: first-committer-wins(같은 객체). 약점 ★Write Skew → A=10, B=1★.