[Recovery]Log-based recovery

log recored는 우선 buffer에 저장을 하게 된다. 적절한 시점이 되면 storage에 있는 log db에 저장하게 된다. 이 때 disk io단위는 block이고 log도 블락 단위로 저장이 된다. 버퍼가 꽉 차면 디스크에 써야하고 log force라면 commit시 저장을 하게 된다.  

 

비용을 줄이기 위해 가급적 log 버퍼를 블락만큼 채워서 디스크에 써야 할 것이다. 

 

로그 기록은 생성된 순서대로 저장이 되어야 한다.

Ti가 commit state가 되려면 <Ti commit>이 log db에 저장되어야 한다.

 

 

Logging

트랜잭션이 정상적으로 수행될 떄 기록되는 로그를 살펴보자.

 

Logging(during normal operation)

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

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

<Ti commit> : commit 될 때 

 

Ti 을 롤백 명령을 하는 경우 (during normal operation)

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

<Ti start>

<Ti, Xj, V1, V2>

rollback 시점

 

rollback 시점으로 부터 백워드 스캐닝을 하면 처음 로그로 <Ti, Xj, V1, V2>을 만난다. Xj를 V1로 바꾸고 <Ti, Xj,V1,V2> 의 짝으로 <Ti, Xj, V1>를 log db에 남긴다. 이 로그 레코드를 compensation log record라고 한다.  compensation log는 이후에 살펴볼 redo에 필요하게 된다.

<Ti start>를 만나면 백워드 스캐닝을 멈추고 <Ti abort>를 로그레코드에 남긴다.

정리하면 rollback을 하면 스캐닝을 백워드로 진행. <Ti Xj Vx, Vy>로그를 만나면 Xj를 Vx로 바꾸고 log에 <Ti,Xj Vx> 추가. <Ti start>를 만나면 <Ti abort>를 추가하고 백워드스캐닝 종료.

 

따라서 위의 <Ti start> <Ti, Xj, V1, V2> 을 하고 롤백하면 다음과 같은 로그로 바뀐다.

<Ti start>

<Ti, Xj, V1, V2>

<Ti, Xj, V1>

<Ti abort>

 

만약 트랜잭션 하나가 더 추가되면 어떻게 될까?

<Ti start>

<Ti, Xj, V1, V2>

<Ti, Xj, V2, V3>

 

이렇게 되면 백워드 스캐닝을 하면서 앞서 설명한 규칙을 따른다. <Ti, Xj, V2, V3>을 가장 먼저 만나므로 Xj를 V2로 바꾸고 compensation log <Ti Xj V2>가 먼저 생성된다. 다음으로 <Ti, Xj, V1, V2>를 만나면 Xj를 V1으로 바꾸고 compensation log인 <Ti Xj V1>이 기록된다. <Ti start>에 대하여 <Ti abort> 가 기록되고 스캐닝이 종료된다.

백워드 스캐닝 결과는 다음과 같다.

<Ti start>

<Ti, Xj, V1, V2>

<Ti, Xj, V2, V3>

<Ti Xj V2>

<Ti Xj V1>

<Ti abort>

 

이것을 가지고 알고리즘을 진행한다. 핵심은 백워드 스캐닝을 하면서 로그를 순서상 뒤쪽에 추가하는 것이다. 로그의 순서도 신경써야 한다.

 

two phase recovery algorithm

redo phase: commited, aborted, imcomplete 트랜잭션은 모두 redo한다.

undo phase: incomplete 트랜잭션은 모두 undo한다.

 

redo phase에서 commited, aborted 트랜잭션은 정상적으로 수행됬기 때문에 redo하는 것이 당연하다. 하지만 incomplete는 redo하지만 정상적으로 수행되지 않았기 때문에 undo 해야한다.

 

redo phase

<checkpoint L>을 기준으로 포워드 스캐닝을 하면서 undo-list와 redo-list를 만든다.

undo-list는 L을 보고 만든다. L은 commit 당시에 commit되지 않은 트랜잭션이기 때문에 undo의 대상이 되는 것이다. checkpoint 시점 이후에 로그 레코드를 포워드 스캐닝을 하면서 <Ti, Xj, V1, V2>를 보면서 Xj를 V2로 write하여 redo 작업을 한다. 

<Ti start>를 보면 undo-list에 Ti를 넣는다. 즉 checkpoint 이후에 시작한 트랜잭션은 undo-list에 들어간다. 이후 Ti에 대해 <Ti commit>이나 <Ti abort>가 발견되면 undo-list에서 Ti를 뺸다.

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

 

undo phase

redo phase에서 구한 undo-list를 사용한다.

failure 시점 기준으로 백워드 스캐닝을 하면서 <Ti, Xj, V1, V2>가 undo-list에 있다면 Xj를 V1으로 write한다. 이 작업을 하고 <Ti, Xj, V1>을 로그 레코드를 추가해야 한다.

스캐닝 중 <Ti start> 를 만나면 undo-list에서 지우고 <Ti abort>를 로그 레코드에 추가한다. 

 

 

undo phase에서 compensation log를 안 남기면 어떻게 될까? 

<Ti start> <Ti Xj V1 V2> 트랜잭션이 있는 부분을 복구한다고 해보자. 그러면 redo undo에 의해

<Ti start>

<Ti Xj V1 V2>

<Ti Xj V1>

<Ti abort>

와 같은 로그가 남을 것이다. 근데 compensation log를 안 남기면

<Ti start>

<Ti Xj V1 V2>

<Ti abort>

이런 로그가 남게 된다.

 

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

redo phase에서는 Xj를 V2로 바꾸게 된다. <Ti abort>를 만나게 되면 undo-list에서 빠지게 된다. undo phase에서 undo-list가 없기 때문에 아무것도 하지 않는다.

 하지만 정상적인 상황은 checkpoint 이후에 Ti가 시작되었기 때문에 Xj가 V1으로 바뀌어야 복구가 잘 된 것으로 볼 수 있다. 하지만, compensation log를 남기지 않아 Xj가 V2로 바뀌는 것으로 복구되었다.

compensation log를 남기면 어떻게 될까?

<Ti start>

<Ti Xj V1 V2>

<Ti Xj V1>

<Ti abort>

이렇게 되면 redo phase에서 <Ti Xj V1 V2>에 의해 Xj가 V2로 바뀌지만 <Ti Xj V1> 로그 레코드를 통해 V1으로 다시 바꿔준다. undo phase에서 Ti 트랜잭션이 없다고 하더라도 정상적인 복구의 결과가 된다. 

 

이 알고리즘의 핵심은 redo하면서 업데이트하고 undo에서는 incomplete한 트랜잭션을 처리하는 것이다.

 

 

redo pahse

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 가 어디선가 롤백 되었다는 것을 파악한다. crash 발생 전에 정상적인 롤백이 이루어졌음을 알 수 있다. 이것을 통해 old value로 업데이트하게 된다. B를 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. 

8. A를 500으로 write

7. T2 start만났으므로 undo-list에서 뺀다. undo-list가 비어있으므로 undo를 완료한다.

 

12,13,14는 undo phase의 11,8,7에서 생성된 log record이다.