[ DB ] Chapter 19. Recovery System

1. Failure Classification

트랜잭션이 실패하는 이유는 여러가지가 있다.

• Transaction failure : 코드의 오류나 deadlock 같은 시스템 적인 오류로 인해 트랜잭션을 종료해야하는 경우
• System crash : 전원이 갑자기 나가거나 OS 오류 (비활성화 메모리의 내용이 손상되지 않았다고 가정)
• Disk failure : 디스크 오류나 손상

1.1 Recovery Algorithms

트랜잭션 수행시 트랜잭션에서 업데이트 되었던 정보와 원래 DB의 정보가 분리된 공간에 저장되어있어야 data inconsistency하게 recovery할 수 있다. recovery 알고리즘에는 두가지 파트가 있다.

1. 장애로부터 복구하기에 충분한 정보가 존재하는지 확인하기
2. 데이터베이스 내용을 원자성, 일관성, 내구성을 보장하게 복구하기

---

 

 

2. Storage

2.1 Data Access

 

disk에서 main menory로 이동시키는 것을 input, 메인메모리에서 disk로 이동시키는 것을 Output이라고 한다. 각 transaction Ti에는 access 및 update된 모든 data item의 local copies가 보관되는 private work-area가 있다. Ti의 local copy를 Xi라고 한다. system buffer block과 해당 private work-area 간 data item을 transfer하는 방법은 다음과 같다.

• read(X) : data item X의 값을 local variable Xi에 할당한다. buffer→value
• write(X) : buffer block의 data item X에 local variable Xi 값을 할당한다. value→buffer

트랜잭션은 X에 처음 access하기 전에 read(X)를 수행해야 한다. 이후에는 local copy에서 할 수 있다. 하지만 write(X)는 트랜잭션이 커밋되기 전에 언제든지 실행할 수 있고 local copy에 쓰여있다고해서 꼭 바로 output되지는 않는다.

 

 

---

 

3. Recovery and Atomicity

 

failure에도 불구하고 atomicity를 보장하기 위해, 먼저 데이터베이스 자체를 수정하지 않고 안정적인 스토리지에 업데이트 정보를 저장한다.

3.1 Shadow Paging

 

DB를 가르키는 포인터가 있다고 할때 이는 기본적으로 old하고 consisrency한 DB를 가르키도 있는다. 그리고 기존 DB를 copy한 shdadow page를 만들어 업데이트되는 정보는 모두 여기다가 저장해준다. 포인터는 기존 DB만을 가르키도 있어 DB는 이렇게 만들어지고 저장되는지도 모르고 있는다. 모듬 업데잍 연산이 마치면 포인터를 새로 만들었던 shadow page로 옮겨준다.

이는 간단하고 이해하기 쉽지만 DB 전체를 매번 copy 할 수는 없고, 그걸 page 단위로 업데이트를 하며 관리해줘야 한다.

 

트랜잭션이 진행되는 동안 current page table과 shadow page table의 두 page table 상태를 유지하는 방안이 제시되었다. 하나는 내가 수정하면서 쓸 table, 하나는 consistency 상태를 유지하며 복구를 하기 위해 갖고 있는 table이다. shadow page table을 비휘발성 스토리지에 저장하여, 트랜잭션 실행 전 데이터베이스 상태를 복구할 수 있다. 실행 중에는 shadow page table이 수정되지 않는다. 우선 두 page table이 identical하다. current page table만 트랜잭션 실행 중 data item access에 사용된다. page가 처음 write될 때마다 이 page의 copy본은 사용하지 않는 page에 만들어진다. 그런 다음 모든 업데이트가 종료되면 current page table이 copy본을 가리키도록 한다.

commit이 된다면 다음과같은 과정을 거친다.

1. 메인메모리의 수정된 page를 모두 디스크로 flush한다.
2. 현재 수정된 정보를 갖고 있는 current page table을 디스크로 기록한다.
3. 다음과 같이 current page table을 새 shadow page table로 만든다.

shadow page table에 대한 포인터가 작성되면 트랜잭션이 커밋된다. 이는 쓰기량이 많긴 하지만 crash 발생 후에는 recovery가 필요하지 않아 간편하다. 새 트랜잭션은 shadow page table을 사용하여 바로 시작할 수 있다.

 

3.2 Log-Based Recovery

log는 일련의 log record이다. 이는 DB의 log란 DB에 문제가 생겼을 때 복구하기 위해 보기 위해 존재한다. log는 안정적인 스토리지에 보관되어 데이터베이스의 업데이트 활동에 대한 정보를 유지한다.

transaction Ti가 시작되면, <Ti start > log record를 write 함으로써 스스로 기록한다. Ti가 write(X)를 실행하기 전 log record <Ti, X, V1, V2>가 write되고, 여기서 V1은 old value, V2는 X에 write할 새로운 value이다. Ti가 마지막 statement를 마치면, log record <Ti commit>이 write된다.

log-based에서는 마지막 commit record가 안정적인 sotorage로 output될 때 commit되었다고 말한다. 그 이전의 log는 이미 ouput되어있어야한다.

로그를 사용하는데에는 두가지 접근방식이 존재한다.

• Immediate database modification
  • DB의 수정을 바로 하는 것. 버퍼에 바로 쓰겠다
• Deferred database modification.
  • 버퍼에 최대한 기록하지 않고 local variable에 기록하다가 넣겠다

Immediate database modification

이를 사용하면 트랜잭션이 커밋되기 전에 버퍼나 디스크 자체에 커밋되지 않은 트랜잭션을 업데이트할 수 있다. 데이터베이스 item을 write하기 전에 log record를 디스크에 write해야 한다. log가 완전히 기록된 후에 item을 write 해야 한다.

이 log를 가지고 어느 정도의 순서를 보장할 수 있다. 이는 트랜잭션 커밋 전에도 후에도 트랜잭션에 의해 업데이트된 내용이 disk에 ouput 될 수 있다. 블록이 output되는 순서는 블록이 write되는 순서와 다를 수 있다.

 

이 예시는 T1이 커밋 되지 않았는데도 C의 block이 output되었다. 하지만 C에 값이 저장되기 전에 log가 기록되었기 때문에 T1이 커밋 직전에 트랜잭션을 종료시켰다고 해도 T0 커밋 직후에 기록된 log를 쭉 읽어보며 C를 복구할 수 있다.

 

Deferred database modification.

이는 트랜잭션 커밋 시에만 버퍼/디스크 업데이트를 수행한다. 모든 수정에 대한 log는 disk에 기록하지만 실제 업데이트된 데이터는 commit된 시점에 진행한다. 이에 이는 트랜잭션이 commit에 실패하면 log를 보며 redo 하면되기 때문에 recovery를 단순화 하였다. 그러나 locol copy본을 저장하는 오버헤드가 존재한다.

log-based scheme에 vs shadow-paging

shadow-paging 의 장점

• log record를 writing하는 데에 드는 overhead 없음

log-based scheme에 대한 shadow-paging의 이점

• recovery가 trivial함

shadow-paging 의 단점

• 전체 page table을 copy하는 게 비싼 연산임
• 커밋 오버헤드가 높다. (업데이트된 모든 page 및 page table을 flush 해야 한다. )
• data가 조각화된다. (관련 page가 디스크에서 분리될 수도 있다)
• 트랜잭션이 완료될 때마다 기존 page를 garbage collected해야한다 (오버헤드)
• 동시 트랜션을 허용하기 힘들다.

 

3.3 Concurrency Control and Recovery

모든 concurrent taransaction들은 단일 디스크 버퍼와 단일 log를 공유한다. 버퍼는 모든 트랜잭션의 업데이트 된 내용을 가지고 있다. lock을 사용하여 트랜잭션이 한 데이터를 수정한 경우 commit하기 전까지 다른 트랜잭션이 그 데이터를 수정할 수 없다고 가정한다.

Using the Log to Redo and Undo Transactions

• undo(Ti)
  • Ti에 대한 마지막 log record에서 역방향으로 Ti에 의해 업데이트된 모든 data item의 값을 old value로 복원한다.
  • 이전 값으로 복원될때마다 특수 log record <Ti, X, V>가 write. V는 복원된 값
  • 트랜잭션의 undo가 완료되면 log record <Ti abort>가 write된다.
• redo(Ti) :
  • Ti에 대한 첫 번째 log record에서 앞으로 나아가 Ti에 의해 업데이트된 모든 data item의 값을 new value으로 설정한다.

트랜잭션이 중간에 실패했다면 일단 < Ti start>를 보고 트랜잭션의 시작지점을 찾는다. 그 후 < Ti commit> or < Ti abort> 있나 확인한다. 둘다 없다면 이는 정상적으로 종료된 것이 아니기 때문에 undo 해줘야한다. 하지만 있다면 commit은 되었지만 아직 disk에 저장되지 못했을 수도 있기 때문에 log를 읽으며 disk에 저장된 값이랑 같은지 확인해야한다.

 

 

• (a) : 중간에 중단되었기 때문에 T0의 내용을 undo 해줘야한다.
• (b) : T0은 comit 되었지만 T1은 commit되지 못했다. T0가 디스크에 잘 저장되어있는지 보장이 되지 않기 때문에 redo해줘야하고, T1는 정상종료되지 못했기 떄문에 undo 해줘야한다.
• (c) : T0와 T1 모두 정상 commit이 되었지만 disk에 적혀있는지는 확신할 수 없기 때문에 둘다 redo 해준다.

commit이 된 트랜잭션은 redo해주고 비정상 종료된 트랜잭션은 undo 해준다. 하지만 이는 정상적으로 잘 기록된 트랜잭션도 다시 redo해 줄 수 있어 오버헤드가 발생한다. 이에 repeating history를 체크할 수 있다. 이는 recovery를 단순화 하지만 오버헤드 또한 가지고 있다.

 

 

3.4 Checkpoint

log에 기록된 모든 트랜잭션을 redo하고 undo하는 것은 많은 오버헤드를 갖는다. 시스템이 오래 실행된 경우에는 이를 처리하는데 오랜시간이 걸릴 것이다. 이에 대한 해결방안으로는 checkpoint가 있다. 이는 정기적으로 checkpointing 하여 recovery 절차를 간소화한다. checkpoint의 과정은 다음과같다.

1. 현재 메인메모리에 있는 모든 로드 레코드를 disk에 저장
2. 수정된 데이터들은 모두 disk에 저장
3. <checkpoint  L>이라는 로그를 dosk에 저장

이 과정을 수행하는 동안 모든 updating은 stop된다. 이 과정이 끝난 뒤에는 가장 최근의checkpoint 이후의 트랜잭션만 고려하면 된다. 이 시점 이전에 commit되거나 중단된 트랜잭션은 이미 모든 업데이트가 disk에 저장되었기 때문에 그 이후만 redo 혹은 undo해주면 된다. 하지만 undo하기 위해 checkpoint 이전의 log가 일부 필요할 수도 있기 때문에 checkpoint 시점으로부터 위로 올라가면서 한 트랜잭션이 시작하는 지점을 찾는다.

 

위 그림과 같은 상황이라고 했을 떄, T1과 T2의 일부는 disk에 저장되었음을 보장한다. 그렇기 떄문에 T1은 고려하지 않고 T2는 일부만 보장하기 때문에 고려해줘야한다. 이에 T2와 T3는 redo를 실행해 복구해주고 T4는 트랜잭션이 종료되기 전에 실행종료 되었으므로 undo를 실행해준다. 그 이후에는 T3이 종료한 시점으로 돌아가게 된다.