本文來自微信公眾號：低并發(fā)編程 （ID：dibingfa），原文標(biāo)題：《圖解 | 你管這破玩意叫文件系統(tǒng)？》，作者：閃客
你手里有一塊硬盤，大小為 1T
你還有一堆文件
這些文件在硬盤看來，就是一堆二進(jìn)制數(shù)據(jù)而已
你準(zhǔn)備把這些文件存儲在硬盤上，并在需要的時候讀取出來。
要設(shè)計怎樣的軟件，才能更方便地在硬盤中讀寫這些文件呢？
1
首先我不想和復(fù)雜的扇區(qū)，設(shè)備驅(qū)動等細(xì)節(jié)打交道，因此我先實(shí)現(xiàn)了一個簡單的功能，將硬盤按邏輯分成一個個的塊，并可以以塊為單位進(jìn)行讀寫。
每個塊就定義為兩個物理扇區(qū)的大小，即 1024 字節(jié)，就是 1KB 啦。
硬盤太大不好分析，我們就假設(shè)你的硬盤只有 1MB，那么這塊硬盤則有 1024 個塊。
OK，我們開始存文件啦！
準(zhǔn)備一個文件
隨便選個塊放進(jìn)去，3 號塊吧！
成功！首戰(zhàn)告捷！
2
再存一個文件！
誒？發(fā)現(xiàn)問題了，萬一這個文件也存到了 3 號塊，不是把原來的文件覆蓋了么？不行，得有一個地方記錄，現(xiàn)在可使用的塊有哪些，像這樣。
塊 0：未使用
塊 1：未使用
塊 2：未使用
塊 3：已使用
塊 4：未使用
...
塊 1023：未使用
那我們就用 0 號塊，來記錄所有塊的使用情況吧！怎么記錄呢？
位圖！
那我們給塊 0 起個名字，叫塊位圖，之后這個塊 0 就專門用來記錄所有塊的使用情況，不再用來存具體文件了。
當(dāng)我們再存入一個新文件時，只需要在塊位圖中找到第一個為 0 的位，就可以找到第一個還未被使用的塊，將文件存入。同時，別忘了把塊位圖中的相應(yīng)位置 1。
完美！
3
下面，我們嘗試讀取剛剛的文件。
咦？又遇到問題了，我怎么找到剛剛的文件呢？根據(jù)塊號么？這也太蠢了，就像你去書店找書，店員讓你提供書的編號，而不是書名，顯然不合理。
因此我們給每個文件起一個名字，叫文件名，通過它來尋找這個文件。
那必然就要有一個地方，記錄文件名與塊號的對應(yīng)關(guān)系，像這樣。
葵花寶典.txt：3 號塊
數(shù)學(xué)期末復(fù)習(xí)資料.mp4：5 號塊
低并發(fā)編程的秘密.pdf：10 號塊
...
別急，既然都要選一個地方記錄文件名稱了，不妨多記錄一點(diǎn)我們關(guān)心的信息吧，比如文件大小、文件創(chuàng)建時間、文件權(quán)限等。
這些東西自然也要保存在硬盤上，我們選擇用一個固定大小的空間，來表示這些信息，多大空間呢？128 字節(jié)吧。
為啥是 128 字節(jié)呢？我樂意。
我們將這 128 字節(jié)的結(jié)構(gòu)體，叫做一個 inode。
之后，我們每存入一個新的文件，不但要占用一個塊來存放這個文件本身，還要占用一個 inode 來存放文件的這些元信息，并且這個 inode 的所在塊號這個字段，就指向這個文件所在的塊號。
如果一個 inode 為 128 字節(jié)，那么一個塊就可以容納 8 個 inode，我們可以將這些 inode 編上號。
如果你覺得 inode 數(shù)不夠，也可以用兩個或者多個塊來存放 inode 信息，但這樣用于存放數(shù)據(jù)的塊就少了，這就看你自己的平衡了。
同樣，和塊位圖管理塊的使用情況一樣，我們也需要一個 inode 位圖，來管理 inode 的使用情況。我們就把 inode 位圖，放在 1 號塊吧！
同時，我們把 inode 信息，放在 2 號塊，一共存 8 條 inode，這樣我們的 2 號塊就叫做 inode 表。
現(xiàn)在，我們的文件系統(tǒng)結(jié)構(gòu)，變成了下面這個樣子。
注意：塊位圖是管理可用的塊，每一位代表一個塊的使用與否。inode 位圖管理的是一條一條的 inode，并不是 inode 所占用的塊，比如上圖中有 8 條 inode，則 inode 位圖中就有 8 位是管理他們的使用與否。
4
現(xiàn)在，我們的文件很小，一個塊就能容下。
但如果需要兩個塊、三個塊、四個塊呢？
很簡單，我們只需要采用連續(xù)存儲法，而 inode 則只記錄文件的第一個塊，以及后面還需要多少塊，即可。
這種辦法的缺點(diǎn)就是：容易留下大大小小的空洞，新的文件到來以后，難以找到合適的空白塊，空間會被浪費(fèi)。
看來這種方式不行，那怎么辦呢？
既然在 inode 中記錄了文件所在的塊號，為什么不擴(kuò)展一下，多記錄幾塊呢？
原來在 inode 中只記錄了一個塊號，現(xiàn)在擴(kuò)展一下，記錄 8 個塊號！而且這些塊不需要連續(xù)。
嗯，這是個可行的辦法！
但是這也僅僅能表示 8 個塊，能記錄的最大文件是 8K（記住，一個塊是 1K）, 現(xiàn)在的文件輕松就超過這個限制了，這怎么辦？
很簡單，我們可以讓其中一個塊，作為間接索引。
這樣瞬間就有 263 個塊（多了 256 -1 個塊）可用了，這種索引叫一級間接索引。
如果還嫌不夠，就再弄一個塊做一級間接索引，或者做二級間接索引（二級間接索引則可以多出 256 * 256 - 1 個塊）。
我們的文件系統(tǒng)，暫且先只弄一個一級間接索引。硬盤一共才 1024 個塊，一個文件 263 個塊夠大了。再大了不允許，就這么任性，愛用不用。
好了，現(xiàn)在我們已經(jīng)可以保存很大的文件了，并且可以通過文件名和文件大小，將它們準(zhǔn)確讀取出來啦！
5
但我們得精益求精，我們再想想看這個文件系統(tǒng)有什么毛病。
比如，inode 數(shù)量不夠時，我們是怎么得知的呢？是不是需要在 inode 位圖中找，找不到了才知道不夠用了？
同樣，對于塊數(shù)量不夠時，也是如此。
要是有個全局的地方，來記錄這一切，就好了，也方便隨時調(diào)整，比如這樣
inode 數(shù)量
空閑 inode 數(shù)量
塊數(shù)量
空閑塊數(shù)量
那我們就再占用一個塊來存儲這些數(shù)據(jù)吧！由于他們看起來像是站在上帝視角來描述這個文件系統(tǒng)的，所以我們把它放在最開始的塊上，并把它叫做超級塊，現(xiàn)在的布局如下。
我們繼續(xù)精益求精。
現(xiàn)在，塊位圖、inode 位圖、inode 表，都是是固定地占據(jù)這塊 1、塊 2、塊 3 這三個位置。
假如之后 inode 的數(shù)量很多，使得 inode 表或者 inode 位圖需要占據(jù)多個塊，怎么辦？
或者，塊的數(shù)量增多（硬盤本身大了，或者每個塊變小了），塊位圖需要占據(jù)多個塊，怎么辦？
程序是死的，你不告訴它哪個塊表示什么，它可不會自己猜。
很簡單，與超級塊記錄信息一樣，這些信息也選擇一個塊來記錄，就不怕了。那我們就選擇緊跟在超級塊后面的 1 號塊來記錄這些信息吧，并把它稱之為塊描述符。
當(dāng)然，這些所在塊號只是記錄起始塊號，塊位圖、inode 位圖、inode 表分別都可以占用多個塊。
好了，大功告成！
6
現(xiàn)在，我們再嘗試存入一批文件。
葵花寶典.txt
數(shù)學(xué)期末復(fù)習(xí)資料.mp4
贅婿 1.mp4
贅婿 2.mp4
贅婿 3.mp4
贅婿 4.mp4
低并發(fā)編程的秘密.pdf
誒？這看著好不爽，所有的文件都是平鋪開的，能不能擁有層級關(guān)系呢？比如這樣
葵花寶典.txt
數(shù)學(xué)期末復(fù)習(xí)資料.mp4
贅婿
贅婿 1.mp4
贅婿 2.mp4
贅婿 3.mp4
贅婿 4.mp4
低并發(fā)編程的秘密.pdf
我們將葵花寶典.txt 這種稱為普通文件，將贅婿這種稱為目錄文件，如果要訪問贅婿 1.mp4，那全文件名要寫成
贅婿 / 贅婿 1.mp4。
如何做到這一點(diǎn)呢？那我們又得把 inode 結(jié)構(gòu)拿出來說事了。
此時需要一個屬性來區(qū)分這個文件是普通文件，還是目錄文件。
缺什么就補(bǔ)什么嘛，我們已經(jīng)很熟悉了，專門加一個 4 字節(jié)，來表示文件類型。
如果是普通文件，則這個 inode 所指向的數(shù)據(jù)塊仍然和之前一樣，就是文件本身原封不動的內(nèi)容。
但如果是目錄文件，則這個 inode 所指向的數(shù)據(jù)塊，就需要重新規(guī)劃了。
這個數(shù)據(jù)塊里應(yīng)該是什么樣子呢？可以是一個一個指向不同 inode 的緊挨著的結(jié)構(gòu)體，比如這樣。
這樣先通過 贅婿 這個目錄文件，找到所在的數(shù)據(jù)塊。再根據(jù)這個數(shù)據(jù)塊里的一個個帶有 inode 信息的結(jié)構(gòu)體，找到這個目錄下的所有文件。
完美！
7
不過這樣的話，你想想看，如果想要查看一下贅婿這個目錄下的所有文件（比如 ll 命令），將文件名和文件類型都展示出來，怎么辦呢？
就需要把一個個結(jié)構(gòu)體指向的 inode 從 inode 表中取出，再把文件名和文件類型取出，這很是浪費(fèi)時間。
而讓用戶看到一個目錄下的所有文件，又是一個極其常見的操作。
所以，不如把文件名和文件類型這種常見的信息，放在數(shù)據(jù)塊中的結(jié)構(gòu)體里吧。
同時，inode 結(jié)構(gòu)中的文件名，好像就沒啥用了，這種變長的東西放在這種定長的結(jié)構(gòu)中本身就很討厭，早就想給它去掉了。而且還能給其他信息省下空間，比如文件所在塊的數(shù)組，就能再多幾個了。
太好了，去掉它！
OK，大功告成，現(xiàn)在我們就可以給文件分門別類放進(jìn)不同目錄下了，還可以在目錄下創(chuàng)建目錄，無限套娃！
8
現(xiàn)在的文件系統(tǒng)，已經(jīng)比較完善了，只是還有一點(diǎn)不太爽。
我們訪問到一個目錄下，可以很舒服地看到目錄里的文件，然后再根據(jù)名稱訪問這個目錄下的文件或者目錄，整個過程都是一個套路。
但是，最上層的目錄下的所有文件，即根目錄，現(xiàn)在仍然需要通過遍歷所有的 inode 來獲得，能不能和上面的套路統(tǒng)一呢？
答案非常簡單，我們規(guī)定，inode 表中的 0 號 inode，就表示根目錄，一切的訪問，就從這個根目錄開始！
好了，這回沒有然后了！
我們最后來欣賞下我們的文件系統(tǒng)架構(gòu)。
你是不是覺得這沒啥了不起的。
但這個破玩意，它就叫文件系統(tǒng)
后記
這個文件系統(tǒng)，和 linux 上的經(jīng)典文件系統(tǒng) ext2 基本相同。
下面是我畫的 ext2 文件系統(tǒng)的結(jié)構(gòu)（字段部分只畫了核心字段）
估計你是看不清了，我說下主要異同點(diǎn)：
1. 超級塊前面是啟動塊，這個是 PC 聯(lián)盟給硬盤規(guī)定的 1KB 專屬空間，任何文件系統(tǒng)都不能用它。
2. ext2 文件系統(tǒng)首先將整個硬盤分為很多塊組，但如果只有一個塊組的話，和我們的文件系統(tǒng)整體結(jié)構(gòu)就完全一樣了，分別是超級塊、塊描述符、塊位圖、inode 位圖、inode 表、數(shù)據(jù)塊。
3. ext2 文件系統(tǒng)的 inode 表中用 15 個塊來定位文件，其中第 13 個塊為一級間接索引、14 個為二級間接索引、15 個為三級間接索引。
4. ext2 文件系統(tǒng)的文件類型分得更多，還有常見的如塊設(shè)備文件、字符設(shè)備文件、管道文件、socket 文件等。
5. ext2 文件系統(tǒng)的超級塊、塊描述符、inode 表中記錄的信息更多，但核心的和我們的文件系統(tǒng)一樣，而且這些字段在后續(xù)的 ext3 和 ext4 中不斷增加，保持向前兼容。
6. ext2 文件系統(tǒng)的 2 號 inode 為根目錄，而我們的系統(tǒng)是 0 號 inode 為根目錄，這個很隨意，你設(shè)計一個文件系統(tǒng)定一個 187 號 inode 為根目錄也沒人攔著你。
如果你想了解 ext2 文件系統(tǒng)的全部細(xì)節(jié)，有三種方式。
1. 看源碼，linux1.0 后的源碼都有 ext2 文件系統(tǒng)的實(shí)現(xiàn)，源碼是最準(zhǔn)確的。
2. 看官方文檔，這里有個 pdf 連接。
https://www.nongnu.org/ext2-doc/ext2.pdf
3. 看優(yōu)質(zhì)博客，這里我推薦一個。
http://docs.linuxtone.org/ebooks/C&CPP/c/ch29s02.html
4. 用 linux 的 mke2fs 命令生成一個 ext2 文件系統(tǒng)的磁盤鏡像，然后一個字節(jié)一個字節(jié)分析其格式，可以在公眾號 低并發(fā)編程 回復(fù) ext2 獲得我的鏡像分析文件。
如果看源碼和官方文檔毫不吃力，我當(dāng)然主推這兩個，因?yàn)楫吘故且皇仲Y料。
但大多數(shù)人可能無法做到，有時也沒大必要，因此也可以看一些優(yōu)質(zhì)的博客。
介紹思想的，我覺得我這一篇就算是很優(yōu)質(zhì)的一篇了，它會帶你從設(shè)計者角度了解為什么這樣來設(shè)計文件系統(tǒng)。
介紹細(xì)節(jié)的，那些連文件系統(tǒng)的格式和字段都寫不對的，就別看了，所以我這里良心推薦一篇，就是上面的方式三，可以放心大膽，逐字逐句地食用。
本文來自微信公眾號：低并發(fā)編程 （ID：dibingfa），作者：閃客
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。