文件系統(tǒng)基本都是構(gòu)建于塊存儲(chǔ)之上的。但當(dāng)然，現(xiàn)在的一些分布式文件系統(tǒng)，如 JuiceFS[2]，底層是基于對(duì)象存儲(chǔ)的。但無論塊存儲(chǔ)還是對(duì)象存儲(chǔ)，其本質(zhì)都是按 “數(shù)據(jù)塊” 進(jìn)行尋址和數(shù)據(jù)交換的。

我們首先會(huì)探討一個(gè)完整的文件系統(tǒng)在硬盤上的數(shù)據(jù)結(jié)構(gòu)，也即布局；然后再通過打開關(guān)閉、讀寫流程將各個(gè)子模塊串起來，從而完成對(duì)一個(gè)文件系統(tǒng)要點(diǎn)的覆蓋。

總體布局

假設(shè)我們的塊大小是 4KB，然后有一塊非常小的硬盤，只有 64 個(gè)塊（則總大小為 64 * 4KB = 256KB），且該硬盤只給文件系統(tǒng)用。由于硬盤是按塊進(jìn)行尋址的，則地址空間為 0~63 。

就這么點(diǎn)空間的迷你硬盤

基于此迷你硬盤，我們一起來逐步推導(dǎo)下這個(gè)極簡(jiǎn)文件系統(tǒng)。

文件系統(tǒng)的首要目的肯定是存儲(chǔ)用戶數(shù)據(jù)，為此我們?cè)诖疟P留出一塊數(shù)據(jù)區(qū)（Data Region）。假設(shè)我們使用后面 56 個(gè)塊作為數(shù)據(jù)區(qū)。為什么是 56 個(gè)呢？從后面就可以知道，其實(shí)是可以算出來的——我們可以大致算出元信息和真正數(shù)據(jù)的比例，進(jìn)而可以確定兩部分大小。

隔出來數(shù)據(jù)區(qū)

接下來，我們需要為系統(tǒng)中的每個(gè)文件保存一些元信息，比如：

1. 文件名
2. 文件大小
3. 文件歸屬者
4. 訪問權(quán)限
5. 創(chuàng)建、修改時(shí)間

等等。保存這些元信息的數(shù)據(jù)塊，我們通常稱為 inode （index node）。如下，我們給 inode 分配 5 個(gè) block。

隔出來索引區(qū)

元信息所占空間相對(duì)較小，比如 128B 或者 256B，我們這里假設(shè)每個(gè) inode 占用 256B。則每個(gè) 4KB 塊能容納 16 個(gè) inode，則我們的文件系統(tǒng)最多可以支持 5 * 16 = 80 個(gè) inode，也即我們的迷你文件系統(tǒng)最多可以支持 80 個(gè)文件，但由于目錄也要占 inode，所以實(shí)際可用文件數(shù)要少于 80。

現(xiàn)在我們有了數(shù)據(jù)區(qū)，有了文件元信息區(qū)，但在一個(gè)正常使用的文件系統(tǒng)中，還需要追蹤哪些數(shù)據(jù)塊被用了，哪些還沒有被使用。這種數(shù)據(jù)結(jié)構(gòu)我們稱之為分配結(jié)構(gòu)（allocation structures）。業(yè)界常用的方法有空閑鏈表（free list），即把所有空閑塊按鏈表的方式串起來。但為了簡(jiǎn)單，這里使用一種更簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：位圖（bitmap），數(shù)據(jù)區(qū)用一個(gè)，稱數(shù)據(jù)位圖（data bitmap）；inode 表用一個(gè)，稱 inode 位圖（inode bitmap）。

位圖的思想很簡(jiǎn)單，即為每一個(gè) inode 或者數(shù)據(jù)塊使用一個(gè)數(shù)據(jù)位，來標(biāo)記是否空閑：0 表示空閑，1 表示有數(shù)據(jù)。一個(gè) 4KB 的 bitmap 最多能追蹤 32K 的對(duì)象。為了方便，我們給 inode 表和數(shù)據(jù)池各分配一個(gè)完整的塊（雖然用不完），于是便有了下圖。

造兩個(gè) map 作為空閑列表

可以看出，我們的基本思路是從后往前進(jìn)行數(shù)據(jù)布局，最后還剩一個(gè)塊。該塊我們是故意留的，用以充當(dāng)文件系統(tǒng)的超級(jí)塊（superblock）。超級(jí)塊作為一個(gè)文件系統(tǒng)的入口，通常會(huì)保存一些文件系統(tǒng)級(jí)別的元信息，比如本文件系統(tǒng)中有多少個(gè) inode 和數(shù)據(jù)塊（80 和 56），inode 表的起始?jí)K偏移量（3），等等。

最后一個(gè) block 是入口，稱為超級(jí)塊

則當(dāng)文件系統(tǒng)被裝載（ mount ）時(shí)，操作系統(tǒng)會(huì)首先讀取超級(jí)塊（所以放最前面），并據(jù)此初始化一系列參數(shù)，并將其作為數(shù)據(jù)卷掛載到文件系統(tǒng)樹中。有了這些基本信息，當(dāng)該卷中的文件被訪問到時(shí)，就能逐步找出其位置，也就是我們之后要講的讀寫流程。

但在講讀寫流程之前，需要先放大一些關(guān)鍵數(shù)據(jù)結(jié)構(gòu)看看其內(nèi)在布局。

索引節(jié)點(diǎn)（Inode）

inode 是索引節(jié)點(diǎn)（index node）的簡(jiǎn)稱，是對(duì)文件和文件夾的索引節(jié)點(diǎn)。為了簡(jiǎn)單，我們使用數(shù)組來組織索引節(jié)點(diǎn)，每個(gè) inode 會(huì)關(guān)聯(lián)一個(gè)編號(hào)（inumber），也即其在數(shù)組中的下標(biāo)（偏移量）。

索引區(qū)的詳細(xì)布局

上面提到過一嘴，每個(gè) inode 占 256B。則給定一個(gè) inumber，我們就可以計(jì)算出其在硬盤中的偏移量（12KB + inumber * 256），但由于內(nèi)外存交換是按塊來的，我們可以據(jù)此進(jìn)而計(jì)算出其所在磁盤塊。

inode 主要保存文件名、一些元信息（權(quán)限控制、各種事件、一些標(biāo)記位）和數(shù)據(jù)塊索引。數(shù)據(jù)塊索引其實(shí)也是元信息，單拎出來說是因?yàn)樗苤匾?/p>

我們使用一種比較簡(jiǎn)單的索引方式：間接指針（indirect pointer）。即 inode 中保存的不是直接指向數(shù)據(jù)塊的指針，而是指向一個(gè)指針塊（也在數(shù)據(jù)區(qū)分配，但保存的都是二級(jí)指針）。如果文件足夠大，可能還會(huì)引出三級(jí)指針（至于我們這個(gè)小系統(tǒng)是否用的著，大家可以估算下）。

但我們統(tǒng)計(jì)發(fā)現(xiàn)，在大多數(shù)文件系統(tǒng)中，小文件占多數(shù)。小到什么地步呢？一個(gè)數(shù)據(jù)塊就可以存下。

Untitled

因此實(shí)踐中，我們?cè)?inode 中使用一種直接指針和間接指針混合的方式進(jìn)行表示。在我們的文件系統(tǒng)中，就是使用 12 個(gè)直接指針和 1 個(gè)間接指針。所以只要文件尺寸不超過 12 個(gè)數(shù)據(jù)塊，就可以直接用直接指針。只有過大時(shí)，才使用間接指針，并且在數(shù)據(jù)區(qū)新分配數(shù)據(jù)塊，來存間接指針。

我們的數(shù)據(jù)區(qū)很小，只有 56 個(gè) block，假設(shè)使用 4byte 進(jìn)行索引。則二級(jí)指針最多可支持 (12 + 1024) · 4K ，也就是 4144KB 大小的文件。

另一種實(shí)踐中常用的方式是數(shù)據(jù)段（extents）。即將每個(gè)連續(xù)數(shù)據(jù)區(qū)用起始指針和大小來表示，然后將一個(gè)文件的所有數(shù)據(jù)段串起來。但多段數(shù)據(jù)時(shí)，如果想訪問最后一個(gè)數(shù)據(jù)段或者隨機(jī)訪問，性能會(huì)很差（下一個(gè)數(shù)據(jù)段的指針都保存在上一個(gè)數(shù)據(jù)段中）。為了優(yōu)化訪問速度，常將該數(shù)據(jù)段的索引鏈表存在內(nèi)存中。Windows 的早期文件系統(tǒng) FAT 就是這么干的。

目錄組織

在我們的文件系統(tǒng)中，目錄組織得很簡(jiǎn)單——即和文件一樣，每個(gè)目錄也占用一個(gè) inode，但在 inode 指向的數(shù)據(jù)塊不是存文件內(nèi)容，而是存儲(chǔ)該目錄中所包含的所有文件和文件夾的信息，通常是用 List<entry name, inode number>  表示。當(dāng)然要轉(zhuǎn)為實(shí)際編碼，還要存文件名長(zhǎng)度等信息（因?yàn)槲募亲冮L(zhǎng)的）。

看一個(gè)簡(jiǎn)單例子，設(shè)我們有一個(gè)文件夾 dir （inode 編號(hào)是 5），里面有三個(gè)文件（foor，bar 和 foobar），其對(duì)應(yīng)的 inode 編號(hào)分別是 12，13 和 24 。則在該文件夾的數(shù)據(jù)塊中存儲(chǔ)的信息如下：

dir 內(nèi)容的編碼

其中 reclen （record length）是文件名所占空間大小，strlen 是實(shí)際長(zhǎng)度。點(diǎn)和點(diǎn)點(diǎn)是指向本文件夾和上級(jí)文件夾的兩個(gè)指針。記錄reclen 看著有點(diǎn)多此一舉，但要考慮到文件刪除問題（可以用特殊的 inum，比如 0 來標(biāo)記刪除）。如果文件夾下的某個(gè)文件或者目錄被刪除，存儲(chǔ)就會(huì)出現(xiàn)空洞。reclen 的存在，可以讓刪除留下的空洞為之后新增的文件復(fù)用。

需要說明的是，線性的組織一個(gè)目錄中的文件是最簡(jiǎn)單的方式。實(shí)踐中，還有其他方式。比如說在 XFS 中，如果目錄中文件或者子文件夾特別多，會(huì)使用 B+ 樹進(jìn)行組織。從而在插入時(shí)，可以很快地知道是否有同名文件。

空閑空間管理

當(dāng)我們需要新建文件或者目錄項(xiàng)時(shí)，就需要從文件系統(tǒng)中獲取一塊可用空間。因此，如何高效的管理空閑空間，是個(gè)很重要的問題。我們使用兩個(gè) bitmap 進(jìn)行管理，優(yōu)點(diǎn)是簡(jiǎn)單，缺點(diǎn)是每次都得線性的掃描查找所有空閑 bit 位，且只能做到塊粒度，塊內(nèi)如果有剩余空間，就管不到了。

讀寫路徑

有了對(duì)磁盤上的數(shù)據(jù)結(jié)構(gòu)的把握之后，我們?cè)賮硗ㄟ^讀寫流程將不同的數(shù)據(jù)結(jié)構(gòu)串一下。我們假設(shè)文件系統(tǒng)已經(jīng)被掛載：即超級(jí)塊（superblock）已經(jīng)在內(nèi)存中。

讀取文件

我們的操作很簡(jiǎn)單，就是打開一個(gè)文件（如 /foo/bar），進(jìn)行讀取，然后關(guān)閉。簡(jiǎn)化起見，假設(shè)我們文件大小占一個(gè) block，即 4k。

當(dāng)發(fā)起一個(gè)系統(tǒng)調(diào)用 open("/foo/bar", O RDONLY)時(shí)，文件系統(tǒng)需要首先找到文件 bar 對(duì)應(yīng)的 inode，以獲取其元信息和數(shù)據(jù)位置信息。但現(xiàn)在我們只有文件路徑，那怎么辦呢？

答曰：從根目錄往下遍歷。根目錄的 inode 編號(hào)，我們要么保存在超級(jí)塊中，要么就寫死（比如 2，大部分 Unix 文件系統(tǒng)都是從 2 開始的）。也即，必須能事先知道（well known）。

于是文件系統(tǒng)將該根目錄的 inode 從硬盤調(diào)入內(nèi)存，進(jìn)而再通過 inode 中的指針找到其指向數(shù)據(jù)塊，進(jìn)而從其包含所有子目錄和文件夾中找到 foo 文件夾和其對(duì)應(yīng) inode。遞歸的重復(fù)上述過程，open 系統(tǒng)調(diào)用的最后一步是將 bar 的 inode 載入內(nèi)存，進(jìn)行權(quán)限檢查（比對(duì)進(jìn)程用戶權(quán)限和 inode 訪問權(quán)限控制），分配文件描述符放到進(jìn)程打開文件表中，并將其返回給用戶。

一旦文件被打開后，就可以繼而發(fā)起 read() 的系統(tǒng)調(diào)用 ，真正地去讀取數(shù)據(jù)。讀取時(shí)，首先會(huì)根據(jù)文件的 inode 信息，找到第一個(gè) block（除非讀前實(shí)現(xiàn)用 lseek() 修改過偏移量），然后讀取。同時(shí)，可能會(huì)更改 inode 的一些元信息，比如說訪問時(shí)間。繼而，更新進(jìn)程中該文件描述符的偏移量，繼續(xù)往下讀，直到某個(gè)時(shí)刻，調(diào)用 close() 關(guān)閉該文件描述符。

進(jìn)程關(guān)閉文件時(shí)，所需工作要少得多，只需要釋放文件描述符即可，并不會(huì)有真正的磁盤 IO。

最后，我們?cè)俎垡幌逻@個(gè)讀文件過程。從根目錄的 inode 編號(hào)開始，我們交替地讀取 inode 和相應(yīng)數(shù)據(jù)塊，直到最終找到待查找文件。然后要進(jìn)行數(shù)據(jù)讀取，還要更新其 inode 的訪問時(shí)間等元信息，進(jìn)行寫回。下表簡(jiǎn)單地總結(jié)了下這個(gè)過程，可以看出，讀取路徑全程不會(huì)涉及分配結(jié)構(gòu)—— data bitmap 和 inode bitmap。

文件讀取時(shí)間線

從深度上來說，如果我們的待查找路徑層級(jí)非常多，這個(gè)過程會(huì)線性增長(zhǎng)；從廣度上來說，如果中間查找時(shí)涉及到的文件夾，其包含的目錄子項(xiàng)特別多，即文件樹“很寬”，則每次在目錄中進(jìn)行查找時(shí)，可能需要讀取不止一個(gè)數(shù)據(jù)塊。

寫入硬盤

寫文件和讀取文件的流程很類似，也是打開文件（從根目錄一路找到對(duì)應(yīng)文件）；然后開始寫入，最后關(guān)閉。但與讀取文件不同的是，寫入需要分配新的數(shù)據(jù)塊，這就需要涉及我們之前的 bitmap 了，通常來說，一次寫入至少需要五次 IO：

1. 讀取 data bitmap（以找到空閑塊，并在內(nèi)存中標(biāo)記使用）
2. 寫回 data bitmap（以對(duì)其他進(jìn)程可見）
3. 讀取 inode（增加新的數(shù)據(jù)位置指針）
4. 寫回 inode
5. 在找到的空閑塊中寫入數(shù)據(jù)

這還只是對(duì)已經(jīng)存在的文件進(jìn)行寫入。如果是尚未存在的文件進(jìn)行創(chuàng)建并寫入，那流程還要更為復(fù)雜：還要?jiǎng)?chuàng)建 inode，這就會(huì)引入一系列新的 IO：

1. 一次對(duì) inode bitmap 的讀?。ㄕ业娇臻e inode）
2. 一次對(duì) inode bitmap 的寫回（標(biāo)記某個(gè) inode 被占用）
3. 一次對(duì) inode 本身的寫入（初始化）
4. 一次對(duì)父文件夾所對(duì)應(yīng)目錄子項(xiàng)數(shù)據(jù)塊的讀寫（增加新建的文件和 inode 對(duì)）
5. 一次對(duì)父文件夾 inode 的讀寫（更新修改日期）

如果父文件夾的數(shù)據(jù)塊不夠用，還得需要新分配空間，就又得讀 data bitmap，和 data block。下圖是創(chuàng)建 /foo/bar 文件的時(shí)間線上涉及到的 IO：

創(chuàng)建文件的時(shí)間線

緩存和緩沖

從上面對(duì)讀寫流程的分析可以看出，即便如此簡(jiǎn)單的讀寫操作，都會(huì)涉及大量 IO，這在實(shí)踐中是不可接受的。為了解決這個(gè)問題，大部分工業(yè)上的文件系統(tǒng)，會(huì)充分利用內(nèi)存，將重要的（也就是頻繁訪問的）數(shù)據(jù)塊緩存（cache）在內(nèi)存中；與此同時(shí)，為了避免頻繁刷盤，會(huì)將修改先應(yīng)用到內(nèi)存緩沖區(qū)（buffer）里，然后積攢后一塊落盤。

早期的文件系統(tǒng)引入了固定尺寸緩存（fixed-size cache），如果滿了，會(huì)利用 LRU 等替換算法進(jìn)行頁面淘汰。其缺點(diǎn)在于當(dāng)緩存不滿的時(shí)候浪費(fèi)空間，滿了又可能頻繁換頁。我們稱這種風(fēng)格為靜態(tài)分區(qū)（static partitioning）。大部分現(xiàn)代文件系統(tǒng)，都是用動(dòng)態(tài)分區(qū)（dynamic partitioning）技術(shù)。比如，將虛擬內(nèi)存頁和文件系統(tǒng)頁放到一個(gè)池子中，稱為統(tǒng)一頁面緩存（unified page cache），從而上兩者分配和更加彈性。上了緩存之后，對(duì)于同一個(gè)目錄中多個(gè)文件的讀取，后面的讀取就可以省下很多 IO。

寫流程由于前半程根據(jù)路徑查找數(shù)據(jù)塊時(shí)牽扯到讀，所以也會(huì)從緩存中受益。但對(duì)于寫的部分，我們可以通過緩沖區(qū)（writing buffering），來延遲刷盤。延遲刷盤有很多好處，比如說可以多次修改 bitmap 可能只需要刷一次；積攢一批更改，可以提高 IO 帶寬利用率；如果文件先增后刪，可能就直接省了刷盤。

但這些性能的提升是有代價(jià)的——意外宕機(jī)可能會(huì)造成數(shù)據(jù)丟失。所以，雖然現(xiàn)代文件系統(tǒng)大部分開啟了讀寫緩沖，但也通過 direct I/O 的方式，來允許用戶繞過緩存，直接寫磁盤。對(duì)丟失數(shù)據(jù)很敏感的應(yīng)用，可以利用其對(duì)應(yīng)的系統(tǒng)調(diào)用 fsync() 來即時(shí)刷盤。

小結(jié)

至此，我們完成了一個(gè)至簡(jiǎn)的文件系統(tǒng)的實(shí)現(xiàn)。其“麻雀雖小，五臟俱全”，我們從中可以看出文件系統(tǒng)設(shè)計(jì)一些基本的理念：

1. 使用 inode 存儲(chǔ)文件粒度的元信息；使用數(shù)據(jù)塊存真正的文件數(shù)據(jù)
2. 目錄是一種特殊的文件，只不過存的不是文件內(nèi)容，而是文件夾子目錄項(xiàng)
3. 除了 inode 和數(shù)據(jù)塊外，還需要一些其他的數(shù)據(jù)結(jié)構(gòu)，比如 bitmap 來追蹤空閑塊

從這個(gè)基本的文件系統(tǒng)出發(fā)，我們其實(shí)可以看到特別多的可以取舍和優(yōu)化的點(diǎn)，如果感興趣，大家可以在本文基礎(chǔ)上，去看看一些工業(yè)上的文件系統(tǒng)的設(shè)計(jì)。

參考資料

[1]Operating Systems: Three Easy Pieces: https://pages.cs.wisc.edu/~remzi/OSTEP/

[2]JuiceFS: https://github.com/juicedata/juicefs