文件系統基本都是構建于塊存儲之上的。但當然，現在的一些分布式文件系統，如 JuiceFS[2]，底層是基于對象存儲的。但無論塊存儲還是對象存儲，其本質都是按 “數據塊” 進行尋址和數據交換的。

我們首先會探討一個完整的文件系統在硬盤上的數據結構，也即布局；然后再通過打開關閉、讀寫流程將各個子模塊串起來，從而完成對一個文件系統要點的覆蓋。

總體布局

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

就這么點空間的迷你硬盤

基于此迷你硬盤，我們一起來逐步推導下這個極簡文件系統。

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

隔出來數據區

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

1. 文件名
2. 文件大小
3. 文件歸屬者
4. 訪問權限
5. 創建、修改時間

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

隔出來索引區

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

現在我們有了數據區，有了文件元信息區，但在一個正常使用的文件系統中，還需要追蹤哪些數據塊被用了，哪些還沒有被使用。這種數據結構我們稱之為分配結構（allocation structures）。業界常用的方法有空閑鏈表（free list），即把所有空閑塊按鏈表的方式串起來。但為了簡單，這里使用一種更簡單的數據結構：位圖（bitmap），數據區用一個，稱數據位圖（data bitmap）；inode 表用一個，稱 inode 位圖（inode bitmap）。

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

造兩個 map 作為空閑列表

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

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

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

但在講讀寫流程之前，需要先放大一些關鍵數據結構看看其內在布局。

索引節點（Inode）

inode 是索引節點（index node）的簡稱，是對文件和文件夾的索引節點。為了簡單，我們使用數組來組織索引節點，每個 inode 會關聯一個編號（inumber），也即其在數組中的下標（偏移量）。

索引區的詳細布局

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

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

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

但我們統計發現，在大多數文件系統中，小文件占多數。小到什么地步呢？一個數據塊就可以存下。

Untitled

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

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

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

目錄組織

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

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

dir 內容的編碼

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

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

空閑空間管理

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

讀寫路徑

有了對磁盤上的數據結構的把握之后，我們再來通過讀寫流程將不同的數據結構串一下。我們假設文件系統已經被掛載：即超級塊（superblock）已經在內存中。

讀取文件

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

當發起一個系統調用 open("/foo/bar", O RDONLY)時，文件系統需要首先找到文件 bar 對應的 inode，以獲取其元信息和數據位置信息。但現在我們只有文件路徑，那怎么辦呢？

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

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

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

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

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

文件讀取時間線

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

寫入硬盤

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

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

這還只是對已經存在的文件進行寫入。如果是尚未存在的文件進行創建并寫入，那流程還要更為復雜：還要創建 inode，這就會引入一系列新的 IO：

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

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

創建文件的時間線

緩存和緩沖

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

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

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

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

小結

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

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

從這個基本的文件系統出發，我們其實可以看到特別多的可以取舍和優化的點，如果感興趣，大家可以在本文基礎上，去看看一些工業上的文件系統的設計。

參考資料

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

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