innodb 物理文件解析

1 綜述

innodb的物理文件包括系統(tǒng)表空間文件ibdata，用戶表空間文件ibd，日志文件ib_logfile，臨時(shí)表空間文件ibtmp，undo獨(dú)立表空間等。

• 系統(tǒng)表空間是innodb最重要的文件，它記錄包括元數(shù)據(jù)信息，事務(wù)系統(tǒng)信息，ibuf信息，double write等關(guān)鍵信息。

• 用戶表空間文件通常分為兩類，一類是當(dāng)innodb_file_per_table打開時(shí)，一個(gè)用戶表空間對(duì)應(yīng)一個(gè)文件，另外一種則是5.7版本引入的所謂General Tablespace，在滿足一定約束條件下，可以將多個(gè)表創(chuàng)建到同一個(gè)文件中。

• 日志文件主要用于記錄redo log。innodb在所有數(shù)據(jù)變更前，先寫redo日志。為保證redo日志原子寫入，日志通常以512字節(jié)的block單位寫入。但由于現(xiàn)代文件系統(tǒng)升級(jí)，block_size通常設(shè)置到了4k，因此innodb也提供了一個(gè)選項(xiàng)支持redo日志以4k為單位寫入。

• 臨時(shí)表空間文件用于存儲(chǔ)所有非壓縮的臨時(shí)表，第1~32個(gè)臨時(shí)表專用的回滾段也存放在該文件中。由于臨時(shí)表的本身屬性，該文件在重啟時(shí)會(huì)重新創(chuàng)建。

• undo獨(dú)立表空間是innodb的一個(gè)可選項(xiàng)，由innodb_undo_tablespaces配置。默認(rèn)情況下，該值為0，即undo數(shù)據(jù)是存儲(chǔ)在ibdata中。innodb_undo_tablespaces 設(shè)置為非0，可使得undo 回滾段分配到不同的文件中，目前開啟undo tablespace 只能在install階段進(jìn)行。

上述文件除日志文件外，都具有較為統(tǒng)一的物理結(jié)構(gòu)。所有物理文件由頁（page 或 block）構(gòu)成，在未被壓縮情況下，一個(gè)頁的大小為UNIV_PAGE_SIZE（16384，16K）。不同用途的頁具有相同格式的頁頭（38）和頁尾（8），其中記錄了頁面校驗(yàn)值，頁面編號(hào)，表空間編號(hào)，LSN等通用信息，詳見下表。所有page通過一定方式組織起來，下面我們分別從物理結(jié)構(gòu)，邏輯結(jié)構(gòu)，文件管理過程來具體了解innodb的文件結(jié)構(gòu)。

2 文件物理結(jié)構(gòu)

2.1 基本物理結(jié)構(gòu)

innodb 的每個(gè)數(shù)據(jù)文件都?xì)w屬于一個(gè)表空間（tablespace），不同的表空間使用一個(gè)唯一標(biāo)識(shí)的space id來標(biāo)記。值得注意的是，系統(tǒng)表空間ibdata雖然包括不同文件ibdata1, ibdata2…，但這些文件邏輯上是相連的，這些文件同屬于space_id為0的表空間。

表空間內(nèi)部，所有頁按照簇（extent）為物理單元進(jìn)行劃分和管理。extent內(nèi)所有頁面物理相鄰。對(duì)于不同的page size，對(duì)應(yīng)的extent大小也不同，對(duì)應(yīng)為：

通常情況下，extent由64個(gè)物理連續(xù)的頁組成，表空間可以理解為由一個(gè)個(gè)extent物理相鄰的extent組成。為了組織起這些extent，每個(gè)extent都有一個(gè)占40字節(jié)的XDES entry。格式如下：

利用XDES entry，我們可以方便地了解到該extent每頁空閑與否，以及其當(dāng)前狀態(tài)。

所有XDES entry都統(tǒng)一放在extent描述頁中，一個(gè)extent描述頁至多存放256個(gè)XDES entry，用于管理其隨后物理相鄰的256個(gè)extent（256*64 = 16384 page），如下圖所示所示：

表空間物理結(jié)構(gòu)

由圖可見，每個(gè)XDES entry有嚴(yán)格對(duì)應(yīng)的頁面，其對(duì)應(yīng)頁面上下界可以描述為：
min_scope = extent 描述頁 page_no + xdes 編號(hào) * 64
max_scope =（ extent 描述頁 page_no + xdes 編號(hào) * 64 ）+63

值得注意的是，其中 page 0的extent描述頁還記錄了與該table space相關(guān)的信息(FSP HEADER)，其類型為FIL_PAGE_TYPE_FSP_HDR。其他extent描述頁的類型相同，為FIL_PAGE_TYPE_XDES。

2.2 系統(tǒng)數(shù)據(jù)頁

系統(tǒng)表空間（ibdata）不僅存放了SYS_TABLE / SYS_INDEX 等系統(tǒng)表的數(shù)據(jù)，還存放了回滾信息（undo），插入緩沖索引頁（IBUF bitmap），系統(tǒng)事務(wù)信息（trx_sys），二次寫緩沖（double write）等信息。

innodb中核心的數(shù)據(jù)都存放在ibdata中的系統(tǒng)數(shù)據(jù)頁中。系統(tǒng)數(shù)據(jù)頁主要包括：FIL_PAGE_TYPE_FSP_HDR, FIL_PAGE_IBUF_BITMAP, FIL_PAGE_TYPE_SYS, IBUF_ROOT_PAGE, FIL_PAGE_TYPE_TRX_SYS, FIL_PAGE_TYPE_SYS, DICT_HDR_PAGE等。

• FIL_PAGE_TYPE_FSP_HDR/FIL_PAGE_TYPE_XDES
  extent描述頁(page 0/16384/32768/... )，上文已述及，故不再展開。

• FIL_PAGE_IBUF_BITMAP
  ibdata第2個(gè)page類型為FIL_PAGE_IBUF_BITMAP，主要用于跟蹤隨后的每個(gè)page的change buffer信息。由于bitmap page的空間有限，同樣每隔256個(gè)extent Page之后，也會(huì)在XDES PAGE之后創(chuàng)建一個(gè)ibuf bitmap page。

• FIL_PAGE_INODE
  ibdata的第3個(gè)page的類型為FIL_PAGE_INODE，用于管理數(shù)據(jù)文件中的segment，每個(gè)inode頁可以存儲(chǔ)FSP_SEG_INODES_PER_PAGE（默認(rèn)為85）個(gè)記錄。segment是表空間管理的邏輯單位，每個(gè)索引占用2個(gè)segment，分別用于管理葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)。關(guān)于segment的詳細(xì)介紹，將在第三節(jié)展開。

• FSP_IBUF_HEADER_PAGE_NO 和 FSP_IBUF_TREE_ROOT_PAGE_NO
  上述兩個(gè)頁分別是Ibdata的第4個(gè)page和第5個(gè)page。change buffer本質(zhì)上也是btree結(jié)構(gòu)，其root頁固定在第5個(gè)page FSP_IBUF_TREE_ROOT_PAGE_NO。 由于FSP_IBUF_TREE_ROOT_PAGE_NO中原先用于記錄leaf inode entry的字段被用于維護(hù)空閑page鏈表了，因此ibdata需要使用第4頁FSP_IBUF_TREE_ROOT_PAGE_NO 來對(duì)ibuf進(jìn)行空間管理。

• FSP_TRX_SYS_PAGE_NO
  ibdata第6個(gè)page的類型為FSP_TRX_SYS_PAGE_NO，記錄了innodb重要的事務(wù)系統(tǒng)信息，包括持久化的最大事務(wù)ID，以及128個(gè)rseg（rollback segment）的地址，double write位置等。這128個(gè)rseg中，rseg0固定在ibdata中，rseg1-rseg32用于管理臨時(shí)表，rseg33-rseg128 當(dāng)未開啟undo獨(dú)立表空間 （innodb undo tablespace = 0）時(shí)，仍放在ibdata中，否則放在undo獨(dú)立表空間中。每個(gè)rseg中記錄了1024個(gè)slot，每個(gè)slot也都可對(duì)應(yīng)一個(gè)事務(wù)，用于管理該事務(wù)的undo記錄。由于每個(gè)slot也需要申請(qǐng)和釋放page，因此每個(gè)slot也對(duì)應(yīng)一個(gè)segment（空間管理邏輯單位）。

• FSP_DICT_HDR_PAGE_NO
  ibdata第8個(gè)page的類型為FSP_DICT_HDR_PAGE_NO，用來存儲(chǔ)數(shù)據(jù)詞典表的信息 。該頁存儲(chǔ)了SYS_TABLES，SYS_TABLE_IDS，SYS_COLUMNS，SYS_INDEXES和SYS_FIELDS的root page，以及當(dāng)前最大的TABLE_ID/ROW_ID/INDEX_ID/SPACE_ID。當(dāng)對(duì)用戶表操作時(shí)，需要先從數(shù)據(jù)字典表中獲取到用戶表對(duì)應(yīng)的表空間，以及其索引root頁的page_no，才能定位到具體數(shù)據(jù)的位置，對(duì)其進(jìn)行增刪改查。（只有拿到數(shù)據(jù)詞典表，才能根據(jù)其中存儲(chǔ)的表信息，進(jìn)一步找到其對(duì)應(yīng)的表空間，以及表的聚集索引所在的page no）

• double write buffer
  innodb使用double write buffer來防止數(shù)據(jù)頁的部分寫問題，在寫一個(gè)數(shù)據(jù)頁之前，總是先寫double write buffer，再寫數(shù)據(jù)文件。當(dāng)崩潰恢復(fù)時(shí)，如果數(shù)據(jù)文件中page損壞，會(huì)嘗試從dblwr中恢復(fù)。double write buffer總共128個(gè)page，劃分為兩個(gè)block。由于dblwr在安裝實(shí)例時(shí)已經(jīng)初始化好了，這兩個(gè)block在Ibdata中具有固定的位置，page64 ~127 劃屬第一個(gè)block，page 128 ~191劃屬第二個(gè)block。

當(dāng)innodb_file_per_table為off狀態(tài)時(shí)，所有用戶表也將和SYS_TABLE / SYS_INDEX 等系統(tǒng)表一樣，存儲(chǔ)在ibdata中。當(dāng)開啟innodb_file_per_table時(shí)，innodb會(huì)為每一個(gè)用戶表建立一個(gè)獨(dú)立的ibd文件。該ibd文件存放了對(duì)應(yīng)用戶表的索引數(shù)據(jù)和插入緩沖bitmap。 而該表的回滾數(shù)據(jù)（undo）仍記錄在ibdata中。

3 文件邏輯結(jié)構(gòu)

3.1 基本邏輯結(jié)構(gòu)

innodb為了組織各extent，在表空間的第一個(gè)page還維護(hù)了三個(gè)extent的鏈表：FSP_FREE、FSP_FREE_FRAG、FSP_FULL_FRAG。分別將extent完全未被使用，部分被使用，完全被使用的Xdes entry串聯(lián)起來。

innodb的邏輯管理管理單位是段（segment 或稱 inode）。為節(jié)省空間，每個(gè)segment都先從表空間FREE_FRAG中分配32個(gè)頁（FSEG_FRAG_ARR），當(dāng)這些32個(gè)頁面不夠使用時(shí)。按照以下原則進(jìn)行擴(kuò)展：如果當(dāng)前小于1個(gè)extent，則擴(kuò)展到1個(gè)extent滿；當(dāng)表空間小于32MB時(shí)，每次擴(kuò)展一個(gè)extent；大于32MB時(shí)，每次擴(kuò)展4個(gè)extent。

在為segment分配空閑的extent時(shí)，如果表空間FSP_FREE上沒有空閑的segment，則會(huì)為FSP_FREE重新初始化一些空閑extent。extent的分配類似于實(shí)現(xiàn)了一套借還機(jī)制。segment向表空間租借extent，只有segment退還該空間時(shí)，該extent才能重新出現(xiàn)在FSP_FREE/FSP_FULL_FRAG/FSP_FULL中。

segment內(nèi)部為了管理起這些分配來的extent。也有三個(gè)extent鏈表：FSEG_FREE、FSEG_NOT_FULL、FSEG_FULL。也分別對(duì)應(yīng)extent完全未被使用，部分被使用，完全被使用的Xdes entry。這三個(gè)鏈表的地址被記錄在inode entry中。INode entry的具體結(jié)構(gòu)如下表所示：

從上文我們可以看到，innodb通過inode entry來管理每個(gè)Segment占用的數(shù)據(jù)頁，每個(gè)segment可以看做一個(gè)文件頁維護(hù)單元。inode entry所在的inode page有可能存放滿，因此又通過頭Page（FIL_PAGE_TYPE_FSP_HDR）中維護(hù)了兩個(gè)inode Page鏈表FSP_SEG_INODES_FULL和FSP_SEG_INODES_FREE。前者對(duì)應(yīng)沒有空閑inode entry的inode page鏈表，后者對(duì)應(yīng)的至少有一個(gè)空閑inode entry的inode page鏈表。

3.2 索引

ibd文件中真正構(gòu)建起用戶數(shù)據(jù)的結(jié)構(gòu)是BTREE。表中的每一個(gè)索引對(duì)應(yīng)一個(gè)btree。主鍵（cluster index）對(duì)應(yīng)btree的葉子節(jié)點(diǎn)上記錄了行的全部列數(shù)據(jù)（加上transaction id列及rollback ptr）。當(dāng)表中無主鍵時(shí)，innodb會(huì)為該表每一行分配一個(gè)唯一的rowID，并基于它構(gòu)造btree。如果表中存在二級(jí)索引（secondary index），那么其BTREE葉子節(jié)點(diǎn)存儲(chǔ)了鍵值加上cluster index索引鍵值。

每個(gè)btree使用兩個(gè)Segment來管理數(shù)據(jù)頁，一個(gè)管理葉子節(jié)點(diǎn)（leaf segment），一個(gè)管理非葉子節(jié)點(diǎn)（non-leaf segment）。這兩個(gè)segment的inode entry地址記錄在btree的root page中。root page分配在non-leaf segment第一個(gè)碎片頁上（FSEG_FRAG_ARR）。

當(dāng)對(duì)一個(gè)表進(jìn)行增刪改查的操作時(shí)，我們首先需要從ibdata的第8頁FSP_DICT_HDR_PAGE_NO中l(wèi)oad改表的元數(shù)據(jù)信息，從SYS_INDEXES表中獲取該表各索引對(duì)應(yīng)的root page no，進(jìn)而通過root page對(duì)這個(gè)表的用戶數(shù)據(jù)btree進(jìn)行操作。表空間的邏輯結(jié)構(gòu)如下圖所示：

表空間邏輯結(jié)構(gòu)

3.3 索引頁數(shù)據(jù)

索引最基本的頁類型為FIL_PAGE_INDEX，其結(jié)構(gòu)如下表所示。Index Header中記錄了page所在Btree層次，所屬index ID，page directory槽數(shù)等與頁面相關(guān)的信息。Fseg Header中記錄了該index的leaf-segment和non-leaf segment的inode entry，system records包括infimum和supremum，分別代表該頁最小、最大記錄虛擬記錄。page directory是頁內(nèi)記錄的索引。Btree只能檢索到記錄所在的page，page內(nèi)的檢索需要使用到通過page directory構(gòu)建起的二分查找。

innodb按行存放數(shù)據(jù)。當(dāng)前MySQL支持等行格式包括antelope（compact和redundant），和barracuda（dynamic和compressed）。barracuda與antelope主要區(qū)別在于其處理行外數(shù)據(jù)等方式，barracuda只存儲(chǔ)行外數(shù)據(jù)等地址指針，不像antelope一樣存放768字節(jié)的行前綴內(nèi)容。以compact行格式為例介紹行格式的具體內(nèi)容，如下圖所示，行由變長(zhǎng)字段長(zhǎng)度列表、NULL標(biāo)志位、記錄頭信息、系統(tǒng)列、用戶列組成。記錄頭信息中存放刪除標(biāo)志、列總數(shù)、下行相對(duì)偏移等信息、系統(tǒng)列包括rowID、transactionID、rollback pointer等組成。

4 文件管理過程

下面用精簡(jiǎn)后的源碼來簡(jiǎn)單介紹innodb文件的管理過程：

4.1 btree的創(chuàng)建過程

btree的創(chuàng)建過程可以概括為：先創(chuàng)建non_leaf segment，利用non_leaf segment的首頁（即32個(gè)碎片頁中第一頁）作為root page；然后創(chuàng)建leaf_segment；最后對(duì)root page進(jìn)行必要的初始化。詳細(xì)過程請(qǐng)參考以下代碼：

btr_create(
    ulint           type,
    ulint           space,
    const page_size_t&  page_size,
    index_id_t      index_id,
    dict_index_t*       index,
    const btr_create_t* btr_redo_create_info,
    mtr_t*          mtr)
{
    /* index tree 的segment headers 存儲(chǔ)于新分配的root page中，ibuf tree的
    segment headers放在獨(dú)立的ibuf header page中。以下代碼屏蔽了ibuf tree的
    創(chuàng)建邏輯，重點(diǎn)介紹index tree的創(chuàng)建過程 */
    
    /* 局部變量 */
    ...
    
    /* 創(chuàng)建一個(gè)non_leaf segment段，并將段的地址存儲(chǔ)到段首頁偏移為
    PAGE_HEADER + PAGE_BTR_SEG_TOP的位置，用block記錄下non_leaf segment
    段首頁page對(duì)應(yīng)的block，該block將作為該btree的root page */
    block = fseg_create(space, 0,
                   PAGE_HEADER + PAGE_BTR_SEG_TOP, mtr);
    
    if (block == NULL) {

        return(FIL_NULL);
    }

    /* 記錄下root page的信息 */
    page_no = block->page.id.page_no();
    frame = buf_block_get_frame(block);


    /* 創(chuàng)建leaf_segment，并將段首存儲(chǔ)到root page上偏移為
    PAGE_HEADER + PAGE_BTR_SEG_LEAF的位置 */
    if (!fseg_create(space, page_no,
             PAGE_HEADER + PAGE_BTR_SEG_LEAF, mtr)) {
             
        /* 沒有足夠的空間分配新的segment，需要釋放掉已分配的root page */
        btr_free_root(block, mtr);
        return(FIL_NULL);
    }

    /* 在root page上做index page的初始化，根據(jù)頁面壓縮與否做不同處理 */
    page_zip = buf_block_get_page_zip(block);
    if (page_zip) {
        /* 其他邏輯 */
        page = page_create_zip(block, index, 0, 0, NULL, mtr);
    } else {
        /* 其他邏輯 */
        page = page_create(block, mtr,
                   dict_table_is_comp(index->table),
                   dict_index_is_spatial(index));
    }

    /* 在root page上設(shè)置其所在的index id */
    btr_page_set_index_id(page, page_zip, index_id, mtr);

    /* 將root page的前后頁面設(shè)置為NULL */
    btr_page_set_next(page, page_zip, FIL_NULL, mtr);
    btr_page_set_prev(page, page_zip, FIL_NULL, mtr);

    /* 其他邏輯 */
    
    /* 返回root page的頁面號(hào) */
    return(page_no);
}

4.2 segment的創(chuàng)建過程

segment的創(chuàng)建過程比較簡(jiǎn)單：先在inode page中為segment分配一個(gè)inode entry，然后再inode entry上進(jìn)行初始化，更新space header里的最大segment id，即可。需要注意的是：當(dāng)傳入的page 為0 時(shí)，意味著要?jiǎng)?chuàng)建一個(gè)獨(dú)立的segment，需要將當(dāng)前的inode entry地址記錄在段首page中，并返回；當(dāng)傳入的page非0時(shí)，segment需要在指定的page的指定位置記錄下當(dāng)前的inode entry地址。詳細(xì)過程請(qǐng)參考代碼：

buf_block_t*
fseg_create_general(
/*================*/
    ulint   space_id,/*!< in: space id */
    ulint   page,   /*!< in: page where the segment header is placed: if
            this is != 0, the page must belong to another segment,
            if this is 0, a new page will be allocated and it
            will belong to the created segment */
    ulint   byte_offset, /*!< in: byte offset of the created segment header
            on the page */
    ibool   has_done_reservation, /*!< in: TRUE if the caller has already
            done the reservation for the pages with
            fsp_reserve_free_extents (at least 2 extents: one for
            the inode and the other for the segment) then there is
            no need to do the check for this individual
            operation */
    mtr_t*  mtr)    /*!< in/out: mini-transaction */
{
    /* 局部變量 */
    ...
    
    /* 如果傳入的page是0，則創(chuàng)建一個(gè)獨(dú)立的段，并把segment header的信息
    存儲(chǔ)在段首page中。如果傳入page是非0，則這是一個(gè)非獨(dú)立段，需要將
    segment header的信息存儲(chǔ)在指定page的指定位置上 */
    
    if (page != 0) {
        /* 獲取指定page */
        block = buf_page_get(page_id_t(space_id, page), page_size,
                     RW_SX_LATCH, mtr);

        header = byte_offset + buf_block_get_frame(block);
    }
    
    /* 其他邏輯 */

    /* 獲取space header和inode_entry */
    space_header = fsp_get_space_header(space_id, page_size, mtr);
    inode = fsp_alloc_seg_inode(space_header, mtr);
    if (inode == NULL) {

        goto funct_exit;
    }

    /* 獲取當(dāng)前表空間最大segment id，并更新表空間最大
    segment id */
    seg_id = mach_read_from_8(space_header + FSP_SEG_ID);
    mlog_write_ull(space_header + FSP_SEG_ID, seg_id + 1, mtr);

    /* 初始化inode entry的segment id 和 FSEG_NOT_FULL_N_USED */
    mlog_write_ull(inode + FSEG_ID, seg_id, mtr);
    mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr);

    /* 初始化inode entry的三個(gè)extent鏈表 */
    flst_init(inode + FSEG_FREE, mtr);
    flst_init(inode + FSEG_NOT_FULL, mtr);
    flst_init(inode + FSEG_FULL, mtr);

    /* 初始化innode entry的32個(gè)碎片頁 */
    mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE,
             MLOG_4BYTES, mtr);
    for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
        fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr);
    }

    /* 如果傳入的page是0，則分配一個(gè)段首page */
    if (page == 0) {
        block = fseg_alloc_free_page_low(space, page_size,
                         inode, 0, FSP_UP, RW_SX_LATCH,
                         mtr, mtr
#ifdef UNIV_DEBUG
                         , has_done_reservation
#endif /* UNIV_DEBUG */
                         );

        header = byte_offset + buf_block_get_frame(block);
        mlog_write_ulint(buf_block_get_frame(block) + FIL_PAGE_TYPE,
                 FIL_PAGE_TYPE_SYS, MLOG_2BYTES, mtr);
    }

    /* 在page指定位置記錄segment header，segment header由
    inode page所在的space id，page no, 以及inode entry的在
    inode page 中的頁內(nèi)偏移組成 */
    mlog_write_ulint(header + FSEG_HDR_OFFSET,
             page_offset(inode), MLOG_2BYTES, mtr);

    mlog_write_ulint(header + FSEG_HDR_PAGE_NO,
             page_get_page_no(page_align(inode)),
             MLOG_4BYTES, mtr);

    mlog_write_ulint(header + FSEG_HDR_SPACE, space_id, MLOG_4BYTES, mtr);

funct_exit:

    DBUG_RETURN(block);
}

4.3 extent的分配過程

表空間分配extent的邏輯比較簡(jiǎn)單，直接查詢FSP_FREE上有沒有剩余的extent即可，沒有的話就為FSP_FREE重新初始化一些extent。詳細(xì)邏輯如下：

static
xdes_t*
fsp_alloc_free_extent(
    ulint           space_id,
    const page_size_t&  page_size,
    ulint           hint,
    mtr_t*          mtr)
{
    /* 局部變量 */
    ...

    /* 獲取space header */
    header = fsp_get_space_header(space_id, page_size, mtr);

    /* 獲取hint頁所在的xdes entry */
    descr = xdes_get_descriptor_with_space_hdr(
        header, space_id, hint, mtr, false, &desc_block);

    fil_space_t*    space = fil_space_get(space_id);
    
    /* 當(dāng)hint頁所在的xdes entry的狀態(tài)是XDES_FREE時(shí)，直接將其摘下返回，
    否則嘗試從FSP_FREE中為segment分配extent。如果FSP_FREE為空，
    則需要進(jìn)一步從未初始化的空間中為FSP_FREE新分配一些extent，
    并從新的FSP_FREE中取出第一個(gè)extent返回 */
    if (descr && (xdes_get_state(descr, mtr) == XDES_FREE)) {
        /* Ok, we can take this extent */
    } else {
        /* Take the first extent in the free list */
        first = flst_get_first(header + FSP_FREE, mtr);

        if (fil_addr_is_null(first)) {
            fsp_fill_free_list(false, space, header, mtr);

            first = flst_get_first(header + FSP_FREE, mtr);
        }

        /* 分配失敗 */
        if (fil_addr_is_null(first)) {

            return(NULL);   /* No free extents left */
        }

        descr = xdes_lst_get_descriptor(
            space_id, page_size, first, mtr);
    }

    /* 將分配到的extent從FSP_FREE中刪除 */
    flst_remove(header + FSP_FREE, descr + XDES_FLST_NODE, mtr);
    space->free_len--;

    return(descr);
}

當(dāng)為segment分配extent時(shí)稍微復(fù)雜一些：先檢查FSEG_ FREE中是否有剩余的extent，如果沒有再用fsp_alloc_free_extent從表空間中申請(qǐng)extent。在第二種情況下，F(xiàn)SEG_ FREE中的extent不足，因此還會(huì)進(jìn)一步嘗試為FSEG_FREE分配更多extent。詳細(xì)過程如下：

static
xdes_t*
fseg_alloc_free_extent(
    fseg_inode_t*       inode,
    ulint           space,
    const page_size_t&  page_size,
    mtr_t*          mtr)
{
    /* 局部變量 */
    ...

    /* 如果FSEG_FREE非空，則從其中為segment分配extent，如果FSEG_FREE為空，
    則從調(diào)用fsp_alloc_free_extent 為當(dāng)前segment分配extent */
    if (flst_get_len(inode + FSEG_FREE) > 0) {
        first = flst_get_first(inode + FSEG_FREE, mtr);

        descr = xdes_lst_get_descriptor(space, page_size, first, mtr);
    } else {
        descr = fsp_alloc_free_extent(space, page_size, 0, mtr);

        if (descr == NULL) {

            return(NULL);
        }
        
        /* 將從space申請(qǐng)到的extent設(shè)置為segment私有狀態(tài)（XDES_FSEG），
        將改extent加入到FSEG_FREE中 */
        seg_id = mach_read_from_8(inode + FSEG_ID);

        xdes_set_state(descr, XDES_FSEG, mtr);
        mlog_write_ull(descr + XDES_ID, seg_id, mtr);
        flst_add_last(inode + FSEG_FREE, descr + XDES_FLST_NODE, mtr);

        /* 當(dāng)前FSEP_FREE中剩余的extent不多，嘗試為當(dāng)前segment分配更多
        物理相鄰的extent */
        fseg_fill_free_list(inode, space, page_size,
                    xdes_get_offset(descr) + FSP_EXTENT_SIZE,
                    mtr);
    }

    return(descr);
}

4.4 page的分配過程

表空間page的分配過程如下：先查看hint_page所在的extent是否適合分配空閑頁面，不適合的話，則嘗試從FSP_FREE_FRAG鏈表中尋找空閑頁面。如果FSP_FREE_FRAG為空，則新分配一個(gè)extent，將其添加到FSP_FREE_FRAG中，并在其中分配空閑頁面。

static MY_ATTRIBUTE((warn_unused_result))
buf_block_t*
fsp_alloc_free_page(
    ulint           space,
    const page_size_t&  page_size,
    ulint           hint,
    rw_lock_type_t      rw_latch,
    mtr_t*          mtr,
    mtr_t*          init_mtr)
{
    /* 局部變量 */
    ...
    
    /* 獲取表空間header 和 hint page所在extent的xdes entry */
    header = fsp_get_space_header(space, page_size, mtr);
    
    descr = xdes_get_descriptor_with_space_hdr(header, space, hint, mtr);

    /* 如果xdes entry的狀態(tài)是XDES_FREE_FRAG，那就直接從該extent中分配page，
    否則從FSP_FREE_FRAG中去尋找空閑page */
    if (descr && (xdes_get_state(descr, mtr) == XDES_FREE_FRAG)) {
        /* Ok, we can take this extent */
    } else {
        /* Else take the first extent in free_frag list */
        first = flst_get_first(header + FSP_FREE_FRAG, mtr);

        /* 嘗試從FSP_FREE_FRAG中尋找空閑頁面，當(dāng)FSP_FREE_FRAG鏈表為空時(shí)，
        需要使用fsp_alloc_free_extent分配一個(gè)新的extent，將該extent加入
        FSP_FREE_FRAG,并在其中分配空閑page */
        if (fil_addr_is_null(first)) {
            descr = fsp_alloc_free_extent(space, page_size,
                              hint, mtr);

            if (descr == NULL) {
                /* No free space left */

                return(NULL);
            }

            xdes_set_state(descr, XDES_FREE_FRAG, mtr);
            flst_add_last(header + FSP_FREE_FRAG,
                      descr + XDES_FLST_NODE, mtr);
        } else {
            descr = xdes_lst_get_descriptor(space, page_size,
                            first, mtr);
        }

        /* Reset the hint */
        hint = 0;
    }

    /* 從找到的extent中分配一個(gè)空閑頁面 */
    free = xdes_find_bit(descr, XDES_FREE_BIT, TRUE,
                 hint % FSP_EXTENT_SIZE, mtr);
    if (free == ULINT_UNDEFINED) {

        ut_print_buf(stderr, ((byte*) descr) - 500, 1000);
        putc('\n', stderr);

        ut_error;
    }

    page_no = xdes_get_offset(descr) + free;

    /* 其他邏輯 */

    /* 在fsp_alloc_from_free_frag中設(shè)置分配page的XDES_FREE_BIT為false，
    表示被占用；遞增頭page的FSP_FRAG_N_USED字段；如果該extent被用滿了，
    就將其從FSP_FREE_FRAG移除，并加入到FSP_FULL_FRAG鏈表中，更新FSP_FRAG_N_USED的值 */
    fsp_alloc_from_free_frag(header, descr, free, mtr);
    
    /* 對(duì)Page內(nèi)容進(jìn)行初始化后返回 */
    return(fsp_page_create(page_id_t(space, page_no), page_size,
                   rw_latch, mtr, init_mtr));
}

為了能夠使得segment內(nèi)邏輯上相鄰的節(jié)點(diǎn)在物理上也盡量相鄰，盡量提高表空間的利用率，在segment中分配page的邏輯較為復(fù)雜。詳細(xì)過程如下所述：

static
buf_block_t*
fseg_alloc_free_page_low(
    fil_space_t*        space,
    const page_size_t&  page_size,
    fseg_inode_t*       seg_inode,
    ulint           hint,
    byte            direction,
    rw_lock_type_t      rw_latch,
    mtr_t*          mtr,
    mtr_t*          init_mtr
#ifdef UNIV_DEBUG
    , ibool         has_done_reservation
#endif /* UNIV_DEBUG */
)
{
    /* 局部變量 */
    ...

    /* 計(jì)算當(dāng)前segment使用的和占用的page數(shù)。前者統(tǒng)計(jì)的統(tǒng)計(jì)方法為
    累加32個(gè)碎片頁中已使用的數(shù)量，F(xiàn)SEG_FULL/FSEG_NOT_FULL中已使
    用page的數(shù)量，后者的統(tǒng)計(jì)方法為累加32個(gè)碎片頁已使用數(shù)量，
    FSEG_FULL/FSEG_NOT_FULL/FSEG_FREE三個(gè)鏈表中總page數(shù)*/
    reserved = fseg_n_reserved_pages_low(seg_inode, &used, mtr);

    /* 獲取表空間header 和 hint page所在extent的xdes entry */
    space_header = fsp_get_space_header(space_id, page_size, mtr);
    descr = xdes_get_descriptor_with_space_hdr(space_header, space_id,
                           hint, mtr);
    if (descr == NULL) {
        /* 說明hint page在free limit之外，將hint page置0，取消hint page的作用*/
        hint = 0;
        descr = xdes_get_descriptor(space_id, hint, page_size, mtr);
    }

    /* In the big if-else below we look for ret_page and ret_descr */
    /*-------------------------------------------------------------*/
    if ((xdes_get_state(descr, mtr) == XDES_FSEG)
        && mach_read_from_8(descr + XDES_ID) == seg_id
        && (xdes_mtr_get_bit(descr, XDES_FREE_BIT,
                 hint % FSP_EXTENT_SIZE, mtr) == TRUE)) {
take_hinted_page:
        /* 1. hint page所在的extent屬于當(dāng)前segment，并且
        hint page也是空閑狀態(tài)，這是最理想的情況 */
        ret_descr = descr;
        ret_page = hint;
        
        goto got_hinted_page;
        /*-----------------------------------------------------------*/
    } else if (xdes_get_state(descr, mtr) == XDES_FREE
           && reserved - used < reserved / FSEG_FILLFACTOR
           && used >= FSEG_FRAG_LIMIT) {

        /* 2. segment空間利用率高于臨界值（7/8 ，F(xiàn)SEG_FILLFACTOR)，
        并且hint page所在的extent處于XDES_FREE狀態(tài)，直接將該extent從
        FSP_FREE摘下，分配至segment的FSEG_FREE中，返回hint page */
        
        ret_descr = fsp_alloc_free_extent(
            space_id, page_size, hint, mtr);

        xdes_set_state(ret_descr, XDES_FSEG, mtr);
        mlog_write_ull(ret_descr + XDES_ID, seg_id, mtr);
        flst_add_last(seg_inode + FSEG_FREE,
                  ret_descr + XDES_FLST_NODE, mtr);

        /* 在利用率條件允許的情況下，為segment的FSEG_FREE多分配幾個(gè)
        物理相鄰的extent */
        fseg_fill_free_list(seg_inode, space_id, page_size,
                    hint + FSP_EXTENT_SIZE, mtr);
                    
        goto take_hinted_page;
        /*-----------------------------------------------------------*/
    } else if ((direction != FSP_NO_DIR)
           && ((reserved - used) < reserved / FSEG_FILLFACTOR)
           && (used >= FSEG_FRAG_LIMIT)
           && (!!(ret_descr
              = fseg_alloc_free_extent(
                  seg_inode, space_id, page_size, mtr)))) {

        /* 3. 當(dāng)利用率小于臨界值，不建議分配新的extent，避免空間浪費(fèi)，
        此時(shí)從FSEG_FREE中獲取空閑extent，用于分配新的page */
        ret_page = xdes_get_offset(ret_descr);

        if (direction == FSP_DOWN) {
            ret_page += FSP_EXTENT_SIZE - 1;
        }
        
    } else if ((xdes_get_state(descr, mtr) == XDES_FSEG)
           && mach_read_from_8(descr + XDES_ID) == seg_id
           && (!xdes_is_full(descr, mtr))) {

        /* 4. 當(dāng)hint page所在的extent屬于當(dāng)前segment時(shí)，該extent內(nèi)如有空閑page，
        將其返回 */

        ret_descr = descr;
        ret_page = xdes_get_offset(ret_descr)
            + xdes_find_bit(ret_descr, XDES_FREE_BIT, TRUE,
                    hint % FSP_EXTENT_SIZE, mtr);

    } else if (reserved - used > 0) {
    
        /* 5. 如果該segment占用的page數(shù)大于實(shí)用的page數(shù)，說明該segment還有空
        閑的page，則依次先看FSEG_NOT_FULL鏈表上是否有未滿的extent，如果沒有，
        再看FSEG_FREE鏈表上是否有完全空閑的extent */
        fil_addr_t  first;

        if (flst_get_len(seg_inode + FSEG_NOT_FULL) > 0) {
            first = flst_get_first(seg_inode + FSEG_NOT_FULL,
                           mtr);
        } else if (flst_get_len(seg_inode + FSEG_FREE) > 0) {
            first = flst_get_first(seg_inode + FSEG_FREE, mtr);
        } else {
            return(NULL);
        }

        ret_descr = xdes_lst_get_descriptor(space_id, page_size,
                            first, mtr);
        ret_page = xdes_get_offset(ret_descr)
            + xdes_find_bit(ret_descr, XDES_FREE_BIT, TRUE,
                    0, mtr);

    } else if (used < FSEG_FRAG_LIMIT) {
    
        /* 6. 當(dāng)前segment的32個(gè)碎片頁尚未使用完畢，使用fsp_alloc_free_page從
        表空間FSP_FREE_FRAG中分配獨(dú)立的page，并加入到該inode的frag array page
        數(shù)組中 */
        buf_block_t* block = fsp_alloc_free_page(
            space_id, page_size, hint, rw_latch, mtr, init_mtr);

        if (block != NULL) {
            /* Put the page in the fragment page array of the
            segment */
            n = fseg_find_free_frag_page_slot(seg_inode, mtr);

            fseg_set_nth_frag_page_no(
                seg_inode, n, block->page.id.page_no(),
                mtr);
        }

        return(block);

    } else {
        /* 7. 當(dāng)上述情況都不滿足時(shí)，直接使用fseg_alloc_free_extent分配一個(gè)空閑
        extent，并從其中取一個(gè)page返回 */

        ret_descr = fseg_alloc_free_extent(seg_inode,
                           space_id, page_size, mtr);

        if (ret_descr == NULL) {
            ret_page = FIL_NULL;
            ut_ad(!has_done_reservation);
        } else {
            ret_page = xdes_get_offset(ret_descr);
        }
    }

    /* page分配失敗 */
    if (ret_page == FIL_NULL) {
        return(NULL);
    }

got_hinted_page:

    /* 將可用的hint page標(biāo)記為used狀態(tài) */
    if (ret_descr != NULL) {
        fseg_mark_page_used(seg_inode, ret_page, ret_descr, mtr);
    }

    /* 對(duì)Page內(nèi)容進(jìn)行初始化后返回 */
    return(fsp_page_create(page_id_t(space_id, ret_page), page_size,
                   rw_latch, mtr, init_mtr));
}

5 總結(jié)

innodb的文件結(jié)構(gòu)由自下而上包括page（頁），extent（簇），segment（段），tablespace（表空間）等幾個(gè)層次。page是最基本的物理單位，所有page具有相同的頁首和頁尾；extent由通常由連續(xù)的64個(gè)page組成，tablespace由一個(gè)個(gè)連續(xù)的extent組成；段是用來管理物理文件的邏輯單位，可以向表空間申請(qǐng)分配和釋放page 或 extent，是構(gòu)成索引，回滾段的基本元素；表空間是一個(gè)宏觀概念，當(dāng)innodb_file_per_table為ON時(shí)一個(gè)用戶表對(duì)應(yīng)一個(gè)表空間。