15-445/645 Intro to Database Systems/Fall 2022 3강을 보고 정리한 내용입니다.

링크: https://www.youtube.com/watch?v=df-l2PxUidI

1,2강에서 relational database에 대해 배웠다. 3,4강에서는 relational database의 저장 방식 중 disk-oriented 아키텍처에 집중한다. 구체적으로, 시스템이 겉으로 드러나진 않지만 기본적인 시스템과 어떻게 상호작용하는지를 공부한다. 상호작용을 다루기 전 우선 disk-oriented 아키텍처 자체에 집중한다.

위 그림의 오른쪽 표에서, 위에 있는 층은 아래 층들에서 필요한 내용을 api로 가져와서 활용할 수 있다. 예를 들어, buffer pool manager는 하단에 있는 disk manager에서 필요한 정보를 가져옴으로써 디스크 상 이루어지는 동작을 신경쓰지 않아도 된다. 강의의 진행 방식도 최하단에서부터 최상단으로 진행한다. 이번 강의에선 가장 low level에 있는 disk manager를 다룬다.

1. Storage 기본 용어 정리

본격적으로 Disk-oriented DBMS 아키텍처를 다루기 전, 데이터가 저장되는 하드웨어 용어를 먼저 짚어본다.

1-1. Devices

Storage에는 계층이 존재하는데, 계층에 속하는 장치들은 크게 volatile, non-volatile로 나뉜다.

1-1.1 Volatile

Volatile 장치는 전원을 제거하면 데이터를 잃는다. 또한 byte-addressable 위치로 빠른 random access가 가능하다. 다시 말해서, 임의의 정확한 위치로 접근 가능하다는 것이다. Volatile 장치들은 빠르고 작기 때문에 상대적으로 비싸다.

우리는 이러한 저장 계층 중 DRAM을 메모리라고 부를 것이다. 참고로, volatile 나머지 장치들인 CPU registers와 CPU caches들은 CPU라고 한다.

1-1.2 Non-Volatile

Non-volatile 장치는 전원을 제거하더라도 데이터를 보존한다. 따라서, disk-oriented DBMS 아키텍처는 기본적으로 데이터를 이곳에 보존한다고 가정한다. Disk-oriented DBMS라는 이름에서 알 수 있듯이 이곳을 disk라고 한다.

Non-volatile 장치들은 block/page addressable하다. Block/page addressable하다는 것은 특정 offset에서 값을 읽기 위해서는 먼저 4KB의 페이지를 메모리에 업로드해야 한다는 뜻이다. 이는 volatile 장치가 임의의 정확한 위치에 바로 접근 가능했던 것과 대조적이다. 또한 non-volatile 장치는 random access보다 sequential access를 더 빠르게 한다. 이는 알고리즘 수업에서 direct access array나 hash table을 이용한 random access가 $O(1)$ 시간이 걸리는 것에 비해 array를 이용한 sequential access가 $O(n)$ 시간이 걸린다고 배운 것과 모순이다. 그 이유는 알고리즘이 몇 가지 가정 하에 논리를 전개하기 때문이다. 알고리즘은 모든 데이터가 메모리에 있고 동일한 액세스 특성을 가진다고 가정한다. 하지만 실제 하드웨어는 요소들 간의 전자 통신이 발생하여 랜덤한 요소들 접근에 추가적인 시간을 발생시킨다.

추가적으로, 많은 데이터를 저장하기 위해 volatile 장치들은 크고 느릴 것이기 때문에 상대적으로 저렴하다.

2. Disk-Oriented DBMS

DBMS는 데이터베이스가 디스크에 있다고 간주하지만 디스크의 데이터베이스에서 직접 작동하진 않는다. 그 대신, non-volatile 장치인 메모리에서 작동한다. 그렇기 때문에, DBMS의 구성 요소들은 non-volatile과 volatile 저장소 간의 데이터의 움직임을 관리하는데에 중점을 둔다. 디스크에서 데이터를 가져오는 속도가 매우 느리기 때문에 디스크의 지연 시간을 숨기는 것을 목표로 한다.

2-1. 시스템 디자인 목표

Disk-oriented DBMS는 시스템을 디자인 목표는 다음과 같다.

1. DBMS가 제공되는 메모리 용량을 초과하는 데이터베이스를 관리할 수 있어야 한다.
2. 디스크에 읽고 쓰는 데에 많은 비용이 발생하기 때문에 대형 지연과 성능 저하를 방지하는데에 힘을 써야 한다.
3. Random access보다 sequential access가 주로 더 빠르기 때문에, sequential access를 최대한 빠르게 하기 위한 노력을 기울인다.

2-2. DBMS 전체적인 과정

Disk-oriented DBMS의 전체적인 과정을 훑어보면 다음과 같다. 데이터베이스는 우선 모두 디스크에 저장되어 있다. 디스크에 저장된 데이터는 페이지로 나뉘며 첫 번째 페이지는 디렉토리 페이지로 각 정보가 어느 페이지에 저장되어 있는지 알려주는 길잡이 역할을 한다. DBMS가 데이터에 대해 작동하기 위해 디스크에 있는 데이터를 메모리에 가져와야하는데 그 과정은 다음과 같다. Execution engine은 쿼리를 실행하는데 이 때 필요한 페이지를 buffer pool에게 요청한다. Buffer pool이 디스크와 메모리 간의 데이터 이동을 관리하기 때문에 해당 페이지를 메모리에 가져오고 execution engine에게 메모리에 있는 페이지에 대한 포인터를 제공한다. 또한 buffer pool은 execution engine이 그 페이지에 대해 실행할 때 페이지가 메모리에 위치하고 있도록 보장한다.

2-3. DBMS vs OS

앞서 disk-oriented DBMS의 디자인 목표는 제공되는 메모리 용량을 초과하는 데이터베이스를 관리할 수 있어야하고 디스크에 읽고 쓰는 데에 많은 비용이 발생하기 떄문에 대형 지연과 성능 저하를 방지한다였다. 이러한 목표는 가상 메모리와 같다. 가상 메모리는 OS가 mmap를 사용하여 프로세스의 주소 공간에 있는 파일 내용을 매핑하기 때문에 디스크와 메모리 사이에서 페이지를 이동시킬 수 있다.

위와 같은 그림에서 page1, page3이 아닌 새로운 페이지를 불러와야할 때 physical memory가 찼기 때문에 os는 기존의 page1, page3 중 어떤 페이지를 삭제할지 정해야한다. 이 때, 원하는 페이지가 physical memory에 없기 때문에 os는 어느 페이지를 삭제할지 정할 시간을 확보하기 위해 thread stall interrupt를 발생시킨다. 그 결과, 프로세스가 차단된다.

위에서 구체적인 문제를 설명하였는데, 다음과 같은 문제들도 발생할 수 있다.

• #1: Transaction Safety
  → OS는 언제든지 dirty pages를 플러시할 수 있다.
  이상적으로 transaction이 commited된 상태에만 디스크에 페이지를 쓸 수 있어야하는데 os는 언제든지 페이지를 쓸 수 있기 때문에 문제가 발생한다.

• #2: I/O Stalls
  → 위에서 구체적인 예시를 제시했던 문제다. DBMS는 어느 페이지가 메모리에 있는지 알지 못할 때, OS는 스레드의 페이지 오류를 발생시켜 스레드를 중단한다.

• #3: Error Handling
  → 페이지의 유효성을 검사하기 어렵다.
  페이지에 문제가 발생하면 exception이 아닌 SIGBUS를 발생시키는데 SIGBUS는 DB 전체에 signal handler 코드를 발생시킨다. 그에 반해, DBMS는 checksum으로 간단하게 파일이 유효한지 체크한다. 따라서, DB 전체가 아닌 disk managing 부분에서 기능을 수행하기 때문에 효율적이다.

• #4: Performance Issues
  → OS의 데이터는 데이터베이스 시스템의 자체적인 페이지 테이블을 가지고 있다. 따라서, TLB shootdown이 발생한다. TLB(Translation Lookaside Buffer)는 가상 메모리 주소에서 실제 메모리 주소로 변환하는 캐시로, 프로세서가 주소의 가상-물리적 매핑을 변경할 때 다른 프로세서의 캐시에서 해당 매핑을 무효화하도록 지시한다.

결론적으로, 비록 OS가 DBMS에서 요구하는 기능들을 수행할 수도 있겠지만 DBMS가 더 효율적이고 정확하게 기능을 수행할 수 있기 때문에 DBMS를 사용해야 한다.

3. Storage

DBMS는 데이터베이스를 디스크에 파일들로 저장하는데 DBMS마다 각각 다른 형식으로 저장한다. 그렇기 때문에 예를 들어 sqlite의 데이터 파일을 MySQL에 사용할 수 없다.

DBMS의 storage manager는 데이터의 파일들을 페이지의 모음으로 관리한다. 페이지에 읽고 쓴 데이터와 더불어 해당 페이지의 여유 공간을 추적한다.

3-1. Pages

페이지는 고정된 크기의 데이터 블록이다. 페이지는 튜플, 메타데이터, 인덱스, 로그 기록 등을 포함할 수 있는데 대부분 이러한 유형을 혼합하지 않는다. 예를 들어 하나의 페이지에 인덱스와 테이블을 저장한다면 다른 페이지에도 인덱스와 테이블만을 저장한다.

각 페이지에는 고유한 식별자가 부여된다. 만약 데이터베이스가 단일 파일인 경우, 페이지 id가 파일 오프셋일 수 있다. 그에 반해 단일 파일이 아닌 경우, 페이지 id로부터 변환 작업을 거친다. 대부분의 DBMS에는 페이지 id를 파일 경로 및 오프셋에 매핑하는 indirection layer가 존재한다.

데이터베이스에서 파일을 찾는 흐름은 다음과 같다. 우선, 시스템의 상위 수준에서 특정 페이지를 찾기 위해 페이지 번호를 건넨다. 그러면 storage manager는 페이지를 찾기 위해 해당 페이지 번호를 파일과 오프셋으로 변환한다. 이 과정을 용이하게 하기 위해 대부분의 DBMS는 고정된 크기의 페이지를 사용한다.

DBMS에서의 페이지 개념은 3가지가 있다.

• #1. Hardware page (주로 4KB)
• #2. OS page (4KB)
• #3. Database page (512B-16KB)

페이지의 개념을 나누는 이유는 데이터베이스 페이지의 크기에 따른 장단점을 이해하기 위함이다. 아래 그림에서 볼 수 있듯이 데이터베이스 페이지의 크기는 상이하다.

페이지의 크기가 클수록 sequential IO를 빠르게 읽을 수 있기 때문에 얼핏보면 페이지 크기가 16KB로 가장 큰 MySQL이 가장 좋은 선택이라고 생각할 수 있다. 하지만 하드웨어 페이지는 주로 4KB이기 때문에 안정성이 떨어진다. 이게 무슨 말인지 이해하려면 우선 저장 장치가 하드웨어 페이지의 atomic write를 보장한다는 점을 알아야 한다. 예를 들어 하드웨어 페이지가 4KB이고 시스템이 디스크에 4KB를 쓸 때, 4KB가 모두 기록되거나 모두 기록되지 않는 것이 atomic write다. 따라서 하드웨어 페이지보다 데이터베이스 페이지가 큰 경우 atomic write가 보장되지 않기 때문에 시스템이 충돌할 때 디스크에 데이터의 일부분만 저장(ex 8KB 중 4KB)되는 문제가 발생할 수 있다. 이때, DBMS는 데이터가 안전하게 기록되도록 추가 조치를 취해야 한다. 대조적으로 만약 하드웨어 페이지와 데이터베이스 페이지의 크기가 같았다면 실패했다는 에러 메시지가 뜨기 때문에 해당 페이지를 디스크에 다시 쓰면 된다. 요약하자면 페이지의 크기 하드웨어 페이지만큼 작다면 디스크에 데이터를 쓸 때 안정성이 보장된다.

3-1.1 Database Heap

앞서 각 페이지에 고유한 식별자인 page_id가 부여된다고 하였다. 이제 page_id를 가지고 DBMS에서 그 페이지가 어디에 위치해있는지 찾기 위한 구조에 대해 살펴본다.

페이지 저장 아키텍처의 종류는 다음과 같다.

이번 시간에는 그 중 하나인 heap file organization 방법을 배운다. Heap file organization에서 페이지의 순서는 정렬되어 있지 않고 각 페이지 안에 있는 튜플 또한 임의의 순서로 저장되어 있다.

순간 처음엔 Heap 파일 구조라고 해서 binary heap 자료구조 방식으로 페이지가 저장되어 있다고 생각했다. 하지만 페이지의 순서가 정렬되어 있지 않다는 점이 마음에 걸렸다. Binary heap 자료구조는 물론 원소(페이지)들을 완전히 정렬하진 않지만, heap property를 만족하도록 부분적인 정렬은 진행하기 때문이다. 검색해본 결과 힙 파일 구성과 힙 데이터 구조는 완전히 다른 개념이었다.

• heap file organization: 가장 높은 키 페이지에 대한 직접적인 접근을 제공하지 않으며, 페이지 내의 레코드를 순서 없이 저장하고 검색할 수 있는 효율적인 방법. Create / Get / Write / Delete Page 연산을 위해 모든 페이지에 대한 iteration을 지원해야 한다.
• heap data structure: 우선순위 큐를 구현하는 데 사용되며 요소의 우선순위를 효율적으로 관리하는 방법

앞서 각 페이지에는 고유한 식별자가 부여된다고 하였다. 데이터베이스가 단일 파일인 경우, 페이지 id가 파일 오프셋일 수 있다고 하였는데 그 이유는 페이지의 크기가 정해져있기 때문이다.

Storage manager의 역할은 페이지에 읽고 쓴 데이터와 해당 페이지의 여유공간을 추적하는 것이다. 이러한 작업을 위해서, 존재하는 페이지를 추적하기 위해 여유공간이 있는 페이지에 대한 정보가 담긴 메타데이터가 필요하다.

• offset = page # * page size
  

데이터베이스가 단일 파일이 아닌 경우, 오프셋을 구하기 위해 페이지 id로부터 변환 작업을 거쳐야 한다고 하였다.

다만 메타데이터에 여유공간이 있는 페이지에 대한 정보 뿐 아니라 여러 개의 파일에 있는 페이지가 어디에 있는지에 대한 정보가 추가적으로 제공되어야 한다.

Heap file을 저장하기 위한 방법이 두 가지 있다.

• #1. Linked List
  : 헤더 페이지에는 사용 가능한 페이지 목록 및 데이터 페이지 목록에 대한 포인터가 있다. 그러나 DBMS가 특정 페이지를 찾고 있는 경우 DBMS는 찾고 있는 페이지를 찾을 때까지 데이터 페이지 목록에서 순차적으로 검색해야 한다는 단점이 있다.
• #2. Page Directory
  : DBMS는 각 페이지의 여유 공간과 함께 데이터 페이지의 위치를 추적하는 특수 페이지를 유지 및 관리한다. 따라서, linked list에서 발생했던 단점인 페이지의 순차적인 검색을 하지 않아도 된다.
  

이 중 강의에선 linked list의 단점 때문에 page directory 방식만을 다룬다. Heap file을 page directory 방식으로 저장하면 다음과 같은 특징이 있다.

• DBMS는 데이터베이스 파일에서 메타 페이지의 위치를 추적하는 특수 페이지인 디렉토리를 유지 및 관리한다.
• 디렉토리에서 사용 가능한 공간에 대한 메타 데이터를 저장한다.
• 디렉토리 페이지와 데이터 페이지의 동기화를 보장한다.

페이지 디렉토리 방식은 hash table lookup 방식과 유사하다. 따라서 검색에 $O(1)$시간이 걸려 $O(n)$ 시간이 걸리는 linked list에 비해 경쟁력이 있다.

디렉토리 페이지가 어디에 저장되어있는지는 DBMS마다 다르다. 예를 들어, SQLite의 경우 디렉토리 페이지가 파일 자체에 저장되어 있는 반면 postgress에선 여러 개의 파일에 흝어져있다. 이는 SQLite가 하나의 파일만을 저장하는 것과 관련되어 있는 것 같다.

3-1.2 Page Layout

방금까지 페이지의 저장 구조를 알아봤다. 페이지들은 heap file로 저장되어 있으며 heap file의 구현을 위해 디렉토리 페이지를 사용한다.

Header

이제는 페이지 내부에 데이터가 구성되어 있는 방식을 살펴본다. 각 페이지에는 해당 페이지에 대한 메타데이터를 포함하는 헤더 영역이 존재한다. 헤더는 다음과 같은 정보를 포함하고 있다.

• 페이지 크기
• checksum
• DBMS 버전 정보
• transaction visibility
• 압축 정보
  

오라클과 같은 DBMS는 self-contained하다. Self-contained하다는 것은 페이지의 헤더 영역에 테이블, 스키마 등에 대한 메타 데이터를 가지고 있는 것이다. 따라서, 시스템이 손상되었을 때 헤더 영역의 메타데이터를 가지고 데이터를 복구할 수 있다.

Tuple Storage

헤더를 제외한 페이지 내의 영역에 튜플만이 저장되어 있다고 가정을 해본다. 실제로는 인덱스도 존재하겠지만 개념을 이해하기 위해 단순화하였다. 데이터 레이아웃을 가장 단순하게 생각한다면 DBMS가 페이지에 저장한 수를 추적한 후 새 튜플이 추가될 때마다 끝에 추가하는 것이다. 아래의 그림에서 num tuples = 3인 것을 파악하고 튜플의 크기가 일정하다면 그 다음의 위치인 파란 영역에 4번째 튜플을 추가할 것이다.

하지만 튜플을 삭제하거나 튜플의 길이가 가변길이라면 문제가 생긴다. 다음 그림과 같이 삭제한 위치에 새로운 튜플이 추가되는 상황이 이상적이나, 페이지 내에 튜플이 몇 개 존재하는지에 대한 정보만으로는 이 작업이 불가능하다.

이 문제에 대한 해결 방법으로 데이터 레이아웃을 정하는 두 가지 방법이 있다.

• Slotted Pages
• Log-Structured

그 중 이번 강의에선 DBMS에서 가장 많이 사용되는 slotted pages에 대해 다루고 다음 강의에서 log-structured 구조에 대해 다룬다.

Slotted Pages

Slotted pages는 아래의 그림과 같이 slot array의 원소를 각 튜플의 오프셋에 매핑한다.

Slotted pages를 구성 요소별로 더 자세히 알아보자.

• header: 헤더는 사용된 슬롯의 수, 마지막으로 사용된 슬롯의 시작 위치 오프셋을 추적한다.
• slot array: 슬롯 배열은 각 튜플의 시작 위치를 추적한다.

튜플이 추가되는 과정을 살펴보면, 슬롯 배열은 처음부터 끝까지 증가하고 튜플의 데이터는 끝에서부터 시작까지 증가한다. 따라서, slot array와 튜플 데이터가 만났을 때 페이지가 꽉 찼다고 간주한다.

Slot array가 각 튜플의 시작 위치를 추적하기 때문에 튜플의 가변길이 문제를 해결하였다. 그렇다면 튜플을 삭제했을 땐 어떻게 될까?

튜플을 삭제한다면 처음엔 빈 공간이 생기겠지만 DBMS가 한번씩 compaction 과정을 수행함으로써 위의 그림의 세번째 페이지처럼 빈 공간이 사라진다.

3-2. Tuples

이제 페이지 내에서 실질적으로 데이터의 내용을 담고 있는 튜플을 살펴본다. 튜플은 본질적으로 바이트의 시퀀스로 이러한 바이트를 해석하여 타입과 값으로 변환하는 것이 DBMS의 역할이다.

3-2.1 Tuple Layout

Tuple Header

페이지에 헤더가 붙던 것처럼 각 튜플에도 해당 튜플에 대한 메타데이터가 포함된 헤더가 존재한다.

• 튜플의 헤더에 포함되는 내용
  • visibility 정보: Concurrency control을 위한 정보라는데 무슨 내용인지 아직 모르겠다.
  • NULL 값에 대한 비트맵 정보
• 튜플의 헤더에 포함되지 않는 내용
  • 스키마에 대한 정보. 그럼 이 정보는 어디에 저장할지 궁금하다.

Tuple Data

튜플 데이터는 데이터의 속성에 대한 실제 데이터를 포함하는 영역이다. 속성은 일반적으로 테이블을 만들 때 지정한 순서대로 저장된다. 그 이유는 엔지니어링 수고가 덜하기 때문이다. 다른 순서대로 나열하는 것이 더 효과적일 수도 있지만 항상 수고 대비 결과물을 생각해야 한다. 또한 DBMS는 튜플이 페이지의 크기보다 더 큰 상황을 용납하지 않는다.

추가적으로, DBMS에서 하나의 페이지에 하나의 테이블 관련 데이터만 저장하는 것이 통상적이나, 일부 시스템들은 몇개의 테이블로부터의 데이터를 하나의 페이지에 저장하는 것을 허용한다.

3-2.2 Unique Identifier

앞서 각 페이지에는 고유한 식별자가 부여된다고 하였다. 데이터베이스가 단일 파일인 경우, 페이지 id가 파일 오프셋일 수 있는 반면, 데이터베이스가 단일 파일이 아닌 경우, 오프셋을 구하기 위해 페이지 id로부터 변환 작업을 거쳐야 한다고 하였다.

고유 식별자란 하나의 logical tuple이 있는 물리적인 위치를 의미한다. 위치를 파악하기 위해 가장 일반적으론 고유식별자를 page_id + 오프셋/슬롯으로 정의한다. DBMS마다 page_id를 지칭하는 용어가 다른데, PostgreSQL은 CTID, SQLITE와 ORACLE은 ROWID로 page_id를 지칭한다. 예를 들어 CTID는 (0, 1)와 같은 형식으로 (페이지 수, 슬롯 수)를 나타낸다.

하지만 여기서 주의할 점은 물리적인 위치는 vacuum 기능으로 계속 바뀔 수 있기 때문에 page_id로 튜플을 찾는 것은 좋지 않다는 것이다. DBMS는 물리적인 위치와 논리적인 위치를 분리한다. 따라서, 물리적인 위치보다 논리적인 위치로 튜플을 찾는 것이 이상적이다.

3-2.3 Denormalized Tuple Data

두 테이블이 관련된 경우 DBMS는 테이블을 미리 조인할 수 있으므로 테이블은 동일한 페이지에 있게 된다. 이 경우 DBMS가 두 개의 개별 페이지가 아닌 한 페이지에서만 로드되므로 읽기 속도가 빨라진다는 장점이 있다. 그러나 DBMS는 각 튜플에 더 많은 공간을 필요로 하기 때문에 업데이트 비용이 많이 든다. 결국 모든 것은 tradeoff 관계에 있다는 것을 다시 한번 확인하였다.

예를 들어 foo 테이블과 bar 테이블을 살펴보자.

Bar 테이블은 항상 foo 테이블을 레퍼런스하므로 두 개의 테이블이 관련되어 있다는 점을 알 수 있다. 논리적으로 foo 테이블과 bar 테이블은 두 개의 다른 테이블이지만, 물리적으로 두 개의 테이블을 합쳐서 foo 테이블 안에 bar테이블을 embed할 수 있다.

요약

데이터베이스는 페이지로 나뉘어져 있고, 페이지를 추적하고 저장하는 데에 다양한 방법이 있음을 배웠다. 페이지 내에 실질적인 정보를 담고 있는 튜플을 저장하는 방법 또한 다양한 것을 확인하였다.