Linux之文件系统前世今生（一）

Linux在线1
Linux在线2

一、 基本概念

1.1 块（Block）

在计算机存储之图解机械硬盘这篇文章中我们提到过，磁盘读写的最小单位是扇区，也就是 512 Byte；很明显，每次读写的效率非常低。

为了提高IO效率，我们要一次读写多个扇区。Linux 中一次性读写 8 个扇区， 也就是 4 KB，我们给这 4KB一个名字，记为块（Block）；也就是说，块（Block）是 Linux 中每次读写磁盘的最小单位。

当然也可以一次性读取 1K（2个扇区），2K (4个扇区)。

• Block 的大小和数量在格式化后无法改变。
• 一个 Block 只能存放一个文件的数据。
• 如果文件大于 Block 的大小，则一个文件会占用多个 Block。
• 如果文件小于 Block 的大小，则 Block 中多余的容量将无法再被使用，即磁盘空间会浪费。

1.2 文件系统

1.2.1 Inode

我们给所有 Block 编号（从0开始）后，就可以在 Block 中写入数据了。

比如，现在有一个名为 today.log 的文件，文件内容大小为 10 K，我们可以把它存储在Block 40 、Block 41 、Block 42 中（Block大小为4K，所以需要3个Block）；

文件存起来了，怎么找到这个文件呢？

• 得有个索引啊，不然，只有GOD知道这个文件存在了哪个Block了，我们将这个索引记为 Inode（Index node），前面提到的3个 Block 记为 数据区（Data Area 或者 Data Blocks）；

  • Inode中除了存储数据块号码（地址），还有其它文件元数据需要存储，比如文件类型、文件CRUD时间、文件权限等；
  • Inode一般为 128 byte 或 256 byte。

• Inode 也要存储起来，以便我们日后使用，我们可以把所有的 Inode 统一存放在几个连续的 block 中，记为 Inode 区（Inode Table）；
• Inode table 就是个Inode数组（ Inode[] ），数组下标我们记为Inode号；
• Inode数组很大时，要找到一个空闲的 Inode 就得线性扫描了，为提高效率，我们用1个位图（Bitmap）来标识 Inode 数组中元素被使用情况，记为 Inode位图（Inode Bitmap），Inode位图也要消耗 Block 来存储。

  • Inode Bitmap 用于标识 Inode Table 的使用状态，其使用 1 bit 来表示：0 表示空闲，1 表示占用；

现在我们思考另外一个问题，我们把 today.log的内容放在了Block 40 、Block 41 、Block 42 中，万一这3个Block中有数据，即被别的文件写入内容了，那我们这么暴力的使用就会导致别的文件被损坏了，所以我们得记录下哪些Block使用了，哪些未被使用。同样，我们得把这部分信息使用 Bitmap 存储在 Block 中，记为数据位图 ( Block Bitmap )

• Block Bitmap 用于标识所有的 Block 的使用状态，其使用 1 bit 来表示：0 表示空闲，1 表示占用；
• 如果 Block 的大小为 4K，那么其总共有 32768( 4 x 1024 x 8 ) 个 bit ，即一个 Block 可用于描述的 Block为 32768 个；
• 注意，Block Bitmap 只在写数据时使用，因为只有写数据才需要找到空闲的 Block；
• 使用Bitmap 可以在大量数据块的情况下，快速找到哪些块是可用的，避免了线性扫描。

到目前为止，我们的 Block 划分成了下图所示：

我们today.log文件的写入逻辑如下：

1. 系统查询 Inode Bitmap 后分配 Inode号为12,659，同时标识该bit 为 1；
2. 在 Inode Table 中 写入信息，即Inode[12,659] = Inode信息 ;
3. 查询 Block Bitmap 后分配 block 40 ，同时更新 Block Bitmap 40这个bit 为 1；
4. 将文件内容写入；
5. 写满一个Block，继续回到3. 直到写完数据才往6.走；
6. 更新Inode Table ，即将数据块号（40、41、42），文件大小等其它信息更新到Inode[12,659]中；

1.2.2 Inode记录大文件数据地址

前面我们限制了文件内容为 10KB，若文件很大，比如 400 MB，存储会有什么问题呢？

• 我们的数据块存储400M内容需要 100,000（400 M / 4 K）个Block，这当然没有什么问题，但是 Inode 是有大小的，100,000个 Block 地址(大小为 4 Byte)存储需要 400 KB（100,000 * 4）空间，已超过 Inode的大小（即使为256 Byte）；
• 一个直观的方式是扩大Inode 大小，若文件内容为1G呢，扩大到什么范围？
• 软件领域里有一句经典的话是“计算机科学中的所有问题都可以通过增加一个间接层来解决”，所以

  • 一个Block可以存储 1024 (4KB / 4Byte ) 个地址，1024个地址表示的数据范围可以达到 4MB（1024 * 4k），即加一层可以存储4MB数据；
  • 加两层可以存储 4GB（1024 * 4M）数据；
  • 加三层可以存储 4TB （1024 * 4G）数据；

• 我们可以加两层，把这100,000个Block地址存储在另外的几个 Block 内，然后让 Inode 中数据块地址指向第2层Block即可。

Inode结构示意图如下：Inode记录数据Block号码的Block数组大小为15，前12个为直接地址（可以记录 48 KB 数据，12 * 4KB = 48KB）、1个一级间接指针、1个二级间接指针，1个三级间接指针。

综上，文件大小理论上最大是 48K + 4M + 4G + 4T。

• 当文件小于 48KB 时，用直接指针即可记录；
• 超过48KB，但小于4MB + 48KB 时，增加一级间接指针记录；
• 超过4MB + 48KB，但小于4GB + 4MB + 48KB时，增加二级间接指针记录；
• 超过4GB + 4MB + 48KB 时，增加三次间接指针记录。

注意，这里采用 32 bit 寻址；所以 Block指针数组占用空间大小为 60 Byte （15 * 4 Byte）

1.2.3 目录

前面我们通过 Inode 信息和数据块（Data Blocks）解决了文件储存和读取问题，但是我们的文件都是位于某个目录下的，怎么样将目录信息也储存起来呢？
比如目录 /xiaolingting/month/january/下有2个文件：yesterday.log、today.log：

Linux中有句经典哲学： “一切皆文件 ” ，所以我们把目录也看成文件处理即可，即：
目录january看成是文件名，文件内容为目录下文件列表，假设其 Inode 号为10,000，我们来看下在目录/xiaolingting/month/january/下打开today.log的步骤：

1. 根据january的 Inode号：10,000 到 Inode Table 里找到对应的Inode信息，即 Inode[10,000]；
2. 从上述Inode信息里的数据块地址 37 找到 目录下的内容；
3. 在目录的数据块内容里找到了today.log的 Inode号码：12,659;
4. 根据today.log的 Inode号：12,659 到 Inode Table 里找到对应的Inode信息，即 Inode[12,659]；
5. 从上述Inode信息里的数据块地址 40、41、42找到文件 today.log的内容；
6. 读取文件 today.log：“世人妙性本空……”

1.2.4 文件类型

在前面我们把目录也统一看成文件，从而方便的利用文件的存储规则对目录进行了存储；但数据块内存储到底是目录还是真实的文件内容，这个是需要标识出来的，我们把这个标识记为文件类型，同样存储在 Inode 里。

常见文件类型如下表所示：

编码	文件类型
0	Unknown
1	Regular File
2	Director
3	Character Device
4	Block Device
5	Named Pipe
6	Socket
7	Symbolic Link

1.2.5 超级块

思考以下问题：

1. 前面我们成功找到了/xiaolingting/month/january/下的today.log文件，但是有个前提，我们假设了目录january的Inode号为10,000，抛开这个假设，我们怎么知道这个Inode号呢？当然是从上一层目录month里的文件内容里去读喽，这不是死循环了吗？得有个终止条件啊，即根目录 / 的Inode号码是多少呢？
2. 我们约定的Block大小为4KB，Inode 的大小为128 Byte， 这些信息记录在哪里？
3. 磁盘一共有多少空间可用，已经用了多少，还有多少可用呢？

我们可以使用存储空间开头的位置来存储上面的这些信息，在机器初始化时将这些内容加载到内存中使用即可；我们将这个特殊的块记为超级块（super_block）；

• 使用 df 命令读取的就是超级块（super_block），所以它的统计速度非常快。
• 相对应的，用 du 命令时，需要遍历整个目录的所有文件，所以查看一个较大目录的已用空间会非常慢。
• 常见的df和du不一致情况就是文件删除的问题。当一个文件被删除后，在文件系统目录中已经不可见了，所以du就不会再统计它了。然而如果此时还有运行的进程持有这个已经被删除了的文件的句柄，那么这个文件就不会真正在磁盘中被删除， 分区超级块中的信息也就不会更改。这样df仍旧会统计这个被删除了的文件。
  通过lsof | grep delete 查看占用文件的进程，kill 进程即可解决。

此外还有我们之前提到的Inode Bitmap、Block Bitmap、Inode Table、Data Blocks它们各自的起始位置和容量大小，也需要记录下来，我们把这些信息存储在超级块（super_block） 旁边的块上，记为描述块（Description Block）。

至此，逻辑块变成了下面图示的样子，我们的文件就可以愉快的读取和写入了。

看上面图示会发现图里多了个启动块即Boot Block，也称为boot sector。它位于分区上的第一个块，占用 1K Byte，并非所有分区都有这个boot sector，只有装了操作系统的主分区和装了操作系统的逻辑分区才有。

二、EXT文件系统

前面我们捣鼓出来一个简易的文件系统，麻雀虽小，但五脏俱全。接下来我们看看Linux中真实的文件系统 EXT。

EXT
全称Linux extended file system, extfs，即Linux扩展文件系统，Ext2就代表第二代文件扩展系统，Ext3/Ext4以此类推，它们都是Ext2的升级版，只不过为了快速恢复文件系统，减少一致性检查的时间，增加了日志功能，所以Ext2被称为索引式文件系统，而Ext3/Ext4被称为日志式文件系统。

常见的文件系统类型非常多，比如：

• Windows 默认使用 NTFS
• MacOS、iOS、watchOS 默认使用 APFS（曾经使用 HFS）
• 光盘类的文件系统ISO9660
• 网络文件系统NFS
• 内容寻址文件系统 Git
• 分布式文件存储系统 TFS（Taobao File System）

2.1 EXT2

以EXT2为例，系统结构如下图所示：

• 为了方便管理，Ext2将这些Block聚集在一起分为几个大的块组（Block Group），每个块组包含的等量的逻辑块，在块组的数据块中存储文件或目录；

  为啥分组呢？

  1. 降低文件系统损坏风险；
     • 以 Block Bitmap 为例来说，因为如果所有的bitmap都存放在同一个块组（Block Group）中，当该group数据块被损坏时，整个文件系统的可用性都会受到影响。分散保存可以降低这种风险。
  2. 提高性能。
     • 假设文件系统是 100GB 时，分为 25,000,000(100G / 4K)个Block，用Bitmap需要存储需要储存25,000,000 个bit，25MB的数据量啊，想在其中找一个空闲的 Bit 要扫描好长时间啊。将这 25MB数据分散到不同块组中，扫描一个块组可以节约不少时间。

  块组容量
  根据图示，一个块组里 Block Bitmap 占用1 个block ，即 4KB，即 2¹⁵ ( 4 * 1024 * 8 ) 个 bit，则可以表示128 MB (4 * 1024 * 8 * 4KB)

• 注意：块组（Block Group），并没有限制 Inode 中记录的数据块（data block）属于其它group的情况！ext2文件系统甚至鼓励这种跨group存储文件。

• 块组描述信息为Inode Bitmap、Block Bitmap、Inode Table、Data Blocks，其大小固定为32Byte， 每个块组都占用一个Block，有点浪费空间，把所有块组描述信息统一放在一起，组成了块组描述符表(Group Description Table, GDT)，保留GDT 用于以后扩容文件系统使用，防止扩容后块组太多，使得块组描述符超出当前存储GDT的blocks。

• 超级块不仅存储在第一个块组，后续还有特定的块组内部存储超级块（Super Block），这些超级块均存储一样的信息，起到备份的作用，提高了文件系统的健壮性。

  超级块（Super Block）、块组描述符表( GDT) 和 保留GDT 对于文件系统而言是至关重要的，三者形影不离，超级块丢失或损坏必将导致文件系统的损坏。
  正常情况下文件系统只使用第一个块组即Block Group 0中超级块信息来获取文件系统属性，只有当Group0上的Super Block损坏或丢失才会将下一个备份Super Block复制到Group0中来恢复文件系统。

2.1.1 EXT2 文件实际大小

在 “1.2.2 Inode记录大文件数据地址” 这一小节中，我们提到了 “文件大小理论上最大是 48K + 4M + 4G + 4T”，注意，这里说的是理论，实际有内核等各种限制（2.4 内核对单个块设备的限制是 2TB），最大为 2 TB;

2.2 Ext文件系统预留 Inode

Ext 文件系统预留了一部分 Inode 作为特殊用途，如下所示。

Inode	用途
0	不存在，可用于标识目录的 Data Block 中已删除的文件
1	虚拟文件系统，如：/proc、/sys
2	根目录
3	ACL 索引
4	ACL 数据
5	Boot Loader
6	未删除的目录
7	预留的区块组描述符 Inode
8	日志 Inode
11	第一个非预留的 Inode，通常是 lost+fount 目录

注意：Inode有效编号从 1 开始

2.3 如何删除文件

• 从前面章节可以了解到，删除一个文件时，
  • 先把目录文件里的文件名和Inode映射删除；

    实际是把文件名对应的 Inode 修改为 0（2.2 小节中 预留 Inode 为 0 时用于标记删除）

  • 然后把 Block Bitmap 和 Inode Bitmap 均置为0即可，这就表示该空间空闲了；

    这里有个前提：即Inode 里的链接数为 0，详见Linux之文件系统前世今生（二）

• 至于文件占用 Data Blocks 和 Inode 信息，后面使用时直接覆盖即可。
• 如果在Linux中误删除一个文件，还是能恢复的，但是前提必须是Inode和Data Block没有被占用。

2.4 EXT3

Ext2写一个文件要多个步骤，如更新Inode Bitmap、更新Block Bitmap、刷新Inode数据块指针……

当系统突发故障，刚写完Inode Bitmap，系统断电了，我们怎么保证数据的持久化和一致性呢？

聪明的你一定想到了数据库事务是怎么保证事务ACID的，当然是预写式日志（Write-ahead logging，WAL）。

Ext3 正是采用了 WAL 来解决上述问题的。

2.5 EXT4

2.5.1 Ext2/3 面临的问题：

• Ext2/3 的 Inode 中 数据块指针数组容量为15，文件最大为 4TB + 4GB + 4MB + 48KB ；即无法存储超过此大小的文件；
• 文件很大时，使用三级间接指针，性能较低；
• block很多，导致消耗 Block Bitmap 也多，对于一个巨大的文件，扫描整个 Block Bitmap 耗时显著增加。

2.5.2 Ext4 优化

Ext2/3 上述问题的一个重要原因是面向 Block 进行分配，对于N个连续的 Block ，需要记录N个指针信息。所以我们可以将这连续的N个Block的指针信息记录1份，我们把这一份信息记为 区(Extent） ，即 Extent 可以尽可能的包含物理上连续的 N 个 Block，N为任意正整数( 1 <= N <= 2¹⁵ ，一个块组最多2¹⁵个 Block) ，如下图所示：

• Extent 分为 head 和 body，一个head 可以搭配多个body，如下图所示：
  

• Ext4 通过 B+树 将 Extent 组织起来：

  • Extent 这个结构的根节点（Root）存在了 Inode 里原来的的数据指针区域；
  • 中间节点和叶子节点存在 1个 Block 上，即Extent 最大为 4KB；
    

• Extent 组成的B+ 树，添加了中间节点，如下图所示：
  

我们来算下Ext4 这样存储后，可以存储的文件大小：

• 1 个块组为 128 M，一个 extent_body最多可以表示一个块组，Inode 里有4个 extent_body，可以表示 512 MB （4 * 128 MB）；
• 加一个中间节点Extent，可以表示大约 340 (4 KB / 12 Byte ) 个块组，可以表示大约40 GB ( 340 * 128 MB)；
• 第二层可以放4个中间节点，可以表示大约160 GB (4 * 40GB);
• ……

Ext4 实际实现时比较复杂，大概原理如上所述。

三、虚拟文件系统(Virtual File System， VFS)

Linux中允许众多不同的文件系统共存并且对文件的操作可以跨文件系统而执行，这依赖于VFS（Virtual File System）虚拟文件系统。通俗点，就是 VFS 类比接口，不同的文件系统如Ext2、Ext3、Ext4、NFS 都是这个接口的具体实现，这个和面向对象里的多态一样。

VFS 支持的文件系统：

• 基于磁盘（disk-based）的文件系统
  • 管理本地磁盘和模拟磁盘的设备。
• 网络文件系统
  • 它允许方便访问网络上其它计算机的文件系统。
• 特殊文件系统
  • 也是一种虚拟文件系统，它不管理磁盘空间。

文件系统分类	具体文件系统	备注
基于磁盘	Ext2/3/4	Linux
	NFTS（New Technology File System）	windows
	HFS（Hierarchical File System）、AFFS（Apple File System）、ADFS	苹果
	ZFS(Zettabyte File System)	Zettabyte 相当于1万亿兆字节。它能存储1800亿亿（18.4×1018）倍于当前64位文件系统的数据。ZFS 的设计如此超前以至于这个极限就当前现实实际可能永远无法遇到。
	btrfs( B-Tree Filesystem)
网络文件系统	NFS、CIFS（Common Internet Filesystem）
	Coda、AFS（Andrew filesystem）
	NCP（Novell’s NetWare Core Protocol）
特殊文件系统（虚拟文件系统）	proc	挂载于/proc目录下，由内核在内存中创建，用于跟踪正在执行的进程
	devfs	linux 2.6内核以前使用devfs来管理位于/dev目录下的所有设备。devfs缺点：一个设备映射的设备文件可能不同。例如，U盘可能对应sda，也可能对应sdb，没有足够的主/辅设备号，当设备过多的时候，此问题突显
	sysfs	为了解决devfs的缺点，linux 2.6内核引入了sysfs，挂载于/sys目录下
	tmpfs（temporary filesystem）	tmpfs是构建在内存中的，所以存放在tmpfs中的所有数据在卸载或断电后都会丢失

借助VFS可以直接使用open()、read()、write()这样的系统调用操作文件，而无须考虑具体的文件系统和实际的存储介质。

VFS是一种软件机制，只存在于物理内存当中，屏蔽了下层具体文件系统操作的差异，为上层的操作提供一个统一的接口。VFS同样也有 超级块（Super Block）和 Inode，此外新增了目录项（Directory Entry, Dentry）和文件对象（File）。

• 超级块：超级块对象表示一个文件系统。它存储一个已安装的文件系统的控制信息，包括文件系统名称（比如Ext2）、文件系统的大小和状态、块设备的引用和元数据信息（比如空闲列表等等）。VFS超级块存在于内存中，它在文件系统安装时建立，并且在文件系统卸载时自动删除。

• Inode：将磁盘中的Inode加载到内存中，同时添加VFS内的额外信息如进程引用计数器。详见Linux之文件系统前世今生（二）

• 目录项（Dentry）：由于VFS会经常的执行目录相关的操作，比如切换到某个目录、路径名的查找等等，为了提高这个过程的效率，VFS引入了目录项的概念。目录项对象没有对应的磁盘数据结构，只存在于内存中。一个路径的各个组成部分，不管是目录还是普通的文件，都是一个目录项对象。如在路径/xiaolingting/month/january/today.log中，VFS在遍历 /, xiaolingting、month、january、today.log的过程中，将它们逐个解析成目录项对象。解析一个路径是一个耗时的、常规的字符串比较过程。

• 文件对象（File）：文件对象描述的是进程已经打开的文件。一个文件可以被多个进程打开，所以一个文件可以存在多个文件对象。