Log-Based Recovery

Log Block Buffering

log recored는 우선 메인 메모리의 buffer에 저장을 하며, 적절한 시점이 되면 storage에 있는 log db에 저장하게 된다.

버퍼에 있는 로그 기록이 가득 찼거나, log force 연산이 실행될 때 stable storage 로 이동한다.

Log Force 는 commit 을 할 때 stable storage에 쓴다.

 

Group commit : log 버퍼를 블락만큼 채워서 한 번의 output 연산으로 디스크에 쓰면 I/O 비용을 줄일 수 있을 것이다.

 

 

 

Logging rule

• 로그 레코드는 반드시 생성된 순서대로 저장되어야한다. -> undo, redo 를 위함
• 트랜잭션 Ti가 commit state가 되려면 <Ti, commit> 이 먼저 log db에 저장되어야 한다.
• write-ahead logging (WAL) : 메인 메모리 내의 데이터 블록이 데이터베이스 (비휘발성 storage내에)에 output 될 수 있기 전에, 해당 블록의 데이터와 관련된 모든 로그 레코드가 stable storage에 output되어야 한다.                 
• -> data block 을 디스크에 쓰기 전에, 로그를 먼저 저장해야 한다. (엄격하게 말하면 WAL 은 로그 내의 undo 정보가 stable storage로 output 될 것을 요구하는 것이다.)

 

A Recovery Algorithm

Logging(during normal operation)

<Ti start> : 트랜잭션이 시작될 때

<Ti, Xj, V1, V2> : 업데이트가 될 때

<Ti commit> : commit 될 때 

 

Transaction rollback (during normal operation)

Ti 는 roll back 해야 하는 트랜잭션이다.

정상적인 롤백 명령을 할 때 생성되는 로그이다.

rollback 시점으로 부터 backwards scan 을 하다가 <Ti, Xj, V1, V2> 를 만나게 된다.

이때 Xj 에 V1 을 쓰는 undo 작업을 진행한다.
그리고 <Ti, Xj, v1> 이라는 로그 기록을 작성한다.
-> 이러한 로그 기록을 compensation log record 라고 한다.

<Ti start>를 만나면 backwards scan 을 멈추고, <Ti abort> 로그 레코드를 남기게 된다.

 

 

two phase recovery algorithm

-> 이 알고리즘은 모든 트랜잭션에 대해서 update를 수행하기 때문에 redo-list 없이 undo-list만 만들어 낸다.

Redo phase : committed, aborted, incomplete 상태의 모든 트랜잭션에 대해 수행한다.

• 마지막 <checkpoint L> 을 찾고, L 을 모두 undo-list 에 넣는다.
• 이후 위의 <checkpoint L> 부터 로그를 Forward로 스캔한다.
• 그러다가 <Ti, X, V1, V2> 를 만나면 X에 V2 를 write한다. (Redo)
• 만약 <Ti start> 를 만난다면 Ti 를 undo-list 에 넣음
• <Ti commit> 또는 <Ti abort> 를 만나면 Ti 를 undo-list 로부터 삭제한다.

Undo phase : incomplete 상태의 트랜잭션에 대해 수행한다.

• 로그 끝에서부터 Backward 로 스캔한다.
• 만약 <Ti, X, V1, V2> 를 만난다면 X에 V1 를 write(Undo) 한다. 그리고 <Ti, X, V1> 로그 를 남긴다.
• 이는 undo-list 의 모든 트랜잭션 Ti 에 대해서 <Ti, start>를 만날때까지 계속한다. 그리고 <Ti, start> 를 만난다면 <Ti, abort> 로그 기록을 남기며, Ti 를 undo-list 로부터 제거한다.
• undo-list 가 empty 할 때까지 계속한다.

위 과정의 undo phase에서 compensation log 가 필요한 이유는 무엇일까?

<Ti start> <Ti Xj V1 V2> 을 복구한다고 해보자.

원래는 <Ti Xj V1 V2> <Ti Xj V1> <Ti abort>와 같은 로그가 남을 것이다.

 

compensation log를 안 남기면 <Ti Xj V1 V2> <Ti abort> 이런 로그가 남을 것이다.

복구 도중 undo phase 진행 중에 failure가 또 발생했다고 하자. 그러면 다시 복구를 진행하게 된다.

redo phase에서는 Xj를 V2로 바꾸게 되고, <Ti abort>를 만나게 되면 undo-list에서 제거하기 때문에 undo phase 는 더 이상 진행되지 않을 것이다. 

그러나 Ti 는 checkpoint 이후에 시작되어씩 때문에 V1 으로 복구가 되어야 한다. 그러나 compensation log 를 남기지 않으면 Xj 가 V2 로 바뀌게 된다.

 

compensation log를 남긴다면? redo phase에서 Xj가 V2로 바뀌지만 <Ti Xj V1> 로그 레코드를 통해 다시 Xj 가 V1 으로 바뀌게 된다. 

 

 

 

redo phase

4. checkpoint에서 시작하고 undo-list={T0, T1}로 시작한다.

5. C을 600으로 write한다. 

6. T1을 undo-list에서 제거한다 -> undo-list={T0}

7. T2를 undo-list에 삽입한다. undo-list={T0,T2} 

8. A에 400을 write한다.

9. T0 가 어디선가 rollback 되었다는 것을 알 수 있다. 즉, crash 발생 전에 정상적인 롤백이 이루어졌음을 알 수 있다. 따라서 B를 old value 인 1900으로 write한다.

10. T0는 정상적으로 수행된 트랜잭션이므로 undo-list에서 뺀다. undo-list={T2}

11. C에 300을 write한다.

->undo-list={T2}

 

undo phase

11. T2가 undo-list에 있으므로 C를 600으로 write한다. -> 12 의 <T2, C, 600> 로그를 기록한다.

8. A를 500으로 write한다. -> 13의 <T2, A, 500> 로그를 기록한다.

7. T2 를 undo-list에서 뺀다. undo-list가 비어있으므로 undo phase를 완료한다. -> 14의 <T2, abort> 로그를 기록한다.

 

 

Fuzzy Checkpointing

checkpoint를 할 때 실행 중인 모든 트랜잭션을 중지하고 디스크에 버퍼의 값을 저장하게 된다.

이 때 트랜잭션을 중지하지 않고 checkpoint를 만드는 방법이 Fuzzy checkpointing이다.

• 일시적으로 모든 트랜잭션의 update를 중단시킨다.
• <checkpoint L> log 레코드를 기록하고, force log 를 수행한다. (로그 블럭을 stable stoarge 에 저장, WAL)
• 업데이트된 buffer block 에 대해서 리스트 M을 만든다. -> dirty block 리스트
• 일시적으로 멈춰두었던 트랜잭션들을 재개한다.
• 리스트 M의 모든 블럭을 디스크에 저장한다. output 되는 동안 buffer block 이 업데이트 되면 안된다. -> latch 사용 / WAL 규칙을 만족해야 한다.
• 가장 마지막에 수행한 checkpoint에 대한 포인터 last_checkpoint 를 방금 수행한 로그 레코드로 업데이트한다. 

이로서 checkpoint 이전의 모든 행위들은 디스크에 저장된 것이므로 이후의 과정에 대해서만 리커버리할 수 있음

 

recovery algorithm 이 fuzzy checkpoint 기법을 사용한다면 stable storage 에서 last_checkpoint 를 관리한다.

즉, recovery가 될 때 로그를 순회하면서 마지막 체크포인트를 탐색하는 것이 아니라, last_checkpoint 로 찾아가 바로 forward scanning 수행할 수 있게 된다.

 

Failure of Nonvolatile storage

non-volatile 저장장치 (disk) 의 손실을 방지하기 위해 dump를 사용한다.

데이터베이스의 전체 내용을 주기적으로 stable storage 에 dump 한다.

- 메인메모리에 있는 모든 로그 기록을 stable storage 로 output 한다.
- 모든 buffer block 을 디스크에 output 한다.
- 데이터베이스의 내용을 stable storage 에 copy한다.
- <dump> 로그를 stable storage 로 output 한다.