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

我們將進入文件系統(tǒng)的第二個十年，即1984年，計算機由微型計算機發(fā)展到了桌面和機柜工作站， BSD Fast Filing System 登場。

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

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

1984 年發(fā)表的一篇經典論文《A Fast File System for UNIX》中，可以找到更簡明、也更學術的討論。該論文的作者包括 Marshall McKusick、Bill Joy（當時在Sun公司）、Samuel Leffler（當時在LucasFilm 公司）和 Robert Fabry。該論文提出了一個對 Unix 文件系統(tǒng)的重新實現(xiàn)方案，旨在提升文件系統(tǒng)的吞吐能力、優(yōu)化存儲空間的分配和增強數(shù)據(jù)訪問的局部性。

The hardware

在1984 年，4.3BSD 所針對的計算機是桌面和機柜工作站。這些機器具有 32 位數(shù)據(jù)寄存器和 32 位地址寄存器。

外部數(shù)據(jù)和地址總線的大小各不相同：早期的 68k 系列 CPU 總線尺寸較小。 但在 1984 年，Motorola 68020 誕生了。它是首款提供完整 32 位寬度總線的 68k 系列，集成了大約 200,000 個晶體管在芯片上。后來，68030 將原本獨立的 MMU（內存管理單元）集成到了芯片上，而 68040 則將原本獨立的 FPU（浮點運算單元）也集成到了芯片上。

早期的 Sun 工作站，如 Sun-3系列，采用了這些 CPU。但 Sun 公司從伯克利實驗性的 RISC 系統(tǒng)中借鑒了設計思路，并于1986年發(fā)布了基于 SPARC 架構的 Sun-4 系列工作站。SPARC 架構采取了一些妥協(xié)的策略，但運行地很好，在 Sun 公司被 Oracle 收購之前持續(xù)得到改進與發(fā)展。然而，在之后的發(fā)展中 Oracle 先后終止了 SPARC和 Itanium CPU 架構的發(fā)展。

Curt Schimmel 在《UNIX Systems for Modern Architectures》一書中討論了 SPARC 在 MMU、寄存器和內存訪問設計上所做的權衡，以及為什么這樣做是合理的。與此同時，在1985年，MIPS 架構首次亮相，這是另一系列的 RISC CPU 架構。它也是一個完全的 32位系統(tǒng)，被用于 SGI 工作站。

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

計算機系統(tǒng)領域的先鋒公司 DEC自己有 VAX，這是一種具有 CISC CPU 的 32 位機柜式計算機，從 1977 年開始就已經存在。直到 1992 年，他們才轉向 RISC 架構，而后采用 Alpha AXP（“DEC Alpha”）架構，完全實現(xiàn)了 64 位。盡管這個架構很有趣，但它的存在時間不長：1998年被康柏公司收購后，該 CPU 停產，其知識產權于 2001 年出售給了英特爾。

總的來說，1984 年的工作站類型系統(tǒng)的主內存容量在幾十 MB 左右，運行時的系統(tǒng)時鐘頻率在幾十 MHz 左右。

傳統(tǒng)文件系統(tǒng)的短板

在 20 世紀 80 年代，32 位 VAX 系統(tǒng)被用于典型的工作站任務，包括圖像處理和 VLSI 芯片設計等工作。當時使用的 Unix 文件系統(tǒng)在處理文件大小、 I/O 速度和文件數(shù)量方面出現(xiàn)了結構性問題。此外，只有 512 字節(jié)的 I/O 大小大大降低了磁盤子系統(tǒng)的性能。

論文中提到，文件系統(tǒng)的元數(shù)據(jù)和數(shù)據(jù)嚴格分離，即元數(shù)據(jù)位于文件系統(tǒng)的前部，而實際數(shù)據(jù)則位于文件系統(tǒng)的后部。這種分離設計有助于提高文件系統(tǒng)的性能和擴展性。

一個150MB 的傳統(tǒng) Unix 文件系統(tǒng)由4MB 的inode（索引節(jié)點）和146MB 的數(shù)據(jù)組成。這種組織方式將 inode 信息與數(shù)據(jù)分隔開來，因此訪問文件通常需要從文件的 inode 到其數(shù)據(jù)之間進行一次長距離尋道。在一個目錄中，文件通常不會被分配到 4MB 的 inode 連續(xù)槽位中，這就導致在對目錄中多個文件的 inode 執(zhí)行操作時，需要訪問許多非連續(xù)的 inode 塊。

正是因為這個元數(shù)據(jù)和數(shù)據(jù)分離的設計帶來的問題，BSD FFS （BSD Fast Filing System) 的一個主要目標是改善文件系統(tǒng)的布局，將元數(shù)據(jù)和數(shù)據(jù)更加靠近，將單個目錄中的文件存儲得更加緊湊，避免文件被分散成小碎片，從而提高加載效率。

碎片化：首先，創(chuàng)建四個文件，每個文件使用兩個塊。然后刪除了文件 B 和 D。接著，空閑的空間被一個占用三個塊大小的文件E回收，但是文件 E 被存儲在不連續(xù)的塊中。這導致了小的磁盤尋道和較慢的 I/O 操作。

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

1. 較大的磁盤塊提供了更大的 I/O 單元，因此可以在單個 I/O 操作中傳輸更多的數(shù)據(jù)；
2. 較大的磁盤塊還允許文件系統(tǒng)在一個間接塊中存儲更多的文件指針，大大減少了對間接塊的訪問次數(shù)。

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

BSD FFS 的創(chuàng)新之處

理解柱面組和扇區(qū)

BSD FFS 的設計基于對硬盤的物理布局的理解，包括柱面、磁頭和扇區(qū)（CHS）。它將硬盤分成柱面組，相鄰的磁道屬于同一個柱面組。

tu

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

每個柱面組都是一個傳統(tǒng) Unix 文件系統(tǒng)的迷你版本，包括超級塊的副本、自己的本地索引節(jié)點區(qū)域以及本地索引節(jié)點和塊使用位圖。位圖的使用也是新穎的，它們取代了傳統(tǒng)文件系統(tǒng)中使用的空閑列表。由于文件系統(tǒng)知道 CHS 布局的信息，它能夠確保每個副本的超級塊不總是放置在同一盤片上，以提高文件系統(tǒng)對硬盤故障的容錯性。

在 RAID（冗余磁盤陣列）論文發(fā)表之前幾年，根據(jù) Katz 的說法，RAID也是在伯克利開發(fā)的，時間為1983/1984年。

Katz 還提到，在那個時候，Stonebraker 一直在開發(fā) Ingres（Postgres的前身），并提到他對低提交延遲的要求推動了改善 FFS 和后來 RAID 磁盤帶寬的嘗試。然而，對于RAID 分類的正統(tǒng)的研究直到1987年才開始。

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

BSD FFS 不僅了解磁盤的 CHS 幾何結構，還了解處理器速度和磁盤的旋轉速度。這使得它能夠配置并在超級塊中記錄交錯因子，以優(yōu)化磁盤 I/O 吞吐量。

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

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

隨著硬盤開始配備集成控制器，并開始隱藏 CHS幾何結構，并最終被線性塊地址（LBA）取代，所有這些優(yōu)化相對變得無關緊要。然而，在過去的十到十五年間，這些優(yōu)化為系統(tǒng)提供了顯著的性能優(yōu)勢。

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

在內部，F(xiàn)FS 使用至少4 KB大小的邏輯塊。這些邏輯塊，通過最多不超過兩級間接塊可以創(chuàng)建出最大 4GB 的文件。

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

為了防止進入片段逐漸增長和不斷需要重新布局的階段，此處系統(tǒng)采用的設計是：系統(tǒng)預先分配空間以填滿邏輯塊，并且尾部打包僅在文件關閉（即取消預分配）時才會發(fā)生。

長距離尋址分配策略

BSD FFS 引入了一系列布局策略，用于控制新目錄、新文件的放置以及大文件的處理。全局策略主要關注選擇適合的柱面組來存放數(shù)據(jù)，而本地策略則負責柱面組內的具體放置。
新的文件系統(tǒng)布局采用柱面組。每個柱面組都有自己的 inode 表，以及用于 inode 和塊的空閑空間位圖。文件系統(tǒng)旨在防止碎片化。

在某些情況下，是無法實現(xiàn)的：例如，如果一個柱面組的大小為 512 MB，并且要寫入一個大于512 MB的文件，它將使用該柱面組中的一個 inode，但所有可用的空閑塊已經用完。如果要將第二個文件放置到該柱面組中，inode可以被使用，但是該文件的數(shù)據(jù)塊需要放置在其他地方，這是不理想的。

對于大文件，最好強制進行長距離尋道，從一個柱面組切換到下一個柱面組。文件系統(tǒng)可以從每一兆字節(jié)文件大小開始強制執(zhí)行這樣的長距離尋道。這將均勻地使用相鄰柱面組之間的空閑塊，同時在每個柱面組中保留一定數(shù)量的空閑塊供其他文件使用。

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

目錄分配策略

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

當然，這樣做時還需要將不同的目錄放置在不同的柱面組中，以確保文件系統(tǒng)空間的均勻使用。這意味著一個像這樣的 Shell 腳本：

這個腳本將創(chuàng)建名為 fileXX 的十個文件，并將它們全部放置在與當前目錄相同的柱面組中。

它還會在當前目錄下創(chuàng)建十個名為 dirXX 的子目錄。條件允許的話，每個子目錄都會被放置在不同的柱面組中。FFS 會選擇那些空閑 inode 數(shù)量高于平均水平且已有目錄數(shù)量最少的柱面組。在柱面組中選擇 inode 的方式是“下一個可用的”，因為整個柱面組的 inode 表只占用 8-16 個塊。

為了放置數(shù)據(jù)塊，考慮到這臺機器所需的交錯因子，F(xiàn)FS 投入了很多精力來尋找旋轉最優(yōu)的塊。

BSD FFS 要求文件系統(tǒng)始終保持一定的可用空間。如果文件系統(tǒng)填滿超過90％，許多算法將退化為傳統(tǒng)文件系統(tǒng)的性能水平。

BSD FFS 其他改進

更大 Inode 和分塊地址

例如，inode 號現(xiàn)在是 32 位數(shù)字。這個改變使得文件系統(tǒng)中可能的文件數(shù)量從 64K 增加到 42億。

Inode 的大小已經翻倍：它現(xiàn)在被強制為 128 字節(jié)的大?。ㄆ渲杏?20 個未使用的字節(jié)）。此外，磁盤塊地址現(xiàn)在是 4 個字節(jié)。在 4KB 塊大小的情況下，這足以支持 42 億個塊，或者最大 16TB 的文件系統(tǒng)大小。

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

Unix 用戶 ID 和組 ID 長度仍然限制為一個 short 類型，每個系統(tǒng)的用戶和組數(shù)量限制為 64 K。

即使 inode 中的時間類型仍然限制為 4 字節(jié)，但已經為 8 字節(jié)的時間戳預先分配了空間。

長文件名

傳統(tǒng)文件系統(tǒng)中，目錄項具有固定的 16 字節(jié)長度，其中 2 字節(jié)用于存儲 inode 號，14字節(jié)用于存儲文件名。

BSD FFS 定義了更復雜的目錄項結構。一個目錄項包含一個 4 字節(jié)的 inode 號，一個 2 字節(jié)的記錄長度和一個 2 字節(jié)的名稱長度，然后是實際的文件名。路徑中的每個文件或者目錄名限制為 255 字節(jié)，目錄項的長度向上取整到下一個 4 字節(jié)邊界。

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

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

符號鏈接

傳統(tǒng)的文件系統(tǒng)允許一個文件擁有多個名稱，使用link()系統(tǒng)調用和硬鏈接機制。硬鏈接有數(shù)量限制（一個 short 類型，最多 64K 個名稱）。

硬鏈接（hardlink）可能會意外丟失，例如，通過使用某些編輯器保存一個有硬鏈接的文件時。如果編輯器將文件保存為 filename.new，然后取消鏈接舊的 filename 并將新文件移動到相應位置，那么文件的硬鏈接屬性將會被修改。

硬鏈接（hardlink）是指在文件系統(tǒng)中創(chuàng)建的指向同一文件或目錄的多個文件名。它們與原始文件（或目錄）共享相同的 inode（索引節(jié)點），因此它們實際上是相同的文件，只是具有不同的文件名。硬鏈接允許多個文件名引用同一份數(shù)據(jù)，節(jié)省存儲空間，并且對文件的更改會在所有硬鏈接之間保持同步。

硬鏈接還會多次引用原始文件的 inode，而 inode 是特定于文件系統(tǒng)的， 因此它們不能跨越文件系統(tǒng)。

BSD 引入了一種新的文件類型（l，符號鏈接），并在鏈接文件中放置一個“替換文件名”，用于確定鏈接目標位置。它可以是絕對路徑或相對路徑（相對于符號鏈接文件的位置）。

當嘗試訪問符號鏈接時，系統(tǒng)將在 namei() 函數(shù)中重新解析文件名，使用鏈接中的文件名，從而將 open() 系統(tǒng)調用重定向到鏈接指向的位置。簡單來說，符號鏈接提供了一個文件名的替代方式，當訪問符號鏈接時，實際上是在訪問鏈接的目標文件。

由于重定向發(fā)生在 namei() 中，它可以跨文件系統(tǒng)，因此新的鏈接類型不受單個文件系統(tǒng)的限制。它也不計入任何鏈接計數(shù)限制。

重命名系統(tǒng)調用

BSD 引入了 rename() 系統(tǒng)調用。過去，則需要通過調用 unlink() 和 link() 實現(xiàn)。由于這涉及多個系統(tǒng)調用，該操作不是原子操作：它可能會部分執(zhí)行，并且容易受到惡意干擾。

配額

BSD 引入了文件系統(tǒng)使用配額的概念：這是對用戶或組可以使用的文件數(shù)量和磁盤空間量設置的軟限制 （soft limit）和硬限制（hard limit）。

為了有效地實現(xiàn)它們，需要做如下修改：

• 現(xiàn)在，如果一個用戶想要把自己文件的所有者改為其他用戶，那么他必須擁有特權操作的權限。否則，他就只能創(chuàng)建一個只有自己能訪問的目錄，然后把目錄里的所有文件都發(fā)送給目標用戶。這樣一來，這些文件就會占用另一個用戶的配額，而不是自己的配額。
• 類似地，不再允許將文件的組員身份更改為任意組。只允許設置為該用戶所屬的某個組。
• 最后，新創(chuàng)建的目錄和文件繼承自它們的父目錄，而不是用戶的主要組。這樣，項目目錄中的文件將計入項目的配額，而不是用戶主要組配額。

咨詢式文件鎖

4.2BSD 中已經引入了咨詢式文件鎖。為了實現(xiàn)這種機制，它引入了新的 flock() 系統(tǒng)調用。

• 文件鎖可以是共享的（讀鎖）或獨占的（寫鎖）；
• 它們總是作用于整個文件，而不是字節(jié)范圍；
• 不嘗試檢測死鎖；
• 它們與文件描述符綁定。因此，當進程死亡時，其文件句柄會自動關閉，從而自動釋放所有持有的鎖。這非常健壯，直到 dup() 和 fork() 開始發(fā)揮作用。

后來，POSIX 試圖改進這一點，引入了第二種完全不同的鎖系統(tǒng) fcntl()。它存在一些缺陷，但可以對字節(jié)范圍進行操作，并實現(xiàn)了一些基本的死鎖檢測。

在這類實現(xiàn)了這兩種文件鎖機制的內核中如Linux系統(tǒng)，這兩種鎖機制互不兼容，也不知道對方的存在。

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

總體表現(xiàn)

在論文中，作者指出了以下優(yōu)點：

• Ls 和ls -l 命令的速度很快，因為單個目錄中文件的 inode 位于同一個柱面組內。因此，讀取和列出目錄時，尋道次數(shù)非常少，尋道距離也很短（除了子目錄，它們通常要保證彼此的距離很遠）。測試發(fā)現(xiàn)，當檢索一個沒有包含子目錄的目錄時，速度提高了8倍；

• 在傳統(tǒng)文件系統(tǒng)中，理論最大帶寬的利用率僅為3%，而在使用不同的控制器硬件的情況下，這一利用率增加到了22%甚至47%。作者對這些結果感到非常自豪，因為這些結果是在實際的生產系統(tǒng)上產生的。盡管文件的數(shù)量和規(guī)模可能會改變，但文件系統(tǒng)在其生命周期內能夠持續(xù)相對穩(wěn)定的吞吐量。

這些改進解決了主要的需求，即提高吞吐量和穩(wěn)定的布局，使性能不會隨時間降低。

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

雖然 Linux 中并沒有 BSD 代碼，但 Ext2 文件系統(tǒng)基本上是對 BSD FFS 的重新實現(xiàn)。

無論是 BSD FFS 還是 Linux ext2，它們仍然是非日志文件系統(tǒng)，在發(fā)生崩潰后需要進行文件系統(tǒng)檢查。它們在處理具有許多條目的目錄方面也表現(xiàn)不佳，在處理深層次目錄結構時稍好一些。為了跟上不斷增長的存儲容量，BSD FFS 和 Linux ext2 這兩個文件系統(tǒng)需要進行額外的改進和優(yōu)化，以便能夠更好地支持處理大容量存儲介質和大型文件系統(tǒng)。

此外，仍然存在其他一些不太明顯的限制：文件系統(tǒng)代碼中的幾個位置受到鎖的保護，使得在具有高并發(fā)性的系統(tǒng)上擴展某些操作變得困難。

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

未完待續(xù)。

如有幫助的話歡迎關注我們項目?Juicedata/JuiceFS?喲！ (0?0?)文章來源地址http://www.zghlxwxcb.cn/news/detail-475465.html

到了這里，關于文件系統(tǒng)考古2：1984 - BSD Fast Filing System的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！