MySQL系列：innodb源碼分析之表空間管理
innodb在實現表空間（table space）基於文件IO之上構建的一層邏輯存儲空間管理，table space采用邏輯分層的結構：space、segment inode、extent和page.在實現層的邏輯使用了磁盤鏈表這種結構來管理邏輯關系。我們先來介紹磁盤鏈表。
1.磁盤鏈表
磁盤鏈表的實現fut0lst.*文件當中， innodb為了管理表空間和索引模塊，定義了一個基於磁盤的鏈表，主要是用來保存磁盤數據結構之間的關系。這個鏈表不是基於內存指針的，而是基於page no和boffset來做位置綁定的。在innodb中定義了一個fil_addr_t的結構來做描述：
typedef struct fil_addr_struct
{
ulint page; /*page在space中的編號*/
ulint boffset; /*page中的字節偏移量，在內存中使用2字節表示*/
}fil_addr_t;
fil_addr_t可以通過fut_get_ptr函數來獲得對應node的內存位置(flst_node_t)
flst_node_t可以通過buf_ptr_get_fsp_addr來確定fil_addr_t。
flst_node_t中存有12個字節的內容，前6個字節（page:4 boffset:2）表示相對自己前一個node的fil_addr_t信息，後6個字節表示相對自己後1個node的fil_addr_t。除了flst_node_t以外，磁盤鏈表還有一個頭信息flst_base_node_t，頭信息是一個節點個數FLST_LEN（4字節） + FLST_FIRST (6字節)+ FLST_LAST（6字節）.
1.1磁盤鏈表的結構關系
2.space結構分析
在innodb的表空間中，所有的數據都是以page為單位來存儲的，在space(表空間)中有兩種
page: FSP_HDR/XDES Page、fseg inodes Page。每個page是以默認16KB的大小存儲的，
innodb在分配page的時候總以一個extent為單位一次性分配64個page。
2.1 FSP HDR/XDES Page
2.1.1XDES結構分析（extent）
這個類型的page主要存儲兩類信息，前面112個字節存儲的是File Space header信息，後面剩余的空間存儲多個extent描述信息（XDES ），具體存儲結構圖如下：
只有space的第一個page會保存FSP header,其他的頁是用0填充的。 每個XDES Page最大包含256個XDES descritptors Entry，每個XDES descritptors Entry對應的是一個extent。XDES descritptors Entry的結構描述如下：
File Segment ID 是當前extent所屬segment的ID
XDES list 是磁盤雙向鏈表的一個節點，分別指向前一個XDES entry的page位置和後一個
XDES entry的page位置
state extent的狀態, XDES_FREE、XDES_FREE_FRAG、XDES_FULL_FRAG、
XDES_FSEG,在為XDES_FSEG的時候，表示這個extent已經隸屬於一個
Segment,extent在創建的時候會指定成XDES_FSEG狀態。一個extent在剛
分配時的狀態XDES_FREE.
bitmap 當前extent的所有page的狀態索引，一個page占用2 bit,第一個bit表示是否被使用
狀態，第二個位表示是否並 清空狀態，清空狀態暫時好像沒有用 到，都是TRUE。
2.1.2 FSP Header
space id 當前表空間的ID
size 當前space最大可容納的page數,文件擴大時才會改變這個值
limit 當前space已經分配初始化的page數,包括空閒的和已經使用的
flag 未起作用
frage used FSP_FREE_FRAG列表中已經被使用的page數
free list space中可用的extent對象列表，extent裡面沒有一個page被使用
frag free list 有可用碎葉page的extent列表，exntent裡面有部分page被使用
frag full list 沒有有可用page的extent列表，exntent裡面全部page被使用
segment id 下一個可利用的segment id
full inode list space當前完全占滿的segment inode頁列表
free inode list space當前完全占滿的segment inode頁列表
2.2 Fseg inode Page
這個頁類型是存儲fseg inode用的頁，每個inode 占用192個字節，一個page存儲有85個inode對象,結構如下：
在FIL Header後面緊接了12個字節，這個12個字節其實就是full inode list或則free inode list中的列表所以，分別表示前後的fil_addr_t。每個inode信息占用192個字節，裡面分別管理對應的extent和fragment page。inode 結構如下：
fseg id segment ID
not full used FSEG_NOT_FULL列表中的page數
FSEG_FREE inode中空閒的extent列表
FSEG_NOT_FULL extent有部分page被占用，有部分page空閒的extent列表
FSEG_FULL 完全占滿的extent的列表
FSEG_MAGIC_N 校驗魔法字
fragment array 一個長度為32的零散page索引存儲的數組，如果這個數據滿了.主要的作用是
節省空間，例如在表剛建立時，不會分配一個完整的extent給表用，只會分配
6個PAGE頁，這時候就需要用fragment array來管理。
3.space結構圖
3.1space框架關系圖
3.2模塊關系示意圖
4.space的inode、extent和page分配流程
innodb的space中，inode、extent和page之間的關系是環環相扣的，inode對應的是segment，extent對應的是區，page是頁，也是表空間的最小分配單位。一個page在MySQL中默認是16KB大小，一個extent管理64個page,大小為1M，而inode可以管理很多extent加32個frag page（碎頁）。frag page是為了節省空間而定義的。在了解了以上基本的概念後，我們開始分析inode的分配、extent的分配和page的分配過程。
4.1 inode的分配流程
通過inode page的介紹我們可以知道，inode信息一定是存儲在inode page中的，在分配inode的時候，一定是從inode page中獲取空閒的inode。如果沒有inode page可以使用，會先去在space的free list得到一個inode page（在函數fsp_alloc_seg_inode_page），然後再在這個inode page獲得空閒的inode。在這個過程中會涉及到兩個磁盤鏈表：FSP_SEG_INODES_FREE和FSP_SEG_INODES_FULL，這兩個隊列是管理inode
page的，如果沒有空閒inode的inode page是放在FSP_SEG_INODES_FULL中的，如果還有空閒inode的inode page是放在FSP_SEG_INODES_FREE中。一個inode頁包含85個inode信息。以下是inode 分配示意圖：
第1步：在FSP_SEG_INODES_FREE為空時，向space默認的頭頁中獲取一個inode page，對應函數fsp_alloc_seg_inode_page
第2步：在申請inode時，如果FSP_SEG_INODES_FREE有可以的inode page,從inode page或的一個inode，對應函數fsp_alloc_seg_inode
第3步：如果在申請inode後，inode所處的inode page已經沒有空閒的inode了，會將這個inode page放入FSP_SEG_INODE_FULL,並將其從FSP_SEG_INODES_FREE中刪除。
第4步：如果inode管理的所有的頁都是空閒，那麼這個inode狀態會被置為空閒狀態，這個時候會將這個inode page從FSP_SEG_INODE_FULL移 到FSP_SEG_INODES_FREE中;這個過程只有在segment刪除的時候才會調用。對應的函數fsp_free_seg_inode
4.2extent的分配流程
extent的分配方式有兩種，一種是通過inode進行申請分配，一種是通過fragment碎片方式申請分配。inode分配方式是當inode中沒有空閒可用的extent的時候，會向space free list中申請1個或者5個extent進行管理，如果當inode管理的extent數量小於40時，每次只會申請1個extent,如果超過這個大小，就會一次申請5個extent，這個過程會涉及到inode的FSEG_FREE、FSEG_NOT_FULL和FSEG_FULL三個磁盤鏈表。第二種申請方式是分配frag
page時，是直接對extent進行申請，這其中會涉及到FSP_FREE_FRAG和FSP_FULL_FRAG這兩個磁盤鏈表。以下是分配示意圖：
源碼中很清晰。inode方式分配是比較復雜的，其主要實現是在fseg_alloc_free_page_low和fseg_free_page_low這兩個函數。在fseg_alloc_free_page_low函數中實現了7種情況獲得inode中的page.
1. 指定的inode的hint位置的頁是空閒狀態，直接返回對應的page
2.descr是空閒狀態，但segment inode中的空閒page數量 < 1/8,且碎片頁被全部用完,為其分配一個extent,並獲得hint對應的page
3.如果descr不是空閒狀態，且segment inode中的空閒page數量 < 1/8,在inode當中獲得一個空閒的extent，並且將這個extent descr對應的頁返回。
4.descr是XDES_FSEG狀態，且這個extent中還有空閒page,從其中獲取一個page.
5.除了以上情況外，如果descr不是空閒的，但是inode還有其他的空閒extent,從其他的extent獲得一個空閒。
6.如果其他的extent沒有空閒頁，但是fragment array還有空閒的碎片page，從空閒的碎片page中獲得一個空閒頁。
7.如果連碎頁也沒有，直接申請分配一個新的extent，並在其中獲取一個空閒的page.
5.綜述
table space的實現在fsp0fsp.*文件當中，也依賴於page0page.* fil0fil.* 等文件。innodb在存儲上，定義了最小的存儲單位就是page，space在設計這些層關系，都是為了更為高效和合理的管理page。space可以和其他表存在同一個數據庫文件中，也可以一張表一個文件存儲。這取決於MySQL的配置。分析space的結構和工作原理有利於我們理解innodb的存儲方式，其後面理解索引、鎖和事務提供有力的基礎。上面也說到最小的存儲單位是page，我將在下一章節中單獨來介紹數據page的存儲方式和其工作原理。
