[DB] 13-5. Database Buffer

Main Memory의 크기가 시간이 지나면서 커지면서 중간 사이즈(medium-sized) DB들이 메모리에 들어갈 수 있게 됐다.
하지만, 서버는 memory에 많은 것을 요구(demand)하기 때문에 DB에게 줄 수 있는 메모리의 공간은 DB의 크기보다 훨씬 작을 수 있다.

그래서, DB의 데이터들은 주로 Disk에 저장되고 데이터를 읽거나 수정할 때 메모리로 가져온다.
물론, 수정된 데이터 블록은 다시 디스크에 반영이되야 한다.

디스크에 접근하는 건 in-memory에 있는 데이터에 접근하는 속도보다 느리기 때문에
DB 시스템의 주요 목적은 디스크와 메모리 사이의 블록을 전송하는 횟수를 최소화하는데 있다.

이를 위한 방법 중 하나로 최대한 많은 블록을 main memory에 저장하는 방법이 있다.
즉, 데이터 블록을 필요로 할 때 마다 main memory에 이미 데이터가 있어서 디스크에 접속하지 않아도 될 확률을 높이는 것이 중요하다.

모든 데이터를 main memory에 저장하는 건 불가능하기 때문에 우리는 main memory에서 사용할 수 있는 공간 할당을 관리해야 한다.

Buffer는 디스크 블록의 복사본을 저장하기 위해서 사용가능한 main memory의 일부분이다.
버퍼 공간의 할당을 책임지는 하위 시스템(sub-system)을 buffer manager라고 부른다.

1. Buffer Manager

DB 시스템에 있는 프로그램들은 disk에서 block을 필요로 할 때 buffer manager에게 요청한다.

• 이미 block이 buffer에 있는 경우 ⇒ buffer manager는 요청한 프로그램에게 main memory에 있는 블록의 주소를 전달
• 없는 경우
  1) buffer manager가 새로운 블록을 저장하기 위해서 공간을 할당 (필요하다면 기존에 있던 블록들을 disk로 이동시킨다)
  2) 요청받은 block을 디스크에서 버퍼로 읽어온 다음에 main memory에 저장한 주소를 요청한 프로그램에게 전달한다

이러한 buffer manager의 내부 동작은 disk-block 요청이 발생했을 때 자연스럽게 발생한다.

1.1 Buffer Replacement Strategy

buffer에 공간이 남지 않았을 때, block을 버려야 한다. 대부분의 OS는 LRU(Least Recently Used) 방식을 사용한다.
가장 최근까지 사용되지 않은 블록을 다시 disk로 보내고 buffer에서 제거하는 방식이다.
DB application을 위해 이러한 간단한 접근법을 개선할 수 있다.

1.2 Pinned blocks

블록을 읽고 쓸 때 이런 상황이 펼쳐질 수 있다.

1) A라는 블록을 읽고 있는데 동시에 다른 process에서 해당 블록을 버리고 다른 블록으로 교체 ⇒ 읽고 있던 process는 새롭게 교체된 블록이 아닌 이전 블록을 읽었기 때문에 정확하지 않은 데이터를 읽게 된다.

2) B라는 블록에 쓰기 작업을 하고 있는데 다른 process에서 해당 블록을 버리고 다른 블록으로 교체 ⇒ 그러면, 교체된 블록에 쓰기 작업이 수행되다보니 해당 블록의 내용에 손상(damage)을 가할 수 있게 된다.

따라서, process가 buffer에서 데이터를 읽기/쓰기 전에 해당 block이 버퍼에서 삭제되고 다른 블록으로 교체되지 않는다는 걸 확인해줘야 한다. 이를 위해서 process는 대상이 되는 block에 pin이라는 operation을 수행한다. 이러면 buffer manager가 절대로 해당 블록을 버리고 다른 블록으로 교체하는 작업을 수행하지 않는다.

읽기/쓰기 작업이 완료되면 반드시 unpin 연산을 수행해줘야 한다. unpin을 해주지 않으면 많은 block에 pin이 수행되면서 교체작업을 할 수 없게 되버리기 때문이다.

block이 pin인지 unpin 상태인지 확인하는 간단한 방법은 pin count을 이용하는 것이다.
pin 연산이 수행되었다면 count를 증가시키고 / pin 연산 이후에 unpin을 실행했다면 pin count값은 0이 된다.

따라서, pin count 값이 0이 될 때만 해당 블록을 버퍼에서 삭제하고 다른 블록으로 교체하는 작업을 수행할 수 있다.

1.3 Shared and Exclusive Locks on Buffer (공유 lock, 배타 lock)

블록 (또는 page)에서 튜플을 더하거나 빼는 프로세스는 해당 페이지의 내용을 옮겨야 하는 상황이 발생한다.
이 작업이 진행되는 동안 다른 프로세스들은 해당 페이지에 있는 내용을 읽어들이면 안된다. 왜냐하면 page 자체의 일관성이 없기 때문이다. Buffer Manager는 프로세스들이 버퍼에 대해 공유락과 배타락을 얻을 수 있도록 해야 한다.

이에 대해서는 17, 18장에서 좀 더 자세히 다룰것이다.

1.4 Output of blocks

버퍼 공간이 다른 block을 위해 필요할 때에만 블록을 출력하는 것이 가능하다.
그러나 버퍼 공간이 필요해질 때까지 기다리는 것이 아니라, 버퍼 공간이 필요하기 전에 업데이트된 블록을 미리 기록하는 것이 더 의미가 있다. 그래서, buffer에서 공간이 필요할 때 pin 연산이 수행되지 않았다면 이미 작성했던 블록을 evicted(해당 블록을 디스크에 쓰고 버퍼에서 제거하는 일)할 수 있다.

하지만, 충돌(crash)로 부터 복구 가능한 DB 시스템을 위해서 블록이 다시 disk에 작성되는 횟수를 제한하는 것이 필요하다.

ex) 대부분의 복구 시스템 ⇒ block에 대한 업데이트가 진행 중이라면 그 block이 디스크에 작성되지 못하도록 한다.

이를 강요하기 위해서 block을 disk에 작성하고 싶어하는 process는 반드시 block에 대한 공유 lock을 얻어내야 한다.

1.5 Forced output of blocks

19장에서 좀 더 자세히 다룰 것이다.

2. Buffer-Replacement Strategies

버퍼에서 block에 대한 Replacement 전략의 목적은 디스크에 접근하는 횟수를 최소화하기 위함이다.

OS는 미래에 어떤 block이 참조될 지는 알 수 없기에 과거의 기록을 통해 어떤 block이 참조될 지 예측하려고 한다.
그 가정은 다음과 같다.

가장 최근까지 참조되어왔던 블록은 다시 참조될 가능성이 크다 

따라서, block을 교체해야 한다면, 가장 오래전에 참조되었던 블록을 교체한다. 이러한 접근법을 LRU(Least Recently Used)라고 한다.

DB 시스템에 대한 사용자 요청은 몇 가지 단계를 포함한다. 그래서, DB 시스템은 각각의 단계에서 어떤 블록을 필요로 할지 미리 결정할 수 있다.

그래서 OS와는 달리 DB 시스템은 가까운 미래와 관련된 정보를 가질 수 있다.

ex) SELECT * FROM instructor NATURAL JOIN department;

• 가정
  1) 예시로 든 쿼리문을 처리하기 위한 전략으로 아래의 의사코드를 이용했다. (더 효율적인 방법은 15장에서 다룬다)
  2) 예시로 든 2개의 relation이 별도의 파일에 저장되어 있다

이 예시에서 instructor의 튜플의 처리가 끝나면, 그 튜플을 다시 필요로 하지는 않는다.
따라서, instructor의 튜플의 전체 블록의 처리가 끝나면 그 블록은 더이상 Main Memory에서 필요로 하지 않는다.

Buffer Manager는 instructor 블록의 마지막 튜플의 처리가 끝나자마자 instructor 블록에 의해 차지되던 공간을 해제(free)하도록 명령을 받는다. 이러한 buffer-management 전략을 toss-immediate 전략이라고 한다.

이번에는 department 튜플을 포함하는 block을 생각해보자.

각각의 instructor relation의 튜플마다 department 튜플의 모든 블록을 한 번씩 검사해야한다.
이 내용은 아래의 의사코드를 보면 알 수 있는데 각각의 instructor의 튜플마다 department relation과 NATURAL JOIN 관계가 있는지를 살펴봐야 하기 때문이다.
department 블록의 처리가 완료되면, 해당 블록은 다른 모든 department block이 처리될 때까지 다시 접근할 수 없다.

즉, 가장 최근에 참조된 department block은 가장 마지막에 재 참조될 블록이 되고 가장 최근에 사용되지 않은 department block은 바로 다음에 참조될 블록이 된다.

이를 LRU 전략과 정반대인 MRU(Most Recently Used) 전략이라 한다.
만약에 department 블록이 버퍼로 부터 제거되어야 한다면, MRU 전략을 통해 가장 최근에 사용된 블록을 선택해서 교체한다.
왜냐하면, 가장 마지막에 재참조될 블록이기 때문이다.

이 예시에서 MRU 전략이 효율적으로 동작하기 위해서는 시스템이 현재 실행되고 있는 department 블록을 pin해야 한다.
그 블록의 마지막 department 튜플이 실행되고 나면, 블록을 unpin하게 되고 해당 블록은 가장 최근에 사용된 블록(MRU block)이 된다.

또한 Buffer Manager는 request가 특정 relation을 참조할 확률에 대한 통계 정보를 사용할 수 있다.

ex) Data Dictionary

DB에서 가장 많이 접근하는 곳 중 하나가 Data Dictionary이다. 왜냐하면, 모든 쿼리들을 프로세싱할 때 data dictionary가 필요하기 때문이다. 따라서, Buffer manager는 별다른 이유가 없다면 data-dictionary 블록을 main memory에서 제거하지 않는다.

이상적인 DB의 block 교체 전략은 DB의 연산에 대한 지식을 필요로 한다. 현재 수행되는 연산과 미래에 수행될 연산에 대한 지식을 필요로 한다. 모든 가능성을 다룰 수 있는 단 하나의 전략은 없다. 그리고 굉장히 DB 시스템은 LRU의 결함이 있더라도 LRU를 사용한다.

Buffer manager가 block 교체를 위해 사용하는 전략은 해당 블록이 다시 참조될 횟수 외에도 다른 요소들에 의해 영향을 받는다.
이에 대해서는 Chapter 18, 19에서 다루도록 하겠다.

3. Reordering of Writes and Recovery

DB 버퍼가 in-memory에서 쓰기 작업을 수행하고 disk에 출력할 때 쓰기 작업의 순서와 다른 순서로 출력될 수 있다.
마찬가지로 파일 시스템은 정기적으로 쓰기 연산의 순서를 재정렬한다.

이러한 재졍렬(Reordering)은 시스템 충돌(System crash) 과정에 있어 디스크에 있는 데이터의 불일치성을 야기한다.

재정렬과 관련해 파일 시스템에서 발생하는 문제를 이해해보자.

• 가정
  1) 파일 시스템이 어떤 블록이 파일의 일부분인지 추적하기 위해 연결 리스트를 사용한다.
  2) 연결리스트는 새로운 노드를 리스트의 마지막에 삽입한다. 처음에는 새 노드에 데이터를 쓰고 이전 노드에 대한 포인터를 업데이트한다.
  3) 쓰기 작업이 재정렬되면 처음에 포인터를 업데이트하고 새 노드 앞에 시스템 충돌(system crash)을 작성한다.

이러한 과정을 지나면 노드들의 content는 이전에 disk에서 무슨 일이 발생하던지 간에 결과적으로 망가진 자료구조가 되버린다.

이렇게 자료구조가 망가질 가능성을 다루기 위해서
초기 세대의 파일 시스템은 시스템을 재시작할 때 파일 시스템 일관성 확인을 통해 자료구조가 일관성(consistent)있는지 확인했다.
만약, 일관성 있지 않다면, 일관성을 복구하기 위한 추가적인 단계를 수행했다.
이러한 확인 과정은 충돌이 발생한 이후의 시스템을 재시작했을 때 delay가 길어지는 결과를 초래했고 disk 시스템의 용량이 커지면서 delay는 점점 더 길어졌다.

파일 시스템은 메타데이터 업데이트를 신중하게 선택한 순서대로 기록함으로써 많은 경우에 일관성 문제(inconsistencies)를 피할 수 있다. 그러나 이렇게 하면 disk arm 스케줄링과 같은 최적화가 수행되지 않아 업데이트의 효율성에 영향을 줄 수 있다.
비휘발성 쓰기 버퍼가 있다면 비휘발성 RAM으로 쓰기 작업을 수행한 후 쓰기 작업을 디스크에 기록할 때 쓰기 작업을 재정렬할 수 있다.

그러나 대부분의 디스크는 비휘발성 쓰기 버퍼가 없다. 대신 현대적인 파일 시스템은 쓰기 작업의 순서대로 쓰기 작업 로그를 저장하기 위해 디스크를 할당한다. 이러한 디스크를 로그 디스크(log disk)라고 한다. 각 쓰기 작업에 대해 로그는 쓰여질 블록 번호와 쓰여질 데이터를 쓰기 작업을 수행한 순서대로 포함하고 있다. 로그 디스크로의 모든 접근은 순차적이며 검색 시간을 사실상 제거하며 연속된 여러 블록을 동시에 쓸 수 있어 로그 디스크로의 쓰기 작업은 무작위 쓰기 작업보다 몇 배 빠르다.

여전히 데이터는 실제 디스크 위치에 써야 하지만 실제 위치로 이뤄지는 쓰기 작업은 나중에 수행될 수 있다. 쓰기 작업은 disk-arm의 이동을 최소화하기 위해 재정렬될 수 있다.

시스템이 실제 디스크 위치로의 일부 쓰기 작업을 완료하기 전에 충돌이 발생했다면, 시스템이 다시 시작될 때 시스템은 로그 디스크에서 완료되지 않은 쓰기 작업을 찾아내고 해당 작업을 실행한다. 쓰기 작업이 완료되면 record는 log disk에서 삭제된다.

위에서 설명한 log disk를 지원하는 파일 시스템을 journaling file system이라고 한다. journaling file system은 독립된 로그 디스크 없이도 구현할 수 있으며 데이터와 로그를 동일한 디스크에 유지한다. 이렇게 하면 performance을 희생하고 비용을 절감할 수 있다.

대부분의 현대 파일 시스템은 journaling을 구현하며 파일 할당 정보와 같은 파일 시스템 메타데이터를 작성할 때 log disk를 사용한다. Journaling file system은 파일 시스템 일관성 검사가 필요로 하지 않기 때문에 빠르게 재시작할 수 있도록 한다다.

그러나 application에서 수행하는 쓰기 작업은 일반적으로 로그 디스크에 기록되지 않는다. 대신 데이터베이스 시스템은 장애 발생 시 데이터베이스의 내용을 안전하게 복구할 수 있도록 자체 형식의 로깅을 구현한다. 이에 대해 19장에서 자세히 다루도록 하겠다.