Published 2022. 9. 1. 08:32

[Database] DBA급 개발자로 - #3 Database Storage 1/2

728x90

이전 포스팅에서 중급 SQL에 대해 살펴봤습니다. 이번 포스팅을 통해서 DBMS가 데이터를 디스크에 어떻게 저장하고 관리하는지 살펴보겠습니다.

DBMS가 데이터를 저장하는 방법

대다수의 DBMS는 전원이 꺼져도 데이터가 보존되는 비휘발성 저장 장치를 기준으로 설계됐습니다.

최근에는 휘발성 저장 장치만큼 빠르면서도 비휘발성 저장 장치처럼 전원이 꺼져도 데이터가 보존되는 특성을 지닌 NVRAM이 개발됐습니다.

비휘발성 저장 장치는 휘발성 저장 장치보다 더 많은 데이터를 저장할 수 있지만 I/O에 소요되는 시간이 훨씬 깁니다. 따라서 DBMS는 비휘발성 저장장치를 사용함에 있어 I/O 비용을 최소화할 수 있도록 설계됐습니다(예를 들면 random access보다는 sequential access를 선호하도록 설계).

디스크에 저장된 데이터베이스 파일의 페이지와 메모리 상에 위치한 버퍼 풀 페이지에 대해 알아보겠습니다.

디스크에는 데이터를 저장하는 페이지(page)가 존재합니다. 각 페이지는 헤더 정보를 가지고 있습니다. 페이지 디렉터리(page directory)는 디스크에 저장된 페이지들에 대한 대한 포인터를 저장합니다. DBMS가 실행되면 페이지 디렉터리와 쿼리에 필요한 페이지가 메모리, 즉 버퍼 풀에 로드됩니다.

위의 과정은 모두 DBMS에 의해 실행되고 관리됩니다. 여기서 다음과 같은 의문이 들 수 있습니다. OS의 기능만으로도(가상 메모리, 페이징 기법 등) 필요한 페이지를 메모리에 올려서 사용할 수 있는데 왜 OS를 활용하지 않을까요? OS의 기능을 활용하면 로직 구현에 시간을 낭비하지 않아도 될 것 같은데 말이죠. 이는 DBMS에게 최적화된 로직을 구현할 수 없기 때문입니다. OS는 모든 소프트웨어가 범용적으로 사용할 수 있는 소프트웨어입니다. 범용적인 OS 기능은 DBMS에 최적화된 기능이 아닐 수 있습니다. 따라서 DBMS는 OS의 기능을 사용하기보다는 DBMS에 최적화된 기능을 직접 구현해서 사용합니다. 예시는 다음과 같습니다.

디스크에 dirty page를 올바른 순서로 flushing
Prefetching (향후 읽을 확률이 높은 데이터를 메모리로 미리 로드하는 기능)
Buffer replacement policy (메모리에 데이터를 어떻게 효율적으로 올리고 내릴지 결정하는 정책)
Thread/Process scheduling for DBMS

DBMS는 OS보다 데이터베이스와 관련된 정보가 훨씬 많기 때문에 몇몇 기능은 DBMS에서 구현했을 때 효율적일 확률이 높습니다. 따라서 DBMS는 독자적으로 페이징 기능을 구현합니다.

몇몇 DBMS에서는 OS의 기능을 활용해서 페이지를 관리하기도 합니다.
- Elastic Search
- MongoDB
- SQLite

DBMS는 최적화를 위해 특정 포맷에 맞춰 디스크에 데이터를 저장합니다. File ⊃ Page ⊃ Tuple 형태로 데이터를 저장하는데요, 먼저 file에 대해서 알아보겠습니다.

File Layout

DBMS는 하나 이상의 파일(file)로 데이터베이스를 관리합니다. 정확히 말해 DBMS의 storage manager가 이 파일들을 관리합니다. 파일은 DBMS의 용도에 맞는 포맷으로 구성됩니다.

Heap File

Heap file이란 정렬되지 않은 페이지로 구성된 파일을 의미합니다. 정렬되지 않았기 때문에 특정 페이지에 대한 작업을 하려고 하면 모든 파일 내 모든 페이지를 탐색해야 합니다. 페이지를 구성하는 방법으로는 크게 Linked List와 Page Directory 방식이 존재합니다.

Linked List

Linked List 방식에서는 각 파일의 가장 처음에 헤더 페이지(Header Page)가 등장합니다. 헤더 페이지는 Free Page List(데이터를 저장할 수 있는)의 첫 번째 페이지와 Data Page List(데이터가 저장된)의 첫 번째 페이지 대한 포인터가 저장됩니다. 각 페이지에서는 해당 페이지에 얼마만큼의 free slot이 존재하는지 표시합니다.

Page Directory

페이지 디렉터리(page directory) 방식은 데이터를 저장한 페이지 위치를 기록하는 특수한 페이지(페이지 디렉터리)를 활용합니다. 페이지 디렉터리는 페이지당 데이터를 저장할 수 있는 free slot의 수를 기록하기도 합니다.

Page Layout

페이지(page)란 튜플을 저장하기 위해 사용되는 고정 크기의 데이터 덩어리입니다. 페이지에는 메타데이터, 튜플, 인덱스와 로그 등 다양한 데이터가 저장됩니다. 페이지는 페이지를 식별할 수 있는 페이지 ID가 부여됩니다. 페이지 ID는 페이지에 접근하기 위해서 사용되는 포인터 역할을 한다고 볼 수 있습니다.

페이지 헤더에는 다음과 같은 정보를 저장합니다.
- 페이지 크기
- Checksum(페이지에 저장된 데이터가 올바른지 확인하는 데 사용)
- DBMS version
- Transaction visibility
- Compression information

데이터베이스 페이지는 hardware page, OS page와 구분됩니다. Hardware page, OS page는 주로 4KB, 데이터베이스 페이지는 각 DBMS에 맞게 크기가 설정됩니다. 예시로 Oracle은 4KB, PostgreSQL은 8KB 그리고 MySQL은 16KB입니다.

파일에 데이터를 저장하는 방식은 크게 tuple-oriented와 log-structured로 구분할 수 있습니다. 먼저 tuple-oriented 저장 방식에 대해 살펴보겠습니다.

Tuple Oriented

튜플을 저장할 수 있는 가장 단순한 페이지의 구조를 떠올려보면 다음과 같습니다.

튜플을 저장할 때 페이지의 빈 공간 아무 데나 튜플을 저장한다고 가정합시다. 튜플의 크기가 고정이라면 튜플의 위치는 (튜플 크기) × (튜플 수)를 통해서 쉽게 구할 수 있습니다. 만약 가변 길이 튜플이 저장되면 어떤 일이 발생할까요? 튜플의 크기가 고정되지 않았기 때문에 튜플의 위치를 알기 어렵습니다. 따라서 튜플을 찾기 위해서 페이지 전체를 탐색해야 하는 오버헤드가 발생합니다. 만약 데이터를 삭제하면 어떻게 될까요? 빈 공간이 생길 겁니다. 만약 저장하고자 하는 튜플이 있는데 해당 튜플의 크기가 빈 공간의 크기와 맞지 않는다면 어떻게 해야 할까요? 그럼 해당 튜플을 저장할 수 있는 빈 공간을 찾아 저장해야 할 겁니다. 이러한 작업을 반복할수록 저장공간의 단편화(fragmenatation)가 증가하게 됩니다. 조금만 생각해보더라도 위와 같은 페이지 구조로 해결할 수 없는 문제가 많습니다. 이러한 문제점들을 극복하기 위해서 DBMS는 slotted pages를 활용합니다.

Slotted Pages

가장 자주 활용되는 페이지 구조입니다. 여기서 슬롯(slot)이란 페이지에 저장된 튜플을 가리키는 포인터 배열로 생각하면 됩니다. 각 슬롯은 페이지에 저장된 튜플의 첫 시작점(offset)을 가리킵니다. 페이지의 헤더는 사용된 슬롯의 개수와 가장 마지막에 사용된 슬롯의 위치(offset) 정보를 저장합니다. 각 튜플을 식별하기 위해 식별자가 부여되는데 보통은 페이지 ID와 튜플의 offset의 조합으로 구성됩니다.

Slotted page를 사용하면 위에서 설명드렸던 단순한 페이지 구조를 사용했을 때의 문제를 해결할 수 있습니다. 첫 번째는 가변 길이 튜플을 저장하더라도 슬롯을 통해 위치를 쉽게 파악할 수 있기 때문에 튜플을 찾는 오버헤드가 적습니다. 두 번째는 튜플을 삭제했을 때 메모리 단편화를 해결할 수 있습니다. 빈 공간을 채우도록 튜플을 이동시키고 슬롯 값을 업데이트해줌으로써 단편화를 해결할 수 있습니다(물론 이런 작업이 자주 발생하면 오버헤드가 커집니다).

Tuple Layout

튜플은 값의 집합을 포함하는 데이터 구조입니다.

튜플과 레코드의 차이는 다음과 같습니다.
튜플은 값의 집합을 포함하는 데이터 구조이고, 레코드는 데이터베이스에 저장된 컬렉션입니다. 두 개 모두 값의 집합을 저장하므로 유사하지만, 다릅니다. 튜플은 서로 연관된 값의 집합을 저장하는 데 사용됩니다. 예를 들어 공간의 점의 좌표 또는 사람의 세부 정보가 그렇습니다. 반면에, 레코드는 일반적으로 데이터베이스에 고객 또는 직원과 같은 특정 개체(entity)에 대한 정보를 저장하는 데 사용됩니다. 레코드의 필드는 데이터베이스 테이블의 열에 해당하고, 각 레코드는 테이블의 한 행을 나타냅니다.

튜플의 헤더에는 메타데이터를 저장합니다.

튜플 헤더에는 다음과 같은 정보가 저장됩니다.
- Concurrency control을 위한 visibility info
- Bitmap (해당 attribute이 NULL인지 확인하기 위해 사용)
- 그 외 필요한 값

튜플 헤더에는 저장된 데이터의 (테이블) 스키마는 함께 저장되지 않습니다. 보통은 테이블 스키마에 정의된 칼럼의 순서대로 튜플에 각 칼럼 데이터가 저장됩니다.

하지만 가변 길이 컬럼의 데이터는 경우에 따라 저장되는 방식이 달라질 수 있습니다(PostgreSql의 경우 가변 필드는 경우에 따라 다른 칼럼의 데이터와 함께 튜플 내에 저장될 수도 있고 별도의 TOAST 테이블에 저장될 수 있다고 명시돼있습니다).

Log Structured File Organization

파일에 데이터를 저장하는 방식에는 크게 Tuple-Oriented와 Log-Structured 형태가 있다고 말씀드렸는데요, Log-Structured에 대해서 간략하게 알아보겠습니다.

Log-Structured 형태의 파일 구조는 페이지에 튜플을 저장하는 게 아니라 로그만 저장합니다. 데이터베이스의 변경이 발생할 때 변경 이후 최종 결과물을 저장하는 게 아니라 어떻게 변경됐는지를 나타내는 로그를 추가합니다.

Insert는 튜플 전체 정보를 가진 로그를 추가합니다.
Delete는 튜플에 삭제됐음을 표시할 수 있는 로그를 추가합니다.
Update는 튜플 내 업데이트된 attribute를 표시한 로그를 추가합니다.

별도의 처리없이 로그를 계속 추가하면 어떻게 될까요? 특정 튜플을 읽기 위해서 해당 튜플과 관련된 모든 로그를 찾고 로그를 취합해야 합니다. 만약 저장된 전체 로그의 크기가 크다면 우리가 원하는 튜플을 읽기 위해서는 관련 로그를 모두 취합해야 합니다(오버헤드가 엄청 크겠죠). 이러한 오버헤드를 줄이기 위해서 Log-Structured 파일 구조를 사용하는 DBMS는 로그를 압축시킵니다. 새로 추가된 로그를 이전에 압축한 로그에 반영시키기 때문에 튜플을 탐색할 때 관련된 모든 로그를 확인할 필요가 없습니다(압축된 로그와 아직 압축되지 않은 로그만 반영해서 읽으면 되기 때문입니다). Log-Structured 파일 구조의 대표적인 방식으로는 크게 Leveled Compaction이 존재합니다.

Leveled Compaction

Leveled Compaction은 데이터를 저장하는 영역을 level 0, level 1, level 2... 의 형태로 나눠 데이터를 저장합니다. 각 레벨은 정렬된 데이터의 연속입니다(Level 0은 제외될 수 있습니다). Level 0은 메모리에서 디스크로 막 플러시 된 데이터를 저장합니다. 만약 level 0에 저장할 수 있는 최대 용량을 초과하면 level 0에 저장된 데이터를 압축해서 level 1에 저장된 데이터와 병합시킵니다(이후 Level 1이 꽉 차면 Level 1의 데이터를 압축해서 Level 2로 옮기고 Level 2는 Level 3로...). 각 Level에 저장된 데이터는 정렬됐기 때문에 이진 탐색이 가능합니다.

더 자세한 설명은 아래 포스팅을 참고해주세요.

Leveled Compaction · rocksdb-wiki-kr

meeeejin.gitbooks.io

마무리

이번 포스팅을 통해 DBMS가 데이터를 디스크에 어떤 형태로 저장하는지 알아봤습니다. 요약하자면 DBMS는 데이터를 효율적으로 활용할 수 있는 형태로(file, page, tuple, log) 저장합니다. 다음 포스팅에서는 튜플의 어트리뷰트(attribute)가 어떻게 저장되는지 알아보겠습니다.