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這兩個磁盤鏈表。以下是分配示意圖：  上圖中，1~7是屬于inode申請分配流程， 8~12是屬于frag page的申請extent方式 ? 1: 當inode的free list為空，如果需要使用申請使用新的extent，innodb會從space free list獲得空閑的extent加入到inode free list當中。 ? 2: 當inode ?free list中有extent,如果申請使用新的extent，只只需要從inode free list中拿取，并將extent移到inode not full當中。 ? 3:只是通過inode方式申請頁的一個操作，這個時候extent有足夠多的空閑page. ? 4: 當extent中沒有空閑的page時，會將這個extent從inode not full中轉移到inode full當中。 ? 5: 當一個page釋放時，這個page所處的extent是一個完全占用的且被inode管理的extent,那么page釋放后，就會將這個extent從inode full移到inode not full ? 6:當一個page釋放時，這個page所處的extent有且只有這一個page被占用，那么page釋放后,這個extent就會歸還給inode list.并且會直接進行 7將extent歸還給space free list. ** 8~12和以上步驟類似** ### 4.3page的分配流程 page的申請分配是基于inode 申請和extent申請的基礎上，頁的申請有外部通過inode方式申請，也有通過fragment page方式申請。fragment方式申請相對比較簡單，就不在表述，源碼中很清晰。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的存儲方式和其工作原理。