—- In-depth understanding of InnoDB table Spaces

Page Type Review

InnoDB manages storage on a per-page basis. Our clustered indexes (i.e., complete table data) and other secondary indexes are stored in the table space as B+ trees whose nodes are data pages. The data page’s type name is actually FIL_PAGE_INDEX

General section of page

An INDEX page consists of seven sections, two of which are common to all types of pages.

As you can see from the figure, any type of page has file headers (to record some general information about the page) and file Trailer (to verify the integrity of the data to ensure the consistency of the contents when refreshing from memory to disk)

Independent table space structure

The concept of extents

In order to manage pages better, we put forward the concept of an entent. For a 16KB page, 64 consecutive pages are called an entent. In other words, an entent occupies 1MB space by default. Each 256 extents is called a group. Note that the first few page types of each group are fixed. Why y do we have an extent? Because pages are very random, the performance of random I/O and sequential I/O is very different under the large amount of data, put forward the concept of a region, we try to put data into a region or several consecutive regions, try to ensure sequential I/O, even if it wastes space, but improve the performance, so it is worthwhile.

The concept of segment

InnoDB’s designers have made a distinction between leaf nodes and non-leaf nodes in the B+ tree, meaning that leaf nodes have their own regions and non-leaf nodes have their own regions. A set of leaves is a segment, and a set of non-leaves is a segment. That is, an index generates two segments, a leaf segment and a non-leaf segment. InnoDB put forward the concept of A fragment (fragments) area, which is in A fragment area, not all of the pages is to store the same piece of data, but the fragments area of the page can be used for different purposes, such as some page is used to segment A, some pages used in section B, even some pages which do not belong to every section. The shard area belongs directly to the table space, not to any segment. So the strategy for allocating storage space to a segment thereafter looks like this:

1. When data is first inserted into a table, segments allocate storage space on a per-page basis from a fragment.
2. When a segment has occupied 32 shard pages, storage space is allocated in units of full extents.

In summary, two concepts are scattered pages and complete collections of extents

The classification of

We know that tablespaces are composed of extents, which can be roughly divided into four types:

• FREE area: No pages in this area are currently being used.
• Shard with free space (FREE_FRAG) : Indicates that there are pages available in the shard.
• FULL_FRAG: indicates that all pages in the fragmentation zone are used and no free pages are available.
• Extents attached to segments (FSEG) : Each index can be divided into leaf segments and non-leaf segments. InnoDB also defines special segments that use extents as the basic unit of allocation if the volume of data in these segments is large.

Once again, extents in the FREE, FREE_FRAG, and FULL_FRAG states are independent and directly within the tablespace; Areas in the FSEG state are attached to a segment.

XDES Entry is divided into four parts

1. Segment ID (8 bytes) : Each Segment has a unique ID. The Segment ID field indicates the Segment where the Segment resides. Of course, if the field is already assigned to a segment, otherwise the value of the field is meaningless.
2. List Node (12 bytes) : This part concatenates several XDES Entry structures into a linked List
3. State (4 bytes) : This field indicates the State of the extents
4. Page State Bitmap (16 bytes) : This section takes up 16 bytes, or 128 bits. Let’s say a region has 64 pages by default. The 128 bits are divided into 64 parts, each of which has 2 bits, corresponding to a page in the region. For example, bits 1 and 2 in the Page State Bitmap section correspond to the first Page in the area, bits 3 and 4 correspond to the second Page in the area, and so on, bits 127 and 128 in the Page State Bitmap section correspond to the 64th Page in the area. The first of these two bits indicates whether the corresponding page is free. The second bit is not yet used and is reserved.

In fact, our only purpose is to be efficient. It is very resource-consuming to traverse one by one, so List Node is to help us quickly locate the resources we need

• The XDES Entry structure corresponding to the FREE area is connected into a linked List through List Node, which is called FREE linked List.
• The XDES Entry structure corresponding to the FREE_FRAG area is connected to a linked List through the List Node, which is called the FREE_FRAG linked List.
• The XDES Entry structure corresponding to the FULL_FRAG area is connected into a linked List through List Node, which is called FULL_FRAG linked List.

So we maintain several different linked lists, and we can directly locate the corresponding linked list for data processing. In general, 32 scattered pages are merged into a full section.

There are three linked lists in each section

• FREE list: The XDES Entry structure corresponding to the section in which all pages are FREE will be added to the list. Notice the difference from the FREE list that is directly attached to a table space, where the FREE list is attached to a segment.
• NOT_FULL: XDES Entry structures corresponding to extents in the same segment that still have free space are added to this list.
• FULL list: XDES Entry structures corresponding to areas in the same segment that have no free space are added to this list.

Again, there are two segments for each index, and each segment maintains the three linked lists described above

CREATE TABLE t (
    c1 INT NOT NULL AUTO_INCREMENT,
    c2 VARCHAR(100),
    c3 VARCHAR(100),
    PRIMARY KEY (c1),
    KEY idx_c2 (c2)
)ENGINE=InnoDB;
Copy the code

Table T has two indexes, one clustered index and one secondary index idx_c2. Therefore, there are 4 segments in the table. Each segment maintains the above 3 linked lists, making a total of 12 linked lists. Insert the NOT_FULL header into the NOT_FULL section. If the section has run out of space, insert the NOT_FULL header into the FULL section.

Linked list base node

InnoDB gives the concept of the base node of a linked list in the design, which can help us quickly locate the position of the linked list. There are roughly the following parts:

1. List Length: Indicates the number of nodes in the List
2. First Node Page Number and First Node Offset indicate the position of the head Node in the table space.
3. Last Node Page Number and Last Node Offset indicate the position of the Last Node in the table space.

List summary

To sum up, a table space is composed of several extents, each of which corresponds to an XDES Entry structure. The XDES Entry structure corresponding to the extents directly in the table space can be divided into three linked lists: FREE, FREE_FRAG, and FULL_FRAG. Each segment can be attached to several segments. The XDES Entry structure corresponding to the segments can be divided into three linked lists: FREE, NOT_FULL, and FULL. Each linked List corresponds to a List Base Node structure, which records the position of the first and last nodes of the List and the number of nodes contained in the List. It is because of these linked lists that managing these areas becomes so easy.

The structure of the paragraph

As we said earlier, a segment does not correspond to a contiguous physical region of a table space, but rather is a logical concept consisting of discrete pages and complete extents. Just as each segment has an XDES Entry to record the attributes in that segment, InnoDB designers define an INODE Entry structure for each segment to record the attributes in that segment. So let’s look at the schematic

1. Segment ID: indicates the ID of the Segment corresponding to the INODE Entry structure.
2. NOT_FULL_N_USED: This field indicates how many pages have been used in the NOT_FULL list.
3. Three List Base nodes: List Base nodes are defined for FREE, NOT_FULL, and FULL lists respectively, so that when we want to find the first and last nodes of a List of a segment, we can directly go to this section to find the corresponding List Base Node
4. Magic Number: This value is used to indicate whether the INODE Entry has been initialized (initialized means the value of each field has been filled in). If the number is 97937874 of the value, the INODE Entry is initialized, otherwise it is not.
5. Fragment Array Entry: Each Fragment Array Entry structure corresponds to a Fragment page. The Fragment Array Entry structure consists of 4 bytes and represents the page number of a Fragment page.