Qifan Wang
The Jungle Book
A blog for programming

MIT 6.S081 Lecture 14: File System

We all need people who will give us feedback. That’s how we improve.

6.S081第十四课，需要阅读课本第八章除 logging 外的章节，学习文件系统的知识。

Why are file systems useful and interesting?

文件系统帮助OS实现持久性，数据内容命名组织与用户共享。FS有许多有趣的问题，

  • crash recovery
  • performance/concurrency
  • sharing
  • security

同时文件系统帮助抽象，如 pipes, devices, /proc, /afs 等。所以面向FS的程序可以处理多种对象。

FS API

API example – UNIX/Posix/Linux/xv6/etc:

  fd = open("x/y", -);
  write(fd, "abc", 3);
  link("x/y", "x/z");
  unlink("x/y");
  write(fd, "def", 3);
  close(fd);
  // file y/z contains abcdef

在 UNIX FS API 可见许多高级抽象，

  • objects: files (vs virtual disk, DB)
  • content: byte array (vs 80-byte records, BTree)
  • naming: human-readable (vs object IDs)
  • organization: name hierarchy
  • synchronization: none (vs locking, versions)
    • link()/unlink() can change name hierarchy concurrently with an open()

同时也有其他FS API，有时因 FS 而异。但通常 FS API 都有一些假设，

  • 文件描述符 fd 引用的内容会保留，即使文件名改变或文件在打开时被删除。
  • 一个文件可以有多个链接 link 。也就是一个文件可以存在于多个目录下，没有一个存在是特殊的。所以文件信息并不在目录下。p.s. 这是通常说的硬链接。
  • FS 一般记录文件信息于磁盘的 inode 中。FS 通过 i-number 索引 inode (可将 i-number 看作内部版本的 fd )。inode 有链接计数与 open fd 计数。只有最后的链接与 fd 结束，一个 inode 才会 deallocation 。

Xv6 File System

分层看 FS ,

  • system calls
  • name ops FD ops
  • inodes
  • inode cache
  • log
  • buffer cache
  • virtio_disk driver

数据存储在持续性介质，即无电也能保留在磁盘上，一般的存储介质，

  • hard disk drives (big but slow, inexpensive)
  • solid state drives (smaller, but fast, and more expensive)

历史原因，磁盘一般以 512 字节为一个 sector (扇区) 单位进行读写。

hard disk drives (HDD) 的特点，

  • concentric tracks
  • each track is a sequence of sectors
  • head must seek, disk must rotate
    • random access is slow (5 or 10ms per access)
    • sequential access is much faster (100 MB/second)
  • ECC(error-correcting code) on each sector
  • can only read/write whole sectors
    • thus: sub-sector writes are expensive (read-modify-write)

solid state drives (SSD) 的特点，

  • non-volatile “flash” memory
  • random access: 100 microseconds
  • sequential: 500 MB/second
  • internally complex – hidden except sometimes performance
    • flash must be erased before it’s re-written
    • limit to the number of times a flash block can be written
    • SSD copes with a level of indirection – remapped blocks

可以发现，对于 HDD 与 SSD 而言，顺序读写快于随机读写，大规模读写(按sector计)优于 sub-sector 读写。这两点影响了 FS 的设计与性能。

大部分 OS 用 disk blocks 的设计，减少 book-keeping (a process of recording and organizing all the transactions that have occurred) 与 寻道 (HDD需要寻道) 开销。例如， 4 KB = 1 block = 8 sectors 。 xv6 使用 2-sector block 。

on-disk layout

xv6 将硬盘当作 sectors/blocks 的数组，忽略硬盘的物理性质。

  • 0: unused
  • 1: super block (size, ninodes)
  • 2: log for transactions
  • 32: array of inodes, packed into blocks
  • 45: block in-use bitmap (0=free, 1=used)
  • 46: file/dir content blocks
  • end of disk

xv6 的 mkfs 程序会为一个空的 FS 生成布局 layout 。这个布局在这个 FS 的生命周期内是静态的。除了文件内容，磁盘上其他内容都可视作元数据，如 super block, i-nodes, bitmap, directory content 。

on-disk inode 记录“描述文件的信息”，每一个 inode 有一个唯一 i-number

  type (free, file, directory, device)
  nlink
  size
  addrs[12+1]

p.s. 书上写 inode 不仅可在硬盘中，也可加载到内存中。所以这里有区分。

xv6 的 directory contents 类 UNIX。目录很像文件，但用户不能直接写。目录内容是一个 dirents 数组。p.s. dirent = directory entry

  dirent:
    inum
    14-byte file name

如果 inum 为 0 则 dirent 是空闲的。

我们可以将 FS 看作磁盘上的数据结构，其用于分配 inode 与 block 。

Real World

现实世界的操作系统的 buffer cache 要比xv6复杂得多，但它具有相同的两个目的：缓存和同步对磁盘的访问。与 V6一样，Xv6的缓冲区缓存使用简单的最近最少使用(LRU)清除策略；可以实现许多更复杂的策略，每种策略都适合某些工作负载，但不适合其他工作负载。一个更有效的LRU缓存会消除链表，取而代之的是使用哈希表进行查找，使用堆进行LRU移除。现代缓冲缓存通常与虚拟内存系统集成以支持内存映射文件。

XV6使用与早期Unix相同的基本磁盘和目录布局。多年来，该计划一直非常持久。BSD的UFS/FFS和Linux的Ext2/Ext3从本质上使用相同的数据结构。文件系统布局中最低效率的部分是目录，该目录需要在每个查找过程中对所有磁盘块进行线性扫描。当目录只有几个磁盘块时，这是合理的，但是对于持有许多文件的目录来说很昂贵。Microsoft Windows的NTF，MacOS的HFS和Solaris的ZFS仅举几例，将目录实现为一盘平衡的块状树。这很复杂，但保证了对数时间的目录查找。

Xv6对磁盘故障很简单:如果磁盘操作失败，Xv6会 panic 。这个选择取决于硬件。如果操作系统位于使用冗余来掩盖磁盘故障的特殊硬件之上，也许操作系统很少看到故障，因此恐慌是可以的。另一方面，使用普通磁盘的操作系统应该预料到故障，并更优雅地处理它们，这样一个文件中的块丢失就不会影响文件系统其余部分的使用。

Xv6要求文件系统适合于一个磁盘设备，并且大小不能改变。由于大型数据库和多媒体文件的存储要求越来越高，操作系统正在开发消除每个文件系统一个磁盘瓶颈的方法。基本方法是将多个磁盘组合成一个逻辑磁盘。像RAID这样的硬件解决方案仍然是最流行的，但目前的趋势是在软件中实现尽可能多的这种逻辑。这些软件实现通常允许丰富的功能，如通过动态添加或删除磁盘来增加或缩小逻辑设备。当然，可以动态增长或收缩的存储层需要具有相同功能的文件系统：xv6使用的固定大小的inode块数组在这种环境中不能很好地工作。将磁盘管理从文件系统中分离出来可能是最干净的设计，但是两者之间复杂的接口导致一些系统(如Sun的ZFS)将它们结合起来。

Xv6文件系统缺乏现代文件系统的许多其他特性。例如，它缺乏对快照和增量备份的支持。

现代的UNIX系统允许使用与磁盘存储相同的系统调用访问多种资源：命名管道，网络连接，远程接收的网络文件系统以及监视和控制界面（例如 /proc）。这些系统通常会给每个打开的文件一个函数指针的表，一个指针对应一个操作，并调用函数指针以调用 inode 的实现。网络文件系统和用户级文件系统提供了将这些调用转换为网络RPC的功能，并在返回之前等待响应。

Conclusion

这节课主要讲了 File System 的用途，通用设计以及 xv6 的设计实现。需要重点注意的就是 inode 的设计与底层磁盘的布局。Linux 会使用 VFS (virtual file system) 对存储文件系统( storage system)，如 EXT2 ，NTFS 等，额外做一层抽象。这节课教授的 FS 是指存储文件系统。而 CSAPP 提到的 open file table 与 v-node table 则属于 VFS 范畴。

Reference

  1. 6.S081
  2. 课本

Table of Contents