Series Four of Basic of Persistence - File System Implementation

• 本篇为持久化技术的基础篇系列第四篇（文件系统实现），将以 vsfs 为例。

Chapter Index

• Basic of Persistence
  • Flavor of IO
  • I/O Devices
  • Hard Disk Drives
  • Files and Directories
• File Systems Implementation
• Locality and The Fast File System
• Crash Consistency: FSCK and Journaling
• Log-structured File System

File System Implementation

• CRUX：如何实现一个简单的文件系统？

The Way To Think

• 文件系统如何管理其数据和元数据？ 数据结构
• 如何将系统调用映射成对相应的数据结构的访问？ 访问方法

Overall Organization

• 如何组织磁盘？将磁盘划分成 blocks，假设单个块大小为 4KB。划分之后块从 0 ~ N-1 开始寻址。假设我们有一个小磁盘，只有 64 blocks
  
• 如何将数据存放到这些块中？
  • 因为数据大部分都是用户实际有效的数据，所以我们划分出数据区域。即后 56 个区域为数据区。
    
  • 还要跟踪每个文件的信息，即一组元数据。所以划分出相应的元数据区域。如图中所示的 inode table.
    
  • 还需要追踪 inode 和 data 两个区域中哪些块已经被分配或者空闲，即分配结构，通常是位图。又需要区分为 inode bitmap 和 data bitmap
    
  • 还剩了一个块，通常作为超级块。通常包括文件系统的相关信息，inodes 和数据块的数目，inode table 起始块地址，magic number等
    
• 所以当挂载一个文件系统的时候，操作系统会首先读取超级块信息，从而初始化各种变量并把文件系统目录树和实际的卷关联起来。当卷中的文件被访问时，才知道从磁盘的哪个位置去读取对应的数据。

File Organization: The Inode

• inode 全称 index node。每一个 inode 都有对应的 i-number，即前面章节提到的 low-level name。在 vsfs 中，有了 inode-number，就能计算出 inode 所在的位置。如上图所示例子中，使用了 5 blocks 共 20KB 的容量，假设每个 inode 大小 256B，那么将能容纳 80 个 inodes。inode 的起始地址为 12KB
  
• 由于磁盘不是字节寻址的，通常是由可寻址的扇区组成，每个扇区的大小通常为 512 bytes。inode 32 对应的地址可以计算出来为 20KB，因此在磁盘上则是 20 * 1024 / 512 = 40，即扇区号为 40 的扇区 。
• inode 中存放的数据信息如下，我们又称元数据信息。
  
• inode 设计中最重要的决策之一是如何引用数据块的位置。z最简单的方式就是用 inode 内部的指针去指向数据块，每个指针指向一个数据块，但该方法有一定的局限：即文件特别大，对应的数据块数量大于 inode 中允许的数据块指针数量。

The Multi-Level Index

• 为了引用更大的文件，文件系统必须引入新的数据结构。一个办法就是用一个特别的指针，我们称之为 indirect pointer，这个指针不指向包含用户数据的数据块，而是指向包含更多的指向数据块的指针的数据块。因此，一个 inode 通常有确定数量（12个）的 direct pointer 和一个 indirect pointer
• 当文件越来越大之后，一个 indirect block 将会从 data block 区域中分配，然后将 inode 中的 indirect pointer 指向该 indirect block。假设一个块大小为 4KB，地址为 4B，那么一个块可以容纳 1024 个指针，那么这个文件最大即为 1024+12=1036 个块大小
• 如果为了支持更大的文件，即使用 double indirect pointer，如果更大，即 triple indirect pointer。继续加索引，也就是所谓的多级索引。double indirect pointer 即对应 （12 + 1024 + 1024*1024）个块大小的文件，此时已经超过 4G
• Linux ext2/ext3, NetApp’s WAFL 以及 UNIX 原始的文件系统都使用了多级索引；而 SGI XFS，Linux ext4 则使用的是 Extent 机制来代替多级索引。

• 一个 Extent 是指一个磁盘指针加上一个数据块的长度来表示，而不用对文件内的每一个数据块都维护指针，整个文件就只需要一个指针和一个长度从而定位到具体的地址。但是一个单独的 Extent 有很大的局限，因为可能很难找到一个足够大的且连续的空间，因此基于 Extent 的文件系统通常允许多个 Extent，从而在分配空间时就提供了更多的自由。
• 相比于多级索引，多级索引更加灵活，但是可能会使用更多的元数据，即元数据可能相对更大，但是 Extent 这种方式相对更加死板，但是占用空间更少。特别是，当磁盘上有足够的空闲空间并且文件可以连续布局时(这实际上是任何文件分配策略的目标)，基于 Extent 的方法显得更好。
• Ext4文件系统之文件数据组织

• 研究人员发现大多数文件都很小，这种不平衡的设计反映了这样一个现实;如果大多数文件确实很小，那么在这种情况下进行优化是有意义的
  

Other

• 设计 inodes 的另一个办法是使用链表。inode 中不用存储多个指针，只需要存储文件的第一个块对应的指针，如果是比较大的文件，再加一个指针指向最后一个数据块。但这种链式的文件分配方法有时候可能性能较差，考虑读文件的最后一个块的时候，或者做随机的访问的时候。
• 为了让这种链式分配的方式更高效，很多系统会维护一个 link information 表在内存中，而不是用数据块本身存储下一个指针，该表由数据块 D 的地址索引，对应的 entry 内容则为 D 的下一个指针。，即文件中 D 之后的数据块的地址，也可能存在空值(表示文件结束)，或者其他一些标记，表示特定的块是空闲的。拥有这样一个下一个指针表使得链接分配方案可以有效地进行随机文件访问，只需首先扫描(在内存中)表中找到所需的块，然后直接访问(在磁盘上)它。
• file allocation table (FAT file system) 就是这样实现的，和标准的 UNIX 文件系统也有很大的不同。它本身没有 inode 节点，而是存储关于文件的元数据并直接引用该文件的第一个块的目录条目，这使得不可能创建硬链接

Directory Organization

• 在许多文件系统中，目录都是一个比较简单的结构。一个目录通常包含一组数据对（entry name, inode number）。在指定目录下的每一个文件和目录，在目录对应的数据块中都存放着对应的字符串和数字。对于字符串可能还会存储对应字符串的长度。
• 例如 dir 中存储着 foo,bar,foobar_is_a_pretty_longname 三个文件，对应的 inode-number 为 12，13，24。dir 上的磁盘数据大致如下： inode number, record length (the total bytes for the name plus any left over space), string length (the actual length of the name), and finally the name of the entry.

• 删除操作可能会造成目录所对应的数据块中间为空白，因此需要标记以下这部分空白的空间，例如使用保留的 inode number 来表示。为什么要使用记录长度 record length？就是为了在删除操作之后，新的数据对信息可以重用被删除的记录对应的空间，但是可能需要record length 来计算是否还有额外的空间剩余。
• 文件系统把目录当成一种特殊的文件，不是常规的文件，会对应的 inode 存取的数据中的 type 类型设置为 directory。目录有索引节点指向的数据块(可能还有间接块);这些数据块位于简单文件系统的数据块区域中。因此，我们的磁盘结构保持不变。
• 需要注意的是对于目录数据的存取，简单的线性表不是唯一的办法，任何其他的数据结构也是可能的。比如，XFS 使用 B-tree 存储目录，使得文件的创建操作（创建之前需要确保该文件名没有被使用）比简单的链表更快，因为链表必须遍历一次才能执行创建。

Free Space Management

• 文件系统必须跟踪哪些inode和数据块是空闲的，以便在分配新文件或目录时，能够为其找到空间。因此，自由空间管理对所有文件系统都很重要。在vsfs中，这个任务有两个简单的位图。
• 创建文件之前首先需要分配一个 inode，因此首先看 inode bitmap 中是否有空闲的 inode 可供分配，分配之后则标记 inode 被使用过了，然后更新磁盘上的位图。数据块操作同理。
• Linux 文件系统 ext2/ext3 在创建文件时，将要寻找一组空闲的块序列（通常为 8 个块），找到之后分配给新创建的文件，文件系统保证文件的一部分在磁盘上是连续的，从而提高了性能。这种 pre-allocation 策略在数据块分配时是一种常用的分配方式。

• 空闲空间的管理方式有很多种，位图就是其中一种，早期的使用 free lists 的文件系统则是用一个在超级块中的指针指向第一个空闲块，而空闲块中又保存了下一个空闲块的指针，从而形成一个空闲块的列表。当使用空闲块的时候，相应的更新指针。
• XFS 使用 B-tree 来简洁地标识磁盘的哪些块是空闲的

Access Paths: Reading and Writing

• 举例之前，首先假设文件系统已经挂在，且超级块信息已经读取到内存，其他数据都还在磁盘上。

Reading A File From Disk

• 例子：打开一个文件 /foo/bar，读取数据，然后关闭该句柄。假设文件大小为 12KB，3 个块大小。
  
• 当进行 open 操作的时候，文件系统首先需要找到文件 bar 的 inode，即获取到该文件对应的基础信息，包括权限信息和文件大小等。但是现有的参数时文件对应的绝对路径，所以需要遍历的路径才能找到对应的信息。
  • 首先读取根目录 / ，即获取根目录对应的额 inode，获取 inode 需要知道对应 i-number，通常需要从其父目录中才能获取到对应 i-number，但是根目录没有父目录，所以根目录的 i-number 就是一个众所周知的值，因为文件系统必须知道文件系统挂载在哪里以及挂载到了什么地方。在大多数 UNIX 文件系统中，根目录对应的 inode number 是 2，因此首先读取 i-number 号为 2 的 inode 数据，即第一个 inode block。
  • 一旦读取了根目录的 inode，文件系统就能找到该 inode 对应的数据块信息，即根目录所包含的文件条目。因此FS 将使用这些磁盘上的指针来读取目录，在本例中查找 foo 的条目，读取了多个条目之后找到了该目录，然后发现了该目录对应的 i-number，假设为 44，然后继续
  • 下一步是递归地遍历路径名，直到找到所需的 inode。本例中继续在 foo 中找到 bar 的 inode number。open 的最后一步操作就是将 bar 的 inode 读取到内存中，然后文件系统做最后的权限检查，并为当前进程中的 open file table 分配一个文件描述符，然后返回给用户。
• open 之后发起读操作，第一次读会读文件的第一个数据块，所以首先需要访问 inode 中查看第一个数据块的位置，与此同时，可能会更新 inode 中存储的最近访问时间，读取操作之后可能还会更新内存中的 open-file table 对应的额该文件描述符的信息，因为需要更新文件对应的偏移量以便读取下一个数据块。
• 需要注意的是，open 操作引发的 read 的数量和路径长度成比例，因为每多一个目录，我们就需要额外的访问一次该目录对应的元数据和数据，如果是大目录的话，可能会更糟。示例中我们都只需要通过读取一个块就能获取到该目录的全部数据信息，如果是大目录，可能需要读取大量数据块来才能找到对应的数据条目。

Writing A File To Disk

• 写文件流程和读文件类似，就是把对应的读操作换成写操作。但是和读文件不同的是，写文件需要分配对应的块，避免原有的数据被覆盖，每一次写不仅需要写数据到磁盘，还要决定分配哪个块给文件，因此还要更新其他数据结构，如 bitmap 和 inode。因此一次写操作可能会产生至少 5 次 I/O：
  • 读 data bitmap，寻找空闲的 data block
  • 写 data bitmap，分配之后更新对应的 bitmap
  • 对 inode 的读写，即更新新的数据块信息到 inode
  • 最后写实际的数据块
• 如果是创建文件的操作，可能更为复杂。创建操作不仅要分配 inode，还要将该文件所在的目录所包含的空间进行分配，I/O 流量将特别高：
  • 读取 inode bitmap 寻找空闲的 inode block
  • 写 inode bitmap，分配之后对应更新 bitmap
  • 对应的更新自己的 inode 和所在目录的 data（父目录保存了 i-number 和文件名对应的数据对）
  • 对自己父目录的 inode 的读取和更新
  • 如果目录需要增长以容纳新创建的文件的话，则需要分配新的块，将会导致更多的 I/O
    
• CRUX：文件系统如何以合理的效率完成这些任务呢？如何减少文件系统的 I/O 次数？

Caching and Buffering

• 为了解决这一明显的巨大性能问题，大多数文件系统积极使用系统内存(DRAM)来缓存重要的块。
• 早期的文件系统引入了固定大小的缓存来保存流行的块，正如我们对虚拟内存的讨论一样，LRU 等策略和不同变体将决定在缓存中保留哪些块。这个固定大小的缓存通常在引导时被分配为占总内存的 10%
• 然而，这种内存的静态分区是很浪费的;如果文件系统在某个时间点不需要10%的内存怎么办? 使用上面描述的固定大小的方法，文件缓存中未使用的页面不能被重新用于其他用途，就是一种浪费
• 相比之下，现代系统采用 动态分区 方法。特别是，许多现代操作系统将虚拟内存页面和文件系统页面集成到统一的页面缓存中。通过这种方式，可以在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定的时间内需要多少的内存。

• 静态分配只将固定的资源分配一次，例如，如果内存有两个可能的用户，您可以将一部分固定的内存分配给一个用户，将其余部分分配给另一个用户
• 动态方法更加灵活，它会随着时间的推移而给出不同数量的资源。例如，一个用户可能在一段时间内获得较高百分比的磁盘带宽，但随后，系统可能会切换并决定给另一个用户更大比例的可用磁盘带宽。
• 每种方法都有其优点。静态分区确保每个用户获得资源的一部分，通常提供更可预测的性能，而且通常更容易实现。动态分区可以实现更好的利用率(通过让资源紧缺的用户使用其他空闲资源)，但是实现起来更复杂，并且可能导致用户的性能下降，这些用户的空闲资源被其他人使用，然后需要很长时间才能回收。通常情况下，没有最好的方法;相反，您应该考虑手头的问题并决定哪种方法最合适。

• 让我们再考虑一下缓存对写操作的影响。虽然读 I/O 可以通过足够大的缓存完全避免，但写流量必须进入磁盘才能持久化。因此，缓存对写流量的作用与对读流量的作用不同。
  • 首先，通过延迟写操作，文件系统可以将一些更新批处理到更小的 I/Os 集合中。比如 如果在创建一个文件时更新inode 位图，然后在稍后创建另一个文件时更新，则文件系统通过在第一次更新之后延迟写操作来节省一次 I/O。
  • 其次，通过在内存中缓冲大量的写操作，系统可以调度后续的 I/Os，从而提高性能
  • 最后，有些写操作通过延迟完全避免了。例如，如果应用程序创建了一个文件，然后删除了它，那么延迟写操作以将文件创建反映到磁盘可以完全避免这些操作。在这种情况下，惰性(将块写入磁盘)是一种优点
• 大多数现代文件系统都会将写操作缓存在内存中大约 5~30s，也是一种 trade-off。如果系统在写操作落盘之前挂掉的话，写操作肯定会丢失，但是如果保存在内存越久，性能就能通过批量写、延迟写、调度等策略变得更好。本质是 DURABILITY/PERFORMANCE TRADE-OFF

• 存储系统常常需要做 持久性和性能之间的 trade-off。如果用户希望写入的数据能够立即持久，则系统必须将新写入的数据提交到磁盘，因此写入速度较慢(但安全)。但是，如果用户可以容忍丢失少量数据，系统可以在内存中缓冲写入一段时间，然后将它们写入磁盘(在后台)。这样做可以使写入看起来很快完成，从而提高感知性能;但是，如果发生崩溃，还没有提交到磁盘的写就会丢失，因此需要进行权衡。
• 需要结合实际的场景中对于持久化的需求再做权衡。

• 数据库系统常常为了避免不必要的数据丢失就强制写操作刷入磁盘，通过使用 fsync，缓存模式时使用 diret I/O 或者直接使用裸设备接口避免文件系统的缓存。虽然大多数应用程序都需要文件系统进行权衡，但是如果默认值不理想，有足够的控制可以让系统执行您希望它执行的操作。

Homework

• 模拟文件系统的状态变化 vsfs.py