슬라이드 정리 자료

Outline

  • Failure Classification
  • Recovery and Atomicity
  • Log-Based Recovery
  • Shadow Paging
  • Recovery with Concurrent Transactions
  • Buffer Management

Failure Classification

  • 트랜젝션 실패

    • 논리적 오류
    • 시스템 오류(데드락 등)

  • 시스템 장애

  • 디스크 실패

  • Transaction이 실행되다가 failure 발생 undo (취소)

  • 데이터베이스 변경이 memory에서만 반영되고, DB에는 반영되지 않음. -> failure 발생 시 output이 없다. 다시 실행해야함. Redo

Recovery Algorithms

  • Recovery 알고리즘은 DB Consistency, transaction, atomicity, durability를 보장함
  • Failure 발생 –> log-record를 이용해서 DB를 이전상태로 복구하는 작업이 필요

Data Access (1/2)

  • 물리적 블럭은 디스크에 존재
  • 버퍼는 메모리에 존재
  • 디스크와 메모리 사이의 블럭 이동은 input(B)나 output(B)에 의해 발생
  • 각 트랜젝션 Ti는 work-area가 존재 (단순화 하기 위해 모든 데이터가 같은 블럭에 있다고 가정)

Data Access (2/2)

  • read(X)와 write(X) 사이에 블럭을 버퍼로 옮김
  • 트랜젝션
    • 최초로 X에 접근할 때 read(X) 수행
    • 추가적인 엑세스는 로컬 카피를 사용
    • 마지막 엑세스 이후 write(X)
  • output(Bx)는 write(X)를 즉시 수행할 필요가 없음

Example of Data Access

Recovery and Atomicity (1/2)

  • 트랜젝션이 커밋되는것을 확정지지 않은 상태에서 다른 수정을 하는것은 DB의 inconsitent 상태를 초래함
  • 트랜젝션 Ti가 A로부터 B에게 50$를 송금하는 것이라면 DB의 목표는 All or Nothing을 만드는 것
  • operation 수행 실패가 A에서 돈을 빼고 B에 돈을 넣는것을 완료하게 전에 일어날 수 있음

Recovery and Atomicity (2/2)

  • atomic 실패를 보장하기 위해 db에 수정을 가하기 전에 안전한 스토리지에 정보를 기술해두어야함
  • 2가지 접근방법
    • Log-based Recovery
    • Shadow-paging
  • 트랜젝션은 직렬로 실행되는 것을 가정함

Log-Based Recovery (1/2)

  • 모든 수정이력을 로깅함

  • 트랜젝션 Ti가 시작될 때 아래와 같이 기록

  • Ti가 write(X)를 실행하기 전에 아래 로그를 기록 > <Ti, X, V1, V2>

Log-Based Recovery (2/2)

  • Ti가 마지막 statement를 끝냈을때 아래를 기록

  • 로그기록은 direct로 안정된 스토리지에 기록됨을 가정

  • 2가지 로그 기록법(기록시점에 따라)

    • deferred
    • immediate

Deferred Database Modification (1/4)

  • Deferred Modification은 아래와 같은 전략을 취함
    • 모든 DB 수정은 스토리지에 로그로 기록
    • 실제 DB에는 부분적으로 커밋될때에 기록
  • 트랜젝션 시작은 아래를 기록 >

Deferred Database Modification (2/4)

  • Ti가 부분적으로 커밋될때 은 로그에 기록됨

  • 마지막으로 로그 레코드는 이전의 deferred를 기록하기 위해 쓰여짐

  • 장애로부터 복구 시 트랜젝션은 부터 까지 로그를 redo

  • redo Ti 모든 이전값을 새로운 값으로 옮기는 작업을 포함함

Deferred Database Modification (3/4)

  • 장애는 아래 상황이 일어날 수도 있음
    • 트랜젝션이 original 업데이트 되는 동안
    • recovery 액션이 수행되는 동안

Deferred Database Modification (4/4)



  • 안전한 스토리지에 있는 로그는 장애시 아래의 케이스로 쓰여짐 a. redo 액션이 필요없음 b. Redo(T0) 는 이 존재하므로 필요함 c. Redo(T0), Redo(T1) 필요

Immediate Database Modification (1/4)

  • immediate Modification은 모든 DB의 수정을 트랜젝션이 수행된는 동안에도 반영함

  • DB 기록 전에 업데이트 로그가 기록되어야 함

  • 업데이트된 버퍼 블록의 출력이 트랜젝션 커밋 이전이나 이후에 일어날 수 있음

  • 쓰여진 블록의 순서가 기록된 순서와 다를 수 있음

Immediate Database Modification (2/4)

Immediate Database Modification (3/4)

  • 복구 프로세스는 2가지 연산이 있음
    • Undo : Ti의 old값으로 backward로 업데이트
    • Redo : Ti의 new값으로 forward로 업데이트
  • 두 연산 모두 idempotent함
    • 즉, 만약 연산이 여러번 실행되더라도 결과가 같음

Immediate Database Modification (4/4)

  • 실패이후 복구시
    • 이후 이 없으면 undo
    • 이후 이 있으면 redo
  • undo 연산이 먼저 실행되고 redo가 실행됨

Immediate Database Modification Recovery Example



  • recovery를 아래 3가지 케이스로 진행 a. Undo(T0) : A가 1000, B가 2000으로 restore b. Undo(T1) : C가 700으로 restore Redo(T0) : A 950, B 2050으로 변경 c. Redo(T0) : A 950, b 2050, C 600으로 변경

Checkpoints (1/2)

  • 기존 복구 프로세스의 문제점
    • 모든 전체 로그를 검색하는것은 시간이 많이 걸림
    • 대부분의 redo해야 하는 트랜젝션은 이미 DB에 기록되어 있음
  • 오버헤드를 줄이기 위해 시스템은 주기적으로 checkpoint를 수행함
    • 모든 로그를 안전한 스토리지로 기록
    • 모든 수정된 버퍼 블록을 디스크에 기록
    • 안전한 스토리지로 를 기록

Checkpoints (2/2)

  • 복구 프로세스 때 최근 체크포인트 전후의 트랜젝션만 고려함
    • 제일 마지막 로그에서 위로 checkpoint 레코드를 찾음
    • 이 부분에서 조금 더 위로 를 찾음
    • 보다 위 로그는 고려할 필요 없음
    • 시점 이후로 이 되지 않은 로그는 undo(Ti)
    • 로그를 앞으로 forward하면서 된 로그를 redo(Ti)

Example of Checkpoints

  • T1은 무시
  • T2와 T3는 redone
  • T4는 undo

Page And Page Table

  • 데이터 베이스는 고정된 길이의 블럭으로 나뉘어 지는데 이를 페이지라고 부름

  • 페이지는 디스크에 순서없이 저장됨

  • 페이지 테이블은 주어진 i에 따라 i번째 페이지로 찾아짐

Sample Page Table

Shadow Paging (1/6)

  • shadow paging은 log 기반 복구의 대안으로 트랜젝션이 직렬로 실행만 된다면 유용함

  • 페이지 테이블을 현재와 shadow테이블로 관리하는 기법

  • 트렌젝션이 시작할 때 두 페이지는 똑같음

  • shadow table은 트랙젝션이 수행되는 동안 shadow를 변하지 않음 반면에 현재 페이지는 변경 가능

  • 모든 입력과 출력 연산은 현재의 페이지 테이블을 사용함

  • 트랜젝션 커밋이 완료되면 shadow 페이지를 다시 현재 페이지와 같게 만듬

Shadow Paging (2/6)

  • Tj가 wirte(X)를 수행하고 X가 i번째 페이지라고 가정해보자.

  • 시스템은 아래와 같이 쓰기 연산을 수행

    • i번째 페이지가 아직 메모리에 없으면 input(X)를 수행

Shadow Paging (3/6)

  • 트랜젝션이 시작되면서 현재 페이지에 수정이 필요하면 아래의 작업 수행

    • 안쓰는 페이지를 디스크에서 찾음

    • i번째 페이지의 내용을 복사하여 위의 페이지로 복사

    • 현재의 페이지 테이블의 포인터를 위의 안쓰는 페이지로 이동

Shadow Paging (4/6)

Shadow Paging (5/6)

  • 트랜젝션을 커밋하기 위해
    • 페이지의 모든 수정을 메모리에서 디스크로 flush
    • 현재의 페이지 테이블을 디스크에 기록
    • 현재의 페이지 테이블을 shadow page 테이블로 만듦
  • shadow 페이지 테이블의 포인터가 쓰여지는 순간 트랜젝션이 커밋됨
  • 장애 이후 recovery가 필요하지 않음 새로운 트랜젝션은 shadow 페이지 테이블로 바로 시작가능하기때문
  • shadow 페이지 테이블이 가리키지 않은 페이지는 garbage임

Shadow Paging (6/6)

  • log기반 스키마에 비해 shadow 페이지의 장점
    • 로그를 기록하는 오버헤드가 없음
    • 복구가 쉬움
  • 단점
    • 전체 페이지 테이블 복사는 비용이 비쌈
    • 커밋 오버헤드가 큼
    • 데이터가 파편화 될 수 있음
    • 모든 트랜젝션이 완료된 후 기존의 페이지는 GC 되어야 함
    • 동시 트랜젝션을 허용하기 힘듦

Recovery With Concurrent Transactions (1/3)

  • 로그 기반 복구 스키마를 동시 트랜젝션 지원을 위해 수정해보자.
  • 로깅을 최대한 빠르게 기록한다.
  • checkpoint 테크닉과 액션은 변경이 필요함

Recovery With Concurrent Transactions (2/3)

  • 체크포인트가 이전에 수행되었는데 이부분을 아래와 같이 변경해보자. , L은 List라는 뜻.
  • 시스템이 복구될 때 아래의 것들을 수행해야함
    • undo-list와 redo-list를 초기화
    • 로그를 끝에서 부터 이 나타날때 까지 backward로 스캔
    • 이 발견되면 redo-list에 넣음
    • 가 발견되고 redo-list에 없으면 undo-list에 넣음
    • L안에 들어간 모든 Ti중에서 redo-list에 없는 녀석은 undo-list에 넣음

Recovery With Concurrent Transactions (3/3)

  • 이 시점에서 undo-list는 완료되지 않은 트랜젝션들이고 redo-list는 다시 실행되어야 하는 트랜젝션들이다.
  • undo-list를 먼저 수행하고 redo-lisst를 수행하는 것이 중요함

Log Record Buffering (1/2)

  • 로그 레코드 버퍼링 : 로그 레코드는 바로바로 디스크에 쓰여지는것 대신에 메인메모리에 버퍼됨
    • 로그 레코드는 버퍼가 꽉 차거나 log force연산이 수행될 때 디스크에 flush됨
  • Log Force는 로그 레코드에 기록된 모든 트랜젝션을 commit하기 위해 디스크에 flush됨
  • 몇몇 로그 레코드들은 하나의 연산에 한번에 디스크에 기록됨(I/O를 줄이기 위해)

Log Record Buffering (2/2)

  • 로그 레코드가 버퍼링 되면 아래의 룰을 지켜야 함
    • 로그 레코드는 생성된 이후 안전한 스토리지로 출력되어야함
    • 트랜젝션 Ti가 commit 상태로 가기 위해서는 로그가 먼저 스토리지에 기록되어야 함
    • 메모리의 데이터 블록 DB로 쓰여지기 전에 모든 로그 레코드는 스토리지로 기록되어야 함 -> 이 룰은 Write Ahead Log 즉 WAL 로그라 부름