Log Based Recovery Mechanism

Log 란 sequence of log records. log records는 트랜잭션의 데이터베이스 시스템에서 활동 정보를 기록한다.

• 트랜잭션 T가 시작했을 때
  <T start>
• 트랜잭션 T가 write(X)를 실행하기 전,
  <T, X, V old , V new >
• 트랜잭션 T가 마지막 instructuon을 끝냈을 때
  <T commit >

(이 때 로그에 commit이 있다고 실제로 commit이 확정된 것은 아님. log buffer에 log record가 있으면 해당 로그는 어떠한 오류로 날라갈 수 있기 때문에, stable한 곳에 저장되어야 완전히 commit 된 것으로 간주함.)

Immediate Database Modification

Immediate Database Modification은 트랜잭션이 데이터베이스에서 수행하는 모든 변경 작업을 즉시 데이터베이스에 반영하는 방식입니다. 이 방식에서는 트랜잭션의 각 단계마다 데이터베이스의 상태가 실시간으로 변경됩니다. 따라서, 트랜잭션이 커밋되기 전까지 변경된 데이터는 다른 트랜잭션에 의해 읽을 수 있습니다. 보통 데이터베이스 시스템에서 사용하는 방식.

• 아직 commit 되지 않은 트랜잭션의 update가 buffer 혹은 disk에 기록될 수 있음. 그렇기 때문에 데이터 베이스 시스템에 update가 되기 전에 log record가 먼저 기록되어야함.
  (일단 여기서는 log record가 바로 바로 stable storage에 기록된다고 가정)
• update된 block의 output 되는 순서는 응용에서 write된 순서와 다를 수 있음.

Deferred Database Modification

Deferred Modification은 트랜잭션이 완료될 때까지 변경된 데이터를 데이터베이스에 반영하지 않는 방식입니다. 트랜잭션이 실행되는 동안 변경 작업은 임시로 메모리나 임시 영역에 기록되며, 트랜잭션이 커밋되면 변경 사항이 한 번에 데이터베이스에 반영됩니다. 따라서, 다른 트랜잭션들은 해당 트랜잭션이 커밋되기 전까지 변경된 데이터를 읽을 수 없습니다.

• 복구 관점에서는 간단하지만, 응용에서 임시로 작업 내용을 기록해서 가지고 있어야 하기 때문에 메모리 사용 측면에서 performance가 떨어짐.

Undo Operation

트랜잭션 T의 마지막 log record에서부터 backwards로 확인하면서 T가 update한 모든 데이터의 값을 old value로 다시 되돌려 놓는 작업.

• 트랜잭션 T가 X를 old value V로 다시 write함
  <T, X, V >

• undo가 완료 되었을 때
  <T abort>

• failure가 발생했을 때 트랜잭션 T에 대해서 <T start > 는 있지만 <T commit > 혹은 <T abort > record는 없다면 해당 트랜잭션은 undo 대상.

• faulure 직전에 stable storage로 output 되었을 수도 있기 때문

Redo Operation

트랜잭션 T의 처음 log record에서부터 forwards로 확인하면서 T가 update한 모든 데이터의 값을 다시 new value로 set하는 작업.

• failure가 발생했을 때 트랜잭션 T에 대해서 <T start > 있고 <T commit > 혹은 <T abort > record가 있다면 해당 트랜잭션은 redo 대상.
• failure 직전에 stable storage에 output 안 되었을 수도 있기 때문

Checkpoint

Checkpoint는 데이터베이스 시스템의 상태를 정기적으로 기록하는 지점을 의미합니다. 모든 트랜잭션의 log record를 redo, undo 하는 것은 복구 시스템을 비효율적으로 만듭니다. 따라서 checkpoint를 설정하여 복구 시스템을 효율적으로 동작하게 할 수 있습니다.

• 로그 관리: Checkpoint는 로그 파일의 크기를 관리하고, 로그 파일의 꽉 찬 부분을 비워주는 역할을 합니다. Checkpoint 시점에서 이전에 완료된 트랜잭션들의 로그 기록은 더 이상 필요하지 않으므로 로그 파일을 재사용할 수 있도록 만들어줍니다.

• 데이터베이스 복구: Checkpoint는 데이터베이스 복구 과정에서 중요한 역할을 합니다. 데이터베이스 시스템은 Checkpoint 이후에 발생한 변경 작업만 로그에서 복구하면 됩니다. Checkpoint를 기준으로 이전에 완료된 트랜잭션들은 이미 데이터베이스에 반영되었으므로, 이를 다시 복구할 필요가 없습니다.

• 성능 개선: Checkpoint는 데이터베이스 시스템의 성능을 향상시킬 수 있습니다. 주기적인 Checkpoint는 로그 파일의 크기를 관리하고, 디스크 I/O 작업을 최적화하여 시스템의 성능을 향상시킵니다. 또한, 복구 작업 시에도 Checkpoint를 기준으로 한정된 범위의 로그를 처리하므로, 복구 시간을 단축시킬 수 있습니다.

1. checkpoint를 설정할 때는 모든 update를 멈춘다.
2. main memory에 있는 모든 log record를 stable storage로 output한다.
3. main memory에 있는 수정된 block을 disk로 output한다.
4. <checkpoint L> log record를 stable storage에 쓴다.
   L: checkpoint 중 active한 트랜잭션 리스트.
   

T1은 Checkpoint이전에 완료되었기 때문에 복구 대상에서 제외
T2,T3 는 Redo 대상
T4,T5 는 Undo 대상

Recovery Algorithm

failure 발생시 Recovery 과정은 크게 두 가지 과정으로 나뉩니다. 첫 번째는 Redo Phase , 두 번째는 Undo Phase입니다. Redo Phase에는 모든 트랜잭션의 update를 replay합니다. (repeating history)그리고 Undo Phase에는 incomplete한 트랜잭션들은 undo 합니다.

Redo Phase

1. 가장 최근에 작성한 <checkpoint L > record를 찾는다. 그리고 undo 리스트를 L로 초기화합니다.

2. <checkpoint L> 부터 forward로 스캔을 시작합니다

   1. <T, X, V Old, V New > or < T, X, V old > 를 찾으면 해당 log reord를 redo합니다.
   2. <T start > 를 찾으면 , undo list에 해당 트랜잭션을 추가합니다.
   3. <T commit > or <T abort >를 찾으면 해당 트랜잭션을 undo 리스트에서 제거합니다.

Undo Phase

1. log record를 backward로 스캔을 시작합니다.
   1. <T, X, V old, V new > 를 찾고 , T가 undo 리스트에 있으면
      1. X에 V old를 다시 write 합니다.
      2. <T, X, V old> log record를 write합니다.
   2. <T start>를 찾고, T가 undo 리스트에 있으면
      1. log record를 write하고 T를 undo 리스트에서 제거합니다.
2. undo 리스트가 empty가 되면 Undo Phase를 종료합니다. ( undo 리스트에 있는 모든 트랜잭션의 start log record를 만날 때까지)

Log Record Buffering

Log Record Buffering은 데이터베이스 시스템에서 로그 기록의 효율성과 성능을 개선하기 위해 사용되는 기법입니다. log record를 바로 바로 stable storage에 기록할 수도 있지만 그렇게 되면 memory와 disk간 IO가 많아져 성능이 떨어지게 됩니다. 따라서 main memory에 log buffer를 두어 log record를 buffer에 쓰고 buffer가 모두 차면 log를 stable storage에 저장합니다.

• log buffer에 있는 log record는 생성된 시간 순서대로 stable storage에 output 됩니다.
• 트랜잭션 T는 log record가 stable storage에 output 되야만 commit 상태가 됩니다.
• data X가 output 될 때 X와 관련된 log record를 먼저 stable storage로 output 해야합니다. (Write-ahead-logging)

DataBase - Buffering

데이터베이스는 인메모리 버퍼를 유지하여 데이터 블록을 관리합니다.
• 새로운 블록이 필요한 경우, 버퍼가 가득 찬 경우 기존의 블록을 버퍼에서 제거해야 합니다.
• 제거할 블록이 업데이트된 경우, 해당 블록은 디스크로 출력되어야 합니다.

복구 알고리즘은no-force 정책을 지원합니다. 즉, 트랜잭션이 커밋될 때 업데이트된 블록을 디스크에 기록할 필요가 없습니다.
• force 정책: 업데이트된 블록을 커밋할 때 디스크에 기록해야 합니다.
더 많은 비용 소모
복구 알고리즘이 steal 정책을 지원합니다. 즉, 커밋되지 않은 트랜잭션의 업데이트가 포함된 블록은 트랜잭션이 커밋되기 전에도 디스크에 기록될 수 있습니다.

No-Force 정책

No-Force 정책은 트랜잭션이 커밋될 때 업데이트된 블록을 강제로 디스크에 기록할 필요가 없는 정책입니다. 즉, 트랜잭션의 커밋 시점에서 해당 트랜잭션이 변경한 블록들을 디스크로 출력하지 않아도 됩니다. 이는 디스크 I/O 작업을 줄이고 성능을 향상시키는 장점을 가지고 있습니다. 그러나 데이터베이스 시스템이 중단되었을 때 복구 과정에서 커밋되지 않은 트랜잭션에 대한 변경 내용을 재수정해야 할 수 있습니다.(redo 해야 할 수 있다)

Steal 정책

Steal 정책은 커밋되지 않은 트랜잭션의 업데이트가 포함된 블록을 디스크에 기록할 수 있는 정책입니다. 즉, 트랜잭션이 커밋되기 전에도 해당 트랜잭션의 변경 내용이 디스크에 기록될 수 있습니다. 이를 통해 메모리 버퍼를 비워서 다른 트랜잭션에게 필요한 공간을 제공할 수 있습니다. Steal 정책은 버퍼가 가득 찬 상태에서 새로운 블록을 로드해야 할 때 사용됩니다. 그러나 데이터베이스 시스템이 중단되었을 때 복구 과정에서 커밋되지 않은 트랜잭션에 대한 변경 내용을 롤백해야 할 수 있습니다.(undo 해야 할 수 있다.)