文件系統(tǒng)磁盤分配
在存儲(chǔ)知識(shí)棧上提到文件系統(tǒng), 大家首先就關(guān)心他是如何管理好硬件層提供的磁盤空間的。
本文開篇就先描述典型的幾種文件系統(tǒng)管理磁盤的技術(shù)方案: 連續(xù)分配, 鏈?zhǔn)椒峙?span lang="EN-US">, 索引分配。
連續(xù)分配
顧名思義, 就是創(chuàng)建文件的時(shí)候, 給分配一組連續(xù)的塊。在單獨(dú)拿出一塊地方存儲(chǔ)各個(gè)文件的meta信息, meta信息也很簡(jiǎn)單, 包含文件名, 起始位置和長(zhǎng)度即可, 這個(gè)存放meta信息的地方也叫做FAT(文檔分配表)。
如下圖:
該方案的優(yōu)點(diǎn):
1. 簡(jiǎn)便, 適用于一次性寫入操作;
2. 所需磁盤尋道次數(shù)和尋道時(shí)間最少;
缺點(diǎn)也很明顯:
1. 文件不能動(dòng)態(tài)增長(zhǎng), 因?yàn)楹竺娴膲K可能已經(jīng)分配給別人了;
2. 不利于文件的插入和刪除, 插入文件之前需要聲明文件大小;
3. 外部碎片問(wèn)題;
為了克服連續(xù)分配的問(wèn)題, 又進(jìn)化出來(lái)了鏈?zhǔn)椒峙浞桨浮?span lang="EN-US">
鏈?zhǔn)椒峙?/span>
鏈?zhǔn)椒峙浼磳⑽募K像鏈表一樣管理起來(lái), 每個(gè)塊中放一個(gè)指針, 指針指向下一個(gè)文件塊所在的位置。這樣在FAT中存儲(chǔ)也很簡(jiǎn)單, 只需要存儲(chǔ)文件名, 起始?jí)K號(hào)和結(jié)束塊號(hào)(都可以不存)。
如下圖:
該方案的優(yōu)點(diǎn):
1. 提高磁盤利用率, 沒(méi)有碎片問(wèn)題
2. 有利于文件的插入, 刪除
缺點(diǎn):
1. 存取速度慢, 需要移動(dòng)的磁道次數(shù)多, 尋道時(shí)間長(zhǎng);
2. 讀寫任何一個(gè)地方都需要沿著指針前進(jìn)直到找到對(duì)應(yīng)塊為止;
3. 鏈接占據(jù)了一定的磁盤空間, 數(shù)據(jù)不是嚴(yán)格按照塊大小分配;
索引分配
這是一個(gè)折衷方案, 也是現(xiàn)在大部分文件系統(tǒng)采用的方案, 他綜合了連續(xù)分配和鏈?zhǔn)椒峙涞暮锰帯?/span>
該方案會(huì)在FAT中保存所有文件塊的位置, 各文件系統(tǒng)都有一套自己對(duì)應(yīng)的細(xì)節(jié)分配策略, 會(huì)保證一個(gè)文件盡量連續(xù)的同時(shí), 又避免出現(xiàn)大量的磁盤碎片。
如下圖:
該方案的優(yōu)點(diǎn)是:
1. 能夠保持好大部分文件的局部性
2. 滿足文件插入, 刪除的高效
3. 隨機(jī)讀寫不需要沿著指針前進(jìn)
缺點(diǎn):
1. 會(huì)有較多的磁盤尋道次數(shù)
2. 索引表本身管理復(fù)雜, 也會(huì)帶來(lái)額外的系統(tǒng)開銷
ext文件系統(tǒng)
基本概念
1. 塊. 即Block, 數(shù)據(jù)存儲(chǔ)的最小單元, 每個(gè)塊都有一個(gè)唯一的地址, 從0開始, 起源于第一個(gè)可以用來(lái)存儲(chǔ)數(shù)據(jù)的扇區(qū);
2. 超級(jí)塊. 超級(jí)塊保存了各種文件系統(tǒng)的meta信息, 比如塊大小信息。他位于文件系統(tǒng)的2號(hào)和3號(hào)扇區(qū)(物理地址), 占用兩個(gè)扇區(qū)大小;
3. 塊組. 所有的塊會(huì)劃分成多個(gè)塊組, 每個(gè)塊組包含同樣多個(gè)塊, 但是可能整個(gè)文件系統(tǒng)整個(gè)塊數(shù)不是塊組的整數(shù)倍, 所以最后一個(gè)塊組包含的個(gè)數(shù)可能會(huì)小于其他塊;
總體結(jié)構(gòu)
一個(gè)ext文件系統(tǒng)分成多個(gè)塊組, 每個(gè)塊組的結(jié)構(gòu)基本相同, 如下:
解釋如下:
1. 0~1號(hào)扇區(qū): 引導(dǎo)扇區(qū). 如果沒(méi)有引導(dǎo)代碼, 則這兩個(gè)扇區(qū)為空, 全部用0填充;
2. 2~3號(hào)扇區(qū): 超級(jí)塊, 超級(jí)塊包含各種meta信息:
3. 塊大小, 每個(gè)塊組包含塊數(shù), 總塊數(shù), 第一個(gè)塊前保留塊數(shù), inode節(jié)點(diǎn)數(shù), 每個(gè)塊組的inode節(jié)點(diǎn)數(shù)
4. 卷名, 最后掛載時(shí)間, 掛載路徑, 文件系統(tǒng)是否干凈, 是否要調(diào)用一致性檢查標(biāo)識(shí)
5. 空間inode節(jié)點(diǎn)和空閑塊的記錄信息, 在分配inode節(jié)點(diǎn)和新塊的時(shí)候使用
6. 組描述符表:
7. 位于超級(jí)塊后面的一個(gè)塊, 注意在超級(jí)塊之前只占用了4個(gè)扇區(qū), 如果一個(gè)塊大小超過(guò)4個(gè)扇區(qū)的話, 這里就會(huì)有空的扇區(qū)。
8. 組描述符表中包含了所有塊組的描述信息, 每個(gè)塊組占據(jù)32個(gè)字節(jié)(差不多是8個(gè)整數(shù)的大小)。如果格式化使用默認(rèn)參數(shù), 那么組描述符表不會(huì)超過(guò)一塊塊組。
9. 組描述符和超級(jí)塊在每個(gè)塊組中都有一個(gè)備份, 但是激活了稀疏超級(jí)塊特征的情況除外。
10. 稀疏超級(jí)塊即不是在所有塊組中都存儲(chǔ)超級(jí)塊和組描述符的備份, 默認(rèn)該策略被激活, 其策略類似當(dāng)塊組號(hào)是3,5,7的冪的塊組才存副本。
11. 塊位圖表
12. 每個(gè)塊對(duì)應(yīng)一個(gè)bit, 只包含了本塊組的信息。而文件系統(tǒng)創(chuàng)建的時(shí)候, 默認(rèn)每個(gè)塊組包含的塊數(shù)跟每個(gè)塊包含的bit數(shù)是一樣的, 這種情況下每個(gè)塊位圖表正好等于一個(gè)塊的大小。
13. 而該位圖表的塊的起始位置會(huì)在組描述符表中指定, 大小則為塊組中包含塊數(shù)個(gè)bit。
14. inode位圖塊
15. 跟塊位圖表類似, 通常情況他也只占用一個(gè)塊。通常一個(gè)塊組中的inode節(jié)點(diǎn)數(shù)會(huì)小于block數(shù)量, 所以其不會(huì)超過(guò)一個(gè)塊大小。
16. inode節(jié)點(diǎn)表
17. 每個(gè)inode都占用128位的一個(gè)描述信息, 起始位置在組描述符中表示, 大小為inode節(jié)點(diǎn)數(shù)*128。
18. 數(shù)據(jù)區(qū)
19. 這就是真正存儲(chǔ)數(shù)據(jù)的區(qū)域。
塊大小為4096的時(shí)候, 各部分和扇區(qū)對(duì)應(yīng)關(guān)系如下圖:
塊大小為2048的時(shí)候, 各部分和扇區(qū)對(duì)應(yīng)關(guān)系如下圖:
超級(jí)塊詳細(xì)信息
超級(jí)塊總是位于文件系統(tǒng)的第1024~2048字節(jié)處。
超級(jí)塊中包含的信息如下:
偏移(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號(hào)塊組起始?jí)K號(hào)18~1B4塊大小(1024左移位數(shù))1C~1F4片段大小, 跟塊大小一模一樣20~234每個(gè)塊組中包含的塊數(shù)量24~274每個(gè)塊組中包含的片段數(shù)量, 跟包含的快數(shù)量一致28~2B4每個(gè)塊組中包含的inode節(jié)點(diǎn)數(shù)量2C~2F4文件系統(tǒng)最后掛載時(shí)間30~334文件系統(tǒng)最后寫入時(shí)間34~352當(dāng)前掛載數(shù)36~372最大掛載數(shù)38~392文件系統(tǒng)簽名標(biāo)識(shí) 53EF3A~3B2文件系統(tǒng)狀態(tài), 正常, 錯(cuò)誤, 恢復(fù)了孤立的inode節(jié)點(diǎn)3C~3D2錯(cuò)誤處理方式, 繼續(xù), 以只讀方式掛載3E~3F2輔版本號(hào)40~434最后進(jìn)行一致性檢查的時(shí)間44~474一致性檢查的間隔時(shí)間48~4B4創(chuàng)建本文件系統(tǒng)的操作系統(tǒng)4C~4F4主版本號(hào), 只有該值為1的時(shí)候, 偏移54之后的擴(kuò)展超級(jí)塊的一些動(dòng)態(tài)屬性值才是有意義的50~512默認(rèn)為UID的保留塊52~532默認(rèn)為GID的保留塊54~572第一個(gè)非保留的inode節(jié)點(diǎn)號(hào), 即用戶可以使用的第一個(gè)inode節(jié)點(diǎn)號(hào)58~592每個(gè)inode節(jié)點(diǎn)的大小字節(jié)數(shù)5A~5B2本超級(jí)塊所在的塊組號(hào)5C~5F4兼容標(biāo)識(shí)特征60~634非兼容標(biāo)識(shí)特征64~674只讀兼容特征標(biāo)識(shí)68~7716文件系統(tǒng)ID號(hào)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ì)信息
每個(gè)塊組描述符占用32個(gè)字節(jié), 其數(shù)據(jù)結(jié)構(gòu)如下:
偏移(16進(jìn)制)字節(jié)數(shù)含義&解釋00~034塊位圖起始地址(塊號(hào))04~074inode節(jié)點(diǎn)位圖起始地址(塊號(hào))08~0B4inode節(jié)點(diǎn)表起始地址(塊號(hào))0C~0D2塊組中空閑塊數(shù)0E~0F2塊組中空閑inode節(jié)點(diǎn)數(shù)10~112塊組中的目錄數(shù)12~1F-未使用
inode信息
每個(gè)inode會(huì)被分配給一個(gè)目錄或者一個(gè)文件, 每個(gè)inode包含了128個(gè)字節(jié), 里面包含了這個(gè)文件的各種meta信息。
在所有inode中, 1~10號(hào)會(huì)用作保留給內(nèi)核使用, 在這些保留節(jié)點(diǎn)中, 2號(hào)節(jié)點(diǎn)用于存儲(chǔ)根目錄信息, 1號(hào)表示壞塊, 8號(hào)表示日志文件信息。
第一個(gè)用戶可見(jiàn)的都是從11號(hào)inode開始, 11號(hào)節(jié)點(diǎn)一般用作lost+found目錄, 當(dāng)檢查程序發(fā)現(xiàn)一個(gè)inode節(jié)點(diǎn)已經(jīng)被分配, 但是沒(méi)有文件名指向他的時(shí)候, 就會(huì)把他添加到lost+found目錄中并賦予一個(gè)新的文件名。
inode通過(guò)三級(jí)指針的方式來(lái)找到文件數(shù)據(jù)最終存儲(chǔ)的數(shù)據(jù)塊, 見(jiàn)下圖:
這種方式能保證小文件的讀取效率的同時(shí), 也支持大文件的讀取。
目錄項(xiàng)
在ext文件系統(tǒng)中, 每個(gè)目錄也對(duì)應(yīng)一個(gè)inode節(jié)點(diǎn), 該inode節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)塊里面會(huì)存儲(chǔ)該目錄下所有文件/目錄的信息。
每個(gè)文件/目錄對(duì)應(yīng)的信息就叫目錄項(xiàng), 目錄項(xiàng)包含的內(nèi)容也很簡(jiǎn)單, 主要就是文件名和指向該文件名的inode指針, 詳細(xì)信息如下:
偏移(16進(jìn)制)字節(jié)數(shù)含義&解釋00~034inode節(jié)點(diǎn)號(hào)04~052本目錄項(xiàng)的長(zhǎng)度字節(jié)數(shù)06~061名字長(zhǎng)度字節(jié)數(shù)07~071文件類型08~不定長(zhǎng)度名字的ascii碼
當(dāng)文件刪除的時(shí)候, 不會(huì)真正刪除文件, 會(huì)將該文件所屬目錄對(duì)應(yīng)的目錄項(xiàng)給刪除, 同時(shí)將對(duì)應(yīng)數(shù)據(jù)塊在快位圖表中標(biāo)記為0。
鏈接
1. 硬鏈接是指在另外一個(gè)目錄對(duì)應(yīng)的目錄項(xiàng)中增加一個(gè)目錄項(xiàng)。硬鏈接建立之后, 用戶無(wú)法通過(guò)文件名來(lái)判斷到底哪個(gè)是原文件名, 哪個(gè)是鏈接名;
2. 軟連接是一種文件類型, 該文件里面就存儲(chǔ)源文件的完整路徑, 如果源文件完整路徑長(zhǎng)度小于60個(gè)字節(jié), 那么就將該值直接存儲(chǔ)在inode節(jié)點(diǎn)表中, 避免浪費(fèi)數(shù)據(jù)塊;
分配策略
1. 首先判斷應(yīng)該在哪個(gè)塊組中分配
2. 如果是為文件創(chuàng)建節(jié)點(diǎn)
3. 默認(rèn)會(huì)在其父目錄所在的組中為其創(chuàng)建節(jié)點(diǎn), 這樣可以確保一個(gè)目錄中所有文件都位于一個(gè)大致的區(qū)域中
4. 如果父目錄所在組沒(méi)有空閑的節(jié)點(diǎn)或者空閑的塊了, 就到別的塊組中為該文件分配節(jié)點(diǎn), 找尋別的塊組的算法如下
5. 每次講當(dāng)前組號(hào)加上2^N次方再求hash
6. 如果上面的算法沒(méi)找到, 就線性查找
7. 如果是為目錄創(chuàng)建節(jié)點(diǎn)
8. 會(huì)將其分配到可用空間較多的塊組中, 分配算法如下:
9. 首先利用超級(jí)塊中的剩余inode和剩余塊數(shù)字算出每個(gè)塊組的平均剩余數(shù)字, 然后依次找到一個(gè)大于平均值的塊組
10. 如果沒(méi)找到, 就利用塊組描述符表中的信息, 找到一個(gè)最空閑的塊組
11. 當(dāng)一個(gè)數(shù)據(jù)塊分配給某文件之后
12. 該塊原來(lái)的內(nèi)容會(huì)被請(qǐng)出, inode節(jié)點(diǎn)對(duì)應(yīng)的各種元信息會(huì)跟著做修改
13. 如果是文件, 節(jié)點(diǎn)對(duì)應(yīng)鏈接數(shù)會(huì)設(shè)置為1, 如果是目錄, 鏈接數(shù)會(huì)被設(shè)置為2
實(shí)際創(chuàng)建/刪除文件過(guò)程
我們創(chuàng)建一個(gè)/xuanku/file.txt, 該文件大小為10000字節(jié), 文件塊大小為4096, 那么下面來(lái)看一下過(guò)程:
1. 讀取文件系統(tǒng)的1024字節(jié)~2048字節(jié), 即超級(jí)塊信息。通過(guò)超級(jí)塊得到快大小為4096, 每個(gè)塊組含有8192個(gè)塊以及2008個(gè)inode節(jié)點(diǎn)
2. 讀取文件系統(tǒng)中第1個(gè)塊(即組描述符表), 得到所有塊組布局信息
3. 訪問(wèn)2號(hào)inode節(jié)點(diǎn)(即根節(jié)點(diǎn)), 通過(guò)讀取根節(jié)點(diǎn)數(shù)據(jù)塊信息, 假設(shè)讀到其位于5號(hào)塊
4. 在第5號(hào)塊所有目錄項(xiàng)中從前往后遍歷, 直到找到文件名為xuanku的目錄項(xiàng), 讀到該inode節(jié)點(diǎn)為4724
5. 每個(gè)塊組有2008個(gè)inode, 用4724針對(duì)2008取模, 得到的結(jié)果是2號(hào)塊組
6. 通過(guò)組描述符表中得到第2個(gè)塊組的inode節(jié)點(diǎn)表起始于16378號(hào)塊
7. 從16378號(hào)塊讀取inode節(jié)點(diǎn)表中查找4724號(hào)對(duì)應(yīng)的inode節(jié)點(diǎn)(708號(hào)表項(xiàng)), 查詢到該xuanku的目錄內(nèi)容位于17216號(hào)塊
8. 從17216塊讀取xuanku目錄項(xiàng)內(nèi)容, 將file.txt相關(guān)信息更新到該塊的目錄項(xiàng)當(dāng)中
9. 然后開始為文件分配inode節(jié)點(diǎn), 默認(rèn)會(huì)放到父目錄所在塊組, 即2號(hào)塊組, 再次2號(hào)塊組的inode節(jié)點(diǎn)表16378, 開始從4724往后找到第一個(gè)可用的inode節(jié)點(diǎn)分配給該文件, 假設(shè)找到的是4850號(hào)inode。
10. 然后就給4850號(hào)的inode位圖表設(shè)置為1, 組描述符的空閑inode節(jié)點(diǎn)數(shù)和超級(jí)塊的總空閑inode節(jié)點(diǎn)數(shù)都減1, 將inode節(jié)點(diǎn)的地址寫入file.txt對(duì)應(yīng)的目錄項(xiàng)當(dāng)中, 然后寫各種時(shí)間, 記錄日志
11. file.txt需要3個(gè)塊的存儲(chǔ)空間, 通過(guò)2號(hào)塊組描述符找到塊位圖對(duì)應(yīng)的塊, 并從前往后找到可用的塊。然后將對(duì)應(yīng)的位設(shè)置為1, 并更新到inode節(jié)點(diǎn)當(dāng)中
12. 然后將文件的內(nèi)容寫入到對(duì)應(yīng)的塊中
下面再演示一下將該文件刪除的過(guò)程:
讀取文件系統(tǒng)的1024字節(jié)~2048字節(jié), 即超級(jí)塊信息。通過(guò)超級(jí)塊得到快大小為4096, 每個(gè)塊組含有8192個(gè)塊以及2008個(gè)inode節(jié)點(diǎn)
讀取文件系統(tǒng)中第1個(gè)塊(即組描述符表), 得到所有塊組布局信息
訪問(wèn)2號(hào)inode節(jié)點(diǎn)(即根節(jié)點(diǎn)), 通過(guò)讀取根節(jié)點(diǎn)數(shù)據(jù)塊信息, 假設(shè)讀到其位于5號(hào)塊
在第5號(hào)塊所有目錄項(xiàng)中從前往后遍歷, 直到找到文件名為xuanku的目錄項(xiàng), 讀到該inode節(jié)點(diǎn)為4724
每個(gè)塊組有2008個(gè)inode, 用4724針對(duì)2008取模, 得到的結(jié)果是2號(hào)塊組
通過(guò)組描述符表中得到第2個(gè)塊組的inode節(jié)點(diǎn)表起始于16378號(hào)塊
從16378號(hào)塊讀取inode節(jié)點(diǎn)表中查找4724號(hào)對(duì)應(yīng)的inode節(jié)點(diǎn)(708號(hào)表項(xiàng)), 查詢到該xuanku的目錄內(nèi)容位于17216號(hào)塊
從17216塊讀取xuanku目錄項(xiàng)內(nèi)容, 讀到file.txt的inode節(jié)點(diǎn)為4850
然后取消file.txt的目錄項(xiàng)分配, 修改系列xuanku目錄對(duì)應(yīng)的目錄項(xiàng)信息
取消inode節(jié)點(diǎn)信息, 修改2號(hào)塊組對(duì)應(yīng)的inode節(jié)點(diǎn)表信息, 將inode節(jié)點(diǎn)位設(shè)置為0, 更新塊組描述符和超級(jí)塊的空閑inode節(jié)點(diǎn)數(shù)加1
還要回收文件內(nèi)容對(duì)應(yīng)的6個(gè)塊空間, 將塊位圖表中的bit設(shè)置為0, 清除inode節(jié)點(diǎn)的塊指針, 更新塊組描述符和超級(jí)塊的空閑塊數(shù)加1。
