Lec 14 文件系统与设备

License

本内容版权归上海交通大学并行与分布式系统研究所所有
使用者可以将全部或部分本内容免费用于非商业用途
使用者在使用全部或部分本内容时请注明来源
资料来自上海交通大学并行与分布式系统研究所+材料名字
对于不遵守此声明或者其他违法使用本内容者，将依法保留追究权
本内容的发布采用 Creative Commons Attribution 4.0 License
完整文本

文件与系统

• 文件是对数据的一种抽象

  • 文件的定义：有名字且持久化的一段数据

• 文件系统

  • 提供了一组操作文件的API

• UNIX系统API

  • OPEN, READ, WRITE, SEEK, CLOSE
  • FSYNC
  • STAT, CHMOD, CHOWN
  • RENAME, LINK, UNLINK, SYMLINK
  • MKDIR, CHDIR, CHROOT
  • MOUNT, UNMOUNT

INODE：文件的元数据

简单文件系统

• 文件系统的特性与操作
  • 文件系统的特性
    • 文件数量固定：10 个文件
    • 文件名固定：从 “0”到“9”
    • 每个文件的大小固定为 4 KB
    • 10个文件在磁盘上是连续的
  • 文件系统的操作
    • 文件查找：文件名就是磁盘块号
    • 文件读写：即对相应磁盘块的读写
    • 文件删除：不支持

将磁盘抽象成一个大数组，块号为磁盘的索引，每个块的大小为4KB。

• 改进简单文件系统
  • 增加文件的数量
  • 假设使用一个容量为 1 GB 的磁盘，最多保存 1 GB / 4 KB = 256 K个文件
• 支持文件删除操作
  • 引入文件位图（bitmap），大小为256 × 1024 × 1b = 8 × 4KB = 32KB
  • 每个bit对应一个文件，若bit为0表示不存在，bit为1表示存在
  • 删除文件时，将该文件对应的bit设置为0

• 仍然存在限制
  • 文件大小固定
    • 无法支持大于一个磁盘块（4KB）的文件
    • 文件系统依赖文件数据存储的连续性
  • 文件名固定
    • 只能用磁盘块号来表示文件名

引入inode

• 引入inode：index node
  • 记录多个磁盘块号
  • 头部记录文件size信息
  • 每个文件对应一个inode
  • 称为文件元数据（Metadata）
• 文件读写操作
  • 给定inode和文件内偏移（offset）
  • 根据offset计算出对应的磁盘块号
  • 若offset超出size则返回错误

• inode表：记录所有inode

  • 可以看成inode的大数组
  • 每个inode使用inode号作为索引
  • 此时，inode号即为文件名

• inode分配信息（位图）

  • 记录哪些inode已分配，哪些空闲

• 超级块：Super Block

  • 记录磁盘块的大小、其他信息的起始磁盘块位置，等等
  • 是整个文件系统的元数据

• 加载文件系统

  • 首先读取超级块，然后找到其他信息

• 创建新文件

  • 根据inode分配信息找到空闲inode，将inode对应的bit设置为1
  • 返回inode在inode表中的索引，作为文件名

• 查找文件（根据inode号）

  • 在inode表中根据inode号定位该inode

• 删除文件

  • 在inode分配表中，将该inode对应的bit设置为0

• 单级inode太大啦

• 一个4GB的文件，对应inode有多大？

  • 假设磁盘块号（块指针）为8-Byte（64-bit）
  • inode大小：4GB/4KB * 8 = 8MB
  • 若文件大小为4TB，则inode大小为8GB！

• 一个多级inode占用的空间很少。我们设计一个inode，假设如下：
  • 一共只有15个指针（即记录磁盘块），这些指针占用120-Byte
  • 包含12个直接指针，3个间接指针，1个二级间接指针
  • 文件最大为：4K x 12 + 4K x 512 x 3 + 4K x 512 x 512 = 48K + 6M + 1G
• 如何支持更大的文件？
  • 可以启用三级索引，甚至四级索引
  • 与页表有所不同！页表储存的是虚拟地址到真实地址的转换索引，每一层级页表都会占用真实的物理空间。而磁盘的inode表（类似对应于0级页表）与磁盘数据区域是分开的，不会一同计算。
  • 格式化后，需要填写inode表指明每个磁盘的块，则超级块，存储块分配信息，inode分配信息和表格会占有一部分位置，因此会比表明的空间小一些。

目录也是文件

inode与文件名

• inode本身已经包含了一个文件的所有信息
  • 可以使用inode号（inode表的索引）作为文件名
  • 给定一个inode号，就可以访问文件的所有数据
• inode作为文件名的缺点
  • 名字很难记住，不够 user-friendly
  • 名字依赖于inode表位置的名字
  • 一旦改变了位置，就必须改变文件名
• 以字符串作为文件名的好处
  • 在操作文件时，将文件的元数据隐藏起来，用户无需感知
  • 不依赖特定的存储设备
• 如何实现字符串文件名到inode号的映射？
  • 使用映射表，记录字符串到inode号的映射
  • 将该表保存在一类特殊的文件中，称为目录文件
    • 目录本身也是一个文件，同样有inode
  • 复用inode机制来实现目录！

• 目录中的每条映射称为一个目录项
  • 每一条目录项记录了一个inode号与文件名字符串的映射
  • 一个目录可以记录很多目录项
• 目录文件的大小（占用空间）
  • 与其记录的文件大小无关
  • Q：与什么因素有关？
  • “目录” VS. “文件夹”
• 目录支持查找操作
  • 给定一个目录文件和字符串
  • 在目录文件中查找字符串，并返回对应的inode
• 目录中可以记录子目录，因为目录本身也是一个文件。
  • 通过“/”来分割父目录和子目录
• 最顶端的目录没有目录名（文件名）
  • 被称为“根目录”（root）
  • 根目录没有文件名，在“/”的前面什么都没有
• 绝对路径和相对路径
  • 绝对路径：如“/home/alice/test.md”
  • 相对路径：如“./test.md”

1. 寻找根目录。我们的根目录在inode表中的第一个inode。
2. 文件路径还没有结束，继续索引。inode-1的最后一项指向索引块。前往数据块33.
3. 对数据块内存储的块分别进行寻找。在块31中，我们找到了os-book目录，需要回到inode表内去寻找对应的inode号。
4. 回到inode表，找到inode号63内存储的数据块inode号。因为最后的是一个文件，因此逐个寻找对应。
5. 在29号数据块内找到了对应的文件，其在inode表内存储为58号。
6. 依次读取表内的数据块号，如果遇到了索引号则继续读取，直到文件读取结束。

软链接和硬链接

硬链接

• 硬链接创建：ln命令
• LINK
  • LINK("Mail/inbox/new-assignment", "assignment")
  • 将严格的层次结构（树）变成有向图
    • 注意：用户不能为目录创建link
  • 不同的文件名可以指向同一个inode号
• UNLINK
  • 删掉从文件名到inode号的绑定关系
  • 如果 UNLINK 最后一个绑定，则把 inode 和对应的 blocks放到 free-list
    • 每个文件都需要一个 reference counter
• 引用计数器（Reference count）
  • 一个 inode 可以绑定多个文件名
    • LINK 时 +1, UNLINK 时 -1
  • 当reference count为0时，文件被删除
  • 不允许出现环
    • 除了 '.' 和 '..'
    • 用来表明当前目录和上一层目录而不需要知道它们实际的名字

为什么LINK不能成环？

• /a/b是一个目录，a的引用次数为1。a的inode号为25.
• 执行LINK(/a/b/c, a)，形成了一个环，a的引用次数为2。
• 执行UNLINK(/a)，删除了一条引用。因为a的引用次数为1，所以不能删除。这下谁也找不到inode 25了。

软链接

• 软连接创建ln -s，windows好像叫做快捷方式。
• 如何在一个磁盘上建立指向另一个磁盘的Link？
  • 无法，因为不同磁盘的 inode 命名空间是不同的（因为文件系统不同）
• 一种简单的方案
  • 让inode在所有磁盘中是唯一的，显然不可行
• 引入软链接（符号链接）: soft link (symbolic link)
  • SYMLINK
  • 增加一种新的 inode 类型

• 目录上下文转变的例子。设当前目录为Desktop。
• 假设有一个目录: "./Scholarly/programs/www"
• 目录下包含一个soft link
• "./web" -> "./Scholarly/programs/www"
• 运行如下命令
• cd web
• cd ..
• 当前是哪个目录？
  • Desktop
• cd -p ..
  • programs

文件系统的细节

• 文件名并不是文件的一部分
  • 文件名不是文件的数据，也不是文件的元数据（inode）
  • 文件名是目录的数据，是文件系统的元数据
  • 一个inode可以有多个文件名（硬链接）
• 每个硬链接的地位都是相同的
  • 文件名就是硬链接（而不是一个文件名，一个链接名）
• 目录所占磁盘空间通常是很小的
  • 目录仅仅负责记录文件名到inode号的映射
  • "文件夹"这个名字有一定的误导性

文件系统API

• 应用程序通过系统调用使用这些 API
  • CHDIR, MKDIR, RMDIR
  • CREAT, LINK, UNLINK, RENAME
  • SYMLINK
  • MOUNT, UNMOUNT
  • OPEN, READ, WRITE, CLOSE
  • SYNC
• 文件系统的两类元数据
  • 磁盘上文件的元数据：静态的、在磁盘中
  • 被打开文件的元数据：动态的、在内存中

文件的元数据（磁盘中）

• 拥有者/所在组 ID
  • 拥有该 inode 的 用户 ID 和 组 ID
• 权限的类型
  • 拥有者、所在组、其他
  • 读、写、执行
• 时间戳
  • 最后一次访问 (如：READ 操作)
  • 最后一次修改 (如：WRITE 操作)
  • 最后一次 inode 更新 (如：LINK 操作)

POSIX定义的部分文件元数据

被打开文件的元数据（内存中）

• 整个系统维护了一个 file_table
  • 记录了所有打开的文件的信息
  • 包括：文件游标（file cursor）、引用数（ref_count）
  • 父子进程间可以共享文件游标
• 每个进程维护了一个 fd_table
  • 记录了该进程每个 fd 所对应文件在 file_table 中的索引
• 文件游标
  • 记录了一个文件中下一次操作的位置
  • 可以通过 SEEK 操作修改
• 情况 1: 共享游标
  • 父进程将 fd 传递给子进程
    • UNIX 中，子进程会继承父进程所有已经打开的 fd
  • 允许父子进程共享同一个文件
• 情况 2: 非共享游标
  • 两个不同的进程打开同一个文件

• write() 与 read() 类似

  • 可能需要分配新的 block
  • 更新 inode 的 size 和 mtime

• close()

  • 释放 fd_table 中的相关项
  • 减小 file table 中相关项的 refcnt
  • 如果 file table 中相关项 refcnt 为 0，则将其释放

• 删除一个打开的文件

• 进程P1打开了文件 A

  • 运行 open，在 file_table 和 fd_table 中都增加了一项

• 进程P2将文件 A 删除

  • 删掉了指向文件 A 的最后一个目录项
  • 文件 A 的 inode 引用数变成了 0

• 文件 A 的 inode 不会被立即释放和删除

  • 直到前一个进程调用 close 将其关闭
  • （在 Windows 上，则通过"禁止删除打开的文件"实现类似效果）

• fsync

• Block cache

  • 缓存了最近被使用的磁盘块
  • 缓存缺失时，从磁盘中读取
  • 推迟数据向磁盘的写入
  • 寻求机会批量写入，提升性能
  • 问题：如果在写入前发生故障，可能会造成不一致

• SYNC

  • 保证对文件的所有修改被写入到存储设备

文件系统的崩溃一致性

• 文件系统中保存了多种数据结构
• 各种数据结构之间存在依赖关系与一致性要求
  • inode中保存的文件大小，应该与其索引中保存的数据块个数相匹配
  • inode中保存的链接数，应与指向其的目录项个数相同
  • 超级块中保存的文件系统大小，应该与文件系统所管理的空间大小相同
  • 所有inode分配表中标记为空闲的inode均未被使用；标记为已用的inode均可以通过文件系统操作访问
• 突发状况（崩溃）可能会造成这些一致性被打破！

• 重启并恢复后

1. 维护文件系统数据结构的内部的不变量
   例如, 没有磁盘块既在free list中也在一个文件中
2. 仅有最近的一些操作没有被保存到磁盘中
3. 没有顺序的异常

• 方法一：同步元数据写+fsck

• 同步元数据写

  • 每次元数据写入后，运行sync()保证更新后的元数据入盘

• 若非正常重启，则运行fsck检查磁盘，具体步骤：

  • 检查superblock
    • 例：保证文件系统大小大于已分配的磁盘块总和
    • 如果出错，则尝试使用superblock的备份
  • 检查空闲的block
    • 扫描所有inode的所有包含的磁盘块
    • 用扫描结果来检验磁盘块的bitmap
    • 对inode bitmap也用类似方法
  • 检查inode的状态
    • 检查类型：如普通文件、目录、符号链接等
    • 若类型错误，则清除掉inode以及对应的bitmap
  • 检查inode链接
    • 扫描整个文件系统树，核对文件链接的数量
    • 如果某个inode存在但不在任何一个目录，则放到/lost+found
  • 检查重复磁盘块
    • 如：两个inode指向同一个磁盘块
    • 如果一个inode明显有问题则删掉，否则复制磁盘块一边给一个
  • 检查坏的磁盘块ID
    • 如：指向超出磁盘空间的ID
  • 检查目录
    • 这是fsck对数据有更多语义的唯一的一种文件
    • 保证 . 和 .. 是位于头部的目录项
    • 保证目录的链接数只能是1个
    • 保证目录中不会有相同的文件名

• 问题：方法一太慢了，同步元数据写导致创建文件操作非常慢

• 方法二：日志(journaling)

• 在进行修改之前，先将修改记录到日志中

  • 如：如何修改block-bitmap、如何修改data

• 所有要进行的修改都记录完毕后，提交日志

• 确定日志落盘后，再修改数据和元数据

• 修改完成后，删除日志

• example: Ext4的日志

• Data mode（即 full journaling）

  • 数据和元数据都写入日志区域

• Ordered mode（默认配置）

  • 先写数据（原本的文件位置），再写元数据（日志）

• Writeback mode

  • 仅仅将元数据写入日志
  • 数据依然写入原本的位置
  • 日志和数据之间没有顺序保证

• 崩溃后基于日志恢复
• 启动后首先检查日志区域
  • 若没有任何日志记录，则无需恢复
• 扫描所有已经COMMIT的事务
  • 若没有COMMIT的事务，则无需恢复
  • 对已经COMMIT的事务，将元数据从日志区写到原本位置
• 完成后清空日志区域