文件系統磁盤分配

在存儲知識棧上提到文件系統, 大家首先就關心他是如何管理好硬件層提供的磁盤空間的。

本文開篇就先描述典型的幾種文件系統管理磁盤的技術方案: 連續分配, 鏈式分配, 索引分配。

連續分配

顧名思義, 就是創建文件的時候, 給分配一組連續的塊。在單獨拿出一塊地方存儲各個文件的meta信息, meta信息也很簡單, 包含文件名, 起始位置和長度即可, 這個存放meta信息的地方也叫做FAT(文檔分配表)。

如下圖:

該方案的優點:

1. 簡便, 適用於一次性寫入操作;
2. 所需磁盤尋道次數和尋道時間最少;

缺點也很明顯:

1. 文件不能動態增長, 因為後面的塊可能已經分配給別人了;
2. 不利於文件的插入和刪除, 插入文件之前需要聲明文件大小;
3. 外部碎片問題;

為了克服連續分配的問題, 又進化出來了鏈式分配方案。

鏈式分配

鏈式分配即將文件塊像鏈表一樣管理起來, 每個塊中放一個指針, 指針指向下一個文件塊所在的位置。這樣在FAT中存儲也很簡單, 只需要存儲文件名, 起始塊號和結束塊號(都可以不存)。

如下圖:

該方案的優點:

1. 提高磁盤利用率, 沒有碎片問題
2. 有利於文件的插入, 刪除

缺點:

1. 存取速度慢, 需要移動的磁道次數多, 尋道時間長;
2. 讀寫任何一個地方都需要沿著指針前進直到找到對應塊為止;
3. 鏈接佔據了一定的磁盤空間, 數據不是嚴格按照塊大小分配;

索引分配

這是一個折衷方案, 也是現在大部分文件系統採用的方案, 他綜合了連續分配和鏈式分配的好處。

該方案會在FAT中保存所有文件塊的位置, 各文件系統都有一套自己對應的細節分配策略, 會保證一個文件儘量連續的同時, 又避免出現大量的磁盤碎片。

如下圖:

該方案的優點是:

1. 能夠保持好大部分文件的局部性
2. 滿足文件插入, 刪除的高效
3. 隨機讀寫不需要沿著指針前進

缺點:

1. 會有較多的磁盤尋道次數
2. 索引表本身管理複雜, 也會帶來額外的系統開銷

ext文件系統

基本概念

1. 塊. 即Block, 數據存儲的最小單元, 每個塊都有一個唯一的地址, 從0開始, 起源於第一個可以用來存儲數據的扇區;
2. 超級塊. 超級塊保存了各種文件系統的meta信息, 比如塊大小信息。他位於文件系統的2號和3號扇區(物理地址), 佔用兩個扇區大小;
3. 塊組. 所有的塊會劃分成多個塊組, 每個塊組包含同樣多個塊, 但是可能整個文件系統整個塊數不是塊組的整數倍, 所以最後一個塊組包含的個數可能會小於其他塊;

總體結構

一個ext文件系統分成多個塊組, 每個塊組的結構基本相同, 如下:

解釋如下:

1. 0~1號扇區: 引導扇區. 如果沒有引導代碼, 則這兩個扇區為空, 全部用0填充;
2. 2~3號扇區: 超級塊, 超級塊包含各種meta信息:
3. 塊大小, 每個塊組包含塊數, 總塊數, 第一個塊前保留塊數, inode節點數, 每個塊組的inode節點數
4. 卷名, 最後掛載時間, 掛載路徑, 文件系統是否乾淨, 是否要調用一致性檢查標識
5. 空間inode節點和空閒塊的記錄信息, 在分配inode節點和新塊的時候使用
6. 組描述符表:
7. 位於超級塊後面的一個塊, 注意在超級塊之前只佔用了4個扇區, 如果一個塊大小超過4個扇區的話, 這裡就會有空的扇區。
8. 組描述符表中包含了所有塊組的描述信息, 每個塊組佔據32個字節(差不多是8個整數的大小)。如果格式化使用默認參數, 那麼組描述符表不會超過一塊塊組。
9. 組描述符和超級塊在每個塊組中都有一個備份, 但是激活了稀疏超級塊特徵的情況除外。
10. 稀疏超級塊即不是在所有塊組中都存儲超級塊和組描述符的備份, 默認該策略被激活, 其策略類似當塊組號是3,5,7的冪的塊組才存副本。
11. 塊位圖表
12. 每個塊對應一個bit, 只包含了本塊組的信息。而文件系統創建的時候, 默認每個塊組包含的塊數跟每個塊包含的bit數是一樣的, 這種情況下每個塊位圖表正好等於一個塊的大小。
13. 而該位圖表的塊的起始位置會在組描述符表中指定, 大小則為塊組中包含塊數個bit。
14. inode位圖塊
15. 跟塊位圖表類似, 通常情況他也只佔用一個塊。通常一個塊組中的inode節點數會小於block數量, 所以其不會超過一個塊大小。
16. inode節點表
17. 每個inode都佔用128位的一個描述信息, 起始位置在組描述符中表示, 大小為inode節點數*128。
18. 數據區
19. 這就是真正存儲數據的區域。

塊大小為4096的時候, 各部分和扇區對應關係如下圖:

塊大小為2048的時候, 各部分和扇區對應關係如下圖:

超級塊詳細信息

超級塊總是位於文件系統的第1024~2048字節處。

超級塊中包含的信息如下:

偏移(16進制)字節數含義&解釋00~034文件系統中總inode節點數04~074文件系統中總塊數08~0B4為文件系統預保留的塊數0C~0F4空閒塊數10~134空間inode節點數14~1740號塊組起始塊號18~1B4塊大小(1024左移位數)1C~1F4片段大小, 跟塊大小一模一樣20~234每個塊組中包含的塊數量24~274每個塊組中包含的片段數量, 跟包含的快數量一致28~2B4每個塊組中包含的inode節點數量2C~2F4文件系統最後掛載時間30~334文件系統最後寫入時間34~352當前掛載數36~372最大掛載數38~392文件系統簽名標識 53EF3A~3B2文件系統狀態, 正常, 錯誤, 恢復了孤立的inode節點3C~3D2錯誤處理方式, 繼續, 以只讀方式掛載3E~3F2輔版本號40~434最後進行一致性檢查的時間44~474一致性檢查的間隔時間48~4B4創建本文件系統的操作系統4C~4F4主版本號, 只有該值為1的時候, 偏移54之後的擴展超級塊的一些動態屬性值才是有意義的50~512默認為UID的保留塊52~532默認為GID的保留塊54~572第一個非保留的inode節點號, 即用戶可以使用的第一個inode節點號58~592每個inode節點的大小字節數5A~5B2本超級塊所在的塊組號5C~5F4兼容標識特徵60~634非兼容標識特徵64~674只讀兼容特徵標識68~7716文件系統ID號78~8716卷名88~C764最後的掛載路徑C8~CB4位圖使用的運算法則CC~CC1文件再分配的塊數CD~CD1目錄再分配的塊數CE~CF2未使用D0~DF16日誌IDE0~E34日誌inode節點E4~E74日誌設備E8~EB4孤立的inode節點表EC~3FF788未使用

塊組描述符詳細信息

每個塊組描述符佔用32個字節, 其數據結構如下:

偏移(16進制)字節數含義&解釋00~034塊位圖起始地址(塊號)04~074inode節點位圖起始地址(塊號)08~0B4inode節點表起始地址(塊號)0C~0D2塊組中空閒塊數0E~0F2塊組中空閒inode節點數10~112塊組中的目錄數12~1F-未使用

inode信息

每個inode會被分配給一個目錄或者一個文件, 每個inode包含了128個字節, 裡面包含了這個文件的各種meta信息。

在所有inode中, 1~10號會用作保留給內核使用, 在這些保留節點中, 2號節點用於存儲根目錄信息, 1號表示壞塊, 8號表示日誌文件信息。

第一個用戶可見的都是從11號inode開始, 11號節點一般用作lost+found目錄, 當檢查程序發現一個inode節點已經被分配, 但是沒有文件名指向他的時候, 就會把他添加到lost+found目錄中並賦予一個新的文件名。

inode通過三級指針的方式來找到文件數據最終存儲的數據塊, 見下圖:

這種方式能保證小文件的讀取效率的同時, 也支持大文件的讀取。

目錄項

在ext文件系統中, 每個目錄也對應一個inode節點, 該inode節點對應的數據塊裡面會存儲該目錄下所有文件/目錄的信息。

每個文件/目錄對應的信息就叫目錄項, 目錄項包含的內容也很簡單, 主要就是文件名和指向該文件名的inode指針, 詳細信息如下:

偏移(16進制)字節數含義&解釋00~034inode節點號04~052本目錄項的長度字節數06~061名字長度字節數07~071文件類型08~不定長度名字的ascii碼

當文件刪除的時候, 不會真正刪除文件, 會將該文件所屬目錄對應的目錄項給刪除, 同時將對應數據塊在快位圖表中標記為0。

鏈接

1. 硬鏈接是指在另外一個目錄對應的目錄項中增加一個目錄項。硬鏈接建立之後, 用戶無法通過文件名來判斷到底哪個是原文件名, 哪個是鏈接名;
2. 軟連接是一種文件類型, 該文件裡面就存儲源文件的完整路徑, 如果源文件完整路徑長度小於60個字節, 那麼就將該值直接存儲在inode節點表中, 避免浪費數據塊;

分配策略

1. 首先判斷應該在哪個塊組中分配
2. 如果是為文件創建節點
3. 默認會在其父目錄所在的組中為其創建節點, 這樣可以確保一個目錄中所有文件都位於一個大致的區域中
4. 如果父目錄所在組沒有空閒的節點或者空閒的塊了, 就到別的塊組中為該文件分配節點, 找尋別的塊組的算法如下
5. 每次講當前組號加上2^N次方再求hash
6. 如果上面的算法沒找到, 就線性查找
7. 如果是為目錄創建節點
8. 會將其分配到可用空間較多的塊組中, 分配算法如下:
9. 首先利用超級塊中的剩餘inode和剩餘塊數字算出每個塊組的平均剩餘數字, 然後依次找到一個大於平均值的塊組
10. 如果沒找到, 就利用塊組描述符表中的信息, 找到一個最空閒的塊組
11. 當一個數據塊分配給某文件之後
12. 該塊原來的內容會被請出, inode節點對應的各種元信息會跟著做修改
13. 如果是文件, 節點對應鏈接數會設置為1, 如果是目錄, 鏈接數會被設置為2

實際創建/刪除文件過程

我們創建一個/xuanku/file.txt, 該文件大小為10000字節, 文件塊大小為4096, 那麼下面來看一下過程:

1. 讀取文件系統的1024字節~2048字節, 即超級塊信息。通過超級塊得到快大小為4096, 每個塊組含有8192個塊以及2008個inode節點
2. 讀取文件系統中第1個塊(即組描述符表), 得到所有塊組佈局信息
3. 訪問2號inode節點(即根節點), 通過讀取根節點數據塊信息, 假設讀到其位於5號塊
4. 在第5號塊所有目錄項中從前往後遍歷, 直到找到文件名為xuanku的目錄項, 讀到該inode節點為4724
5. 每個塊組有2008個inode, 用4724針對2008取模, 得到的結果是2號塊組
6. 通過組描述符表中得到第2個塊組的inode節點表起始於16378號塊
7. 從16378號塊讀取inode節點表中查找4724號對應的inode節點(708號表項), 查詢到該xuanku的目錄內容位於17216號塊
8. 從17216塊讀取xuanku目錄項內容, 將file.txt相關信息更新到該塊的目錄項當中
9. 然後開始為文件分配inode節點, 默認會放到父目錄所在塊組, 即2號塊組, 再次2號塊組的inode節點表16378, 開始從4724往後找到第一個可用的inode節點分配給該文件, 假設找到的是4850號inode。
10. 然後就給4850號的inode位圖表設置為1, 組描述符的空閒inode節點數和超級塊的總空閒inode節點數都減1, 將inode節點的地址寫入file.txt對應的目錄項當中, 然後寫各種時間, 記錄日誌
11. file.txt需要3個塊的存儲空間, 通過2號塊組描述符找到塊位圖對應的塊, 並從前往後找到可用的塊。然後將對應的位設置為1, 並更新到inode節點當中
12. 然後將文件的內容寫入到對應的塊中

下面再演示一下將該文件刪除的過程:

讀取文件系統的1024字節~2048字節, 即超級塊信息。通過超級塊得到快大小為4096, 每個塊組含有8192個塊以及2008個inode節點

讀取文件系統中第1個塊(即組描述符表), 得到所有塊組佈局信息

訪問2號inode節點(即根節點), 通過讀取根節點數據塊信息, 假設讀到其位於5號塊

在第5號塊所有目錄項中從前往後遍歷, 直到找到文件名為xuanku的目錄項, 讀到該inode節點為4724

每個塊組有2008個inode, 用4724針對2008取模, 得到的結果是2號塊組

通過組描述符表中得到第2個塊組的inode節點表起始於16378號塊

從16378號塊讀取inode節點表中查找4724號對應的inode節點(708號表項), 查詢到該xuanku的目錄內容位於17216號塊

從17216塊讀取xuanku目錄項內容, 讀到file.txt的inode節點為4850

然後取消file.txt的目錄項分配, 修改系列xuanku目錄對應的目錄項信息

取消inode節點信息, 修改2號塊組對應的inode節點表信息, 將inode節點位設置為0, 更新塊組描述符和超級塊的空閒inode節點數加1

還要回收文件內容對應的6個塊空間, 將塊位圖表中的bit設置為0, 清除inode節點的塊指針, 更新塊組描述符和超級塊的空閒塊數加1。

感謝各位支持，點擊屏幕右上角的【關注】每天文章不落下。感激不盡！