當一名開發者在應用程式中寫下一行看似簡單的 open("data.txt") 程式碼時，他其實啟動了作業系統內部一趟精密而複雜的旅程。這個高階的、以符號名稱為基礎的請求，是如何被層層轉譯，最終成為驅動儲存硬體讀寫特定磁區的低階電氣訊號？這整個過程的奧秘，深藏於檔案系統的分層式架構（Layered File-System Structure）之中。此設計是現代作業系統的基石，它透過優雅的抽象化，將複雜的I/O操作分解為數個職責分明、相互協作的層級。
這種分層設計不僅實現了關注點分離（Separation of Concerns），讓系統的開發與維護變得模組化，更使得不同層級的實作可以獨立演進。例如，我們可以替換底層的硬碟為固態硬碟（SSD），而無需修改上層處理檔案名稱與目錄的邏輯。接下來，我們將由下至上，逐一剖析這四個關鍵層級，揭示檔案系統如何從物理現實走向邏輯抽象。
檔案系統的最底層是 I/O 控制層，它是作業系統核心與物理儲存裝置之間最直接的橋樑。此層級的組成核心為裝置驅動程式（Device Drivers）與中斷處理常式（Interrupt Handlers）。它的根本職責是將來自上層的、較為抽象的指令（例如「讀取物理區塊編號 12345」），轉化為特定硬體控制器（Hardware Controller）能夠理解的具體操作序列。
裝置驅動程式扮演著翻譯官的角色。不同的儲存裝置，例如 SATA 硬碟、NVMe SSD 或 USB 隨身碟，都有其專屬的通訊協定與指令集。驅動程式封裝了這些硬體細節，為上層提供一個統一的、以區塊（Block）為單位的操作介面。當需要執行操作時，作業系統會透過 記憶體映射 I/O（Memory-Mapped I/O） 等技術，將命令與資料位址等參數寫入到裝置控制器的特定暫存器（Registers）中。控制器接收到這些訊號後，便會啟動硬體執行實際的讀寫。當操作完成或發生錯誤時，硬體會觸發一個中斷，喚醒對應的中斷處理常式，後者再將操作結果通知作業系統核心，從而完成一次非同步的 I/O 流程。在此層級，系統完全感知不到檔案或目錄的存在，其視野僅限於物理裝置上的區塊陣列與硬體控制訊號。
在 I/O 控制層之上，是基本檔案系統層。此層級的功能是基於 I/O 控制層提供的基礎，進行通用區塊的 I/O 管理。它向上層隱藏了具體裝置的驅動細節，只提供一個更為簡潔的命令介面，例如 read_block(block_number) 或 write_block(block_number)。
此層級肩負兩項關鍵的效能優化任務。第一是緩衝區快取管理（Buffer Cache Management）。為了避免每次讀寫請求都直接觸發緩慢的物理 I/O，作業系統會在主記憶體中保留一塊區域作為快取，稱為緩衝區快取。當上層請求讀取某個磁碟區塊時，基本檔案系統會先檢查該區塊是否已存在於快取中。若命中，則直接從記憶體回傳資料，速度極快；若未命中，才向 I/O 控制層發出讀取請求，並將讀回的區塊存入快取以備後用。同理，寫入操作也常採用寫回（Write-back）策略，先寫入快取，稍後再由系統排程批量寫回硬碟。
第二項任務是 I/O 排程（I/O Scheduling）。當系統中存在多個待處理的磁碟 I/O 請求時，若不加管理，隨機的存取順序會導致傳統硬碟的磁頭頻繁移動，大幅降低吞吐量。I/O 排程器會根據電梯演算法（Elevator Algorithm）等策略，對這些請求進行重新排序，使其盡可能地沿著磁碟的單一方向移動，從而優化存取效率。即便對於沒有磁頭的 SSD，I/O 排程依然有其價值，例如可以合併相鄰的請求或進行優先權管理。值得注意的是，此層級依然只處理匿名的物理區塊，對「檔案」這一邏輯概念一無所知。
檔案組織模組層是檔案系統抽象化過程中的關鍵躍升。正是在此層，系統首次將無差別的物理區塊與具體的「檔案」概念連結起來。其核心職責是管理檔案的邏輯結構與磁碟空間的分配。
此模組知道一個檔案是由一連串的邏輯區塊（Logical Blocks）（例如，檔案的第 0 塊、第 1 塊...）所組成，並且負責將這些邏輯區塊映射到儲存裝置上的物理區塊（Physical Blocks）。這種映射關係的建立方式，直接定義了檔案的磁碟配置策略，例如：連續配置（Contiguous Allocation）、連結配置（Linked Allocation）或索引配置（Indexed Allocation）。不同的策略在空間利用率、存取效能與檔案大小的彈性上各有取捨。例如，FAT 檔案系統使用連結配置，而 Unix-like 系統的 ext 家族則採用了更高效的索引配置（i-node）。
此外，此層級也負責管理整個儲存卷的可用空間（Free Space）。它必須知道哪些物理區塊已被佔用，哪些是空閒的。為了高效追蹤這些資訊，它會使用如位元圖（Bitmap）或空閒鏈結串列（Free List）等資料結構。當需要為新檔案或擴增的檔案分配空間時，檔案組織模組會查詢這些資料結構，找出合適的空閒區塊並將其分配出去。
位於最上層的邏輯檔案系統層，是使用者與應用程式最常直接互動的介面。它處理所有關於檔案的符號性資訊，也就是元資料（Metadata）。此層級不再關注資料區塊的物理位置，而是專注於管理檔案的邏輯屬性。
其核心功能包括管理目錄結構（Directory Structure）、檔案名稱、檔案權限（擁有者、群組、存取模式）以及其他屬性（如建立時間、修改時間、檔案類型等）。這些元資料通常被組織在一個稱為檔案控制區塊（File Control Block, FCB）的資料結構中，在 Unix-like 系統中則更常被稱為 i-node。
當應用程式發出 open() 系統呼叫時，邏輯檔案系統便會介入。它會解析檔案路徑（Path），逐層遍歷目錄結構，查找與檔名對應的 FCB。一旦找到，系統會進行權限驗證，檢查發起請求的程序是否具備所需的操作權限。驗證通過後，系統會在核心中建立一個代表此開啟檔案的物件（通常稱為 file handle），並將其回傳給應用程式。後續的 read()、write() 等操作都會透過這個 file handle 進行。
在檔案系統的宏觀架構中，目錄（Directory）扮演著至關重要的角色，它如同檔案世界的索引或地圖，為每一個檔案名稱提供尋找其實體資料的線索。任何檔案操作，例如 open("data.txt")，都始於一次目錄查詢。因此，目錄結構的設計效率，直接決定了檔案系統的整體效能與使用者體驗。本文將深入探討兩種核心的目錄實作策略：最基礎的線性串列（Linear List）與為效能而生的雜湊表（Hash Table）。
一個目錄的核心功能，是維護一系列的目錄項目（Directory Entry）。每個項目都至少包含兩個關鍵資訊：檔案的名稱，以及一個指向該檔案元資料與資料區塊的指標（例如在 Unix-like 系統中的 i-node 編號）。如何組織這些目錄項目，便是目錄實作所要解決的核心問題。一個優良的設計，必須在搜尋效率、新增與刪除操作的成本，以及使用者執行 ls 等指令時的反應速度之間取得平衡。
最直觀且易於實作的目錄結構，便是線性串列。此方法將所有目錄項目一個接一個地存放在一個連續的資料區塊中，形成一個簡單的列表。當需要建立一個新檔案時，系統首先必須遍歷整個串列，以確保沒有同名的檔案存在。這一步驟是為了維持檔案名稱在同一目錄下的唯一性。確認名稱可用後，新的目錄項目便會被附加到串列的末尾。檔案的搜尋操作同樣依賴於線性掃描，系統從串列的開頭開始，逐一比對檔案名稱，直到找到目標或遍歷完所有項目為止。這種方法的演算法時間複雜度為 O(n)，其中 n 為目錄中的檔案數量。
刪除操作則相對複雜一些。在找到目標檔案並釋放其對應的資料區塊後，目錄中會留下一個空位。如何處理這個空位，有幾種不同的策略。最簡單的方式是將其標記為未使用，例如將檔案名稱清空或設定一個無效標記。但這種方法可能導致目錄結構內部產生碎片，浪費儲存空間。更有效的方法是將串列中的最後一個項目移動到被刪除的空位上，以保持結構的緊湊性。另一種做法是維護一個「空位清單」，專門記錄可供後續新檔案重複使用的位置。
線性串列的優點在於其結構簡單明瞭。然而，其致命的缺點也源於此。隨著目錄下的檔案數量增長，線性搜尋的成本急劇上升，導致系統效能顯著下降。在一個包含數千個檔案的目錄中進行操作，會變得極其緩慢，這在現代應用場景中是難以接受的。
為了解決線性串列的效能瓶頸，現代檔案系統普遍採用了更為高效的資料結構——雜湊表。此方法不再依賴循序搜尋，而是試圖透過計算直接定位檔案。其運作原理是將檔案名稱作為輸入，透過一個精心設計的雜湊函數（Hash Function），將其轉換成一個數值，這個數值即為該目錄項目在雜湊表中的索引（Index）。理想情況下，如果每個檔案名稱都能對應到一個獨一無二的索引，那麼無論是搜尋、新增還是刪除，都只需要一次計算即可完成，時間複雜度接近於常數時間 O(1)。
然而，在現實中，「雜湊碰撞（Collision）」是不可避免的，即兩個或多個不同的檔案名稱可能產生相同的雜湊索引。處理碰撞是雜湊表設計的關鍵。最常見且高效的策略是鏈結法（Chaining）。在此方法中，雜湊表的每一個槽位（bucket）不再只存放單一項目，而是作為一個鏈結串列（Linked List）的頭部。所有雜湊到同一個索引的目錄項目，都會被依序加入到對應的鏈結串列中。
採用此設計後，檔案的搜尋過程變為：首先計算檔案名稱的雜湊值以定位到對應的槽位，然後只需遍歷該槽位後方的短鏈結串列即可，而非整個目錄。只要雜湊函數分佈良好，且雜湊表大小適當，每個鏈結串列的長度都能維持在一個很小的範圍內，從而確保操作效率接近 O(1)。新增與刪除操作也同樣高效，它們轉化為對目標鏈結串列的節點移除或插入，過程極為迅速
檔案系統的核心職責之一，是對儲存裝置的空間進行生命週期管理。磁碟上的區塊（Block）是一種有限的資源，當檔案被創建、增大、縮減或刪除時，作業系統必須有一套精確而高效的機制來分配與回收這些區塊。這套機制被稱為「空間管理」（Free-Space Management），其優劣直接影響到檔案系統的效能、可靠性與空間利用率。
為了達成此目標，作業系統會維護一份名為「空閒空間列表」（Free-Space List）的紀錄，此紀錄追蹤著所有尚未被使用的磁碟區塊。當需要為新檔案分配空間時，系統會查詢此列表以尋找合適的區塊；當檔案被刪除後，其佔用的區塊則會被歸還至此列表，以供後續使用。以下將深入探討四種實現此機制的經典策略，並分析其各自的設計哲學與應用場景。
位元向量，或稱位元圖（Bitmap），是空間管理中最為直觀的方法之一。其概念是為磁碟上的每一個區塊，都對應到一個位元（bit）。例如，可以用 1 來表示該區塊處於空閒（Free）狀態，用 0 表示已被分配（Allocated）。如此一來，整個磁碟的空間使用狀況就被映射成一張巨大的位元地圖。這種方法的顯著優點在於其簡單性與查詢效率。當檔案系統需要尋找一個或多個連續的空閒區塊時，只需在記憶體中掃描這位元向量，尋找一串連續的 1 即可。現代處理器通常具備高效的位元操作指令集，能夠極快地完成這類搜尋任務，因此位元向量法對於需要連續配置策略的檔案系統而言特別高效。
然而，它的缺點也相當明顯。最主要的問題是空間開銷。對於一個大型的磁碟區，位元向量本身可能會佔用相當可觀的記憶體空間。舉例來說，一個 4TB 的磁碟若以 4KB 大小的區塊進行管理，其位元向量將需要高達 128MB 的儲存空間。若此向量無法完全載入主記憶體，系統就必須在磁碟和記憶體之間來回分頁讀取，從而降低效能。此外，每次區塊狀態的變更都需要更新位元向量，並最終將其寫回磁碟以確保資料一致性，這也可能成為 I/O 的一個瓶頸。
鏈結串列法則採用了截然不同的思路。它將所有空閒的磁碟區塊串連成一條單向的鏈結串列。具體的做法是，在每一個空閒區塊的起始處，存放一個指向下一個空閒區塊的指標（Pointer）。作業系統在記憶體中僅需儲存一個指向串列頭部（Head）的指標即可。這種策略的最大優勢在於其極低的記憶體需求，因為整個空閒區塊的資訊是分佈儲存在磁碟本身之上的。新增與回收區塊的操作也相對簡單：從頭部取下一個區塊進行分配，或將被釋放的區塊插入到串列頭部。
但是，鏈結串列法的效能問題也極為突出。由於指標存放在磁碟區塊中，對串列的任何遍歷操作都意味著一次或多次的磁碟 I/O。例如，僅僅是為了找到串列中的第二個空閒區塊，就需要讀取第一個空閒區塊以獲得指標。這種循序存取的特性使得查找效率極低，且完全無法有效地支援需要連續空間的分配請求。因此，純粹的鏈結串列法在現代高效能檔案系統中已不多見。
分組法可以視為對傳統鏈結串列法的一種改良，旨在緩解其嚴重的 I/O 效能問題。其核心思想是，不再讓每個空閒區塊只指向下一個空閒區塊，而是在一個空閒區塊中儲存一組（例如 n-1 個）其他空閒區塊的位址，並將第 n 個位置用作指標，指向下一個存放著更多空閒區塊位址的「組區塊」。
透過這種方式，作業系統只需執行一次磁碟讀取操作，就能將一個「組區塊」載入記憶體，從而一次性獲得數十甚至數百個可用區塊的位址。這大大減少了為滿足批量分配請求所需的磁碟 I/O 次數，顯著提升了效率。本質上，分組法是用批次處理的方式，攤銷了鏈結串列法的磁碟存取成本。儘管它仍然需要在需要新的一組位址時讀取磁碟，但相比於逐塊讀取，效能已有巨大提升。
計數法專為優化連續空間的管理而設計。它不再記錄每一個單獨的空閒區塊，而是記錄連續空閒區塊的起始位置與其長度。例如，空閒空間列表中的一筆紀錄可能是 (起始區塊位址: 1000, 連續區塊數量: 128)，這代表從區塊 1000 到 1127 都是可用的。
當檔案系統中存在大量連續的空閒空間時（例如一個剛格式化或剛刪除一個大檔案的磁碟），計數法的優勢便展露無遺。它能以極小的空間開銷來表示大片的可用區域，使得空閒列表本身非常簡潔。當需要分配一段連續空間給新檔案時，系統只需在此列表中尋找一個長度足夠的條目即可，查詢效率極高。然而，計數法的效能與磁碟的碎片化程度息息相關。如果磁碟空間被分割得非常零碎，到處都只是單一的、不連續的空閒區塊，那麼計數法的列表將會退化為大量的 (位址, 數量: 1) 這樣的條目，其空間和管理效率反而可能不如位元向量法。
iThome鐵人賽
看影片追技術