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

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

總體布局

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

就這么點空間的迷你硬盤

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

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

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

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

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

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

隔出來索引區(qū)

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

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

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

造兩個 map 作為空閑列表

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

最后一個 block 是入口，稱為超級塊

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

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

索引節(jié)點（Inode）

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

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

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

inode 主要保存文件名、一些元信息（權(quán)限控制、各種事件、一些標(biāo)記位）和數(shù)據(jù)塊索引。數(shù)據(jù)塊索引其實也是元信息，單拎出來說是因為它很重要。

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

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

Untitled

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

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

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

目錄組織

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

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

dir 內(nèi)容的編碼

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

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

空閑空間管理

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

讀寫路徑

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

讀取文件

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

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

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

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

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

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

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

文件讀取時間線

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

寫入硬盤

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

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

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

1. 一次對 inode bitmap 的讀取（找到空閑 inode）
2. 一次對 inode bitmap 的寫回（標(biāo)記某個 inode 被占用）
3. 一次對 inode 本身的寫入（初始化）
4. 一次對父文件夾所對應(yīng)目錄子項數(shù)據(jù)塊的讀寫（增加新建的文件和 inode 對）
5. 一次對父文件夾 inode 的讀寫（更新修改日期）

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

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

緩存和緩沖

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

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

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

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

小結(jié)

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

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

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

參考資料

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

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