[DB] Recovery 로깅 방식

로깅 방식

로그는 stable storage 에 존재

작업을 성공적으로 마친 뒤 반드시 로그를 write 함

 

로그

<Ti start> : 트랜잭션 Ti 가 시작

<Ti, X, V1, V2> : 트랜잭션 Ti 가 X 값을 V1에서 V2 로 write

<Ti commit> : 트랜잭션 Ti 가 commit

 

여러 트랜잭션이 동시에 실행되더라도 모든 트랜잭션은 하나의 디스크 버퍼와 로그를 공유함

앞으로는 Strict two-phase 기법을 기준으로 설명함 : Read 를 할 때 해당 정보는 commit 이 된 상태임을 보장

 

Checkpoint

트랜잭션의 로그를 남겨 Backward 방식으로 리커버리(Undo)하는 것은 좋으나 그 범위가 너무 큼

이 문제를 해결하기 위해 체크포인트 개념 도입

checkpoint 이후의 statement 만 redo 함

<checkpoint L> : L = 현재 active 상태인 트랜잭션의 리스트

Recovery 과정 예시

T1 은 이미 commit 된 상태이므로 제외

T2, T3 : Redo : 로그에 따라 재실행하며 disk 에 저장함 (checkpoint 이후에 commit 된 적이 있으므로)

T4 : Undo : rollback 으로, 아예 실행된 적이 없는 것처럼 되돌림

 

Recovery 과정

• undo-list 와 redo-list 생성
• 로그를 Backward 스캔
• <Ti commit> 발견 시 Ti 를 redo-list 에 추가
• <Ti start> 발견했는데 Ti 가 redo-list 에 없으면 undo-list 에 추가 (failure 발생 전에 commit 된 적이 없으므로 미실시 처리하는 것임)
• <checkpoint L> 발견시 스캔 종료
• L 중에서 redo-list 에 없는 것들은 다 undo-list 에 추가 (active 상태로, 트랜잭션이 commit 된 것은 아니나 checkpoint 이후에 어떠한 명령어도 등장하지 않아 backward scan 에서 처리되지 못한 케이스)
• undo-list 는 backward 로 돌면서 이전값으로 되돌림
• redo-list 는 forward로 돌면서 명령어를 재실행하고, 디스크에 저장함

Steal vs Force

• Force : commit 된 순간에 버퍼에 있던 해당 페이지들을 강제 디스크에 저장
• Not-force : 트랜잭션이 커밋되어도 저장하지 않음(Redo 필요) 
• Steal : 트랜잭션이 커밋되지 않았지만 디스크에 저장(Undo 필요)
• Not-Steal : 트랜잭션이 커밋되지 않았으면 디스크에 저장하지 않음

주로 Steal + Not-force 조합을 사용함

 

로그 기반 리커버리 (Repeating History)

로그 레코드는 stable storage 에 저장하기 전에 메인 메모리에 먼저 저장함

나중에 블럭 단위로 모아서 한 번에 stable storage 에 저장함

• 한 블럭이 로그로 가득 찬 경우 저장
• 또는 Log force 연산으로 강제 저장
• commit 이 로그 레코드에 쓰인 순간 disk 에 write
  Force 정책인 데이터베이스는 commit 을 만나면 바로 디스크에 저장해야하는데 WAL 정책에 의해 로그도 저장됨

Group commit : 로그 write 또한 비용이 크므로 비용을 낮추기 위해 하나의 블럭에 몰아넣고 한 번에 저장하는 방법

로깅 규칙

• 로그 레코드는 반드시 생성된 순서대로 저장되어야함 -> undo, redo 를 위함
• 트랜잭션 Ti가 commit 되면 반드시 <Ti commit> 로그를 stable storage 에 저장
• WAL(Write-Ahead Logging) 준수 : 데이터 블럭이 디스크에 저장되기 전에 로그가 먼저 디스크에 저장

리커버리 알고리즘

• 로그를 backward 로 돌면서 수행
• <Ti, X, V1, V2> 와 같이 update 로그를 만나면 <Ti, X, V1> 로그를 남기고 X에 V1 write
• 롤백 작업을 마치면 <Ti abort> 로그를 남기고 종료

Two-phase recovery

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

• 마지막 <checkpoint L> 을 찾고, L 을 모두 undo-list 에 넣음
• 이후 로그를 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 로 스캔
• undo-list 의 모든 트랜잭션에 대해서 <Ti start> 만날때까지 순회
• <Ti, X, V1, V2> 를 만나면 X에 V1 를 write(Undo) -> <Ti, X, V1> 로그 남김
• <Ti start> 만나면 <Ti abort> 로그 남김

<Ti abort> 같은걸 남기는 이유는 롤백 도중 에러가 발생한 경우 재시작될 때 제대로 처리되는 것을 보장하기 위함

왜냐하면 undo-list 에서 처리되던 트랜잭션도 <Ti abort> 를 남기고 실패처리되면 그 다음 재시작될 때는 redo-list 에서 처리되므로 <Ti, X, V1> 같은 로그가 없으면 복구가 제대로 되지 않음

 

그림이 좀 이상한데 11번까지 실행되고 crash 가 난 경우임

Fuzzy checkpoint

리커버리 시 체크포인트 이후만 관리할 수 있도록 보장하기 위한 기법

checkpoint 호출 시 처리 방법

• 일시적으로 모든 트랜잭션의 update를 중단시킴
• <checkpoint L> 로그 레코드를 남기고 force log 를 수행 (로그 블럭을 stable stoarge 에 저장, WAL)
• 변경된 데이터 블럭을 리스트와 시킴 (리스트 M)
• 일시적으로 멈춰두었던 트랜잭션의 액션들을 재개
• 리스트 M의 모든 블럭을 디스크에 저장함

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

 

리커버리 알고리즘이 fuzzy checkpoint 기법을 사용한다면 stable storage 에서 last_checkpoint 를 관리함

즉 리커버리가 될 때 로그를 순회하면서 마지막 체크포인트를 찾아다니는 것이 아닌 last_checkpoint 로 찾아가 바로 forward scanning 수행

 

Failure of Nonvolatile storage

disk 에러를 방지하기 위해 덤프를 사용

<dump> 로그를 남김 -> 다른 disk 에 DB를 복사 -> 복구 요청 -> dump DB를 복사 -> <dump> 로그 이후의 로그를 redo