文件系统

文件系统概览

什么是文件系统？

磁盘是计算机中用于持久存储数据的主要设备。这些数据多种多样，包括：

• 程序数据：例如可执行文件、动态链接库、应用程序运行时产生的数据。
• 用户数据：例如用户创建的文档、下载的文件、截图、照片等。
• 系统数据：例如操作系统的配置文件（如 Linux 下的 /etc 目录中的文件）。

早期（约 1950 年代），应用程序可能直接通过驱动程序访问存储设备。这种方式存在巨大风险：

• 程序 Bug 导致数据损坏：应用程序中的错误（不可避免）可能轻易破坏整块磁盘的数据。
• 系统崩溃：关键数据（包括操作系统本身）的损坏可能导致整个系统无法运行。

为了解决这些问题，引入了文件系统的概念。文件系统在应用程序和原始存储设备之间提供了一个抽象层。

文件系统

文件系统（File System）是操作系统中用于管理持久性存储设备（如磁盘、SSD）上的数据的一种机制。它提供了对数据的组织、存储、检索、命名、共享和保护等功能，为用户和应用程序提供了一个结构化、易用的接口来访问存储设备上的数据。

文件系统的核心目标是：

1. 提供合理的 API，使得多个应用程序能够方便、安全地共享数据。
2. 提供隔离机制，限制恶意程序或出错程序可能造成的损害范围，保护数据的完整性和系统的稳定性。

可以将文件系统与其他操作系统中的抽象概念进行类比：

• 线程抽象：将一个物理 CPU 抽象为多个虚拟 CPU，在时间上共享。
• 虚拟存储：将一份物理内存抽象并划分给多个进程，每个进程拥有独立的虚拟地址空间。
• 文件系统：将一个物理磁盘（或存储设备）抽象为多个虚拟磁盘，供不同用户和程序使用。

文件系统在系统中的位置

文件系统作为操作系统的一部分，在整个系统架构中扮演着承上启下的角色：

• 用户程序通过系统调用（如 open, read, write）与文件系统交互。
• 操作系统内核中的文件系统模块接收这些请求。
• 文件系统将用户对文件和目录的逻辑操作（如按文件名访问）转换为对磁盘上逻辑块的操作，并将逻辑块映射到物理块。
• 设备驱动程序位于 I/O 控制层，负责管理具体的 I/O 设备，将文件系统对逻辑块的请求转换为对设备物理块的读写指令。
• 硬件执行实际的读写操作。

文件系统的主要职责包括：

• 持久性和命名数据：管理文件和目录。数据会一直存储在系统中，直到被显式删除。用户可以通过文件系统提供的可读标识符（如文件名、路径）来访问数据。
• 访问和保护：提供如打开、读取、写入等操作，并调节不同用户对文件的访问权限。
• 磁盘管理：公平有效地利用磁盘空间，包括为文件分配空间、跟踪空闲空间、以及实现对文件的快速访问。
• 可靠性：确保文件数据不因系统故障（如突然断电）而轻易丢失或损坏。

文件

文件

文件（File）是操作系统创建的逻辑存储单元，用于存储相关信息的集合。它是文件系统中最基本的数据组织单位。

文件的内容可以是多种多样的，例如数据库、音频、视频、网页、程序代码、配置文件等。从用户的角度看，文件是一组有意义的数据集合，其具体类型和结构通常由用户（或创建该文件的应用程序）定义。

文件系统提供了一套机制，使得用户可以在磁盘上存储信息，并在之后方便地读取这些信息。基本的文件操作包括：创建、读取、写入和删除。

文件命名

文件命名是文件系统抽象的一个重要特征。它允许用户：

• 使用人类可读的名称来引用数据，而不是记忆底层的磁盘地址或块号。一个有意义的名称可以代表任意大小的数据集合。
• 有效地组织大量的存储空间。
• 屏蔽信息存储的细节，如数据的低级结构（如何分布在磁盘块上）以及磁盘的实际工作方式。

文件命名规则因操作系统而异，常见差异包括：

• 长度限制：文件名允许的最大字符数。
• 特殊字符：哪些字符不允许出现在文件名中（如 /, \, :, *, ?, ", <, >, | 等）。
• 字母大小写敏感性：例如，File.txt 和 file.txt 在某些系统（如 Linux）中是不同的文件，而在另一些系统（如 Windows，不过 Windows 也能启用大小写敏感）中是相同的文件。

文件扩展名（File Extension），如 .txt, .c, .jpg, .pdf，是文件名的一部分，通常位于主文件名之后，由一个点号分隔。

• 它通常用于指示文件内容的类型。
• 为应用程序或操作系统提供关于如何处理该文件的提示。例如，双击一个 .docx 文件通常会用 Microsoft Word 打开它。
  • 在某些系统中（如 Unix-like 系统），文件扩展名更多的是一种约定，操作系统本身可能并不严格依赖它来确定文件类型，而是通过文件内容（如魔数 magic number）或其他元数据。

文件类型

许多操作系统支持多种类型的文件，以满足不同的需求。在 Unix-like 系统中，常见的文件类型有（ls -l 命令输出的第一个字符通常表示文件类型）：

• 普通文件（-）：包含用户信息或程序数据，如文本文件、二进制可执行文件、图像文件等。
  • ASCII 文件（文本文件）：内容是可读字符。
  • 二进制文件：内容是机器可直接执行的指令或特定格式的非文本数据。
• 目录文件（d）：用于维护文件系统结构的系统文件，它包含了一组其他文件或目录的条目。
• 符号链接文件（l）：也称软链接，它指向另一个文件或目录的路径名。
• 命名管道文件（p）：也称 FIFO (First-In, First-Out)，用于进程间通信，数据以先进先出的方式在管道中流动。
• 块设备文件（b）：代表块设备，如硬盘驱动器、SSD。数据以固定大小的块进行传输。
• 字符设备文件（c）：代表字符设备，如终端、打印机。数据以字符流的方式进行传输。
• 套接字文件（s）：用于网络通信或本地进程间通信的端点。

文件元数据（属性）

除了文件名和实际存储的数据内容外，操作系统还会为每个文件保留一些额外的信息，称为文件元数据（File Metadata）或文件属性。这些信息对于文件的管理和使用至关重要。

常见的文件元数据包括：

• 位置：文件数据在存储设备上的具体位置指针（如指向数据块的指针）。
• 大小：文件的当前大小（字节数），有时也包括最大允许大小。
• 时间戳：
  • 创建时间（Creation time, ctime，在某些系统指 inode change time）
  • 最近访问时间（Last access time, atime）
  • 最近修改时间（Last modification time, mtime）
• 所有者：创建或拥有该文件的用户 ID（UID）。
• 组：文件所属的用户组 ID (GID)。
• 保护信息：定义了哪些用户（所有者、同组用户、其他用户）可以对文件执行哪些操作（读、写、执行）。
• 引用计数：指向该文件元数据的硬链接数量。
• 文件类型：如上所述的普通文件、目录等。

以下表格列举了一些常见的文件属性及其含义：

属性	含义
Protection	谁可以以何种方式访问文件
Password	访问文件所需的密码
Creator	创建文件的用户 ID
Owner	当前文件所有者
Read-only flag	0 表示可读写；1 表示只读
Hidden flag	0 表示正常；1 表示不在列表中显示
System flag	0 表示普通文件；1 表示系统文件
Archive flag	0 表示已备份；1 表示需要备份
ASCII/binary flag	0 表示 ASCII 文件；1 表示二进制文件
Random access flag	0 表示仅顺序访问；1 表示随机访问
Temporary flag	0 表示正常；1 表示进程退出时删除文件
Lock flags	0 表示未锁定；非零表示已锁定
Record length	记录中的字节数
Key position	每条记录中键的偏移量
Key length	键字段中的字节数
Creation time	文件创建的日期和时间
Time of last access	文件最后访问的日期和时间
Time of last change	文件最后更改的日期和时间
Current size	文件中的字节数
Maximum size	文件可能增长到的最大字节数

在 Unix-like 系统中，文件元数据通常存储在一个称为 inode 的数据结构中。每个文件（和目录，因为目录也是一种特殊文件）都有一个对应的 inode。文件系统会在磁盘上维护一个 inode 表，并将活跃的 inode 缓存在内存中以加快访问速度。

inode

inode(Index Node) 是 Unix-like 文件系统中用于存储文件元数据（除文件名外的一切信息）的数据结构。文件名存储在目录文件中，目录条目将文件名映射到 inode 号。

文件访问方式

文件系统支持多种访问文件内容的方式：

• 顺序访问：按顺序从头到尾读取或写入数据。
  • 操作通常是「读取下一个」或「写入下一个」字节/记录。
  • 这是最常见的访问模式，例如复制文件、编译器读写源文件和目标文件。
  • 速度快，因为磁盘可以进行连续读写，可能达到峰值传输速率。
• 随机访问或直接访问：可以不按顺序直接访问文件中的任意数据块。
  • 操作通常包括指定块号或文件内的偏移量，如 read(n)（读取第 n 块）、write(n)（写入第 n 块）、seek(n)（寻址到第 n 块/字节）。
  • 速度相对较慢，因为可能涉及多次磁盘寻道和旋转延迟。

文件的常见 API（系统调用）

操作系统提供了一系列 API（通常以系统调用的形式）供应用程序对文件进行操作：

• open(pathname, flags, mode) 或 create(pathname, mode)：打开（或创建）一个具有给定路径名（目录和文件名）的文件。成功后返回一个文件描述符，并将文件指针（偏移量）设置为文件的开头（或指定位置）。
• read(fd, buf, count)：从文件描述符 fd 指向的已打开文件中读取最多 count 数量的字节到缓冲区 buf 中，并相应移动文件指针。
• write(fd, buf, count)：将缓冲区 buf 中的 count 字节数据写入到文件描述符 fd 指向的已打开文件中，并相应移动文件指针。
• close(fd)：关闭由文件描述符 fd 引用的已打开文件，释放相关资源。
• lseek(fd, offset, whence)：移动文件描述符 fd 关联的文件指针到文件中的某个指定偏移量 offset 处。whence 参数指定了偏移量的基准（如文件开头、当前位置、文件末尾）。
• fsync(fd)：确保所有对文件 fd 的已缓冲的修改（脏数据）立即被推送到磁盘等持久存储设备。

C 语言拷贝文件示例

下面是一个使用上述系统调用在 C 语言中实现文件拷贝功能的简单示例：

#include <sys/types.h> // For types like off_t, size_t
#include <fcntl.h>     // For open, creat, O_RDONLY, file modes
#include <stdlib.h>    // For exit
#include <unistd.h>    // For read, write, close, TRUE
#include <stdio.h>     // For perror

#define BUF_SIZE 4096      // 使用 4096 字节的缓冲区大小
#define OUTPUT_MODE 0700   // 输出文件的保护位（rwx------）

int main(int argc, char *argv[]) {
    int in_fd, out_fd;
    ssize_t rd_count, wt_count; // ssize_t for read/write return values
    char buffer[BUF_SIZE];

    if (argc != 3) {
        fprintf(stderr, "Usage: %s <source_file> <destination_file>\n", argv[0]);
        exit(1); // 语法错误，参数数量不为 3
    }

    /* 打开输入文件并创建输出文件 */
    in_fd = open(argv[1], O_RDONLY); // 打开源文件（只读）
    if (in_fd < 0) {
        perror("Error opening source file");
        exit(2); // 如果无法打开，则退出
    }

    // creat() 等价于 open(pathname, O_WRONLY | O_CREAT | O_TRUNC, mode)
    // O_WRONLY: 只写模式
    // O_CREAT:  如果文件不存在则创建
    // O_TRUNC:  如果文件已存在，则截断为 0 长度
    out_fd = creat(argv[2], OUTPUT_MODE); // 创建目标文件
    if (out_fd < 0) {
        perror("Error creating destination file");
        close(in_fd); // 关闭已打开的输入文件
        exit(3); // 如果无法创建，则退出
    }

    /* 拷贝循环 */
    while (TRUE) {
        rd_count = read(in_fd, buffer, BUF_SIZE); // 读取一块数据
        if (rd_count <= 0) break; // 如果读到文件末尾或出错，则退出循环

        wt_count = write(out_fd, buffer, rd_count); // 写入数据
        if (wt_count <= 0) { // 如果写入出错
            perror("Error writing to destination file");
            close(in_fd);
            close(out_fd);
            exit(4); // wt_count <= 0 是一个错误
        }
    }

    /* 关闭文件 */
    close(in_fd);
    close(out_fd);

    if (rd_count == 0) { // 上次读取没有错误（正常到达文件末尾）
        exit(0);
    } else { // 上次读取发生错误
        perror("Error reading from source file");
        exit(5);
    }
}

文件描述符

文件描述符

文件描述符（File descriptor），有时也称句柄（handle），是操作系统为进程打开的每个文件所分配的一个唯一的非负整数。这个数字由进程私有，用于在该进程中引用这个已打开的文件。

持有文件描述符，进程就可以对对应的文件执行特定操作（如 read, write, close）。使用文件描述符的好处是：

• 效率：避免了每次访问文件时都需要解析文件名（在目录中搜索文件名）和检查权限。这些操作在 open 时完成一次即可。
• 灵活性：一个文件可以被同一个进程或不同进程以不同方式多次打开（例如，一次以只读方式打开，另一次以只写方式打开），每次打开都会获得一个新的文件描述符（通常情况下）。

在 Unix-like 系统中，有一个著名的哲学思想：一切皆文件（Everything is a file）。这意味着许多不同类型的资源，如常规文件、目录、管道、设备（如终端、磁盘）、套接字等，都被抽象为文件，并通过文件描述符进行访问。它们都表现为字节流。

通常，当一个程序从 Shell 运行时，会有三个特殊的文件描述符默认可用：

FD	用途	POSIX 名称	C 标准 I/O 流
0	标准输入（Standard input）	STDIN_FILENO	stdin
1	标准输出（Standard output）	STDOUT_FILENO	stdout
2	标准错误（Standard error）	STDERR_FILENO	stderr

文件偏移

对于进程打开的每个文件，操作系统都会跟踪一个文件偏移量（File Offset），也称为读写指针或当前文件位置。该偏移量决定了下一次 read 或 write 操作将从文件中的哪个字节位置开始。

文件偏移量的更新方式：

• 隐式更新：当进行 N 字节的读取或写入操作成功后，文件偏移量会自动增加 N。
• 显式更新：可以使用 lseek() 系统调用来直接设置文件偏移量到指定位置。

打开文件表

当进程打开一个文件时，操作系统需要在内存中创建并维护一些额外的数据结构，用于存储关于该进程打开文件的信息。这些结构通常组织成「表」的形式。

在 Unix-like 系统中，通常涉及以下三种内核数据结构来描述文件描述符和打开文件之间的关系：

1. 每进程文件描述符表（Per-process File Descriptor Table）：

   • 每个进程都有自己独立的文件描述符表。
   • 这是一个数组，数组的索引就是文件描述符（一个小的非负整数）。
   • 表中的每个条目包含一个指向系统级打开文件表中对应条目的指针。

2. 系统级打开文件表（System-wide Open File Table）：

   • 整个操作系统维护一个全局的打开文件表。
   • 当任何进程打开一个文件时，如果该文件尚未被任何其他「打开实例」引用，则会在此表中创建一个新条目；否则可能共享现有条目（取决于打开方式和共享情况）。
   • 每个条目包含：
     • 当前文件偏移量（读写指针）。
     • 访问模式（如只读、只写、读写）。
     • 与文件打开相关的标志（如 O_APPEND）。
     • 一个指向该文件在磁盘上的 inode（即文件元数据）的指针（指向 inode 表中的条目）。
     • 一个打开计数器，记录有多少个每进程文件描述符表条目指向此条目。

3. 内存驻留的 inode 表（In-memory Inode Table）：

   • 系统范围的表，缓存了磁盘上 inode 表中活跃的 inode。
   • 每个条目存储文件的完整元数据（类型、大小、权限、时间戳、数据块指针等）。

• 打开文件的过程：
  1. 当进程调用 open() 打开一个文件时，系统首先在系统级打开文件表中查找。
     • 如果文件当前没有被任何打开实例引用（或者需要一个新的打开实例），则会搜索目录以找到文件名对应的 inode，然后在系统级打开文件表中创建一个新条目，并初始化其文件偏移量、访问模式等。该条目会指向 inode 表中对应的 inode。
  2. 接着，在进程的文件描述符表中分配一个未使用的最小文件描述符。
  3. 该文件描述符表条目将指向系统级打开文件表中的相应条目。
  4. 系统级打开文件表条目的打开计数器增加。
  5. open() 调用返回这个文件描述符给进程。
• 关闭文件的过程：
  1. 当进程调用 close(fd) 时，会清除进程文件描述符表中 fd 对应的条目。
  2. 系统级打开文件表中对应条目的打开计数器减 1。
  3. 如果打开计数器变为 0，则系统级打开文件表中的该条目被移除。

多个进程打开同一个文件：

• 每个进程在自己的文件描述符表中获得一个条目。
• 这些不同进程的文件描述符表条目可以指向系统级打开文件表中的同一个条目（如果它们共享文件偏移量，例如 fork 之后父子进程共享）或不同条目（如果它们独立打开文件，各自维护偏移量）。
• 无论指向系统级打开文件表的哪个条目，这些条目最终都会通过 inode 指针指向 inode 表中同一个 inode，因为它们操作的是同一个物理文件。
• 例子：
  • 两个进程打开相同文件（指向不同全局打开项）：
    • 例如，进程 A 打开 /path/to/file1 得到 fd_A，进程 B 也独立打开 /path/to/file1 得到 fd_B。它们在各自的 FD 表中有条目，这些条目指向系统打开文件表中不同的条目（因为它们有独立的偏移量），但这两个系统打开文件表条目都指向 inode 表中同一个 inode。
    • 
  • 两个进程指向同一个全局打开项（如 fork()）：
    • 当一个进程 fork() 创建子进程时，子进程会继承父进程的打开文件表。这意味着父子进程中对应的文件描述符会指向系统打开文件表中同一个条目，因此它们共享文件偏移量。对文件偏移量的修改在父子进程间是可见的。
    • 
  • 一个进程有多个指向同一个打开项的文件描述符（如 dup() 或 dup2()）：
    • dup() 系统调用会创建一个新的文件描述符，该描述符与旧文件描述符指向系统打开文件表中同一个条目。因此，它们共享文件偏移量和文件状态标志。
    • 

目录

目录

目录（Directory 或 Folder）是一种特殊类型的文件，其内容是其他文件或目录的列表（条目）。目录用于组织文件系统中的文件，形成层次化的树状结构。

如果没有目录，所有文件都将存放在一个扁平的空间中，难以管理和查找。通过将目录嵌套在其他目录内，用户可以构建任意复杂的目录树（或目录层次结构）。

graph LR
    root["根目录"]
    root --> A
    root --> B
    root --> C

    A --> A_file["A/file.txt (file)"]

    B --> B_sub1["B/sub1 (directory)"]
    B --> B_sub2["B/sub2 (directory)"]
    B --> B_file["B/another.txt (file)"]

    B_sub1 --> B_sub1_file["B/sub1/data (file)"]

    C --> C_sub1["C/subdir (directory)"]
    C --> C_file["C/config (file)"]

    C_sub1 --> C_sub1_sub["C/subdir/nested (subdirectories)"]
    C_sub1_sub --> C_sub1_sub_f1["... (file)"]
    C_sub1_sub --> C_sub1_sub_f2["... (file)"]

    classDef file fill:#f9f,stroke:#333;
    classDef dir fill:#9cf,stroke:#333;
    class root,A,B,C,B_sub1,B_sub2,C_sub1,C_sub1_sub dir;
    class A_file,B_file,B_sub1_file,C_file,C_sub1_sub_f1,C_sub1_sub_f2 file;

路径

标识文件或目录位置的字符串称为路径（Path）。

• 绝对路径（Absolute Path）：从根目录开始，逐级列出到目标文件或目录的完整路径。路径各组成部分之间使用特定的分隔符（如 Unix-like 中的 /，Windows 中的 \）。
  • 例如：/home/user/docs/report.txt（Unix）或 C:\Users\user\Documents\report.txt（Windows）
• 相对路径（Relative Path）：从当前工作目录（Current Working Directory, CWD）开始的路径。每个进程都有一个当前工作目录。
  • 例如：如果当前目录是 /home/user/，则相对路径 docs/report.txt 指向 /home/user/docs/report.txt。
  • 在 Unix-like 系统中，每个目录（除了根目录）都包含两个特殊的条目：
    • .：代表当前目录本身。
    • ..：代表上一级（父）目录。
    • 例如：cd .. 命令会切换到父目录。

目录的实现

目录的核心功能是存储文件名与其对应的低级结构（通常是文件的 inode 号）之间的映射关系。

• 在 Unix-like 系统中，每个目录条目通常是一个 <文件名, inode 号> 的键值对。
• 目录本身也像普通文件一样存储在磁盘上，有自己的 inode 和数据块。
• 要查找一个文件（如 /usr/ast/mbox），文件系统需要：
  1. 从根目录（其 inode 号通常是固定的，如 2）开始。
  2. 读取根目录的数据块，查找名为 usr 的条目，获取 usr 目录的 inode 号（例如，inode 6）。
  3. 读取 inode 6 对应的数据块（即 usr 目录的内容），查找名为 ast 的条目，获取 ast 目录的 inode 号（例如，inode 26）。
  4. 读取 inode 26 对应的数据块（即 ast 目录的内容），查找名为 mbox 的条目，获取 mbox 文件的 inode 号（例如，inode 60）。
  5. 此时，就找到了 mbox 文件的元数据（inode 60），可以进行后续操作。

目录的操作

文件系统通常提供以下目录操作（对应的系统调用）：

• create(name) 或 mkdir(name)：创建一个新目录（初始时通常只包含 . 和 .. 条目）。
• delete(name) 或 rmdir(name)：删除一个目录（通常要求目录必须为空）。
• opendir(name)：打开一个目录以准备读取其内容。
• readdir(dir_stream)：读取并返回打开目录中的下一个条目（文件名和 inode 号）。
• closedir(dir_stream)：关闭先前打开的目录。
• rename(old_name, new_name)：更改文件或目录的名称（或将其移动到同一文件系统内的另一个位置）。
• link(existing_file_path, new_link_path)：为现有文件创建一个新的硬链接（新的目录条目指向同一个 inode）。
• unlink(pathname)：删除一个目录条目。如果这是指向某个 inode 的最后一个硬链接，则文件本身（inode 和数据块）将被标记为可回收。在 Unix 中，unlink 是删除文件的主要方式。

目录修改的间接性

目录的内部格式通常被视为文件系统的元数据，由文件系统自身负责维护其完整性。因此，用户程序通常不能直接修改目录文件的内容（例如，像编辑普通文件一样用 write 修改目录条目）。用户只能通过上述的目录操作 API（如创建文件、删除文件、创建目录等）来间接更新目录的内容。

共享文件

文件共享允许同一个文件在文件系统中的多个位置出现，或者被多个用户访问。通过将一个新的文件名（目录条目）链接到一个已存在的文件，可以创建另一种引用同一文件数据的方式。

• 可以为同一个文件创建多个不同的名称（路径）。
• 如果允许链接，目录结构就不再是严格的树形，而可能变成一个有向无环图（DAG），因为多个目录条目可以指向同一个文件 inode。

主要有两种类型的链接：

• 硬链接
• 软链接/符号链接

硬链接

硬链接

硬链接（Hard Link）是在一个目录中创建一个新的目录条目，该条目直接指向目标文件（或目录，但通常不允许链接到目录）的 inode 号。

• 创建：
  • Linux

    $ ln target_file link_name

  • PowerShell

    > New-Item -ItemType HardLink -Path link_name -Target target_file

  • CMD

    > mklink /H link_name target_file

    • mklink 命令用于创建链接，/H 参数表示创建硬链接。
• 效果：link_name 和 target_file 都指向磁盘上完全相同的 inode 和数据块。它们是同一文件的不同名称。
• 无复制：文件数据没有被复制。
• 引用计数：inode 中有一个链接计数器（links_count），记录有多少个目录条目指向该 inode。
  • 创建硬链接时，计数器加 1。
  • 删除硬链接（unlink）时，计数器减 1。
  • 当链接计数器达到 0 时，表示没有任何目录条目指向该 inode，此时文件系统才会真正删除文件（回收 inode 和数据块）。
• 限制：
  • 不能跨文件系统：inode 号只在单个文件系统内是唯一的。因此，硬链接不能指向位于不同文件系统（不同磁盘分区）上的文件。
  • 通常不允许链接到目录：这是为了简化管理，防止在目录层次结构中创建循环（例如，目录 A 包含指向目录 B 的硬链接，目录 B 又包含指向目录 A 的硬链接），并避免父目录 .. 的不明确性（如果一个子目录有多个父目录通过硬链接指向它，它的 .. 该指向谁？）。

软链接

软链接

软链接（Symbolic Link 或 Soft Link）是创建一种特殊类型的文件，该文件的内容是另一个文件或目录的路径名。

• 创建：
  • Linux

    $ ln -s target_path link_name

  • PowerShell

    > New-Item -ItemType SymbolicLink -Path link_name -Target target_path

  • CMD

    > rem 文件软链接
    > mklink link_name target_path
    > rem 目录软链接
    > mklink /D link_name target_path

• 效果：link_name 是一个独立的文件（有自己的 inode），它存储了指向 target_path 的文本路径。当访问 link_name 时，操作系统会解析其内容（路径名），然后访问该路径名指向的目标。
• 类似快捷方式：Windows 中的快捷方式与软链接类似。
• 特点：
  • 可以跨文件系统：因为它存储的是路径名，而不是 inode 号。
  • 可以链接到目录。
  • 目标可以是另一个软链接：系统会递归解析，直到找到实际文件或解析失败。
  • 效率较低：访问软链接需要额外的解析步骤，比硬链接慢。
  • 删除软链接：删除 link_name 本身，目标文件 target_path 不受影响。
  • 悬空引用：如果目标文件 target_path 被删除或移动，软链接 link_name 仍然存在，但它指向一个不再有效的路径，此时软链接就「悬空」了。

文件保护

文件保护机制是为了防止文件被意外或恶意地破坏、篡改或未经授权的访问。文件所有者应该能够控制：

• 可以对文件做什么操作？（如读、写、执行）
• 谁可以执行这些操作？（如所有者、特定用户组、其他所有人）

访问权限的类型通常包括：

• 对于文件：
  • read（r）：允许查看文件内容。
  • write（w）：允许修改文件内容。
  • execute（x）：如果文件是程序，允许运行它。
• 对于目录：
  • list（r）：允许列出目录中的文件名。
  • modify（w）：允许在目录中创建、删除、重命名文件（需要执行权限配合）。
  • search（x）：允许进入该目录（即将其作为路径的一部分）和访问目录中的文件元数据。
• 对于访问权限本身：更改文件的所有者、权限设置等。

访问控制矩阵

理论上，系统访问控制的实现可以视为一个巨大的访问控制矩阵（Access Control Matrix）。

• 行：代表主体（Subjects），通常是用户或用户组。
• 列：代表客体（Objects），通常是文件或目录。
• 单元格 [Subject, Object]：包含该主体对该客体拥有的权限集合（如 rwx）。

	File1	File2	File3	Dir1	Dir2	…
UserA	rw	r	rwx	lmd	l	…
GroupB	-	r	rw	-	lm	…
…	…	…	…	…	…	…

lmd 可能代表 list, modify, delete

由于实际系统中用户和文件数量庞大，完整的访问控制矩阵非常稀疏且难以管理。因此，通常采用更紧凑的实现方式，如访问控制列表（ACLs）或 Unix 风格的权限位。

Unix 中的访问控制

Unix-like 系统采用一种简化的访问控制模型：

• 每个文件和目录关联一个所有者（User ID, UID）和一个组（Group ID, GID）。
• 权限被分为三类用户类别：
  1. 所有者（Owner/User, u）：文件的创建者。
  2. 组（Group, g）：与文件所有者同组的其他用户。
  3. 其他人（Others, o）：系统中的其他所有用户。
• 为每个用户类别定义三种基本访问模式：
  1. 读取（read, r）：用数字 4 表示。
  2. 写入（write, w）：用数字 2 表示。
  3. 执行（execute, x）：用数字 1 表示。
• 权限通常用 9 个字符（如 rwxr-xr--）或 3 个八进制数字（如 754）表示。

示例：rwxrw-r--（八进制 764）

• 所有者（u）: rwx（读、写、执行）为 $4+2+1 = 7$
• 组（g）: rw-（读、写）为 $4+2+0 = 6$
• 其他人（o）: r--（只读）为 $4+0+0 = 4$

当用户尝试访问文件时，系统会检查其 UID 和 GID，并根据对应的权限类别决定是否允许操作。

文件系统挂载

一个文件系统在能被访问之前，必须先进行挂载（Mount）。

• 挂载点：现有文件系统（通常是根文件系统或其子目录）中的一个目录，作为新文件系统接入点。
• 操作：将一个存储设备（如 U 盘、硬盘分区）上的文件系统的根目录映射到这个挂载点。
• 效果：使得多个独立的文件系统（可能位于不同设备上，甚至类型不同）能够统一到一个逻辑上的目录树中，用户可以透明地访问它们。

例如，在 Linux 上：

• mkfs 命令（如 mkfs.ext4 /dev/sdb1）可以在一个块设备（如分区 /dev/sdb1）上创建一个新的文件系统。
• mount 命令（如 mount /dev/sdb1 /mnt/myusb）可以将 /dev/sdb1 上的文件系统挂载到当前文件系统中的 /mnt/myusb 目录下。之后，访问 /mnt/myusb 实际上就是在访问 /dev/sdb1 上的文件系统。
• 不带参数的 mount 命令通常会显示当前所有已挂载的文件系统及其挂载点。

WSL(Windows Subsystem for Linux) 自动挂载 Windows 文件系统到 /mnt/c、/mnt/d 等目录下，使得用户可以在 WSL 环境中访问 Windows 的文件。

两个关键的抽象回顾

文件系统的核心功能可以概括为两个关键的抽象映射过程：

1. 目录结构：将用户提供的文件路径名加上文件内的偏移量映射到相应文件的文件控制块（通常是 inode 号）。
2. 文件索引结构（File Index Structure，如 inode 内的块指针）：将文件控制块（inode）和文件内的逻辑偏移量映射到磁盘上的具体数据块编号。

graph LR
    Input["文件名（路径名）+ 偏移量"] --> DirStruct{"目录结构"}
    DirStruct -- "#inode + 偏移量" --> FileIdxStruct{"文件索引结构<br/>（如 inode 中的块指针）"}
    FileIdxStruct -- "#block（数据块号）" --> DataBlocks[("数据块<br/>")]

    style Input fill:#f9f
    style DirStruct fill:#9cf
    style FileIdxStruct fill:#c9f
    style DataBlocks fill:#9fc

文件系统与虚拟内存的对比

文件系统和虚拟内存都是操作系统中重要的抽象机制，它们有一些相似之处，也有显著区别：

特性	文件元信息	页表
映射	文件逻辑块 $\to$ 磁盘物理数据块	虚拟地址 $\to$ 物理内存页帧
权限与检测	访问权限，非法块访问检测	访问权限，非法地址检测（段错误）
实现依赖	通常是纯软件实现	实现高度依赖硬件支持（如 MMU, TLB）
持久性	持久存储	易失性存储（通常）
管理单元	文件、目录	进程地址空间
查找结构	目录树、inode 表	多级页表、TLB

文件系统实现

要实现一个文件系统，需要解决以下核心问题：

• 文件和目录是如何在磁盘上存储和组织的？
• 磁盘空间（包括空闲空间）是如何管理的？
• 如何确保文件系统的实现既高效又可靠？

文件系统的磁盘布局

文件系统需要在磁盘上维护一套特定的数据结构来组织和管理数据。磁盘通常被划分为固定大小的数据块，从 0 到 N-1 编号。一个典型的 Unix 文件系统在磁盘上的简化布局可能包含以下几个部分：

1. 启动块：
   • 通常是磁盘分区中的第一个块。
   • 包含启动操作系统所需的信息（引导加载程序）。如果该分区不用于启动系统，则此块可能为空。
2. 超级块（Superblock）：
   • 存储关于文件系统自身的元信息，如：
     • 文件系统类型（如 ext4, NTFS）。
     • inode 的总数量、数据块的总数量。
     • inode 表的起始块地址。
     • 空闲块和空闲 inode 的数量。
     • 块大小等。
   • 当挂载一个文件系统时，操作系统会首先读取超级块的信息。由于其重要性，通常会有备份副本。
   • 下图的 S。
3. 空闲空间管理结构：
   • 用于跟踪哪些 inode 和数据块是空闲的，哪些已被分配。
   • 常见的实现方式是使用位图：
     • inode 位图：每个 bit 代表一个 inode，0 表示空闲，1 表示已分配。
       • 下图的 i。
     • 数据块位图：每个 bit 代表一个数据块，0 表示空闲，1 表示已分配。
       • 下图的 d。
4. inode 表：
   • 一个连续的区域，存储了文件系统中所有文件的 inode 结构。
   • 每个 inode 包含文件的元数据（大小、权限、时间戳、数据块指针等）。
   • 一个数据块可以存储多个 inode（例如，一个 4KB 的块可以存储 16 个 256 字节的 inode）。
   • 通过 inode 号可以计算出其在 inode 表中的位置。
5. 数据区域：
   • 磁盘上剩余的大部分空间，用于存储实际的文件数据和目录数据。
   • 目录本身也作为文件存储在数据块中，其内容是 <文件名, inode号> 的条目列表。
   • 根目录通常有一个固定的 inode 号（如 2），其数据块也位于数据区域。

• 主引导记录（Master Boot Record, MBR）：位于整个硬盘的第一个扇区，包含一小段启动代码和分区表。
• 分区表（Partition Table）：描述硬盘如何被划分为多个逻辑分区，每个分区的起始和结束地址，以及哪个分区是「活跃的」（用于启动操作系统）。
• 每个分区可以被格式化为一个独立的文件系统，其类型可以不同（例如，一个 Linux 系统可能有 /boot (ext2), / (ext4), swap (特殊格式) 等不同分区）。

内存中的文件系统结构

除了磁盘上的数据结构，文件系统还需要在内存中维护相应的数据结构，以方便对磁盘数据的访问、提高性能并反映磁盘结构的状态：

• 挂载表：记录当前系统中所有已挂载文件系统的信息，如设备名、挂载点、文件系统类型等。
• 打开文件表：包括系统级的打开文件表和每个进程的文件描述符表（如前所述）。
• 目录结构缓存：缓存最近访问的目录信息，以加速路径解析。
• I/O 内存缓冲：用于缓存从磁盘读取的数据块和待写入磁盘的数据块，以减少磁盘 I/O 次数，弥补主存和磁盘之间的速度差异。

文件组织（数据块分配）

文件的数据需要存储在磁盘的数据块中。文件系统必须采用某种策略来组织这些数据块，并记录哪些块属于哪个文件。常见的文件组织（分配）方式有：

1. 连续分配
2. 链式分配
3. 文件分配表
4. 索引分配

连续分配

• 原理：为每个文件分配一组连续的磁盘数据块。
• 记录：目录条目中只需存储文件的起始块地址和文件长度（总块数）。
• 优点：
  • 顺序访问高效：由于数据块连续，磁头移动最少，可以快速读取整个文件。
  • 随机访问也较快：给定文件内偏移量，可以直接计算出对应的磁盘块地址（起始地址 + 逻辑块号）。
• 缺点：
  • 灵活性差：创建文件时通常需要预先知道文件大小，以便分配足够的连续空间。文件增长困难，如果相邻空间已被占用，可能需要移动整个文件。
  • 外部碎片：随着文件的创建和删除，磁盘上会产生许多离散的小块空闲空间，这些小块可能无法满足较大文件的连续分配需求，即使总空闲空间足够。需要进行碎片整理来合并空闲块，但这非常耗时。
• 适用场景：对于大小固定或只读的文件系统（如 CD-ROM, DVD）效果较好。
• 变体：基于 Extent 的分配
  • 一个 Extent 是一组连续的数据块。
  • 文件由一个或多个 Extent 组成，这些 Extent 之间不必相邻，可以通过链表或其他方式连接。
  • 比纯粹的连续分配更灵活，支持文件增长，但仍可能存在一定程度的碎片问题。

链式分配

• 原理：文件的数据块可以分散在磁盘的任何位置。每个数据块包含一个指向文件中下一个数据块的指针。
• 记录：目录条目中只需存储文件的第一个数据块的地址。最后一个数据块的指针为 null 或特殊标记。
• 优点：
  • 无外部碎片：任何空闲块都可以被利用。
  • 文件增长灵活：只需在空闲块中找到一个新块并链接到文件末尾即可。
• 缺点：
  • 随机访问效率低：要访问文件中间的某个块，必须从头开始沿着指针链顺序遍历。
  • 指针开销：每个数据块都需要一部分空间来存储指针，减少了存储实际数据的有效空间。
  • 可靠性问题：如果某个块中的指针损坏，该块之后的所有数据都可能丢失。
  • 顺序访问可能也不如连续分配快：因为数据块物理上可能不连续，导致多次寻道。

文件分配表

• 原理：是链式分配的一种变体，将所有数据块的链接指针集中存放在磁盘开头的一个特殊区域，称为文件分配表（File Allocation Table, FAT）。
• FAT 表本身是一个数组，每个条目对应磁盘上的一个数据块。
• FAT 条目中的内容：
  • 如果该块是文件中下一个块的块号，则存储下一个块的块号。
  • 如果该块是文件的最后一个块，则存储一个特殊的文件结束标记。
  • 如果该块未被分配（空闲），则存储 0 或特殊标记。
  • 如果该块是坏块，则存储特殊标记。
• 记录：目录条目中存储文件的第一个数据块的块号。
• 优点：
  • 随机访问改善：要查找文件的第 N 块，只需在 FAT 表中（通常可以整个加载到内存）进行 N-1 次查找，而无需实际访问磁盘数据块。
  • FAT 表本身也可以用于空闲空间跟踪。
  • 通常有 FAT 表的备份副本以提高可靠性。
• 缺点：
  • FAT 表大小限制：对于大容量磁盘和小编号的 FAT（如 FAT12, FAT16），可寻址的块数量有限。FAT32 改善了此问题。
  • FAT 表需缓存：为提高性能，整个 FAT 表通常需要缓存在内存中。对于非常大的磁盘，FAT 表本身可能占用大量内存
    • 例如，1TB 磁盘，4KB 块大小，4 字节/FAT 条目，则 FAT 表约需 $2^{28} \times 4\text{B} = \pu{1GB}$。
  • 顺序访问仍然可能涉及非连续的物理块。

索引分配

• 原理：为每个文件分配一个称为索引块或 i-node（在某些语境下特指这种结构）的特殊数据块。索引块本身不存储文件数据，而是存储指向该文件实际数据块的指针（地址）列表。
• 记录：目录条目中存储该文件索引块的地址。
• 优点：
  • 支持高效的随机访问：要访问文件的第 N 块，只需读取索引块，从中获取第 N 个指针，然后直接访问对应的数据块。
  • 无外部碎片。
  • 文件增长灵活，只需在索引块中添加新的数据块指针。
  • 索引块只在文件打开时加载到内存，内存开销与打开文件数相关，而不是整个磁盘大小。
• 缺点：
  • 指针开销：如果文件很小（例如只有一个数据块），仍然需要一个完整的索引块，可能造成空间浪费（内部碎片的一种形式）。
  • 索引块大小限制：一个索引块能容纳的指针数量是有限的。对于非常大的文件，一个索引块可能不足以指向所有数据块。

多级索引：为了解决单个索引块对大文件大小的限制，可以采用多级索引方案。

• 一级间接块：索引块中的某些指针不直接指向数据块，而是指向另一个「间接块」，这个间接块里充满了指向实际数据块的指针。
• 二级/三级间接块：间接块中的指针还可以指向更深层次的间接块。
• 结构：形成一个非平衡的树状结构，叶节点是实际数据块。
• Unix inode 实现：一个典型的 Unix inode 包含：
  • 若干（如 12 个）直接块指针：直接指向文件的前几个数据块。
  • 一个一级间接块指针：指向一个包含数据块指针的块。
  • 一个二级间接块指针：指向一个包含一级间接块指针的块。
  • 一个三级间接块指针：指向一个包含二级间接块指针的块。

假设数据块大小为 4KB，每个块地址（指针）为 4 字节。一个 4KB 的索引块或间接块可以容纳 $4096/4 = 1024$ 个指针（$2^{10}$ 个）。

• 12 个直接指针：$12 \times \pu{4KB} = \pu{48KB}$
• 1 个一级间接指针：$2^{10} \times \pu{4KB} = \pu{4MB}$
• 1 个二级间接指针：$2^{20} \times \pu{4KB} = \pu{4GB}$
• 1 个三级间接指针：$2^{30} \times \pu{4KB} = \pu{4TB}$

这种结构能够很好地支持从小文件到非常大的文件。

现实文件系统特性（FAST 2007 研究）

• 大部分文件都很小（例如，约 2KB 是最常见的文件大小）。
• 但大部分磁盘空间被大文件占据。

一个好的文件组织策略需要考虑这些特性，平衡对小文件和大文件的支持，以及顺序访问和随机访问的性能、空间碎片、实现复杂度和存储开销。

目录组织

目录提供了文件名到文件索引信息（如 inode 号或完整磁盘地址）的映射。

• 当打开文件时，OS 根据路径名在磁盘上查找目录条目。
• 目录条目提供的信息可以是：
  • 整个文件所在的磁盘地址（如连续分配）。
  • 文件的第一个数据块编号（如链式分配、FAT）。
  • 文件的 inode 号（如索引分配）。

目录条目的存储方式：

1. 直接存储信息：目录项中包含文件的所有元信息（属性）。
   • MS-DOS (FAT) 的目录项是一个例子，它包含文件名、扩展名、属性、时间、日期、起始块号、大小等。
2. 存储 inode 指针：目录项中只包含文件名和指向该文件 inode 的指针（inode 号）。文件的元信息存储在 inode 中。
   • Unix 的目录项通常是这种方式，例如 <inode 号（2 bytes）, 文件名（14 bytes）>（早期固定长度）。

处理长文件名：

• 固定长度上限：文件名限制在 N 个字符内，目录项中文件名槽固定大小。简单，但对短文件名浪费空间，对长文件名不支持。
• 可变长度目录项：
  • 每个目录项包含：项总长度、文件属性（定长）、文件名（变长，以特殊符号结束）。
  • 删除文件时会产生不定大小的空洞，管理复杂。
  • 
• 固定长度项 + 名称堆：目录项本身定长，文件名存储在目录数据块末尾的一个特殊区域（名称堆）。目录项中包含指向名称堆中文件名的指针/偏移量。删除和空间回收相对容易管理。
  • ext2 文件系统采用类似方式：目录项包含 inode 号、项长度、文件名长度、文件类型、文件名（最多 255 字符）。项长度允许下一个条目不一定紧跟当前文件名之后，可以跳过因删除产生的空洞。
  • 

目录查找优化：

• 线性搜索：如果目录存储为 <文件名, inode 号> 的列表，查找时从头到尾扫描。对小目录有效，但大目录效率低。
• 哈希表：为目录内的文件名构建哈希表，以文件名（或其哈希值）为键，inode 号为值。使用链表处理哈希冲突。查询快，但管理更复杂。
• B 树/B+ 树：对于非常大的目录，可以使用 B 树或 B+ 树结构来组织目录条目，以文件名的哈希值或字母顺序进行索引，提供高效的查找、插入和删除。
• 缓存：无论哪种方案，都可以利用缓存（LRU 等策略）来加速对常用目录的查找。

大目录的用户层优化可以参考 Git，.git/objects 目录使用了一个特殊的命名约定，即使用 SHA-1 哈希值的前两位作为子目录名，后面是剩下的哈希值。这样可以将大目录分散到多个子目录中，避免单个目录过大导致的性能问题。

有意思的是目前（2025.6.6）Blog 的 Git 仓库（698 commits）里面除了 info 和 pack 外才有 255 个目录，而产物 Git 仓库（57 commits）已经有了 256 个目录。对比发现目前前者少的是 44。

Git 原理暑假会写的【待补充】。

空闲空间管理

文件系统需要跟踪哪些 inode 和数据块是空闲的，以便在创建新文件或目录时分配它们。

1. 位图：为每个 inode 和每个数据块分别维护一个位图。
   • 位图中的每一位对应一个块/inode，0 表示空闲，1 表示已分配。
   • 优点：很容易找到连续的空闲块（对于连续分配或 extent 分配有益）。
   • 缺点：位图本身需要额外的存储空间。例如，对于 1TB 磁盘（$2^{40}$ 字节），块大小为 4KB ($2^{12}$ 字节)，则需要 $2^{40}/2^{12} = 2^{28}$ 个数据块。如果每个块用 1 bit 表示，则数据块位图需要 $2^{28}$ bits = 32MB。
2. 空闲列表：将所有空闲块链接成一个链表。空闲块本身用于存储指向下一个空闲块的指针。
   • 优点：没有额外的空间浪费（除了链表头指针）。内存中只需存储链表头指针。
   • 缺点：
     • 分配过程可能较慢，尤其当需要分配多个块时，可能需要遍历链表。
     • 难以找到连续的空闲块。
     • 如果需要分配多个不连续的块，可能涉及多次磁盘 I/O 来读取链表中的指针。
3. 其他结构：如 B 树也可以用于管理空闲空间，尤其适用于需要快速找到特定大小空闲区域的场景。

块大小的选择

磁盘块（或文件系统块）的大小是一个重要的设计参数：

• 过大：
  • 内部碎片：大部分文件都很小。如果块很大（如 64KB），一个小文件（如 1KB）也会占用整个块，浪费大量空间。
  • 传输大块数据可能更有效率，但如果只修改少量数据，仍需读写整个大块。
• 过小：
  • 寻道和延迟开销大：一个文件会分散在更多的小块中，读取文件需要更多次的寻道和旋转等待。
  • 元数据开销大：每个块都需要元数据（如 FAT 表项或 inode 中的指针），块越小，同样大小文件所需的元数据越多。
• 历史选择：传统文件系统通常选择 1KB 到 4KB 的块大小。
• 现代趋势：随着磁盘容量超过 1TB 甚至更大，以及内存价格下降（可以缓存更多元数据），更大的块大小（如 64KB 甚至更大）可能更合适，以提高大文件传输的吞吐量。磁盘空间浪费的相对重要性在下降。

检查块大小

Linux 系统可以通过 stat -f /path/to/mountpoint 命令查看文件系统的块大小（Block size 字段）。例如：

$ stat -f /
...
Block size: 4096       Fundamental block size: 4096
...

Windows 系统可以通过 fsutil fsinfo ntfsinfo C: 命令查看 NTFS 文件系统的块大小（Bytes Per Cluster 字段）。例如：

> fsutil fsinfo ntfsinfo C:
...
Bytes Per Cluster :                4096  (4 KB)
...

文件系统操作示例：读/写文件

假设文件系统已挂载，超级块在内存中，但 inode 和目录数据主要在磁盘上（可能会被缓存）。

读文件 /foo/bar 的前 3 个数据块

1. 打开文件 open("/foo/bar")：
   • 读根目录 inode，然后读根目录数据块，找到 foo 的 inode 号。
   • 读 foo 目录 inode，然后读 foo 目录数据块，找到 bar 的 inode 号。
   • 读 bar 文件 inode，检查权限。如果合法，在进程文件描述符表和系统打开文件表中创建条目，返回文件描述符 fd。
2. 第一次 read(fd, ...)：
   • （可能再次）读 bar 文件 inode（获取数据块指针）。
   • 读 bar 的第 0 个数据块。
   • 写 bar 文件 inode（更新最后访问时间 atime）。
   • 更新内存中打开文件表条目的文件偏移量。
3. 第二次 read(fd, ...)：
   • 读 bar 文件 inode。
   • 读 bar 的第 1 个数据块。
   • 写 bar 文件 inode (更新 atime)。
   • 更新文件偏移量。
4. 第三次 read(fd, ...)：
   • 读 bar 文件 inode。
   • 读 bar 的第 2 个数据块。
   • 写 bar 文件 inode (更新 atime)。
   • 更新文件偏移量。

创建文件 /foo/bar 并写入 3 个数据块

1. 创建/打开文件 create("/foo/bar")：
   • 分配 inode for bar：读 inode 位图，找到一个空闲 inode，标记为已用，写回 inode 位图。
   • 初始化 bar inode：写入 bar 的 inode（类型、权限、时间戳等，数据块指针为空）。
   • 添加目录项：
     • 读根目录 inode，读根目录数据，找到 foo inode 号。
     • 读 foo 目录 inode。
     • 读 foo 目录数据块。
     • （如果 foo 目录空间不足以添加新条目，则需为 foo 目录分配新数据块：读数据块位图，分配，写回位图；更新 foo inode 指向新数据块，写回 foo inode）。
     • 将 <"bar", bar_inode_num> 写入 foo 目录数据块。
     • 更新 foo inode（如修改时间、大小），写回 foo inode。
   • 返回文件描述符 fd。
2. 第一次 write(fd, ...)：
   • 分配数据块 D0 for bar：读数据块位图，找到空闲块，标记已用，写回数据块位图。
   • 更新 bar inode：读 bar inode，添加指向 D0 的指针，更新大小、时间戳，写回 bar inode。
   • 写数据块 D0：将用户数据写入 D0。
   • 更新文件偏移量。
3. 第二次 write(fd, ...)（分配 D1）：类似操作，涉及数据块位图、bar inode、数据块 D1。
4. 第三次 write(fd, ...)（分配 D2）：类似操作。

I/O 次数

上述操作中，每次「读」或「写」磁盘结构（位图、inode、数据块）都对应一次或多次磁盘 I/O。实际操作中，由于缓存的存在，许多读操作可能命中缓存，写操作也可能被延迟和合并，从而显著减少实际的物理 I/O 次数。

文件系统性能

减少磁盘 I/O 是提高文件系统性能的关键，因为磁盘访问远慢于内存访问。

• Read-Modify-Write：许多文件系统操作（如更新 inode 或目录）遵循此模式：先读取块到内存，修改内容，再写回磁盘。
• 缓存和缓冲：
  • 缓存：将频繁访问的磁盘块（如 inode、目录块、数据块）保留在内存中（称为页缓存或缓冲区缓存）。后续的读请求如果命中缓存，则无需访问磁盘。
    • 使用哈希表等结构快速查找块是否在缓存中。
    • 当缓存满时，使用替换策略（如 LRU）淘汰旧块。
    • 现代系统通常将虚拟内存页和文件系统缓存页集成到统一的页缓存中，以便内存资源在两者间灵活分配。
  • 预取：预测性地将可能很快被访问的数据块提前读入缓存。对于顺序文件访问（如大文件读取）非常有效。对随机访问则效果不佳，甚至可能因加载无用数据、替换有用数据而降低性能。文件系统可以跟踪打开文件的访问模式来决定是否预取。
  • 写缓冲：写操作通常先写入内存缓冲区，而不是立即写入磁盘。
    • 延迟写：文件系统可以将多个小的写操作合并成一个大的写操作，或在系统空闲时批量写入，以提高效率（例如，多次修改 bitmap 可以合并）。
    • 写调度：缓冲写操作允许文件系统或磁盘控制器对写请求进行重新排序，以优化磁头移动（例如，将物理上相近的块一起写入）。
    • 避免写：某些写操作甚至可以完全避免（例如，创建一个临时文件然后很快删除它，数据可能从未真正写入磁盘）。
    • 一致性风险：写缓冲提高了性能，但也带来了数据丢失的风险。如果系统在缓冲数据写回磁盘前崩溃，这些未持久化的修改将会丢失。因此，系统需要定期（如每隔几秒或通过 fsync 调用）将脏缓存块刷新到磁盘。这是一个性能与可靠性之间的权衡。

快速文件系统

早期 Unix 文件系统（如 System V FS）性能不佳，磁盘带宽利用率很低（约 2%），因为它们将磁盘视为纯粹的随机访问设备，导致大量寻道时间。数据块和其对应的 inode 可能分散在磁盘的远端。

快速文件系统 FFS (Berkeley Fast File System) 针对传统机械硬盘的特性进行了优化，核心思想是磁盘感知和数据局部性。

• 柱面组/块组：FFS 将磁盘划分为多个块组。每个块组由一组物理上相邻的磁道（柱面）构成。
  • 每个块组都有自己的超级块副本、inode 表、数据块位图、inode 位图和数据块。这类似于一个微型文件系统。
• 数据局部性策略：
  • 文件数据与 inode：尽量将文件的数据块分配到与其 inode 相同的块组中。
  • 目录内容：尽量将同一目录下的所有文件（它们的 inode 和数据）放置在该目录所在的块组中。
  • 新目录分配：创建新目录时，FFS 会尝试找到一个块组，该块组中已分配的目录数量较少（以平衡各组负载）且空闲 inode 数量较多（以便该目录能容纳许多文件）。
• 目标：通过将相关数据（如一个文件的 inode 和其数据块，或一个目录及其内容）物理上聚集在一起，减少磁头在不同块组间的长距离寻道，从而提高顺序访问和相关文件访问的性能。

SSD 的影响

FFS 的设计主要针对机械硬盘的寻道和旋转延迟。对于固态硬盘：

• 随机访问和顺序访问的速度差异远小于机械硬盘。
• SSD 没有移动部件，因此寻道和旋转延迟不再是主要瓶颈。
• SSD 的主要特性是每个存储单元（块）的擦写次数有限（磨损问题）。

因此，FFS 的某些优化（如碎片整理以实现数据连续）对 SSD 可能不是最优的，甚至可能因增加不必要的写入而加剧磨损。现代文件系统针对 SSD 会采用不同的策略，如损耗均衡和 TRIM 命令。

文件系统可靠性

持久存储意味着数据在系统重启或电源故障后依然存在。文件系统必须保证数据的可靠性和一致性。

崩溃一致性问题

文件系统的许多更新操作（如创建一个文件、向文件追加数据）需要修改磁盘上的多个不同结构（如 inode、数据块、位图、目录块）。这些修改通常涉及多次独立的磁盘 I/O 操作。

• 如果在这一系列 I/O 操作的中间发生系统崩溃（如电源故障），某些操作可能已完成并写入磁盘，而另一些操作可能尚未开始或只完成了一部分。
• 这会导致文件系统处于一种不一致的状态，元数据之间可能相互矛盾。

例如「为一个文件增加一个数据块」需要三个写操作：

1. 写入新的数据块（D）。
2. 更新文件的 inode（I），使其指向新的数据块 D，并增加文件大小。
3. 更新数据块位图（B），将块 D 标记为已分配。

如果在这三个写操作之间发生崩溃：

• 只写了 D：数据写入了，但 inode 和位图不知道它的存在。这个写操作会丢失，但文件系统元数据本身还是一致的（只是损失了新数据）。
• 只写了 I：inode 指向了块 D 并认为它包含有效数据，但位图 B 可能仍认为 D 是空闲的（导致未来可能将 D 分配给其他文件，造成数据冲突），或者块 D 实际上包含的是垃圾数据（因为 D 本身没写成功）。不一致。
• 只写了 B：位图 B 认为块 D 已被使用，但没有 inode 指向它。这会导致磁盘空间泄露（块被占用但无法访问）。不一致。
• 写了 I 和 B，但没写 D：inode 指向 D，位图也说 D 已用，但 D 包含垃圾数据。读取时会得到错误内容。元数据层面可能是一致的，但文件内容损坏。
• 写了 I 和 D，但没写 B：inode 指向正确的 D，但位图认为 D 空闲。未来 D 可能被重分配。不一致。
• 写了 B 和 D，但没写 I：位图说 D 已用，D 也有数据，但没有 inode 指向它。空间泄露。不一致。

理想情况下，文件系统的更新应该是原子的，即从一个一致状态转换到另一个一致状态，要么全部完成，要么完全不做。但磁盘通常只保证单个扇区（或块）的写操作是原子的，而文件系统更新涉及多个块。

解决方案

1. 文件系统一致性检查
2. 日志或预写日志

文件系统一致性检查

文件系统一致性检查（File System Consistency Check, fsck）

• 思路：允许不一致发生，在系统重启后、挂载文件系统之前，运行一个工具（如 fsck）来检测和修复文件系统元数据中的不一致性。
• fsck 通常会执行以下检查和修复：
  • 超级块检查：验证超级块中的信息（如文件系统大小、块总数）是否合理。如果不一致，尝试使用备份副本。
  • 空闲块和 inode 位图：通过扫描所有 inode 来确定哪些块和 inode 确实已被分配，然后与位图进行比较。如果不一致，通常以 inode 表的信息为准来重建位图（修复空间泄露或错误标记的空闲块）。
  • Inode 状态：检查每个 inode 的字段是否有效（如类型、大小、时间戳范围）。损坏的 inode 可能被清除。
  • Inode 链接计数：遍历整个目录树，计算每个 inode 的实际硬链接数，并与 inode 中存储的链接计数比较。如果不匹配，则修正 inode 中的计数。如果一个已分配的 inode（链接计数 > 0）但没有任何目录条目指向它（「孤儿」inode），它可能会被移动到 lost+found 目录中。
  • 重复指针/坏块：检查是否有多个 inode 指向同一个数据块（通常是错误的）。如果一个 inode 指向分区外的数据块，则该 inode 可能被清除。
  • 目录完整性：检查目录结构是否正确（如 . 和 .. 条目是否存在且正确），目录中每个条目指向的 inode 是否已被分配且有效。
• 缺点：
  • 慢：fsck 通常需要扫描整个磁盘的元数据，对于大容量磁盘可能非常耗时。
  • 修复不完美：fsck 旨在恢复文件系统的「一致」状态，但这并不总是「正确」的状态（即用户期望的状态）。它可能无法恢复所有丢失的数据，有时甚至会为了达到一致性而丢弃一些可疑数据。

日志或预写日志

借鉴自数据库系统，日志技术通过在实际修改文件系统结构（如 inode 表、数据块）之前，先将要做的修改操作记录到一个称为日志的特殊磁盘区域。

日志（Journaling）或预写日志（Write-ahead Logging, WAL）

• 基本流程：
  • 
  1. 日志写入：
     • 开始一个事务，例如写入一个事务开始标记 TxB 到日志，包含事务 ID 和将要修改的块的元数据。
     • 将所有待更新的内容写入日志。
  2. 日志提交：
     • 当所有待更新内容都已写入日志后，写入一个事务结束标记 TxE 到日志。这个 TxE 的写入必须是原子的（通常通过确保它足够小，如在一个扇区内，并等待其完成）。一旦 TxE 成功写入，该事务就被认为是已提交的。
  3. 检查点：
     • 在事务提交到日志之后，文件系统再将日志中记录的更新内容实际写入它们在磁盘上的最终位置（即覆盖旧的 inode、位图和数据块）。
  • 
• 崩溃恢复：
  • 系统重启后，扫描日志。
  • 如果一个事务在日志中只有 TxB 而没有 TxE（在日志提交前崩溃）：忽略该事务，因为它未完成。
  • 如果一个事务在日志中有完整的 TxB 和 TxE（在检查点操作期间或之前崩溃）：按顺序重放日志中该事务记录的更新操作，将它们写入磁盘的最终位置，这称为重做日志（redo logging）。这可能是冗余的（如果某些块在崩溃前已写入），但能确保所有已提交的更改都生效。
• 优点：
  • 快速恢复：恢复时只需扫描日志（通常比整个文件系统小得多），而无需扫描整个磁盘。
  • 保证一致性：确保文件系统总能恢复到一个一致的状态。
• 日志管理：
  • 日志空间有限，通常实现为循环日志。一旦事务被成功应用到检查点，其在日志中占用的空间就可以被后续事务重用。
  • 需要一个日志超级块来记录哪些事务已提交但尚未检查点。
  • 
• 数据日志 vs. 元数据日志：
  • 数据日志：将文件数据和元数据都写入日志。提供最高级别的一致性（保证数据和元数据同步），但代价较高，因为所有数据都要写两次（一次到日志，一次到最终位置）。
  • 元数据日志：只将文件系统的元数据（inode、位图、目录块）写入日志，文件数据直接写入最终位置。
    • 顺序：通常是先确保数据块写入磁盘，然后记录元数据更新到日志并提交，最后才更新磁盘上的元数据。这样可以避免元数据指向未写入或垃圾数据的风险。
    • 一致性：保证文件系统元数据的一致性，但如果崩溃发生在数据块写入后、元数据日志提交前，文件内容可能已更新，但元数据尚未反映，可能导致新数据丢失（但不会指向垃圾数据）。这是性能和可靠性之间的常见折衷，被 ext3, ext4, NTFS 等广泛采用。
  • 

日志结构文件系统

传统文件系统（即使是 FFS）在处理大量小文件写入或随机写入时，仍会产生较多寻道，难以充分利用磁盘带宽。

日志结构文件系统（Log-structured File System, LFS）的核心思想：将所有写入操作（包括数据和元数据）都顺序地追加到磁盘末尾的一个大型、连续的日志区域，就像磁带一样。

• 从不原地修改：当数据或元数据（如 inode）发生变化时，LFS 不会去修改磁盘上旧的版本，而是将新版本作为一个新块写入日志的当前末尾。
• 段：为了减少旋转延迟并提高效率，LFS 将多次小的写操作先缓冲在内存中，当积累到一定大小（如几 MB）时，作为一个段一次性顺序写入磁盘。一个段可能包含数据块、inode 块、inode 映射块等。

Inode 查找：由于 inode 不再位于固定位置的 inode 表中，而是随数据一起写入日志，LFS 需要一种方法来定位最新的 inode 版本。

• Inode 映射：每个段可以包含一个 imap，记录该段中写入的每个 inode 的新位置。
• 检查点区域（Checkpoint Region, CR）：LFS 在磁盘的固定位置维护一个 CR。CR 包含指向所有当前有效的 imap 块的指针。当系统启动或需要查找 inode 时，先读取 CR，然后通过 imap 找到 inode。imap 通常会被缓存在内存中。CR 会定期更新。
• 

垃圾回收：

• 由于 LFS 从不原地修改，旧版本的数据和 inode 会散布在磁盘上，占用空间。磁盘容量是有限的，最终需要回收这些「死」空间。
• LFS 有一个清理器进程，定期扫描磁盘上的段。
• 段摘要块（Segment Summary Block, SSB）：每个段包含一个 SSB，记录该段中每个数据块属于哪个 inode 以及其在文件内的偏移量。
• 清理器读取一个或多个段，通过 SSB 和当前的 imap（或 CR）判断哪些块仍然是「活」的（即被最新版本的 inode 引用）。
• 活的块被重新组织并写入到日志的末尾（作为新段的一部分）。
• 一旦段中所有活块都被迁移，整个旧段就可以被标记为空闲，供将来写入。
• 

优缺点：

• 优点：
  • 写入性能高：所有写入都是大块顺序写入，非常适合机械硬盘，也能减少 SSD 的写放大。
  • 恢复快：类似日志系统，从检查点恢复。
  • 版本化潜力：由于旧数据不立即覆盖，理论上可以支持文件系统的快照和版本回溯（如果 CR 和旧 imap 被保留）。
    • 
• 缺点：
  • 垃圾回收开销：清理过程本身会产生读写开销，如果磁盘空间利用率很高，清理器可能难以找到足够多的空闲空间，导致性能下降（「清理墙」问题）。
  • 读取性能：如果文件的数据块在逻辑上连续，但在 LFS 中可能因为多次修改而散布在磁盘的不同段中，读取时可能不如传统文件系统高效（尽管缓存可以缓解）。

总结

文件系统是操作系统中管理持久化数据的核心组件，它通过一系列抽象（文件、目录、inode）和机制（API、打开文件表、链接、保护、挂载）为用户和应用程序提供了方便、高效、可靠的数据访问。

关键概念回顾：

• 两个关键抽象：文件和目录。
• 元数据信息：主要通过 inode 存储。
• 访问句柄：文件描述符和相关的打开文件表。
• 共享机制：软链接和硬链接。
• 文件系统实现：
  • 磁盘布局：超级块、空闲空间管理（位图/列表）、inode 表、数据块。
  • 文件组织：连续分配、链式分配、FAT、索引分配（多级索引）。
  • 目录组织：文件名到 inode 的映射，长文件名处理，查找优化。
  • 性能优化：缓存与缓冲、预取、FFS（块组、数据局部性）。
  • 可靠性保障：崩溃一致性、fsck、日志技术（预写日志、元数据/数据日志）、日志结构文件系统（LFS）。

理解文件系统的设计原理、各种数据结构和算法的权衡，对于编写高效可靠的应用程序以及进行系统管理和故障排除都至关重要。