一口气搞懂「文件系统」,就靠这 20 张图了

用户头像
小林coding
关注
发布于: 2020 年 08 月 13 日
一口气搞懂「文件系统」,就靠这 20 张图了








前言



不多 BB,直接上「硬菜」。








正文



文件系统的基本组成



文件系统是操作系统中负责管理持久数据的子系统,说简单点,就是负责把用户的文件存到磁盘硬件中,因为即使计算机断电了,磁盘里的数据并不会丢失,所以可以持久化的保存文件。



文件系统的基本数据单位是文件,它的目的是对磁盘上的文件进行组织管理,那组织的方式不同,就会形成不同的文件系统。



Linux 最经典的一句话是:「一切皆文件」,不仅普通的文件和目录,就连块设备、管道、socket 等,也都是统一交给文件系统管理的。



Linux 文件系统会为每个文件分配两个数据结构:*索引节点(index node)和目录项(directory entry*,它们主要用来记录文件的元信息和目录层次结构。



  • 索引节点,也就是 inode,用来记录文件的元信息,比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识,它们之间一一对应,也同样都会被存储在硬盘中,所以索引节点同样占用磁盘空间

  • 目录项,也就是 dentry,用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来,就会形成目录结构,但它与索引节点不同的是,目录项是由内核维护的一个数据结构,不存放于磁盘,而是缓存在内存



由于索引节点唯一标识一个文件,而目录项记录着文件的名,所以目录项和索引节点的关系是多对一,也就是说,一个文件可以有多个别字。比如,硬链接的实现就是多个目录项中的索引节点指向同一个文件。



注意,目录也是文件,也是用索引节点唯一标识,和普通文件不同的是,普通文件在磁盘里面保存的是文件数据,而目录文件在磁盘里面保存子目录或文件。



目录项和目录是一个东西吗?



虽然名字很相近,但是它们不是一个东西,目录是个文件,持久化存储在磁盘,而目录项是内核一个数据结构,缓存在内存。



如果查询目录频繁从磁盘读,效率会很低,所以内核会把已经读过的目录用目录项这个数据结构缓存在内存,下次再次读到相同的目录时,只需从内存读就可以,大大提高了文件系统的效率。



注意,目录项这个数据结构不只是表示目录,也是可以表示文件的。



那文件数据是如何存储在磁盘的呢?



磁盘读写的最小单位是扇区,扇区的大小只有 512B 大小,很明显,如果每次读写都以这么小为单位,那这读写的效率会非常低。



所以,文件系统把多个扇区组成了一个逻辑块,每次读写的最小单位就是逻辑块(数据块),Linux 中的逻辑块大小为 4KB,也就是一次性读写 8 个扇区,这将大大提高了磁盘的读写的效率。



以上就是索引节点、目录项以及文件数据的关系,下面这个图就很好的展示了它们之间的关系:





索引节点是存储在硬盘上的数据,那么为了加速文件的访问,通常会把索引节点加载到内存中。



另外,磁盘进行格式化的时候,会被分成三个存储区域,分别是超级块、索引节点区和数据块区。

  • 超级块,用来存储文件系统的详细信息,比如块个数、块大小、空闲块等等。

  • 索引节点区,用来存储索引节点;

  • 数据块区,用来存储文件或目录数据;



我们不可能把超级块和索引节点区全部加载到内存,这样内存肯定撑不住,所以只有当需要使用的时候,才将其加载进内存,它们加载进内存的时机是不同的:



  • 超级块:当文件系统挂载时进入内存;

  • 索引节点区:当文件被访问时进入内存;






虚拟文件系统



文件系统的种类众多,而操作系统希望对用户提供一个统一的接口,于是在用户层与文件系统层引入了中间层,这个中间层就称为*虚拟文件系统(Virtual File System,VFS)。*



VFS 定义了一组所有文件系统都支持的数据结构和标准接口,这样程序员不需要了解文件系统的工作原理,只需要了解 VFS 提供的统一接口即可。



在 Linux 文件系统中,用户空间、系统调用、虚拟机文件系统、缓存、文件系统以及存储之间的关系如下图:





Linux 支持的文件系统也不少,根据存储位置的不同,可以把文件系统分为三类:



  • 磁盘的文件系统,它是直接把数据存储在磁盘中,比如 Ext 2/3/4、XFS 等都是这类文件系统。

  • 内存的文件系统,这类文件系统的数据不是存储在硬盘的,而是占用内存空间,我们经常用到的 /proc/sys 文件系统都属于这一类,读写这类文件,实际上是读写内核中相关的数据数据。

  • 网络的文件系统,用来访问其他计算机主机数据的文件系统,比如 NFS、SMB 等等。



文件系统首先要先挂载到某个目录才可以正常使用,比如 Linux 系统在启动时,会把文件系统挂载到根目录。






文件的使用



我们从用户角度来看文件的话,就是我们要怎么使用文件?首先,我们得通过系统调用来打开一个文件。





fd = open(name, flag); # 打开文件
...
write(fd,...); # 写数据
...
close(fd); # 关闭文件



上面简单的代码是读取一个文件的过程:

  • 首先用 open 系统调用打开文件,open 的参数中包含文件的路径名和文件名。

  • 使用 write 写数据,其中 write 使用 open 所返回的文件描述符,并不使用文件名作为参数。

  • 使用完文件后,要用 close 系统调用关闭文件,避免资源的泄露。



我们打开了一个文件后,操作系统会跟踪进程打开的所有文件,所谓的跟踪呢,就是操作系统为每个进程维护一个打开文件表,文件表里的每一项代表「文件描述符」,所以说文件描述符是打开文件的标识。





操作系统在打开文件表中维护着打开文件的状态和信息:

  • 文件指针:系统跟踪上次读写位置作为当前文件位置指针,这种指针对打开文件的某个进程来说是唯一的;

  • 文件打开计数器:文件关闭时,操作系统必须重用其打开文件表条目,否则表内空间不够用。因为多个进程可能打开同一个文件,所以系统在删除打开文件条目之前,必须等待最后一个进程关闭文件,该计数器跟踪打开和关闭的数量,当该计数为 0 时,系统关闭文件,删除该条目;

  • 文件磁盘位置:绝大多数文件操作都要求系统修改文件数据,该信息保存在内存中,以免每个操作都从磁盘中读取;

  • 访问权限:每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等),该信息保存在进程的打开文件表中,以便操作系统能允许或拒绝之后的 I/O 请求;



在用户视角里,文件就是一个持久化的数据结构,但操作系统并不会关心你想存在磁盘上的任何的数据结构,操作系统的视角是如何把文件数据和磁盘块对应起来。



所以,用户和操作系统对文件的读写操作是有差异的,用户习惯以字节的方式读写文件,而操作系统则是以数据块来读写文件,那屏蔽掉这种差异的工作就是文件系统了。



我们来分别看一下,读文件和写文件的过程:



  • 当用户进程从文件读取 1 个字节大小的数据时,文件系统则需要获取字节所在的数据块,再返回数据块对应的用户进程所需的数据部分。

  • 当用户进程把 1 个字节大小的数据写进文件时,文件系统则找到需要写入数据的数据块的位置,然后修改数据块中对应的部分,最后再把数据块写回磁盘。



所以说,文件系统的基本操作单位是数据块






文件的存储



文件的数据是要存储在硬盘上面的,数据在磁盘上的存放方式,就像程序在内存中存放的方式那样,有以下两种:



  • 连续空间存放方式

  • 非连续空间存放方式



其中,非连续空间存放方式又可以分为「链表方式」和「索引方式」。



不同的存储方式,有各自的特点,重点是要分析它们的存储效率和读写性能,接下来分别对每种存储方式说一下。



连续空间存放方式



连续空间存放方式顾名思义,文件存放在磁盘「连续的」物理空间中。这种模式下,文件的数据都是紧密相连,读写效率很高,因为一次磁盘寻道就可以读出整个文件。

使用连续存放的方式有一个前提,必须先知道一个文件的大小,这样文件系统才会根据文件的大小在磁盘上找到一块连续的空间分配给文件。



所以,文件头里需要指定「起始块的位置」和「长度」,有了这两个信息就可以很好的表示文件存放方式是一块连续的磁盘空间。



注意,此处说的文件头,就类似于 Linux 的 inode。





连续空间存放的方式虽然读写效率高,但是有「磁盘空间碎片」和「文件长度不易扩展」的缺陷。



如下图,如果文件 B 被删除,磁盘上就留下一块空缺,这时,如果新来的文件小于其中的一个空缺,我们就可以将其放在相应空缺里。但如果该文件的大小大于所有的空缺,但却小于空缺大小之和,则虽然磁盘上有足够的空缺,但该文件还是不能存放。当然了,我们可以通过将现有文件进行挪动来腾出空间以容纳新的文件,但是这个在磁盘挪动文件是非常耗时,所以这种方式不太现实。





另外一个缺陷是文件长度扩展不方便,例如上图中的文件 A 要想扩大一下,需要更多的磁盘空间,唯一的办法就只能是挪动的方式,前面也说了,这种方式效率是非常低的。



那么有没有更好的方式来解决上面的问题呢?答案当然有,既然连续空间存放的方式不太行,那么我们就改变存放的方式,使用非连续空间存放方式来解决这些缺陷。



非连续空间存放方式



非连续空间存放方式分为「链表方式」和「索引方式」。



我们先来看看链表的方式。



链表的方式存放是离散的,不用连续的,于是就可以消除磁盘碎片,可大大提高磁盘空间的利用率,同时文件的长度可以动态扩展。根据实现的方式的不同,链表可分为「隐式链表」和「显式链接」两种形式。



文件要以「隐式链表」的方式存放的话,实现的方式是文件头要包含「第一块」和「最后一块」的位置,并且每个数据块里面留出一个指针空间,用来存放下一个数据块的位置,这样一个数据块连着一个数据块,从链头开是就可以顺着指针找到所有的数据块,所以存放的方式可以是不连续的。





隐式链表的存放方式的缺点在于无法直接访问数据块,只能通过指针顺序访问文件,以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差,系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏,会导致文件数据的丢失。



如果取出每个磁盘块的指针,把它放在内存的一个表中,就可以解决上述隐式链表的两个不足。那么,这种实现方式是「显式链接」,它指把用于链接文件各数据块的指针,显式地存放在内存的一张链接表中,该表在整个磁盘仅设置一张,每个表项中存放链接指针,指向下一个数据块号



对于显式链接的工作方式,我们举个例子,文件 A 依次使用了磁盘块 4、7、2、10 和 12 ,文件 B 依次使用了磁盘块 6、3、11 和 14 。利用下图中的表,可以从第 4 块开始,顺着链走到最后,找到文件 A 的全部磁盘块。同样,从第 6 块开始,顺着链走到最后,也能够找出文件 B 的全部磁盘块。最后,这两个链都以一个不属于有效磁盘编号的特殊标记(如 -1 )结束。内存中的这样一个表格称为*文件分配表(File Allocation Table,FAT*。





由于查找记录的过程是在内存中进行的,因而不仅显著地提高了检索速度,而且大大减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系,它的主要的缺点是不适用于大磁盘



比如,对于 200GB 的磁盘和 1KB 大小的块,这张表需要有 2 亿项,每一项对应于这 2 亿个磁盘块中的一个块,每项如果需要 4 个字节,那这张表要占用 800MB 内存,很显然 FAT 方案对于大磁盘而言不太合适。



接下来,我们来看看索引的方式。



链表的方式解决了连续分配的磁盘碎片和文件动态扩展的问题,但是不能有效支持直接访问(FAT除外),索引的方式可以解决这个问题。



索引的实现是为每个文件创建一个「索引数据块」,里面存放的是指向文件数据块的指针列表,说白了就像书的目录一样,要找哪个章节的内容,看目录查就可以。



另外,文件头需要包含指向「索引数据块」的指针,这样就可以通过文件头知道索引数据块的位置,再通过索引数据块里的索引信息找到对应的数据块。



创建文件时,索引块的所有指针都设为空。当首次写入第 i 块时,先从空闲空间中取得一个块,再将其地址写到索引块的第 i 个条目。





索引的方式优点在于:

  • 文件的创建、增大、缩小很方便;

  • 不会有碎片的问题;

  • 支持顺序读写和随机读写;



由于索引数据也是存放在磁盘块的,如果文件很小,明明只需一块就可以存放的下,但还是需要额外分配一块来存放索引数据,所以缺陷之一就是存储索引带来的开销。



如果文件很大,大到一个索引数据块放不下索引信息,这时又要如何处理大文件的存放呢?我们可以通过组合的方式,来处理大文件的存。



先来看看链表 + 索引的组合,这种组合称为「链式索引块」,它的实现方式是在索引数据块留出一个存放下一个索引数据块的指针,于是当一个索引数据块的索引信息用完了,就可以通过指针的方式,找到下一个索引数据块的信息。那这种方式也会出现前面提到的链表方式的问题,万一某个指针损坏了,后面的数据也就会无法读取了。





还有另外一种组合方式是索引 + 索引的方式,这种组合称为「多级索引块」,实现方式是通过一个索引块来存放多个索引数据块,一层套一层索引,像极了俄罗斯套娃是吧。





Unix 文件的实现方式



我们先把前面提到的文件实现方式,做个比较:





那早期 Unix 文件系统是组合了前面的文件存放方式的优点,如下图:





它是根据文件的大小,存放的方式会有所变化:



  • 如果存放文件所需的数据块小于 10 块,则采用直接查找的方式;

  • 如果存放文件所需的数据块超过 10 块,则采用一级间接索引方式;

  • 如果前面两种方式都不够存放大文件,则采用二级间接索引方式;

  • 如果二级间接索引也不够存放大文件,这采用三级间接索引方式;



那么,文件头(Inode)就需要包含 13 个指针:

  • 10 个指向数据块的指针;

  • 第 11 个指向索引块的指针;

  • 第 12 个指向二级索引块的指针;

  • 第 13 个指向三级索引块的指针;



所以,这种方式能很灵活地支持小文件和大文件的存放:

  • 对于小文件使用直接查找的方式可减少索引数据块的开销;

  • 对于大文件则以多级索引的方式来支持,所以大文件在访问数据块时需要大量查询;



这个方案就用在了 Linux Ext 2/3 文件系统里,虽然解决大文件的存储,但是对于大文件的访问,需要大量的查询,效率比较低。



为了解决这个问题,Ext 4 做了一定的改变,具体怎么解决的,本文就不展开了。






空闲空间管理



前面说到的文件的存储是针对已经被占用的数据块组织和管理,接下来的问题是,如果我要保存一个数据块,我应该放在硬盘上的哪个位置呢?难道需要将所有的块扫描一遍,找个空的地方随便放吗?



那这种方式效率就太低了,所以针对磁盘的空闲空间也是要引入管理的机制,接下来介绍几种常见的方法:



  • 空闲表法

  • 空闲链表法

  • 位图法



空闲表法



空闲表法就是为所有空闲空间建立一张表,表内容包括空闲区的第一个块号和该空闲区的块个数,注意,这个方式是连续分配的。如下图:





当请求分配磁盘空间时,系统依次扫描空闲表里的内容,直到找到一个合适的空闲区域为止。当用户撤销一个文件时,系统回收文件空间。这时,也需顺序扫描空闲表,寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。



这种方法仅当有少量的空闲区时才有较好的效果。因为,如果存储空间中有着大量的小的空闲区,则空闲表变得很大,这样查询效率会很低。另外,这种分配技术适用于建立连续文件。



空闲链表法



我们也可以使用「链表」的方式来管理空闲空间,每一个空闲块里有一个指针指向下一个空闲块,这样也能很方便的找到空闲块并管理起来。如下图:





当创建文件需要一块或几块时,就从链头上依次取下一块或几块。反之,当回收空间时,把这些空闲块依次接到链头上。



这种技术只要在主存中保存一个指针,令它指向第一个空闲块。其特点是简单,但不能随机访问,工作效率低,因为每当在链上增加或移动空闲块时需要做很多 I/O 操作,同时数据块的指针消耗了一定的存储空间。



空闲表法和空闲链表法都不适合用于大型文件系统,因为这会使空闲表或空闲链表太大。



位图法



位图是利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有的盘块都有一个二进制位与之对应。



当值为 0 时,表示对应的盘块空闲,值为 1 时,表示对应的盘块已分配。它形式如下:



1111110011111110001110110111111100111 ...



在 Linux 文件系统就采用了位图的方式来管理空闲空间,不仅用于数据空闲块的管理,还用于 inode 空闲块的管理,因为 inode 也是存储在磁盘的,自然也要有对其管理。






文件系统的结构



前面提到 Linux 是用位图的方式管理空闲空间,用户在创建一个新文件时,Linux 内核会通过 inode 的位图找到空闲可用的 inode,并进行分配。要存储数据时,会通过块的位图找到空闲的块,并分配,但仔细计算一下还是有问题的。



数据块的位图是放在磁盘块里的,假设是放在一个块里,一个块 4K,每位表示一个数据块,共可以表示 4 * 1024 * 8 = 2^15 个空闲块,由于 1 个数据块是 4K 大小,那么最大可以表示的空间为 2^15 * 4 * 1024 = 2^27 个 byte,也就是 128M。



也就是说按照上面的结构,如果采用「一个块的位图 + 一系列的块」,外加「一个块的 inode 的位图 + 一系列的 inode 的结构」能表示的最大空间也就 128M,这太少了,现在很多文件都比这个大。



在 Linux 文件系统,把这个结构称为一个块组,那么有 N 多的块组,就能够表示 N 大的文件。



下图给出了 Linux Ext2 整个文件系统的结构和块组的内容,文件系统都由大量块组组成,在硬盘上相继排布:





最前面的第一个块是引导块,在系统启动时用于启用引导,接着后面就是一个一个连续的块组了,块组的内容如下:

  • 超级块,包含的是文件系统的重要信息,比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。

  • 块组描述符,包含文件系统中各个块组的状态,比如块组中空闲块和 inode 的数目等,每个块组都包含了文件系统中「所有块组的组描述符信息」。

  • 数据位图和 inode 位图, 用于表示对应的数据块或 inode 是空闲的,还是被使用中。

  • inode 列表,包含了块组中所有的 inode,inode 用于保存文件系统中与各个文件和目录相关的所有元数据。

  • 数据块,包含文件的有用数据。



你可以会发现每个块组里有很多重复的信息,比如超级块和块组描述符表,这两个都是全局信息,而且非常的重要,这么做是有两个原因:

  • 如果系统崩溃破坏了超级块或块组描述符,有关文件系统结构和内容的所有信息都会丢失。如果有冗余的副本,该信息是可能恢复的。

  • 通过使文件和管理数据尽可能接近,减少了磁头寻道和旋转,这可以提高文件系统的性能。



不过,Ext2 的后续版本采用了稀疏技术。该做法是,超级块和块组描述符表不再存储到文件系统的每个块组中,而是只写入到块组 0、块组 1 和其他 ID 可以表示为 3、 5、7 的幂的块组中。






目录的存储



在前面,我们知道了一个普通文件是如何存储的,但还有一个特殊的文件,经常用到的目录,它是如何保存的呢?



基于 Linux 一切皆文件的设计思想,目录其实也是个文件,你甚至可以通过 vim 打开它,它也有 inode,inode 里面也是指向一些块。



和普通文件不同的是,普通文件的块里面保存的是文件数据,而目录文件的块里面保存的是目录里面一项一项的文件信息。



在目录文件的块中,最简单的保存格式就是列表,就是一项一项地将目录下的文件信息(如文件名、文件 inode、文件类型等)列在表里。



列表中每一项就代表该目录下的文件的文件名和对应的 inode,通过这个 inode,就可以找到真正的文件。





通常,第一项是「.」,表示当前目录,第二项是「..」,表示上一级目录,接下来就是一项一项的文件名和 inode。



如果一个目录有超级多的文件,我们要想在这个目录下找文件,按照列表一项一项的找,效率就不高了。



于是,保存目录的格式改成哈希表,对文件名进行哈希计算,把哈希值保存起来,如果我们要查找一个目录下面的文件名,可以通过名称取哈希。如果哈希能够匹配上,就说明这个文件的信息在相应的块里面。



Linux 系统的 ext 文件系统就是采用了哈希表,来保存目录的内容,这种方法的优点是查找非常迅速,插入和删除也较简单,不过需要一些预备措施来避免哈希冲突。



目录查询是通过在磁盘上反复搜索完成,需要不断地进行 I/O 操作,开销较大。所以,为了减少 I/O 操作,把当前使用的文件目录缓存在内存,以后要使用该文件时只要在内存中操作,从而降低了磁盘操作次数,提高了文件系统的访问速度。






软链接和硬链接



有时候我们希望给某个文件取个别名,那么在 Linux 中可以通过*硬链接(Hard Link*)软链接(Symbolic Link)** 的方式来实现,它们都是比较特殊的文件,但是实现方式也是不相同的。



硬链接是多个目录项中的「索引节点」指向一个文件,也就是指向同一个 inode,但是 inode 是不可能跨越文件系统的,每个文件系统都有各自的 inode 数据结构和列表,所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode,那么只有删除文件的所有硬链接以及源文件时,系统才会彻底删除该文件。





软链接相当于重新创建一个文件,这个文件有独立的 inode,但是这个文件的内容是另外一个文件的路径,所以访问软链接的时候,实际上相当于访问到了另外一个文件,所以软链接是可以跨文件系统的,甚至目标文件被删除了,链接文件还是在的,只不过指向的文件找不到了而已。








迟到理由



是的,小林依然迟到了,因为最近发生了一件非常倒霉的事情,我之前使用的图床挂掉了……



这就导致我所有文章的图片都挂了,好在大部分博客平台都会转存图片,所以微信公众号、CSDN、知乎等平台都正常,但我的本地文章笔记和博客园平台的图片都挂掉了,在博客园还有个读者私信提醒我的文章图片挂了,他很喜欢小林文章,希望早点恢图片,太感动了。





这就是白嫖免费图床的下场,本打算换阿里云图床,但阿里云图床是按访问流量收费的,如果有人搞你,那直接刷爆你的钱包,想想都可怕,小林穷搞不起搞不起。



后来,询问了一位朋友 guide 哥,他说可以使用 GitHub 作为图床,用开源工具 Picgo 关联 GitHub 上传图片,再通过 jsdelivr CDN 加速访问,这一套组合很完美,于是我就采用了此方案搭建了自己的图床,依旧继续白嫖,我就不信 GitHub 也挂!



图床虽然搞定了,最糟糕的事情才开始,我要把以前近 500 张的图片重新保存(以前有的图片丢了)和分类,并一个一个上传到 Github,接着还得把图片的新地址改到本地文章,这工作量简直要命,到现在我也才搞定了操作系统篇的图片,网络篇的图片还有 2/3 没弄完,瞬间后悔自己画那么多图。



唉,发完这篇文章,小林还得继续恢复图片……



最近,我都在 B 站学习操作系统,但有时候是想看操作系统,但奈何 B 站首页推送太丰富,看着看着半天就过去了,甚至还花了一天时间专门看一个 UP 主解说「火影忍者」动漫全集,于是就这么忘了文章的事情,哈哈哈。





不过,确实很过瘾,毕竟偷的了忙中闲,方能人上人嘛。



好了,小林是专为大家图解的工具人,我们下次见!






好文推荐



凉了!张三同学没答好「进程间通信」,被面试官挂了....



万粉福利,300 页图解网络 PDF 打包送你



发布于: 2020 年 08 月 13 日 阅读数: 1787
用户头像

小林coding

关注

别问,问就是图解 2018.11.12 加入

公众号:小林coding,爱图解的小林

评论

发布
暂无评论
一口气搞懂「文件系统」,就靠这 20 张图了