• 1. 文件系统
  • 1.1 文件系统的基本组成
  • 1.2 数据块
  • 1.3 虚拟文件系统
  • 1.4 文件的使用
  • 1.5 文件的存储
    • 1.5.1 连续空间存放方式
    • 1.5.2 非连续空间存放方式
      • 1.5.2.1 链表方式
      • 1.5.2.2 索引方式
    • 1.5.3 Unix 文件的实现方式
  • 1.6 空闲空间管理
    • 1.6.1 空闲表法
    • 1.6.2 空闲链表法
    • 1.6.3 位图法
  • 1.7 文件系统的结构
  • 1.8 目录的存储
  • 1.9 软链接和硬链接
  • 1.10 文件 I/O
    • 1.10.1 缓冲与非缓冲 I/O
    • 1.10.2 直接与非直接 I/O
    • 1.10.3 阻塞与非阻塞 I/O VS 同步与异步 I/O
      • 1.10.3.1 同步 I/O
        • 1.10.3.1.1 阻塞 I/O
        • 1.10.3.1.2 非阻塞 I/O
        • 1.10.3.1.3 基于非阻塞 I/O 的多路复用I/O 多路复用
      • 1.10.3.2 异步 I/O

1. 文件系统

1.1 文件系统的基本组成

文件系统的基本数据单位是文件，它的目的是对磁盘上的文件进行组织管理，那组织的方式不同，就会形成不同的文件系统。

Linux 文件系统会为每个文件分配两个数据结构：

• 索引节点（index node）：用来记录文件的元信息。比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等。索引节点是文件的唯一标识，索引节点会存储在磁盘中，也会占用磁盘空间。
• 目录项（directory dentry）：用来记录文件的名字、索引节点指针以及与其它目录项的层级关联关系。多个目录项关联起来就会形成目录结构。目录项是由内核维护的一个数据结构，不存放在磁盘，而是缓存在内存（dentry cache）。

目录项和索引节点的关系是多对一，也就是说，一个文件可以有多个别名。比如，硬链接的实现就是多个目录项中的索引节点指向同一个文件。

Note

目录也是文件，也是用索引节点唯一标识，和普通文件不同的是，普通文件在磁盘里面保存的是文件数据，而目录文件在磁盘里面保存子目录或文件。

如果查询目录和文件频繁从磁盘读，效率会很低，所以内核会把已经读过的目录和文件用目录项这个数据结构缓存在内存，下次再次读到相同的目录时，只需从内存读就可以，大大提高了文件系统的效率。

1.2 数据块

磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小。

文件系统把多个扇区组成了一个逻辑块，每次读写的最小单位就是逻辑块（数据块），Linux 中的逻辑块大小为 4KB，也就是一次性读写 8 个扇区，提高了磁盘的读写的效率。

磁盘进行格式化的时候，会被分成三个存储区域：

• 超级块，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。当文件系统挂载时进入内存
• 索引节点区，用来存储索引节点。当文件被访问时进入内存
• 数据块区，用来存储文件或目录数据。

1.3 虚拟文件系统

文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了虚拟文件系统（Virtual File System，VFS）。

VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样程序员不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。

Linux 系统中，根据存储位置的不同，可以把文件系统分为三类：

• 磁盘的文件系统：直接把数据存储到磁盘中。比如 ext2/3/4、xfs 等
• 内存的文件系统：这里文件的数据存储在内存中，占用内存空间。比如 /proc、sys 等，读写这类数据实际上就行读写内核中的相关数据
• 网络的文件系统：用来访问其它计算机主机数据的文件系统。比如 nfs、smb 等

文件系统首先要先挂载到某个目录才可以正常使用，比如 Linux 系统在启动时，会把文件系统挂载到根目录。

1.4 文件的使用

打开了一个文件后，操作系统会跟踪进程打开的所有文件，就是操作系统为每个进程维护一个打开文件表，文件表里的每一项代表文件描述符，所以说文件描述符是打开文件的标识。

操作系统在打开文件表中维护着打开文件的状态和信息：

• 文件指针：系统跟踪上次读写位置作为当前文件位置指针，这种指针对打开文件的某个进程来说是唯一的；
• 文件地址：绝大多数文件操作都要求系统修改文件数据，该信息保存在内存中，以免每个操作都从磁盘中读取；
• 文件计数器：文件关闭时，操作系统必须重用其打开文件表条目，否则表内空间不够用。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件，该计数器跟踪打开和关闭的数量，当该计数为 0 时，系统关闭文件，删除该条目。
• 访问权限：每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等），该信息保存在进程的打开文件表中，以便操作系统能允许或拒绝之后的 I/O 请求；

读文件和写文件的过程：

• 当用户进程从文件读取 1 个字节大小的数据时，文件系统则需要获取字节所在的数据块，再返回数据块对应的用户进程所需的数据部分。
• 当用户进程把 1 个字节大小的数据写进文件时，文件系统则找到需要写入数据的数据块的位置，然后修改数据块中对应的部分，最后再把数据块写回磁盘。

所以说，文件系统的基本操作单位是数据块。

1.5 文件的存储

数据在磁盘上的存放方式，就像程序在内存中存放的方式那样，有以下两种：

• 连续空间存放方式
• 非连续空间存放方式

其中，非连续空间存放方式又可以分为链表方式和索引方式。

1.5.1 连续空间存放方式

文件存放在磁盘连续的物理空间中。这种模式下，文件的数据都是紧密相连。读写效率很高。

使用连续存放的方式有一个前提，必须先知道一个文件的大小，这样文件系统才会根据文件的大小在磁盘上找到一块连续的空间分配给文件。

所以，文件头里需要指定起始块的位置和长度，有了这两个信息就可以很好的表示文件存放方式是一块连续的磁盘空间。

缺陷：磁盘空间碎片和文件长度不易扩展。

当然了，我们可以通过将现有文件进行挪动来腾出空间以容纳新的文件，但是这个在磁盘挪动文件是非常耗时，所以这种方式不太现实。

同理，文件长度扩展不方便，例如上图中的文件 A 要想扩大一下，需要更多的磁盘空间，唯一的办法就只能是挪动的方式。

1.5.2 非连续空间存放方式

1.5.2.1 链表方式

链表的方式存放是离散的，不用连续的，于是就可以消除磁盘碎片，可大大提高磁盘空间的利用率，同时文件的长度可以动态扩展。根据实现的方式的不同，链表可分为隐式链表和显式链接两种形式。

隐式链表

实现的方式是文件头要包含「第一块」和「最后一块」的位置，并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置，这样一个数据块连着一个数据块，从链头开始就可以顺着指针找到所有的数据块，所以存放的方式可以是不连续的。

缺点在于无法直接访问数据块，只能通过指针顺序访问文件，以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

显式链接

它指把用于链接文件各数据块的指针，显式地存放在内存的一张链接表中，该表在整个磁盘仅设置一张，每个表项中存放链接指针，指向下一个数据块号。

例：

文件 A 依次使用了磁盘块 4、7、2、10 和 12，文件 B 依次使用了磁盘块 6、3、11 和 14。利用下图中的表，可以从第 4 块开始，顺着链走到最后，找到文件 A 的全部磁盘块。同样，从第 6 块开始，顺着链走到最后，也能够找出文件 B 的全部磁盘块。最后，这两个链都以一个不属于有效磁盘编号的特殊标记（如 -1）结束。内存中的这样一个表格称为文件分配表（File Allocation Table，FAT）。

由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系，它的主要的缺点是不适用于大磁盘。

1.5.2.2 索引方式

索引的实现是为每个文件创建一个索引数据块，里面存放的是指向文件数据块的指针列表。

另外，文件头需要包含指向「索引数据块」的指针，这样就可以通过文件头知道索引数据块的位置，再通过索引数据块里的索引信息找到对应的数据块。

创建文件时，索引块的所有指针都设为空。当首次写入第 i 块时，先从空闲空间中取得一个块，再将其地址写到索引块的第 i 个条目。

索引的方式优点在于：

• 文件的创建、增大、缩小很方便；
• 不会有碎片的问题；
• 支持顺序读写和随机读写；

由于索引数据也是存放在磁盘块的，如果文件很小，明明只需一块就可以存放的下，但还是需要额外分配一块来存放索引数据，所以缺陷之一就是存储索引带来的开销。

如果文件很大，大到一个索引数据块放不下索引信息，此时可以通过组合的方式，来处理大文件的存放。

链式索引块

链式索引块就是链表 + 索引，它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针。这种方式也会出现前面提到的链表方式的问题，万一某个指针损坏了，后面的数据也就会无法读取了。

多级索引块

多级索引块就是索引 + 索引，实现方式是通过一个索引块来存放多个索引数据块。

1.5.3 Unix 文件的实现方式

早期 Unix 文件系统是组合了前面的文件存放方式的优点，如下图：

根据文件的大小，存放的方式会有所变化：

• 如果存放文件所需的数据块小于 10 块，则采用直接查找的方式；
• 如果存放文件所需的数据块超过 10 块，则采用一级间接索引方式；
• 如果前面两种方式都不够存放大文件，则采用二级间接索引方式；
• 如果二级间接索引也不够存放大文件，这采用三级间接索引方式；

那么，文件头（Inode）就需要包含 13 个指针：

• 10 个指向数据块的指针；
• 第 11 个指向索引块的指针；
• 第 12 个指向二级索引块的指针；
• 第 13 个指向三级索引块的指针；

所以，这种方式能很灵活地支持小文件和大文件的存放：

• 对于小文件使用直接查找的方式可减少索引数据块的开销；
• 对于大文件则以多级索引的方式来支持，所以大文件在访问数据块时需要大量查询；

这个方案就用在了 Linux Ext 2/3 文件系统里，虽然解决大文件的存储，但是对于大文件的访问，需要大量的查询，效率比较低。

为了解决这个问题，Ext 4 做了一定的改变，具体怎么解决的，TODO 哈哈。

1.6 空闲空间管理

前面说到的文件的存储是针对已经被占用的数据块组织和管理。本节说下针对磁盘的空闲空间的管理机制：

• 空闲表法
• 空闲链表法
• 位图法

1.6.1 空闲表法

空闲表法就是为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，注意，这个方式是连续分配的。

当请求分配磁盘空间时，系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域为止。当用户撤销一个文件时，系统回收文件空间。这时，也需顺序扫描空闲表，寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

这种方法仅当有少量的空闲区时才有较好的效果。因为，如果存储空间中有着大量的小的空闲区，则空闲表变得很大，这样查询效率会很低。另外，这种分配技术适用于建立连续文件。

1.6.2 空闲链表法

空闲链表法，每一个空闲块里有一个指针指向下一个空闲块。

当创建文件需要一块或几块时，就从链头上依次取下一块或几块。反之，当回收空间时，把这些空闲块依次接到链头上。

这种技术只要在主存中保存一个指针，令它指向第一个空闲块。其特点是简单，但不能随机访问，工作效率低，因为每当在链上增加或移动空闲块时需要做很多 I/O 操作，同时数据块的指针消耗了一定的存储空间。

空闲表法和空闲链表法都不适合用于大型文件系统，因为这会使空闲表或空闲链表太大。

1.6.3 位图法

位图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。

当值为 0 时，表示对应的盘块空闲，值为 1 时，表示对应的盘块已分配。它形式如下：

1111110011111110001110110111111100111 ...

在 Linux 文件系统就采用了位图的方式来管理空闲空间，不仅用于数据空闲块的管理，还用于 inode 空闲块的管理，因为 inode 也是存储在磁盘的，自然也要有对其管理。

1.7 文件系统的结构

数据块的位图是放在磁盘块里的，假设是放在一个块里，一个块 4K，每位表示一个数据块，共可以表示 4 * 1024 * 8 = 2^15 个空闲块，由于 1 个数据块是 4K 大小，那么最大可以表示的空间为 2^15 * 4 * 1024 = 2^27 个 byte，也就是 128M。

也就是说按照上面的结构，如果采用「一个块的位图 + 一系列的块」，外加「一个块的 inode 的位图 + 一系列的 inode 的结构」能表示的最大空间也就 128M。

在 Linux 文件系统，把这个结构称为一个块组，那么有 N 多的块组，就能够表示 N 大的文件。

下图给出了 Linux Ext2 整个文件系统的结构和块组的内容，文件系统都由大量块组组成，在硬盘上相继排布：

最前面的第一个块是引导块，在系统启动时用于启用引导，接着后面就是一个一个连续的块组了，块组的内容如下：

• 超级块，包含的是文件系统的重要信息，比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。
• 块组描述符，包含文件系统中各个块组的状态，比如块组中空闲块和 inode 的数目等，每个块组都包含了文件系统中「所有块组的组描述符信息」。
• 数据位图和 inode 位图， 用于表示对应的数据块或 inode 是空闲的，还是被使用中。存放的是本块组内的位图信息。
• inode 列表，包含了块组中所有的 inode，inode 用于保存文件系统中与各个文件和目录相关的所有元数据。
• 数据块，包含文件的有用数据。

每个块组里有很多重复的信息，比如超级块和块组描述符表，这两个都是全局信息，而且非常的重要，这么做是有两个原因：

• 如果系统崩溃破坏了超级块或块组描述符，有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本，该信息是可能恢复的。
• 通过使文件和管理数据尽可能接近，减少了磁头寻道和旋转，这可以提高文件系统的性能。

不过，Ext2 的后续版本采用了稀疏技术。该做法是，超级块和块组描述符表不再存储到文件系统的每个块组中，而是只写入到块组 0、块组 1 和其他 ID 可以表示为 3、5、7 的幂的块组中。

1.8 目录的存储

普通文件的块里面保存的是文件数据，而目录文件的块里面保存的是目录里面一项一项的文件信息。

在目录文件的块中，最简单的保存格式就是列表，就是一项一项地将目录下的文件信息（如文件名、文件 inode、文件类型等）列在表里。通过 inode，就可以找到真正的文件。

如果一个目录有超级多的文件，我们要想在这个目录下找文件，按照列表一项一项的找，效率就不高了。

于是，保存目录的格式改成哈希表，对文件名进行哈希计算，把哈希值保存起来，如果要获取所有文件，直接遍历就好了；如果我们要查找一个目录下面的文件名，可以通过名称取哈希。如果哈希能够匹配上，就说明这个文件的信息在相应的块里面。

Linux 系统的 ext 文件系统就是采用了哈希表，来保存目录的内容，这种方法的优点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免哈希冲突。

目录查询是通过在磁盘上反复搜索完成，需要不断地进行 I/O 操作，开销较大。所以，为了减少 I/O 操作，把当前使用的文件目录缓存在内存，以后要使用该文件时只要在内存中操作，从而降低了磁盘操作次数，提高了文件系统的访问速度。

1.9 软链接和硬链接

硬链接是多个目录项中的「索引节点」指向一个文件，也就是指向同一个 inode，但是 inode 是不可能跨越文件系统的，每个文件系统都有各自的 inode 数据结构和列表，所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。

软链接相当于重新创建一个文件，这个文件有独立的 inode，但是这个文件的内容是另外一个文件的路径，所以访问软链接的时候，实际上相当于访问到了另外一个文件，所以软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已。

1.10 文件 I/O

1.10.1 缓冲与非缓冲 I/O

文件操作的标准库可以实现数据的缓存，那么根据是否利用标准库缓冲，可以把文件 I/O 分为缓冲 I/O 和非缓冲 I/O：

• 缓冲 I/O，利用的是标准库的缓存实现文件的加速访问，而标准库再通过系统调用访问文件。
• 非缓冲 I/O，直接通过系统调用访问文件，不经过标准库缓存。

这里所说的「缓冲」特指标准库内部实现的缓冲。

1.10.2 直接与非直接 I/O

磁盘 I/O 是非常慢的，所以 Linux 内核为了减少磁盘 I/O 次数，在系统调用后，会把用户数据拷贝到内核中缓存起来，这个内核缓存空间也就是「页缓存」，只有当缓存满足某些条件的时候，才发起磁盘 I/O 的请求。

那么，根据是否利用操作系统的缓存，可以把文件 I/O 分为直接 I/O 与非直接 I/O：

• 直接 I/O，不会发生内核缓存和用户程序之间数据复制，而是直接经过文件系统访问磁盘。
• 非直接 I/O，读操作时，数据从内核缓存中拷贝给用户程序，写操作时，数据从用户程序拷贝给内核缓存，再由内核决定什么时候写入数据到磁盘。

如果你在使用文件操作类的系统调用函数时，指定了 O_DIRECT 标志，则表示使用直接 I/O。如果没有设置过，默认使用的是非直接 I/O。

在使用了非直接 I/O 的情况下，以下几种场景会触发内核缓存的数据写入磁盘：

• 在调用 write 的最后，当发现内核缓存的数据太多的时候，内核会把数据写到磁盘上；
• 用户主动调用 sync，内核缓存会刷到磁盘上；
• 当内存十分紧张，无法再分配页面时，也会把内核缓存的数据刷到磁盘上；
• 内核缓存的数据的缓存时间超过某个时间时，也会把数据刷到磁盘上；

1.10.3 阻塞与非阻塞 I/O VS 同步与异步 I/O

1.10.3.1 同步 I/O

1.10.3.1.1 阻塞 I/O

阻塞I/O（bio），当用户程序执行read时，现场会被阻塞，一直等到内核把数据准备好并且把数据从内核缓冲区拷贝到应用程序的缓冲区中，当拷贝完成，read才会返回。

Note

阻塞等待的是内核数据准备好和数据从内核态拷贝到用户态这两个过程。

1.10.3.1.2 非阻塞 I/O

非阻塞 I/O，非阻塞的 read 请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷贝到应用程序缓冲区，read 调用才可以获取到结果。过程如下图：

Note

这里最后一次 read 调用，获取数据的过程，是一个同步的过程，是需要等待的过程。这里的同步指的是内核态的数据拷贝到用户程序的缓存区这个过程。

1.10.3.1.3 基于非阻塞 I/O 的多路复用I/O 多路复用

应用程序在使用非阻塞I/O时。每次轮询内核的 I/O 是否准备好，因为轮询的过程中，应用程序啥也做不了，只是在循环。

为了解决这种傻乎乎轮询方式，于是 I/O 多路复用（nio）技术就出来了，如 select、poll，它是通过 I/O 事件分发，当内核数据准备好时，再以事件通知应用程序进行操作。

这个做法大大改善了 CPU 的利用率，因为当调用了 I/O 多路复用接口，如果没有事件发生，那么当前线程就会发生阻塞，这时 CPU 会切换其他线程执行任务，等内核发现有事件到来的时候，会唤醒阻塞在 I/O 多路复用接口的线程，然后用户可以进行后续的事件处理。

I/O 多路复用接口最大的优势在于，用户可以在一个线程内同时处理多个 socket 的 IO 请求（参见：I/O 多路复用：select/poll/epoll）。用户可以注册多个 socket，然后不断地调用 I/O 多路复用接口读取被激活的 socket，即可达到在同一个线程内同时处理多个 IO 请求的目的。而在同步阻塞模型中，必须通过多线程的方式才能达到这个目的。

Note

read 获取数据的过程（数据从内核态拷贝到用户态的过程），也是一个同步的过程，需要等待。

1.10.3.2 异步 I/O

实际上，无论是阻塞 I/O、非阻塞 I/O，还是基于非阻塞 I/O 的多路复用都是同步调用。因为它们在 read 调用时，内核将数据从内核空间拷贝到应用程序空间，过程都是需要等待的，也就是说这个过程是同步的，如果内核实现的拷贝效率不高，read 调用就会在这个同步过程中等待比较长的时间。

而真正的异步 I/O（aio） 是「内核数据准备好」和「数据从内核态拷贝到用户态」这两个过程都不用等待。

当我们发起 aio_read 之后，就立即返回，内核自动将数据从内核空间拷贝到应用程序空间，这个拷贝过程同样是异步的，内核自动完成的，和前面的同步操作不一样，应用程序并不需要主动发起拷贝动作。