데이터베이스 버퍼매니저(BUFFER MANAGER)란 무엇인가?

버퍼 매니저

• 버퍼 매니저는 인덱스와 디스크 사이에 있는 중간 층이다. 파일과 인덱스 관리를 하는데 중간의 추상 계층을 제공한다.

• 버퍼 풀은 페이지 단위의 프레임이라고 하는 것의 집합으로 구성되어 있다. 버퍼 매니저의 주요 역할은 메인 메모리에서 디스크에 저장된 데이터를 조작하는 것이다. 따라서 마치 디스크에 접근하는 것이 아니라, 모든 것이 메인 메모리에서 끝나게 느끼는 것이 목적이다.

• 하지만 실제 모든 데이터 연산은 버퍼 풀과 디스크 사이에 이루어지게 된다. 만약 데이터를 읽고 싶은 요청이 버퍼 매니저에 들어온다면 버퍼 매니저는 디스크 매니저에 다시 요청하게 되며, 버퍼 매니저로 불러온 상태로 데이터를 반환하게 된다.

• 또한 이미 버퍼 매니저에 올라온 데이터를 요청할 경우 디스크 매니저에 요청할 필요없기 바로, 버퍼 매니저에 있는 데이터를 반환하게 된다.

더티 페이지

• 더티 페이지는 메모리에 올라간 데이터와 실제 디스크에 있는 데이터의 내용이 상이한 페이지를 말한다.

• 더티 페이지를 관리하는데는 두가지 중요한 점이 있는데 버퍼 매니저가 더티 페이지를 어떻게 찾아 낼 것 인가에 대한 문제와 더티 페이지를 나중에 디스크에 어떻게 반영할 것인가이다.

• 위의 문제는 동시성 문제와, 리커버리에서 중요하다. 왜냐하면, 더티 페이지가 디스크에 반영되기 전에 시스템이 충돌하면 데이터가 유실 되기 때문이다.

• 버퍼 매니저에서 프레임은 테이블 처럼 관리되며, 페이지 아이디와, 더티 플래그를 가지고 있어서, 디스크에 반영되지 않은 페이지를 확인할 수 있다.

• 또한 버퍼 매니저는 핀 카운트를 통해서 해당 페이지가 사용되고 있는지를 확인할 수 있다. 그리고 버퍼 매니저가 꽉 채워졌을 때는 교체 된다.

페이지 요청 시 버퍼매니저에서 생기는 일

• 1. 핀 카운트가 0인 (사용되지 않은) 프레임을 찾는다.
• 2. 만약 프레임이 더티 상태라면 디스크에 반영하여 깨끗한 상태로 만든다. 그리고 디스크 매니저에게 요청한 데이터를 프레임에 채운다.
• 3. 그리고 핀 카운트를 증가시키고 주소를 반환한다.

• 특정 페이지가 요청 될 것이라고 예상 되면, 미리 디스크로부터 프리 패치한다.

• 4. 요청이 끝나고 나서, 데이터가 변경되면 더티 상태로 만들고, 아니더라도 사용이 끝나면 핀을 해제한다.

페이지 교체

LRU

• 핀을 해제할 때 해제한 시간을 기록하여, 마지막으로 페이지를 사용한 시간을 알려준다.

• 하지만 핀 카운트가 0이면서, 최근에 사용되지 않은 프레임을 찾는데 선형적으로 탐색을 하게 되고 시간이 증가하게 된다. 또한 우선순위 힙 같은 자료 구조를 사용한다고 하더라도, 구조를 유지하기 위해서 LOG(N)의 시간 복잡도를 가진다. 따라서 상수시간에 교체할 페이지를 찾기 위해서는 CLOCK을 사용하게 된다.

CLOCK

• 클락은 시계바늘로 다음에 교체할 페이지를 가리키고 있다. 그리고 각 페이지들은 ref_bit을 가지는데 최근에 참조된 페이지를 나타낸다.

• 위 그림처럼 페이지 7을 찾는 경우 우선 핀이 없는 페이지를 시계 바늘로 순서대로 찾아간다. 그리고 나서, 페이지 3을 가리킬 때 ref_bit가 체크되어있다면 체크를 해제하고 다음 페이지로 넘어간다.

• 만약 ref_bit이 체크되어 있지 않은 페이지라면 해당 페이지를 교체하는 식으로 동작한다. 그리고 해당 페이지의 핀 카운트를 증가시킴과 동시에 ref_bit 또한 체크 한다.

• 이를 코드로 구현한다면 위와 같은 그림으로 보일 것이다.

LRU / MRU 어떤 것이 더 좋은가?

• LRU 알고리즘의 경우 연속적인 플루딩이라고 위의 예제에서 버퍼 매니저에 프레임이 6개 있고 디스크에 페이지가 총 7개가 있다면 순차적으로 읽으며서 공간이 없을 때마다 버퍼 매니저에서 하나를 방출하고 새로 디스크에서 읽어오고 있다.

• 이러한 경우에 캐시 히트율을 0%이고 LRU의 가장 안좋은 케이스이다.

• 연속적으로 반복해서 값을 읽어오는 것은 매우 일반적인 경우이다. 특히 NESTED LOOP에서 반복해서 같은 값을 읽는다.

• 이러한 경우에는 MRU를 사용할 수 있다. MRU는 가장 최근에 사용된 페이지를 교체한다.

• 따라서 버퍼매니저에 1 ~ 6까지 7 페이지를 읽어야 할 때 6을 제거하고 7을 넣는 것이다. 그려면 다시 1 ~ 5까지의 데이터를 읽을 때는 페이지 교체를 하지 않아도 되므로 연속적인 데이터를 읽을 때 페이지 교체가 덜 일어난다.

• 결론은 LRU와 MRU를 같이 사용하는 것이 좋다. 조인을 할 때와 같이 연속적인 데이터에 접근할 때는 MRU를 사용하면 좋고 그 외의 일반적인 경우에는 LRU를 사용하는것이 좋다.

• LRU와 MRU외에도 2Q, LRU-2, ARC와 같은 페이지 교체 알고리즘이 많이 존재한다.

프리 패칭

• 프리 패칭은 연속적인 페이지를 읽을 때 디스크 매니저에서 미리 여러개의 페이지를 요청하는 것이다.

• 랜덤 I/O를 줄일 수 있고, I/O 연산을 많이 줄일 수 있다.

운영체제에 있는 파일시스템으로 버퍼와 페이지를 관리해도 되지 않는가?

• 몇가지 문제점이 있다. 이식성 문제이다 OS 마다 파일 시스템이 달라서 이것이 힘들다.

• DBMS는 강제로 페이지를 디스크로 기록하는 기능이 필요하다. 리커버리 시스템 때문이다.

• DBMS는 자체적으로 페이지 참조 패턴을 예측할 수 있어야 한다. 이는 페이지 교체와 프리 패칭에 영향을 준다. B+TREE의 인덱스는 리프 노드 다음에 연속한 페이지가 있다는 것 을 알 수 있지만, OS의 파일 시스템은 오직 물리적인 연속적인 페이지만 알고 있다. 따라서 데이터 구조를 알지 못해 프리패칭을 하기 힘들다.

참고 문헌

• CS186Berkeley