복구 시스템

kudos·2021년 5월 20일

데이터베이스

목록 보기

8/8

1. 저장장치

데이터베이스 내의 다양한 데이터 항목들은 수없이 다양한 저장 매체에 저장되고 액세스 된다. 저장 매체는 다음 3개의 카테고리로 분류할 수 있다.

휘발성 저장 매체
비휘발성 저장 매체
안정 저장 매체

이 중에서 안정 저장 매체는 복구 알고리즘에서 중요한 역할을 수행한다.

1) 안정 저장 장치의 구현

안정 저장 장치를 구현하기 위해서는 먼저 필요한 정보를 여러 비휘발성 저장 매체(주로 디스크)에 중복해 저장해야 한다. 또 필요로 하는 정보가 데이터 전송 실패로 인해 손상되지 않는 것을 보장하기 위해 통제된 방법으로 데이터를 갱신해야 한다.

RAID 시스템은 데이터 전송 중에 한 디스크의 실패가 발생해도 데이터의 손실이 발생하지 않도록 보장해준다. 그러나 RAID 시스템은 화재나 홍수 같은 재난으로 발생하는 데이터 손실은 보호해 줄 수 없다. 이러한 재난에 대비하여 별도의 장소에 보관용 백업 테이프를 저장해둔다. 그러나 테이프를 쉬지 않고 계속해서 별도의 장소로 이동할 수 없기 때문에, 가장 최근 테이프를 이동한 이후 발생한 갱신 내용은 그런 재난으로 잃어버릴 수도 있다.

좀더 안전한 시스템은 로컬 디스크 시스템에 블록을 저장함과 동시에 각 블록의 사본을 원격 사이트에 보관하고 컴퓨터 네트워크를 통해 갱신하는 방식의 시스템이다. 블록은 로컬 저장 장치에 기록되는 동시에 원격 시스템에 기록되기 때문에 한 번 기록 연산이 종료되면 재난이 발생해도 결과가 보존된다.

메모리와 디스크 저장 장치 사이의 블록 전송 결과는 다음과 같다.

성공적인 완료 : 전송된 정보가 목적지에 안전하게 도착
부분 실패 : 전송 중에 실패가 발생해 목적기 블록이 정확하지 않은 정보를 갖게 됨
완전 실패 : 전송 초기에 실패가 발생해 목적지의 블록이 그대로 남아있음

데이터 전송 실패(data transfer failure)가 발생하면 시스템은 이를 탐지하고 복구 프로시저를 호출해 블록을 일관성 있는 상태로 되돌려야 한다. 이를 위해 시스템은 각 논리적 데이터베이스 블록에 대해 두 개의 물리적 블록을 유지해야 한다. 기록 연산은 아래와 같이 실행된다.

정보를 첫 번째 물리 블록에 기록
첫 번째 기록이 성공적으로 끝나게 되면 동일한 정보를 두 번째 물리 블록에 기록
두 번째 기록이 성공적으로 종료된 경우에만 기록 완료

블록이 기록되는 도중 시스템 실패가 발생하는 경우 두 블록의 내용이 일치하지 않는 상황이 발생할 수 있다. 복구 시에는 각 블록에 대해 두 개 사본을 모두 검사해야 한다.

둘이 서로 같고 발견된 에러가 있는 경우 : 특별한 동작 필요 X
한 블록에 에러가 있다는 것을 발견한 경우 : 다른 블록의 내용으로 대체
두 블록에 오류가 없는데 서로 다른 내용을 가진 경우 : 첫 번째 블록의 내용으로 두 번째 블록의 내용 변경

복구 중에 모든 대응되는 블록의 쌍을 비교하는 것은 비용이 매우 많이 드는 일이다. 이 비용을 작은 양의 비휘발성 RAM을 사용해 어느 블록에 기록 중이었는지 저장해둠으로써 크게 감소시킬 수 있다. 복구 시에는 오직 기록 작업이 진행되었던 블록만 비교하면 된다.

2) 데이터 액세스

데이터베이스 시스템은 비휘발성 저장 장치(보통 디스크)에 저장되며 전체 데이터베이스의 일부분만 메모리에 상주한다. 데이터베이스는 블록(block)이라 불리는 고정 길이 저장 단위로 분할된다. 블록은 디스크 사이의 데이터 전송 단위이며 여러 개의 데이터 항목을 가진다.

트랜잭션은 디스크에서 메인 메모리로 정보를 입력하며 다시 그 정보를 디스크에 기록한다. 입력과 기록의 연산은 블록 단위로 이뤄진다. 디스크 상의 블록을 물리적 블록(physical block)이라고 하고 메인 메모리에 임시적으로 있는 블록을 버퍼 블록(buffer block)이라고 한다. 블록이 임시로 있게 되는 메모리 영역을 디스크 버퍼(disk buffer)라고 부른다.

메인 메모리와 디스크 사이의 블록 이동은 아래 두 가지 연산에 의해 발생한다.

input(B) : 물리적 블록 B를 메인 메모리로 전송한다.
output(B) : 버퍼 블록 B를 디스크로 전송하고 그곳에 적당한 물리적 블록을 대체시킨다.

개념적으로, 각 트랜잭션 $T_{i}$ 는 자신이 액세스하고 갱신할 모든 데이터 항목들의 사본이 저장될 개인 작업 영역을 가진다. 트랜잭션이 초기화될 때 이 작업 영역의 시스템에 의해 만들어지며 트랜잭션이 커밋되거나 취소될 때 제거된다. 트랜잭션 $T_{i}$ 의 작업 영역 안에 있는 데이터 항목 X를 $x_{i}$ 라고 하자. 트랜잭션 $T_{i}$ 는 자신의 작업 영역과 시스템 버퍼 사이에 데이터를 주고받음으로써 데이터베이스 시스템과 상호 작용한다. 다음 두 가지 연산을 통해 데이터를 전송한다.

read(X) : 데이터 항목 X의 값을 지역변수 $x_{i}$ 에 할당한다. 이 연산은 아래와 같다.
a. X가 위치하는 블록 $B_{x}$ 가 메인 메모리에 없을 경우 input( $B_{x}$ )를 실행한다.
b. 버퍼 블록으로부터 X의 값을 $x_{i}$ 에 할당한다.
write(X) : 지역변수 $x_{i}$ 의 값을 버퍼 블록 안에 있는 데이터 항목인 X에 할당한다. 이 연산은 아래와 같다.
a. X가 위치하는 블록 $B_{x}$ 가 메인 메모리에 없을 경우 input( $B_{x}$ )를 실행한다.
b. 버퍼 $B_{x}$ 내의 X에 $x_{i}$ 값을 할당한다.

두 연산 모두 디스크로부터 메인 메모리로 블록 전송을 요구하지만 메인 메모리로부터 디스크로의 블록 전송을 요구하지는 않는다.

하지만 버퍼 관리자가 다른 목적으로 인해 메인 메모리의 공간을 필요로 하거나 데이터베이스 시스템이 갱신 내용을 디스크 상의 B에 반영하기를 원할 때 버퍼 블록은 결국 디스크에 기록된다. 데이터베이스 시스템이 버퍼 B에 ouput(B)를 실행하는 것을 강제 기록(force-output)이라고 한다.

트랜잭션이 데이터 항목 X에 처음으로 액세스하고자 할 때 반드시 read(X)를 실행해야 한다. 그런 다음 시스템은 X에 대한 모든 갱신을 $x_{i}$ 에 수행한다. 트랜잭션은 X의 변경 사항을 데이터베이스에 반영하기 위해 언제든지 write(X)를 실행할 수 있다. 마지막 갱신 작업이 끝난 후에는 반드시 write(X)를 수행해야 한다.

X가 위치한 블록 버퍼 $B_{x}$ 에 대한 연산 output( $B_{x}$ )는 write(X)가 실행된 후 즉각적으로 실행될 필요는 없다. 왜냐하면 X가 위치하는 $B_{x}$ 가 현재 아직 실행 중인 데이터 항목들을 포함하고 있을 수도 있기 때문이다. 따라서 실제적인 기록은 이후에 일어난다. 그러므로 만약 write(X) 연산이 실행되었지만 아직 output( $B_{x}$ )가 실행되기 전에 시스템 실패가 일어나면 X의 새로운 값은 디스크에 기록되지 않았고 따라서 갱신 내용을 잃게 된다.

2. 복구와 원자성

초기 값이 각각 $1000와 $2000인 A계좌와 B계좌 간에 A에서 B로 $50의 이체가 있는 트랜잭션 $T_{i}$ 를 생각해보자. 트랜잭션 $T_{i}$ 를 실행하는 도중 output( $B_{A}$ )는 실행되고 output( $B_{B}$ )가 실행되기 전에 시스템 오류가 발생했다고 가정하자. 메모리의 내용이 손실되었기 때문에 트랜잭션의 상황을 알 수는 없다.

시스템이 재시작된 후는 트랜잭션 $T_{i}$ 의 원자성이 깨진 상태이다. 데이터베이스의 상태를 조사해 장애 이전에 어떤 블록이 출력되었으며 어떤 블록이 그렇지 못했는지 알아낼 방법이 없다.

$T_{i}$ 에 의해 행해진 데이터베이스 변경 내용은 모두 적용되던지 아니면 전혀 변경되지 않던지 둘 중 하나여야 한다. 그러나 $T_{i}$ 가 데이터베이스에 다수의 변경 사항을 적용하는 경우 여러 개의 기록 연산이 필요할 것이며 이들 변경 사항 중 일부는 이미 변경되었고 일부는 오류로 인해 반영되지 못했을 것이다.

원자성을 보장하기 위해서는 먼저 데이터에비스 자체에 변경을 하기 전에 안정 저장 장치에 데이터베이스 변경과 연관된 정보를 기록해야 한다. 이 정보는 커밋된 트랜잭션에 의해 수행된 변경 사항이 데이터베이스에 모두 반영되는 것을 보장해준다. 또한, 이 정보는 트랜잭션의 변경 사항이 데이터베이스에 반영되지 않도록 해준다.

1) 로그 레코드

로그는 로그 레코드의 시퀀스이며 데이터베이스의 모든 갱신 작업을 기록한다. 로그 레코드에는 몇 가지 종류가 있다. 갱신 로그 레코드(update log record)는 한 번의 데이터베이스 기록을 기술하며 아래의 필드를 갖는다.

트랜잭션 ID : 기록(write) 연산을 수행하는 트랜잭션의 고유 식별자
데이터 항목 ID : 기록한 데이터 항목의 고유 식별자로, 일반적으로 데이터 항목의 디스크 상 위치이며, (데이터 항목이 존재하는 블록의 블록 식별자 + 블록 안에서의 offset)으로 구성된다.
old value : 기록하기 전의 데이터 항목의 값
new value : 기록 이후에 데이터 항목이 가질 값

로그 레코드의 종류별 형식

갱신 로그 레코드 : < $T_{i}$ , $X_{j}$ , $V_{1}$ , $V_{2}$ >
트랜잭션 시작 : < $T_{i}$ , start>
트랜잭션 커밋 : < $T_{i}$ , commit>
트랜잭션 취소 : < $T_{i}$ , abort>

트랜잭션이 기록 연산을 수행할 때마다 데이터베이스가 변경되기 전에 기록 연산을 위한 로그 레코드가 생성되고 로그에 추가되어야 한다. 일단 로그 레코드가 존재하면 바로 언제든 데이터베이스에 변경 내용을 기록할 수 있다. 또한 데이터베이스 상에 이미 기록된 변경 사항을 로그 레코드 상의 이전 값을 이용하여 취소(undo)할 수도 있다.

시스템과 디스크 실패로부터의 복구를 위해 로그 레코드를 사용하기 위해서는 로그가 안정 저장 장치에 있어야 한다. 이제부터 모든 로그 레코드는 생성되자마자 안정 저장 장치 상에 있는 로그의 마지막에 기록된다고 가정하자.

2) 데이터베이스 변경

트랜잭션이 데이터 항목을 변경하는 과정

트랜잭션은 메인 메모리의 개인 영역에서 여러 연산을 수행한다.
트랜잭션은 데이터 항목이 존재하는 메인 메모리에 위치한 디스크 버퍼 상의 데이터 블록을 변경한다.
데이터베이스 시스템이 데이터 블록을 디스크에 기록하기 위해 output 명령을 수행한다.

지연 변경 vs 즉시 변경

트랜잭션이 데이터베이스를 수정한다는 것은 트랜잭션이 디스크 버퍼 또는 디스크 자체를 갱신하는 것을 말한다.

지연 변경(deferred-modification) : 트랜잭션이 커밋될 때까지 데이터베이스 수정 X
즉시 변경(immediated-modification) : 트랜잭션이 수행되는 도중 데이터베이스 수정

복구 알고리즘이 고려해야할 것

데이터베이스에 대한 변경 중 일부가 메인 메모리의 디스크 버퍼에만 반영되고 디스크에 기록되지 않았음에도 트랜잭션이 커밋된 경우
트랜잭션이 active 상태에서 데이터베이스를 수정했지만 추후에 실패로 인해 취소가 필요한 경우

undo vs redo

모든 데이터베이스 변경은 반드시 로그 레코드를 생성한 후 수행되어야 하기 때문에 시스템은 데이터 항목의 old value와 new value를 사용할 수 있다. 이 덕분에 시스템은 undo와 redo 명령을 적절히 사용할 수 있다.

undo : 로그 레코드를 사용해 로그 레코드에 지정된 데이터 항목을 old value으로 변경
redo : 로그 레코드를 사용해 로그 레코드에 지정된 데이터 항목을 new value로 변경

3) 동시성 제어와 복구

만일 동시성 제어 방법이 트랜잭션 $T_{1}$ 이 변경한 데이터 항목 X를 $T_{1}$ 이 커밋되기 전에 다른 트랜잭션 $T_{2}$ 가 수정하는 것을 허용한다면 X의 값을 복구해 $T_{1}$ 을 되돌릴 경우 $T_{2}$ 의 수정사항이 사라지게 된다. 이와 같은 상황을 방지하기 위해 복구 알고리즘은 한 트랜잭션이 수정한 데이터 항목은 이 트랜잭션이 커밋되거나 취소되기 전까지는 다른 트랜잭션이 수정할 수 없도록 해야 한다. 이를 위해서는 수정하는 모든 데이터 항목에 대해 exclusive lock을 획득하고 트랜잭션이 커밋되기 전까지 lock을 해제하지 않아야 한다.

4) 트랜잭션 커밋

트랜잭션의 마지막 로그 레코드인 커밋 로그 레코드가 안정 저장 장치에 기록되면 트랜잭션이 커밋되었다고 한다. 이 시점에서는 이전의 모든 레코드들이 이미 안정 저장 장치에 기록되어 있다. 따라서 시스템 장애가 발생해도 트랜잭션에서 발생한 갱신 작업들을 다시 수행할 수 있는 충분한 정보를 갖게 된다. 만일 로그 레코드 < $T_{i}$ , commit>이 기록되기 전에 시스템이 실패했다면, 트랜잭션 $T_{i}$ 는 롤백되어야 한다.

5) 로그를 이용한 트랜잭션 redo와 undo

redo( $T_{i}$ ) : 트랜잭션 $T_{i}$ 에 의해 갱신된 new value로 데이터베이스의 데이터 항목들의 값을 갱신한다.
- redo에 의한 갱신 작업 처리 순서의 중요성 : 복구 시 특정 데이터 항목에 대한 갱신 작업이 본래 작업한 순서와 다르게 이뤄진다면, 그 데이터 항목의 최종 값이 잘못된 값이 될 수 있다. 대부분의 복구 알고리즘은 redo 작업을 각 트랜잭션 별로 수행하지 않고 로그를 순차적으로 스캔하며 각 로그 레코드에 대한 redo 작업을 한다.
undo( $T_{i}$ ) : 트랜잭션 $T_{i}$ 에 의해 갱신된 모든 데이터 항목들을 old value로 되돌린다.
- 데이터 항목을 old value로 복구할 뿐만 아니라 이런 복구 과정에서 생기는 갱신 작업에 대한 로그를 기록한다. 이들 로그 레코드는 갱신된 데이터 항목에 대해 이전 값을 갖고 있을 필요가 없다.
- 트랜잭션 $T_{i}$ 의 undo 연산이 끝나면 undo 작업이 완료되었음을 나타내는 < $T_{i}$ , abort> 로그 레코드를 기록한다.

시스템 장애가 발생한 이후 시스템은 원자성을 보장하기 위해 로그를 통해 어떤 트랜잭션을 재실행하고 어떤 트랜잭션을 되돌릴지 결정한다.

undo 해야 하는 경우 : 로그가 < $T_{i}$ , start> 레코드를 가지고 있지만 < $T_{i}$ , commit> 또는 < $T_{i}$ , abort> 레코드를 포함하지 않을 경우
redo 해야 하는 경우 : 로그가 < $T_{i}$ , start> 레코드를 가지고 있고 < $T_{i}$ , commit> 또는 < $T_{i}$ , abort> 레코드를 포함하는 경우

6) checkpoint

시스템에 장애가 발생하면 로그를 참조하여 재실행되어야 할 트랜잭션과 취소되어야 할 트랜잭션을 결정해야 한다. 이 결정을 위해 원칙적으로는 로그 전체를 탐색해야 하지만 로그 전체를 탐색할 경우 다음과 같은 두 가지 문제가 있다.

검색에 너무 많은 시간이 소비된다.
알고리즘에 따르면 redo를 해야 하는 트랜잭션 중 대부분은 데이터베이스에 이미 갱신이 이루어졌을 수 있다. 이는 불필요한 시간을 잡아먹는다.

이러한 종류의 부하를 줄이기 위해 checkpoint를 사용한다.

checkpoint 동작 방식

현재 메인 메모리에 존재하는 모든 로그 레코드를 안정 저장 장치로 기록
변경된 모든 버퍼 블록을 디스크로 기록한다.
로그 레코드 <checkpoint L>을 안정 저장 장치로 기록한다. 여기서 L은 checkpoint 시점에 동작 중인 트랜잭션의 목록이다.

checkpoint가 실행되는 동안에는 버퍼 블록이나 로그 레코드를 기록하는 등의 어떠한 갱신도 허용되지 않는다.

checkpoint 활용 방식

시스템 장애 후에 시스템은 로그에서 마지막 <checkpoint L> 레코드를 찾는다.
redo와 undo 연산은 L에 있는 트랜잭션과 <checkpoint L> 레코드 이후에 시작된 트랜잭션에 대해서만 수행하면 된다.

3. 복구 알고리즘

1) 트랜잭션 롤백

정상 상황(즉, 시스템 장애로부터의 복구가 아닌)에서의 트랜잭션 롤백을 살펴보자. 트랜잭션 $T_{i}$ 의 롤백은 다음과 같이 수행된다.

로그를 역방향으로 탐색한다. $T_{i}$ 의 로그 레코드 < $T_{i}$ , $X_{j}$ , $V_{1}$ , $V_{2}$ >에 대해
a. 데이터 항목 $X_{j}$ 에 값 $V_{1}$ 을 기록한다.
b. redo 전용 로그 레코드 < $T_{i}$ , $X_{j}$ , $V_{1}$ >을 로그에 기록한다.
< $T_{i}$ start>를 찾으면 역방향 탐색을 중단한다. 그리고 < $T_{i}$ abort> 로그 레코드를 로그에 기록한다.

2) 시스템 실패 후의 복구

실패 이후에 데이터베이스 시스템이 재시작될 때 다음 두 가지 단계를 거쳐 복구가 이뤄진다.

redo 단계에서 시스템은 마지막 checkpoint에서부터 순방향으로 로그를 탐색하며 모든 트랜잭션의 갱신을 재실행한다. 재실행되는 로그 레코드에는 실패 이전에 롤백되었던 트랜잭션의 로그 레코드와 실패 시 미완료 트랜잭션의 로그 레코드 등을 포함한다. 로그 탐색 과정은 다음과 같다.
a. 롤백해야 할 트랜잭션의 리스트, undo-list를 <checkpoint L>의 L로 초기화한다.
b. < $T_{i}$ , $X_{j}$ , $V_{1}$ , $V_{2}$ > 형태의 일반적인 로그 레코드나 < $T_{i}$ , $X_{j}$ , $V_{1}$ > 형태의 redo 전용 로그 레코드를 만나면 해당 연산을 재수행한다.
c. < $T_{i}$ start>를 만나면 $T_{i}$ 를 undo-list에 추가한다.
d. < $T_{i}$ abort> < $T_{i}$ commit> 로그 레코드를 만나면 $T_{i}$ 를 undo-list에서 제거한다.

redo 단계가 끝나면 undo-list는 미완료 트랜잭션, 즉 실패 이전에 커밋되거나 롤백을 완료하지 못한 트랜잭션을 갖게 된다.

undo 단계에서 시스템은 undo-list에 있는 모든 트랜잭션들을 롤백한다. 끝에서부터 역방향으로 탐색을 통해 롤백을 수행한다.
a. undo-list의 트랜잭션에 속한 로그 레코드를 찾으면 실패한 트랜잭션의 롤백과 같은 방식으로 undo 동작을 수행한다.
b. undo-list 내의 트랜잭션 $T_{i}$ 에 대해 < $T_{i}$ start> 로그 레코드를 발견하면 < $T_{i}$ abort>를 로그에 기록하고 undo-list에서 $T_{i}$ 를 제거한다.
c. undo-list가 비어있는 상태가 되면, 즉 초기의 undo-list 내의 모든 트랜잭션에 대해 < $T_{i}$ start>를 발견하면 undo 단계를 종료한다.

undo 단계가 끝나면 정상적인 트랜잭션 처리를 다시 시작할 수 있다.

그림 16.5에는 정상 작업에서의 로그와 복구시의 작업 예제를 보여준다. 그림의 로그에서 시스템 실패 이전에 $T_{1}$ 은 커밋되었고 트랜잭션 $T_{0}$ 는 롤백되었다. $T_{0}$ 의 롤백 중에 데이터 항목 B의 값이 어떻게 복구되었는지, 또한 checkpoint 레코드에 active 트랜잭션인 $T_{0}$ 과 $T_{1}$ 이 있는 것을 볼 수 있다.

실패로부터 복구할 때에 redo 단계에서 시스템은 마지막 checkpoint 이후의 모든 작업을 재실행한다. 이 단계에서 undo-list는 $T_{0}$ 과 $T_{1}$ 으로 초기화된다. $T_{1}$ 은 commit 로그를 발견하게 되면 가장 먼저 제거되고 $T_{2}$ 는 start 로그를 발견하는 때에 추가된다. 트랜잭션 $T_{0}$ 는 abort 로그를 만나면 undo-list에서 제거되고 $T_{2}$ 만 undo-list에 남게된다. undo 단계에서는 로그를 마지막부터 역방향으로 탐색한다. A를 갱신하는 $T_{2}$ 로그를 발견하면 A의 이전 값이 복구되고 redo 전용 로그가 로그에 기록된다. $T_{2}$ 의 start레코드를 발견하면 $T_{2}$ 의 abort 레코드가 추가된다. undo-list에 트랜잭션이 더 이상 없기 때문에 undo 단계가 끝나고 복구가 완료된다.

참고

Database System Concepts 16장

kudos

이전 포스트