[Database] DBA급 개발자로 - #20 Database Recovery

이전 포스팅에서는 DBMS의 정책(steal, force policy)에 따라 데이터를 디스크에 어느 시점에 저장하는지와 WAL에 대해 간단히 살펴봤습니다. 이번 포스팅에서는 로그를 활용해서, 특히 WAL(Write Ahead Log)를 활용해서 어떻게 복구를 수행하는지 살펴보겠습니다. 

WAL(Write Ahead Log) 

WAL 기록 방법 

우선 WAL을 활용한 데이터베이스에서는 변경사항이 어떻게 기입되는지 살펴보겠습니다. WAL에는 다음과 같은 로그를 추가합니다. 

• 새로운 트랜잭션이 시작되면 WAL에 <BEGIN> 로그를 기입합니다.
• 트랜잭션이 종료되면 <COMMIT> 로그를 기입합니다. 
• WAL에 기입된 각각의 로그는 transaction Id, Object Id, 이전 값과 변경 이후의 값을 포함합니다. 

A의 값이 1이고 B의 값이 2일 때 트랜잭션 T1이 A와 B의 값을 수정할 때 WAL에 로그는 다음과 같이 기입됩니다. 

WAL에 로그가 기입되는 방식

그럼 WAL는 어느 시점에 디스크로 플러시 될까요? 매 트랜잭션마다 디스크로 플러시 하면 좋겠지만 트랜잭션이 많은 경우 플러시 과정이 병목이 될 수 있습니다. 이를 해결하기 위해 매 트랜잭션 커밋 시점이 아닌 커밋된 여러 트랜잭션을 묶어서 한 번에 디스크로 플러시 하는 group commit 기능이 존재합니다.

Logging Methods 

WAL에 기입하는 로그의 유형에 따라 physical, logical 그리고 physiological로 분류할 수 있습니다. 

• Physical logging: 특정 데이터가 어떻게 변했는지, 이전 값과 이후의 값을 기록하는 방식입니다. 
• Logical logging: 데이터 변경을 발생시킨 명령을 기록합니다. 예를 들어 "UPDATE table SET name = 'seonwoo'"와 같은 로그를 기록합니다. 
• Physiological logging: Physical logging과 Logical logging을 적절히 조합한 방식입니다. 

Checkpoint

WAL의 데이터가 디스크로 플러시 되면 WAL에 <CHECKPOINT> 로그를 추가하게 됩니다. <CHECKPOINT> 이전에 <COMMIT> 기록이 있는 트랜잭션의 변경사항은 디스크에 모두 반영됐음을 보장할 수 있습니다. 따라서 복구 과정에서 <CHECKPOINT> 시점 이후에 <COMMIT> 된 트랜잭션 또는 진행 중인 트랜잭션만 고려하면 됩니다.

WAL Checkpoint

Log Types 

WAL에 저장되는 로그의 유형을 더 자세히 살펴보겠습니다.

• Begin: 트랜잭션 시작 시점에 추가되는 레코드입니다. 
• Update: 특정 페이지가 수정되는 경우 udpate 레코드가 로그에 추가됩니다. 
• Commit: 트랜잭션의 commit 시점에 메모리에서 관리하던 레코드를 영구 저장소로 플러시 합니다. 
• Abort: 트랜잭션 abort시 추가되는 레코드입니다. 
• End: 트랜잭션이 commit 또는 abort 이후 트랜잭션이 완료됐음을 표시하기 위한 레코드입니다. 
• CLR: Compensation Log Record의 약자로 undo 과정에서 추가되는 레코드입니다. 
• Checkpoint: Checkpoint시 추가되는 레코드입니다. 

각각의 로그에는 어떤 정보가 담기는지 살펴보겠습니다. 

• 모든 로그 유형에서 사용하는 공통 필드 
  • LSN(Log Sequence Number): 로그를 식별하기 위한 number
  • prevLSN: 해당 트랜잭션에 의해 생성된 로그 중 바로 직전에 생성된 로그의 LSN   
  • transID: transaction ID 
  • type: 로그 레코드의 타입 
• Update 로그 레코드에서만 사용하는 필드 
  • pageID: 수정된 disk page의 ID 
  • length
  • offset
  • before-image: 변경 전의 값 
  • after-image: 변경 후 값 

LSN (Log Sequence Number) 

다음으로는 데이터베이스 복구에 필요한 정보와 자료구조(transaction table, dirty page table)에 대해 살펴보겠습니다.  

• Transaction table: 시스템 crash 당시 active transaction 정보를 저장하는 메모리 상의 자료구조 
• Dirty page table: 시스템 crash 당시 dirty 상태의 페이지를 기록하는 메모리 상의 자료구조 

데이터의 저장 위치

트랜잭션의 유형별 작업 

다음으로는 트랜잭션의 유형에 따라 어떤 작업이 수행되는지 살펴보겠습니다 

 

Create, Update 등 일반적인 트랜잭션의 작업 유형 

1. Max(LSN) + 1의 LSN을 가진 로그 레코드를 생성합니다. 해당 로그 레코드의 prevLSN은 트랜잭션 테이블에서 관련된 트랜잭션을 찾고, 해당 트랜잭션의 lastLSN 값을 가져옵니다.

$$ newLSN\,=\,++Max(LSN) $$
$$ prevLSN\,=\,transactionTable[transID].lastLSN $$

 

2.  트랜잭션 테이블에서 관련된 트랜잭션의 lastLSN을 새로 생성된 로그의 LSN으로 업데이트합니다.

$$ transactionTable[transID].lastLSN\,=\,newLSN $$

 

3. 해당 페이지가 더티 페이지 테이블에 없으면 더티 페이티 테이블에 페이지를 추가하고 recLSN값을 새로 추가된 로그 레코드의 LSN으로 지정합니다.

$$ if\,(!dirtyPage.contains(page))\,{\,recLSN\,=\,newLSN\,}$$

 

Commit 

1. Commit 레코드를 로그에 추가합니다.
2. 해당 트랜잭션 커밋 시점에 추가한 Commit 레코드 지점까지 디스크로 플러시 합니다.
3. Transaction table에서 해당 트랜잭션 entry를 제거합니다.
4. End 레코드를 로그에 추가합니다. 

Checkpoint

1. begin_checkpoint: 체크포인트가 시작되는 시점에 추가됩니다.
2. end_checkpoint: begin_checkpoint 시점의 transaction table과 dirty page table을 포함합니다. 

ARIES

다음으로는 대표적인 데이터베이스 복구 알고리즘에 대해 살펴보겠습니다. ARIES는 Algorithms for Recovery and Isolation Exploiting Semantics의 약자이며 IBM에 의해 발명된 알고리즘입니다. ARIES의 핵심 개념은 다음과 같습니다. 

• Write Ahead Logging: 변경사항이 디스크에 반영되기 전에 반드시 로그(영구 저장소)에 기록돼야 합니다.  
• Repeating history during redo: 데이터베이스를 재시작하면 로그를 적절히 읽어 이전의 상태를 복구합니다. 
• Logging changes during undo: Undo 과정에서 로그를 남김으로써 반복되는 실패 상황(복구과정에서 서버가 반복적으로 다운되는 경우)에서 동일한 undo 작업을 중복 실행하지 않도록 방지합니다. 

동작 원리 

다음으로는 ARIES가 어떻게 동작하는지 살펴보겠습니다. 

1. Analysis 단계
   • 시스템 crash 시점의 transaction table과 dirty page table을 생성합니다. 
   • Redo가 시작돼야 하는 로그의 위치를 결정합니다. 
2. Redo 단계 
   • (분석 단계에서 결정된) Redo가 시작돼야 하는 로그의 위치부터 로그가 끝날 때까지 redo를 수행합니다. 
   • Dirty page table에서 가장 작은 recLSN부터 redo를 진행합니다. Redo와 관련된 레코드를 제외한 모든 변경사항을 다시 적용합니다.  
3. Undo 단계 
   • 로그를 역순으로 읽으면서 시스템 붕괴 시점에 진행 중이었던 트랜잭션(트랜잭션 테이블에 entry가 존재하는 트랜잭션)의 변경사항을 undo 합니다. 
   • 시스템 crash 시점에서 active 상태였던 트랜잭션의 가장 오래된 LSN까지 undo를 진행합니다. 
   • Undo 과정에서는 CLR 레코드가 추가됩니다. 만약 시스템 crash가 다시 발생하는 경우, CLR을 다시 적용할 수는 있지만 CLR에 undo를 수행하지는 않습니다. 

마무리 

이번 포스팅을 통해 데이터베이스의 복구 알고리즘에 대해 살펴봤습니다. 복구에 필요한 정보가 많고 알고리즘이 복잡해서 처음에 이해하는 게 쉽지 않았지만 꾸준히 복습하다 보니 차근차근 이해가 된 것 같습니다. 다음 포스팅에서는 분산 환경에서 데이터베이스가 어떻게 동작하는지 살펴보겠습니다. 

Reference 

https://courses.cs.washington.edu/courses/cse444/11wi/lectures/lecture11-12.pdf

https://15445.courses.cs.cmu.edu/fall2021/slides/20-recovery.pdf