技術文章 » 檔案系統考古：1974-Unix V7 File System

檔案系統考古：1974-Unix V7 File System

2023-05-26 18:01:28

有時，進步難以察覺，特別是當你正身處其中時。而對比新舊資料之間的差異，尋找那些推動變革的資訊源，我們就可以清晰地看到進步的發生。在Linux（以及大部分Unix系統）中，都可以印證這一點。

Unix V7 是 Unix 作業系統的一個重要的早期版本，於 1979 年釋出，是貝爾實驗室最後一個廣泛分發的版本。它是第一個真正可移植的 Unix 版本，被移植到了多種平臺上，包括 DEC PDP-11, VAX, x86, Motorola 68000 等。Unix V7 的 VAX 移植版本，叫做 UNIX/32V，是流行的 4BSD 系列 Unix 系統的直接祖先。許多老牌的 Unix 使用者認為 Unix V7 是 Unix 發展的頂峰。

Unix V7 Research Release 的原始碼可以在 unix-history-repo 這個由 Diomidis Spinellis 維護的專案中找到。如果你想深入瞭解 Unix 的設計原理，可以參考 Maurice J. Bach 的經典著作 The Design of the Unix Operating System，並檢視 Research V7 Snapshot 這個分支的程式碼庫。

Machines

1974 年，計算機擁有一個「核心」，即中央處理單元。然而，在某些計算機中，這個「核心」已經發生了變化。不再是由多個部件（如算術邏輯單元、暫存器、順序控制器和微碼記憶體）組成的裝置，而是一顆單一的整合晶片，單個晶片上整合了數千個電晶體。它們被叫做「小型計算機」。

Kernels

在 Unix 中，我們通過設定標頭檔案（header file）來處理系統資源。如下圖所示，這裡顯示了標頭檔案中設定的預設值，資料結構是陣列，所示值是相應的陣列大小。如果要更改它們，則需要編輯檔案，重新編譯和連結核心，然後重新啟動系統。

它有一個檔案系統緩衝區快取（file system buffer cache），使用 NBUF（29）個磁碟塊，每個磁碟塊的大小是 512 位元組，用來暫時儲存磁碟上的資料塊和 inode，從而加速檔案系統存取。另外還有一個索引節點陣列（inode array），它有 NINODE （200）個條目，每個條目對應一個檔案的後設資料，還可以同時掛載 NMOUNT （8）個檔案系統。每個使用者最多可以執行MAXUPRC（25）個程序，總共有 NPROC（150）個系統程序。每個程序最多可以開啟 NOFILE（20）個檔案。

閱讀 Bach 的著作和 V7 原始碼是很有趣的，儘管它們已經完全過時。因為這些原始碼中呈現出的許多核心概念更加清晰，結構更簡潔，有時甚至帶有古老的風格。然而，正是這些概念定義了 Unix 檔案系統。V7 Unix 被寫入了 POSIX 標準，之後的每個檔案系統都必須遵守它。如果您想了解更多相關範例，請參考 But Is It Atomic?

核心概念

Unix 檔案系統的基本概念和結構來自這個系統。其中一些概念甚在現代系統中依然存在。

磁碟由一系列資料塊（block）組成，從第 0 塊開始，一直到第 n 塊結束。在檔案系統的開始部分，我們可以找到超級塊（superblock）。它位於檔案系統的第 1 塊。超級塊儲存了檔案系統的一些基本資訊，比如檔案系統的大小、空閒塊的數量、空閒索引節點的數量等。當我們執行掛載（mount）系統呼叫時，系統會找到一個空閒的掛載結構（mount structure），並且從磁碟上讀取超級塊，把它作為掛載結構的一部分。

Inode

記憶體中的超級塊（in-memory superblock）是磁碟上超級塊的副本，用於加快檔案系統的存取速度。它包含一個 short 型別的欄位，用於儲存一個索引節點陣列（inode array）在磁碟上的位置。

索引節點（inode）是一個描述檔案內容和屬性的結構，檔案內容由一系列資料塊（block）組成，每個資料塊的大小是固定的（通常是 512 位元組或 1024 位元組），檔案屬性包含檔名、大小、許可權、時間戳等後設資料（metadata）。

檔案系統中的 inode 陣列是一個 short 型別的計數器，它的最大值是 65535，也就是說檔案系統中最多隻能有 65535 個 inode。由於每個檔案都需要一個 inode，因此每個檔案系統最多隻能容納 65535 個檔案。
每個檔案具有一些固定屬性：

  • （2位元組）mode，它包含了檔案的型別和存取許可權；
  • （2位元組）nlink，它表示這個檔案有多少個名字；
  • （2位元組）uid，檔案的所有者；
  • （2位元組）gid，檔案所有者的組 ID；
  • （4位元組）size，檔案的長度，以位元組為單位（定義為 off_t，長整型）；
  • （40位元組）addr 陣列，包含了檔案的資料塊在磁碟上的地址;
  • （3x 4位元組）三個時間，atime（存取時間），mtime（修改時間）和 ctime（所謂的建立時間，但實際上是最後一個 inode 更改的時間）。

總大小為 64 位元組。

bmap()

Addr 陣列包含 40 個位元組，但它儲存了 13 個磁碟塊地址，每個地址使用 3 個位元組。這對於 24 位來說非常適用，或者說對應於 16 個大小為 512 位元組的兆塊，總檔案系統大小為 8M 千位元組，即 8GB。

PDP-11 RL02K磁碟盒可容納 10.4 MB，而更新的 RA92 可儲存 1.5 GB。
Addr 陣列在 bmap() 函數中被使用。該函數接收一個 inode（ip）和一個邏輯塊號 bn，並返回一個物理塊號。也就是說，它將檔案中的一個塊對映到磁碟上的一個塊，因此得名。

前 10 個塊指標直接儲存在 inode 中。例如，要存取塊 0，bmap() 將在 inode 中查詢 di_addr[0] 並返回該塊號。

額外的塊儲存在一個間接塊中，而間接塊則儲存在 inode 中。對於更大的檔案，會分配一個雙間接塊，並指向更多的間接塊，最終非常大的檔案需要甚至三次間接塊。

程式碼首先確定需要多少層間接定址，也就是要通過多少個間接塊才能找到檔案內容的磁碟塊。然後，獲取相應的間接塊。最後，程式碼按照適當的次數解析間接定址，也就是根據層數依次從間接塊中讀取其他間接塊或直接塊的地址，直到找到檔案內容的磁碟塊。

對於越來越大的檔案，原始的 Unix 檔案結構採用了逐漸增加的間接存取次數。這樣形成了一個壓縮的陣列，其中較短的檔案可以直接通過 inode 中的資料進行存取，而較大的檔案則需要通過越來越多的間接存取來獲取資料。為了提高效能，保持間接塊在檔案系統緩衝區快取記憶體中是至關重要的。

這種擴充套件性取決於塊大小（早期為 512 位元組，現在為 4096 位元組）和塊號的位元組大小（最初為 3 位元組，後來為 4 位元組甚至 8 位元組）。

Atomic writes

檔案的寫入是在加鎖的狀態下進行的，因此它們始終具有原子性。即使是跨越多個資料塊的寫入操作，也是如此。這一點在 But Is It Atomic? 中有詳細討論。
這也意味著即使有多個寫入程序，在單個檔案上，任何時刻只能有一個磁碟寫入操作處於活躍狀態。這對資料庫系統的開發者來說非常不便利。

Naming files

目錄是一個具有特殊型別和固定記錄結構的檔案。

一個目錄條目包含一個inode號（一個無符號整數）和一個檔名，檔名的長度最多可以達到14個位元組。這使得一個磁碟塊可以容納32個目錄條目，而一個目錄檔案的直接塊可以參照的10個磁碟塊可以容納320個目錄條目。

下層（lower）的檔案系統中充滿了大量的檔案。這些檔案沒有名稱，只有編號。
上層 （upper）的檔案系統使用一種特殊型別的檔案，具有簡單的16位元組記錄結構，用於為檔案分配最多14個字元的名稱。一個特殊的函數namei()將檔名轉換為inode號。

傳遞給namei()的路徑名具有層次結構：它們可以包含/作為路徑分隔符，並以\0（NUL）作為終止符。路徑名若以/開頭，則遍歷將從檔案系統的根目錄開始，形成絕對路徑名；若不以/開頭，則遍歷將從u.u_cdir，即當前目錄開始。
該函數逐個消耗路徑名的各個組成部分，使用當前活動目錄，並在該目錄中線性搜尋當前元件的名稱。當找到最後一個路徑名元件或在任何階段找不到元件時，該函數結束。如果在路徑中的任何目錄的任何點上，我們沒有 x 許可權，它也會結束。

該函數按順序逐個處理路徑名的各個組成部分。它使用當前目錄，並在該目錄中線性搜尋當前組成部分的名稱。函數的結束條件有兩種情況：一是找到了路徑名的最後一個組成部分，二是在路徑的任何目錄中，出現了無法存取的情況。
掛載點是特殊條目，它會從當前節點和檔案系統的目錄條目切換到掛載檔案系統的根inode。這使得Unix中的所有檔案系統看起來像是一棵單一的樹，如果要進行"硬碟修改"的操作，只需簡單地切換到不同的目錄。

最終，該函數將返回給定路徑名的inode指標，根據需要和需求建立（或刪除）inode（和目錄條目）。它是目錄遍歷和存取許可權檢查的集中點。

一些創新的想法以及限制

這個早期的Unix檔案系統具有許多很好的特性：

  • 它將多個檔案系統呈現為一個統一的樹形結構；

  • 檔案是無結構的位元組陣列；

  • 這些陣列以可動態增加深度的動態陣列的形式儲存。它們內部使用一種逐漸巢狀的間接塊系統，其中陣列的元素可以是指向其他陣列或資料的指標，從而形成層次巢狀的結構。這使得磁碟搜尋的複雜度為O(1)；

  • 下層檔案系統建立檔案和上層的檔案系統組織檔案互相隔離，分工明確。獲取inode的唯一方式是路徑名遍歷，並且在此過程中始終檢查許可權；

  • 檔名中只有很少的特殊字元，即/和\0（空字元）。

但也有明顯的限制：

  • 檔案只能有16M個塊；

  • 檔案系統只能有非常有限的65535個inode。

還有一些令人討厭的限制：

  • 檔案只能有一個正在寫入的程序，這會導致並行性受限；

  • 目錄查詢是線性掃描，因此對於大型目錄（超過320個條目），速度變得非常慢；

  • 沒有強制檔案鎖定系統。但存在幾種用於諮詢式檔案鎖定的系統。

還有一些特殊情況：

  • 在 Unix V7 系統中，沒有 delete() 系統呼叫，而是 unlink() 系統呼叫，它可以刪除一個檔案的名字，並且那些沒有任何檔名和開啟檔案控制程式碼的檔案會被自動清理。這會導致一些不符合預期的結果，例如，只有當一個完全沒有檔名的檔案被完全關閉時，它佔用的磁碟空間才會被釋放。許多 Unix 系統管理員都曾經問過他們的磁碟空間去哪了，當他們刪除了 /var/log 目錄下的紀錄檔檔案，卻忘記了有一些程序還在使用它；

  • 最初沒有 mkdir() 和 rmdir() 系統呼叫，這導致了存在可被利用的競態條件。競態條件是指在多執行緒或多程序環境中，由於操作的順序和時機不確定性，可能導致安全漏洞或錯誤行為的情況。這在 Unix 的後續版本中得到了修復；

  • 有一些操作在特定條件下具有原子性（例如write(2)系統呼叫），或者經過修改後具有原子性（mknod(2)和mkdir(2)）。

在結構上，inode表和塊和inode的空閒對映位於檔案系統的開頭，磁碟空間也是從磁碟的前端線性分配的。這導致了頻繁的定址操作，並且可能導致檔案系統的碎片化（即檔案儲存在非相鄰的塊中）。

遍歷目錄結構意味著從磁碟開頭讀取目錄的inode，然後向後移動到更遠的資料塊，再從磁碟開頭讀取下一個路徑名組成部分的下一個inode，並向後移動到相應的資料塊。這個過程在每個路徑名組成部分上來回進行，速度並不快。

改進

在之後的發展中，minix檔案系統忠實繼承了PDP-11 V7 Unix檔案系統，保留了它的特性包括侷限。然而，隨著時間的推移，在現代的Linux系統中，由於其不再具備實用性，它已經從核心原始碼中移除。

在稍後的一篇文章中，我們將會了解到關於BSD快速檔案系統，如何更好地佈局磁碟上的資料，如何實現更長的檔名、更多的inode，以及如何通過考慮磁碟的物理特性來加快速度。

要解決目錄查詢時間線性增長、單個寫入者或有限的檔案後設資料這些問題需要更新的檔案系統。

翻譯自：《50 years in filesystems》 由 KRISTIAN KÖHNTOPP 撰寫。

如有幫助的話歡迎關注我們專案 Juicedata/JuiceFS 喲！ (0ᴗ0✿)