第11章：文件系统——介绍与概述

11.1 文件系统抽象

文件系统是操作系统提供的一种抽象，用于持久化存储和命名数据。其主要组成部分包括：

  • 文件：命名的数据集合，包含元数据（如大小、修改时间、权限）和实际数据（无类型字节流）。
  • 目录：文件和其他目录的命名容器，通过路径（如 /home/alice/file.txt）组织成层次结构。绝对路径从根目录（/）开始，相对路径基于当前工作目录。
  • 硬链接与符号链接：硬链接是目录到文件的直接映射，允许多个路径指向同一文件；符号链接是间接映射到另一个路径，可能形成悬垂链接。
  • 卷：逻辑存储设备，可跨物理设备或分区，通过挂载（mount）整合到文件系统树中。

11.2 文件系统API

文件系统通过系统调用提供以下操作：

  • 创建与删除：create() 创建文件，unlink() 删除文件链接，mkdir() 和 rmdir() 管理目录。
  • 打开与关闭：open() 返回文件描述符，close() 释放资源。
  • 文件访问：
    • read() 和 write() 按当前文件位置读写数据。
    • seek() 调整文件位置。
    • mmap() 将文件映射到内存，通过内存访问文件数据。
    • fsync() 确保数据持久化到存储设备。
  • 现代API扩展：如 POSIX 的 fopen()/fwrite() 提供缓冲，提升小文件操作效率。

11.3 软件层次

文件系统实现分为两层：

  1. API与性能层：
    • 用户库（如 stdio）包装系统调用，提供缓冲。
    • 块缓存：缓存常用数据，减少存储设备访问。
    • 预取：预测性读取数据，提升性能（需避免过度预取导致缓存压力）。
  2. 设备访问层：
    • 设备驱动：屏蔽硬件细节，提供统一块设备接口。
    • 设备通信：
      • 内存映射I/O：通过物理地址访问设备寄存器。
      • DMA：设备直接与内存传输数据，减少CPU干预。
      • 中断：设备通知操作系统事件完成。
    • 可靠性挑战：驱动错误可能影响系统稳定性，现代系统通过隔离提升安全性。

11.4 总结与未来方向

文件系统接口稳定，但应用需注意性能与可靠性问题（如 fsync() 的使用）。未来可能改进：

  • 原子多对象更新：简化应用开发。
  • 高效数据传输：如直接从文件到网络的零拷贝接口。

本章为后续章节（存储设备、文件实现、可靠存储）奠定基础，强调理解硬件特性对系统设计的重要性。

第12章：存储设备

本章详细介绍了两种主要的持久存储设备：磁盘存储和闪存存储，分析了它们的物理特性、访问性能、调度策略以及技术趋势。

12.1 磁盘存储（Magnetic Disk）

12.1.1 磁盘结构与访问性能

磁盘由多个盘片（platter）组成，每个盘片有两个表面（surface），数据存储在磁道（track）和扇区（sector）（通常512B~4KB）上。

  • 关键组件：
    • 磁头（head）：读写数据，悬浮在盘片上方。
    • 磁盘臂（arm）：移动磁头到目标磁道。
    • 主轴（spindle）：以恒定转速（如7200 RPM）旋转盘片。
  • 访问时间计算： \(\text{访问时间} = \text{寻道时间} + \text{旋转延迟} + \text{传输时间}\)
    • 寻道时间（seek time）：磁头移动到目标磁道的时间（平均10ms）。
    • 旋转延迟（rotational latency）：等待目标扇区旋转到磁头下方（平均旋转半圈时间，如7200 RPM ≈ 4.15ms）。
    • 传输时间（transfer time）：数据从盘面读取到磁盘缓存的时间（如100MB/s带宽下，512B传输约5μs）。
  • 随机访问 vs. 顺序访问：
    • 随机访问（如500个随机扇区读取）可能耗时数秒（如7.33s）。
    • 顺序访问（如500个连续扇区读取）仅需几十毫秒（如16.4ms）。

12.1.2 案例研究：Toshiba MK3254GSY 磁盘

  • 参数：320GB容量、7200 RPM、平均寻道时间10.5ms（读）/12ms（写）。
  • 带宽：54-128MB/s（外圈更快）。
  • 性能对比：
    • 随机访问（500次读）≈ 7.33s。
    • 顺序访问（500次读）≈ 16.4ms。

12.1.3 磁盘调度（Disk Scheduling）

为提高I/O效率，操作系统或磁盘固件优化请求顺序：

  1. FIFO（先进先出）：简单但性能差（如交替访问内外磁道导致长寻道）。
  2. SPTF/SSTF（最短定位/寻道时间优先）：贪心策略，可能造成饥饿。
  3. SCAN（电梯算法）：磁头来回扫描磁道，公平但可能低效。
  4. C-SCAN（循环SCAN）：仅单向扫描，减少等待时间。
  5. R-SCAN/R-CSCAN：考虑旋转延迟，优化调度。

示例：

  • FIFO调度（500随机读）≈ 7.33s。
  • C-SCAN调度（500随机读）≈ 2.6s（提升近3倍）。

12.2 闪存存储（Flash Storage）

闪存结构与访问方式

  • 基本单元：浮栅晶体管（floating gate transistor），通过电荷存储数据。
  • 操作类型：
    • 擦除（erase）：以擦除块（erasure block，128KB~512KB）为单位，耗时数毫秒。
    • 写入（write）：以页（page，2KB~4KB）为单位，耗时几十微秒。
    • 读取（read）：以页为单位，耗时几十微秒。

闪存转换层（FTL）

  • 功能：逻辑页映射到物理页，避免频繁擦除。
  • 优化技术：
    • 磨损均衡（wear leveling）：分散写入，延长寿命。
    • 垃圾回收（garbage collection）：回收无效页，腾出空间。
    • TRIM命令：通知SSD哪些数据可回收，减少写入放大。

案例研究：Intel 710 SSD

  • 参数：200GB容量，随机读38,500 IOPS，随机写2,000 IOPS。
  • 性能对比：
    • 随机读（500次）≈ 13ms（比磁盘快500倍）。
    • 随机写（500次）≈ 250ms（受垃圾回收影响）。
    • 顺序读/写带宽：270MB/s / 210MB/s。

12.3 总结与未来方向

磁盘 vs. 闪存对比

| 指标 | 磁盘 | 闪存 | |————————|————–|————–| | 容量/成本 | 优（$/GB低） | 良（$/GB较高） | | 顺序带宽 | 良（100MB/s） | 优（200MB/s+） | | 随机IOPS | 差（<200） | 优（>20,000） | | 功耗 | 中（10W+） | 优（<5W） | | 物理尺寸 | 大（3.5”） | 小（可微型化） |

技术趋势

  • 磁盘：容量持续增长（如20TB+），但性能提升缓慢（寻道时间仍≈10ms）。
  • 闪存：密度提高（3D NAND），但写入寿命和成本仍是挑战。
  • 新兴技术：
    • 相变存储器（PCM）：更快写入，更高耐久性。
    • 忆阻器（Memristor）：纳米级存储，接近DRAM速度。

本章强调存储设备的物理特性直接影响文件系统设计，并展望了未来存储技术的发展方向。

第13章：文件与目录

13.1 实现概述

文件系统需要将文件名和文件偏移量映射到物理存储块，同时满足以下四个主要挑战：

  • 性能：通过空间局部性优化访问效率。
  • 灵活性：支持多种文件类型和访问模式。
  • 持久性：确保数据在崩溃或断电后仍可恢复。
  • 可靠性：长期存储数据，即使硬件故障或更新中断。

文件系统通过以下四个关键机制实现这些目标：

  1. 目录：将文件名映射到文件编号。
  2. 索引结构：通过持久化数据结构（如树）定位文件块。
  3. 空闲空间映射：跟踪哪些块是空闲的。
  4. 局部性启发式：优化数据布局以提高性能。

13.2 目录：命名数据

目录是特殊的文件，存储文件名到文件编号的映射。文件系统通过分层目录结构组织文件，例如：

  • 根目录的编号是预定义的（如Unix FFS中为2）。
  • 查找文件时，逐级解析目录（如/home/tom/foo.txt需依次读取根目录、home目录和tom目录）。

目录API：

  • 使用专用系统调用（如create、link、unlink）修改目录，确保一致性。
  • 普通文件读取API（如read）可用于读取目录内容。

目录内部实现：

  • 链表结构：早期实现（如ext2）使用链表存储目录条目，适用于少量文件。
  • 树结构：现代文件系统（如XFS、NTFS）使用B+树或哈希加速大规模目录的查找。

硬链接与软链接：

  • 硬链接：多个目录条目指向同一文件编号，通过引用计数管理。
  • 软链接：存储目标文件的路径名，解引用时需查找目标文件。

13.3 文件：查找数据

文件系统需支持高效随机访问和顺序访问，同时兼顾小文件和大文件的需求。以下是四种文件系统的设计案例：

13.3.1 FAT：链表

  • 索引结构：文件分配表（FAT）是一个链表数组，每个文件对应一条链。
  • 空闲空间管理：FAT条目为0表示空闲块。
  • 局限性：
    • 随机访问需遍历链表。
    • 不支持硬链接和现代可靠性技术。
    • 最大文件和卷大小受限（如FAT-32支持4GB文件）。

13.3.2 FFS：固定树

  • 索引结构：多级索引树（inode包含直接、间接、双重间接指针）。
    • 支持稀疏文件（空洞不占用存储空间）。
  • 空闲空间管理：位图跟踪空闲块。
  • 局部性启发式：
    • 块组放置：将目录及其文件放在同一块组，减少寻道时间。
    • 保留空间：预留10%空间以避免碎片化。

13.3.3 NTFS：灵活树与区段

  • 索引结构：可变深度树，跟踪区段（连续块序列）。
    • 主文件表（MFT）存储文件元数据和区段指针。
    • 小文件数据可直接存储在MFT记录中（驻留属性）。
  • 元数据文件化：MFT本身是一个文件（$MFT），其他元数据（如位图、坏块列表）也存储为文件。
  • 局部性启发式：最佳适应分配策略，支持预分配文件大小（SetEndOfFile）。

13.3.4 写时复制文件系统（如ZFS）

  • 核心思想：更新时不覆盖旧数据，而是写入新位置，将随机写转为顺序写。
  • 优势：
    • 优化RAID和闪存性能。
    • 支持快照和版本控制。
  • ZFS实现：
    • 索引结构：动态树（dnode）跟踪区段，根节点存储在uberblock中。
    • 空间映射：按块组管理空闲空间，使用AVL树和日志结构更新。
    • 写入优化：批量更新和顺序写入。

13.4 综合应用：文件与目录访问

以FFS为例，读取文件/foo/bar/baz的步骤：

  1. 读取根目录inode（编号2）和数据块，找到foo的inode编号。
  2. 读取foo的inode和数据块，找到bar的inode编号。
  3. 重复上述过程，最终读取baz的inode和数据块。
    • 缓存优化：常用目录和inode会被缓存，减少磁盘访问。

13.5 总结与未来方向

  • 技术趋势：
    • 固态存储（如闪存）改变了文件系统设计约束，需优化随机访问和耐久性。
    • 磁盘容量增长快于性能提升，需最大化顺序访问。
  • 工作负载变化：
    • 虚拟化和云计算要求共享存储的性能隔离。
    • 应用程序（如照片管理）可能替代传统目录结构。

第14章：可靠存储

14.1 事务：原子更新

  • 问题背景：系统在更新非易失性存储时若发生崩溃，可能导致部分更新丢失，数据处于不一致状态。
  • 解决方案：
    • 临时方法：早期文件系统（如Unix FFS）通过精心排序写入操作和崩溃后扫描修复（如fsck）确保一致性，但存在复杂性高、更新慢和恢复时间长的问题。
    • 事务抽象：
      • ACID特性：原子性（全部或零）、一致性（状态合法）、隔离性（并发事务互不干扰）、持久性（提交后数据持久化）。
      • 实现技术：
        • 重做日志（Redo Logging）：分为准备（记录更新到日志）、提交（写入提交记录）、写回（更新目标位置）和垃圾回收四个阶段。崩溃恢复时通过日志重放确保原子性。
        • 撤销日志（Undo Logging）：先记录旧值到日志，再更新目标位置，崩溃时恢复旧值。
      • 性能优化：异步写回、组提交（合并多个事务提交）、顺序日志写入。
    • 文件系统中的应用：
      • 日志文件系统：仅对元数据使用事务（如ext3默认模式），数据块直接写入。
      • 日志结构文件系统：所有更新（包括数据）通过事务处理（如ext3可选模式）。
      • 写时复制文件系统（如ZFS）：通过批量更新和意图日志（ZIL）实现高效事务。

14.2 错误检测与纠正

  • 存储设备故障：
    • 扇区/页故障：通过纠错码（ECC）和重映射修复。
    • 整盘故障：通过冗余阵列（RAID）容忍。
  • RAID技术：
    • 镜像（RAID 1）：数据写入两块磁盘，读取任一块，容忍单盘故障。
    • 旋转奇偶校验（RAID 5）：数据分条带存储，每组一个奇偶校验块，分布负载，容忍单盘故障。
    • 双冗余（RAID 6）：每组两个冗余块，容忍双盘故障。
  • 可靠性计算：
    • 数据丢失风险：双盘故障、单盘故障加扇区错误。
    • MTTDL（平均数据丢失时间）：需考虑独立故障假设的局限性（实际故障可能相关）。
  • 提升可靠性：
    • 增加冗余：如三副本或RAID 6。
    • 磁盘清理（Scrubbing）：定期检测并修复潜在错误。
    • 热备盘：快速替换故障盘，缩短修复时间（MTTR）。
    • 分布式恢复（如HDFS）：并行重建数据。
  • 软件完整性检查：
    • 块级校验（如WAFL）：每个块附加校验和与身份信息。
    • 文件系统指纹（如ZFS）：树形结构中每个节点包含子节点校验和，确保全局一致性。

14.3 总结与未来方向

  • 现状：现代存储系统需结合设备级ECC、RAID冗余和文件系统校验，以应对硬件故障。
  • 趋势：分布式多机复制（如Amazon S3）通过跨数据中心冗余和定期校验，提供更高可靠性（如“11个9”的持久性）。