CMU Database Fall 2022 를 듣고 정리한 글입니다.
Disk-Based Architecture
DBMS는 데이터베이스의 primary storage location이 non-volatile disk일 것임을 가정한다.
DBMS의 각 구성 요소들은 데이터가 non-volatile(disk)과 volatile(memory) 사이를 이동하도록 관리한다.
Speed
storage는 CPU Register, CPU Cache, DRAM, SSD, HDD, Network Storage 순으로 점점 느려지고 용량 대비 가격이 저렴해진다. 이 중 Register, Cache, DRAM은 volatile 하고, 나머지는 non-volatile storge이다.
하위 계층으로 갈수록 얼마나 느려지는지를 아라보기 위해, L1 Cache의 latency를 1s라고 하면, 나머지 디바이스들의 latency는 아래와 같다.
- L1 Cache: 1초
- L2 Cache: 4초
- DRAM: 100초
- SSD: 4.4시간
- HDD: 3.3주
참고로 가장 빠른 Register는 L1 Cache보다 약 3배 빠르다고 한다.
Sequential vs Random Access
non-volatile storage로의 Random access는 sequential access보다 느리다. 그 이유는 디스크는 DRAM과 달리, 특정 Address의 데이터를 바로 가져오도록 하는 것이 아니라 한번에 연속된 바이트 (block/pages)를 가져오는 것에 최적화되어 있기 때문이다.
HDD의 경우 물리적인 제약이 있어 매우 느리고, 전자적으로 작동하는 SSD 또한 wear leveling (쓰기 작업을 여러 셀에 고르게 분배하는 작업)과 garbage collection (더 이상 필요하지 않은 블록을 비워주는 작업) 때문에 sequential access가 훨씬 빠르다.
System Design Goals
이러한 제약을 고려하면, DBMS는 다음 목표들을 갖는다.
- (VM과 비슷하게) Memory Space보다 더 큰 데이터베이스를 다룰 수 있도록 한다.
- 디스크에 읽고 쓰는 것은 비싼 작업이므로, 이를 최소화한다.
- Random Access는 비효율적이므로, Sequential Access를 최대화한다.
DBMS Structure
앞으로 다룰 DBMS의 대략적인 구조는 위 그림과 같다.
최상위 레벨인 Execution Engine이 특정 페이지를 요구하면, Buffer Pool이 Memory 혹은 Disk로부터 파일을 가져온다. (실질적으로 반환되는 값은 page가 위치하는 곳을 가리키는 pointer)
Execution Engine은 해당 page가 메모리에 있는지, 디스크에 있는지... 등등은 알지 못하고 page를 해석해서 필요한 operation을 하는 데 사용한다.
Why not use the OS?
일단 위 구조를 생각하면 구조가 VM과 매우 유사함을 알 수 있다. DBMS가 mmap 을 사용한다면 page를 disk와 memory 사이에서 옮기는 것을 OS에 위임할 수 있다.
하지만 이러한 방법은 여러 스레드가 mmap 파일에 접근하여 쓰기 operation 을 하려고 할 때 문제가 될 수 있다. 만약에 physical memory에 남은 공간이 없어서, page fault가 일어나는 경우, evict 되는 page들이 다른 스레드에서는 필요로 하고 있는 page일 수 있어, thread가 stall될 수 있다.
그 외에도 다음과 같은 문제점들이 있을 수 있다.
- Transaction Safety: OS가 dirty page를 아무때나 flush할 수 있기 때문에, atomicity가 깨질 수 있다.
- I/O Stalls: DBMS는 어떤 page가 현재 available한지 알 수 없기 때문에, page fault가 일어나는 경우 thread가 stall 된다.
- Error Handling: Page를 validate하기 어렵다. OS가 page를 validation 해 주지 않으므로, 잘못된 참조 혹은 data corruption으로부터 발생하는 Signal에 대한 핸들링을 직접 해 주어야 한다.
- Performance Issue: 서로 다른 프로세스/스레드가 같은 데이터에 접근하는 경우 TLB 등의 OS data structure의 정합성을 맞춰주기 위한 많은 작업들이 소요되므로 성능 이슈가 생긴다.
이러한 문제를 해결할 수 있는 몇 방법들이 있지만, 여전히 DBMS 자체가 통제를 갖고 OS보다 최적화를 수행할 수 있는 여지가 많기 때문에 잘 사용되지 않는다. (madvise, mlock, msync)
- dirty page들을 disk에 순서대로 쓰는 것
- prefetching
- buffer replacement policy
- thread/process scheduling
How the DBMS represents database
Storage Manager
DBMS는 database를 디스크에 각자의 형식으로 저장한다. 파일은 한개가 될 수도 있고, 여러개가 될 수도 있는데, 이 파일들을 관리하는 것은 Storage Manager의 몫이다.
Storage Manager들은 그 파일들의 spatial/temporal locality를 향상시키도록 읽기/쓰기를 관리하며, 파일들을 읽고 쓰기 위한 단위인 page로 관리한다.
Page
Page는 일반적으로 fixed-size의 데이터 블록으로 tuple, meta-data, index, log records 등 다양한 정보를 담을 수 있다.
- Hardware Page (일반적으로 4KB)
- OS Page (일반적으로 4KB)
- Database Page (512B - 16KB)
대부분의 DBMS는 page type을 섞진 않고, 일부는 page가 self-contained 이기를 요구한다.
각 page들은 page id라고 불리는 unique identifier를 통해 구분되며, DBMS 는 page id를 physical location으로 매핑하는 레이어를 가지고 있다.
DBMS들은 page를 여러 방법으로 보관하는데, 이 중에서는 Heap File Organization에 대해서 알아본다.
Heap File
Heap File은 random order tuple을 가지고 있는 page의 unordered selection이다.
위처럼 file이 여러 개 존재하는 경우, (한 개만 있는 경우와는 달리) 어떤 page가 어떤 file에 있고, 어떤 page가 free space를 가지고 있는지 파악해야 하므로 page들의 meta data를 가지고 있는 특별한 page인 directory page를 만든다.
directory page는, data page들의 위치와 page 당 free slot, empty page의 목록을 가지고 있다.
Page Layout
그러면 이러한 Page는 실제로 어떻게 생겼을까?
Page Header
모든 Page는 size, checksum, dbms version, transaction visibility, compression information 등의 정보를 포함하는 헤더를 갖는다.
Tuple-Oriented Layout
page 내부에 어떻게 정보를 저장할 지 또한 디자인해야 하는데, 일단 지금은 tuple 만을 저장한다고 가정한다.
두가지 접근이 있는데, 이번에는 Tuple-Oreinted 방식을 사용한다고 가정한다.
가장 심플한 생각은 page 내부의 tuple의 개수를 기억하고 매번 tuple을 맨 아래에 추가하는 것이다. 하지만 이 방식은, 중간에 tuple을 삭제하거나, tuple의 bytelength가 서로 다른 경우 곤란해진다.
그래서 위 방식과 같은 slotted page 방식을 많이 사용한다. 이 방식은, 각 tuple의 starting position offset을 저장하는 slot array를 header 뒤에 위치시키고, tuple은 파일의 끝에서부터 저장한다. 이 때 header는 사용된 slot의 개수와 마지막 slot의 starting location을 저장한다.
이러면 variable length tuple에도 대응할 수 있고, 특정 tuple을 지우는 경우 그 tuple 앞쪽의 tuple들을 shift 해 주면 된다.
Record Ids
DBMS 는 각 tuple을 tracking하기 위한 방법이 필요하기 때문에, unique record identifier라는 이름의 식별자를 부여한다. 일반적으로는 page_id + offset/slot 이고, application level에서는 이것에 의존할 수 없다.
Tuple Layout
각 Tuple은 어떻게 생겼을까? Tuple은 본질적으로는 byte sequence이고, 이것을 의미 있는 값으로 해석하는 일은 전적으로 DBMS의 일이다.
Tuple Header
각 Tuple은 metadata를 포함하는 header를 가지고 있다. 이는 concurrency control을 위한 visibility info와, NULL value를 위한 Bit Map을 가지고 있다. 이 Bit map은 tuple 전체를 검사하지 않고, 각 attribute가 null 값을 갖는지의 여부를 bit 값만으로 알 수 있어 매우 효율적이다.
Tuple Data
Attribute들은 일반적으로 table을 만들 때 선언했던 순서대로 저장된다.
Denormalized Tuple Data
하지만 DBMS들은 때때로 관련된 tuple들을 같은 page에 저장하는 denormalize (pre-join)를 수행할 수 있다. 이는 일반적인 워크로드에서 I/O를 줄일 수 있어 효율적이지만, update에 있어서는 비효율적이다.
