06. 데이터베이스 - Buffer Management

앞서 Disk Space Management와 File Management를 다루었습니다. 

데이터베이스의 입출력 동작을 위해서는 실질적으로 Disk Space Management만 있어도되지만, 더 빠른 검색을 위해 File (Index) Management를 통해 페이지를 관리하도록 하였습니다. 

 

Buffer Management

이때, File Management가 동작하는 RAM과 Disk Space Management가 동작하는 Disk 사이의 속도 차가 매우 크기 때문에 매번 Disk로 I/O작업을 요청하면 오버헤드가 커지게 됩니다.

따라서 두 레이어 사이에 Buffer Management를 추가적으로 두어  Disk와 Memory의 속도차를 메울 수 있습니다.

Buffer management layer의 주요한 역할은 두가지가 있습니다.

1. Cache 역할

최근 접근된 페이지들을 메모리에 담아두고, 해당 페이지가 다시 접근되면 Disk까지 갈 필요 없이 메모리에서 바로 꺼내줄 수 있도록 합니다.

2. Write Buffering

특정 페이지에 새로운 데이터를 Write할 때, 실제 디스크에까지 저장될 때까지는 오랜 시간이 걸립니다. 버퍼 매니저는 중간에서 완충제 역할을 하여 상위레이어에는 빠르게 Write가 완료된 것처럼 보이도록 하고, 실제 Disk에 저장하는 작업은 따로 수행하도록 합니다.

하지만 이렇게 Write를 버퍼에만 저장해놓고 디스크에는 이후에 저장하도록 하면, 버퍼와 디스크에 저장된 페이지 내용에 차이가 생길 수 있는 문제가 있습니다. 이에 대한 해결에 대해서는 이후 다루도록 하겠습니다.

 

위 그림과 같이 RAM에 버퍼를 위한 일정 공간을 마련해놓고, Disk Space, File 레이어 사이에서 접근되는 페이지들을 담아두며, 상위 레이어에게 마치 in-memory에서 동작하는 것과 같은 착각을 줄 수 있습니다.

 

예를 들어 2번 페이지를 Read하고자 한다면, 우선 버퍼에 해당 페이지가 존재하는지 검사합니다.

(이때, 버퍼에서 특정 페이지를 찾는 것은 해쉬테이블 등을 이용해 빠르게 찾을 수 있습니다.)

만약 해당 페이지가 버퍼에 존재한다면 Hit 이고,

찾는 페이지가 버퍼에 존재하지 않는다면 Miss 입니다. 이 경우 디스크에 접근하여 해당 페이지를 읽어온 후 버퍼에 추가합니다. 이렇게 Miss의 경우 디스크에 접근하여 I/O작업을 수행하는 등의 오버헤드가 발생하는데, 이를 Miss Penalty라고 합니다.

 

버퍼매니저에서 해결해야하는 두가지 문제가 있습니다.

1. Dirty Pages 처리

위에서 언급했듯이 쓰기 작업이 일어날 때, Disk에 갔다오는 것은 매우 오래걸리기 때문에 버퍼에만 Wirte를 반영한 후 디스크에는 이후 한꺼번에 모아서 반영하게됩니다. 

이렇게 되면 같은 페이지이더라도 버퍼와 디스크에서의 내용에 차이가 생기게 됩니다. 이런 페이지를 Dirty Page라고 하고 이것을 관리해주어야합니다.

이를 위해 페이지에 Dirty bit을 추가하여 버퍼와 디스크의 내용이 다른 페이지에 대해 이를 체크해둡니다. 

그리고 특정 시기에 Dirty bit이 표시된 페이지들을 한꺼번에 디스크에 반영(Write-back)해줍니다.

2. Page Replacement

버퍼의 용량은 제한되어 있고, 버퍼의 용량보다 디스크의 용량이 훨씬 크기 때문에 디스크의 일부 페이지만이 버퍼에 담겨있을 수 있습니다.

이때 버퍼의 성능을 높이기 위해서는 hit 되는 비율을 높일 수 있는, 더 필요한 페이지를 버퍼에 남겨야합니다.

그리고 다른 곳에서 사용중인 페이지는 버퍼에서 교체하면 안되는데, 이는 페이지에 pin count를 관리하여 해결할 수 있습니다.

교체될 수 있는 페이지들 중에 어떤 것을 교체할지 결정하는 방법에는 다양한 방식이 있습니다.

+) 한 페이지에서 여러 사용자의 Concurrent한 동작이 발생하거나, 디스크에 Dirty page를 반영해주기 전에 시스템에 Crash가 발생하는 등의 경우에 생기는 문제점들은 이후 Concurrency Control, Recovery 파트에서 공부해보겠습니다.

 

Buffer Manager State

Buffer Manager에는 버퍼된 페이지들을 저장하는 Frame들이 존재하고, 이 Frame들에 필요한 meta data를 관리해야합니다.

이 Meta data에는 해당 프레임에 저장된 Page id, Dirty bit, pin count 등이 있습니다.

pin count는 해당 페이지가 몇 군데에서 사용되고 있는지를 나타내며, 해당 페이지를 Read 해갈때 하나씩 올려주고, 사용이 끝나면 하나씩 내려주게 됩니다. 따라서 pin count가 0일때만 해당 페이지를 버퍼에서 지울 수 있습니다.

 

특정 페이지를 버퍼에서 읽어올 때 거치는 과정은 다음과 같습니다. 

1. 해당 페이지가 버퍼에 있는지 확인한다.

• 버퍼에 있다면 버퍼에서 바로 읽어온다.
• 버퍼에 없다면 2번 과정으로 간다.

2. 디스크에서 해당 페이지를 읽어온다.

• 만약 버퍼에 빈 프레임이 있다면 읽어온 페이지를 버퍼에 저장한다.
• 만약 버퍼에 빈 프레임이 없다면 다음의 page replacement 작업을 통해 한 페이지를 버퍼에서 지운다.
  1. 버퍼에 담긴 페이지 중 pin count가 0인 프레임 중 하나를 고른다. (어떤 기준으로 고르는지는 이후 설명)
  2. 만약 해당 페이지에 Dirty bit이 체크되어있다면 디스크에 Write 작업을 통해 반영해준다.
  3. 읽어온 페이지를 해당 버퍼프레임에 넣어준다.

3. 새롭게 버퍼에 넣은 페이지의 pin count를 올려주고 페이지를 리턴한다. 

 

Page Replacement Policy

위의 과정에서 버퍼가 꽉찼을 때, pin count가 0인 프레임 중 하나를 골라 해당 프레임을 버퍼에서 지워버린다고 하였습니다. 그러면 pin count가 0인 프레임 중 어떤 프레임을 골라야할까요? 

기본적인 기준은 hit ratio를 높일 수 있는 프레임을 최대한 남겨야 한다는 것입니다.

이를 위한 두가지 방법이 있습니다.

1. LRU (Least Recently Used)

LRU 방식은 말 그대로 마지막으로 사용한 시점이 가장 오래된 페이지를 지우겠다는 것입니다. 

이는 한참전에 사용되고 이후 사용을 안 한 기간이 오래됐으므로 앞으로도 사용하지 않을 것이라고 생각하여, 이것을 지우는게 hit ratio를 높이는데 좋을 것이라고 예상한 것입니다.

LRU는 특히 가까운 시간내에 같은 페이지를 다시 접근하는 경우가 많은 temporal locality 상황에서 사용하기 적합합니다. 

각 버퍼프레임에 Time stamp 필드를 관리하며 마지막으로 사용된 시간을 기록해둠으로써 구현할 수 있습니다.

2. MRU (Most Recently Used)

MRU는 가장 최근에 사용된 페이지를 지우겠다는 것입니다.

이는 해당 페이지가 최근에 사용되었으니 조만간은 또 다시 사용되지 않을 것이라는 생각이 반영된 것입니다.

MRU는 Repeated Scan 상황(spacial locality)에서 효율적으로 동작합니다.

 

두 방식은 어떤 것이 무조건 좋다기 보다는 각자 더 효율적인 상황이 존재합니다. 하지만 랜덤한 상황에서는 일반적으로 LRU가 더 잘 동작한다고 합니다.

3. Clock Algorithm

Clock 알고리즘은 LRU의 동작을 근사한 알고리즘입니다.

LRU는 정확히 사용된 시간을 저장해두고 가장 사용된 지 오래된 페이지를 고릅니다. 하지만 이것은 얻는 효과에 비해 쓸데없는 오버헤드가 많이 생깁니다. 예를 들어, 매번 timestamp에 대해 min값을 찾아야한다거나 정확한 시간을 저장하기 위해 프레임마다 8byte 의 공간을 사용해야한다는 점 등이 있습니다.

 

따라서 Clock algorithm은 정확한 시간을 계산하는 대신 Approximate하게 LRU를 처리하여 효율을 높일 수 있습니다.

Clock algorithm의 동작은 다음과 같습니다.

1. 각 프레임에 1byte의 Reference bit를 두고, Clock hand는 다음에 살펴볼 프레임을 의미합니다.

2. 페이지의 교체가 필요한 시점에 Clock hand를 하나씩 돌립니다.

• 만약 reference bit이 켜져(1)있는 경우 0으로 변경합니다. (Clock 이 한바퀴 돌 동안 사용된 흔적이 있는 것이므로 교체하지 않습니다.)
• reference bit이 꺼져(0)있고 pin count가 0인 경우 해당 페이지를 교체합니다. (Clock이 한바퀴 돌아오는 동안 한 번도 사용되지 않은 것이므로 LRU 기준에 의해 사용된지 오래되었다고 판단)

Sequential Flooding

LRU는 많은 상황에서 MRU보다 효율적이지만 비효율적인 상황도 존재합니다.

특정 범위의 페이지를 반복적으로 탐색하는 경우를 살펴보겠습니다.

Page1

Page2

Page3

Page4

Page5

Page6

Page7

다음과 같은 7개의 페이지를 반복적으로 접근하는 (1->2->3->4->5->6->7->1->2->3->...) 상황을 생각해보겠습니다.

버퍼는 총 6개의 프레임으로 되어있고, replacement policy는 LRU일 때,

1번 프레임에 1번 페이지가 들어오고 (Miss)

2번 프레임에 2번 페이지가 들어오고 (Miss)

3번 프레임에 2번 페이지가 들어오고 (Miss)

4번 프레임에 2번 페이지가 들어오고 (Miss)

5번 프레임에 2번 페이지가 들어오고 (Miss)

6번 프레임에 2번 페이지가 들어옵니다 (Miss)

여기까지는 처음에 버퍼가 비어있었으므로 어쩔 수 없이 발생하는 Miss였지만, 이제는 Hit 을 통한 버퍼의 효과를 기대할 수 있습니다.

하지만 LRU에 의해 1번 프레임이 7번 프레임으로 교체되고 (Miss)

2번 프레임이 1번 프레임으로 교체되고 (Miss)

3번 프레임이 2번 프레임으로 교체되고 (Miss)

...

이렇게 Hit은 전혀 일어나지 않고 계속 Miss penalty만 발생하게됩니다. 

 

이처럼 Repeated scan 상황에서 버퍼매니저가 가지고있는 프레임의 용량보다 자주 접근되는 데이터의 Set이 더 클 때, LRU에 의해 계속 페이지가 교체되며 Miss penalty만 지속적으로 발생하는 문제를 "Sequential Flooding"이라고 합니다.

이 문제는 MRU를 사용하면 쉽게 해결됩니다.

 

Prefetch

위처럼 LRU는 연속된 페이지가 연속적으로 요청되는 spacial locality 상황에서 문제가 있습니다. 이에 대한 Optimization을 위해 Prefetch 라는 방법을 추가적으로 사용할 수 있습니다.

Prefetch는 한 페이지가 요청되었을 때, Disk Space Manager에게 이후 연속된 몇개의 페이지도 추가적으로 한꺼번에 가져오도록 요청하는 것입니다.

따라서 LRU와 Prefetch를 함께 사용하면 temporal locality와 spacial locality 상황에 모두 잘 대처할 수 있습니다.