- Published on
ARIES 알고리즘
- Authors
- Name
- Intro
- Name
- Intro
- Name
- ARIES Main Idea
- Name
- Data Structures
- Name
- Transaction Rollback
- Name
- Pseudo Code
- Name
- Partial Rollback
- Name
- Fuzzy Checkpoints
- Name
- Restart Recovery
- Name
- Analysis Phase
- Name
- Redo Phase
- Name
- Undo Phase
- Name
- 미디어 손실로부터의 복구
- Name
- 참고
Tags
Previous Article
Next Article
Intro
데이터베이스 트랜잭션과 Undo와 Redo Log
로그 기반 복구 작업
로그 기반 복구 작업-2
이제 모든 준비가 끝났다. ARIES는 DBMS 복구작업을 위한 state of the art 기법이다.
Intro
전체적 흐름을 되짚어보고 ARIES로 나아가자.
먼저 트랜잭션은 논리적으로 더 이상 쪼갤 수 없는 작업의 단위로서 물리적으로는 일련의 읽기와 쓰기 작업의 결합이다. 이러한 트랜잭션이 안전하게 수행되지 않으면, 데이터베이스의 상태가 망가질 수 있기 때문에 반드시 ACID(Atomicity, Consistency, Isolation, Duration) 성질을 지킴으로써 안전한 트랜잭션이 보장되어야만 한다.
통상적인 목적의 데이터베이스는 데이터의 손실을 방지하기 위해 non-volatile storage(디스크)를 기본 저장소로 이용한다. 그런데, non-volatile storage는 반영구적인 데이터 보존이 가능한 대신 접근 속도가 느리다는 단점이 있다. 일련의 읽기/쓰기 작업을 수행하기 위해선 필연적으로 volatile storage를 임시 저장소로 사용(cache)하여 빠른 접근 속도를 이용해야만 한다.
따라서 데이터에 대한 접근은 반드시 다음과 같은 순서로 이루어져야 한다.
- 먼저 대상이 되는 레코드를 메모리에 복사한다.
- 필요한 쓰기 작업을 메모리에서 수행한다.
- 다시 변경된 레코드(dirty record)를 디스크로 출력한다.
이 때 데이터베이스는 안정적인 트랜잭션을 위해 다음과 같은 기능을 제공해야 한다.
| 작업 | 설명 |
|---|---|
| Redo | DBMS로부터 commit이 된 변경사항이 반드시 영구적(durability)으로 반영되도록 보장하는 과정 |
| Undo | 부분적으로 완료된 트랜잭션이 중단(abort)되면 부분완료된 결과가 데이터베이스의 상태를 변경하지 않도록 보장하는 과정 |
데이터베이스에서 트랜잭션을 복구해야하는 상황은 크게 2가지로
- 트랜잭션 과정 일부에 문제(무결성 제약 위반, 데드락 등)가 생겨 트랜잭션을 더이상 진행할 수 없어 atomicity와 consistency를 위해 전체 작업을 취소해야 하는 경우
- 어떤 이유로 DBMS가 의도치 않게 종료되어 데이터베이스의 상태가 더 이상 트랜잭션의 atomicity, consistency, durability를 보장할 수 없는 경우
변경된 레코드(dirty record)를 디스크에 쓰는 시점에 따라 메모리 버퍼 관리 정책이 나뉘게 되는데 이는 다음과 같다.
트랜잭션을 진행하는 과정에서 버퍼를 어떻게 관리할 것인가?
- STEAL: 커밋되지 않은 레코드를 디스크로 출력(flush)하고 메모리에서 제거(evict)할 수 있다.
- NO-STEAL: 커밋되지 않은 레코드를 디스크로 출력하지 않고 메모리에 유지한다.
트랜잭션을 커밋하는 시점에서 버퍼를 어떻게 관리할 것인가?
- FORCE: 커밋을 처리하는 시점에 디스크로 모든 변경사항이 반영되어야 한다.
- NO-FORCE: 커밋을 처리하는 시점에 디스크에 변경사항이 반영되지 않을 수 있다.
| STEAL | NO-STEAL | |
|---|---|---|
| FORCE | Pros: 구현과 관리가 간단하고 복구작업이 쉬움 Cons: 메모리 사용량과 트랜잭션 throughput 감소 | |
| NO-FORCE | Pros: 메모리 사용량 감소, throughput 증가 Cons: 트랜잭션 중단 시 복구 방안이 필요 |
RDBMS의 경우 runtime performance를 위해 대부분 STEAL + NO-FORCE 정책을 채택하고 추가적인 복구 알고리즘을 사용하는데,
- 이는 앞서 얘기한 메모리 사용량과 throughput뿐만 아니라,
- FORCE 정책을 통한 디스크 쓰기 작업이 현실적으로 atomic하지 않다는 문제로 인해 필연적으로 복구작업이 필요하기 때문이다.
그렇다면 STEAL과 NO-FORCE 작업에선 어떤 복구 알고리즘이 필요한가? 보통 로그를 이용한다.
STEAL
문제: 만약 트랜잭션이 **취소(Abort)**되었으나 디스크에 이미 dirty record가 flush됐다면? => Atomicity가 깨진 상황해결볍: 기존 값을 따로 저장(log)해둔 뒤에 복구(undo)
NO-FORCE
문제: 만약 트랜잭션이 커밋되고 dirty page가 flush되기 전에 crash가 일어난다면? => Durability가 깨진 상황해결법: 변경사항을 따로 저장(log)해둔 뒤에 재실행(redo)
로그는 데이터베이스의 변경사항에 관한 정보를 연속적인 형태로 기록한 자료구조이다. DBMS는 변경사항을 디스크에 반영하기 전에 반드시 먼저 변경사항을 로그로 기록해야 한다. 이러한 규칙을 Write-Ahead Logging이라고 하는데, 이를 통해 undo와 redo를 수행하여 안전한 트랜잭션 수행을 보장한다.
Physical Logging
페이지의 변경 전, 변경 후의 페이지 자체를 byte-level로 기록한다. 만약 여러 레코드를 수정하는 트랜잭션의 경우 로그의 양이 많아질 수 있다. byte-level과 offset 자체를 기록했기 때문에 undo와 redo 작업이 단순하다.Logical Logging
레코드에 대한 high-level 연산(예. A=A+1)을 기록한다. 로그의 양이 줄어든다는 장점이 있으며, undo와 redo 작업을 위해 연산을 다시 실행해야 하기 때문에 physical logging보다 복구 시간이 오래 걸리고 구현이 좀 더 어렵다.Physiological Logging
페이지 자체는 물리적으로 식별하고, 해당 페이지 내의 변경사항은 논리적으로 기록한다. Physical logging보다는 적은 공간을 차지하고, logical logging보다는 복구 방식이 단순하다.
약간의 추가적 논의로 lock과 latch를 알아보자. lock과 latch는 모두 synchronization mechanism의 일종으로 공유 자원에 대한 접근을 통제, 관리하는 용도이다. lock은 아마 다들 많이 들어봤을텐데 latch는 무엇일까?
latch
하위 레벨의 자원(메모리, 디스크 접근 등)을 보호하기 위한 lock! 보통 하드웨어(CPU)의 atomic operation을 통해 구현하며, 잠금을 대기하는 과정도 보통 자원이 해제될 때까지 무한루프(spin lock)를 도는 방식이다.
따라서 매우 짧은 대기 시간이 필요한 하위 레벨의 자원 접근을 통제하는 경우 쓰이며, 큐 등의 복잡한 메커니즘은 지원하지 않는다.보통 Shared Latch(S-latch)와 eXclusive Latch(X-latch)로 구분.
lock
상위 레벨 코드에서 논리적인 차원의 공유자원 보호를 위해 사용하는 개념이다. 따라서 lock은 latch와는 달리 유저레벨 라이브러리에서 구현되며, 보통 좀 더 상위 레벨 오브젝트(테이블, 테이블 레코드, 사용자 로직 등)을 보호하기 위해 사용된다.접근레벨로는 Shared(S), eXclusive(X), Intention Shared(IS), Intention eXclusive(IX), Shared Intention eXclusive(SIX)
Intention ~라는 것은 간단히 하위노드에서 lock을 걸겠다는 의미로 받아들이자.
ARIES Main Idea
**ARIES(Algorithms for Recovery and Isolation Exploiting Semantics)**는 상기한 배경 아래 IBM에서 개발된 Recovery Algorithm으로 현재 대부분의 DBMS 구현체에서 이용하고 있는 SOTA 회복기법이다.
ARIES의 핵심 아이디어를 요약하면 다음과 같다.
Write-Ahead Logging(WAL)
STEAL + NO-FORCE 정책을 통해 runtime performance를 확보하고 recovery를 위해 WAL 정책을 이용한다.Repeating History During Redo
DBMS의 재시작 시점에 그동안 기록된 log를 순서대로 스캔하며 데이터베이스의 상태를 충돌 시점으로 복원한다.Logging Changes During Undo
이미 실행된 undo 작업에 대해 보상 로그 레코드(Compensation Log Record)를 기록하여 반복된 undo 작업으로 인한 오버헤드를 방지한다.
그 외에도 ARIES는 partiall rollback과 fuzzy checkpoint 등 몇 가지 테크닉을 통해 최적화를 수행하는데, 이 글에서도 조금 살펴볼 것이다.
Data Structures
- Log Records
로그레코드는 데이터베이스의 변경사항에 관련한 모든 정보를 저장하는 가장 중요한 자료구조로서 일련의 연속된 형태로 저장하게 된다.
몇 가지 데이터의 경우 임의로 int 타입으로 설명하겠다.
class LogRecord:
lsn: int
# 로그를 식별하기 위한 번호로서 storage 상의 로그레코드 주소이다. 로그는 일련의 연속된 형태로 저장하기 때문에 **단조증가(monotone increasing)**한다.
type: str
# 로그의 타입을 의미하는데, 이 글에서는 간단히 "update", "compensation", "end", "begin_chkpt", "end_chkpt" 등을 다룬다.
trans_id: int
# 로그의 변경사항이 발생한 트랜잭션의 고유식별자이다.
prev_lsn: int
# 담당 트랜잭션으로부터 발생한 이전의 로그레코드를 식별한다. 따라서 모든 트랜잭션의 로그레코드는 일종의 Linked List 형태로 접근할 수 있다. 만약 트랜잭션의 첫 로그일 경우 0으로 설정한다.
page_id: int
# 변경사항이 발생한 페이지의 식별자이다.
undo_nxt_lsn: int
# compensation log record에서 사용하는 필드로 롤백 과정에서 다음으로 수행할 undo record를 지정한다. 즉, compensation log를 발생시킨 log(현재 undo log)의 prev_lsn. 마찬가지로 더이상 undo할 레코드가 없을 경우 0으로 설정한다.
data: bytes
# undo and/or redo 정보. 즉 undo 정보만 담길 수도(undoable) 있고, redo 정보만(redoable) 담길 수도 있고, 둘 다 담을 수도 있다. 로그의 타입(physical, logical ...)에 따라 필요한 정보가 달라진다.
- Page Structure
모든 페이지는 PageLSN 필드를 포함한다. 이는 페이지의 마지막 업데이트 정보를 기록한 로그의 LSN으로 CLR도 그 대상이 될 수 있다.
class Page:
page_lsn: int
# last update log of page
# 버퍼에 있는 페이지와 디스크 페이지의 정보가 달라질 수 있다.(dirty page)
data: bytes
- Active Transaction Table(ATT)
Active Transaction Table은 재시작 시점에서 충돌 시점에 실행 중(active)이던 트랜잭션의 목록을 저장한 테이블이다.
class ActiveTransactionTableEntry:
trans_id: int
# Transaction identifier
state: 'P' | 'U'
# 트랜잭션 상태. 2PC의 'P'=prepared, 'U'=unprepared
last_lsn: int
# 트랜잭션의 가장 마지막 로그 레코드
undo_nxt_lsn: int
# 롤백 과정에서 다음으로 undo 작업을 실행할 로그 레코드이다.
# 만약 last_lsn이 undoable이고 non-CLR일 경우 undo_nxt_lsn=last_lsn.
# 만약 last_lsn이 CLR 레코드일 경우 undo_nxt_lsn=prev_lsn of log[last_lsn]
- Dirty Page Table(DPT)
Dirty Page Table은 normal processing 과정에서 발생한 dirty buffer page에 대한 목록을 관리한다. ATT와 마찬가지로 재시작 시점에서 복구(redo)를 위해 사용한다. 보통 hash table을 통해 구현하거나 deferred writes queue 방식으로 구현한다고 한다.
class DirtyPageTableEntry:
page_id: int
# Page identifier
rec_lsn: int
# Recovery LSN. 페이지를 dirty하게 만드는(=최초로 변경하는) 로그를 기록한다.
# 페이지 변경 시점에 lsn of EoL로 설정되어 다음 로그가 쓰일 위치를 기록하는 셈이다.
# 이 때 rec_lsn의 관리는 버퍼 매니저에 의해 이루어진다.
Transaction Rollback
이제 normal operation 과정에서 롤백 과정을 살펴보자.
Pseudo Code
def rollback(
save_lsn,
# partial rollback checkpoint record
trans_id
# transaction identifier
):
undo_nxt_lsn = active_trans_table[trans_id].undo_nxt_lsn
# ATT 레코드의 undo_nxt_lsn은 트랜잭션의 다음 undo 작업을 저장한다.
# 이를 통해 rollback 과정에서 crash가 발생하여 재시작하는 시점에서
# 불필요한 undo 작업을 피할 수 있다.
while save_lsn < undo_nxt_lsn: # partaill rollback
log_record = log_read(undo_nxt_lsn)
# stable storage로부터 log를 읽어온다.
if log_record.type is 'update':
if undoable(log_record):
# log_record에 undo 관련 데이터가 들어있는가?
page = fix_and_latch(log_record.page_id, 'X')
# 페이지에 새로운 데이터를 작성하기 위해 X-latch를 획득한다.
# fix는 stable storage의 데이터를 버퍼에 캐싱한다는 의미이며,
# 버퍼 매니저는 내부적으로 fix와 unfix를 카운트하여
# 버퍼 페이지를 사용 중인 task의 개수를 체크한다.
undo_update(page, log_record)
# page undo
log_lsn = log_write(
type='compensation',
trans_id=trans_id,
prev_lsn=active_trans_table[trans_id].last_lsn,
# 트랜잭션의 마지막 로그를 prev_lsn으로 설정
page_lsn=log_record.page_id,
undo_nxt_lsn=log_record.prev_lsn,
# 현재 log_record는 이미 undo했기 때문에
# 이후 재시작 시점에서는 prev_lsn부터 시작해야 한다.
...
)
# 로그 쓰기 작업은 페이지 latch 구역 안에서 이루어져야 한다.
# 페이지 변경정보가 안전하게 복구되기 위해선 변경순서가
# 페이지 변경과 똑같은 순서로 이루어져야만 한다.
page.page_lsn = log_lsn
active_trans_table[trans_id].last_lsn = log_lsn
# page와 ATT의 최신 로그 정보를 CLR로 변경한다.
unfix_and_unlatch(page)
undo_nxt_lsn = log_record.prev_lsn
# 다음으로 복구할 로그
elif log_record.type is 'compensation':
undo_nxt_lsn = log_record.undo_nxt_lsn
# Compensation log record일 경우 무시하고 바로 다음으로 넘어간다.
# 이 때 log_record.prev_lsn이 아니라 log_record.undo_nxt_lsn을
# 설정하는 이유는 CLR이 역순으로 기록되기 때문이다.
# 즉, CLR.undo_nxt_lsn과 CLR 사이 모든 로그는 이미 undo되었음이 보장된다.
else:
undo_nxt_lsn = log_record.prev_lsn
# 기타 로그는 모두 무시하고 다음으로 넘어간다.
active_trans_table[trans_id].undo_nxt_lsn = undo_nxt_lsn
# 롤백 과정에서 crash가 일어날 경우 다시 시작하기 위해 기록해준다.
if save_lsn is 0:
# total rollback
log_write(
type='end',
trans_id=log_record.trans_id,
prev_lsn=active_trans_table[log_record_trans_id].last_lsn,
...
)
delete_active_trans_table(log_record.trans_id)
# 만약 모든 작업을 undo했을 경우 'end' 레코드를 작성
return
Partial Rollback
Aries의 롤백은 특별히 partial rollback을 지원한다.
partial rollback이란 것은 하나의 트랜잭션 안에 일종의 체크포인트(savepoint)를 저장하여, 부분 작업에 문제가 생길 경우 해당 체크포인트까지 partially rollback을 진행하고 다시 forward processing을 진행하는 것이다.
앞서 본 pseudo code를 보면 save_lsn을 통해 partial rollback을 위한 체크포인트를 명시해놨음을 알 수 있다. 체크포인트는 보통 사용자 레벨에서 설정된다.
partial rollback의 장점은 하나의 트랜잭션을 필요에 따라 좀 더 부분적으로 쪼갤 수 있다는 점이다. 이상적으론 트랜잭션이 Atomic하기 위해선 하나의 부분작업이라도 실패할 경우(더 이상 진행할 수 없을 경우) 모든 작업이 취소되어야만 한다.
하지만, 예를 들어 대규모 데이터에 대한 작업을 수행하던 중 일부 데이터에 문제(deadlock, integrity 등)가 생길 경우 total rollback을 수행하는 것보단 일부 데이터만 작업을 취소하고, 나머지 데이터는 그대로 작업을 성공하는 것이 더 효율적일 수 있다.
insert (data_1, ..., data_1000000) into database;
-- data_3 violates integrity constraint => fail 100,0000 records
insert (data_1, ..., data_1000000) into database;
-- success 99,9999 records, fail 1 records
- 혹은 여러 개의 부분작업을 다시 여러 개의 중첩된 트랜잭션으로 설계하여, 어떤 부분 작업이 실패할 경우 그 부분만 취소하고 다른 작업으로 진행해나가는 복잡한 설계도 가능하다.
START TRANSACTION;
INSERT (SOME_VALUE1, ...) INTO SOME_TABLE;
SAVEPOINT sp1;
UPDATE SOME_TABLE SET VAL = VAL + 300;
IF SOME_CONDITION THEN
ROLLBACK TO sp1;
UPDATE SOME_TABLE SET ...;
ELSE
SAVEPOINT sp2;
IF ...
...
COMMIT;
UndoNextLSN과 PrevLSN, 로그의 구조
앞서 계속 얘기해왔듯이 로그는 연속된 array이자 linked list이다. 이 때 물리적인 기록과 lsn을 통한 접근은 array의 성질을 이용하고, linked list로서 접근이 가능하도록 하는 것이 로그의 prev_lsn 필드이다.
{lsn=0x10, type='update', T1, 0, PAGE1, 0, 'INSERT x INTO table'},
...
{lsn=0x13, type='update', T1, 0x10, PAGE2, 0, 'UPDATE table SET 3 ...'},
// T1의 이전 로그는 0x10
...
{lsn=0x17, 'compensation', T1, 0x13, PAGE1, 0x10, 'DELETE FROM table WHERE value=x'},
// 이전 로그는 0x10이다. compensation log이므로 다음으로 undo해야 할 0x10을 저장
...
위에서 볼 수 있듯 하나의 트랜잭션에 의한 로그는 연속적이지 않을 수 있다. 그럼에도 트랜잭션은 정상적으로 복구가 가능한데, 이는 회복 기법과는 별개로 DBMS에서 Isolation을 보장해주기 때문이다. 즉, 레코드, 테이블 등 적절한 레벨의 lock을 통해 트랜잭션이 접근하는 영역이 보호되기 때문.
CLR을 정의하는 이유는
- CLR 그 자체로 데이터베이스의 상태변경(Log:X->Y, CLR:Y->X)이란 의미를 지니고 있거니와,
- Partial rollback 이후 혹은 rollback 진행 중 발생한 시스템 중단 이후 재시작 시점에 회복작업을 수행하며 반복적인 undo를 방지하여 오버헤드를 줄이고, Idempotency를 보장하기 위함이다.
- 또한 이후 얘기할 Redo Pass에서 CLR는 redo-only log로서 취급되는데,
- 이를 통해 undo 작업에서 디스크 출력 작업을 lazy하게 수행가능하기 때문에 batch 작업 등을 통해 I/O 작업량을 줄일 수 있고,
- Crash 시점에 데이터베이스의 상태를 완전히 재현하여 Undo Pass에서 트랜잭션의 세부적인 진행 상태를 신경쓰지 않도록 간단하게 만들어준다.
undo_nxt_lsn 필드는 일종의 linked list 제거 연산을 수행하는 역할을 한다. 앞서 얘기했듯, CLR은 original log의 inverse order로 대응되는데, 이 때 undo_nxt_lsn의 위치를 생각해보면, CLR.undo_nxt_lsn와 CLR 사이에 존재하는 모든 undo log는 무시해도 되는 레코드이기 때문이다.
Fuzzy Checkpoints
Checkpoint는 로그가 누적되어 Recovery를 위해 방대한 양의 로그를 스캔하는 것을 방지하기 위해 필요한 개념이다.
DBMS는 Checkpoint 로그 이전에 작성된 로그들이 이후 복구 작업에 필요하지 않은 상태를 보장한다.
이러한 목적 아래 checkpoint log 시점은 어떻게 관리해야 할까?
- 먼저 checkpoint log 시점에서 모든 트랜잭션이 안전하게 종료된 상태여야 한다.
Active transaction이 존재하는 상태로 checkpoint를 기록한 뒤, transaction이 아직 종료되지 않은 시점에서 재시작하는 시나리오가 있기 때문이다. - 또한, 모든 dirty page는 disk로 출력된 상태여야 한다. 만약 dirty page가 디스크에 아직 반영되지 않은 상태로 재시작 시점이 되면, 이 또한 checkpoint 이전의 로그를 스캔해야할 이유가 된다.
따라서 checkpoint log를 작성하는 시점은 모든 active transaction이 종료된 상태여야 하며 dirty page가 디스크로 출력된 상태여야 함을 알 수 있다. 마지막으로 active transaction이 계속해서 발생할 경우 영원히 checkpoint를 기록할 수 없는 경우가 생길 수 있으니, checkpoint 작업(필요한 정보를 수집하고, 로그를 기록하는 등)을 수행하는 동안 새로운 active transaction이 발생하지 못하도록 제한해야 한다.
def checkpoint():
off_trans_start()
# 새로운 트랜잭션의 시작 중단
wait('no_active_trans' & 'no_dirty_pages')
# 대기
log_write('chkpt', ...)
on_trans_start()
return
이러한 작업을 통해 이후 재시작 시점에서는 마지막 checkpoint로부터 안전하게 시작할 수 있지만, 긴 interruption이 발생할 수 있는 문제가 있다.
따라서 우리의 목표는 당연히 active transaction들의 종료(termination)과 dirty page의 flush를 대기하지 않고 체크포인트를 수행하는 것이다. 그리고 이러한 interruption을 최소화하기 위한 몇 가지 테크닉을 적용한 것이 Fuzzy Checkpoint이다.
앞서 생각해봤듯이 이러한 대기가 필연적이었던 이유는 로그 스캔의 범위를 명확히 특정하기 위해서이다.
Fuzzy Checkpoint는 어떻게 이런 문제를 해결했을까?
핵심은 약간의 사고 전환이다.
"체크포인트 시점부터 스캔하자" => "체크포인트 시점에 어디서부터(혹은 어디까지) 스캔해야하는지 기록하자"
Fuzzy checkpoint는 어디서부터 스캔해야하는지에 대한 정보를 추가적으로 기록한다.
이를 위해 Active Transaction Table과 Dirty Page Table을 checkpoint에 기록하는 것.
만약 재시작 시점에서 체크포인트를 통해 복구를 진행한다면, ATT의 last_lsn과 undo_nxt_lsn 필드, DPT의 rec_lsn 필드를 통해 undo 혹은 redo가 필요한 로그의 범위를 완전히 특정가능하다.
따라서 체크포인팅은 다음과 같이 진행할 수 있을 것이다.
def checkpoint(active_trans_table, dirty_page_table):
off_trans_update()
log_write('chkpt', active_trans_table, dirty_page_table, ...)
on_trans_update()
return
여기에 하나 더 추가적인 테크닉이 사용되는데 아예 무중단으로 체크포인트를 수행하는 방법에 대한 고민이다. 이번엔 checkpoint를 begin 시점과 end 시점으로 나누어 관련 정보를 수집하고 처리하는 동안 트랜잭션을 허용해보겠다는 것이다.
그러니까 좀 더 쉽게 생각하면,
"일단 이 시점을 기준(begin)으로 체크포인트를 수행할 건데, 여기에 필요한 정보(ATT, DPT)는 나중에(end) 더 알려줄게."정도로 해석할 수 있다.
이렇게 되면 begin 시점에 ATT와 DPT의 안전한 상태를 위한 S-latch 정도만 잠깐 걸고 아무런 중단 없이 체크포인트를 수행할 수 있기 때문에 runtime overhead를 크게 줄일 수 있다.
여기서 미완성된 체크포인트에 대해 생각해볼 수 있는데, end log를 작성하기 전에 시스템이 중단된 케이스이다. 이를 위해 stable storage에 따로 last_checkpoint_lsn이란 변수를 저장하는데, 이는 마지막으로 complete된 checkpoint를 저장하는 용도이다.
last_checkpoint_lsn의 업데이트는 모든 작업을 완료하고 end log까지 flush하면 이루어지기 때문에 언제나 DMBS가 안전한 체크포인트에 접근할 수 있게 된다.
def checkpoint(active_trans_table, dirty_page_table, master_addr):
att, dpt = None, None
acquire_latch_att('S')
acquire_latch_dpt('S')
# ATT, DPT를 읽기 위한 latch
copy(att, active_trans_table)
copy(dpt, dirty_page_table)
...
# 다른 작업이 있을 수 있다.
log_write('begin_chkpt', ...)
release_latch_dpt()
release_latch_att()
...
master_record = read_disk(master_addr)
lsn = log_write('end_chkpt', att, dpt, ...)
master_record.last_checkpoint_lsn = lsn
write_disk(master_addr, master_record)
# end record를 작성하고, last_checkpoint_lsn 업데이트
return
Restart Recovery
이제 시스템 중단 이후 재시작 시점에서 ARIES가 어떻게 데이터베이스의 상태를 안전하게 복구하는지 알아보자.
꽤 긴 글이지만, 찬찬히 살펴보면 ARIES가 얼마나 명료하고 간단한 방식으로 설계되었는지 느껴질 것이다.
재시작 후 복구 과정은
- 어떤 로그를 redo하고 undo할지 분석하는 Analysis Phase
- 중단 시점의 데이터베이스의 상태를 완전히 재현(repeat history)하는 Redo Phase
- 미완료된 트랜잭션들을 원상태로 복구하는 Undo Phase
로 구성된다.
이에 대한 Pseudo code는 다음과 같다.
def restart(master_addr):
(
active_trans_table,
dirty_page_table,
redo_lsn
) = restart_analysis(master_addr)
# master_addr로부터 마지막 체크포인트를 찾아 redo와 undo의 대상이 될 정보들을 찾아온다.
restart_redo(dirty_page_table, redo_lsn)
# redo_lsn로부터 순서대로 로그를 스캔하며
# redo가 필요한 로그들을 모두 작업한다.
# dirty_page_table은 버퍼매니저가 page를 flush하기 위해
# 필요한 정보이기 때문에 필요한 정보를 반영하는 식으로 진행
restart_undo(active_trans_table)
# 로그를 역순으로 진행하며 미완료된 트랜잭션들을 취소한다.
for transaction in active_trans_table:
if prepared(transaction):
acquire(transaction.lock)
checkpoint()
# 마지막으로 복구 완료시점에서 체크포인트 진행
return
Analysis Phase
def restart_analysis(master_addr):
active_trans_table = None
dirty_page_table = None
redo_lsn = None
master_record = read_disk(master_addr)
open_log_scan(master_record.last_checkpoint_lsn)
# master_addr을 통해 마지막 체크포인트(end_chkpt까지 완료된)를 불러온다.
log_record = next_log() # begin_chkpt 로그를 읽는다.
log_record = next_log() # begin_chkpt 이후 로그부터 읽기 시작
while not end_of_log():
if log_record.trans_id not in active_trans_table:
insert_active_trans_table(
trans_id=log_record.trans_id,
state='U',
last_lsn=log_record.lsn,
undo_nxt_lsn=log_record.prev_lsn
)
# ATT에 기록되지 않은 트랜잭션이 있다면, 삽입한다.
# undo_nxt_lsn을 log_record.lsn이 아닌 prev_lsn으로 설정하는 이유는
# 이후 작업에서 관련 처리를 하기 때문이다.
if log_record.type is ('update' | 'compensation'):
# undo 혹은 redo의 대상이 되는 로그 처리
active_trans_table[log_record.trans_id].last_lsn = log_record.lsn
if log_record.type is 'update' and undoable(log_record):
active_trans_table[log_record.trans_id].undo_nxt_lsn = log_record.lsn
# undo이자 redo 대상이 된다.
elif log_record.type is 'compensation':
active_trans_table[log_record.trans_id].undo_nxt_lsn = log_record.undo_nxt_lsn
# CLR은 redo의 대상으로 undo_nxt_lsn까지 모든 작업이
# Redo Phase에서 undo된다.
if redoable(log_record) and log_record.page_id not in dirty_page_table:
insert_dirty_page_table(log_record.page_id, log_record.lsn)
# DPT에 기록되지 않은 페이지가 변경되었기 때문에 기록한다.
# 미완료(unprepared) 롤백되어야 하는 트랜잭션이더라도 일단 기록하는데
# 이는 Redo Phase에서 중단 시점을 완전히 재현하기 위함이다.
elif log_record.type is 'begin_chkpt':
pass
# 미완료된 체크포인트의 begin 레코드이므로 무시한다.
elif log_record.type is 'end_chkpt':
# end_chkpt 시점에는 active_trans_table와 dirty_page_table을 기록한다.
# end_chkpt 로그까지 작성했으나 master_record를
# 업데이트하지 못한 시나리오의 경우 중복된 end_chkpt가 나올 수 있지만
# 문제 없는 걸 알 수 있다.
for (trans_id, state, last_lsn, undo_nxt_lsn) in log_record.active_trans_table:
if trans_id not in active_trans_table:
insert_active_trans_table(trans_id, state, last_lsn, undo_nxt_lsn)
# begin_chkpt 이후 로그를 기록하지 않았지만 완료되지 않은 트랜잭션들을 추가한다.
for (page_id, rec_lsn) in log_record.dirty_page_table:
if page_id not in dirty_page_table:
insert_dirty_page_table(page_id, rec_lsn)
else:
dirty_page_table[page_id].rec_lsn = rec_lsn
# dirty_page_table의 정보는 begin_chkpt 이전의 정보를 포함한다.
# 따라서 page를 최초로 변경한 로그(rec_lsn)는 dirty_page_table의 정보가 더 이전(=정확한)의 것이다.
elif log_record.type is ('prepare' | 'rollback'):
if log_record.type is 'prepare':
active_trans_table[log_record.trans_id].state = 'P'
else:
active_trans_table[log_record.trans_id].state = 'U'
active_trans_table[log_record.trans_id].last_lsn = log_record.lsn
elif log_record.type is ('end'):
delete_active_trans_table(log_record.trans_id)
log_record = next_log()
for (trans_id, state, last_lsn, undo_nxt_lsn) in active_trans_table:
if state is 'U' and undo_nxt_lsn is 0:
log_write('end', trans_id, ...)
delete_active_trans_table(trans_id)
# 만약 롤백을 위한 모든 작업을 완료했지만, 아직 ATT에서 제거되지 못한
# 트랜잭션은 이후 불필요한 작업들을 방지하기 위해 미리 제거해준다.
redo_lsn = min(rec_lsn for (page_id, rec_lsn) in dirty_page_table)
# redo를 실행할 최초 시점을 설정한다.
# dirty_page_table의 entry는 모두 redo 작업을 실행해야 할 페이지이기 때문에
# 모든 entry의 rec_lsn 중 가장 최초의 시점을 저장하는 것이다.
return active_trans_table, dirty_page_table, redo_lsn
Analysis Phase는 앞서 말한대로 redo와 undo에 필요한 정보를 분석하는 과정이다.
이 때 수집하는 정보는 어디서부터 redo를 실행할 것인지? dirty page가 최초로 변경된 시점, 실행 중이던 트랜잭션의 정보들이다.
Pseudo code를 살펴보다보면, end_chkpt 시점에 기록한 정보(rec_lsn 등)를 계속 변경(일종의 최신화?)할 수 있는 걸 알 수 있는데, 이는 end_chkpt 로그를 위한 정보를 construction한 시점부터 써지는 모든 로그가 end_chkpt에 반영되지 않기 때문이다. 이 때 end_chkpt를 stable storage에 쓰는 동안 발생하는 시간차가 문제가 아닐지 걱정되지만 문제가 없는 걸 알 수 있다.
Active transaction의 상태는 크게 P(prepared), U(unprepared)로 나눌 수 있다.
- Prepared 트랜잭션은 필요한 모든 작업을 마쳤기 때문에 다른 participants의 상태에 따라 Commit이 가능하다. Recovery 과정에 의한 롤백의 대상이 되진 않는다.
- Unprepared 트랜잭션의 경우 모두 롤백의 대상이 되는데, 이 때 모든 롤백 과정을 마쳤으나, end log가 작성되지 않은 경우가 있을 수 있다. pseudo code 마지막 부분을 보면 이런 경우 추가적인 redo와 undo가 필요하지 않기 때문에 오버헤드를 줄이기 위해 미리 end log를 작성해주는 것을 볼 수 있다.
Redo Phase
Redo Phase는 redo_lsn부터 순서대로 로그를 스캔하며 모든 redo log를 실행함으로써
- commit되었으나 dirty page가 디스크에 반영되지 않은 작업이 durable하게 적용되도록 보장함은 물론,
- uncommitted 변경사항을 모두 반영하여 중단 시점의 상황을 완전히 재현한다.
def restart_redo(dirty_page_table, redo_lsn):
open_log_scan(redo_lsn)
# redo_lsn부터 로그를 읽는다.
log_record = next_log() # read redo_lsn
while not end_of_log():
if (
log_record.type is ('update' | 'compensation')
and redoable(log_record)
and log_record.page_id in dirty_page_table # 불필요한 redo 작업을 방지
and log_record.lsn >= dirty_page_table[log_record.page_id].rec_lsn
# 모든 dirty page들을 통틀어 최초시점부터 시작하기 때문에
# 특정 페이지의 경우 이미 반영된 로그를 스캔할 수 있다.
):
page = fix_and_latch(log_record.page_id, 'X')
# 버퍼 페이지.
# 아직 버퍼에 적재되지 않아 디스크로부터 읽어오거나,
# 이미 버퍼에 적재되어 다른 로그에 의해 업데이트되어있을 수 있다.
if page.page_lsn =< log_record.lsn:
redo_update(page, log_record)
page.page_lsn = log_record.lsn
# 새로운 정보를 페이지에 반영한다.
else:
# 만약 중단 시점 이전에 로그가 이미 반영된 경우가 있을 수 있다.
dirty_page_table[log_record.page_id].rec_lsn = page.page_lsn + 1
# 이 경우 페이지에 반영된 이후의 로그만 적용하면 된다.
unfix_and_unlatch(page)
# 마찬가지로
log_record = next_log()
return
계속해서 반복하고 있듯이 Redo Phase에서는 in-complete transaction의 작업도 모두 redo를 진행한다. 이러한 작업을 진행하는 이유는 후술할 undo phase를 단순화하기 위함이다.
만약 in-complete transaction의 작업을 무시하고 Redo Phase를 진행한다면 어떻게될까?
Undo Phase에서는 in-complete transaction의 상태를 고려해야만 할 것이다.
즉, 어떤 시점까지 데이터베이스에 반영되었는지를 체크해야만 하며, CLR(물론, CLR 자체가 이러한 목적을 고려해서도 설계된 사항이긴 하겠지만..)이 어디까지 기록되었는지도 확인해야 한다.Redo Phase에서 병렬처리(parallelism)를 할 수 있는 부분이 있을까? Redo 작업 자체는 로그 순서대로 진행해야만 한다. 정답은 dirty pages이다. dirty_page_table의 entry가 되는 페이지는 결국 디스크로부터 읽어와야만 한다. 로그에 필요할 때마다 순서대로 불러오는 것보다 asynchronous I/O 작업을 통해 미리 불러오는 것이 전체 페이지를 더 빨리 로딩할 수 있고, redo 작업에 아무런 문제가 없음을 알 수 있다.
Undo Phase
이제 Undo Phase는 normal processing의 rollback과 거의 동일하다.
사실상 다중 롤백이나 마찬가지.
def restart_undo(active_trans_table):
while exists_unprepared_transaction(active_trans_table):
# at least 1 unprepared transaction(=in-complete transaction)
undo_lsn = max(
undo_nxt_lsn
for (trans_id, state, last_lsn, undo_nxt_lsn)
in active_trans_table
)
# 모든 active transaction의 undo record를 역순으로 undo
log_record = log_read(undo_lsn)
if log_record.type is 'update':
if undoable(log_record):
page = fix_and_latch(log_record.page_id, 'X')
undo_update(page, log_record)
log_lsn = log_write(
type='compensation',
trans_id=log_record.trans_id,
prev_lsn=trans_table[log_record.trans_id].last_lsn,
page_id=log_record.page_id,
undo_nxt_lsn=log_record.prev_lsn,
data=log_record.data
)
page.page_lsn = log_lsn
active_trans_table[log_record.trans_id] = log_lsn
active_trans_table[log_record.trans_id].undo_nxt_lsn = log_record.prev_lsn
if log_record.prev_lsn is 0:
log_write(
type='end',
trans_id=log_record.trans_id,
prev_lsn=active_trans_table[log_record_trans_id].last_lsn,
...
)
delete_active_trans_table(log_record.trans_id)
# 만약 모든 작업을 undo했을 경우 'end' 레코드를 작성하고
# 트랜잭션이 완전히 종료(active->rollback->terminated)된다.
elif log_record.type is 'compensation':
active_trans_table[log_record.trans_id].undo_nxt_lsn = log_record.undo_nxt_lsn
elif log_record.type is ('rollback' | 'prepare')
active_trans_table[log_record.trans_id].undo_nxt_lsn = log_record.prev_lsn
return
- Undo Phase에서 병렬처리를 할 수도 있을까? 각 트랜잭션의 Undoing 자체는 하나의 프로세스로 수행되어야 함을 알 수 있다. 정답은 Redo Phase와 비슷하다. 대신 이번엔 dirty page table이 아니라 로그 체인(Linked List)을 이용해야 한다. 목표는 필요한 페이지를 ansynchronous I/O 작업으로 미리 불러오는 것이다. 따라서 버퍼 페이지에 대한 undoing은 잠깐 미뤄두고, 먼저 필요한 CLR을 작성하는 처리를 한 다음, 필요한 페이지 목록을 미리 불러오는 것이 더 효율적일 것이다.
미디어 손실로부터의 복구
미디어 손실로부터 복구를 자세히 다루진 않겠다. 시스템 중단과 거의 비슷한 과정으로 복구를 진행하는데, 이 때는 체크포인트 대신 데이터베이스 전체에 대한 backup(dump)를 이용한다.