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)하고, 가장 최근에 사용된 블록으로 지정한다.

시스템이 현재 처리 중인 쿼리에 대해, 이미 알고 있는 정보를 이용하는 것 외에도, 버퍼 관리자는 특정 릴레이션이 참조될 확률에 대한 확률에 대한 통계 정보도 사용할 수 있다. 예를 들어, 데이터 사전(data dictionary)은 쿼리를 처리하기 위해서는 반드시 접근해야 하므로 데이터베이스에서 가장 자주 접근되는 부분 중 하나이다. 따라서 버퍼 관리자는 다른 특별한 이유가 없는 한, 데이터 사전에 대한 블록을 메모리에서 제거하지 않아야 한다. 이는 파일 인덱스(file index)에 대한 블록의 경우도 마찬가지이다.

따라서 이상적인 데이터베이스 블록 교체 전략은 수행 중인 데이터베이스 작업과, 향후 수행될 작업에 대한 지식을 필요로 한다. 하지만 모든 상황을 처리할 수 있는 하나의 전략은 없으며, 이에 따라 대부분의 데이터베이스 시스템이 LRU 전략을 사용한다.

마지막으로, OS나 버퍼 매니저는 성능 최적화를 위해 블록에 대한 쓰기 순서를 재정렬할 수 있다. 하지만 이는 디스크 내에서의 데이터 구조에 문제(corruption)을 유발할 수 있고, 이 때문에 시스템 크래시가 발생할 수 있다. 예를 들어 디스크 내의 블록들의 연결 리스트(linked list)에서 일부 블록이 유실되어 링크(link)가 끊어질 수 있다. 파일 시스템은 이러한 문제를 감지하기 위해서 일관성 검사(consistency check)를 수행하며, 쓰기 순서를 신중하게 관리한다.

Optimization of Disk Block Access

데이터베이스 버퍼는 쓰기 작업을 메모리 상에서 수행하고, 나중에 디스크에 출력할 수 있도록 허용하며, 이 때문에 출력 순서는 쓰기 작업이 수행된 순서와 다를 수 있다. 하지만 이는 디스크 내에서의 데이터 구조에 문제(corruption)을 유발할 수 있고, 이 때문에 시스템 크래시가 발생할 수 있다. 예를 들어 디스크 내의 블록들의 연결 리스트(linked list)에서 일부 블록이 유실되어 링크(link)가 끊어질 수 있다. 파일 시스템은 이러한 문제를 감지하기 위해서 일관성 검사(consistency check)를 수행하는 방법을 사용하곤 했다. 만약 일관적이지 않은 상태라면, 시스템 충돌이 발생한 것이므로 이에 대한 추가적인 작업을 통해 복구한다.

하지만 이는 시스템 충돌 후의 재시작 시간을 매우 길게 만들었으며, 디스크 시스템의 용량이 커짐에 따라 이러한 지연은 더욱 심각해졌다. 시스템 충돌 후의 재시작 시간을 매우 길게 만들었으며, 디스크 시스템의 용량이 커짐에 따라 이러한 지연은 더욱 심각해졌다. 따라서 파일 시스템은 메타데이터(metadata)에 대한 업데이트의 순서를 신중하게 정하여 이러한 문제를 피할 수 있다. 하지만 이러한 방법은 성능 최적화 기법을 적용할 수 없게 되어, 업데이트의 효율성이 떨어지게 된다.

이러한 문제를 해결하기 위해 비휘발성(non-volatile) 쓰기 버퍼가 존재한다면, 업데이트를 해당 버퍼에 순서대로 저장하고, 나중에 디스크에 기록할 때만 순서를 재조정함으로써 문제를 해결할 수 있다. 이는 매우 빠른 쓰기를 지원한다. 하지만, 대부분의 디스크에는 비휘발성 쓰기 버퍼가 존재하지 않는다. 대신, 쓰기 작업을 수행한 순서의 로그(log)를 저장할 수 있는 디스크를 하나 할당한다. 이는 비휘발성 RAM처럼 사용되며, 순차적인 쓰기만 이루어져 매우 그 작업이 빠르다. 또한 트랜잭션 로그를 기록해두므로 이를 시스템 충돌시 복구하는데에 활용할 수 있다.
이와 같이 로그 디스크를 사용하는 파일 시스템을 저널링 파일 시스템(journaling file system)이라고 한다. 대부분의 파일 시스템은 저널링을 지원하며, 파일 할당 정보와 같은 파일 시스템 메타데이터를 기록할 때 로그 디스크를 사용한다. 저널링 파일 시스템은 충돌 후 파일 시스템 일관성 검사가 진행되지 않아도 빠르게 재시작할 수 있게 한다. 이를 통해 시스템 충돌 시에도 데이터가 손상될 위험을 없앨 수 있다.