23. Database Recovery

서울대학교 데이터사이언스대학원 정형수 교수님의 "데이터사이언스 응용을 위한 빅데이터 및 지식 관리 시스템" 강의를 필기한 내용입니다.

• 목차

ARIES §

• 일단 가정은 WAL 을 사용하고 STEAL, NO FORCE 정책이다.
• 여기서의 핵심 아이디어는
  • 일단 전부 REDO 해서 (Repeating History) crash 바로 직전까지 복구해 Durability 를 보장한다.
  • 근데 crash 직전에 돌고 있던 txn 들은 restart 시에 다시 돌아갈 리가 없기 때문에 전부 abort 된거라고 생각해서 얘네들을 UNDO 하면서 Atomicity 를 보장한다.
  • 이때, UNDO 에 대한 log 도 남기며 UNDO fail 이 일어나도 이전에 UNDO 한 것들을 반복하지 않게 한다.

Log Sequence Number: LSN §

• 각 log 는 globally growing sequence number 를 받고 이걸 LSN 이라고 부른다.
  • 근데 even 하게 증가하지는 않는다: 단 하나의 무한정 증가하는 log 파일에 log 가 append only 로 저장된다고 가정하고 이때의 offset 이 LSN 이 된다.
  • 따라서 log message 가 크면 증가폭이 클 수도 있다.
• 근데 이 값을 어떻게 활용하는지가 중요하다.
  • PageLSN: Page 를 변경한 마지막 LSN 을 말한다.
    • 즉, 이건 page 를 변경할때마다 update 된다.
  • RecLSN (RecoveryLSN, FirstLSN): Page 가 flush 된 이후 처음으로 변경한 operation 의 log LSN
  • FlushLSN: Memory 에 저장하는, disk 에 flush 한 가장 최신의 LSN 을 말한다.
    • 즉, 이건 log 를 flush 할 때마다 존재한다.
    • 이건 WAL protocol 을 위해 존재한다.
    • 만약에 buffer page 에 적힌 PageLSN 이 100 인데 flushLSN 이 50이라면 아직 저 page 를 바꾼 log 가 flush 되지 않았다는 의미이다.
    • 따라서 PageLSN > FlushLSN 이면 우선 log flush 를 하고 page flush 를 해서 WAL 을 준수한다.
    • 만약에 flush 된 pageLSN 이 더 높다면 crash 시에 이놈을 UNDO 할 방법이 없다.
      • 가령 disk 로 내려간 page 의 pageLSN 이 100 이고 flushLSN 이 50 인 상황에서 crash 가 나버리면 recovery 시에 이놈을 UNDO 하기 위해서 100 번 LSN 이 필요한데 이놈이 flush 되기 전데 crash 가 났으므로 UNDO 를 못한다.
      • 따라서 atomicity 가 위배된다.
    • 즉, 이 번호까지는 AD 가 위배되어도 복구가 가능하다는 의미이다.

Transaction COMMIT Procedure §

• Txn COMMIT 할때는 다음처럼 작동한다:

1. Commit log 를 생성하고
2. 해당 commit log 의 LSN 까지 flush 한다.

3. FlushLSN 을 이 LSN 으로 고쳐준다.
4. 다음에 commit 된다.

5. 마지막으로 TXN-END 라는 log 를 생성한 뒤에 log buffer 를 비워준다.
   • 이건 아마 commit 과정에 문제가 생길 때를 위함이니라.
   • 근데 이건 바로 flush 될 필요가 없다.

• 참고로 log buffer 와 log file 은 circular buffer 로 관리되며 반복적으로 재활용한다.

Transaction ABORT Procedure §

• Txn ABORT 는 ARIES 에서의 UNDO 와 동일하게 작동하되, 해당 txn 에 대한 것만 건든다.
• 따라서 각 log 에는 PrevLSN 이라는 것이 있어서 하나의 txn 에 대한 이전 log 를 linked list 로 따라갈 수 있게 한다.
• ARIES 에서의 UNDO 와 동일하게 작동한다는 것은, UNDO 에 대한 log 도 같이 생성된다는 것이다.
  • 이걸 Compensation Log Record (CLR) 이라고 하고, 아래 에서 더 다뤄보도록 하자.
• 그래서 과정에 대해 간단하게 말하면,
  1. ABORT log 를 생성한다.
  2. 각 log 를 UNDO 하며, CLR 을 생성한다.
  3. UNDO 가 종료된 다음에는, TXN-END 로 txn 이 끝났다는 log 를 생성한다.

여기부터는 2024-12-09 내용

옮겨진 section: CLR

Recovery §

• DB 가 start 되자마자 첫번째로 실행하는 recovery 절차에 대해 알아보자.

• 크게 세 phase 로 나뉜다: (1) Analysis, (2) REDO, (3) UNDO

1: Analysis Phase §

• 여기에서는 Checkpoint 를 읽고, Checkpoint ~ 마지막 WAL 까지 쭉 훎으면서:
• 어떤놈이 crash 시점에 uncommitted 였는지 (즉, UNDO 가 필요한 애들 - Loser 라고 부른다.), committed 였는지 (즉, REDO 가 필요한 애들 - Winner 라고 부른다.) 검사한다.
  • 원래는 checkpoint 부터 sequential scan 하는데, optimize 되어 있어서 거의 바로 알아낼 수 있다고 한다.

2: REDO Phase §

• 우선 REDO log 를 쭉 훑으며 전부 반영하는 작업을 한다.
• 그럼 crash 나기 직전의 상태로 복구되게 되고, 따라서 D 는 만족되는 상태가 된다.

3: UNDO Phase §

• 근데 uncommit txn 이 작업한 것도 같이 반영되게 되는데, 이 txn 들은 다시 살아나지 못하기 때문에 A 를 위해서 얘네들을 다시 되돌리는 것을 UNDO phase 에서 한다.
  • 위에서 말한대로, UNDO 를 할때는 CLR 을 생성해서 UNDO 를 반복하지 않게 한다.
• 그럼 이때 어떤 txn 들이 uncommitted 인지 (loser 인지) 알아야 하는데, 이건 맨 처음의 analysis phase 에서 이미 알아냈다.

Recovery Scenario §

• 기본적인 상황은 위와 같다.
  • Txn 5개가 돌고 있고, $t_1$, $t_3$, 그리고 $t_4$ 는 COMMIT 되었다.
  • 첫번째 crash 뒤에 REDO 가 끝나고 UNDO 가 시작된 다음 두번째 crash 가 났다.

Before 1st Crash: Normal Case §

• 이게 첫번째 crash 가 나기 전의 log 이다.
  • 왼쪽부터 LSN+Log, buffer pool page, disk page, log buffer, disk log 순서로 상태가 표시되어 있다.
• 이것으로 normal case scenario 를 생각해 보자.
• 일단 각 write 는 log buffer 에다만 log 를 생성하면서 진행된다.
• 그리고 9 번에서 COMMIT 하는 것을 보면 모든 log 가 disk log 로 내려가는 것을 볼 수 있다.
  • 이것이 WAL 을 위한 것이다.
  • 즉, D 가 깨질 것 같으니 log 를 전부 다 disk 로 내려보낸 것.
  • 좀 더 구체적으로 말하면, FlushLSN 이 0일테고, page buffer 에의 PageLSN 은 9일테니 9까지 flush 를 하고 FlushLSN 을 9 로 update 해주게 된다.
• 10번에서는 manual 하게 $d$ 를 flush 한 것인데, 이때는 더 이상 flush 할 log 가 없으므로 log flush 는 skip 한다.
  • 참고: flush log 는 LSN 은 발급되지만 이놈은 log flush 되지는 않는듯하다.
• 14, 15 번도 동일하다. 14번에서는 COMMIT 이 되어 log 들이 전부 flush 되고, 15번에서는 manual 하게 flush 하지만 flush 할 log 가 없는 상황.
• 19번의 flush 는 좀 다르다. 여기서도 manual 하게 page buffer 를 flush 하지만, 이때는 flush 할 log 가 있으므로 page buffer 가 flush 되며 A 가 깨질 것 같으니 남은 log 를 전부 flush 하는 것.

After 1st Crash §

• 이것이 첫번째 crash 에서의 recovery 과정이다.
  • 여기서의 첫번째 column 이 log 가 아니라 recovery action 이라는 것 외에는 위와 동일하다.
• 그리고 analysis phase 결과 loser 는 $t_2$, $t_5$ 가 된다.
• 여기서 저 consider-redo(6) 에 주목하자.
  • Log 를 보면 6번은 $write(b,t_3)$ 이다. 근데 19번을 보면 $flush(b)$ 로 $b$ 를 flush 해주고 있다.
  • 따라서 19번에서 해당 page 의 PageLSN 은 19 로 적혀서 disk 에 반영되었을 것이다.
  • 이에 6번을 REDO 할때, disk 에서 읽어온 page 도 PageLSN 이 19 로 되어 있을 것이고 이것은 6보다 큰 것이기에 해당 operation 은 이미 disk 에 반영이 되어 있다고 판단해 consider-redo action 을 취하게 된다.
• REDO 중간중간에 flush 를 하는 것을 볼 수 있는데, 여기에는 특별한 규칙은 없는듯 하다.
• REDO 이후에 UNDO 가 시작된다. Disk 에 저장된 마지막 update log 는 18번이므로 여기서부터 시작한다.
• 그래서 18, 17, 13 을 UNDO 하며 CLR 을 생성하고 있는 것을 볼 수 있다.
  • 주목할 것은 이 예시에서는 UndoNext 는 적어주지 않고 있는 것을 볼 수 있다.
  • 이에 의한 효과는 아래의 2nd crash 에서 살펴보자.
• 그리고 한번 manual 하게 flush 를 하는데, 이때는 A 를 위해 log 들이 flush 된다.
  • 따라서 22, 23 번이 내려간다.
• UNDO 가 완료된 txn 은 rollback log 를 남겨서 해당 txn 은 더 이상 loser 가 아님을 알려준다.
  • 근데 이 예제에서는 rollback log 가 flush 되지 않았고, 따라서 두번째 recovery 에서는 이 rollback log 를 볼 수 없으므로 해당 txn 은 여전히 loser 이다.
  • 만일 이 rollback log 가 flush 되었다면 다음 recovery 가 발생한다면 여기에서는 loser 에서 제외된다.

After 2nd Crash §

• 이건 두번째 crash 에서의 recovery 이다.
• 여기서 주목할 것은:
• 일단 저 consider-redo(22) 와 redo(23) 이다.
  • UNDO 도중에 crash 가 난다면 새로운 REDO 에서는 이 compensate log 까지 다 한다.
  • REDO 는 가장 최신까지의 모든 log 를 다 하기 때문.
• 그리고 저 consider-redo(13) 이다. 이놈은 첫번째 recovery 에서는 redo(13) 이었는데 왜 이제는 consider-redo 가 된것일까?
  • 그건 첫번째 recovery 에서 $flush(a)$ 로 한번 flush 했기 때문이다.
  • 따라서 자연스레 PageLSN 이 커져 두번째 recovery 에서는 무시되는 것.
• 그리고 26번을 보면 23번을 UNDO 하고 있는 것을 볼 수 있다.
  • 이건 큰 문제다. 왜냐면 23번은 17번에 대한 UNDO 였기 때문에, 23번을 UNDO 한다는 것은 17 번을 두번 UNDO 하는 것이어서 A 가 깨지는 상태가 되기 때문이다.
  • 이것은 27번에서도 마찬가지이다.
  • 이것을 위해 UndoNext 가 필요하다는 것을 알 수 있다. UndoNext 로 아직 UNDO 하지 않은 REDO 를 UNDO 하러 가야 하기 때문이다.
• 참고로,
  • REDO 시에 어떤 log 에 대해 나중에 compensate log 가 있으면 이 log 는 REDO 하지 않는다.
  • REDO 시에 어떤 txn 에 대한 rollback log 가 있으면 이 txn 에 대한 log 도 REDO 하지 않는다.

Using UndoNext §

• 그래서 UndoNext 를 사용하게 하면, 첫번째 recovery 는 다음처럼 된다.
  • 18번을 UNDO 한 다음에는, 이놈이 $t_5$ 의 log 였기 때문에 이놈의 PrevLSN 인 13번이 UndoNext 로 적혀있는 것을 볼 수 있다.
  • 만약 UndoNext 에 적을게 없다면, nil 을 적는다.

• 따라서 두번째 recovery 에서는 바로 13번을 UNDO 하며 CLR 을 생성하고 있는 것을 확인할 수 있다.

• 이렇게 CLR 와 UndoNext 로 빠르게 UNDO 를 끝낼 수 있을 뿐 아니라 UNDO 를 UNDO 하는 바보짓도 안하게 된다.

Recovery Considerations and Optimization §

• 만약 Analysis phase 에서 crash 가 나면 어떡할까?
  • 어쩔 수 없이 다시 처음부터 한다.
• 만약 REDO phase 에서 crash 가 나면 어떡할까?
  • 이때도 어쩔 수 없이 다시 처음부터 한다.
• 어떻게 하면 REDO 를 빠르게 할 수 있을까?
  • Crash 가 다시 안날 것이라고 가정하고, background worker 로 change 를 async 하게 flush 한다.
• 어떻게 하면 recovery 를 더 빠르게 해서 client connection 을 일찍 받을 수 있을까?
  • 원래는 UNDO phase 까지 되면 tcp connection 을 받는게 정통이지만 요즘은 REDO phase 까지만 되어도 tcp connection 을 맺는다.