文件系統(tǒng)磁盤分配

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

本文開篇就先描述典型的幾種文件系統(tǒng)管理磁盤的技術(shù)方案: 連續(xù)分配, 鏈?zhǔn)椒峙? 索引分配。

連續(xù)分配

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

如下圖:

該方案的優(yōu)點(diǎn):

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

缺點(diǎn)也很明顯:

1. 文件不能動態(tài)增長, 因?yàn)楹竺娴膲K可能已經(jīng)分配給別人了;
2. 不利于文件的插入和刪除, 插入文件之前需要聲明文件大小;
3. 外部碎片問題;

為了克服連續(xù)分配的問題, 又進(jìn)化出來了鏈?zhǔn)椒峙浞桨浮?/p>

鏈?zhǔn)椒峙?/strong>

鏈?zhǔn)椒峙浼磳⑽募K像鏈表一樣管理起來, 每個塊中放一個指針, 指針指向下一個文件塊所在的位置。這樣在FAT中存儲也很簡單, 只需要存儲文件名, 起始塊號和結(jié)束塊號(都可以不存)。

如下圖:

該方案的優(yōu)點(diǎn):

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

缺點(diǎn):

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

索引分配

這是一個折衷方案, 也是現(xiàn)在大部分文件系統(tǒng)采用的方案, 他綜合了連續(xù)分配和鏈?zhǔn)椒峙涞暮锰帯?/p>

該方案會在FAT中保存所有文件塊的位置, 各文件系統(tǒng)都有一套自己對應(yīng)的細(xì)節(jié)分配策略, 會保證一個文件盡量連續(xù)的同時, 又避免出現(xiàn)大量的磁盤碎片。

如下圖:

該方案的優(yōu)點(diǎn)是:

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

缺點(diǎn):

1. 會有較多的磁盤尋道次數(shù)
2. 索引表本身管理復(fù)雜, 也會帶來額外的系統(tǒng)開銷

ext文件系統(tǒng)

基本概念

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

總體結(jié)構(gòu)

一個ext文件系統(tǒng)分成多個塊組, 每個塊組的結(jié)構(gòu)基本相同, 如下:

解釋如下:

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

塊大小為4096的時候, 各部分和扇區(qū)對應(yīng)關(guān)系如下圖:

塊大小為2048的時候, 各部分和扇區(qū)對應(yīng)關(guān)系如下圖:

超級塊詳細(xì)信息

超級塊總是位于文件系統(tǒng)的第1024~2048字節(jié)處。

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

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

塊組描述符詳細(xì)信息

每個塊組描述符占用32個字節(jié), 其數(shù)據(jù)結(jié)構(gòu)如下:

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

inode信息

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

在所有inode中, 1~10號會用作保留給內(nèi)核使用, 在這些保留節(jié)點(diǎn)中, 2號節(jié)點(diǎn)用于存儲根目錄信息, 1號表示壞塊, 8號表示日志文件信息。

第一個用戶可見的都是從11號inode開始, 11號節(jié)點(diǎn)一般用作lost+found目錄, 當(dāng)檢查程序發(fā)現(xiàn)一個inode節(jié)點(diǎn)已經(jīng)被分配, 但是沒有文件名指向他的時候, 就會把他添加到lost+found目錄中并賦予一個新的文件名。

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

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

目錄項(xiàng)

在ext文件系統(tǒng)中, 每個目錄也對應(yīng)一個inode節(jié)點(diǎn), 該inode節(jié)點(diǎn)對應(yīng)的數(shù)據(jù)塊里面會存儲該目錄下所有文件/目錄的信息。

每個文件/目錄對應(yīng)的信息就叫目錄項(xiàng), 目錄項(xiàng)包含的內(nèi)容也很簡單, 主要就是文件名和指向該文件名的inode指針, 詳細(xì)信息如下:

偏移(16進(jìn)制)字節(jié)數(shù)含義&解釋00~034inode節(jié)點(diǎn)號04~052本目錄項(xiàng)的長度字節(jié)數(shù)06~061名字長度字節(jié)數(shù)07~071文件類型08~不定長度名字的ascii碼

當(dāng)文件刪除的時候, 不會真正刪除文件, 會將該文件所屬目錄對應(yīng)的目錄項(xiàng)給刪除, 同時將對應(yīng)數(shù)據(jù)塊在快位圖表中標(biāo)記為0。

鏈接

1. 硬鏈接是指在另外一個目錄對應(yīng)的目錄項(xiàng)中增加一個目錄項(xiàng)。硬鏈接建立之后, 用戶無法通過文件名來判斷到底哪個是原文件名, 哪個是鏈接名;
2. 軟連接是一種文件類型, 該文件里面就存儲源文件的完整路徑, 如果源文件完整路徑長度小于60個字節(jié), 那么就將該值直接存儲在inode節(jié)點(diǎn)表中, 避免浪費(fèi)數(shù)據(jù)塊;

分配策略

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

實(shí)際創(chuàng)建/刪除文件過程

我們創(chuàng)建一個/xuanku/file.txt, 該文件大小為10000字節(jié), 文件塊大小為4096, 那么下面來看一下過程:

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

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

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

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

訪問2號inode節(jié)點(diǎn)(即根節(jié)點(diǎn)), 通過讀取根節(jié)點(diǎn)數(shù)據(jù)塊信息, 假設(shè)讀到其位于5號塊

在第5號塊所有目錄項(xiàng)中從前往后遍歷, 直到找到文件名為xuanku的目錄項(xiàng), 讀到該inode節(jié)點(diǎn)為4724

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

通過組描述符表中得到第2個塊組的inode節(jié)點(diǎn)表起始于16378號塊

從16378號塊讀取inode節(jié)點(diǎn)表中查找4724號對應(yīng)的inode節(jié)點(diǎn)(708號表項(xiàng)), 查詢到該xuanku的目錄內(nèi)容位于17216號塊

從17216塊讀取xuanku目錄項(xiàng)內(nèi)容, 讀到file.txt的inode節(jié)點(diǎn)為4850

然后取消file.txt的目錄項(xiàng)分配, 修改系列xuanku目錄對應(yīng)的目錄項(xiàng)信息

取消inode節(jié)點(diǎn)信息, 修改2號塊組對應(yīng)的inode節(jié)點(diǎn)表信息, 將inode節(jié)點(diǎn)位設(shè)置為0, 更新塊組描述符和超級塊的空閑inode節(jié)點(diǎn)數(shù)加1

還要回收文件內(nèi)容對應(yīng)的6個塊空間, 將塊位圖表中的bit設(shè)置為0, 清除inode節(jié)點(diǎn)的塊指針, 更新塊組描述符和超級塊的空閑塊數(shù)加1。

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