회복

Failure and Recovery

Failure Classification

• 트랜잭션 장애
  • 트랜잭션의 내부 논리 오류, 사용자의 명시적인 요구, 또는 시스템 내부 결정에 의해 발생
  • 교착 상태에 있는 트랜잭션중 하나의 트랜잭션은 철회되어야 하며, 철회되는 트랜잭션에게 장애가 발생
• 시스템 장애
  • 주기억 장치 메모리에 문제가 발생하여 메모리 내용이 사라지는 경우.
  • 정전, OS 오류, 하드웨어 결함이 원인이 될 수 있다.
• 디스크장애
  • 하드웨어, 소프트웨어 결함으로 인해 디스크내용이 사라지는 현상
• 시스템이 트랜잭션의 원자성, 일치성, 지속성 (Atomicity, Consistency, Durability)를 지원하기 위하여 회복 기법이 필요하다.

Recovery Algorithm

• 회복기법은 시스템이 오류에 대응하여 원자성, 일치성, 지속성 (Atomicity, Consistency, Durability)를 보장하기 위해 필요하다.
• 회복 알고리즘은 두 파트로 구성된다.
  • 정상상태에서 시스템 회복을 대비하기 위해 수행하는 연산
  • 장애가 발생하였을 때 회복하기 위해 수행하는 연산

Stable Storage

• 어떠한 장애가 발생해도 저장내용이 상실되지 않는 가상의 저장매체이다.
• 여러 개의 비휘발성 메모리를 이용하여 구현한다.
• RAID를 사용한다.

Disk I/O should be atomic

• 회복관점에서 모든 Disk I/O는 원자성을 가져야 한다.
• 데이터 쓰기가 일부만 실행되면 많은 문제점이 발생하고, 이를 발견하기도 쉽지 않다
• RAID하드웨어에서 하드웨어 지원으로 원자성 I/O을 지원한다.

Data Location

(Data Location Example)

• Physical block은 디스크에 있는 블록들이다.
• Buffer block은 메인 메모리에 일시적으로 있는 블록이다.
• 디스크와 메인 메모리 간의 블록 이동은 다음에 의해 이루어 진다.
  • input(B) 은 physical block B를 메인 메모리로 옮긴다.
  • output(B)는 buffer block B를 디스크로 옮기고, 적절한 physical block을 교체한다.
• 각 트랜잭션 Tj는 모든 데이터들의 복사본이 조작되는 private work area가 있다.
  • read(X)는 데이터 아이템 X의 값을 지역 변수에 할당한다.
  • write(X) 지역변수의 값을 데이터 아이템 X에 할당한다.
  • 이 명령어들은 X가 메모리에 없다면 input(X) 명령을 실행할 수 도 있다.
• output(B)는 즉시 write(X) 다음으로 수행될 필요는 없다.
  • 메모리 연산을 바로 디스크에 반영시킬 필요가 없다.

Logs

Recovery Approach

• Log-based recovery
• shadow-paging
  • 현재 데이터를 그대로 복사
  • 더이상 사용되지 않는 방식
• atomicity를 보장하기 위해, 우리는 데이터베이스의 변화를 의미하는 정보를 stable storage에 기록해야한다.

Simple Logging : Normal Processing

• Log는 stable storage에 유지되어야 한다.
  • log는 log기록의 순차이고, 데이터베이스에 대한 갱신의 기록을 유지한다.
• < Ti start > : Ti가 시작되면 기록되는 log
• < Ti, X, V1, V2> : Ti가 V1값을 가지던 X를 V2값으로 갱신
• < Ti commit > : Ti가 끝남
• 여러개의 트랜잭션이 동시에 수행된다.
• 모든 트랜잭션은 하나의 disk buffer와 하나의 log를 공유한다.
  • buffer block은 하나 또는 여러개의 트랜잭션에 의해 갱신된 데이터 아이템을 가지고 있을 수 있다.
• 우리는 엄격한 2PL Lockingㅇ르 사용하여 동시성을 제어한다.
  • uncommitted한 트랜잭션의 갱신은 다른 트랜젝션에게 보여져선 안된다.
• 서로 다른 트랜잭션의 log 기록은 log에 무작위로 번갈아가며 나타난다.Simple Logging : Checkpoint
• 회복 절차의 문제
  • 전체 로그를 검색하는 것은 시간이 많이 걸린다.
  • 데이터베이스에 이미 갱신을 수행한 트랜잭션의 불필요한 재수행을 하게 될 수 있다.
• 주기적으로 checkpointing 함으로써 회복 절차를 최적화한다.
  • 현재 메인 메모리에 있는 모든 로그 기록을 안정적인 저장소에 기록한다.
  • 안정적인 저장소에 < checkpoint L >을 기록한다. L은 체크포인트의 시기에 수행중인 트랜젝션들의 리스트이다.

• T1은 이미 디스크에 update 되었으니 무시한다.
• T2와 T3는 재수행된다.
• T4는 중간에 시스템 장애가 발생하여 완료되지 못하였기에 UNDO해야한다.

Simple Logging : Recovery

• 시스템이 crash로 부터 회복하기 위해 다음과 같은 절차가 진행된다.
  1. "undo-list"와 "redo_list"를 빈 상태로 초기화한다.
  2. Log를 끝에서부터 탐색하고, 첫 번째 < checkpoint L > 레코드가 나오면 멈춘다. 끝에서부터 탐색하면서 각 레코드가 나오면 :
     1. 레코드가 < Ti commit > 이면, Ti를 "redo-list"에 넣는다.
     2. 레코드가 < Ti start > 이고, Ti가 "redo-list"에 없다면, Ti를 "undo-list"에 넣는다.
  3. L에 있는 모든 Ti에 대해서, Ti가 redo-list에 없으면, Ti를 "undo-list"에 넣는다.
• undo-list는 undo 되어야하는 완료되지 못한 트랜잭션을 담고 있으며, redo-list는 redo되어야하는 트랜잭션을 담고 있다.
• 회복은 다음과 같이 진행된다.
  1. Log에서 뒤에서 부터 가장 최근의 기록을 찾고, undo-list 안의 모든 Ti의 < Ti start > 레코드를 찾으면 멈춘다.
  2. 스캔하는 동안, undo-list의 트랜젝션에 해당하는 각 log 레코드에 대해 undo를 수행한다.
• 가장 최근의 < checkpoint > 기록으로 위치한다.
• 로그의 끝까지 앞으로 진행한다.
  1. 스캔하면서, redo-list에 있는 트랜잭션에 대한 레코드를 redo한다.

Buffer Management

• 먼저 buffering은 디스크에 있는 블록의 복사본은 메인메모리에 저장하는 것을 말한다.
• 메인 메모리의 블록이 변경되면, 대응되는 디스크의 블록에 변경의 반영해야 한다. (디스크의 블럭을 메인메모리의 블록으로 변경한다)

Data Page Buffering

• 데이터베이스는 데이터 블록들의 in-memory buffer를 유지한다.
  • 새로운 블록이 필요할 때, 버퍼가 꽉 차있으면, 블록은 버퍼로부터 제거되어야 한다.
  • 제거되야할 블록이 갱신되면, 그것은 디스크로 출력되어야만 한다.
• 만약 uncomitted된 갱신이 이루어진 블록이 블록으로 출력되면, 그 갱신에 대한 undo 정보를 가진 로그 레코드가 안전 저장장치에 있는 로그에 먼저 출력된다. (WAL)
• 한 블록이 디스크로 출력되면 어떠한 갱신도 이루어져서는 안된다 (block should be pinned). 다음에 의해 보장될 수 있다.
  • 데이터 아이템을 쓰기 전에, 트랜잭션이 그 데이터 아이템을 가지는 블록에 X-Lock을 건다.
  • Lock은 Write가 끝나면 해제될 수 있따.
    • 짧은 시간동안 걸리는 이러한 Lock들을 latches 라고 부른다.
  • 그 블럭에 어떠한 갱신도 이루어지지 않는 것을 보장한다.
• Database Buffer는 2가지 방법으로 구현된다.
  • 데이터베이스를 위해 실제 메모리에 공간이 할당됨
  • 가상 메모리를 사용
• 버퍼를 주 메모리에 구현하는 것은 문제가 있다.
  • 메모리는 데이터베이스 버퍼와 어플리케이션을 위해 나누어지고 이는 유연성을 제한한다.
  • 주 메모리에 대한 요구는 동적으로 바뀌지만 메모리를 나누면 이에 적극적으로 대응하지 못한다.
• 데이터베이스 버퍼는 여러가지 단점에 불구하고 가상 메모리로 구현된다.
  • OS는 필요에 의해 변경된 페이지를 디스크의 swap area로 보낸다.
  • DB가 buffer page를 디스크에 쓰기로 결정했을때, buffer page는 swap area에 있을 수 있고, swap area에서 읽고 disk에 출력할 수 있는데, 이는 추가적인 I/O를 초래한다. (daul paging problem)
    • dual paging은 방지되어야 하나, OS는 그러한 기능을 제공하지 않는다.
• OS가 버퍼로부터 page를 옮기려면, 제어를 데이터베이스로 보내야 한다.
  • 페이지가 변경되었다면 데이터베이스 영역으로 출력한다.
  • OS가 사용할 수 있도록 페이지를 버퍼에서 제거한다.Steal vs Force Policy
• 데이터 페이지 버퍼링 방식은 회복 알고리즘과 매우 관련이 있다.
• The Force policy
  • 갱신된 블록이 commit될 때 디스크에 쓰이는 것을 요구함
  • commit 비용이 커진다.
• The no-force policy
  • 갱신된 블록들이 트랜잭션이 commit될 때 디스크에 쓰일 필요가 없다.
• The Steal Policy
  • 트랜잭션이 커밋되기 이전에, 커밋되지 않은 트랜잭션의 갱신을 담은 블록들을 디스크에 쓸 수 있다.
• 좋은 회복 알고리즘은 "steal"과 "not force" 정책을 지원해야한다.
  • not steal방식은 데이터 페이지 버퍼 용량이 초과하는 많은 수의 데이터 페이지를 변경하는 트랜잭션이 수행되면 기능상의 문제가 발생할 수 있다.
  • Force 방식은 트랜잭션이 완수될 때마다 모든 로그가 안전 저장장치에 저장되야하는데, 시스템의 성능 문제를 야기할 수 있다.

    	Steal	Not Steal
    Force	Undo, no redo	No redo, No undo
    Not Force	redo & undo	redo, no undo
    # Log-based Recovery

Log Block Buffering

• 로그 레코드들은 안전 저장장치에 바로 출력되지 않고 메인메모리에 버퍼된다.
  • 로그 레코드들은 버퍼에 있는 로그레코드 블록이 차거나, log force op이 수행되면 안전 저장장치로 출력된다.
• Log force는 모든 로그 레코드를 안전저장장치에 쓰기 연산 함으로써 트랜잭션을 commit하기 위해 수행된다.
• 여러개의 로그 레코드는 하나의 output op들 통해 출력될 수 있으며 이는 I/O 비용을 절감시킨다. (Group Commit)
• 로그 레코드가 버퍼되면 다음과 같은 규칙을 따라야 한다.
  • 로그 레코드들은 그들이 생성된 순서대로 안전 저장장치에 출력되어야 한다.
  • 트랜잭션 Ti는 로그 레코드 < Ti commit>이 안전 저장장치에 출력된 이후에만 커밋상태로 전이할 수 있다.
  • 버퍼의 데이터 블럭이 디스크로 출력되기 이전에, 그 블록에 대한 모든 데이터 레코드는 안전 저장장치로 출력되어있어야 한다.
    • 이 규칙은 write-ahead-loggin (WAL)이라고 불린다.
    • WAL은 undo 정보를 output으로 필요로 한다.

A Recovery Algorithm

• 정상적으로 동작하는 동안 Logging을 한다.
  • start : < Ti start >
  • update : < Ti, Xi, V1, V2 >
  • end : < Ti commit >, < Ti abort >
• 정상적으로 동작하는 동안 Transaction rollback을 한다.
  • Ti가 rollback한다고 하자
  • 뒤에서 부터 스캔하여 Ti의 update form log에 대하여
    • V1을 Xi에 Write하여 undo 한다
    • 로그 레코드 <Ti, Xi, V1>을 Write한다.
      • 이러한 undo 작업 로그를 Compensation Log Record라고 한다.
• < Ti start > 가 발견되면 스캔을 멈추고 로그 레코드 < Ti abort>를 기록한다.
• 오류로 부터의 회복은 2 단계로 나뉜다
  • Redo phase : 모든 트랜잭션의 갱신을 다시 수행한다.
  • Undo phase : 모든 불완전한 트랜잭션을 undo한다.
• Redo phase
  • 가장 최근의 < checkpoint L > 레코드를 찾아, undo-list를 L로 초기화한다.
  • < checkpoint L > 레코드로부터 앞으로 스캔한다.
    • update (< Ti, Xi, V1, V2 >) 기록을 찾으면, Xi를 V2로 Write하여 redo한다.
    • start (< start Ti >) 기록을 찾으면, Ti를 undo-list에 넣는다.
    • end ( < commit Ti >, < abort Ti > )기록을 찾으면, Ti를 undo-list에서 제거한다.
• Undo phase
  • 로그를 뒤에서 부터 앞으로 스캔한다.
    • Ti가 undo-list에 있는 update 로그를 발견하면 undo한다.
      • < Ti, Xi V1>을 로그 레코드에 Write하여 undo.
    • undo-list에 있는 < Ti start > 를 찾으면...
      • < Ti abort > 레코드를 Write한다.
      • Ti를 undo-list에서 제거한다.
  • undo-list가 비면 멈춘다.
  • Undo phase가 끝나면 정상 트랜잭션 처리가 가능하다.
    위와 같은 기법을 Repeating History라고 하며 이는 회복 알고리즘을 간단히 하는 기법이고, 널리 사용되는 기법이다.

• Redo phase
  • T0은 commit하여 undo-list에서 제거
  • T1는 commit하여 undo-list에서 제거
• Undo phase
  • T2가 undo-list에 존재
  • T2의 11번 연산이 undo됨
  • T2의 8번 연산이 undo됨
  • T2의 7번 연산이 undo 됨 (abort)Fuzzy Checkpointing
• 검사점이 진행되는 동안 모든 데이터베이스 연산을 정지시키지 않고 일반 데이터베이스 연산을 수행하도록 허용하는 검사점을 퍼지 검사점 (fuzzy checkpointing)이라고 한다.
• 검사점 시작을 표시하는 검사점 로그 레코드를 안정저장장치에 기록하고, 변경된 버퍼 리스트 ( 디스크에 write하여야 하는 블록리스트)를 만든 후에는 일반 데이터베이스 연산을 허용한다.
• 블록을 디스크에 Write할 때는 WAL원칙을 준수한다.
• 검사점 레코드 로그 위치를 안정저장매체의 정해진 위치에 저장한다.
  • 이는 검사점 중간에 시스템 장애가 발생하는 경우를 대비하는 것이다.Non-Volatile Storage
• 비활성 저장장치 장애 처리방법
• normal 할 때 주기적으로 디스크 덤프를 한다.
• 회복해야할 때 가장 최근의 dump된 DB 상태 이후로 commit된 모든 트랜잭션을 redo