Buffer

버퍼 매니저는 디스크 매니저의 위, 인덱스 매니저의 아래에 위치하며, 두 레이어 간의 속도 차이(전자는 디스크에서, 후자는 메모리에서 동작하기 때문에 발생한다)를 보완하기 위해 존재한다. RAM에 디스크 파일의 일부를 가지고 있음으로써 디스크 페이지를 메모리에서 접근하는 듯한 성능을 제공한다. 일반적인 “캐시”와 비슷하다. 일반적으로 각 DB 인스턴스마다 DRAM의 80% 정도를 버퍼 풀(pool)로 할당하는 것을 추천한다.

💡 CS 기출문제에 그닥 언급되진 않지만 DBMS 아키텍처에선 나름 중요

Untitled

동작 방법

  1. 인덱스 매니저가 버퍼 매니저에게 “n번 페이지를 읽어줘”라고 부탁한다.
  2. 버퍼 매니저는 현재 버퍼풀에 n번 페이지가 존재하는지 확인한다.
  3. 존재 여부에 따라 디스크I/O를 할지 결정한다.
    • 존재한다면, 디스크에서 읽어올 필요 없이 버퍼 풀에 있는 n번 페이지(정확하게는 n번 페이지를 가리키는 포인터)를 바로 반환한다. 버퍼 풀이 RAM에 있기 때문에 속도가 매우 빠를 것이다.
    • 존재하지 않는다면 디스크에서 n번 페이지를 읽어와야 한다. 느린 디스크 I/O가 소요된다. 디스크에서 읽어온 페이지는 버퍼풀에 저장된다. 이후에 n번 페이지에 대한 요청이 들어온다면 버퍼풀에서 바로 반환할 수 있을 것이다.

Hit Ratio/Cache Miss

원하는 정보가 버퍼에 있다면 적중(hit)했다 하고, 없다면 실패(miss)했다 한다. Hit ratio와 Cache miss 는 중요한 성능 지표(performance metrics)다. 이는 접근 가능성이 낮아보이는 페이지를 교체(replace)하고, 접근 가능성이 높아보이는 페이지들을 프리페칭(prefetching)함으로써 개선할 수 있다(아래 더 자세히…).

컨트롤 블럭

버퍼의 일반적인 구조는 다음과 같다. 각 프레임에 대한 메타데이터를 담는 컨트롤 블럭(Control Block)의 배열 뒤에 실제 페이지를 담을 프레임 배열을 만든다. 컨트롤 블럭에서 프레임을 포인터로 순차적으로 가리킨다. 컨트롤 블럭은 프레임을 가리키는 포인터, 프레임이 현재 담고 있는 페이지넘버, 더티 비트, 핀 카운트 등의 정보를 포함한다.

Untitled

더티 페이지

인덱스에서 페이지를 수정하면 디스크 페이지와 메모리(버퍼 풀)에 있는 페이지에 차이가 생길 것이다. 이를 “더티 페이지(Dirty Page)”라고 한다. 페이지를 수정한 후 컨트롤 블럭에 더티 비트(Dirty bit)를 세워 알 수 있다.

핀 카운트

인덱스에서 페이지를 요청해 읽거나 쓰고있는 도중에 버퍼풀에서 해당 프레임을 없애거나 다른 페이지로 교체하면 잘못된 데이터가 발생한다. 따라서 핀카운트(Pin Count)로 페이지가 현재 사용중임을 알려야 한다. 인덱스가 페이지를 요청할 때 +1을 해주고, 사용 후 반환할 때 -1을 해준다. 핀카운트가 0이 아닌 프레임은 버퍼 매니저가 함부로 조작할 수 없다.

Untitled

(수정한) 동작 방법

  1. 요청한 n번 페이지가 버퍼풀에 존재하지 않는다면:
    1. 핀카운트가 0인 프레임을 고른다. (만약 모두 사용중이라면 대체로 DB가 멈춘다)
    2. 프레임이 “더티”하다면, (디스크 매니저를 통해) 디스크에 페이지를 write해 수정사항을 반영하고 더티 비트를 내린다.
    3. 요청한 페이지를 디스크에서 읽어 프레임에 담는다.
  2. 핀 카운트를 세우고 페이지(를 가리키는 포인터)를 인덱스 매니저에게 반환한다.

페이지 반환

사용이 끝난 페이지를 반환할 때 다음 동작이 필요하다. 버퍼 매니저가 아닌 요청자(즉, 인덱스 매니저)가 처리하는 동작임을 주의.

  1. 페이지가 수정되었다면 더티 비트를 세운다.
  2. (가능한 빨리) 핀카운트를 -1 해준다.

페이지 교체 정책

모든 프레임이 페이지를 담고 있는데 새로운 페이지를 요청할 경우, 기존 페이지 중 하나와 교체해야 한다. 어떤 페이지(Victim)를 쫓아낼지(evict) 정하는 기준을 “페이지 교체 정책(Page Replacement Policy)”이라 한다. 어떤 정책을 고르느냐와 접근 패턴(access pattern)에 따라 I/O 수에 큰 영향을 미칠 수 있다

Least-Recently-Used(LRU), Clock

가장 오래전에 사용이 끝난(즉, 핀카운트가 0이 된) 페이지를 쫓아낸다. 자주 사용하는 페이지를 반복 접근하는 데 좋다. 즉, Temporal locality가 좋다.

Untitled

단, Last Used의 최소값을 찾는 게 상당히 비싸다. 따라서 시계 알고리즘(Clock)을 사용해 LRU를 대충 흉내내는 방법을 사용한다.

Untitled

Clock hand를 하나씩 앞으로 이동하며:
    if 현재 프레임의 핀카운트 > 0:
        skip
    else:
        if 레퍼런스 비트가 1:
            레퍼런스 비트 = 0
            skip
        else:
            이 페이지 "쫓아내기"!
            새로운 페이지로 교체한 후
            레퍼런스 비트 = 1
            핀 카운트 = 1

LRU의 성능이 최악일 때는 버퍼풀보다 큰 파일을 반복 순회할 때이다. “Sequential Flooding”이 발생하고 hit ratio가 0%가 된다.

Untitled

Most-Recently-Used(MRU)

가장 최근에 사용이 끝난(즉, 핀카운트가 0이 된) 페이지를 쫓아낸다. MRU는 위 상황에서 아주 좋은 hit ratio를 갖는다. LRU는 random access를 할 때, MRU는 repeated sequential access를 할 때 성능이 좋다.

Prefetch

페이지가 요청될 때, 곧 사용될 것 같은 근처 파일을 미리 함께 읽어오는 것을 “프리페치(Prefetch)”라 한다. (ex. 1번 페이지를 요청받고 2~5번 페이지도 같이 읽어옴) 랜덤 I/O 오버헤드의 비용을 줄이고, I/O 작업을 백그라운드에서 진행하는 동안 다른 작업을 할 수 있게 한다(디스크와 CPU는 parallel devices임).

💡 이후 목차 중 다음부분은 건너뛰거나 요약할 예정 - SortHash - Relational Algebra - Joins - Query Optimization