Ch19_Recovery_System

Chapter 19. Recovery System

한 줄 핵심: 장애가 나도 원자성(atomicity)과 지속성(durability)을 지키는 핵심 도구는 로그(log)다. DB를 고치기 전에 old/new value를 stable storage에 먼저 적어두고, 장애 후 commit 안 된 트랜잭션은 undo, commit/abort된 트랜잭션은 redo한다. 실제 회복은 redo phase(순방향, repeating history) → undo phase(역방향) 2단계이며, 버퍼링 시엔 WAL(데이터보다 로그가 먼저 디스크로) 규칙을 지킨다.

이 챕터가 답하는 핵심 질문

• Q1. 장애에는 어떤 종류가 있고, 저장소는 어떻게 분류되는가?
• Q2. 왜 recovery 알고리즘이 필요하며, 데이터는 어떻게 이동하는가?
• Q3. 로그(log)란 무엇이고 로그 레코드에 무엇을 적는가?
• Q4. Immediate vs Deferred modification, 그리고 commit의 정의는?
• Q5. Undo와 Redo는 무엇이고, 장애 후 어떤 트랜잭션을 undo/redo하는가?
• Q6. Checkpoint는 왜 필요하고 회복을 어떻게 단순화하는가?
• Q7. 실제 recovery 알고리즘(redo phase → undo phase)은 어떻게 동작하는가?
• Q8. 로그 버퍼링·WAL·DB 버퍼링(no-force/steal)은 무엇인가?

---

Q1. 장애에는 어떤 종류가 있고, 저장소는 어떻게 분류되는가?

A. 장애는 Transaction failure / System crash / Disk failure 세 부류이고, 저장소는 생존성에 따라 Volatile / Nonvolatile / Stable 세 계층이다.

Failure Classification

유형	무엇이 잘못되나	예시
Transaction failure	트랜잭션 하나가 완료 못 함	Logical error(잘못된 입력, 데이터 없음, 자원 한도 초과) / System error(deadlock 등으로 시스템이 강제 종료)
System crash	전원·HW/SW 결함으로 시스템 전체 멈춤	정전, OS 크래시
Disk failure	디스크 자체 파손	head crash → 다른 디스크 복사본으로 회복

Fail-stop assumption

System crash 시 비휘발성 저장소(디스크) 내용은 손상되지 않는다고 가정. DB는 디스크 데이터 손상 방지용 무결성 검사를 다수 보유.

Storage Structure

저장소	생존성	예시
Volatile (휘발성)	crash에서 못 살아남음	main memory, cache
Nonvolatile (비휘발성)	crash에서 살아남음, 단 자체 고장으로 잃을 수 있음	disk, tape, flash, NV-RAM
Stable (안정 저장소)	모든 장애에서 살아남는 이상적(mythical) 저장소	서로 다른 비휘발성 매체에 여러 복사본으로 근사

로그는 stable storage에 둔다 — 로그가 날아가면 회복 자체가 불가능.

---

Q2. 왜 recovery 알고리즘이 필요하며, 데이터는 어떻게 이동하는가?

A. 두 갱신 중 하나만 디스크에 반영된 채 장애가 나면 **불일치(inconsistent) 또는 갱신 유실(lost update)**이 생기므로, 회복 알고리즘은 평상시 정보를 남기고(로그) + 장애 후 복구한다. 데이터는 디스크↔버퍼↔작업영역을 블록 단위로 오간다.

왜 필요한가 (계좌이체 예시)

$T_i$가 A→B로 $50 이체(두 갱신). 하나만 반영된 채 장애 → commit 보장 없이 DB를 먼저 고치면 불일치, 안 고치고 미루면 commit 직후 장애 시 lost update. 그래서 회복 알고리즘은 두 부분: ① 평상시 회복용 정보(로그) 남기기 ② 장애 후 atomicity·consistency·durability 복구.

Data Access

• Physical block(디스크) ↔ Buffer block(메모리). input(B)=디스크→메모리, output(B)=버퍼→디스크.
• 각 트랜잭션 $T_i$는 private work-area에 로컬 복사본 $x_i$ 보유.
  • read(X): X 값을 $x_i$로 복사 (최초 접근 전 필수, 이후 read는 로컬로).
  • write(X): $x_i$ 값을 버퍼 블록의 X로 복사 (commit 전 아무 때나 가능).

write ≠ output — 핵심 구분

write(X)는 버퍼까지만 반영. 버퍼가 디스크로 나가는 output($B_X$)은 write 직후일 필요 없고 시스템이 적절할 때 수행. 이 “버퍼-디스크 시차” 때문에 crash 시 무엇이 디스크에 있는지 알 수 없게 되고 — 그래서 로그가 필요하다.

---

Q3. 로그(log)란 무엇이고 로그 레코드에 무엇을 적는가?

A. 로그는 DB 갱신 활동을 시간순으로 기록한 로그 레코드 시퀀스(stable storage 보관)이며, update 레코드 $⟨T_i,X,V_1,V_2⟩$에 **old value $V_1$**과 **new value $V_2$**를 둘 다 적어 undo·redo를 모두 지원한다. 핵심 원칙: DB를 고치기 전에 변경 정보를 먼저 stable storage에 출력한다.

로그 레코드	언제	의미
$⟨T_i\text{start}⟩$	$T_i$ 시작 시	등록
$⟨T_i,X,V_1,V_2⟩$	$T_i$가 write(X) 실행 전에	$X$를 $V_1$(old)→$V_2$(new)로 바꿈
$⟨T_i\text{commit}⟩$	마지막 문장 끝낼 때	완료

old·new 둘 다 적는 이유

$V_1$(옛 값) → undo(되돌리기), $V_2$(새 값) → redo(다시 적용). 레코드 하나로 양방향 복구를 모두 지원.

---

Q4. Immediate vs Deferred modification, 그리고 commit의 정의는?

A. Immediate modification은 commit 전에도 uncommitted 갱신을 버퍼/디스크에 반영하고(이 장이 다루는 방식), Deferred는 commit 시점에만 반영한다. 트랜잭션은 commit 로그 레코드가 stable storage에 출력된 순간 committed다.

항목	Immediate	Deferred
갱신 시점	commit 전에도 반영 가능	commit 시점에만
전제 규칙	update 로그를 DB 쓰기 전에 먼저 기록(로그는 stable storage로 직접 출력 가정; 미루는 법은 Q8)	—
블록 output	commit 전/후 아무 때나, write 순서와 달라도 됨	commit 시
장단점	유연(이 장의 알고리즘)	회복 일부 단순, 단 로컬 복사 오버헤드

Transaction Commit: commit 로그 레코드가 stable storage에 출력된 순간 committed. 그 전 모든 로그가 이미 출력돼 있어야 함. 트랜잭션의 write는 commit 시점에 아직 버퍼에 남아 있어도 되고 나중에 output돼도 된다(로그가 있으니 redo로 재현 가능).

Immediate 동작 예 ($T_0$: A 1000→950, B 2000→2050 / $T_1$: C 700→600): $B_C$가 $T_1$ commit 전에 output될 수도, $B_A$가 $T_0$ commit 후에야 output될 수도 있다 — 로그가 모든 경우를 커버.

Concurrency Control과 Recovery

동시 실행 시 모든 트랜잭션이 하나의 버퍼·하나의 로그 공유 → 서로 다른 트랜잭션 로그가 뒤섞여(interspersed) 기록. 가정: $T_i$가 수정한 항목은 $T_i$가 commit/abort까지 다른 트랜잭션이 수정 불가(uncommitted 갱신은 안 보여야 함). 왜? $T_1$이 A 갱신 → $T_2$가 읽고 갱신 후 commit → $T_1$ abort 시 A를 undo 불가. 보장: 갱신 항목에 exclusive lock을 끝까지 유지 = strict 2PL.

---

Q5. Undo와 Redo는 무엇이고, 장애 후 어떤 트랜잭션을 undo/redo하는가?

A. undo는 역방향으로 old value 복원(로깅 함), redo는 순방향으로 new value 재적용(로깅 없음)이다. 장애 후 start만 있고 commit/abort 없는 트랜잭션은 undo, commit 또는 abort가 있는 트랜잭션은 redo한다.

연산	방향	동작	추가 로깅
undo($T_i$)	마지막 레코드부터 역방향	갱신 항목을 old value로 복원	항목 복원마다 $⟨T_i,X,V⟩$(compensation 레코드), 완료 시 $⟨T_i\text{abort}⟩$
redo($T_i$)	첫 레코드부터 순방향	갱신 항목을 new value로 재설정	없음

판정 조건

로그 상태	판정	직관
start 있고 commit·abort 둘 다 없음	undo	미완료 → 흔적 지워 atomicity
start 있고 commit 또는 abort 있음	redo	결말 확정 → 디스크 반영 불확실하니 재적용해 durability

abort된 트랜잭션도 redo? — Repeating History

$T_i$가 이전에 undo되어 $⟨T_i\text{abort}⟩$까지 적힌 뒤 장애가 나면, 회복 시 $T_i$를 redo한다 — 원래 동작뿐 아니라 옛 값을 복원했던 undo 단계까지 전부 재실행(= repeating history). 낭비처럼 보이지만 “로그에 적힌 역사를 무조건 재생”이라는 단일 원칙이 회복 로직을 크게 단순화한다.

Crash 시점별 예시

• (a) $T_0$ commit 전 crash: $T_0$ undo → B=2000, A=1000 복원, $⟨T_0,B,2000⟩$, $⟨T_0,A,1000⟩$, $⟨T_0\text{abort}⟩$ 기록.
• (b) $T_0$ commit 후, $T_1$ commit 전: redo($T_0$)[A=950,B=2050] + undo($T_1$)[C=700 복원, $⟨T_1,C,700⟩$, $⟨T_1\text{abort}⟩$].
• (c) 둘 다 commit 후: redo($T_0$), redo($T_1$) → A=950, B=2050, C=600.

로그를 보고 undo/redo를 판정하는 법 — 실제 로그 읽기

회복할 때 우리가 가진 건 stable storage의 로그뿐이다. 디스크에 실제로 무엇이 반영됐는지는 모른다(버퍼-디스크 시차 때문). 그래서 오직 로그에 commit/abort가 적혀 있느냐만 보고 각 트랜잭션을 redo할지 undo할지 결정한다.

위 세 경우의 로그를 나란히 놓고 같은 규칙을 적용해 보자. (각 트랜잭션: $T_0$ = A 1000→950, B 2000→2050 / $T_1$ = C 700→600)

경우 (a) — crash 시점의 로그:

<T0 start>
<T0, A, 1000, 950>
<T0, B, 2000, 2050>
         ← 여기서 crash. <T0 commit> 없음!

→ $T_0$은 start만 있고 commit/abort 둘 다 없음 → undo. 로그를 역방향으로 읽으며 B를 2000, A를 1000으로 복원하고 $⟨T_0\text{abort}⟩$ 기록.

경우 (b) — crash 시점의 로그:

<T0 start>
<T0, A, 1000, 950>
<T0, B, 2000, 2050>
<T0 commit>          ← T0은 결말 확정됨!
<T1 start>
<T1, C, 700, 600>
         ← 여기서 crash. <T1 commit> 없음!

→ $T_0$은 commit 있음 → redo (A=950, B=2050 재적용). $T_1$은 commit/abort 없음 → undo (C=700 복원, $⟨T_1\text{abort}⟩$ 기록).

경우 (c) — 로그에 <T0 commit>과 <T1 commit>이 둘 다 있음 → 둘 다 redo.

판정 한 줄 규칙 commit 또는 abort를 봤으면 redo, 못 봤으면(start만) undo. 디스크에 실제로 뭐가 반영됐는지는 신경 쓸 필요 없다 — redo는 어차피 같은 new value를 다시 덮어쓰고, undo는 old value를 다시 덮어쓰니 **이미 반영돼 있어도 멱등(idempotent)**해서 안전하다.

로그에서 그 트랜잭션의

---

Q6. Checkpoint는 왜 필요하고 회복을 어떻게 단순화하는가?

A. 로그 전체를 redo/undo하면 느리므로, 주기적 checkpoint로 “여기까지 디스크에 다 반영됨” 도장을 찍어 회복 범위를 줄인다.

왜 필요한가

오래 돌면 로그가 길어 전체 스캔이 오래 걸리고, 이미 디스크에 반영된 트랜잭션까지 불필요 redo.

수행 절차

1. 메모리의 모든 로그 레코드를 stable storage로 출력.
2. 수정된 모든 버퍼 블록을 디스크로 출력.
3. $⟨\text{checkpoint}L⟩$ 기록 ($L$ = 체크포인트 시점 active 트랜잭션 목록).
4. checkpoint 중엔 모든 갱신 정지.

회복 단순화

• 회복 대상 = $L$에 있는 것 + checkpoint 이후 시작한 것뿐. 로그 끝에서 역방향으로 최근 $⟨\text{checkpoint}L⟩$ 찾음.
• checkpoint 이전에 commit/abort한 트랜잭션은 갱신이 이미 모두 디스크에 출력됨 → redo/undo 불필요.
• 단 undo 위해 $L$의 모든 $T_i$에 대해 $⟨T_i\text{start}⟩$ 찾을 때까지 역방향 스캔. 가장 이른 start 이전 로그는 삭제(erase) 가능.

예시: $T_1$(checkpoint 이전 완료)=무시, $T_2,T_3$(checkpoint 후 commit)=redo, $T_4$(failure 시 미완료)=undo.

checkpoint가 회복 범위를 어떻게 줄이나 — 시각적 타임라인

네 트랜잭션이 시간축에 다음처럼 놓여 있고, 중간에 $⟨\text{checkpoint}⟩$를 한 번 찍은 뒤 마지막에 crash가 났다고 하자.

시간 ────────────────────────────────────────────────▶
 T1  ├──commit──┤
 T2        ├──────────commit──────┤
 T3                  ├─────────────────commit──┤
 T4                        ├──────────(미완료)──── ✗ crash
                 ▲checkpoint                     ▲crash

회복기가 하는 일:

1. 로그 끝에서 역방향으로 가장 가까운 $⟨\text{checkpoint}L⟩$을 찾는다.
2. checkpoint 이전에 이미 commit한 $T_1$ → 통째로 무시. 왜? checkpoint 절차가 수정 버퍼를 전부 디스크에 내보냈으므로 $T_1$의 변경은 이미 디스크에 안전히 있다. redo도 undo도 불필요 → 여기가 시간 절약의 핵심.
3. checkpoint를 걸친/이후 트랜잭션만 처리:
   • $T_2,T_3$: commit 있음 → redo (디스크 반영이 불확실하니 new value 재적용).
   • $T_4$: commit 없음 → undo (old value 복원).

checkpoint가 없었다면 로그 맨 처음부터 스캔하며 $T_1$까지 redo했어야 한다. checkpoint 도장이 “여기 이전은 다 디스크에 있으니 안 봐도 됨”을 보장해 주는 셈.

---

Q7. 실제 recovery 알고리즘은 어떻게 동작하는가?

A. 평상시 logging·rollback을 하고, 장애 후엔 Redo phase(checkpoint부터 순방향, 모든 갱신 재생 + undo-list 구성) → Undo phase(역방향, undo-list 트랜잭션 롤백) 2단계로 회복한다.

Logging (평상시)

$⟨T_i\text{start}⟩$ / 갱신마다 $⟨T_i,X_j,V_1,V_2⟩$ / $⟨T_i\text{commit}⟩$.

Transaction Rollback (평상시, 예: deadlock abort)

로그를 역방향 스캔, $T_i$의 $⟨T_i,X_j,V_1,V_2⟩$마다 → $X_j$에 $V_1$ 써서 undo + $⟨T_i,X_j,V_1⟩$(compensation log record) 기록. $⟨T_i\text{start}⟩$ 만나면 멈추고 $⟨T_i\text{abort}⟩$ 기록.

Redo Phase — repeating history (순방향)

commit·abort·미완료 가리지 않고 모든 갱신 재생.

1. 마지막 $⟨\text{checkpoint}L⟩$ 찾고 undo-list ← $L$.
2. 그 checkpoint부터 순방향:
   • $⟨T_i,X_j,V_1,V_2⟩$ 또는 $⟨T_i,X_j,V_2⟩$(compensation) → $X_j$에 $V_2$ 써서 redo.
   • $⟨T_i\text{start}⟩$ → undo-list에 추가.
   • $⟨T_i\text{commit/abort}⟩$ → undo-list에서 제거.

끝나면 undo-list에는 “start는 있고 commit·abort 없는” 미완료 트랜잭션만 남는다.

Undo Phase — 미완료 롤백 (역방향)

로그를 역방향 스캔:

• undo-list의 $T_i$의 $⟨T_i,X_j,V_1,V_2⟩$ → $X_j$에 $V_1$ 써서 undo + $⟨T_i,X_j,V_1⟩$ 기록.
• undo-list의 $T_i$의 $⟨T_i\text{start}⟩$ → $⟨T_i\text{abort}⟩$ 기록, undo-list에서 제거.
• undo-list 비면 종료. 이후 정상 처리 재개.

전체 예시

<T0 start>; <T0,B,2000,2050>; <T1 start>; <checkpoint {T0,T1}>;
<T1,C,700,600>; <T1 commit>; <T2 start>; <T2,A,500,400>;
<T0,B,2000>(T0 rollback compensation); <T0 abort>
───── crash ─────   →  회복 중 추가: <T2,A,500>; <T2 abort>

Redo pass (checkpoint $\{T_0,T_1\}$부터): $C$=600 redo → $T_1$ commit(제거)→$\{T_0\}$ → $T_2$ start(추가)→$\{T_0,T_2\}$ → $A$=400 redo → $⟨T_0,B,2000⟩$ redo(B=2000, repeating history) → $T_0$ abort(제거) → undo-list=$\{T_2\}$.
Undo pass (역방향): $⟨T_2,A,500,400⟩$ → A=500 복원, $⟨T_2,A,500⟩$ → $⟨T_2\text{start}⟩$ → $⟨T_2\text{abort}⟩$, 제거 → 빈 리스트 → 종료.

crash 시점이 더 빨랐다면?

$T_0$ rollback 끝나기 전($⟨T_0,B,2000⟩$ 직후, $⟨T_0\text{abort}⟩$ 전)에 crash 났다면 redo pass 끝에 undo-list=$\{T_2,T_0\}$(둘 다 미완료) → undo pass에서 둘 다 롤백. 즉 undo/redo 판정은 오직 crash 시점 로그에 commit/abort가 있느냐로 결정.

---

Q8. 로그 버퍼링·WAL·DB 버퍼링은 무엇인가?

A. 로그를 메모리에 모아 한 번에 내보내는 log record buffering으로 I/O를 줄이되, 데이터 블록이 디스크로 나가기 전에 관련 로그가 먼저 나가야 한다는 WAL(write-ahead logging)을 지킨다. 이 알고리즘은 no-force·steal 정책을 지원한다.

Log Record Buffering

로그를 메모리에 버퍼링했다가 버퍼 블록이 가득 차거나 log force 시 stable storage로 출력. log force = commit 시 그 트랜잭션의 모든 로그(commit 레코드 포함)를 강제 출력 → 여러 레코드를 한 번에 내보내 I/O 비용↓.

버퍼링 시 규칙 (WAL)

1. 로그 레코드는 생성 순서대로 출력.
2. $T_i$는 $⟨T_i\text{commit}⟩$이 stable storage에 출력된 후에만 commit.
3. 메모리 데이터 블록이 디스크로 출력되기 전, 그 블록 데이터에 관한 모든 로그가 먼저 stable storage에 출력 = WAL.

WAL 직관 — "장부 먼저, 거래는 나중에"

디스크 데이터가 바뀌었는데 로그가 없으면 crash 후 undo 불가. 로그만 있고 데이터 변경 전이면 redo로 재현하면 됨. 그래서 항상 로그가 데이터보다 먼저 디스크에 도달해야 한다.

Database Buffering — force/steal

정책	의미	이 장
force	commit 시 갱신 블록 반드시 디스크 기록(commit 비쌈)	—
no-force	commit 시 디스크 쓸 필요 없음	지원(commit 쌈, 미반영분은 redo)
steal	uncommitted 갱신 블록도 commit 전 디스크 기록 가능	지원(버퍼 자유, 잘못 나간 건 undo)

• steal로 uncommitted 블록 output 시 그 undo 정보 로그를 먼저 출력(WAL).
• output 중 그 블록에 갱신이 진행 중이면 안 됨 → 쓰기 전 블록에 exclusive lock(짧게 잡는 latch, write 끝나면 즉시 해제). latch는 동시성 제어 락과 무관 → non-two-phase로 풀어도 serializability에 영향 없음.
• 블록 output 절차: ① 블록 exclusive lock(latch) ② log flush(WAL) ③ 블록 디스크 output ④ latch 해제.

---

한눈에 정리

질문	답
로그에 왜 $V_1,V_2$ 둘 다?	$V_1$→undo용, $V_2$→redo용
어떤 트랜잭션 undo?	start 있고 commit/abort 둘 다 없음 (역방향, compensation + abort 기록)
어떤 트랜잭션 redo?	start 있고 commit 또는 abort 있음 (순방향, 로깅 없음)
commit 정의?	$⟨T_i\text{commit}⟩$이 stable storage에 출력된 순간
checkpoint 효과?	이전 완료분 제외, 스캔 범위 축소, 오래된 로그 삭제 가능
회복 구조?	redo phase(순방향, 재생+undo-list) → undo phase(역방향, 미완료 롤백)
WAL?	데이터 블록이 디스크로 나가기 전에 관련 로그가 먼저 출력
no-force/steal?	commit 때 디스크 쓰기 불필요 / commit 전 디스크 쓰기 허용 (둘 다 지원)