檔案系統考古2：1984

今天繼續與大家分享系列文章《50 years in filesystems》，由 KRISTIAN KÖHNTOPP 撰寫。

我們將進入檔案系統的第二個十年，即1984年，計算機由微型計算機發展到了桌面和機櫃工作站， BSD Fast Filing System 登場。

回看第一篇： 1974-Unix V7 File System

早期的 Unix 檔案系統已經表現得很好，但也存在一些明顯的問題。這些問題在作業系統 BSD（Berkeley Software Distribution）中進行了許多修復。 BSD 起源於 20 世紀 70 年代末和 80 年代初，由加州大學伯克利分校的電腦科學系開發和推廣。在 Leffler、McKusick 等人撰寫的的書中《The Design and Implementation of the 4.3BSD UNIX Operating System》有所記錄。

1984 年發表的一篇經典論文《A Fast File System for UNIX》中，可以找到更簡明、也更學術的討論。該論文的作者包括 Marshall McKusick、Bill Joy（當時在Sun公司）、Samuel Leffler（當時在LucasFilm 公司）和 Robert Fabry。該論文提出了一個對 Unix 檔案系統的重新實現方案，旨在提升檔案系統的吞吐能力、優化儲存空間的分配和增強資料存取的區域性性。

The hardware

在1984 年，4.3BSD 所針對的計算機是桌面和機櫃工作站。這些機器具有 32 位資料暫存器和 32 位地址暫存器。

外部資料和地址匯流排的大小各不相同：早期的 68k 系列 CPU 匯流排尺寸較小。但在 1984 年，Motorola 68020 誕生了。它是首款提供完整 32 位寬度匯流排的 68k 系列，整合了大約 200,000 個電晶體在晶片上。後來，68030 將原本獨立的 MMU（記憶體管理單元）整合到了晶片上，而 68040 則將原本獨立的 FPU（浮點運算單元）也整合到了晶片上。

早期的 Sun 工作站，如 Sun-3系列，採用了這些 CPU。但 Sun 公司從伯克利實驗性的 RISC 系統中借鑑了設計思路，並於1986年釋出了基於 SPARC 架構的 Sun-4 系列工作站。SPARC 架構採取了一些妥協的策略，但執行地很好，在 Sun 公司被 Oracle 收購之前持續得到改進與發展。然而，在之後的發展中 Oracle 先後終止了 SPARC和 Itanium CPU 架構的發展。

Curt Schimmel 在《UNIX Systems for Modern Architectures》一書中討論了 SPARC 在 MMU、暫存器和記憶體存取設計上所做的權衡，以及為什麼這樣做是合理的。與此同時，在1985年，MIPS 架構首次亮相，這是另一系列的 RISC CPU 架構。它也是一個完全的 32位元系統，被用於 SGI 工作站。

惠普公司也有另一種 RISC 型別的 CPU，即 PA-RISC，它是「Spectrum」研究計劃的產物，在1986 年上市（後來被 Intel 的一款失敗產品 Itanium 取代）。

計算機系統領域的先鋒公司 DEC自己有 VAX，這是一種具有 CISC CPU 的 32 位機櫃式計算機，從 1977 年開始就已經存在。直到 1992 年，他們才轉向 RISC 架構，而後採用 Alpha AXP（「DEC Alpha」）架構，完全實現了 64 位。儘管這個架構很有趣，但它的存在時間不長：1998年被康柏公司收購後，該 CPU 停產，其智慧財產權於 2001 年出售給了英特爾。

總的來說，1984 年的工作站型別系統的主記憶體容量在幾十 MB 左右，執行時的系統時脈頻率在幾十 MHz 左右。

傳統檔案系統的短板

在 20 世紀 80 年代，32 位 VAX 系統被用於典型的工作站任務，包括影象處理和 VLSI 晶片設計等工作。當時使用的 Unix 檔案系統在處理檔案大小、 I/O 速度和檔案數量方面出現了結構性問題。此外，只有 512 位元組的 I/O 大小大大降低了磁碟子系統的效能。

論文中提到，檔案系統的後設資料和資料嚴格分離，即後設資料位於檔案系統的前部，而實際資料則位於檔案系統的後部。這種分離設計有助於提高檔案系統的效能和擴充套件性。

一個150MB 的傳統 Unix 檔案系統由4MB 的inode（索引節點）和146MB 的資料組成。這種組織方式將 inode 資訊與資料分隔開來，因此存取檔案通常需要從檔案的 inode 到其資料之間進行一次長距離尋道。在一個目錄中，檔案通常不會被分配到 4MB 的 inode 連續槽位中，這就導致在對目錄中多個檔案的 inode 執行操作時，需要存取許多非連續的 inode 塊。

正是因為這個後設資料和資料分離的設計帶來的問題，BSD FFS （BSD Fast Filing System) 的一個主要目標是改善檔案系統的佈局，將後設資料和資料更加靠近，將單個目錄中的檔案儲存得更加緊湊，避免檔案被分散成小碎片，從而提高載入效率。

碎片化：首先，建立四個檔案，每個檔案使用兩個塊。然後刪除了檔案 B 和 D。接著，空閒的空間被一個佔用三個塊大小的檔案E回收，但是檔案 E 被儲存在不連續的塊中。這導致了小的磁碟尋道和較慢的 I/O 操作。

另一個明確的目標是增加磁碟塊的大小。較大的磁碟塊在兩個方面有助於提高吞吐量：

較大的磁碟塊提供了更大的 I/O 單元，因此可以在單個 I/O 操作中傳輸更多的資料；
較大的磁碟塊還允許檔案系統在一個間接塊中儲存更多的檔案指標，大大減少了對間接塊的存取次數。

該論文參照了一個 Unix 檔案系統經過優化後的吞吐量，大約是理論最大值的4%，這是非常低效的。這主要歸因於檔案的碎片化，即檔案中相鄰塊的非連續儲存。對於碎片整理，雖然在 1976 年已經提出，但被認為不可行而被放棄。作者們希望通過在檔案的初始儲存位置上合理地放置檔案來解決這個問題。

BSD FFS 的創新之處

理解柱面組和磁區

BSD FFS 的設計基於對硬碟的物理佈局的理解，包括柱面、磁頭和磁區（CHS）。它將硬碟分成柱面組，相鄰的磁軌屬於同一個柱面組。

當硬碟旋轉時，不同的磁頭進入碟片堆中，就像一個梳子。每個磁頭在磁碟上標記一個磁軌，控制器硬體將該磁軌細分為物理磁碟塊。所有磁頭標記的磁軌組成一個柱面。柱面組是一組連續的柱面。（影象來源：OSTEP，第3頁）

每個柱面組都是一個傳統 Unix 檔案系統的迷你版本，包括超級塊的副本、自己的本地索引節點區域以及本地索引節點和塊使用點陣圖。點陣圖的使用也是新穎的，它們取代了傳統檔案系統中使用的空閒列表。由於檔案系統知道 CHS 佈局的資訊，它能夠確保每個副本的超級塊不總是放置在同一碟片上，以提高檔案系統對硬碟故障的容錯性。

在 RAID（冗餘磁碟陣列）論文發表之前幾年，根據 Katz 的說法，RAID也是在伯克利開發的，時間為1983/1984年。

Katz 還提到，在那個時候，Stonebraker 一直在開發 Ingres（Postgres的前身），並提到他對低提交延遲的要求推動了改善 FFS 和後來 RAID 磁碟頻寬的嘗試。然而，對於RAID 分類的正統的研究直到1987年才開始。

許多初創公司和儲存公司都將 RAID 論文作為他們開發的基礎，其中包括 NetApp 和 EMC（通過Data General的Clariion 磁碟陣列）。

BSD FFS 不僅瞭解磁碟的 CHS 幾何結構，還了解處理器速度和磁碟的旋轉速度。這使得它能夠設定並在超級塊中記錄交錯因子，以優化磁碟 I/O 吞吐量。

硬碟持續不斷地旋轉，但是 CPU 需要時間來設定下一次傳輸。在此期間，磁頭可能已經超過了下一個塊的起始邊界，現在系統需要等待一次完整的旋轉才能進行寫入。使用適當的交錯因子，相鄰的塊號不會被連續地儲存在磁碟上，而是在它們之間交錯插入其他塊。這給了 CPU 足夠的時間來思考和設定下一個塊的傳輸。

CPU速度越快，所需的交錯因子就越低。

隨著硬碟開始配備整合控制器，並開始隱藏 CHS幾何結構，並最終被線性塊地址（LBA）取代，所有這些優化相對變得無關緊要。然而，在過去的十到十五年間，這些優化為系統提供了顯著的效能優勢。

大分塊、小片段和尾部合併

在內部，FFS 使用至少4 KB大小的邏輯塊。這些邏輯塊，通過最多不超過兩級間接塊可以建立出最大 4GB 的檔案。

較大的塊可以提高 I/O 速度，但它們也會帶來儲存開銷，因為檔案的大小會按塊遞增。由於 FFS中的邏輯塊由多個物理塊組成，因此 FFS引入了片段（fragment）的概念，以公開較小的內部物理塊。片段表示邏輯塊內部的更小儲存單位。通過引入片段的概念，FFS 可以更細粒度地管理和利用儲存空間。尾部打包（tail packing）是一種技術，可以將多個檔案的末尾儲存在同一個邏輯塊中。在傳統的檔案系統中，當檔案的末尾部分不足以填滿一個完整的物理塊時，會導致空間浪費。因此，尾部打包的方法可以減少空間浪費。同時，通過利用片段的概念，尾部打包可以儘可能提升儲存空間利用率。

為了防止進入片段逐漸增長和不斷需要重新佈局的階段，此處系統採用的設計是：系統預先分配空間以填滿邏輯塊，並且尾部打包僅在檔案關閉（即取消預分配）時才會發生。

長距離定址分配策略

BSD FFS 引入了一系列佈局策略，用於控制新目錄、新檔案的放置以及大檔案的處理。全域性策略主要關注選擇適合的柱面組來存放資料，而本地策略則負責柱面組內的具體放置。
新的檔案系統佈局採用柱面組。每個柱面組都有自己的 inode 表，以及用於 inode 和塊的空閒空間點陣圖。檔案系統旨在防止碎片化。

在某些情況下，是無法實現的：例如，如果一個柱面組的大小為 512 MB，並且要寫入一個大於512 MB的檔案，它將使用該柱面組中的一個 inode，但所有可用的空閒塊已經用完。如果要將第二個檔案放置到該柱面組中，inode可以被使用，但是該檔案的資料塊需要放置在其他地方，這是不理想的。

對於大檔案，最好強制進行長距離尋道，從一個柱面組切換到下一個柱面組。檔案系統可以從每一兆位元組檔案大小開始強制執行這樣的長距離尋道。這將均勻地使用相鄰柱面組之間的空閒塊，同時在每個柱面組中保留一定數量的空閒塊供其他檔案使用。

這會有意地使檔案產生碎片，但同時也確保碎片足夠大以支援大檔案的 I/O。碎片化（檔案中塊的非相鄰放置）只有在碎片太小以至於無法高效讀取時才會真正成為效能問題。

目錄分配策略

相同目錄中的檔案通常會一起使用。將同一目錄中的所有檔案放置在同一個柱面組中是很有效的做法。

當然，這樣做時還需要將不同的目錄放置在不同的柱面組中，以確保檔案系統空間的均勻使用。這意味著一個像這樣的 Shell 指令碼：

這個指令碼將建立名為 fileXX 的十個檔案，並將它們全部放置在與當前目錄相同的柱面組中。

它還會在當前目錄下建立十個名為 dirXX 的子目錄。條件允許的話，每個子目錄都會被放置在不同的柱面組中。FFS 會選擇那些空閒 inode 數量高於平均水平且已有目錄數量最少的柱面組。在柱面組中選擇 inode 的方式是「下一個可用的」，因為整個柱面組的 inode 表只佔用 8-16 個塊。

為了放置資料塊，考慮到這臺機器所需的交錯因子，FFS 投入了很多精力來尋找旋轉最優的塊。

BSD FFS 要求檔案系統始終保持一定的可用空間。如果檔案系統填滿超過90％，許多演演算法將退化為傳統檔案系統的效能水平。

BSD FFS 其他改進

更大 Inode 和分塊地址

例如，inode 號現在是 32 位數位。這個改變使得檔案系統中可能的檔案數量從 64K 增加到 42億。

Inode 的大小已經翻倍：它現在被強制為 128 位元組的大小（其中有 20 個未使用的位元組）。此外，磁碟塊地址現在是 4 個位元組。在 4KB 塊大小的情況下，這足以支援 42 億個塊，或者最大 16TB 的檔案系統大小。

檔案長度被記錄在一個 quad 中，這樣可以支援超過 4GB 的單個檔案大小。
Inode 現在包含 12 個直接塊和三種型別的間接塊。在 4KB 塊大小的情況下，每個間接塊可以容納 1024 個塊地址，因此每個檔案可以容納 12 + 1024 + 1024^2 + 1024^3 = 1074791436 個塊，或者最大檔案大小略大於 4TB。

Unix 使用者 ID 和組 ID 長度仍然限制為一個 short 型別，每個系統的使用者和組數量限制為 64 K。

即使 inode 中的時間型別仍然限制為 4 位元組，但已經為 8 位元組的時間戳預先分配了空間。

長檔名

傳統檔案系統中，目錄項具有固定的 16 位元組長度，其中 2 位元組用於儲存 inode 號，14位元組用於儲存檔名。

BSD FFS 定義了更復雜的目錄項結構。一個目錄項包含一個 4 位元組的 inode 號，一個 2 位元組的記錄長度和一個 2 位元組的名稱長度，然後是實際的檔名。路徑中的每個檔案或者目錄名限制為 255 位元組，目錄項的長度向上取整到下一個 4 位元組邊界。

目錄仍然基本上是一個連結串列，因此在大型目錄中搜尋名稱是很慢的。而在目錄中搜尋可用空間則更加複雜：為了建立一個新的目錄條目，我們需要從開頭開始遍歷目錄，試圖找到當前結構中足夠大以容納待建立名稱的空隙。如果找不到空隙，則將新名稱追加到末尾，從而增加目錄的大小。

目錄中的空閒空間不會通過壓縮來回收，只有在新的檔名稱恰好適合時才會最終重新使用，也就是說當系統需要在目錄中建立新的目錄項或檔案時，它會首先嚐試找到一個已有的空間，其大小足夠容納待建立的名稱。如果找到這樣的空間，系統將把新的名稱插入到該空間中，利用已有的空閒空間，而無需增加目錄的大小。然而，如果沒有足夠大的空間可用，系統將追加新的名稱到目錄的末尾，從而增加目錄的大小。

符號連結

傳統的檔案系統允許一個檔案擁有多個名稱，使用link()系統呼叫和硬連結機制。硬連結有數量限制（一個 short 型別，最多 64K 個名稱）。

硬連結（hardlink）可能會意外丟失，例如，通過使用某些編輯器儲存一個有硬連結的檔案時。如果編輯器將檔案儲存為 filename.new，然後取消連結舊的 filename 並將新檔案移動到相應位置，那麼檔案的硬連結屬性將會被修改。

硬連結（hardlink）是指在檔案系統中建立的指向同一檔案或目錄的多個檔名。它們與原始檔案（或目錄）共用相同的 inode（索引節點），因此它們實際上是相同的檔案，只是具有不同的檔名。硬連結允許多個檔名參照同一份資料，節省儲存空間，並且對檔案的更改會在所有硬連結之間保持同步。

硬連結還會多次參照原始檔案的 inode，而 inode 是特定於檔案系統的，因此它們不能跨越檔案系統。

BSD 引入了一種新的檔案型別（l，符號連結），並在連結檔案中放置一個「替換檔名」，用於確定連結目標位置。它可以是絕對路徑或相對路徑（相對於符號連結檔案的位置）。

當嘗試存取符號連結時，系統將在 namei() 函數中重新解析檔名，使用連結中的檔名，從而將 open() 系統呼叫重定向到連結指向的位置。簡單來說，符號連結提供了一個檔名的替代方式，當存取符號連結時，實際上是在存取連結的目標檔案。

由於重定向發生在 namei() 中，它可以跨檔案系統，因此新的連結型別不受單個檔案系統的限制。它也不計入任何連結計數限制。

重新命名系統呼叫

BSD 引入了 rename() 系統呼叫。過去，則需要通過呼叫 unlink() 和 link() 實現。由於這涉及多個系統呼叫，該操作不是原子操作：它可能會部分執行，並且容易受到惡意干擾。

配額

BSD 引入了檔案系統使用配額的概念：這是對使用者或組可以使用的檔案數量和磁碟空間量設定的軟限制（soft limit）和硬限制（hard limit）。

為了有效地實現它們，需要做如下修改：

現在，如果一個使用者想要把自己檔案的所有者改為其他使用者，那麼他必須擁有特權操作的許可權。否則，他就只能建立一個只有自己能存取的目錄，然後把目錄裡的所有檔案都傳送給目標使用者。這樣一來，這些檔案就會佔用另一個使用者的配額，而不是自己的配額。
類似地，不再允許將檔案的組員身份更改為任意組。只允許設定為該使用者所屬的某個組。
最後，新建立的目錄和檔案繼承自它們的父目錄，而不是使用者的主要組。這樣，專案目錄中的檔案將計入專案的配額，而不是使用者主要組配額。

諮詢式檔案鎖

4.2BSD 中已經引入了諮詢式檔案鎖。為了實現這種機制，它引入了新的 flock() 系統呼叫。

檔案鎖可以是共用的（讀鎖）或獨佔的（寫鎖）；
它們總是作用於整個檔案，而不是位元組範圍；
不嘗試檢測死鎖；
它們與檔案描述符繫結。因此，當程序死亡時，其檔案控制程式碼會自動關閉，從而自動釋放所有持有的鎖。這非常健壯，直到 dup() 和 fork() 開始發揮作用。

後來，POSIX 試圖改進這一點，引入了第二種完全不同的鎖系統 fcntl()。它存在一些缺陷，但可以對位元組範圍進行操作，並實現了一些基本的死鎖檢測。

在這類實現了這兩種檔案鎖機制的核心中如Linux系統，這兩種鎖機制互不相容，也不知道對方的存在。

在《Advisory File Locking – My take on POSIX and BSD locks》這篇文章中進一步討論了所有這些內容，並提供了範例程式。

總體表現

在論文中，作者指出了以下優點：

Ls 和ls -l 命令的速度很快，因為單個目錄中檔案的 inode 位於同一個柱面組內。因此，讀取和列出目錄時，尋道次數非常少，尋道距離也很短（除了子目錄，它們通常要保證彼此的距離很遠）。測試發現，當檢索一個沒有包含子目錄的目錄時，速度提高了8倍；
在傳統檔案系統中，理論最大頻寬的利用率僅為3%，而在使用不同的控制器硬體的情況下，這一利用率增加到了22%甚至47%。作者對這些結果感到非常自豪，因為這些結果是在實際的生產系統上產生的。儘管檔案的數量和規模可能會改變，但檔案系統在其生命週期內能夠持續相對穩定的吞吐量。

這些改進解決了主要的需求，即提高吞吐量和穩定的佈局，使效能不會隨時間降低。

此外，還進行了許多提升使用者體驗的改進，使得 BSD 在團隊使用的過程中表現地更好；以及開啟了一些新功能。

雖然 Linux 中並沒有 BSD 程式碼，但 Ext2 檔案系統基本上是對 BSD FFS 的重新實現。

無論是 BSD FFS 還是 Linux ext2，它們仍然是非紀錄檔檔案系統，在發生崩潰後需要進行檔案系統檢查。它們在處理具有許多條目的目錄方面也表現不佳，在處理深層次目錄結構時稍好一些。為了跟上不斷增長的儲存容量，BSD FFS 和 Linux ext2 這兩個檔案系統需要進行額外的改進和優化，以便能夠更好地支援處理大容量儲存媒介和大型檔案系統。

此外，仍然存在其他一些不太明顯的限制：檔案系統程式碼中的幾個位置受到鎖的保護，使得在具有高並行性的系統上擴充套件某些操作變得困難。

直到1994年，SGI 的 XFS 才開始解決這些問題，經過了另外十年的時間。

未完待續。

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