List
1. 회복 시스템의 개념
1.1. 회복의 역할
•
예상치 못한 고장 및 오류가 발생했을 때 오류 발생 이전의 일관된 상태로 데이터베이스를 복원시키는 기법이 필요함
•
데이터베이스는 데이터 복원 절차 내재화
1.2. 시스템 실패의 유형
•
트랜잭션 실패
◦
논리적: 잘못된 데이터 입력, 부재, 버퍼 오버 플로우, 자원 초과 이용
◦
시스템적: 운용 시스템의 교착상태
•
시스템 장애
◦
시스템 하드웨어 고장, 소프트웨어 오류
◦
주기억장치 등 휘발성 저장장치 내용 손실
•
디스크 실패
◦
비휘발성 디스크 저장장치의 손상 및 고장으로 인한 데이터 손실
1.3. 회복 데이터의 구성
•
백업
◦
데이터베이스의 일부 또는 전체를 주기적으로 복제하는 방식
•
로그
◦
데이터 변경 이전과 이후의 값을 별도의 파일에 기록하는 방식
1.4. 데이터 저장 구조 및 연산
•
데이터는 디스크와 같은 비휘발성 저장장치에 저장, 전체 데이터의 일부만 주기억장치에 상주
•
데이터베이스는 데이터를 블럭 단위로 전송 & 블럭 단위로 기억장소를 분할
•
트랜잭션은 디스크로부터 주기억장치로 데이터를 가져오고 변경된 데이터는 다시 디스크에 반영
◦
가져오기, 내보내기 연산은 블럭 단위로 실행
◦
물리적 블록: 디스크상의 블록
◦
버퍼 블록: 주기억장치에 임시적으로 상주하는 블록
•
메인 메모리와 디스크 사이의 연산
◦
Input(X) - 물리적 블록 X를 메인 메모리에 적재
◦
Output(X) - 버퍼 블록 X를 디스크에 저장
2. 로그 기반 회복
2.1. 로그 기반 회복의 개념
•
데이터베이스가 수행한 모든 수정 작업을 기록한 여러 종류의 로그를 사용하여 회복하는 시스템
•
로그 레코드
2.2. 데이터 항목 변경 과정
1.
WAL (Write-Ahead Log)
•
트랜잭션은 데이터베이스 수정 전, 로그 레코드를 생성하여 기록
2.
데이터 항목 변경 과정
a.
트랜잭션이 메인 메모리의 개인 영역에서 여러 연산을 수행
b.
트랜잭션이 데이터 항목이 존재하는 메인 메모리에 위치한 버퍼 블럭의 데이터를 변경
c.
Output 명령을 실행하여 버퍼 블럭을 디스크에 기록
2.3. Redo와 Undo 연산
•
회복기법은 로그에 대해 두 연산을 사용
◦
Redo - 데이터베이스에 반영이 안된 경우 다시 반영 시도
◦
Undo - 이전 값으로 되돌림
•
시스템 장애 발생시
◦
로그에 start 로그는 존재하나 commit, abort는 없는 경우 undo
◦
로그에 start 로그는 존재하 commit, abort를 포함하는 경우 redo
•
데이터베이스 커밋
◦
commit 로그 레코드 유무에 따라 커밋 여부를 판단
2.4. 회복 유형
•
요청된 갱신 작업이 디스크에 반영되는 시점에 따라 회복 작업이 구분됨
•
지연 갱신 회복 (deferred update restore)
◦
부분 커밋까지 디스크 반영을 지연시키고 로그에만 기록
◦
실패 시, 별도의 회복 작업 없이 로그만 수정
•
즉시 갱신 회복 (immediate update restore)
◦
갱신 요청을 곧바로 디스크에 반영
◦
실패시 디스크에 반영된 갱신 내용을 로그를 바탕으로 회복
•
예시
2.5. 체크포인트
•
로그 기반 회복 시스템의 한계
◦
로그의 크기는 선형적으로 증가 → 대용량 → 로그 탐색 비용 증가
◦
Redo 해야하는 트랜잭션 중 대부분은 이미 데이터베이스에 반영
◦
반영된 트랜잭션의 재실행은 시스템 자원의 낭비
•
체크포인트 기법 제안
◦
현재 시점에 메인 메모리의 버퍼 블럭에 존재하는 모든 레코드를 안정 저장장치로 기록
▪
버퍼에 있는 모든 레코드를 out하여 디스크에 저장
◦
수정된 모든 버퍼 블럭을 디스크에 반영
◦
로그 레코드 <checkpoint ListT> 를 안정 저장장치에 기록
▪
ListT = 현재 체크포인트 시점에 실행중인 트랜잭션 목록
▪
커밋된 것과 커밋되지 않고 실행중인 것을 구분하는 용도
▪
체크 포인트 시점에서 처리된것은 배제시키고 실행중인거산 회복 시스템을 동작시키겠다는 의미
2.6. 체크포인트를 이용한 회복
•
로그의 마지막으로부터 역방향으로 탐색하여 가장 최근의 <checkpoint ListT> 레코드를 찾음
•
ListT 에 존재하는 <checkpoint ListT> 이후에 실행된 트랜잭션에 대하여 Redo / Undo 연산 수행
◦
로그에 커밋, 어보트가 없는 트랜잭션들은 Undo
◦
로그에 커밋, 어보트가 있는 트랜잭션들은 Redo
3. 회복 알고리즘
3.1. 트랜잭션 롤백 알고리즘
•
1단계 - 로그를 역방향으로 탐색
•
2단계 - 트랜잭션의 로그 레코드 <Ti, Xj, V1, V2> 에 대하여
◦
데이터 항목 Xj에 V1 기록
◦
로그 레코드 <Ti, Xj, V1>을 로그에 기록 (값을 원복시켰음을 의미)
•
3단계 - 트랜잭션의 시작 로그를 찾은 후
◦
역방향 탐색 중단
◦
로그 레코드 어보트로 로그 기록
•
예시)
◦
Wirte 중 시스템 에러 발생
◦
롤백 알고리즘
3.2. 시스템 장애 후 회복 알고리즘
•
시스템 장애 이후 재시작 시 다음 두단계를 거침
◦
Redo, Undo 단계
•
Redo 단계
◦
최근에 체크 포인트에서부터 순방향 로그 탐색
◦
롤백 대상할 트랜잭션의 Undo 리스트인 ListofUndo를 ListT로 초기화
▪
실행시켰던 트랜잭션들을 Undo 트랜잭션 목록으로 추가
◦
<Ti, Xj, V1, V2>. <Ti, Xj, V1> 형태의 모든 레코드를 재실행
▪
Undo 실행
◦
<Ti, start> 발견시, Ti를 ListofUndo에 추가
◦
<Ti, abort>, <Ti, commit> 발견시 Ti를 undo 리스트에서 제거
▪
Redo 해야함
•
Undo 단계 (역방향 로그 탐색)
◦
ListofUndo 트랜잭션의 로그 레코드를 찾으면 트랜잭션 롤백 알고리즘 1단계 수행
◦
ListofUndo의 트랜잭션 Ti에 대하여 <Ti, start>를 만나게 되면 로그에 <Ti, abort>를 기록하고 ListofUndo에서 제거
◦
ListofUndo에 트랜잭션이 존재하지 않는 상태가 되면 Undo 단계 종료
•
예시)
◦
기존 형태 → abort 시 실패 발생
◦
Redo
▪
체크 포인트 기준으로 T0, T1이 undo 리스트에 추가
•
undo 리스트: [T0, T1]
▪
T1은 커밋 로그 → undo 리스트에서 제거
•
undo 리스트: [T0]
▪
T2 시작 로그 → undo 리스트에 추가
•
undo 리스트: [T0, T2]
▪
T0 어보트 로그 → undo 리스트에서 제거
•
undo 리스트: [T2]
◦
undo
▪
T2 undo 진행
