[CMU 15-445 Intro to DB Sys] Lec06 Memory & Disk IO

• spatial하게는 함께 사용되는 페이지들을 디스크에서 물리적으로 가깝게 유지하고 싶으며, temporal하게는 디스크에서 읽어올 때 발생하는 stall의 횟수를 최소화하는 것이다.
• 

Buffer Pool

• buffer pool은 디스크로부터 읽어온 페이지들을 보관하는 in-memory cache로서, 커다란 메모리 구역임.
• 이는 array of fixed-size pages로 구성되어 있음. 개별 entry를 Frame이라고 부름. DBMS에서 특정 페이지를 요청하게 되면 exact copy가 frame에 옮겨짐. dirty page는 buffer된 채로 있으며, 즉시 쓰여지지 않음.
• page table: 현재 메모리 상에 있는 페이지들의 현황을 관리함. 주로 fixed-size hash table이 사용되며, page id를 frame location으로 mapping함.
  • 페이지별 Meta-data 또한 페이지테이블에 저장되는데, dirty flag, pin/reference counter, access tracking information이 있음.
• page directory는 page id -> page location in files의 매핑(디스크에 계속 저장되어야 함), page table은 page id -> copy of page in buffer pool frames의 매핑(in-memory이므로 디스크에 쓰이지 않는다!)으로서 완전히 다른 것이다.

  Lock vs Latch

• lock: db의 Logical contents를 다른 Transaction으로부터 보호함. transaction이 이루어지는 동안 작동하며, 바뀐 내용을 rollback할 수 있어야 함.
• latch: DBMS의 데이터 구조를 다른 Thread로부터 보호함. 즉 이는 더 낮은 단계에서 Operation 기간 동안 유지되며, rollback할 수 있을 필요는 없음. 흔히 말하는 Mutex임.

Buffer Pool Optimizations

Multiple Buffer Pools

• buffer pool을 여러 개 사용하면 각각 Local policy를 사용하여 reduce latch contention and improves locality할 수 있다.
• 페이지를 개별 buffer pool에 매핑하는 방법은 두 가지다. 1) object id: record id 내에 object id를 포함시켜서 특정 buffer pool로 매핑하도록 함 2) hashing: page id를 hash하여 buffer pool에 할당함

Pre-Fetching

• 필요할 것 같은 페이지를 미리 buffer pool로 Prefetch해둔다(주로 sequential할 때 사용). sequential scan에서도 가능하며, index data structure 상에서 leaf page를 미리 가져올 수도 있다. 아래와 같은 상황에서 DBMS는 page5가 page5 다음에 있다는 것을 알기 때문에 prefetch할 수 있지만, OS입장에서는 연속되어 있지 않기 때문에 불가능할 것이다.
• 

Scan Sharing

• scan sharing은 Physical level에서 이루어지는데, 한 쿼리가 scan을 하고 싶고 이미 다른 쿼리가 이를 하고 있다면, DBMS는 새로운 쿼리의 cursor를 기존 cursor에 attach한다.
• 그런데 쿼리에 LIMIT 100과 같은 제한이 걸려 있는 경우에는 결과값이 실행시마다 달라질 수 있기 때문에 구현이 어렵다.
• continuous scan sharing에서는 커서 하나가 계속 돌아가고 있고, 쿼리는 이 커서에 "탑승"하고 필요한 데이터를 다 가져가면 "내린다". 하지만 이게 on premise라면 가능하지만 과금되는 서버에 있다면 사용할 수 없다.

Buffer Pool Bypass

• buffer pool에 저장하지 않는다. 디스크에 연속적으로 저장된 large sequence of pages를 읽어들일 때 유용하다.
• 일시적인 경우(sorting, joins)에도 사용가능하다.

Buffer Replacement Policies

Least Recently Used

• 각 페이지별 timestamp를 유지하다가, 가장 오래 전에 access된 페이지를 evict시킴

  CLOCK

• 각 페이지에 reference bit을 만들어 두고, access되면 이를 1로 바꾼다. circular buffer에서 돌면서 bit이 1이면 0으로 바꿔주고, 0이면 evict시킨다.
• LRU와 CLOCK의 공통적인 문제는 sequential flooding이다. 이 문제는 페이지의 접근 빈도를 신경쓰지 않기 때문에 생긴다. sequential scan을 할 때 사실 가장 최근에 access된 것은 앞으로 사용할 가능성이 낮고, 오히려 최근에 access안 된 것이 사용할 가능성이 높은데, buffer에서는 오래 전에 access된 것이 evict되어 버린다.

LRU-K

• 그래서 대안으로 나온 것이 LRU-K다. 각 페이지에 대한 최근 K번의 reference history를 timestamp로 저장하고, interval을 계산한다. 이를 통해 다음 접근이 이루어지는 시기를 추정하고, longest expected interval인 페이지를 evict한다.

  Localization

• query마다 다른 정책을 써서 evict할 페이지를 고른다.

Priority Hints

• query의 힌트를 활용하여 buffer pool에게 어떤 페이지가 중요한지 아닌지 알려준다.

Dirty Pages

• dirty하지 않은 페이지면 그냥 drop해버려도 된다. dirty page면 disk에 이를 write해 주어야 한다.
• dirty writing page를 들고 있다가 나중에 write할지, 아니면 write해 주고 buffer pool에서 evict시킬지를 두고 trade-off가 생긴다.
• 이를 해결하기 위해서는 다른 Thread를 활용한 background writing을 할 수 있다. DBMS가 주기적으로 page table을 체크하면서 dirty page를 디스크에 쓴다.

Disk IO Scheduling

• DBMS에서는 자체 internal queue를 가지고 page read/write request를 관리한다. 이때 priority는 여러 요소에 의해 결정된다.

OS Page Cache

• OS는 자체 Page cache를 갖고 있는데, 대부분 DBMS(PostgreSQL 제외!)들은 direct I/O를 통해 OS cache를 우회한다. 1) redundant copies of pages 2) different eviction policies 3) loss of control on file I/O 때문이다.
• 만약 DBMS가 fwrite로 파일을 불러오게 되면 중간에 OS가 마음대로 flush해버릴 수도 있다. fsync를 사용하면 flush를 하는데 이것이 실패하면 linux에서는 dirty page를 clean이라고 바꿔버리기 때문에 DBMS가 fsync를 다시 call했을 때 fsync가 성공했다고 한다.
• 그렇기 때문에 DBMS 차원에서 무엇을 읽고 쓰는지 완전히 통제해야 한다.