Buffer Manager

상위 문서: Data Storage Structures

개요

버퍼 관리자(Buffer manager)란 버퍼 공간의 할당을 담당하는 하위 시스템이다. 데이터베이스 시스템 내의 프로그램들은 디스크에서 블록이 필요할 때, 버퍼 관리자에게 요청(call)을 한다. 이때 버퍼 관리자는 상황에 따라 아래의 행동을 취한다.

• 먼저 버퍼 관리자는 요청된 블록이 버퍼에 저장되어 있는지 검사한다.
• 만약 그 블록이 이미 버퍼에 있다면, 버퍼 관리자는 메모리 내 블록의 주소를 요청자에게 전달한다.
• 만약 블록이 버퍼에 없다면, 버퍼 관리자는 먼저 버퍼에서 해당 블록을 위한 공간을 할당하고, 필요하다면 다른 블록을 제거(evict)하여 공간을 만든다. **제거되는 블록은 마지막으로 디스크에 기록된 이후에 수정된 경우에만 디스크에 다시 기록된다.
  • 그런 다음, 버퍼 관리자는 디스크에서 요청된 블록을 읽어와 버퍼에 저장하고, 메모리 상의 블록 주소를 요청자에게 전달한다.

Pinned Blocks

블록이 버퍼에 올라오면, 데이터베이스 프로세스는 해당 블록의 내용을 메모리에서 읽을 수 있다. 그러나 동시에 다른 프로세스가 해당 블록을 제거하고 다른 블록으로 교체한다면, 읽던 프로세스는 잘못된 데이터를 읽게 된다. 심지어 그 블록이 쓰기 중이던 블록이라면, 새로운 블록의 내용이 손상될 수 있다. 따라서 어떤 프로세스가 블록을 읽기 전에는 해당 블록이 제거되지 않도록 보장해야 한다.
이를 위해, 해당 프로세스는 블록에 대해 pin 연산을 실행하며, 버퍼 관리자는 고정된(pinned) 블록은 제거하지 않는다. 읽기가 끝나면, 프로세스는 unpin 연산을 실행해 해당 블록이 다시 제거될 수 있도록 허용해야 한다. 이때 주의할 점은 너무 많은 블록을 pin하면, 모든 블록이 고정되어 새로운 블록을 버퍼에 불러올 수 없게 된다는 것이다.

여러 프로세스가 동시에 하나의 블록을 읽을 수도 있는데, 이때 각 프로세스는 접근 전에 pin, 종료 후 unpin을 수행해야 한다. 이를 보장하기 위해서 각 블록은 pin count을 가지고 있으며, 이는 pin할 때마다 증가하고, unpin할 때마다 감소한다. 이때 pin count가 0일 때만 블록을 제거할 수 있도록 하여 의도치 않은 오류를 방지한다.

Shared and Exclusive Locks on Buffer

한 프로세스가 페이지에 튜플을 추가하거나 삭제할 경우, 기존 튜플들의 위치가 바뀌는 등 페이지 내용이 이동할 수 있다. 이때 다른 프로세스가 동시에 페이지를 읽으면, 일관되지 않은 데이터에 접근할 수 있다. 그래서 데이터베이스 버퍼 관리자는 shared/exclusive 락(lock)이라는 기능을 제공한다. 이때 락은 다음과 같은 규칙을 지닌다:

• 여러 프로세스는 동시에 shared 락을 가질 수 있다.
• exclusive 락은 오직 하나의 프로세스만 가질 수 있고, 그 동안에는 어떤 shared 락도 허용되지 않는다.
• exclusive 락이 걸린 상태에서는, 다른 프로세스의 모든 락 요청은 대기 상태로 남는다.
• shared 락 요청은, exclusive 락이 없거나, 이미 shared 락만 있는 경우에만 즉시 부여될 수 있다.

또한 락과 pin은 다음과 같은 순서로 동작한다:

1. 블록에 작업을 하기 전에, 먼저 pin을 수행한다.
2. 이후 락을 획득하고, 작업 완료 후 락을 해제하고 unpin을 수행한다.
   • 이때 읽기 전에는 shared 락, 쓰기 전에는 exclusive 락을 반드시 얻어야 한다.

이 규칙을 통해서 읽는 도중 다른 프로세스가 해당 블록을 수정하지 못하게 하고, 반대로 쓰는 중일 때 다른 프로세스가 읽지 못하게 하여 안전한 버퍼 접근을 보장한다. 하지만 이것만으로 모든 동시성 문제를 해결할 수 있는 것은 아니다.

Output of Blocks

블록은 보통 다른 블록을 위해 버퍼 공간이 필요할 때 디스크로 출력된다. 하지만 이런 경우를 기다리지 않고, 수정된 블록을 미리 디스크에 쓰는 것이 좋은 경우가 있다. 이는 나중에 버퍼 공간이 필요할 때 이미 디스크에 기록된 블록은 바로 제거할 수 있기 때문이다.

그러나 데이터베이스를 시스템 충돌로부터 복구 가능하게 하려면, 블록을 디스크에 쓸 시점을 제한해야 한다. 예를 들어, 어떤 복구 시스템은 업데이트 중인 블록은 디스크에 쓰면 안 된다는 것을 강제한다. 이를 구현하기 위해서, 블록을 디스크에 쓰기 전에는 shared 락을 얻어야만 한다. 또한 대부분의 데이터베이스는 수정된 블록을 감지하여 지속적으로 디스크에 쓰는 프로세스를 별도로 운용한다.

어떤 상황에서는, 특정 데이터를 디스크에 확실히 기록하여 일관된 상태를 보장해야 하는 경우가 있다. 이러한 쓰기(write)를 강제 출력(forced output)이라고 한다.

Buffer-Replacement Strategies

버퍼 내에서 저장하는 블록에 대한 교체 전략(Buffer-Replacement Strategies)의 목표는 디스크 접근을 최소화하는 것이다. 범용적으로(gerneral-purpose) 사용되는 프로그램의 경우, 어떤 블록이 참조될지 정확히 예측하는 것은 불가능하다. 따라서 OS는 과거에 참조된 블록의 패턴을 미래에 블록을 참조할 때 사용하는 예측 지표로 사용한다. 이때 일반적으로 사용되는 가정은 최근에 참조된 블록이 다시 참조될 가능성이 높다는 것이며, 이에 따라 버퍼 내의 블록을 교체해야 하는 경우, 가장 오래 전에 참조된 블록이 교체된다. 이러한 접근 방식은 LRU(Least Recently Used) 전략이라고 한다.

LRU는 OS 내에서 사용되는 전략이며, 데이터베이스는 이보다 발전된 방식을 사용한다. 사용자의 데이터베이스에 대한 쿼리는 여러 단계로 이루어지며, 데이터베이스 시스템은 쿼리의 각 단계를 관찰하여 어떤 블록이 필요할지를 사전에 결정할 수 있는 상황이 존재한다. 이러한 특징을 통해 사용되는 블록 교체 전략을 어떻게 개선할 수 있는지를 알아보기 위해, 아래 SQL의 처리를 살펴보자:

select *
from instructor natural join department;

이 요청을 처리하기 위한 알고리즘이 아래와 같다고 가정하자:

for each tuple i of instructor do
    for each tuple d of department do
        if i[dept_name] = d[dept_name]
        then begin
            let x be a tuple defined as follows:
                x[ID] := i[ID]
                x[dept_name] := i[dept_name]
                x[name] := i[name]
                x[salary] := i[salary]
                x[building] := d[building]
                x[budget] := d[budget]
            include tuple x as part of result of instructor ⋈ department
        end
    end
end

이 예제의 두 릴레이션이 별도의 파일에 저장되어 있다고 가정하자. 이 예제에서는 instructor의 튜플 하나가 처리된 후에는 다시 필요하지 않다. 따라서 instructor 튜플이 들어 있는 전체 블록이 처리되었으면, 그 블록은 더 이상 주기억장치에 존재할 필요가 없다. 즉, 최근에 사용되었더라도 해당 instructor 블록은 즉시 메모리에서 제거되어야 한다. 이러한 버퍼 관리 전략을 toss-immediate strategy이라고 한다.

다음으로 department 튜플이 들어 있는 블록을 생각해보자. 우리는 instructor 릴레이션의 각 튜플마다 department의 모든 블록을 한 번씩 조사해야 한다. 어떤 department 블록의 처리가 완료되면, 그 블록은 모든 다른 department 블록이 처리되기 전까지 다시 접근되지 않는다. 따라서 가장 최근에 사용된 department 블록은 나중에야 다시 참조되고, 가장 오래 전에 사용된 department 블록이 곧바로 다음에 참조된다. 이는 LRU 전략의 기본 가정과 정반대이다. 따라서 이 경우에서 최적의 블록 교체 전략은 MRU(Most Recently Used)이다. 즉, department 블록 중 하나를 제거해야 한다면, MRU 전략은 가장 최근에 사용된 블록을 선택한다. 이 전략이 정확하게 작동하기 위해서는, 현재 처리 중인 department 블록을 고정(pin)해야 한다. 마지막 department 튜플 처리가 완료되면, 해당 블록을 고정 해제(unpin)하고, 가장 최근에 사용된 블록으로 지정한다.