3. Recovery(복구)

3.1. 장애 및 복구

DBMS가 처리하는 장애는 3가지가 있음.

1) Transaction Failure

: 트랜잭션 자체의 내부 논리 오류, 사용자의 명시적인 요구, 시스템 내부 결정에 의하여 발생 가능.

ex) deadlock -> victim이 abort됨.

 

2) System Failure(=Crash)

: 휘발성 기억 장치인 메인 메모리에 문제가 발생하여 내용이 사라지는 것.

ex) 정전, OS 오류, HW 결함

 

3) Disk Failure

: HW 및 SW 결함으로 인해 디스크 내용이 사라지는 현상.

장애는 언제 어디서든 다양한 형태로 발생할 수 있기에 시스템은 트랜잭션의 ACID성질 지원을 위해 복구 기법이 필요함.

Recovery Algorithms

: 복구 알고리즘은 DB의 일치성(C)과 트랜잭션의 원자성(a), 지속성(d)을 보장하기 위한 기술임.

 -> 두가지 파트로 구성되는데...

1) 정상 상태에서 시스템 복구를 대비하기 위한 연산

2) 장애 발생 시 복구를 위한 연산

=> 이 둘은 밀접한 관계가 있음 ∴ 서로 연관 지어서 분석해야 함.

 

Storage

1) Volatile storage(휘발성 저장장치)

: 시스템의 파워가 나갔을 때 내용이 사라지는 저장장치

ex) 메인 메모리, 캐시 메모리

 

2) Non-Volatile storage(비휘발성 저장장치)

: 시스템의 파워가 나가도 내용이 안 사라지는 저장장치

ex) 디스크, 테이프, 플래시 메모리, RAM

 

3) Stable storage(안정 저장 장치)

: 어떤 장애가 발생해도 데이터는 살아남는 장치

-> 이론적일 뿐 실질적으론 존재 불가능.

 

안정 저장 장치 구현

: 기본적으로 동일 블록을 중복적으로 저장 및 관리하는 방식을 사용함. 중복 장소(second block)에 동일 블록 쓰기 연산이 성공적으로 종료 시 쓰기 연산이 완료된 것으로 처리함.

 

현실적으론 RAID 저장 시스템을 안정 저장 장치로 사용함.

RAID(Redundant Arrays of Independent Disks)

: 2개 이상의 디스크를 병렬로 처리하여 성능 및 안정성을 향상시키는 방식

->  과거에는 주로 용량이 작은 디스크들을 연결하여 디스크 용량을 높이기 위해 사용한 반면, 현재는 디스크 성능 향상 외에도 디스크 오류및 데이터 손실과 같은 장애(Failure)에 대비하기 위한 용도로 사용되고 있음.

 

RAID Level

0: block stripingm non-redundant

1: mirrored disks

5: block-interleaved distributed party

6: P+Q redundancy

 

회복 시스템을 논할 때는 안정 저장 장치란 개념이 필요함.

-> 데이터를 다른데에 Write해두었는데 그게 잘못된 Write이면 어쩔??? 이런 문제가 생기기 시작하면 한도 끝도 없잖아...

∴ 안정 저장 장치라는 '어떤 장애가 발생하여도 데이터는 모두 살아남는다'는 개념 자체가 있다는 가정 하에 회복 시스템을 구성해야 함.

 

 

데이터 위치

데이터 도식도

- 기본적으로 모든 데이터는 디스크에 존재함.

- 디스크에는 블록들이 있고 각 블록들에는 데이터들이 들어가 있음.

- 디스크에 있는 데이터는 직접 못 읽기에 메인메모리의 시스템 버퍼에 올려서(input) 읽음.(버퍼에서 디스크로 데이터를 내리는 것은 output이라 함.)

- 이때 또 메인메모리에서 직접 읽는 것은 아님. 트랜잭션이 자신의 로컬 메모리 영역으로 데이터를 불러와서(read) 거기서 값을 다룸.(반대로 데이터를 버퍼에 다시 담는 것을 write라고 함.)

- 이렇게 디스크, 메인메모리의 버퍼, 트랜잭션의 로컬 메모리 영역 3군데에 값이 다 다를 수 있는데 이때 값이 최신 것이 가장 정확한 값임.

- 시스템 충돌(System Crash)이 나면 메모리(메인메모리의 버퍼, 트랜잭션의 로컬 메모리 영역)에 있는 값들이 모두 사라짐.

- Read/Write은 사용자가 다루는 것이기에 트랜잭션에서의 명령이 버퍼에 바로 적용되지만 input/output은 '버퍼 매니저'의 고유 권한으로 사용자가 다루는 범위가 아님.

-> read했다는 것은 데이터가 버퍼에 쓰여진 것이지 디스크에까지 쓰인 것은 아니다!

 

3.2.  로그(Log)

복구 기법으로는 크게 2가지 방법 (로그, 쉐도잉)이 있음.

현재 대부분의 DBMS는 로그 기법을 사용 중임.

쉐도잉은 옛날에 썼으나 현재는 간단한 Application(ex. 텍스트 에디터)에서 사용 중임.

 

복구 기법에서는 트랜잭션의 원자성(Atomicity) 보장을 위해 DB의 변화 이전에 변화에 대한 정보를 안전 저장 장치에 미리 기록해둠.

즉, 변경이 발생하기 전에 변경에 대한 정보를 디스크에 먼저 저장한다는 것임.

= WAL(Write Ahead Logging) : Log Record를 먼저 쓴다는 뜻.

로그

: 로그 레코드에 대한 Sequence.-> 어떤 DB에 연산이 일어났는지 알 수 있음.

- 로그는 안전 저장 장치에 보관됨.

- 로그 레코드 예시

<Ti start>: Ti 트랜잭션이 시작됨.

<Ti, X, V1, V2>: Ti가 X값을 V1에서 V2로 값을 바꿈.

<Ti commit>: Ti 트랜잭션이 끝남.

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

- 디스크-메인메모리 간의 데이터 이동은 디스크 블록 단위! 로그 레코드를 저장하는 로그 블록도 블록 단위로 데이터를 저장

- 로그 블록 하나에는 여러 개의 트랜잭션 로그 레코드가 저장됨.

 

Checkpoint(검사점)

: 복구 시간을 단축하기 위해서 DBMS가 주기적으로 Checkpointing을 함.

- Checkpointing은 메인 메모리의 모든 내용을 디스크로 output함.

- 먼저 메인메모리의 모든 로그 레코드와 변경된 데이터 버퍼 블록을 디스크에 output하여 동일화.

이후, 이 Checkpointing이 잘 수행되면 <checkpoint L>을 안전 저장 장치에 기록. (L은 checkpoint 시, 동작 중이던 트랜잭션 List임.)

복구 과정을 보자..!

Checkpoint 과정 예시

-> T1은 checkpoint 연산으로 인해 이미 디스크에 반영되어 있으므로 복구 연산이 필요없음, T2, T3는 Redo하고, T4는 Undo함.

 

복구 과정

1) undo-list, redo-list를 비움.

2) 로그를 Backward로(장애 시점부터 처음 만나는 <checkpoint L>까지로의 방향으로) 스캔 후 <Ti commit>이 포함된다면 Ti는 redo-list에,

<Ti start>만 있다면 Ti는 undo-list에 추가.

3) L의 트랜잭션들 중에서 redo-list에 없는 것들은 모두 undo-list에 추가

4) 로그를 다시 backwards로 스캔하면서 undo-list에 있는 트랜잭션들에 대하여 <Ti start>가 존재하는 부분들마다 멈추며 undo.

5) 가장 최근의 <checkpoint L>로 위치시키고 forwards로 log를 스캔하며 redo-list에 있는 트랜잭션들을 수행.

 

3.3.  데이터 버퍼

- 버퍼는 OS가 관리하는 메인 메모리의 일부분임. 디스크 블록을 복사 및 저장하는데 쓰고 이를 관리하는 프로그램이 '버퍼 매니저'임.

- 유저가 데이터를 읽어오는 과정

1) 일단 유저가 데이터를 OS에 요청

2) OS는 버퍼에 해당 값이 존재하면 그 값을 주고 없으면 디스크에 접근하여 해당 데이터가 있는 블록을 찾아서 값을 가져옴.

3) 이때, 버퍼가 빈자리가 있으면 바로 가져오지만 버퍼가 꽉 차있으면 일부를 변경된 값을 고려하여 디스크에 저장 후 버퍼에서 제거하고 가져오려던 값을 그 버퍼의 자리에 채움.

-> 이때! 제거할 버퍼의 블록을 찾는 방식 중 가장 많이 쓰이는 방식이 LRU(Least Recently Used)임.

 

로그 블록 버퍼링

- 데이터 블록과 마찬가지로 로그 레코드를 저장하는 로그 블록도 버퍼링을 함.

- 로그 블록이 바로 stable storage에 저장되는 것이 아니고 메인메모리에 버퍼링이 되었다가 '로그 블록 버퍼가 full되거나 log force operation이 실행될 때' output됨.

- log force는 트랜잭션이 commit할 때 실행됨.(commit할 때의 연산들 중 하나가 log force임.)

- 로그 블록 자체에 로그 레코드가 별로 없어도 트랜잭션이 commit하려면 그 상태까지의 모든 로그 레코드가 stable storage로 저장됨.

->  I/O 비용이 많이 듦!

∴ 로그 블록이 full이 될 때까지 commit을 안하다가 full 되면 stable storage에 한번에 저장하고 이로 인해 한번에 commit을 하게 됨.

=> 이런 걸 Group commit이라고함.

 

로그 블록 버퍼링 규칙

1) 로그 블록은 stable storage에 생성된 순서대로 output됨.

2) 트랜잭션은 커밋되었다는 로그 레코드가 stable storage에 output된 이후에 commit될 수 있음.

3) WAL(Write Ahead Logging): 로그 레코드가 먼저 stable storage로 내려가고, 그 이후 데이터 페이지가 디스크에 output됨.

-> 만약 반대이면 데이터 페이지가 어떻게 변경되었는지 모르기 때문에 회복이 불가능함.

 

데이터 페이지 버퍼링(Data Page Buffering)

- DBMS는 시스템 내에 있는 버퍼로 구성된 메모리를 관리함.

- 변경된 데이터 페이지를 디스크에 쓰려면 WAL을 지켜야 함.

- 데이터 페이지는 디스크에 쓰여질 때는 변경이 일어나면 안됨.(이런걸 pinned된다고 함)

-> 데이터를 쓰기 전에 트랜잭션은 X-Lock(이걸 latch라고 함)을 해당 데이터 블록에 걸어두고 Write 작업이 모두 끝나면 Unlock한다.

 

Latch란?

lock과 비슷한 것임. 유지 시간이 lock에 비해서 매우 짧음.

- Latch 사용 시 Deadlock이 발생하지 않음.

 

DB 버퍼의 구현 방법

1) 실제 메인메모리의 일부 공간을 할당받아서 구현

-> 유연성에서 많이 떨어지기에 이 방법은 잘 쓰지 않음.

 

2) 가상메모리 상에서 구현

-> DB 버퍼는 주로 VM을 통해 구현함.

사실 이것도 단점이 있음: Dual Paging

 

Dual Paging이 뭔데...?!!!

 

VM은 OS가 메모리의 크기를 늘려서 사용하려는 기술임. 그래서 실제 메모리보다 더 크게 메모리를 VM으로 잡는데 이때 실제 메모리보다 넘어가는 부분은 디스크에 swap 영역을 두고 그곳에 저장함. 근데 이때 메인 메모리가 이 swap 영역에 있는 데이터를 디스크에 output하려고 하면...! 원래 디스크에 있던 데이터를 메인 메모리로 input하고 이를 다시 output하는 추가적인 연산을 하게 됨. 이는 시간 비용이 더 들게 만듦.

 

Steal vs. Force 정책

Force: commit될 때 업데이트된 블록들(변경되어 버퍼에 저장되어 있던 데이터 페이지들)이 디스크로 내려가는 것.

-> Redo 안해도 됨(commit된 건 디스크에 무조건 쓰여있으니까)

Not force: commit될 때 업데이트된 블록들이 디스크로 내려가지 않아도 되는 것.

-> Redo 필요함(commit해놓고 안쓰인 것들이 있으니까)

Steal: commit되지 않은 데이터 페이지들도 디스크에 저장하는 것.

-> Undo 필요함(commit 안되었는데 쓰여져 있는게 있으니까)

Not steal: commit되지 않은 데이터 페이지들은 디스크에 저장하지 않는 것.

-> Undo 안해도 됨(commit 안된 건 어차피 디스크에 안쓰여 있으니까)

Force 방식은 트랜잭션이 완수될 때마다 모든 로그가 안전 저장 장치에 저장되다보니 시스템 성능 상의 문제를 야기함.

Not steal 방식은 DB 버퍼 용량을 초과하는 양의 데이터 페이지들을 변경하는 트랜잭션이 수행될 경우 기능 상의 문제를 야기함.

좋은 복구 알고리즘 정책: Steal + Not Force

 

3.4. 로그 기반 복구(Log-Based Recovery)

정상 상태에.

Logging

<Ti start>

<Ti, Xj, V1, V2>

<Ti commit>

 

Transaction rollback

Ti를 롤백하려면

step1. 로그를 end 부분부터 backwards로 스캔한 뒤 <Ti, Xj, V1, V2>와 같은 로그 레코드를 만날 때마다...

- Xj에 V1 값을 Write한 뒤 <Ti, Xj, V1> 로그 레코드를 Write.(이때 이런 로그 레코드를 CLR(compensation log record)라고 함.)

step2. 이후 <Ti start>를 만나게 되면, 스캔을 멈추고 로그 레코드 <Ti abort>를 Write.

 

장애

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

step1. 가장 최근의 <checkpoint L>을 찾고, L에 undo-list 할당.

step2. <checkpoint L>부터 forwards로 스캔.

- <Ti, Xj, V1, V2>를 만나면 Xj에 V2를 Write(Redo).

- <Ti start>를 만나면 Ti를 undo-list에 추가.

- <Ti commit> or <Ti abort>를 만나면 Ti를 undo-list에서 제거.

 

2) Undo Phase: incomplete 상태의 트랜잭션에 대해 수행

step1. 로그의 끝에서부터 Backwards로 스캔

- undo-list에 있는 Ti에 대하여 <Ti, Vj, V1, V2>를 만나면 Xj에 V1을 쓰고(Undo), <Ti, Xj, V1> 로그 레코드를 작성.

- undo-list에 있는 Ti에 대하여 <Ti start>를 만나면, <Ti abort> 로그 레코드를 write한 후 Ti를 undo-list에서 삭제.

- undo-list가 빌 때까지 위 작업을 수행.

 

 

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

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

복구 알고리즘 예시

Fuzzy checkpoint

: checkpointing 동안 DB 연산이 멈추지 않고 수행하도록 허용하는 checkpoint.

 

Fuzzy checkpoint 과정

step1. 일시적으로 모든 트랜잭션의 update를 중단시킴

step2. <checkpoint L> 로그 레코드를 남기고 force log 를 수행 (로그 블럭을 stable stoarge 에 저장, WAL)

step3. 변경된 데이터 블럭을 리스트와 시킴 (리스트 M)

step4. 일시적으로 멈춰두었던 트랜잭션의 액션들을 재개

step5. 리스트 M의 모든 블럭을 디스크에 저장함

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

 

복구 알고리즘이 fuzzy checkpointing을 사용하면 stable storage 에서 last_checkpoint 를 관리함.

 

Failure of Non-volatile storage(디스크 장애)

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

-> DB 전체 상태를 주기적으로 다른 디스크에 덤프시켜서 저장.

 

step1. 메인 메모리에 있는 모든 로그 레코드를 stable storage에 output.

step2. 모든 버퍼 블록을 디스크에 output.

step3. DB 현재 상태를 stable storage에 copy.

step4. <dump> 로그 레코드를 stable storage에 output.

 

이때...! 덤프과정 중에는 어떤 트랜잭션도 active할 수 없다!

디스크 장애 복구 과정

가장 최신 dump를 받아서 로그를 적용하고 그 이후 commit된 트랜잭션들은 redo하여 복구함.

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

 

3.6. 원격 백업(Remote Backup)

System Crash VS Disaster

: 앞서 살펴본 System Crash와 달리 Disaster는 임의의 사이트에 대한 모든 정보가 홍수, 지진, 대공습 등으로 인해 전부 손실되는 경우이고, 이때는 복구 기법을 이용하여 시스템을 복구하는 것은 불가능하다.

 

원격 백업 시스템(Remote Backup System)

원격 백업 시스템 구조도

현대 사회에서는 시스템 장애 시간을 최소화하게 하는 Availability(가용성)가 높은 시스템을 요구함.

-> 원격 백업 시스템을 통해 primary site에 있는 모든 로그 레코드들을 secondary site에 보냄으로서 동기화를 달성할 수 있다.

 

- 장애 인지(Detection of failure)

: primary site에서의 장애를 감지하기 위해 원격 백업 시스템은 여러개의 통신 링크를 유지 및 관리하고 primary site는 지속적으로 메시지(heart-beat message)를 발송함.

 

- 제어 이관(Transfer of control)

: 장애가 발생하면 백업 시스템은 주 시스템의 역할을 하기 위해 로그 레코드를 가지고서 복구 연산을 하여 주 시스템 상태와 동일하게 만듦.

이후, 주 시스템이 고쳐지면 그곳으로 다시 로그 레코드를 받아서 복구함.

 

- 빠른 회복 시간

: 제어권 이관을 빠르게 하기 위해 원격 백업 시스템은 로그를 받는 즉시 이전의 값들은 삭제하고 새로 업데이트를 적용해두기도 함.

= Hot-spare 설정

 

원격 백업 시스템 외에도 시스템의 가용성을 높이는 또 다른 방법

-> 동일 데이터를 분산적으로 다수 장소에 저장하는 분산 DB 방식(원격 백업 방식에 비해 가용성이 더 높긴 하지만, 구현 및 관리 복잡, 고비용이 요구됨)

 

야...근데...! 그럼 언제 commit할 건데??? commit을 언제 하느냐에 따라 주 시스템이랑 원격 시스템에 저장된 값이 달라질 수 있잖슴!?

Time to Commit

원격 백업 시스템 환경에서 트랜잭션의 Durability(지속성) 보장을 위해

-> 원격 시스템에 트랜잭션 완료 로그가 기록된 후 해당 트랜잭션을 commit함.

 

근데...이때 시간이 많이 소요됨.

∴ 상황에 따라 완화된 기준의 트랜잭션 지속성을 제공할 수 있음.

1) One-safe: 주 시스템에 트랜잭션 완료 로그가 기록되자마자 바로 commit

2) Two-very-safe: 주 시스템, 원격 시스템 모두에 트랜잭션 완료 로그가 기록되면 commit

3) Two-safe: 주 시스템, 원격 시스템 모두 active한 상황이면 Two-very-safe방식으로, 만약 주 시스템만 active한 상황엔 one-safe방식으로 commit.(절충안임.)

 

Shadowing

: db_pointer가 partial commit할 때마다 shadow copy를 update하고 이걸 가리킴. 복구 시에는 이전에 가리키던 것을 가리키고 shadow copy는 삭제됨.

Shadowing

이렇게 간단하게 atomicity와 durability를 제공하지만...

1) 동시성 제어를 하기엔 너무 많은 shadow가 있어서 어려움.

2) Data Clustering(데이터 분류, 그룹화)이 불가능하기에 큰 DB에서는 효율성이 떨어짐.

 

∴ 주로 Text Editor에서 씀.