CMU Databse Fall 2022 를 듣고 정리한 글입니다.
Introduction
DB의 데이터는 대부분 디스크에 저장될 것이지만 데이터를 처리하기 위해서는 이를 메모리로 옮겨야 한다. 문제는 디스크에 접근해서 메모리로 데이터를 올리는 작업이 느리다는 것..
Execution Engine의 입장에서는 모든 데이터가 메모리에 준비되어 있어 메모리/디스크 문제를 신경 쓸 필요가 없어야 한다.
이 문제는 Spatial / Temporal control의 두 문제로 쪼개서 생각할 수 있다.
- Spatial Control은 같이 사용되는 페이지들을 디스크의 물리적으로 가까운 곳에 저장하는 것
- Temporal Control은 페이지에 대한 R/W 의 횟수를 최소화하도록 읽고 쓰는 타이밍을 정하는 것
을 의미한다.
Locks vs Latches
DBMS가 내부 자료구조들을 보호하기 위해 사용하는 locks와 latches의 구분은 아래와 같다.
- Lock: DB의 내용 (tuple, table)을 다른 transaction으로부터 보호하기 위해 사용하는 lock으로 latch 보다 고수준임. rollback 할 수 있어야 함.
- Latch: Lock 보다 저수준에서 internal data structure (hash table, memory region)를 보호하기 위해 사용하며 rollback을 지원하지 않아도 됨
Buffer Pool
Buffer pool은 디스크로부터 읽어온 page에 대한 in-memory cache로 fixed size의 page의 배열이다. 각 array element는 frame 이라고 부르는데, DBMS가 page를 요구할 때 마다 page의 복사본이 buffer pool에 저장된다. DBMS는 page를 요청할 때 buffer pool 부터 검사하며, buffer pool에서 page를 찾을 수 없는 경우 그 때 disk에서 page를 복사해 온다. page에 쓰기 작업을 하는 경우 바로 write-back 하는 것이 아니라, 일단 보류한다.
Buffer Pool Meta-data
Buffer pool은 메타데이터를 같이 저장한다.
- Page Table: page table은 현재 메모리에 존재하는 page를 추적하기 위한 hash table로, page id를 buffer pool 내 frame location에 mapping 시킨다.
- Dirty Flag: 특정 thread가 page를 수정할 때 마다 set 된다. 이를 통해 storage manager가 page를 disk에 쓸 지 말지를 결정할 수 있다.
- Pin/Reference Counter: 현재 page에 access하고 있는 thread의 개수를 추적한다. thread가 page에 access 하기 전에 이 counter를 증가시키며, 이 값이 0보다 크면 storage manager는 page를 evict 하지 않는다.
Memory Allocation Policies
Buffer pool은 두 종류의 policy를 통해 memory를 allocate 한다.
- Global Policy: 전체 workload를 고려하여 memory를 allocation한다.
- Local Policy: 특정 query 혹은 transaction이 더 빨리 처리되도록 한다. 전체 workload의 관점에서는 나쁜 선택을 할 수 있다.
Optimizations
Buffer pool은 application의 workload에 맞게 최적화하는 여러 가지 방법을 갖추고 있다.
- Multiple Buffer Pools: per-database, per-page type 등 여러 개의 buffer pool을 갖고 각 pool이 local policy를 사용하도록 하는 방법으로 latch contetion과 locality를 개선할 수 있다. 이 때 page가 어떤 buffer pool에 mapping 되어야 하는지를 결정하기 위해서는 record ID를 확장하여 buffer pool로 mapping 하거나, page ID로부터 buffer pool로의 mapping을 저장하는 hash table을 갖는 방법이 있다.
- Pre-fetching: DBMS가 많은 page를 순차적으로 접근할 때, page를 pre-fetching함으로써 최적화 할 수 있다.
- Scan Sharing (Synchronized Scan): 여러 query가 동시에 돌아갈 때, query cursor를 공유해서 성능을 향상시킨다.
- Buffer Pool Bypass: sequential scan에서는 buffer pool에 page들을 caching하는 것이 오버헤드만을 유발할 수 있다. 이러한 경우에는 caching을 생략해 성능을 향상시킬 수 있다.
OS Page Cache
대부분의 Disk operation은 OS API를 통해 이루어지고 OS는 자체 Filesystem Cache을 가지고 있는 경우가 많다. 많은 DBMS들은 OS의 cache의 비효율을 피하기 위해 direct IO를 사용한다.
Buffer Replacement Policy
새 page가 fetch 되어 frame을 삽입해야 할 때 buffer pool이 가득 차 특정 entry를 evict해야 할 수 있다. replacement policy는 DBMS가 어떤 frame을 evict할 지를 결정하는 알고리즘으로, correctness, accuray, speed, meta-data overhead를 고려해하여 결정한다.
- LRU (Least Recently Used): 각 page의 last accessed timestamp를 저장해 가장 이전에 접근한 frame을 evict한다. 이 timestamp는 효율성을 위해 별도의 자료구조에 저장될 수 있다.
- CLOCK: CLOCK 은 LRU의 approximation으로 page 별 timestamp를 저장하는 대신, 각 page에 reference bit을 할당한다. page가 할당될 때 마다 해당 bit은 1로 set 되고, eviction이 필요할 때에는 circular 탐색을 하면서 bit이 1인 page는 0으로, 0인 page는 evict 한다.
- LRU-K: LRU/CLOCK의 단점인 sequential flooding (sequential search에서는 가장 마지막에 접근한 element가 제일 필요 없는 데이터)을 해소하기 위해, 마지막 K access 사이의 interval을 통해 page의 다음 reference 시점에 대한 기댓값을 구한다.
- Localization per query: 어떤 page를 evict할 지를 query/transaction 별로 계산해서 각 query가 미치는 영향을 제거한다.
- Priority Hint: 특정 query에서 어떤 page가 중요한지에 대한 정보를 buffer pool에 제공한다.
Dirty Pages
Dirty bit이 set 된 page가 eviction의 대상이 된 경우 두가지 선택지가 있다. 하나는 dirty flag가 set 되지 않은 page를 evict 하는 것, 그리고 나머지는 변경사항을 디스크에 쓰고 나서 evict하는 것이다. 전자를 선택하는 경우, dirty flag가 1인 pag가 다시 read 되지 않는 경우 낭비가 되고, 후자의 경우 write-back이 비싼 operation이라는 점이 문제가 된다.
한 가지 해결책은 background writing으로, 이 방법은 DBMS가 주기적으로 page table을 순회하면서 dirty page를 disk에 쓰고 page를 evict 하거나 dirty flag을 초기화 해 줄 수 있다.
