明天持续与大家分享系列文章《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）。它将硬盘分成柱面组，相邻的磁道属于同一个柱面组。
tu
当硬盘旋转时，不同的磁头进入盘片堆中，就像一个梳子。每个磁头在磁盘上标记一个磁道，控制器硬件将该磁道细分为物理磁盘块。所有磁头标记的磁道组成一个柱面。柱面组是一组间断的柱面。（图像起源：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✿)