All Articles

InnoDB Space 파일의 페이지 관리 방법

원문: Page management in InnoDB space files

InnoDB 핵심을 이해하기 위한 여행 시작 에서, InnoDB 내부 구조 문서화를 위한 innodb_diagrams 프로젝트를 소개했습니다. 이 포스트의 다이어그램들은 innodb_diagrams를 이용해 그렸습니다.

Space 및 각 페이지의 기본적인 구조는 Space 파일 레이아웃 기초 에서 설명했습니다. 이제 페이지 및 extent 관리, “여유 공간 (free space)” 관리와 관련된 InnoDB의 구조 및 다양한 목적으로 할당된 페이지들을 추적하는 방법에 대해 설명하겠습니다.

Extent와 extent descriptor

이전에 설명했듯이, InnoDB 페이지는 일반적으로 16 KiB이고, 64개의 연속된 페이지인 1 MiB 블록들로 그룹화되는데, 이를 “extent” 라고 부릅니다. InnoDB는 space 내 고정된 위치에 FSP_HDRXDES 페이지를 할당하여 사용 중인 extent와 사용 중인 extent 내의 페이지를 추적합니다. 이 페이지들은 매우 간단한 구조를 가지고 있습니다:

fsp-overview

여기에는 일반적인 FIL 헤더와 트레일러, FSP 헤더 (나중에 설명) 및 256 개의 “extent descriptor” 또는 단순히 “descriptor” 가 포함됩니다. 또한 상당한 양의 미사용 공간이 포함되어 있습니다.

Extent descriptor의 구조는 다음과 같습니다:

xdes-entry

Extent descriptor 내 각 필드의 목적은 아래와 같습니다:

  • File Segment ID: Extent가 속한 파일 segement의 ID (파일 segement에 속한 경우에만)
  • List node for XDES list: Doubly-linked extent descriptor list에서 이전 및 다음 extent를 가리키는 포인터
  • State: Extent의 현재 상태를 의미하며 현재 네 가지 값만 정의되어 있습니다; FREE, FREE_FRAGFULL_FRAG는 이 extent가 같은 이름을 갖는 space 리스트에 속한다는 걸 의미합니다. FSEG는 이 extent가 File Segment ID 필드에 저장된 ID를 가진 파일 segment 속함을 의미합니다. (아래 리스트에 더 자세히 나와 있습니다.)
  • Page State Bitmap: Extent의 페이지 당 2 bit를 갖는 비트맵 (64 x 2 = 128 bits 또는 16 bytes)을 의미합니다. 첫 번째 비트는 페이지가 사용 가능한지 여부를 나타냅니다. 두 번째 비트는 페이지가 깨끗한 지 (= flush 되지 않은 데이터가 없음)를 나타내지만, 이 비트는 현재 사용되지 않고 항상 1로 설정되어 있습니다.

Extent를 참조하는 다른 구조체들은 extent의 descriptor가 있는 FSP_HDR 또는 XDES 페이지의 페이지 번호와 descriptor 항목 자체의 해당 페이지 내의 바이트 오프셋을 조합하여 사용합니다. 예를 들어, “page 0 offset 150”이 참조하는 extent는 space의 첫 번째 범위이며 0-63 페이지를 차지하고 “page 16384 offset 270”은 16576-16639 페이지를 차지합니다.

List base nodes 및 list nodes

리스트 (InnoDB에서는 “free list”라고 부름)는 여러 관련 구조를 함께 연결할 수 있는 일반적인 구조체입니다. 리스트는 두 개의 상호 보완적인 구조로 구성되어 있으며, 이는 디스크 상의 이중 연결 리스트를 제공합니다. “list base node”는 다음과 같은 구조를 갖습니다:

list-base-node

Base node는 몇몇 하이 레벨 구조 (FSP 헤더와 같은)에서 오직 한번만 저장됩니다. Base node는 리스트의 길이 및 리스트의 처음과 마지막 리스트 노드를 포함하고 있습니다. 실제 “list node”도 비슷한 구조를 갖습니다:

list-node

첫 번째와 마지막 노드에 대한 포인터를 저장하는 대신, 리스트 노드는 이전과 다음 노드에 대한 포인터를 저장합니다.

모든 포인터는 페이지 번호 (같은 space 내에 있어야 함)와 리스트 노드를 찾을 수 있는 해당 페이지 내의 byte offest으로 구성됩니다. 모든 포인터는 리스트 노드의 시작 (즉, N+0)을 가리키며, 반드시 서로 연결된 구조여야 하는 건 아닙니다. 예를 들어, extent descriptor 항목이 리스트에 연결된 경우 리스트 노드가 XDES 항목 구조 내에서 offset 8에 있기 때문에, 리스트 항목을 읽는 코드는 descriptor 구조가 리스트 노드 offset의 8 바이트 전에 시작한다는 것을 “알아야” 거기에서 그 구조체를 읽을 수 있습니다. (리스트 노드가 구조체에서 첫 번째로 등장하는 항목인지 항상 확인하는 것이 좋을 것입니다.)

파일 space 헤더 및 extent 리스트

Extent descriptor 항목 자체를 저장하는 것 외에도, FSP_HDR 페이지 (space에서 항상 페이지 0 임)는 많은 리스트들을 포함하는 FSP 헤더도 저장하므로 이전에 쉽게 설명 할 수 없었습니다. FSP 헤더의 구조는 다음과 같습니다:

fsp-header

FSP 헤더에서 리스트와 관련이 없는 필드들의 용도는 아래와 같습니다 (순서대로 아님):

  • Space ID: 현재 space의 space ID
  • Highest page number in the space (size): “size”는 가장 높은 유효한 페이지 번호이며 파일이 증가할 때 증가합니다. 그러나 space 확장은 여러 단계로 이루어지므로, 이러한 페이지들이 모두 초기화되는 것은 아닙니다 (일부는 0으로 채워질 수 있음).
  • Highest page number initialized (free limit): “free limit”은 FIL 헤더가 초기화된 가장 높은 페이지 번호이며 페이지 번호를 페이지 자체에 저장합니다. Free limit은 항상 size보다 작거나 같습니다.
  • Flags: Space와 관련된 플래그 저장
  • Next Unused Segment ID: 다음에 할당될 파일 segment에 사용될 파일 segment ID (본질적으로 자동으로 증가하는 (auto-increment) 정수)
  • Number of pages used in the FREE_FRAG list: 이 필드는 리스트의 모든 extent를 반복하여 탐색하면서 각각에서 사용 가능한 빈 페이지를 합산하는 것 없이도 FREE_FRAG 리스트에서 free 페이지 수를 빠르게 계산할 수 있도록, 최적화 기법으로서 저장됩니다.

아래의 extent descriptor 리스트에 대한 list base node도 FSP 헤더에 저장됩니다:

  • FREE_FRAG: 전체 extent를 할당하는 대신 개별 페이지를 다른 목적으로 할당하여 “fragments”로 사용될 수 있도록 할당된, free 페이지가 남아있는 extent. 예를 들어, FSPHDR 또는 XDES 페이지를 갖는 모든 extent는 *FREEFRAG* 리스트에 배치되어 extent의 나머지 free 페이지가 다른 용도로 할당될 수 있습니다.
  • FULL_FRAG: FREE_FRAG와 똑같지만 남아있는 free 페이지가 없는 extent에 해당합니다. Extent가 가득 차면 FREE_FRAG에서 FULL_FRAG로 이동하고, 더 이상 가득 차지 않도록 페이지가 해제되면 FREE_FRAG로 다시 이동합니다.
  • FREE: 완전히 미사용 중이고, 특정 목적으로 이용하려고 전체가 할당된 extent. FREE extent는 파일 segment에 할당되거나 (적절한 INODE 리스트에 배치됨) 개별 페이지 사용을 위해 FREE_FRAG 목록으로 이동될 수 있습니다.

파일 segment와 inode

파일 segment와 inode는 용어부터 시작해서 아마 InnoDB에서 문서화가 가장 안 된 부분 중 하나일 것입니다. InnoDB는 파일 시스템에서 일반적으로 사용되는 “inode” 라는 용어를 오버로드하고 INODE 항목 (하나의 작은 구조체)과 INODE 페이지 (많은 INODE 항목을 보유한 페이지 타입)에 모두 사용합니다. InnoDB의 INODE 항목은 단순히 파일 segment (FSEG)를 의미하며, 이제부터는 “파일 segment INODE” 라고 합니다. INODE 페이지의 구조는 다음과 같습니다:

inode-overview

각 INODE 페이지에는 85개의 파일 segment INODE 항목 (16KiB 페이지)이 포함되어 있으며 각각 192 bytes입니다. 또한 여기에는 위에서 설명한 FSP_HDR의 FSP 헤더 구조에 있는, 다음의 INODE 페이지 리스트에 사용되는 리스트 노드가 포함되어 있습니다:

  • FREE_INODES: 한 개 이상의 사용 가능한 파일 segment INODE 항목이 있는 INODE 페이지 리스트
  • FULL_INODES: 비어있는 파일 segment INODE 항목이 없는 INODE 페이지 리스트. “테이블 당 파일 (file-per-table)” space를 사용하는 경우, 각 index가 정확히 두 개의 파일 segment INODE 항목을 사용하므로, 테이블에 42개 이상의 index가 없으면 테이블 당 각 space의 이 리스트가 비어있게 됩니다.

파일 segment INODE 항목의 구조는 다음과 같습니다:

inode-entry

각 INODE 항목에서 리스트가 아닌 필드의 용도는 다음과 같습니다:

  • File Segment ID: 이 파일 segment INODE 항목이 가리키는 파일 segment (FSEG)의 ID입니다. ID가 0이면 항목이 사용되지 않습니다.
  • Magic Number: 값 97937874는 이 파일 segment INODE 항목이 올바르게 초기화되었음을 나타내는 마커로 저장됩니다.
  • Number of used pages in the NOT_FULL list: Space의 FREE_FRAG 리스트 (FSP 헤더에 있음)와 마찬가지로, 이 필드는 NOT_FULL 리스트에 사용된 페이지 수를 저장하는데, 리스트의 모든 extent를 반복하여 탐색하는 것 없이 리스트에서 free 페이지의 개수를 빠르게 계산할 수 있도록 도와주는 최적화 기법의 일종으로 사용됩니다.
  • Fragment Array: “fragment” extent의 space의 FREE_FRAG 또는 FULL_FRAG에 있는 extent로부터 개별적으로 할당된 32개의 페이지의 page number 배열입니다. 이 배열이 가득 차면, 파일 extent에 full extent만 할당할 수 있습니다.

테이블이 커지면 fragment 배열이 가득 찰 때까지 각 파일 segment에 개별 페이지를 할당한 다음, 한 번에 1개의 extent를 할당하고 결국 한 번에 4개의 extent를 할당하도록 전환합니다.

Extent descriptor의 list base node는 각 파일 segment INODE 항목에도 있습니다:

  • FREE: 이 파일 segment에 할당된 extent 중 미사용 중인 extent
  • NOT_FULL: 이 파일 segment에 할당된 extent 중 하나 이상의 페이지가 사용 중인 extent. 마지막 free 페이지가 사용되면, extent가 FULL 리스트로 이동합니다.
  • FULL: 이 파일 segment에 할당된 extent 중 free 페이지가 없는 extent. 페이지가 사용 가능해지면 extent가 NOT_FULL 리스트로 이동합니다.

마지막으로 사용된 페이지가 NOT_FULL 리스트의 extent에서 해제되면, extent는 파일 segment의 FREE 리스트로 이동될 수 있지만 실제로는 space의 FREE 리스트로 이동됩니다.

Index가 파일 segment를 사용하는 방법

INDEX 페이지에 대해서 아직 설명하진 않았지만, 한 가지 작은 사실에 대해 알 수 있습니다. 각 index의 FSEG 헤더의 root 페이지에는 index에 사용된 파일 segment를 나타내는 파일 segment INODE 항목에 대한 포인터가 있습니다. 각 index는 leaf 페이지와 leaf가 아닌 (내부) 페이지에 각각 하나의 파일 segment를 사용합니다. 이 정보는 FSEG 헤더 구조 (INDEX 페이지)에 저장됩니다:

fseg-header

위 그림에 존재하는 space ID는 다소 불필요합니다 --- 항상 현재 space ID와 동일하기 때문입니다. 페이지 번호와 offset은 INODE 페이지의 파일 segment INODE 항목을 가리킵니다. 완전히 비어있을지라도 두 파일 segment는 항상 존재합니다.

예를 들어, 새로 생성된 테이블에서, 존재하는 유일한 페이지는 root 페이지이며 (leaf 페이지이기도 하지만), “내부 (internal)” 파일 segment에 존재하므로 나중에 이동시킬 필요가 없습니다. “leaf” 파일 segment INODE 리스트와 fragment 배열은 모두 비어 있습니다. “내부” 파일 segment INODE 리스트는 모두 비어 있고, 단일 root 페이지는 fragment 배열에 있습니다.

모두 함께 묶기

다음 다이어그램은 index에 대한 전체 다중 레벨 구조를 보여줍니다:

index-file-segment-structure

Index root 페이지는 두 개의 inode (파일 segments)를 가리키며, 각각은 fragment 배열 (fragment 리스트에서 최대 32개의 개별 페이지를 가리킴)과 전체 extent 및 여러 리스트를 가지며, extent descriptor의 리스트 포인터를 사용하여 서로 연결됩니다. Extent descriptor는 extent를 참조하고 extent 내의 free 페이지를 추적하는 데 사용됩니다. Easy!

다음 포스트

다음 포스트에서는 사용자 관점에서 가장 중요한 페이지 유형 중 하나인 INDEX 페이지의 구조를 살펴보겠습니다. 그 다음, 하이 레벨에서 InnoDB가 index를 어떻게 구성하는지 살펴보겠습니다.