想徒手写个文件系统?来一起呀

共 6382字,需浏览 13分钟

 ·

2024-04-11 08:53

本文来自我的大规模数据系统专栏《系统日知录》,专注存储、数据库、分布式系统、AI Infra 和计算机基础知识。欢迎订阅支持,解锁更多文章。你的支持,是我前行的最大动力。

主要“编译”自书籍《Operating Systems: Three Easy Pieces[1]》第 40 章,这是一本非常深入浅出的书,推荐给所有对操作系统感到迷茫的同学。本文件系统基于一个非常小的硬盘空间,以数据结构读写流程为主线,从零到一的推导出各个基本环节,可以帮你快速建立起对文件系统的直觉。

文件系统基本都是构建于块存储之上的。但当然,现在的一些分布式文件系统,如 JuiceFS[2],底层是基于对象存储的。但无论块存储还是对象存储,其本质都是按 “数据块” 进行寻址数据交换的。

我们首先会探讨一个完整的文件系统在硬盘上的数据结构,也即布局;然后再通过打开关闭、读写流程将各个子模块串起来,从而完成对一个文件系统要点的覆盖。

总体布局

假设我们的块大小是 4KB,然后有一块非常小的硬盘,只有 64 个块(则总大小为 64 * 4KB = 256KB),且该硬盘只给文件系统用。由于硬盘是按块进行寻址的,则地址空间为 0~63 。

245f9aefada86bc45b6793bc91901fa8.webp 就这么点空间的迷你硬盘

基于此迷你硬盘,我们一起来逐步推导下这个极简文件系统。

文件系统的首要目的肯定是存储用户数据,为此我们在磁盘留出一块数据区(Data Region)。假设我们使用后面 56 个块作为数据区。为什么是 56 个呢?从后面就可以知道,其实是可以算出来的——我们可以大致算出元信息和真正数据的比例,进而可以确定两部分大小。

a1de0752e84f20376aa60549e41bf05e.webp

隔出来数据区

接下来,我们需要为系统中的每个文件保存一些元信息,比如:

  1. 文件名
  2. 文件大小
  3. 文件归属者
  4. 访问权限
  5. 创建、修改时间

等等。保存这些元信息的数据块,我们通常称为 inode (index node)。如下,我们给 inode 分配 5 个 block。

21e299450541d27fbe3078580c62b69d.webp

隔出来索引区

元信息所占空间相对较小,比如 128B 或者 256B,我们这里假设每个 inode 占用 256B。则每个 4KB 块能容纳 16 个 inode,则我们的文件系统最多可以支持 5 * 16 = 80 个 inode,也即我们的迷你文件系统最多可以支持 80 个文件,但由于目录也要占 inode,所以实际可用文件数要少于 80。

现在我们有了数据区,有了文件元信息区,但在一个正常使用的文件系统中,还需要追踪哪些数据块被用了,哪些还没有被使用。这种数据结构我们称之为分配结构(allocation structures)。业界常用的方法有空闲链表(free list),即把所有空闲块按链表的方式串起来。但为了简单,这里使用一种更简单的数据结构:位图(bitmap),数据区用一个,称数据位图(data bitmap);inode 表用一个,称 inode 位图(inode bitmap)。

位图的思想很简单,即为每一个 inode 或者数据块使用一个数据位,来标记是否空闲:0 表示空闲,1 表示有数据。一个 4KB 的 bitmap 最多能追踪 32K 的对象。为了方便,我们给 inode 表和数据池各分配一个完整的块(虽然用不完),于是便有了下图。

7f2f6db1cce1410b74ad762dbadae028.webp

 造两个 map 作为空闲列表

可以看出,我们的基本思路是从后往前进行数据布局,最后还剩一个块。该块我们是故意留的,用以充当文件系统的超级块(superblock)。超级块作为一个文件系统的入口,通常会保存一些文件系统级别的元信息,比如本文件系统中有多少个 inode 和数据块(80 和 56),inode 表的起始块偏移量(3),等等。

b3bb1ccaf8382dd4db8dc228e1f9c505.webp

最后一个 block 是入口,称为超级块

则当文件系统被装载( mount )时,操作系统会首先读取超级块(所以放最前面),并据此初始化一系列参数,并将其作为数据卷挂载到文件系统树中。有了这些基本信息,当该卷中的文件被访问到时,就能逐步找出其位置,也就是我们之后要讲的读写流程。

但在讲读写流程之前,需要先放大一些关键数据结构看看其内在布局。

索引节点(Inode)

inode 是索引节点(index node)的简称,是对文件和文件夹的索引节点。为了简单,我们使用数组来组织索引节点,每个 inode 会关联一个编号(inumber),也即其在数组中的下标(偏移量)。

64e49007dc50554a575686fdbca830c4.webp

索引区的详细布局

上面提到过一嘴,每个 inode 占 256B。则给定一个 inumber,我们就可以计算出其在硬盘中的偏移量(12KB + inumber * 256),但由于内外存交换是按块来的,我们可以据此进而计算出其所在磁盘块。

inode 主要保存文件名、一些元信息(权限控制、各种事件、一些标记位)和数据块索引。数据块索引其实也是元信息,单拎出来说是因为它很重要。

我们使用一种比较简单的索引方式:间接指针indirect pointer)。即 inode 中保存的不是直接指向数据块的指针,而是指向一个指针块(也在数据区分配,但保存的都是二级指针)。如果文件足够大,可能还会引出三级指针(至于我们这个小系统是否用的着,大家可以估算下)。

但我们统计发现,在大多数文件系统中,小文件占多数。小到什么地步呢?一个数据块就可以存下。

6073cc450f89139338399bf763a497e0.webp

Untitled

因此实践中,我们在 inode 中使用一种直接指针间接指针混合的方式进行表示。在我们的文件系统中,就是使用 12 个直接指针和 1 个间接指针。所以只要文件尺寸不超过 12 个数据块,就可以直接用直接指针。只有过大时,才使用间接指针,并且在数据区新分配数据块,来存间接指针。

我们的数据区很小,只有 56 个 block,假设使用 4byte 进行索引。则二级指针最多可支持 (12 + 1024) · 4K ,也就是 4144KB 大小的文件。

另一种实践中常用的方式是数据段(extents)。即将每个连续数据区用起始指针和大小来表示,然后将一个文件的所有数据段串起来。但多段数据时,如果想访问最后一个数据段或者随机访问,性能会很差(下一个数据段的指针都保存在上一个数据段中)。为了优化访问速度,常将该数据段的索引链表存在内存中。Windows 的早期文件系统 FAT 就是这么干的。

目录组织

在我们的文件系统中,目录组织得很简单——即和文件一样,每个目录也占用一个 inode,但在 inode 指向的数据块不是存文件内容,而是存储该目录中所包含的所有文件和文件夹的信息,通常是用 List<entry name, inode number>  表示。当然要转为实际编码,还要存文件名长度等信息(因为文件名是变长的)。

看一个简单例子,设我们有一个文件夹 dir (inode 编号是 5),里面有三个文件(foor,bar 和 foobar),其对应的 inode 编号分别是 12,13 和 24 。则在该文件夹的数据块中存储的信息如下:

757cf86648dbedba209d9b5265968951.webp

 dir 内容的编码

其中 reclen (record length)是文件名所占空间大小,strlen 是实际长度。点和点点是指向本文件夹和上级文件夹的两个指针。记录reclen 看着有点多此一举,但要考虑到文件删除问题(可以用特殊的 inum,比如 0 来标记删除)。如果文件夹下的某个文件或者目录被删除,存储就会出现空洞。reclen 的存在,可以让删除留下的空洞为之后新增的文件复用。

需要说明的是,线性的组织一个目录中的文件是最简单的方式。实践中,还有其他方式。比如说在 XFS 中,如果目录中文件或者子文件夹特别多,会使用 B+ 树进行组织。从而在插入时,可以很快地知道是否有同名文件。

空闲空间管理

当我们需要新建文件或者目录项时,就需要从文件系统中获取一块可用空间。因此,如何高效的管理空闲空间,是个很重要的问题。我们使用两个 bitmap 进行管理,优点是简单,缺点是每次都得线性的扫描查找所有空闲 bit 位,且只能做到块粒度,块内如果有剩余空间,就管不到了。

读写路径

有了对磁盘上的数据结构的把握之后,我们再来通过读写流程将不同的数据结构串一下。我们假设文件系统已经被挂载:即超级块(superblock)已经在内存中。

读取文件

我们的操作很简单,就是打开一个文件(如 /foo/bar),进行读取,然后关闭。简化起见,假设我们文件大小占一个 block,即 4k。

当发起一个系统调用 open("/foo/bar", O RDONLY)时,文件系统需要首先找到文件 bar 对应的 inode,以获取其元信息和数据位置信息。但现在我们只有文件路径,那怎么办呢?

答曰:从根目录往下遍历。根目录的 inode 编号,我们要么保存在超级块中,要么就写死(比如 2,大部分 Unix 文件系统都是从 2 开始的)。也即,必须能事先知道(well known)。

于是文件系统将该根目录的 inode 从硬盘调入内存,进而再通过 inode 中的指针找到其指向数据块,进而从其包含所有子目录和文件夹中找到 foo 文件夹和其对应 inode。递归的重复上述过程,open 系统调用的最后一步是将 bar 的 inode 载入内存,进行权限检查(比对进程用户权限和 inode 访问权限控制),分配文件描述符放到进程打开文件表中,并将其返回给用户。

一旦文件被打开后,就可以继而发起 read() 的系统调用 ,真正地去读取数据。读取时,首先会根据文件的 inode 信息,找到第一个 block(除非读前实现用 lseek() 修改过偏移量),然后读取。同时,可能会更改 inode 的一些元信息,比如说访问时间。继而,更新进程中该文件描述符的偏移量,继续往下读,直到某个时刻,调用 close() 关闭该文件描述符。

进程关闭文件时,所需工作要少得多,只需要释放文件描述符即可,并不会有真正的磁盘 IO。

最后,我们再捋一下这个读文件过程。从根目录的 inode 编号开始,我们交替地读取 inode 和相应数据块,直到最终找到待查找文件。然后要进行数据读取,还要更新其 inode 的访问时间等元信息,进行写回。下表简单地总结了下这个过程,可以看出,读取路径全程不会涉及分配结构—— data bitmap 和 inode bitmap。

72f50e38cfd7436011585f0d11539640.webp

文件读取时间线

深度上来说,如果我们的待查找路径层级非常多,这个过程会线性增长;从广度上来说,如果中间查找时涉及到的文件夹,其包含的目录子项特别多,即文件树“很宽”,则每次在目录中进行查找时,可能需要读取不止一个数据块。

写入硬盘

写文件和读取文件的流程很类似,也是打开文件(从根目录一路找到对应文件);然后开始写入,最后关闭。但与读取文件不同的是,写入需要分配新的数据块,这就需要涉及我们之前的 bitmap 了,通常来说,一次写入至少需要五次 IO:

  1. 读取 data bitmap(以找到空闲块,并在内存中标记使用)
  2. 写回 data bitmap(以对其他进程可见)
  3. 读取 inode(增加新的数据位置指针)
  4. 写回 inode
  5. 在找到的空闲块中写入数据

这还只是对已经存在的文件进行写入。如果是尚未存在的文件进行创建并写入,那流程还要更为复杂:还要创建 inode,这就会引入一系列新的 IO:

  1. 一次对 inode bitmap 的读取(找到空闲 inode)
  2. 一次对 inode bitmap 的写回(标记某个 inode 被占用)
  3. 一次对 inode 本身的写入(初始化)
  4. 一次对父文件夹所对应目录子项数据块的读写(增加新建的文件和 inode 对)
  5. 一次对父文件夹 inode 的读写(更新修改日期)

如果父文件夹的数据块不够用,还得需要新分配空间,就又得读 data bitmap,和 data block。下图是创建 /foo/bar 文件的时间线上涉及到的 IO:

28ca2ef3d3885e92fc7a00a794f854d3.webp

 创建文件的时间线

缓存和缓冲

从上面对读写流程的分析可以看出,即便如此简单的读写操作,都会涉及大量 IO,这在实践中是不可接受的。为了解决这个问题,大部分工业上的文件系统,会充分利用内存,将重要的(也就是频繁访问的)数据块缓存(cache)在内存中;与此同时,为了避免频繁刷盘,会将修改先应用到内存缓冲区(buffer)里,然后积攒后一块落盘。

早期的文件系统引入了固定尺寸缓存(fixed-size cache),如果满了,会利用 LRU 等替换算法进行页面淘汰。其缺点在于当缓存不满的时候浪费空间,满了又可能频繁换页。我们称这种风格为静态分区(static partitioning)。大部分现代文件系统,都是用动态分区(dynamic partitioning)技术。比如,将虚拟内存页和文件系统页放到一个池子中,称为统一页面缓存(unified page cache),从而上两者分配和更加弹性。上了缓存之后,对于同一个目录中多个文件的读取,后面的读取就可以省下很多 IO。

写流程由于前半程根据路径查找数据块时牵扯到读,所以也会从缓存中受益。但对于写的部分,我们可以通过缓冲区(writing buffering),来延迟刷盘。延迟刷盘有很多好处,比如说可以多次修改 bitmap 可能只需要刷一次;积攒一批更改,可以提高 IO 带宽利用率;如果文件先增后删,可能就直接省了刷盘。

但这些性能的提升是有代价的——意外宕机可能会造成数据丢失。所以,虽然现代文件系统大部分开启了读写缓冲,但也通过 direct I/O 的方式,来允许用户绕过缓存,直接写磁盘。对丢失数据很敏感的应用,可以利用其对应的系统调用 fsync() 来即时刷盘。

小结

至此,我们完成了一个至简的文件系统的实现。其“麻雀虽小,五脏俱全”,我们从中可以看出文件系统设计一些基本的理念:

  1. 使用 inode 存储文件粒度的元信息;使用数据块存真正的文件数据
  2. 目录是一种特殊的文件,只不过存的不是文件内容,而是文件夹子目录项
  3. 除了 inode 和数据块外,还需要一些其他的数据结构,比如 bitmap 来追踪空闲块

从这个基本的文件系统出发,我们其实可以看到特别多的可以取舍和优化的点,如果感兴趣,大家可以在本文基础上,去看看一些工业上的文件系统的设计。

参考资料

[1]

Operating Systems: Three Easy Pieces: https://pages.cs.wisc.edu/~remzi/OSTEP/

[2]

JuiceFS: https://github.com/juicedata/juicefs

最后,如果你对我的文章感兴趣,欢迎点击下方“阅读原文”,订阅我的专栏《系统日知录》,更多干货。

题图故事

65fc32c04f74d53152ccac18b42424a0.webp

帝都的春: 春江水暖鸭先知

浏览 18
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报