서론

디스크 기반(Disk-oriented) 데이터베이스의 모든 모듈 중 제일 많은 보틀넥이 발생하는 곳을 고르라고 한다면 버퍼 매니저(Buffer Manager)일 것입니다. 디스크 기반 데이터베이스의 OLTP 처리 성능에 대한 논문에 의하면 TPC-C 시나리오를 기준으로 전체 CPU Instruction 중 버퍼 매니저에 사용된 것이 35%로 제일 많았고, 그 다음이 락(Lock)과 래치(Latch)가 각각 16%를 차지했습니다. 실제 CPU 연산은 7%에 불과한 것을 보면 버퍼 매니저가 데이터베이스 성능에 미치는 영향력은 상당히 크다는 것을 알 수 있습니다.

PostgreSQL도 데이터베이스에 버퍼 매니저가 차지하는 영향도를 잘 알고 있기 때문에 다양한 매커니즘을 도입하여 성능을 개선하였습니다. 이번 포스팅에서는 어떻게 PostgreSQL이 성능 개선을 달성할 수 있었는지 알아보도록 하겠습니다.

Buffer Manager 소개

버퍼 매니저는 PostgreSQL의 공유 메모리와 영구 저장소 사이의 데이터 전송에 대한 관리를 책임집니다. 읽기/쓰기 요청이 발생한 블록을 메모리에 캐싱하여 디스크 I/O를 최소화 하고 적절한 페이지 교체 알고리즘을 통해 캐시 미스가 최소한으로 발생하도록 관리합니다.

PostgreSQL의 백엔드 프로세스(질의 처리를 담당하는 프로세스)가 테이블이나 인덱스 블록에 대한 접근이 필요한 경우 버퍼 매니저에게 요청하게 됩니다. 동작 방식은 아래와 같이 요약할 수 있습니다.

1. 백엔드 프로세스가 접근하려는 블록에 대해 버퍼 태그(데이터 객체의 식별자, 파일 포크 번호, 그리고 블록 번호로 구성된 구조체)를 키로 버퍼 매니저에 접근 요청
2. 버퍼 매니저는 키에 해당되는 블록이 위치한 버퍼 풀의 슬롯(Slot) 번호를 반환
3. 백엔드 프로세스는 반환받은 슬롯 번호로 원하는 블록을 접근

아래 버퍼 캐시의 구조에 대해 알아보면서 더 상세한 동작 방식을 알아보겠습니다.

Buffer Manager 구조

버퍼 매니저는 데이터 파일을 슬롯으로 갖는 배열인 버퍼 풀(Buffer Pool)과 버퍼 태그와 버퍼 풀 슬롯 번호를 각각 키와 값으로 갖는 해시 테이블인 버퍼 맵(Buffer Map)으로 구성됩니다.

버퍼 맵

백엔드 프로세스가 블록에 대한 접근을 위해 버퍼 태그와 함께 요청을 하면, 버퍼 캐시는 우선 버퍼 맵에 해당 버퍼 태그를 키로 갖는 엔트리가 있는지 확인을 합니다. 만약 이미 엔트리가 존재한다면 엔트리에 적힌 버퍼 풀 슬롯 번호를 백엔드 프로세스에게 전달해주면 요청에 대한 처리가 완료됩니다.

엔트리가 없는 경우에는 영구 저장소로부터 버퍼 풀의 비어있는 슬롯에 블록을 읽어와야 하는데 그 부분에 대해서는 아래에서 설명하도록 하겠습니다.

버퍼 풀

버퍼 풀은 디스크로부터 읽어온 블록을 캐싱해 놓는 버퍼 공간 외에도 캐시로서의 역할을 하기 위해 필요한 다양한 정보를 담고 있는데 주요 필드에 대해 모아보았습니다.

• 버퍼 식별을 위한 정보
  • 버퍼 태그: 맵핑되어 있는 블록에 대한 버퍼 태그
  • 버퍼 아이디: 해당 버퍼가 위치해 있는 배열의 인덱스
• 버퍼 사용 정보
  • 핀 개수(Pin Count): 해당 블록을 사용 중인 프로세스 개수; 프로세스가 블록에 접근할 경우 핀 개수를 하나씩 증가, 블록에 대한 접근이 끝나면 하나씩 감소
  • 사용 횟수: 버퍼 풀 슬롯에 올라온 이후 해당 블록이 접근된 횟수
  • 프리 넥스트: 프리 리스트(아래 설명 참고)의 다음 엔트리가 위치한 인덱스
• 버퍼 접근 제어를 위한 락
  • 컨텐츠 락(Contents Lock): 해당 블록 접근에 대한 동시성을 제어하는 락
  • IO 진행중 락(IO in Progress Lock): 해당 블록에 대한 디스크 I/O를 기다리기 위한 락
• 버퍼 상태 정보
  • 더티(Dirty) 플래그: 해당 블록에 새로운 값이 쓰여졌지만 영구 저장소에는 아직 쓰여지지 않은 상태
  • 유효성(Valid) 플래그: 해당 블록을 읽거나 써도 되는지에 대한 상태
  • IO 진행 중 플래그: 디스크 I/O 중인지에 대한 상태

위 필드를 토대로 메타데이터의 상태를 아래 3가지로 표현하게 됩니다.

• 비어있음(Empty): 슬롯에 블록이 없음 (즉, 핀 개수 0, 사용 횟수 0)
• 핀 꽂음(Pinned): 슬롯에 블록이 있고 프로세스가 사용 중 (즉, 핀 개수, 사용 횟수 모두 1 이상)
• 핀 해제(Unpinned): 슬롯에 블록은 있는데 아무 프로세스도 사용 중이지 않음 (즉, 핀 개수 0, 사용 횟수 1 이상)

프리 리스트

프리 리스트는 비어있는 메타데이터 슬롯을 연결해놓은 리스트입니다. 새로운 블록을 버퍼 풀에 읽어 올릴 때 어떤 슬롯이 비어있는지 탐색을 하기엔 성능 저하가 발생할 수 있습니다. 그래서 새로운 블록을 올릴 때 프리 리스트의 첫번재 엔트리를 꺼내서 빠르게 탐색없이 사용할 수 있도록 관리하게 되어 있습니다.

프리 리스트로부터 꺼내온 메타데이터는 가리키는 블록이 실제로 사라지지 않는 이상 다시 프리리스트로 돌아가지 않습니다. 아래와 같은 일이 발생하는 경우에는 메타데이터의 상태가 “비어있음”으로 변경되고 프리 리스트에 반환되게 됩니다.

1. 테이블 또는 인덱스가 삭제된 경우
2. 데이터베이스가 삭제된 경우
3. VACUUM FULL 명령어로 테이블 또는 인덱스가 정리된 경우

버퍼 풀

버퍼 풀은 데이터 파일 블록을 저장하기 위한 배열이며 각 슬롯의 크기는 8KB로 블록의 크기와 동일합니다.

디스크에서 새로운 블록 읽어오기

이 단계에서 버퍼 캐시가 처음으로 새로운 블록을 읽어올 때의 동작 방식을 설명하겠습니다. 첫 블록을 읽어온 후 하나의 프로세스만 블록을 접근하는 경우는 동작 방식이 거의 동일하지만, 여러 프로세스가 동시에 같은 블록을 접근할 때나, 버퍼 풀에 비어있는 슬롯이 없는 경우 등 조금 더 복잡한 상황에서는 추가로 동작하는 메커니즘이 있기 때문에 그 부분은 아래 섹션에서 설명하도록 하겠습니다.

새로운 블록을 읽어오는 동작 방식은 아래 단계로 요약할 수 있습니다.

1. 프리 리스트로부터 비어있는 메타데이터 슬롯을 구한 후 버퍼에 핀 꽂음
2. 버퍼 테이블에 블록의 버퍼 태그와 슬롯 인덱스를 담은 새로운 엔트리 추가
3. 디스크로부터 핀 꽂은 버퍼 풀 슬롯에 블록 로딩
4. 메타데이터에 읽어온 블록에 대한 정보 저장

버퍼 캐시의 락 관리

버퍼 캐시는 다양한 목적을 위해 락 매커니즘을 사용합니다. 간략하게 나열하면 아래와 같습니다.

1. 버퍼 테이블 락: 버퍼 테이블 수정 시 동시성을 보장하기 위한 락
2. 버퍼 메타데이터 컨텐츠 락: 버퍼 캐시 구조 설명 참고
3. 버퍼 메타데이터 IO 진행중 락: 버퍼 캐시 구조 설명 참고

버퍼 테이블 락

버퍼 테이블의 데이터 정합성을 보장하기 위해 버퍼 테이블 락을 사용합니다. 버퍼 테이블 락은 공유잠금(Shared)과 배타잠금(Exclusive) 모드로 제공되는데 백엔드 프로세스가 버퍼 테이블을 조회할 때는 공유잠금 모드로, 버퍼 테이블을 수정할 때는 배타잠금 모드로 사용합니다.

전체 버퍼 테이블에 대해 배타잠금 모드로 해시 테이블을 수정하려고 하면 락 컨텐션이 많이 발생할 수 밖에 없습니다. 그래서 PostgreSQL에서는 버퍼 테이블 락을 파티션으로 나눠서 관리합니다(기본 값은 128개의 파티션). 파티션으로 나눠 관리하면 여러 백엔드 프로세스가 동시에 버퍼 테이블을 수정하더라도 수정하려는 엔트리가 다른 파티션에 있다면 서로 기다릴 필요 없이 수정할 수 있게 됩니다.

버퍼 메타데이터 락

백엔드 프로세스가 버퍼 캐시로부터 반환받은 슬롯 번호로 버퍼에 접근할 때도 동시성에 대해 고려해야 합니다. 이 때 사용하는 락이 컨텐츠 락입니다. 백엔드 프로세스가 블록을 읽으려고 할 때는 공유잠금 모드로 읽습니다. 단, 아래의 경우에는 배타잠금 모드로 블록에 접근합니다.

• 튜플(Tuple)을 삽입하거나 t_xmin, t_xmax와 같은 필드를 수정하는 경우
• 튜플을 물리적으로 지우거나 가용 공간을 컴팩션해야 하는 경우
• 튜플을 프리즈(Freeze)해야 하는 경우

I/O 진행중 락은 블록의 디스크 I/O이 진행되는 동안에는 접근을 막기 위해 필요합니다. 따라서 프로세스가 블록을 디스크에 쓰거나 디스크로부터 읽어올 때 배타잠금 모드로 메타데이터에 대한 다른 프로세스의 접근을 막아놓습니다.

버퍼 캐시 동작 방식

이제 버퍼 풀에 있는 블록에 접근하는 것부터 비어있는 슬롯에 블록을 로딩하거나 버퍼 풀에 비어있는 슬롯이 더이상 없을 때 페이지 교체(Page Replacement) 알고리즘을 사용하여 버퍼 풀에서 쫓아낼 블록을 찾는 것까지 다양한 상황에서 버퍼 캐시가 어떻게 동작하는지 확인해보겠습니다.’

버퍼 풀에 있는 블록에 접근하기

제일 간단한 상황부터 시작하겠습니다. 백엔드 프로세스가 접근하려고 하는 블록이 이미 버퍼 풀에 있는 경우 버퍼 캐시는 아래와 같이 동작합니다.

1. 백엔드 프로세스가 전달한 버퍼 태그를 키로 해시값 획득
2. 엔트리를 담고 있는 파티션에 대해 버퍼 테이블 락을 공유잠금 모드로 획득
3. 찾은 엔트리로부터 버퍼 풀 슬롯 번호 획득
4. 해당되는 버퍼 메타데이터 슬롯에 핀 꽂음(즉, 핀 개수와 사용 횟수를 하나씩 늘림)
5. 버퍼 테이블 락 해제
6. 버퍼 풀 슬롯에 접근
7. 블록 사용 전 컨텐츠 락 획득
8. 블록 사용이 끝나면 컨텐츠 락과 핀 해제

7번에서 컨텐츠 락 획득 시 블록을 읽기만 할 때는 공유잠금 모드로, 블록에 튜플을 삽입하거나 업데이트를 하는 등 쓰기를 한다면 배타잠금 모드로 락을 획득합니다. 그리고, 쓰기가 완료되면 더티 플래그를 켜주어 백그라운드 라이터(Writer) 프로세스가 더티 블록을 디스크에 플러시(Flush) 할 수 있도록 해줍니다.

버퍼 풀에 찾는 블록이 없어 비어있는 슬롯에 로딩하기

이번에는 백엔드 프로세스가 접근하려고 하는 블록이 버퍼 풀에는 없지만 프리 리스트에 비어있는 슬롯이 있어서 디스크로부터 블록을 로딩하여 백엔드 프로세스에 전달해주는 동작을 살펴 보겠습니다.

1. 버퍼 테이블에 버퍼 태그로 엔트리 탐색 시도(실패)
2. 프리 리스트에서 비어있는 슬롯 획득하여 핀 꽂음
3. 버퍼 태그가 해당되는 버퍼 테이블 파티션에 대해 배타잠금 모드로 락 획득
4. 버퍼 테이블에 새로운 엔트리 추가(키: 버퍼 태그, 값: 새로 획득한 슬롯 번호)
5. 접근하려는 블록을 비어있는 슬롯에 로딩
   1. 해당 슬롯에 대한 메타데이터에 I/O 진행중 락 획득하고 I/O 진행중 플래그 설정
   2. 접근하려는 블록을 디스크로부터 읽어와 슬롯에 씀
   3. I/O 진행중 플래그 해제, 유효성 플래그 설정
   4. I/O 진행중 락 해제
6. 버퍼 테이블 락 해제
7. 블록 접근

버퍼 풀에서 블록을 쫓아내고 필요로 하는 블록을 로딩하기

마지막으로 프리 리스트에 더이상 비어있는 슬롯이 없어서 “필요없는” 블록을 필요로 하는 블록으로 교체하는 동작을 살펴 보겠습니다.

1. 버퍼 테이블에 버퍼 태그로 엔트리 탐색 시도(실패)
2. 페이지 교체 알고리즘을 사용하여 교체할 슬롯 선택
3. 교체할 슬롯의 블록이 더티 블록인 경우 디스크 플러시
4. 교체할 슬롯의 메타데이터에 저장된 버퍼 태그로 버퍼 테이블을 탐색해 예전 엔트리가 담긴 파티션에 배타잠금 모드로 락 획득
5. 백엔드 프로세스가 전달한 버퍼 태그로 해당되는 버퍼 테이블 파티션에 배타잠금 모드로 락 획득 후 새로운 엔트리 추가
6. 새로운 엔트리 추가 완료 후 예전 엔트리를 버퍼 테이블에서 삭제하고 예전 파티션에 대한 락 해제
7. 교체할 슬롯을 필요로 하는 블록으로 덮어 씌우고 메타데이터에 관련 정보 설정
8. 새로운 엔트리 파티션에 대한 버퍼 테이블 락 해제
9. 로딩한 블록에 접근

페이지 교체 알고리즘

다양한 페이지 교체 알고리즘 중 PostgreSQL은 클럭 스위프(Clock Sweep) 알고리즘을 택하여 사용하고 있습니다(8.1 버전 이후이며 이전에는 LRU 알고리즘 사용). 클럭 스위프는 NFU(Not Frequently Used) 방식의 변종으로 자주 사용되지 않는 블록을 효율적이게 선택할 수 있게 해주는 알고리즘입니다.

방식은 버퍼 풀에 있는 슬롯을 순회하며 핀 개수와 사용 횟수를 사용해 적절한 대상자를 찾는 것입니다. 순회할 때 각 슬롯에 대한 선택 여부 조건은 아래와 같습니다.

1. 핀이 꽂혀 있는 슬롯은 건너 뜀
2. 핀이 해제되어 있는데 사용 횟수가 1 이상인 슬롯은 사용 횟수를 하나씩 감소
3. 핀이 해제되어 있고 사용 횟수도 0인 슬롯은 대상자로 선택

위 방식을 사용하면 핀이 해제되어 있는 슬롯이 하나 이상 있을 시 항상 교체 대상자를 찾을 수 있습니다.

지금까지 PostgreSQL의 Buffer Manager에 관해 알아보았습니다

‘PostgreSQL의 WAL(Write Ahead Log)’를 바로 이어서 확인해보세요!