6. Recovery System

Failure Clssification

• Transaction failure
  • Logical errors: 내부 오류에 의해 트랜잭션이 끝나지 않음
  • System errors: deadlock 등에 의해 데이터베이스 시스탬이 트랜잭션을 종료시킴
• System crash: 정전이나 하드웨어 또는 소프트웨어 오류로 인한 시스템 오류
  • Fail-stop assumption: 비휘발성 저장 장치의 내용은 시스템 오류로 인해 망가지지 않는다고 가정
• Disk failure: 디스크 오류가 저장 장치를 파괴하는 상황 - 감지 가능하다고 가정

 

Storage Structure & Data Access

• Physical blocks: 디스크에 존재하는 블록
• Buffer blocks: 메인 메모리에 일시적으로 저장되는 블록
• 디스크와 메인 메모리 간의 블록 이동은 다음의 two operations에 의해 시작된다.
  • input(B): physical block B를 메인 메모리로 이동
  • output(B): buffer block B를 디스크로 이동한 후 적절한 physical block과 교체

• 각 트랜잭션 T는 접근하는 data item의 로컬 복사본이 있는 private work-area를 가진다.
  • T_i's local copy of a data item X is called x_i
• buffer blocks과 private work-area 간의 data item 이동은 다음에 의해 일어난다.
  • read(X): data item X를 local variable x_i에 할당
  • write(X): local variable x_i의 값을 buffer block의 data item X에 할당
  • output(B_x)가 write(X) 이후 즉시 이루어지는 것은 아님
• 트랜잭션은 처음으로 X에 접근하기 전에 반드시 read(X)를 수행
• write(X)는 트랜잭션이 커밋되기 전에 수행되면 됨

---

Recovery Algorithms - key concepts

• Recovery algorithms
  1. 정상적인 트랜잭션 과정 동안의 작업 - failures로부터 회복하기 위한 충분한 정보를 보장
  2. failure 발생 후의 작업 - ACD를 보장하기 위해 데이터베이스 내용을 복구

• atomicity 보장
  • 먼저 DB 수정 사항을 DB에 바로 수정하는 것이 아니라 stable storage에 output한다.

 

Log-Based Recovery

• log-based recovery
  • 아래와 같이 log record를 작성
  • 트랜잭션 T_i 시작 : <T_i start>
  • T_i가 write(X)를 실행하기 전: <T_i, X, V1, V2>
  • T_i 종료 후: <T_i commit>

• 로그는 안정적인 저장소에 보관
• 로그는 a sequence of log records, 데이터베이스 업데이트 활동에 대한 기록을 유지
• 두 가지의 로그 사용 접근이 존재
  • Deferred database modification
  • Immediate database modification

 

Database Modification

• immediate-modification: 커밋되지 않은 트랜잭션의 업데이트를 버퍼나 디스크에 반영하는 것을 허용
  • 데이터베이스에 아이템이 쓰여지기 전에 업데이트 로그 레코드를 작성해야 함
  • stable storage에 업데이트 된 데이터 블록을 output하는 것은 트랜잭션 커밋 전이나 후 상관없음
  • 블록이 output되는 순서와 write되는 순서는 다를 수 있음
• deferred-modification: 트랜잭션이 커밋된 후에 업데이트를 버퍼나 디스크에 반영
  • recovery를 단순화
  • local copy를 저장하는 것에 오버헤드를 가짐

 

Transaction Commit

• 트랜잭션이 커밋되었다. = 커밋 로그가 안정된 저장소에 output되었다.
  • 이전의 모든 로그 레코드는 이미 output 되어야 함
• 트랜잭션이 write한 것은 커밋될 때도 버퍼에 남아있다가 이후에 output될 수 있음

 

 

Log Record Buffering

• Log record buffering: 로그 레코드는 바로 안정된 저장소에 output되지 않고 메인 메모리에 버퍼됨
• Log records are output to stable storage
  1. log buffer의 block of log records가 다 찼을 때
  2. log force operation이 실행됐을 때
     • Log force: 트랜잭션을 커밋하기 위해 모든 로그 레코드를 output
     • checkpoint manager 또는 DB buffer manager로부터 요청받았을 때 실행됨
• write-ahead logging or WAL rule: 로그 레코드가 버퍼될 때 따라야 하는 규칙
  1. 로그 레코드는 만들어진 순서대로 output된다.
  2. 트랜잭션 T_is는 로그 레코드 <T_i commit>이 output됐을 때만 커밋 상태가 된다.
  3. 메인 메모리의 데이터 블록이 데이터베이스로 output되기 전에 모든 로그 레코드가 output된다.

 

Database Buffering

• 데이터베이스는 in-memory buffer를 유지한다.
  • 새로운 블록이 필요한데 버퍼가 가득찬 경우 기존의 블록을 버퍼에서 제거해야 한다.
  • 제거될 블록이 업데이트된 경우 디스크에 output되어야 한다.
• recovery algorithm은 no-force policy를 지지: 업데이트된 블록은 트랜잭션이 커밋되 때 디스크에 쓰여질 필요가 없다.
  • force policy: 업데이트된 블록은 트랜잭션이 커밋될 때 디스크에 쓰여져야 한다.
• recovery algorithm은 steal policy를 지지: 커밋되지 않은 트랜잭션의 업데이트를 가진 블록은 커밋되기 전에 디스크에 쓰여질 수 있다.
  • 커밋되지 않은 업데이트가 output될 때 undo information에 대한 로그 레코드가 먼저 stable storage로 output된다.
• block이 디스크로 output될 때 해당 block에 대한 업데이트는 진행되지 않아야 한다.
  • 데이터 아이템을 쓰기 전에 트랜잭션은 해당 데이터 아이템을 포함하는 블록에 대해 배타적 락을 획득한다.
  • 쓰기가 완료된 후 락을 해제한다.
  • latch: 이렇게 짧은 기간 동안 유지되는 락
• To output a block to disk
  1. 해당 블록에 대한 exclusive latch 획득 -> 해당 블록에 대한 업데이트가 없음을 보장
  2. log flush 수행
  3. disk로 블록 output
  4. 블록에 대한 latch를 해제

 

 

Concurrency Control and Recovery

• 트랜잭션이 동시에 실행될 때, 모든 트랜잭션은 하나의 디스크 버퍼와 로그를 공유
  • buffer block은 여러 트랜잭션에 의해 수정된 데이터 아이템을 가질 수 있음
• T_i 가 아이템을 수정했다면 해당 아이템에 대해 T_i가 커밋되거나 실패할 때까지 수정 불가능
  • 커밋되지 않은 트랜잭션의 수정은 다른 트랜잭션에 보이지 않음 -> 보인다면 undo를 수행하기 복잡해짐
  • strict two-phase locking: 트랜잭션이 끝날 때까지 수정한 아이템에 대한 exclusive locks를 가지고 있음으로써 보장 가능

 

Undo and Redo Operations

• Undo of a log record <Ti, X, V1, V2>: X에 old value V1을 쓴다.
• Redo of a log record <Ti, X, V1, V2>: X에 new value V2를 쓴다.
• Undo and Redo of Transactions
  • undo(Ti): Ti의 log record를 역순으로 처리하여 Ti에 의해 수정된 모든 데이터 아이템을 복구
    • old value V로 복구하면 log record <Ti, X, V> 작성
    • undo가 끝나면 log record <Ti abort> 작성
  • redo(Ti): Ti의 첫 log record부터 처리하여 Ti에 의해 수정된 모든 데이터 아이템을 설정
    • 이 경우 logging이 없음
• 실패 후 복구할 때
  • undo 필요: 트랜잭션 Ti가 <Ti start>는 있는데 <Ti commit> or <Ti abort>가 없는 경우
  • redo 필요: 트랜잭션 Ti가 <Ti start>가 있고 <Ti commit> or <Ti abort>가 있는 경우
  • 트랜잭션 Ti가 undo 되어 <Ti abort>된 경우에도 redo를 수행
    • repeating history: old values를 복구하는 all the original actions까지 수행
    • 낭비처럼 보이지만 recovery를 단순화해줌

 

 

Checkpoints

• 모든 트랜잭션의 로그에 대해 Redoing/undoing하는 것은 매우 느릴 수 있음
  1. 시스템이 매우 오랜 시간 동안 동작했다면 전체 로그 과정은 time-consuming
  2. 이미 데이터베이스에 output된 수정까지 redo하는 것은 불필요
• Checkpointing Mechanism
  1. 메인 메모리에 있는 현재의 모든 로그 레코드을 stable storage로 output
  2. 디스크로 모든 수정된 buffer blocks를 output
  3. 로그 레코드 <checkpoint L>를 stable storage에 작성
     • L:  해당 시점에 활동하는 모든 트랜잭션의 목록
• checkpointing 하는 동안에 모든 수정은 멈춤

 

 

• 그렇게 되면 recovery 동안 checkpoint 이전과 그 후에 시작된 트랜잭션만 고려하면 됨
  1. 가장 최근의 <checkpoint L> 레코드를 거꾸로 스캔
  2. L에 있거나 이후 시작된 트랜잭션을 redo or undo
  3. L에 있는 트랜잭션의 <Ti start> 레코드를 찾을 때까지 거꾸로 스캔

 

Example of Checkpoints

---

Recovery Algorithm - components

1. Logging

• <Ti start> : 트랜잭션 시작
• <Ti, Xj, V1, V2> : 업데이트
• <Ti commit> : 트랜잭션 종료

2. Transaction rollback

• 트랜잭션 Ti가 롤백된 상황
• 로그를 마지막 부터 거꾸로 스캔하여 <Ti, Xj, V1, V2>를 기존 값으로 undo
  • compensation log records: <Ti, Xj, V1> 작성
  • Xj에 V1 작성
• <Ti start>를 발견하면 스캔을 멈추고 <Ti abort> 작성

 

3. Recovery from system failure

• Two phases
  • Redo phase: 트랜잭션이 커밋되든, 실패하든, 불완전하든 상관없이 모든 트랜잭션의 업데이트를 replay
  • Undo phase: 불완전한 트랜잭션을 undo

• Redo phase
  1. 최근의 <checkpoint L>을 찾고 undo-list를 L로 설정
  2. 이후 레코드를 스캔
     • <Ti, Xj, V1, V2> : redo하여 Xj에 V2 작성
     • <Ti start> : undo-list에 Ti 추가
     • <Ti commit> or <Ti abort> : Ti를 undo-list에서 제거

• Undo phase: 끝에서부터 거꾸로 로그를 스캔
  1. <Ti, Xj, V1, V2> (Ti is in undo-list): 트랜잭션 롤백 시와 동일
     • Xj에 V1을 작성해 undo
     • <Ti, Xj, V1> 로그 작성
  2. <Ti start> (Ti is in undo-list)
     • <Ti abort> 로그 작성
     • Ti를 uno-list에서 제거
  3. undo-list가 비면 종료

 

Failure with Loss of Nonvolatile Storage

• 지금까지 비휘발성 저장소의 손실이 없다고 가정
• 비휘발성 저장소의 손실을 해결하기 위해 checkpointing과 비슷한 기술을 사용
  • 주기적으로 안정적인 저장소로 모든 내용을 dump
  • 해당 과정 동안 트랜잭션이 실행 중이면 안됨
• 과정
  1. 메인 메모리의 모든 로그 레코드를 안정적인 저장소로 출력
  2. 모든 버퍼 블록을 디스크로 출력
  3. 데이터베이스의 내용을 안정적인 저장소에 복사
  4. 안정적인 저장소 로그에 <dump> 출력
• 디스크 오류 회복
  1. 최근 dump로부터 데이터베이스 복구
  2. 로그를 확인하여 dump 이후 커밋된 모든 트랜잭션을 redo