[Jeremy Cols's InnoDB] 2. Page management in InnoDB space files

이 글은 다음의 url을 번역한 것입니다.

제 능력으로 번역되는 것인 만큼...100% 확신된 번역 내용은 아닙니다.

http://blog.jcole.us/2013/01/04/page-management-in-innodb-space-files/

Page management in InnoDB space files

Extents and extent descriptors

 

이전의 문서에서 InnoDB page는 기본적으로 16KB 사이즈를 가진다. 그리고, 64 page씩으로 해서 1Mbyte가 그룹으로 묶이는데 우리는 이것을 extent라고 부른다. InnoDB는 사용하는 extent의 정보를 끊임없이 얻어내기 위해 그리고, 각각 사용하는 extent가 가지고 있는 page가 어떤 것인지 알기 위해, FSP_HDR 과 XDES page를 space(tablespace)의 지정된 공간에 할당한다.  

 

 

이것들은 FIL header와 trailer, FSP header 와 256개의 extent descriptors와 그냥 일반 descriptors들을 포함하고 있다. 그리고 상당한 크기의 사용하지 않는 공간도 가지고 있다.

 

extent descriptor들은 다음과 같은 구조를 가진다.

 

 

 

extent descriptor안의 여러 field들은 다음과 같은 목적을 가지고 있다.

• File Segment ID: 만약, file segment에 속해 있다면, 이것은 extent가 속한 file segment의 ID 정보를 말한다.
• List node for XDES list: extent descriptor list는 doubly-linked 구성을 갖는데, 이때 이 값은 내 앞과 뒤에 위치한 extent를 연결하는 포인터 정보를 가지고 있다.
• State: extent의 현재 상태 정보를 말한다. 이때 상태 정보는 4가지로 표현할 수 있다. FREE, FREE_FRAG, FULL_FRAG(extent가 같은 이름을 가진 space의 list에 속해 있다는 것을 의미한다.) 그리고, FESG(extent가 특정 File Segment에 속해 있다는 것을 의미한다. 이때 특정 File Segment는 File Segment ID 필드에 저장된 바로 그 Segment이다.) 이다.
• Page State Bitmap : extent 안에 있는 페이지 하나당 2bit를 표현하는 Bitmap으로 64*2 = 128 bit 즉, 16 byte로 된 Bitmap이다. 2 bit중 첫번째는 해당 페이지가 free인지 아닌지를 표현하고, 두번째는 page가 clean한지 안한지, 즉, flush되지 않은 데이터가 있는지 확인하기 위해 사용한다. 그러나, 2번째 비트는 아직 사용하고 있지 않다. 그래서 현재는 항상 1이다.

 

 

extent를 참조하는 다른 데이터 구조들은  extent의 descriptor에 저장된 FSP_HDR 과 XDES의 page number와 descriptor entry의 페이지 안의 byte offset을 조합하여 사용한다. 예를 들어, page 0 offset 150 이라고 참조되는 extent는 해당 space의 page0에서 63번까지를 가지고 있는 첫번째 extent이다.  while "page 16384 offset 270" accounts for pages 16576-16639(도통 이해가 안간다...흠냐... 내 생각에 64 page씩 extent가 할당되면,  page 16576-16639가 아니라, page 16384-16448 일거 같은데...도통 모르겠다.. 흠 처음만 64 page이고, 이후에는 아니었던거 같은데 그래서 그런가?)

 

List base nodes and list nodes

 

InnoDB에서 free list라고 부르는 List는 꽤 포괄적인 데이터 구조로 여러군데에서 사용하는 List이다. 이것은 두가지의 서로 보충되는 데이터 구조로 구성되어있는데,  이것들은 디스크 기반의 doubly-linked list 구조로 되어있다. 다음은 list base node의 구성을 표현한 것이다.

 

base node는 FSP header와 같이 꽤 높은 레벨의 데이터 구조 안에 저장된다. 여기에는 list의 길이도 포함하고, list의 첫번째 노드와 마지막 노드에 대한 포인터 정보도 포함한다. 사실 상의 list node는 다음과 같은 구조를 가진다.

 

 

여기에는 첫번째 포인터와 마지막 포인터를 저장하는 대신에 이전 노드와 다음 노드에 대한 포인터 정보를 가지고 있다.

모든 포인터들은 page number로 구성되어있다. (그리고 이 포인터들은 모두 같은 space안에 존재한다고 가정한 것이다. 그리고 그렇게 있어야 한다. 즉, 각 space별로 관리된다는 것이다.) 그리고, list node안에 있는 page안의 offset 정보는 모두 찾을 수 있다.

모든 포인터들은 ,함께 linked된 데이터 구조에 대한 것이 아닌, list node의 시작점 즉, N+0을 가르킨다. 예를 들어, extent descriptor entry들이 list에 linked될 때, 그 list node가 XDES entry 구조의 offset 8인 곳에 있다면, list entry의 데이터를 읽는 코드는 descriptor 구조가 list node의 offset전의 8 byte앞에서 시작된 다는 것을 알고 있어야 한다. 그래서, 그 곳에서 부터 구조 정보를 읽어야 한다. ( 이것은 좋은 모양새는 아니다. )

 

The file space header and extent lists

extent descriptor entry를 그들 자신이 저장하는 것은 제처두고, FSP_HDR page(이것은 항상 space의 page0에 저장된다.)는 FSP 헤더 정보를 저장한다. 이것은 많은 list를 포함하고 있지만, 앞에서는 따로 설명하지는 않았다.

 

 

 

FSP header에 위치한 list 구조가 아닌 필드들은 다음과 같이 설명할 수있다. (순서대로 설명하지 않았다.)

• SPACE ID : 현재 page가 위치한 space 의 ID
• Highest page number in the space(size): 여기서 size는 가장 높은 값을 가진 유효한 page number를 말한다. 그리고 이것은 파일이 커질때 마다 숫자가 증가한다. 그러나, 모든 페이지가 초기화 되는 것은 아니며, space가 할당되어 커질때 여러 단계에 따라 이루어 진다.
• Highest page number initialized (free limit) : The "free limit" 는 FIL header가 초기화 된 이후에 가장 높은 page number를 말하는데, 해당 페이지의 page number가 기록된다. free limit는 항상 size값보다 같거나 작다.
• Flags : space에 연관된 flag들의 묶음을 말한다.
• Next Unused Segment ID : 현재 할당 받은 것 중에 다음에 사용될 file segment에 대한 ID값을 나타낸다. (이값은 자동적으로 값이 증가하는 integer 형태로 되어있다.)
• Number of pages used in the FREE_FRAG list: 이 값은 FREE_FRAG 리스트 안에서 사용되지 않은 free page의 수를 계산하여 나온 값을 가지고 있다. 이때 extent list를 통해서 계산된 것이 아니라, 개별 page들을 따로 계산하여 나온 값이다.

FSP head안에 저장된 extent descriptor list에 기반한 List based node들은 다음과 같다.

• FREE_FRAG : fragments에 사용된다고 할당된 extent에서 현재 남아있는 아직 사용하지 않은 page들을 가진 extent을 나타내는데, 이것들은 전체 extent들 중에 다른 목적으로 할당된 것들로 개발적인 page들로 가지고 있는 extent들도 포함된다. 예를 들어, FSP_HDR 또는 XDES 페이지가 가진 모든 extent들은 그들이 가지고 있는 extent들 중 아직 사용하지 않은 free page들이 존재 한다면, FREE_FRAG list안에 위치하게 된다.
• FULL_FRAG : 정확히 얘기하면 FREE_FRAG와 비슷하다. 그러나, 남아있는 free page가 없는 경우에 위치하게 된다. extent들은 남아있는 page를 모두 사용하게 되면, FREE_FRAG에서 FULL_FRAG로 위치를 이동한다. 그리고, page가 release되어 다시 남은 page가 있게 되면, 다시 FREE_FRAG로 돌아가게 된다.
• FREE: extent안에 page를 한번도 사용하지 않은 상태를 말한다.

File segments and inodes

File segment와 inode는 아마도 InnoDB 구조 안에서 가장 번잡하게 사용하는 용어가 아닐까 한다. inode는 일반적인 filesystem안에서는 아주 일상적으로 사용되는 용어이다. 어쨌든 InnoDB에서는 INODE entry와 INODE page라는 용어를 모두 동시에 사용한다. 용어에 대한 내용은 무시하고, InnoDB에서 Inode entry는 file segment를 말한다. file segment는 FSEG라고 줄여서 얘기하기도 한다. 그리고, 이후에 이 문서에서는 file segment INODE로서 언급될 것이다.

INODE page의 구조는 다음과 같다.

 

 

각 INODE page는 85개의 file segment INODE entry(16 KB page를 위한 )들을 포함하고, 각각의 entry는 192byte로 되어있다. 그들은 FSP_HDR의 FSP header 데이터 구조안에 INODE page의 리스트에서 사용되는 list node를 포함하고 있다.

• FREE_INODES: 적어도 하나의 free file segment INODE entry를 가진 INODE Page의 리스트
• FULL_INODES: free한 페이지가 하나도 없는 file segment INODE entry를 가진 INODE Page의 리스트. 만약, file per table 옵션을 사용중이라면, 각각의 테이블의 space의 이 list는 42개보다 더 많은 인덱스를 가지고 있지 않다면, empty가 될 것이다(각각의 인덱스는 정확하게 2개의 file segment INODE entry를 사용하게 될 것이다.)

 

file segment INODE는 다음과 같은 데이터 구조를 가지고 있다.

 

 

INODE entry의 리스트가 아닌 필드들은 다음과 같이 설명할 수 있다.

• File Segment ID:  file segment INODE entry에의해 연결되는 file segment(FSEG)의 ID값을 나타내며, ID값이 0이면, entry는 아직 사용되지 않은 것이다.
• Magic Number : marker로서 97937874라는 값이 저장되는데, 이것은 file segment INODE가 초기화 되었다는 것을 의미한다.
• Number of used pages in the NOT_NULL list: 정확히 각 space의 FREE_FRAG list(FSP header안에 있는 )와 비슷하다.이 필드는 NOT_FULL list에서 사용하는 page number를 기록하는데, 이 값은 모든 extent를 통해서 계산하는 것이 아닌, 모든 free page를 빠르게 계산해서 나온 값으로서 저장된다.
• Fragemtn Array : fragment extents의 리스트인 space의 FREE_FRAG또는 FULL_FRAG에 있는 extent로 부터 개별적으로 할당된 page들의 array인데, 이 array이는 32개의 page를 가지고 있다.

fragment array가 꽉 찰때 까지 테이블은 각 file segment안의 각각의 페이지를 할당받으면서 커질 것이다. 그리고, 한번에 1 extent씩 할당 받다가, 나중에는 한번에 4 extent로 할당받게 될 것이다.

 

extent descriptor의 List base node들은 아래에 설명하는 file segment INODE entry안에 존재하게 된다.

• FREE : file segment 에 할당되었지만, 한번도 사용하지 않은 extent 를 가진 리스트를 말한다.
• NOT_FULL: file segment에 할당 된 것중 적어도 하나는 사용한 extent 를 가진 리스트를 말한다. 마지막에 남은 free page가 사용되면, 이 extent는 FULL list로 넘어간다.
• FULL: file segment에 할당된 페이지를 전부사용하고 있는 extent를 가진 리스트를 말한다. 만약, page하나라도 free상태로 변경된다면, 이 extent는 NOT_FULL 리스트로 넘어간다.

가장 마지막에 사용된 pageNOT_FULL 리스트에서 free가 된다면(모든 페이지가 free된 상태를 말하는 것으로 판단됨), 이 extent는 file segment의 FREE list로 넘어갈 수 있다. 하지만, 실제적으로는 그냥 space의 FREE list로 바로 넘어간다.

 

How indexes use file segments

아직 인덱스에 대한 구조를 설명하지 않았음에도 불구하고, 여기서 간단히 살펴 보도록 한다. 각 인덱스의 FSEG header의 root page는 file segment INODE entry(인덱스에 의해 사용되는 file segment에 대한 정보를 가지고 있다.)에 대한 포인터 정보를 가지고 있다. 각 index는 leaf page와 non-leaf pages를 사용하여 하나의 file segment를 사용한다. 이것에 대한 정보는 FSEG header structure(INDEX page안의)에 저장되어 있다.

 

사실 space ID는 불필요한 정보이다. (이값은 항상 현재 space에서 같은 값이기 때문이다.)  page number와 offset은 INODE entry안의 file segment INODE entry를 가리키는 정보이다. 이 값이 empty값이 더라도, file segment들은 항상 존재한다.

 

예를 들어, 새롭게 생성되는 테이블에서, root page는 꼭 존재해야만 한다. 이것이 바로 leaf page의 역할도 수행하게 된다. 그러나, 이것은 내부적으로만 존재하는 file segment안에 존재하게 된다.(그렇다고, 후에 이동하거나 하지는 않는다.) 즉, leaf file segment INODE list와 fragment array는 empty값이 될 것이다. 이 내부적으로만 존재하는 internal file segment INODE list는 모두 empty가 될것이고, single root page는 fragment array에 존재하게 될 것이다.

 

Tying it all together

 

인덱스에 대한 데이터 구조는 다음과 같은 diagram으로 표현할 수 있다.

 

 

index root page는 두개의 inode( file segment)를 가리킨다. 이때 각각은 fragment array(fragment list로 부터 최고 32개 까지의 개별적인 page를 가리킬 수 있다.)를 가지고 있다. 그리고 이 fragment array는 전체 extent의 여러 리스트들 이기도 하다. 그리고, 이 fragment array는 extent descriptor안의 pointer list들을 함께 linked되어있다. extent descriptor들은 extent를 가리킬때도 사용하지만, extent안의 free page를 추적할 때에도 사용한다.