PostgreSQL의 메모리 레이아웃과 데이터를 읽어오는 과정

개요

• 서버의 가장 중요한 역할은 효율적으로 데이터를 관리하는 데 있다고 생각한다.
• 그러므로 데이터가 어떻게 관리되고, 클라이언트에게 어떠한 과정을 거쳐 데이터를 전달하는지를 이해하는 것은 매우 중요하다.
• 이번 글에서는 PostgreSQL의 메모리 레이아웃과 데이터를 읽어오는 과정에 대해 알아보고자 한다.

 

먼저 PostgreSQL에서의 메모리 레이아웃부터 살펴보자

 

Logical Layout 과 Physical Layout

• PostgreSQL의 Logical Layout과 Physical Layout을 비교해 보자.

• 이전 글(PostgreSQL Logical Structure)에서 알아보았듯이 Tablespace 별로 여러 데이터 베이스의 테이블이 구성된다.
• 또한, 실제 데이터베이스는 $PGDATA/base/{데이터베이스의 OID} 에 디렉토리 형태로 저장된다.
  • 따라서 Logical Layout는 Physical Layout의 디렉토에 해당된다.
• 해당 디렉토리에는 $PGDATA/base/{데이터베이스의 OID}/{테이블의 OID} 라는 파일명으로 Heap File이 존재하며 Heap File안에는 8KB 크기의 페이지(블록)으로 구성되어 있다.

PostgreSQL에서 'Heap File'이라는 용어는 데이터의 물리적인 저장 방식을 의미한다. 여기서 'Heap'이라는 단어는 데이터가 메모리나 디스크 상에서 정렬되지 않은, 일종의 무질서한 더미(pile) 형태로 저장된다는 것을 뜻한다.

 

Page Layout

PostgreSQL에서 페이지는 디스크 상의 데이터 저장 단위이며 블록이라 부른다. 페이지는 기본적으로 8KB의 크기를 가지며, 페이지를 통해서 테이블과 인덱스를 효율적으로 디스크에 저장하고 관리한다. 정리하면 Page Layout은 테이블, 인덱스 파일에서 사용하는 공통적인 구조를 의미한다.

• 페이지의 크기를 변경하기 위해서는 Config 수정이 필요합니다. Config를 수정하는 스크립트는 아래와 같다.

postgres/configure --with-blocksize={BLOCK_SIZE in KB}

• 페이지의 고정 크기는 최대 32KB까지 변경할 수 있다.
• File의 최초 크기는 0KB에서 시작하며 파일 크기는 페이지 단위로 확장된다.
• 즉, Page 크기가 8KB라면, File의 크기는 8KB 배수 단위로 증가한다.
• 각 페이지는 PageHeaderData, ItemId, Free Space, Item, Special Space로 구성된다.
• Page는 크게 Header 영역이고, 나머지는 Data 영역으로 구분된다.
• 아래에서 설명할 PageHeaderData가 Header 영역이고, 나머지는 Data 영역이다.

 

PageHeaderData

• Page Header는 페이지에 대한 일반적인 정보를 담고 있다.
• 페이지의 시작 부분에 위치한다. 따라서 페이지에서 가장 낮은 주소를 갖는다.
• 크기는 24KB로 고정되어 있다.

 

ItemId

• ItemId는 실제로 Item을 가리키는 정보를 저장하고 있으며 Array 형태로 저장된다.
• 각각 Item의 위치(offset)와 크기(size)를 담고 있는데, 이는 해당 ItemId가 가리키는 Item의 물리 위치를 의미한다.
• 크기는 4KB로 고정되어 있다.

 

Free Space

• ItemId와 Items 사이의 아직 할당되지 않은 영역을 의미한다.
• 새로운 ItemId는 Free Space의 시작 부분부터 할당되고, 새로운 Item은 Free Space의 끝부분부터 할당된다.
• 더 이상 추가할 수 없을 때, 페이가 가득 찬 것으로 간주하고 빈 페이지를 추가한다.

 

Item

• Item은 테이블 페이지와 인덱스 페이지가 실제로 저장되는 영역이다.
• 테이블 페이지의 경우에 Tuple이 저장되고 인덱스 페이지의 경우는 Index Entry가 저장된다.

 

Special Space

• Special Space는 페이지의 가장 끝 부분에 위치한다. 따라서 페이지에서 가장 높은 주소를 갖는다.
• Special Space는 일부 인덱스를 저장하는 페이지에서 추가 정보를 저장하는 데 사용되는 영역이다.
• 즉, 테이블을 저장하는 페이지에서는 Special Space의 크기가 0이다.
• 인덱스 페이지에서 Special Space는 인덱스의 유형에 따라 내용이 다르다.

 

페이지 스캔

페이지에서 원하는 데이터를 스캔하는 방식은 크게 Seq Scan과 Index Scan이 있다.

Seq Scan

• 위와 같이 데이터 페이지를 순차적으로 순회하는 방식으로 스캔한다.

Index Scan

• 먼저 인덱스 튜플을 찾아서 그 안에있는 page, offset 정보를 바탕으로 데이터 튜플을 스캔한다.

Shared Buffer

Shared Buffer의 목적은 DISK IO를 최소화함으로써 IO 성능을 향상시키는 것이다. 이를 위해서는 아래와 같은 목표를 완수해야 된다.

1. 매우 큰 버퍼를 빠르게 엑세스 할 수 있어야 한다. -> 해시 테이블을 이용해서 구현
2. 많은 사용자가 동시에 접근할 때 경합을 최소화해야 한다. -> Lock을 효율적으로 사용해서 구현
3. 자주 사용하는 블록은 최대한 오랫동안 버퍼 내에 있어야 한다. -> Clock Sweep 알고리즘으로 구현

Shared Buffer의 크기는 postgresql.conf 에서 설정할 수 있으며, 기본값은 128MB이다.

Shared Buffer의 구조는 아래와 같다.

• Shared Buffer는 Buffer Mapping Table, Buffer Descriptors 그리고 Buffer Pool로 이루어져 있다.

 

Buffer Mapping Table

• Buffer Mapping Table는 Shared Buffer에 저장된 각 데이터 페이지를 식별하고 빠르게 찾을 수 있도록 도와주는 역할을 한다.
• Buffer Mapping Table는 크게 해시 테이블과 해시 엘리먼트로 구성된다.

• 해시 테이블은 메모리 내의 버퍼를 관리할 때 매우 효과적인 자료구조이다.
• 해시 테이블은 여러개의 128개의 버퍼 파티션으로 구성된다. (9.4 버전 이하는 16개)
  • 공유 리소스는 LW 락을 이용해서 보호해야 한다.
  • 만약 LW 락이 1개라면, 락을 점유하기 위해서 기다리는 프로세스가 많아질 것이다.
  • 그렇기 때문에 해시 테이블을 128개의 버퍼 파티션으로 나누고 파티션 별로 LW 락을 할당하는 방식으로 사용한다.
• 해시 엘리먼트는 Buffer Tag 와 Buffer ID로 구성되어 있다.
• Buffer Tag
  • Buffer Tag는 메모리에 캐시된 데이터 페이지를 고유하게 식별하는 정보를 담고 있다. 마치 주민번호와 같다.
  • 테이블스페이스 번호, 데이터베이스 번호, 오브젝트 번호로 구성된다. 이렇게 되면 클러스터 내에서 유일한 오브젝트 번호를 획득할 수 있다.
• Buffer Id
  • Buffer ID는 Buffer Pool 내의 특정 슬롯을 가리키는 식별자이다.

Buffer Descriptors

• 메모리에 캐시된 각 데이터 페이지(또는 블록)에 대한 메타데이터와 상태 정보를 관리한다.

• Buffer Descriptors는 각각의 데이터 페이지에 대한 정보를 담고 있습니다.

• 버퍼 사용 정보에는 해당 버퍼가 몇 번 사용됐고, 현재 몇 개의 프로세스가 사용중인지 나타낸다.
• 버퍼 상태 플래그에는 해당 버퍼의 상태가 나타난다.
• 버퍼 사용 정보와 버퍼 상태 플래그를 통해서 아래와 같이 3가지 상태를 표현할 수 있다.

• Empty의 경우 해당 버퍼는 사용한 적이 없고, 그렇기 때문에 사용중인 프로세스도 없다. 말그대로 비어있는 버퍼이다.
• Pinned의 경우 N번 사용한적 있고, 현재 M개의 프로세스가 사용중인 상태이다.
• Unpinned의 경우 N번 사용한적 있고, 현재 사용중인 프로세스는 없는 상태이다.

Buffer Pool

• 실제로 데이터베이스 페이지(블록)가 메모리에 캐시되는 영역이다.

• Buffer Pool는 자주 조회되는 데이터의 빠른 검색과 디스크 I/O 최소화를 위해 중요한 역할을 한다.
• Buffer Pool에 존재하는 버퍼(페이지)의 크기는 8KiB이다.
• 따라서 Shared Buffer의 크기가 256MiB라고 가정하면 Buffer Pool에 저장된 버퍼의 수는 256MiB / 8KiB이므로 32768개이다.
• 즉 Shared Buffer에는 32768개의 블록을 저장할 수 있다.

 

Buffer Descriptors가 가득 찬 상황에서 Shared Pool에 없는 데이터를 조회하려고 하면, 교체할 버퍼를 찾아야 한다. 여기서 사용되는 알고리즘이 Clock Sweep 알고리즘이다.

 

Clock Sweep (페이지 교체 알고리즘)

• 페이지를 교체하는 것이지 이미 할당된 버퍼를 프리리스트로 반환하는 알고리즘은 아니다.
• Clock Sweep는 자주 사용되지 않는 블록을 효율적이게 선택할 수 있게 해주는 알고리즘이다.
• Clock Sweep는 슬롯(버퍼)을 순회하며 핀 개수와 사용 횟수를 체크해서 페이지를 교체할 슬롯(버퍼)을 결정하는 방식이다.

• 동작방식은 아래와 같다.

1. Pinned 상태의 버퍼는 건너뛴다.
2. Unpinned 상태이고 사용 횟수가 1보다 크면 사용 횟수를 1 감소시킨다.
3. Unpinned 상태이고 사용 횟수가 0이면 해당 버퍼를 페이지를 교체할 버퍼로 선정한다.

• 이제 위 규칙을 바탕으로 Clock Sweep의 동작원리를 이해해 보자.

• 위와 같이 시계방향으로 버퍼를 체크하면서 교체 대상이될 버퍼를 찾는다.
• 페이지 교체는 Buffer Descriptors에 Empty 버퍼가 없을 때 발생한다.

 

Shared Buffer의 구성요소에 대해서 알아보았으니 이제 본격적으로 Shared Buffer에서 데이터를 읽어오는 과정을 알아보자.

 

Buffer Pool에 있는 블록 읽기

Shared Buffer에서 데이터 블록을 읽는 과정을 알아보자. 블록을 읽는 과정을 크게 3가지로 나눠서 설명한다.

 

1. Buffer Pool에 찾는 블록이 있는 경우

2. Buffer Pool에 찾는 블록이 없어서 비어있는 버퍼에 블록을 로딩한 뒤 읽는 경우

3. Buffer Pool에 데이터 없고 Buffer Pool이 가득 차서 Buffer Pool에서 블록 교체 후 블록을 읽는 경우

 

Buffer Pool에 찾는 블록이 있는 경우

1. Buffer Tag를 생성한다.
   • 생성된 Buffer Tag를 사용해서 hash value를 계산한다.
   • 계산된 hash value를 통해서 버퍼 파티션 번호를 계산한다.
2. 해당 버퍼 파티션에 공유모드로 락을 획득한다.
3. 해시 체인을 검색해서 찾은 엔트리를 통해서 원하는 버퍼 Descriptors 배열 인덱스를 찾는다.
4. 찾은 인덱스 번호에 맞는 버퍼 Descriptor 배열에 PIN을 꽂는다.
   • 사용 횟수 1추가, 핀 갯수 1추가
5. 버퍼 파티션에 락 해제한다.
6. 블록을 읽기 전, 찾은 인덱스 번호에 해당하는 버퍼 Descriptor 배열에 컨텐츠락 획득한다.
7. 버퍼풀에서 블록 Read 한다.
8. 버퍼 Descriptor 배열에 컨텐츠락 해제하고 PIN 해제한다.

Buffer Pool에 찾는 블록 없어서 비어있는 버퍼에 블록을 로딩한 뒤 읽기 경우

버퍼풀에 원하는 블록이 없고, 버퍼 Descriptors 배열에 빈 원소가 있다면 새로운 블록을 배열에 로딩해야 한다.

1. Buffer Tag를 생성한다.
   • 생성된 Buffer Tag를 사용해서 hash value를 계산한다.
   • 계산된 hash value를 통해서 버퍼 파티션 번호를 계산한다.
2. 해당 버퍼 파티션에 공유모드로 락을 획득한다.
3. 해시 체인을 검색해서 찾은 엔트리를 통해서 원하는 버퍼 Descriptors 배열 인덱스를 찾지만 실패한다.
4. 버퍼 파티션에 락 해제한다.
5. 버퍼 파티션에 배타잠금모드로 락을 획득한다.
6. 해시 엘리먼트 풀에서 새로운 엘리먼트 추가한다.
7. 블록을 로딩하기 전, 찾은 인덱스 번호에 해당하는 버퍼 Descriptor 배열에 I/O 진행중락 획득 하고 I/O 진행중 플래그 설정한다.
8. 디스크로부터 블록을 로딩한다.
9. 버퍼 Descriptor 배열에 I/O 진행중 플래그 해제하고 유효성 플래그 설정 한다. 그리고 I/O 진행중락도 해제한다.
10. 버퍼 파티션에 락 해제한다.
11. 버퍼풀에서 블록을 Read 한다.

 

Buffer Pool에 데이터 없고 Buffer Pool이 가득 차서 Buffer Pool에서 블록 교체 후 블록을 읽는 경우

버퍼풀에 원하는 블록이 없고, 버퍼 Descriptors 배열이 이미 가득 차있다면 필요 없는 블록을 제거한 뒤 새로운 블록을 로딩해야한다. 블록을 교체하는 과정에서 이전에 설명했던 Clock Sweep이 사용된다.

1. Buffer Tag를 생성한다.
   • 생성된 Buffer Tag를 사용해서 hash value를 계산한다.
   • 계산된 hash value를 통해서 버퍼 파티션 번호를 계산한다.
2. 해당 버퍼 파티션에 공유모드로 락을 획득한다.
3. 해시 체인을 검색해서 찾은 엔트리를 통해서 원하는 버퍼 Descriptors 배열 인덱스를 찾지만 실패한다.
4. 버퍼 파티션에 락 해제한다.
5. Clock Sweep 알고리즘을 통해서 필요 없는 블록을 찾는다.
6. 버퍼 파티션에 배타잠금모드로 락을 획득한다.
7. 생성된 Buffer Tag로 찾은 버퍼파티션에 배타잠금모드로 락을 획득한다.
8. 새로운 엘리먼트를 추가한다.
9. Clock Sweep 알고리즘에 의해 찾아진 버퍼를 가리키는 엘리먼트를 삭제한다.
10. 버퍼 파티션에 락 해제한다.
11. 블록을 로딩하기 전, 찾은 인덱스 번호에 해당하는 버퍼 Descriptor 배열에 I/O 진행중락 획득 하고 I/O 진행중 플래그 설정한다.
12. 디스크로부터 블록을 로딩한다.
13. 버퍼 Descriptor 배열에 I/O 진행중 플래그 해제하고 유효성 플래그 설정 한다. 그리고 I/O 진행중락도 해제한다.
14. 버퍼 파티션에 락 해제한다.
15. 버퍼풀에서 블록을 Read 한다.

나는 Shared Buffer를 공부하면서 이런 의문이 들었다. 일시적으로 대량의 데이터를 조회하면 Shared Buffer는 해당 데이터 블록으로 가득 찰까? 그렇다면 캐시 히트율이 매우 안 좋아 질텐데? 이 문제에 대한 답은 Ring Buffer에 있다. 이제 Ring Buffer에 대해서 알아보자.

Ring Buffer

• Ring Buffer는 원형의 논리적으로 원형 형태의 배열을 의미한다.
• 즉, 일정 크기의 배열을 순환 방식으로 사용하는 것이며, 이를 통해 Shared Buffer를 Large Seq Scan의 위험성으로부터 보호하는 것이다.
• 정리하면, Ring Buffer의 용도는 크고 중요하지 않은 데이터 블록이 Shared Buffer에 올라가지 않게 하는 것이다.
• PostgreSQL에서는 이러한 문제를 해결하기 위해서 아래 4가지 I/O 전략을 사용한다.

 

I/O 전략

• NORMAL
  • 랜덤 엑세스에 사용되는 I/O 전략이다.
  • 작은 쿼리나 평소의 데이터베이스 작업에 주로 사용된다.
• BULK READ
  • Large Seq Scan에 사용되는 I/O 전략이다.
  • 이 전략은 대용량 데이터 읽기 작업에 최적화된 메모리 관리와 I/O 처리를 제공이다.
• BULK WRITE
  • 대량의 데이터를 쓸 때 사용되는 I/O 전략이다.
• VACUUM
  • VACUUM 작업은 데이터베이스를 정리하고 최적화하기 위해 사용한다.
  • 불필요한 데이터를 제거하고 디스크 공간을 회수한다.

위 내가지 전략 중에서 NORMAL을 제외한 I/O전략은 모두 Ring Buffer를 사용한다고 보면 된다.

 

Ring Buffer 크기

• Ring Buffer의 크기는 I/O 전략에 따라 조금씩 다르다.
• 먼저 가장 중요한 BULK READ의 경우, Ring Buffer의 크기는 256KiB(32 블록)이다.
  • 여기서 BULK READ의 기준은 Shared Buffer 크기의 1/4 이상인 테이블에 대한 Seq Scan을 의미한다.
• 만약 32 블록보다 더 큰 데이터를 Read 한다면?
  • 1000만 건으로 Read 한다고 해도 32개의 블록만을 사용한다.
  • Ring Buffer는 논리적으로 원형 배열의 형태로 데이터를 순차적으로 로드한다.
• 만약 1000만 건이 담긴 데이터를 100번 조회한다면?
  • 1000만 건을 읽을 때에도 32블록만을 사용한다. 그렇다면 100번 반복해서 읽으면 3200블록을 사용할까?
  • 맞다. 같은 데이터를 반복해서 읽는다고 해도 매번 새로운 Ring Buffer를 사용하기 때문에 32 * 100인 3200개의 블록을 사용한다.
• Ring Buffer는 쿼리 수행이 완료된 후 바로 해제된다. 즉 Ring Buffer는 임시 사용하는 버퍼라고 생각하면 된다.

References

• PostgreSQL 9.6 성능이야기, 저자 김시연, 최두원
• https://www.interdb.jp/pg/pgsql08.html
• https://blog.ex-em.com/1657?category=1010730
• https://blog.ex-em.com/1764
• https://pankaj-sharma.me/posts/postgres-internals-page-layout/