文件系统原理

文件和目录是我们在使用计算机时的一个重要概念。很多人都在用微软的Word软件编辑文档、写论文。这里的Word软件是一个用户软件，我们所写的论文在操作系统中就是以文件的形式存在的， 它被放在了一个目录下。有时为了组织方便，我们会把一组具有某种共同属性的文件整理到一个目录下，在目录中有时也会建立子目录，当我们从根目录开始，逐级打开每个子目录， 直到找到我们感兴趣的文件时，就形成了一条路径，只要文件存在并且存储路径没有变化，通过这条路径我们总能够找到这个文件。

我们知道物理上，这些文件一定会存放在硬盘、U盘、SD卡等存储设备上。至于说存放在设备的那个地方，我们是不清楚的。很多人甚至都不清楚各种存储设备如何存放文件的。 文件系统(File System, FS)的存在就是为了解决这种尴尬的，它可以理解为操作系统对存储信息的一种抽象。使得用户程序可以在不清楚存储设备的细节的情况下，读写存储数据。

在本文中，我们将对文件系统的功能和实现做简单的介绍。先从用户的角度看下文件系统中文件和目录两个概念，再从实现的角度看下具体的存储方式。 文件系统的设计和使用是有着很高深的学问的，我们会在以后的文章中逐渐深入。

1. FS之文件

文件提供了一种存储信息到设备上，并在以后可以将其重新读入系统的抽象机制。它使得用户不必关系这些信息是如何存储的，也不必关系存储介质是如何工作的， 通常有三个要素：文件名、数据、属性。用户以文件名的形式查找和访问某个文件，同一时间可能有多个用户进程通过文件名访问同一个文件。 文件中的存储的数据才是用户或者程序需要使用和处理的对象，而文件的属性则描述了文件的各种状态，比如创建日期、修改日期、访问权限等等。

文件的命名方式在不同的操作系统中是不一样的。比如说早期微软的DOS系统中文件的命名是不区分大小写的，也就是说文件"FILE","file","File"等等它们都是一样的。 在大多数操作系统中，都会把文件名分为文件名和后缀两个部分，中间用'.'分割。通常应用程序会根据文件的后缀名进行一些初始化或者处理工作，比如说我们用C语言码代码时， 常常会把C语言源文件命名为"*.c"的形式。再比如在Windows系统中双击后缀为"*.docx"的文件，通常都会打开Word进行处理。在很多用户程序中，文件名的后缀是什么并不重要， 它更多的是给用户提供信息。

关于文件中存储的数据内容是什么，又是如何组织的，这点是由具体的程序决定的，操作系统或者文件系统都不会做规定的。 一般根据存储形式可以把文件分为二进制文件和文本文件，文本文件比较好理解就是用记事本打开能够看到文字的文件，其余的在我看来都是二进制文件需要用特定的用户软件才能打开， 用记事本打开看到的就是乱码。比如说，我们写程序时的"*.c"文件就是一种文本文件，"*.docx"文件则是一种二进制文件需要用Word或者类似功能的软件才能够打开。

文件的属性记录了文件的一些额外的数据，有人也把这些属性称为文件的元数据(metadata)。这些数据与存储的数据不同，前者更多的是面向操作系统和用户的，而后者则是应用程序的处理对象。 在Linux系统中，每个文件都有一个所有者(Owner)，组(Group)，针对Owner, Group, Others，每个文件都有三个访问属性(读、写、运行)， 这些属性是操作系统判定一个用户或者一个程序是否有权限打开某个文件的依据。很多时候，操作系统也会存储一些时间信息，用于排序等操作。

在Modern Operating Systems中，提到操作系统对文件通常有11种操作：

2. FS之目录

为了方便组织文件，文件系统一般都会用"目录(directory)"或者说是"文件夹(folder)"来实现这一功能。下面我们把它称为目录系统(Directory System)。

最简单的目录系统就是只有一个目录，所有的文件都在这一个目录里，称该目录为根目录(root directory)。 早期的计算机一般都是用的这种目录系统，它可以简化软件的设计。

把所有文件放在一个目录下，查找起来就会很麻烦，所以现在的操作系统中几乎没有使用这种结构的。为了方便用户查找和使用，通常会对文件分组，把有关联的一些文件放在一起。 比如说我们可以有一堆文件全是文本文件、有一堆文件全是视频等等，把它们分别放在不同的目录下。很自然的，用户会期望在一个目录下不仅有文件，也可以有子目录， 这样就产生了层次化的目录系统(Hierarchy Directory System)，或者说是树型目录系统。

图1 树型目录系统

如图1所示为一个树型目录系统的示意图，其中方框为目录，圆形为文件。在最顶端有一个根目录，其中有三个目录A,B,C，每个目录中有文件和目录， 就像一棵树一样，从根节点开始不断向下延伸，我们称之为目录树。目前常见的操作系统都是这种结构，借助控制终端或者图形化界面，用户可以根据自己的需要方便的组织文件的存放形式。

把文件以目录树的形式存放后，我们可以从根目录开始，依次经过各个子目录直到找到目标文件为止，所经历的各个目录称为一条指向目标文件的绝对路径(absolute path)。 比如在Linux系统中/home/user/Documents/hehe.txt表示的是，根目录下有一个叫home的子目录，它有一个user的子目录，其中的子目录Documents下有一个文件hehe.txt。 最开始的"/"表示从根目录开始查找，之后的"/"都是目录之间的分隔符。

也可以从任意一个目录开始，通过向上找到与目标文件一个共同的目录，再通过该目录依次向下找到目标文件，这样的路径称为相对路径(relative path)。 比如在Linux系统中../Documents/hehe.txt表示的是，在上一级目录下有一个Documents子目录，其中有一个叫hehe.txt的文件。其中".."表示上一级目录。

在Modern Operating Systems中，提到对目录通常有8种操作：

3. FS之实现

前两节我们是从用户的角度看文件系统都有什么功能，下面我们将从开发者的角度来看如何实现一个文件系统。 对于实现而言，关心的更多的是文件和目录是如何存储在磁盘上的，磁盘空间是如何组织的，以及如何高效稳定的实现各种用户接口。

3.1 磁盘的组织

在我理解，文件系统实际上及时对磁盘的组织。在很多资料中所谓的磁盘指的是硬盘，我们这里则是指一般常见的各种存储介质，比如U盘、SD卡等等。 它们在机械和电气结构上可能各不相同，但在软件逻辑上来看都可以理解为一列按顺序摆放的格子。比如机械硬盘上的扇区，SD卡上的块(block)都是这个概念， 以后我们将之称为块。

图2 一个可能的磁盘组织方式

图2是一个可能的磁盘组织方式。具体不知道什么历史原因，硬盘的第0个扇区一般都是一个称为MBR(Master Boot Record)的扇区，用于启动计算机。 在MBR的最后有一个分区表，其中记录了硬盘的分区信息。计算机启动时，由BIOS读取MBR并根据分区表信息，找到某个分区下的启动块(boot block)， 加载boot loader，由boot loader把操作系统镜像读入内存，最后跳转进入操作系统。

一般而言，每个分区的第一个block都被保留做启动块(boot block)。接着可以是一个超级块(superblock)，用于描述文件系统的各种参数，通常会在计算机启动或者插入磁盘时读入到内存中。 然后可能是若干个描述磁盘剩余空间的块，它通过位图(bitmap)或者指针链表(list of pointers)的形式记录磁盘分区的剩余空间。其后可能是若干个记录i-nodes的块， i-nodes似乎是UNIX系统中的概念，对应每个文件都有一个i-node与之对应，它记录了文件的各种属性。在其它系统中，i-nodes可能有别的名称，但实现的功能类似。 最后就是由根目录、目录和文件构成的文件树，有些系统中根目录会专门由若干个数据块来实现。

3.2 文件的存放形式

对于文件系统而言，最重要的问题就是文件的存储。打开文件时需要直到目标文件的数据存放在磁盘上的哪个数据块(block)上，创建文件时需要直到哪个数据块是空闲的。 对文件进行读写操作时需要了解磁盘中是否有足够的空间存放文件。对于这些问题的解决，不同的文件系统实现方式是不同的。

顺序存放

顺序存放应该是最简单的一种文件存放方式，如图3所示，各个文件一个接一个的顺次存放在磁盘上。因为有类似i-nodes的数据块记录文件信息，还有文件树记录文件的存储关系， 我们可以直接访问到各个文件。

图3 文件的顺序存放

这种简单的文件存放形式，有一个极大的弊端就是，随着文件的读写、创建和删除操作的进行，磁盘上的可用空间会逐渐的碎片化。碎片化是对磁盘的一种极大浪费， 因而在硬盘、U盘这类需要频繁增删改文件的介质上几乎不会见到这种存储结构。但是在CD/DVD这样的介质上，因为文件都是只读的，写入时每个文件的大小都是已知的， 所以在这类介质上广泛使用的都是这种简单的方式。

链表形式

如图4所示是一个链表形式的文件存储结构。文件依然是存放在若干个不同的块(block)上，与顺序存储不同的是这些数据块可能不是连续的，在每个数据块中都有记录有下一个数据块的物理地址。 这就构成了一个链表的结构，从第一个数据块开始可以依次遍历到最后一个数据块。

图4 文件的链式存储

相比于顺序存储结构而言，这种存储形式可以充分的利用磁盘空间，对文件的增删改操作并不会带来碎片化，因为它不要求同一个文件的所有数据块必须是连续的。 但这种链表形式对于文件的随机访问是很不方便的，比如我们想读取第\(n\)个块中的数据时，需要先访问之前\(n-1\)个数据块。

带有查找表的链式存储

为了提高对文件随机访问的速度，人们又提出了一种查找表称为FAT(File Allocation Table)的东西。图5.a中描述了两个文件的查找表，文件A使用了编号为7、2、10、12的共四个数据块， 文件B使用了编号为6、3、11、14四个数据块。格子中的-1标识着文件的结束。

图5.a 文件查找表示意图	图5.b 文件查找表示意图

在磁盘上需要专门有若干个数据块存放这个查找表，挂载磁盘时还需要在内存中开辟一段空间把这一查找表读进来。但是如果磁盘空间很大，数据块很多的话，维护这一个查找表也是很费空间的。 因此，在UNIX类系统中引入了i-nodes这一概念，它为每个文件记录了属性和使用数据块表，如图5.b所示。对于这种结构我们大可以在打开文件时将i-node读进内存中，这样就可以减少对内存的占用。

3.3 目录的实现

我们在访问一个文件之前，需要先打开该文件。目录系统根据用户提供的路径找到文件的目录入口(directory entry)。 目录入口为我们提供了关于该文件的属性、数据存放地址等信息。对于不同的文件存放形式数据存放地址的记录有所不同：对于顺序存放的系统，记录的是所有数据块编号； 对于链表形式的系统，只需要记录第一个数据块的编号就可以了；那些实现了i-nodes的系统则是i-node的编号。

目录系统本质上是把用户提供的路径映射到物理介质的数据块上的，它需要记录到两个方面的内容：数据和属性。数据就是我们之前讨论的文件存储，而属性则是对文件的一些特性的描述， 例如创建日期、所有者等等。据Modern Operating Systems介绍，关于属性的存储， Windows和UNIX形成了两种典型的方法。在Window中文件的属性通常都是在目录中存储的，也就说对于每个文件都有一个大的数据结构存放对应的各种属性。 在UNIX类的操作系统中记录的则是i-nodes的编号，在i-nodes中记录了文件的各种属性。

而关于目录中记录的这些信息，我们完全可以将其看成一种特殊的文件进行存储。

4. 总结

在本文中，我们先从用户的角度看了文件系统中涉及到的文件和目录两个主要对象。文件是对存储信息的一种抽象，我们可以通过文件名和路径对文件进行增删改操作。 目录则是为了方便用户对文件进行归类而设计的，通常它都是一种树型的结构。

接着我们简单了解了文件系统的一些实现细节。一般存储介质在逻辑上都可以看做是一系列顺序摆放的块，文件的存储通常都是以块为单位进行存储的。我们提及了文件存储的三种方式：(1) 在一些只读的存储介质上，通常采用的是顺序存储的方式；(2) 为了解决频繁增删改文件操作造成的存储空间碎片化的问题，硬盘、U盘等设备上采用的则是链式存储的方式；(3) 为了提高对链式存储随机访问的效率，人们又引入了FAT和i-nodes构建了带有查找表的链式存储系统。

对于目录系统的实现，可以将其看做是一种特殊的文件在介质上存储。目录所包含的信息在Windows和UNIX两类操作系统中的主要分歧在于文件属性的存放形式，Windows中是直接存放在目录入口中的， UNIX则是存放在i-nodes中的。

关于文件系统还有很多内容需要探索，我们会在以后的文章中逐渐深入。