绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
深度剖析 Linux cp 的秘密
2021-04-02 14:50:11
坚持思考,就会很酷


大纲

  • cp 引发的思考

    • 分析文件

  • 文件系统

    • 现实的存取场景

    • 文件系统

  • 文件的稀疏语义

    • 什么是稀疏文件

    • 为什么要支持稀疏语义?

    • 怎么创建一个稀疏文件?

    • 稀疏语义接口

    • 稀疏文件的应用

    • Go 语言实现

  • `cp` 的秘密

    • spare 三大策略

    • 深入剖析 `cp  --sparse` 源码

    • cp 快速的原因

  • 稀疏文件的应用

  • 一起做个实验

    • 初始条件准备

    • cp 的实验验证

  • 知识点总结

  • 后记


cp 引发的思考


cp 是啥 ? 是的,就是 Linux 是 Linux 下常用的命令之一,copy 的简写,小伙伴 都用过。

cp 命令处于 Coreutils 库里,是 GNU 项目维护的一个核心项目,提供 Linux 上核心的命令。

今天用 cp 命令,把小伙伴惊到了,引发了我对其中细节的思考。

背景是这样的,奇伢今天用 cp  拷贝了一个 100 GiB 的文件,竟然一秒不到就拷贝完成了。一个 SATA 机械盘的写能力能到 150 MiB/s (大部分的机械盘都是到不了这个值的)就算非常不错了,所以,正常情况下,copy 一个 100G 的文件至少要 682 秒 ( 100 GiB/ 150 MiB/s ),也就是 11 分钟。

sh-4.4# time cp ./test.txt ./test.txt.cp

real m0.107s
user m0.008s
sys m0.085s

上面是我们理论分析,少要 11 分钟,实际情况却是我们 cp 一秒没到就完成了工作,惊呆了,为啥呢?并且还有一个更诡异的我文件系统大小才 40 GiB,为啥里面会有一个 100 G的文件呢?


分析文件


我们先用 ls  看一把文件,显示文件确实是 100 GiB.

sh-4.4ls -lh
-rw-r--r-- 1 root root 100G Mar  6 12:22 test.txt

但是再用 du 命令看却只有 2M ,这是怎么回事?(且所在的文件系统总空间都没 100G 这么大)

sh-4.4# du -sh ./test.txt
2.M ./test.txt

再看 stat 命令显示的信息:

sh-4.4stat ./test.txt
  File: ./test.txt
  Size107374182400 Blocks4096       IO Block4096   regular file
Device78h/120d Inode3148347     Links1
Access: (0644/-rw-r--r--)  Uid: (    /    root)   Gid: (    /    root)
Access2021-03-13 12:22:00.888871000 +0000
Modify2021-03-13 12:22:46.562243000 +0000
Change2021-03-13 12:22:46.562243000 +0000
 Birth-

stat 命令输出解释:

  1. Size 为 107374182400(知识点:单位是字节),也就是 100G ;
  2. Blocks 这个指标显示为 4096(知识点:一个 Block 的单位固定是 512 字节,也就是一个扇区的大小),这里表示为 2M;

划重点

  • Size 表示的是文件大小,这个也是大多数人看到的大小;
  • Blocks 表示的是物理实际占用空间

所以,注意到一个新概念,文件大小实际物理占用,这两个竟然不是相同的概念。为什么会这样?

这里先梳理下文件系统的基础知识,文件系统究竟是怎么存储文件的?(以 Linux 上 ext系列的文件系统举例)


文件系统


文件系统听起来很高大上,通俗话就用来存数据的一个容器而已,本质和你的行李箱、仓库没有啥区别。只不过文件系统存储的是数字产品而已。我有一个视频文件,我把这个视频放到这个文件系统里,下次来拿,要能拿到我完整的视频文件数据,这就是文件系统,对外提供的就是存取服务


现实的存取场景


就跟你在火车站使用的寄存服务一样,包裹我能存进去,稍后我能取出来,就可以了。问题来了,存进去?怎么取?仔细回忆下存储行李的场景。

存行李的时候,是不是要登记一些个人信息?对吧,至少自己名字要写上。可能还会给你一个牌子,让你挂手上,这个东西就是为了标示每一个的行李。



取行李的时候,要报自己名字,有牌子的给他牌子,然后工作人员才能去特定的位置找到你的行李(不然机场那么多人,行李都长差不多,他肯定不知道你的行李是哪个)。



划重点:存的时候必须记录一些关键信息(记录ID、给身份牌),取的时候才能正确定位到。


文件系统


回到我们的文件系统,对比上面的行李存取行为,可以做个简单的类比;

  1. 登记名字就是在文件系统记录文件名;
  2. 生成的牌子就是元数据索引;
  3. 你的行李就是文件;
  4. 寄存室就是磁盘(容纳东西的物理空间);
  5. 管理员整套运行机制就是文件系统;

上面的对应并不是非常严谨,仅仅是帮助大家理解文件系统而已,让大家知道其实文件系统是非常朴实的一个东西,思想都来源于生活。

划重点:文件系统的存储介质是磁盘,文件系统是软件层面的,是管理员,管理怎么使用磁盘空间的软件系统而已。


空间管理


现在思考文件系统是怎么管理空间的?

如果,一个连续的大磁盘空间给你使用,你会怎么使用这段空间呢?

直观的一个想法,我把进来的数据就完整的放进去。



这种方式非常容易实现,属于眼前简单,以后麻烦的方式。因为会造成很多空洞,明明还有很多空间位置,但是由于整个太大,形状不合适(数据大小),哪里都放不下。因为你要放一个完整的空间。

这种不能利用的空间我们称之为碎片,准确的说是外部碎片,这种碎片在内存池分配内存的时候常见,产生的原理是一样的。

怎么改进?有人会想,既然整个放不进去,那就剁碎了呗。这里塞一点,那里塞一点,就塞进去了。

对,思路完全正确。改进的方式就是切分,把空间按照一定粒度切分。每个小粒度的物理块命名为 Block,每个 Block 一般是 4K 大小,用户数据存到文件系统里来自然也是要切分,存储到每一个 Block 。Block 粒度越小则外部碎片则会越少(注意:元数据量会越大),可以尽可能的利用到空间,并且完整的用户数据文件存储到磁盘上则不再连续,而是切成一个个 Block 大小的数据块存到磁盘的各个角落上。



图示标号表示这个完整对象的 Block 的序号,用来复原对象用的。

随之而来又有一个问题:你光会切成块还不行,取文件数据的时候,要给完整的用户数据出去,用户不管你内部怎么实现,他只想要的是初的样子。所以,要有一个表记录该文件对应所有 Block 的位置,要把每一个 Block 的位置记录好,取文件的时候,对照这表恢复出一个完整的块给到用户。

所以,写流程再完善一下就是这样子:

  1. 先写数据:数据先按照 Block 粒度存储到磁盘的各个位置;
  2. 再写元数据:然后把 Block 所在的各个位置保存起来,这也就是元数据,文件系统里叫做 inode(我用一本书来表示);


文件读流程则是:

  1. 先读元数据,找到各个 Block 的位置;
  2. 然后读数据,构造一个完整的文件,给到用户;



inode/block 概念


好,现在我们引出了两个概念:

  1. 磁盘空间是按照 Block 粒度来划分空间的,存储数据的区域全都是 Block,我们叫做数据区域;
  2. 文件存储不再连续存储在磁盘上,所以需要记录元数据,这个我们叫做 inode;

文件系统中,一个 inode 对应一个文件,inode 的个数则是在文件系统格式化的时候就确定好了的,换言之,一个 local 文件系统支持的文件数是天然就有上限的

block 固定大小,每个 4k(大部分文件系统都是,这里不做纠结),block 意图存储打散的用户数据。

无论是 inode 区,还是 block 区,本质上都是在线性的磁盘空间上。文件系统的空间层次如下:



一个文件的对应一个 inode,这个文件需要按照 Block 切分存储在磁盘上,存储的位置则由 inode 记录起来,通过 inode 则能找到 block,也就获取到用户数据。

现在有一个新的小问题,inode 区和 block 区都是在初始化就构造好的。存储一个文件的时候,需要取一个空闲的 inode,然后把数据切分成 4k 大小存储到空闲的 block 上,对吧?

划重点:空闲的inode,空闲的 block。 这个很关键,已经存储了数据的地方不能再让写,不然会把别人的数据覆盖掉。

那么,怎么区分空闲和已经在用的 inode ,block 呢?

答案是 :inode 区和 block 区分别需要另一张表,用来表示 inode 是否在用,block 是否在用,这个表的名字我们叫做 bitmap 表。bitmap 是一个 bit 数组,用 0 表示空闲,1 表示在用,如下:



bitmap 什么时候用呢?自然是写的时候,也就是分配 inode 或者 block 的时候,因为只有分配的时候,你才需要找空闲的空间。

上图我为了突出本质思想,类似于超级块,块描述符都省略了,这个感兴趣可以自己扩展,这里只突出主干哈。

小结一下

  1. bitmap 本质是个 bit 数组,占用空间极其少,用 0 来表示空闲,1 表示在用。使用时机是在创建文件,或者写数据的时候;
  2. inode 则对应一个文件,里面存储的是元数据,主要是数据 block 的位置信息;
  3. block 里面存储的是用户数据,用户数据按照 block 大小(4k)切分,离散的分布在磁盘上。读的时候只有依赖于 inode 里面记录的位置才能恢复出完整的文件;
  4. inode 和 block 的总个数在文件系统格式化的时候就确定了,所以文件数和文件大小都是有上限的;

一个文件真实的模样


上面是抽象的样子,现在我们看一个真实的 inode -> block 的样子。一个文件除了数据需要存储之外,一些元信心也需要存储,例如文件类型,权限,文件大小,创建/修改/访问时间等,这些信息存在 inode 中,每个文件对应一个inode 。

看一下 inode 的数据结构(就以 linxu ext2 为例,该结构定义在 linux/fs/ext2/ext2.h 头文件中 ):

struct ext2_inode {
    __le16  i_mode;     /* File mode */
    __le16  i_uid;      /* Low 16 bits of Owner Uid */
    __le32  i_size;     /* Size in bytes */
    __le32  i_atime;    /* Access time */
    __le32  i_ctime;    /* Creation time */
    __le32  i_mtime;    /* Modification time */
    __le32  i_dtime;    /* Deletion Time */
    __le16  i_gid;      /* Low 16 bits of Group Id */
    __le16  i_links_count;  /* Links count */
    __le32  i_blocks;   /* Blocks count */
    __le32  i_flags;    /* File flags */

    __le32  i_block[EXT2_N_BLOCKS];/* Pointers to blocks */
    __le32  i_file_acl; /* File ACL */
    __le32  i_dir_acl;  /* Directory ACL */
    __le32  i_faddr;    /* Fragment address */
};

重点

  • 上面的结构 mode,uid,size,time 等信息就是我们常说的文件类型,大小,创建修改等时间元数据;
  • 注意到 i_block[EXT2_N_BLOCKS]  这个字段,这个字段将会带你找到数据, 因为里面存储的就是 block 所在的位置,也就是 block 的编号;

再来,理解下什么叫做 block 的位置(编号)。



位置就是编号,记录位置就是记录编号,编号就是索引。

我们看到有一个数组:i_block[EXT2_N_BLOCKS],这个数组是存储 block 位置的数组。其中 EXT2_N_BLOCKS 是一个宏定义,值为 15 。也就是说,i_block 是一个 15 个元素的数组,每个元素是 4 字节(32 bit)大小。

举个例子,假设我们现在有一个 6k 的文件,那么只需要 2 个 block 就可以存下了,假设现在数据就存储在编号为 3 和 101  这两个 block 上,那么如下图:



i_block[15] 个元素存的是 3,第二个存储的是 101,其他槽位没用用到,由于 inode 的内存是置零分配的,所以里面的值为 0,表示没有在使用 . 我们通过 [3, 101] 这两个 block 就能拼装出完整的用户数据了。用户的 6k 文件组成如下:

  1. 个 4k 数据在 [3*4K, 4*4K] 范围;
  2. 第二个 2k 数据在 [ 101*4K, 101*4K+2K] 范围;

好,现在我们知道了每个定长 block 都有编号,我们的 i_block[15] 数组 通过有序存储这个编号找到文件数据所在的位置,并且拼装出完整文件。

思考问题:区分文件的切分成 4k 块的编号和 磁盘上物理 4k 块的编号的区别。

举个栗子,一个文件 12K 的大小,那么按照 4K 切分会存储到 3 个 物理 block 上。

文件第 0 个 4k 存储到了 101 这个物理 block 上;文件第 1 个 4k 存储到了 30  这个物理 block 上;文件第 2 个 4k 存储到了 11  这个物理 block 上;

文件逻辑空间上的编号是从 0 开始,到 2 结束,对应存储的物理块编号分别是 101,30,11 。

思考问题:这么一个 inode 结构能够表示多大的文件?

我们看到 inode->i_block[15] 是一个一维数组,里面能存 15 个元素。也就是能存 15 个 block 的编号,那么如果直接存储文件的 block 编号大能表示 60K (15*4K) 的文件。换句话说,如果我拿着 15 个槽位全部用来存储文件的编号,这个文件系统支撑的大文件却就是 60K。惊呆了?(注意:ext2 文件系统是可以创建 4T 以内的文件的!!)

那我们自然会思考,怎么解决呢?怎么才能支撑更大的文件?

直接思考就是用更大的数组,把 inode->i_block  数组变得更大。比如,如果你想要支持 100G 的文件:

那么,需要 i_block 数组大小为 26214400 (计算公式:100\*1024\*1024/4),也就是要分配一个 i_block[26214400]  的数组。

每个编号占用 4 字节,这个数组就占用 100M 的空间(计算公式:(26214400\*4)/1024/1024)。100M !这里就有点夸张了,注意到 i_block 只是一个 inode 内部的字段,是一个静态分配的数组,也就是说,这个文件系统为了支持大 100G 的文件存入,每一个 inode 都要占用 100M 的内存,就算你是一个 1K 的文件,inode 也会占用这么大的内存空间。并且,这种方案扩展性差,支持的文件 size 越大,i_block[N] 消耗内存情况越严重。这是无法接受的。

思考问题:怎么才能让你既能表示更大的文件,又能不浪费占用空间?

我们仔细分析这个问题,你会发现,这里有 2 个核心问题:

  1. 点,核心在于浪费内存空间(关键点是要保证 inode 内存结构的稳定,无论文件怎么变,inode 结构本身不能变);
  2. 第二点,仔细思考你会发现,无论是什么神仙方案,如果你要存储一个按照 4k 切分的 100G 文件,都是需要 100M 的空间来存储索引( block 编号),但是 99.99% 的文件可能都没有这么大;

我们前面用一个大数组来一把存储 block 编号的方案固然简单,但是问题在于太过死板。核心问题在于存储 block 编号的数组是预分配的,为了还没有发生并且 99% 场景都不会发生的事情(文件大小达到 100G),却不管三七二十一,提前准备好了完整的 block 索引数组,预分配就是浪费的根源

那么知道了这两个问题,下一步分析下一个个解决:


索引存磁盘


问题一的解决:索引存磁盘

既然问题在于浪费内存,inode 内存分配不灵活,那就可以看把 inode->i_block 下放到磁盘。

为什么?

因为磁盘的空间比内存大了不止一个量级。100M 对内存来说很大,对磁盘来说很小。换句话说,用把用户数据所在的 block 编号存到磁盘上去,这个也需要物理空间,使用的也是 block 来存储,只不过这种 block 存储的是 block 编号信息,而不是用户数据。

那么我们怎么通过 inode 找到用户数据呢?

因为这个 block 本身也有编号,我们则需要把这个存储用户 block 编号的 block 所在块的编号存储在 inode->i_block[15] 里,当读数据的时候,我们需要先找到这个存储编号的 block,然后再通过里面存储的用户数据所在的 block 编号找到用户所在的 block ,去读数据。

这个存储用户 block 编号的 block 所在块的编号我们叫做间接索引,然后我们根据跳转的次数可以分类成一级索引,二级索引,三级索引。顾名思义,一级索引就是跳转 1 次就能定位到用户数据,二级索引就是跳转 2 次,三级索引就是跳转 3 次才能定位到用户数据。那么 inode->i_block[15]  里面存储的可以直接定位到用户数据的 block 就是直接索引

终于可以说回 ext2 的使用了,ext2 的 inode->i_block[15] 数组。知识点来了,按照约定,这 15 个槽位分作 4 个不同类别来用:

  1. 前 12 个槽位(也就是 0 - 11 )我们成为直接索引
  2. 第 13 个位置,我们称为 1 级索引
  3. 第 14 个位置,我们称为 2 级索引
  4. 第 15 个位置,我们称为 3 级索引


好,那我们在来看下直接索引,一级,二级,三级索引的表现力。

直接索引:能存 12 个 block 编号,每个 block 4K,就是 48K,也就是说,48K 以内的文件,只需要用到 inode->i_block[15]  前 12 个槽位存储编号就能完全 hold 住。

一级索引

inode->i_block[12] 这个位置存储的是一个一级索引,也就是说这里存储的编号指向的 block 里面存储的也是 block 编号,里面的编号指向用户数据。一个 block 4K,每个元素 4 字节,也就是有 1024 个编号位置可以存储。

所以,一级索引能寻址 4M(1024 * 4K)空间 。

二级索引

二级索引是在一级索引的基础上多了一级而已,换算下来,有了 4M 的空间用来存储用户数据的编号。所以二级索引能寻址 4G (4M/4 * 4K) 的空间。

三级索引

三级索引是在二级索引的基础上又多了一级,也就是说,有了 4G 的空间来存储用户数据的 block 编号。所以二级索引能寻址 4T (4G/4 * 4K) 的空间。

后,看一眼完整的表示图:



所以,在我们 ext2 的文件系统上,通过这种间接块索引的方式,大能支撑的文件大小 = 48K + 4M + 4G + 4T ,约等于 4 T。文件系统大支撑 16T 空间,因为 4 Byte 的整形大数就是 2^32=4294967296 , 乘以 4K 就等于 16 T。

ext2 文件系统支持的大单文件大小和文件系统大容量就是这么算出来的(温馨提示:ext4 文件系统不仅兼容间接块的实现,还使用的是 extent 模式来管理的空间,大支持单文件 16 TB ,文件系统大 1 EB)。

思考:这种多级索引寻址性能表现怎么样?

在不超过 12 个数据块的小文件的寻址是快的,访问文件中的任意数据理论只需要两次读盘,一次读 inode,一次读数据块。访问大文件中的数据则需要多五次读盘操作:inode、一级间接寻址块、二级间接寻址块、三级间接寻址块、数据块。


多级索引和后分配


问题二解决:多级索引和后分配

一级索引不够,表现力太差,预留空间又太浪费,不预留空间又无法扩展,怎么解决?

既然问题在于预分配,我们使用后分配(瘦分配,或精简分配)解决。也就是说用户文件数据有多大,我才分配出多大的数组。举个例子,我们存储 100 G 的文件,那么就要用到三级索引块,多分配 26214400 个槽位的数组(因为要 26214400 个 block)。如果是存储 6K 的文件,那么只需要 2 个槽位的数组。

索引数组的后分配

后分配这里说的是 block 索引编号数组的后分配,需要用到的时候才分配,而不是说,现在用户存储一个 1k 的文件,我上来就给他分配一个 100M 的索引数组,只是为了以后这个文件可能增长到 100 G。

数据的后分配

既然这里说到,关于后分配还有一个层面,就是数据所占的空间也是用到了才分配,这个也就是涉及到今天 cp的秘密的核心问题。

实际的栗子

先看下下正常的文件写入要做的事情(注意这里只描述主干,实际流程可能,有优化):

  1. 创建一个文件,这个时候分配一个 inode;
  2. 在 [ 0,4K ] 的位置写入 4K 数据,这个时候只需要 一个 block 假设编号 102,把这个编号写到 inode->i_block[0] 这个位置保存起来;
  3. 在 [ 1T,1T+4K ] 的位置写入 4K 数据,这个时候需要分配一个 block 假设编号 7,因为这个位置已经落到三级索引才能表现的空间了,所以需要还需要分配出 3 个索引块;
  4. 写入完成,close 文件;

这里解释下文件偏移位置 [1T, 1T+4K] 为什么落到三级索引。

  1. offset 为 1T,按照 4K 切分,也就是 block 268435456 块(注意这个是虚拟文件块,不是物理位置);
  2. 先算出范围:直接索引的范围是 [0, 11] 个,一级索引 [12, 1035],二级索引 [1036, 1049611], 三级索引 [1049612, 1074791435],(有人如果不知道怎么来的话,可以往前看看 inode 的结构,直接索引 12个,一级索引 1024 个,二级 1M 个,三级 1G 个,然后算出来的);
  3. 268435456 落在三级索引 [1049612, 1074791435] 这个范围;

实际存储如图

计算索引:

12 + 1024 + 1024 * 1024 + 1024 * 1024 * 254 + 1024 * 1022 + 1012 =  268435456

实际的物理分配如图:



因为偏移已经用到了 3 级索引,所以除了用户数据的两个 block ,中间还需要 3 个间接索引 block 分配出来。

如果要读 [1T, 1T+4K] 这个位置的数据怎么办?

流程如下

  1. 计算 offset 得出在第 268435456 的位置;
  2. 读出三级索引 inode->i_block[14] 里存储的 block 编号,找到对应的物理 block,这个是级的 block;
  3. 然后读该 block 的第 254+1 个槽位里的数据,里面存储的是第二级的 block 编号,把这个编号读出来,通过这个编号找到对应的物理 block;
  4. 读该 block 的第 1022 +1 个操作的数据,里面存储的是第三级的 block 编号,通过这个编号可以找到物理 block 的数据,里面存储的是用户数据所在 block 的编号;
  5. 读该 block 第 1012+1 个槽位里存储的编号,找到物理 block,这个 block 里存的就是用户数据了;

这个时候,我们的文件看起来是超大文件,size 等于 1T+4K ,但里面实际的数据只有 8 K,位置分别是  [ 0,4K ] ,[ 1T,1T+4K ]。

重点:文件 size 只是 inode 里面的一个属性,实际物理空间占用则是要看用户数据放了多少个 block 。

划重点:没写数据的地方不用分配物理 block 块

没写数据不分配物理块?那是什么?那就是我们下面要说的稀疏文件。


文件的稀疏语义


什么是稀疏文件


终于到我们文件的稀疏语义了,稀疏语义什么意思?

稀疏文件英文名 sparse file 。稀疏文件本质上就是计算机文件,用户不感知,文件系统支持稀疏文件只是为了更有效率的使用磁盘空间而已。稀疏文件就是后分配空间的一种实现形式,做到真正用时才分配,大效率的利用磁盘空间。

就以上面举的栗子,文件大小 1T,但是实际数据只有 8K,这种就是稀疏文件,逻辑大小和实际物理空间是可以不等的。文件大小只是一个属性,文件只是数据的容器,没有用户数据的位置可以不分配空间。


为什么要支持稀疏语义?


还是以上面 1T 的文件举例,如果这 1T 的文件只有首尾分别写了 4K 的数据,而文件系统却要分配 1T 的物理空间,这里将带来巨大的浪费。何不等存了用户数据的时候再分配了,实际数据有多少,才去分配多大的 block ,何必着急的预分配呢?

后分配本着用多少给多少的原则,尽量有效的利用空间。

后分配还有一个优点,这也减少了写入的时间,怎么理解?

因为,如果文件大小 1T,就要分配 1T 的空间,那么初始分配需要写入全零到空间,否则上面的数据可能是随机数。

对于稀疏文件空洞的地方,不占用物理空间,但要保证读的时候返回全 0 数据的语义,即可。

又一个知识点:有时候稀疏文件的空洞和用户真正的全 0 数据是无法区分的,因为对外表现是一样的。

稀疏文件也要文件系统支持,并不是所有的文件系统都支持稀疏语义,比如 ext2 就没有,ext4 才有稀疏语义,支持的标志是实现文件系统的 fallocate 接口。


怎么创建一个稀疏文件?


可以使用 truncate 命令在一个 ext4 的文件系统创建一个文件。

truncate -s 100G  test.txt
  • ls -lh ./test.txt 命令看会发现是一个 100 G 的文件;
  • 但是 du -sh ./test.txt  会发现是一个 0 字节的文件;
  • stat ./test.txt 会发现是 Size: 107374182400 Blocks: 0 的文件;

这就是一个典型的稀疏文件。size 只是文件的逻辑大小,实际的物理空间占用还是得看 Blocks 这个数值。

下面这种 1T 的文件,因为只写了头尾 8K 数据,所以只需要分配 2 个 block 存储用户数据即可。



好,我们再深入思考下,文件系统为什么能做到这个?

这也是为什么理解稀疏语义要先了解文件系统的实现的原因。

  1. 首先,关键的是把磁盘空间切成离散的、定长的 block 来管理;
  2. 然后,通过 inode 能查找到所有离散的数据(保存了所有的索引);
  3. 后,实现索引块和数据块空间的后分配;

这三点是层层递进的。


稀疏语义接口


为了知识的完整性,简要介绍稀疏语义的几个接口:

  1. preallocate(预分配):提供接口可以让用户预占用文件内指定范围的物理空间;
  2. punch hole(打洞):提供接口可以让用户释放文件内指定范围的物理空间;

这两个操作刚好相反。

预分配的意思是?

就是说,当你创建一个 1T的文件,如果你没写数据,这个时候其实没有分配物理空间的,支持稀疏语义的文件系统会提供一个 fallocate 接口给你,让你实现预分配,也就是说把这 1T 的物理空间现在就分配出来。

思考:这个有什么好处呢?

  • ,如果你命中注定要 1T 的空间,预分配是有好处的,把空间分配的工作量集中在初始化的时候一把做了,避免了实时现场分配的开销;
  • 第二,如果不提前占坑,很有可能等你想要的时候已经没有空间可占用了。所以你把物理空间先占好,就可以安心使用了;

linux 提供了一个 fallocate 命令,可以用来预分配空间。

fallocate -o  -l 4096 ./test.txt

这个命令的意思就是给 text.txt 这个文件 [0, 4K] 的位置分配好物理空间。

打洞(punch hole) 是干啥的呢?

这个调用允许你把已经占用的物理空间释放掉,从而达到快速释放的目的。这种操作在虚拟机镜像的场景用得多,通常用于快速释放空间,punch hole 能够让业务更有效的利用空间。

linux 提供了一个 fallocate 命令也可以用来 punch hole 空间。

fallocate -p -o  -l 4096 ./test.txt

这个命令的意思是把 test.txt  [ 0,  4K ] 的物理空间释放掉。


Go 语言实现


稀疏文件本身和编程语言无具体关系,可以用任何语言实现,我下面以 Go 为例,看下稀疏文件的预分配和打洞(punch hole)是怎么实现的。

预分配实现:

func PreAllocate(f *os.File, sizeInBytes int) error {
 // use mode = 1 to keep size
 // see FALLOC_FL_KEEP_SIZE
 return syscall.Fallocate(int(f.Fd()), 0x0int64(sizeInBytes))
}

punch hole 实现:

//  mode 0 change to size                  0x0
//  FALLOC_FL_KEEP_SIZE                  = 0x1
// FALLOC_FL_PUNCH_HOLE                 = 0x2

func PunchHole(file *os.File, offset int64size int64) error {
 err := syscall.Fallocate(int(file.Fd()), 0x1|0x2offsetsize)
 if err == syscall.ENOSYS || err == syscall.EOPNOTSUPP {
   return syscall.EPERM
 }
 return err
}

可以看到,本质上都是系统调用 fallocate ,然后带不同的参数而已。指定文件偏移和长度,就能预分配物理空间或者释放物理空间了。

这里有一个知识点:punch hole 的调用要保证 4k 对齐才能释放空间。

举个例子,比如:

punch hole [0, 6k] 的数据,你会发现只有 [0, 4k] 的数据物理块被释放了,[4k, 6k] 所占的 4k 物理块还占着空间呢。

这个很容易理解,因为磁盘的物理空间是划分成 4k 的 block,这个是小单位了,不能再分了,你无法切割一个小的单位。

值得注意的是,就算你没有 4k 对齐的发送调用,fallocate 也不会报错,这个请注意了。


cp 的秘密


铺垫了这么久的基础知识,终于到我们的 cp 命令的解密了。回到开始的问题,cp 一个 100G 的文件 1 秒都不到,为什么这么快?

说到现在,这个问题就很清晰了,这个 100G 的文件是个稀疏文件,盲猜一手:cp 的时候只拷贝了有效数据,空洞是直接跳过的。 往前看 stat 命令和 ls 命令显示的差距就知道了。

接下来我们具体看一下 cp 的实现。

cp 有一个参数 --sparse 很有意思,sparse 这个参数控制这 cp 命令对稀疏文件的行为,这个参数有三个值可选:

  1. --sparse=always :空间省;
  2. --sparse=auto :默认值,速度快;
  3. --sparse=never :吭呲吭呲 copy,傻;

cp 默认的时候,sparseauto 策略。auto,always,never 分别是什么策略呢?


spare 三大策略

auto 策略

默认的情况下,cp 会检查源文件是否具有稀疏语义,对于不占物理空间的位置,目标文件不会写入数据,从而形成空洞。

所以,对于我们的例子,真实的就只进行了 2M 的 IO ,预期的 100G 文件,只拷贝了 2M 的数据,自然飞快了,自然惊艳所有人。

auto 是默认策略,使用该模式的时候,cp 内部实现是通过系统调用拿到文件的空洞位置情况,然后对这些位置目标文件会保持空洞。

注意,不会对非空洞位置的文件内容做判断,如果用户数据占用了物理块,但是是全 0 数据,这种情况下,auto 模式不会识别,会以全零的数据写入到目标文件。这个是跟 always 大的区别。

auto 策略下 cp 的文件的文件,size,物理 block 数量都和源文件一致。

always

这种方式是激进的,追求空间的小化。在 auto 的基础之上,还多做了一步:对源文件内容做了判断。

在读出源数据之后,就算这块数据位置在源文件不是空洞,也会自己在程序里做一次判断,判断是否是全 0 的数据,如果是,那么也会在目标文件里对应的位置创建空洞(不分配物理空间)。

这种方式则会导致源文件的 size 和目标文件一样(三种策略下,文件size 都是不变的),但是 物理 blocks 占用却更小。

never

这种方式保守,实现也简单。不管源文件是否是稀疏文件,cp 完全不感知,读出来的任何数据都直接写入目标文件。也就是说,如果一个 100G 的文件,就算只占用了 4K 的物理空间,也会创建出一个 100G 的目标文件,物理空间就占用 100G。

所以,如果你 cp 的时候带了这个参数,那么将会非常非常慢。


深入剖析 cp --sparse 源码


上面的都是结论,现在我们通过源码再深入理解下 cp 的原理,一起围观下 cp 的代码实现。

cp 命令源码在 GNU 项目的 coreutils 项目中,为 Linux 提供外围的基础命令工具。看似极简的 cp,其实代码实现还挺有趣的。

cp 的入口代码在 cp.c 文件中(以下基于 coreutils 8.30 版本):

以一个 cp 文件的命令举例,我们一起走一下源码视角的旅途:

cp ./src.txt dest.txt

首先,在 main 函数里初始化参数:

      switch (c)
        {
        case SPARSE_OPTION:
          x.sparse_mode = XARGMATCH ("--sparse", optarg,
                                     sparse_type_string, sparse_type);
          break;

这里会根据用户传入的参数,对应翻译成一个枚举值,该枚举值就是 SPARSE_NEVERSPARSE_AUTOSPARSE_ALWAYS 其中之一,默认用户没带这个参数的话,就会是 SPARSE_AUTO

static enum Sparse_type const sparse_type[] =
{
  SPARSE_NEVER, SPARSE_AUTO, SPARSE_ALWAYS
};

所以,main 函数里赋值了 x.sparse_mode 这个参数,这个参数也是稀疏文件行为的指导参数,后面怎么处理稀疏文件,就依赖于这个参数。

下面就是依次调用 do_copycopycopy_internal 函数,do_copycopy 这两个函数就是处理一些封装,校验,包括涉及目录的一些逻辑,跟我们本次稀疏文件解密关系不大,直接略过。

copy_internal 则是一个巨长的函数,里面的逻辑多数是一些兼容性,适配场景的考虑,也和本次关系不大。对于一个普通文件( regular 类型) 终调用到 copy_reg 函数,才是普通文件 copy 的实现所在。

  else if (S_ISREG (src_mode)
           || (x->copy_as_regular && !S_ISLNK (src_mode)))
    {
      copied_as_regular = true;
      // 普通文件的拷贝
      if (! copy_reg (src_name, dst_name, x, dst_mode_bits & S_IRWXUGO,
                      omitted_permissions, &new_dst, &src_sb))
        goto un_backup;

普通文件的 copy 就是从函数 copy_reg 才真正开始的。在这个函数里,首先 open 源文件和目标文件的句柄,然后进行数据拷贝。

static bool
copy_reg( ... ) 
{
  // 确认要拷贝数据
  if (data_copy_required)
    {
      // 获取到块大小,buffer 大小等参数
      size_t buf_alignment = getpagesize ();
      size_t buf_size = io_blksize (sb);
      size_t hole_size = ST_BLKSIZE (sb);

      bool make_holes = false;
      // 关键函数来啦,is_probably_sparse 函数就是用来判断源文件是否是稀疏文件的;
      bool sparse_src = is_probably_sparse (&src_open_sb);

      if (S_ISREG (sb.st_mode))
        {
          if (x->sparse_mode == SPARSE_ALWAYS)
            // sparse_always 模式,也是追求空间效率的策略;
            // 所以这种方式不管源文件是否真的是稀疏文件,都会生成稀疏的目标文件;
            make_holes = true;
          // 如果是 sparse_auto 的策略,并且源文件是稀疏文件,那么目标文件也会是稀疏文件(也就是可以有洞洞的文件)
          if (x->sparse_mode == SPARSE_AUTO && sparse_src)
            make_holes = true;
        }

      // 如果到这里判断不是目标不会是稀疏文件,那么就使用更有效率的方式来 copy,比如用更大的 buffer 来装数据,一次 copy 更多;
      if (! make_holes)
        {
            // 略
        }

      // 源文件是稀疏文件的情况下,可以使用 extent_copy 这种更有效率的方式进行拷贝。
      if (sparse_src)
        {
          if (extent_copy (source_desc, dest_desc, buf, buf_size, hole_size,
                           src_open_sb.st_size,
                           make_holes ? x->sparse_mode : SPARSE_NEVER,
                           src_name, dst_name, &normal_copy_required))
            goto preserve_metadata;
            
        }

      // 如果源文件判断不是稀疏文件,那么就使用标准的 sparse_copy 函数来拷贝。
      if (! sparse_copy (source_desc, dest_desc, buf, buf_size,
                         make_holes ? hole_size : ,
                         x->sparse_mode == SPARSE_ALWAYS, src_name, dst_name,
                         UINTMAX_MAX, &n_read,
                         &wrote_hole_at_eof))
        {
          return_val = false;
          goto close_src_and_dst_desc;
        }
        // 略
    }
    
}

以上对于 copy_reg 的代码我做了极大的简化,把关键流程梳理了出来。

小结

  1. copy_reg 函数才是真正 cp 一个普通文件的逻辑所在,源文件的打开,目标文件的创建和数据的写入都在这里;
  2. 拷贝之前,会先用 is_probably_sparse 函数来判断源文件是否属于稀疏文件;
  3. 如果是 sparse always 模式,那么无论源文件是否是稀疏文件,那么都会尝试生成稀疏的目标文件(这种模式下,源文件如果是非稀疏文件,会判断是否是全 0 数据,如果是的话,还是会在目标文件中打洞);
  4. 如果是 sparse auto 模式,源文件是稀疏文件,那么生成的目标文件也会是稀疏文件;
  5. 源文件为稀疏文件的时候,会尝试使用效率更高的 extent_copy 函数来拷贝数据;
  6. 如果是 never 模式,那么是调用 sparse_copy 函数来拷贝数据,并且里面不会尝试 punch hole,拷贝过程会非常慢,会生成一个实打实的目标文件,物理空间占用完全和文件size一致;

上面的小结,提到几个有意思的点,我们一起探秘下几个问题。


问题一:is_probably_sparse 函数是怎么来判断源文件的?

看了源码你会发现,非常简单,其实就是 stat 一下源文件,拿到文件大小 size,还有物理块的占用个数(假设物理块 512 字节),比一下就知道了。

static bool
is_probably_sparse (struct stat const *sb)
{
  return (HAVE_STRUCT_STAT_ST_BLOCKS
          && S_ISREG (sb->st_mode)
          && ST_NBLOCKS (*sb) < sb->st_size / ST_NBLOCKSIZE);
}

举个例子,文件大小 size 为 100G,物理占用块 8 个,那么 100G/512字节 > 8,所以就是稀疏文件。

文件大小 size 为 4K,物理占用块 8 个,那么 4K/512字节 == 8,所以就不是稀疏文件。


问题二:extent_copy 为什么更有效率?

关键在于里面的一个子函数 extent_scan_read 的实现,extent_scan_read 位于 extent-scan.c 文件中。extent_scan_read 位于 extent_copy 开头,用来获取到源文件的空洞位置信息。这个就是 extent_copy 高效率的根本原因。extent_scan_read 通过这个函数能够拿到文件的空洞的详细位置,那么拷贝数据的时候,就能针对性的跳过这些空洞,只拷贝有效的位置即可。

那么,不禁又要问, extent_scan_read 又是怎么实现的呢?

答案是:ioctl 系统调用,搭配 FS_IOC_FIEMAP 参数,也就是 fiemap 的调用。

/* Call ioctl(2) with FS_IOC_FIEMAP (available in linux 2.6.27) to obtain a map of file extents excluding holes.  */

fiemap 这个是一个非常关键的特性,ioctl 搭配 FS_IOC_FIEMAP 这个函数能够拿到文件的物理空间分配关系,能够让用户知道长达 100G 的文件中,哪些位置才是真正有物理块存储数据的,哪些位置是空洞。

这个特性则由文件系统提供,也就是说,只有文件系统提供了这个对外接口,我们才能拿得到,比如 ext4,就支持这个接口,ext2 就没有。


问题二:sparse_copy 为什么慢,里面哟是做了啥?

这个函数是标准的 copy 函数,对比 extent_copy 来说,没有 fiemap 的加持,那么这个函数就自己判断是否是空洞,怎么判断?

sparse_copy 认为,只要大块连续的全 0 数据,那么就认为是空洞,目标文件就不用写入,直接打洞即可。

判断是否全 0 的函数是is_nul,位于 system.h 头文件中,实现非常简单,就是看整个内存块是否全部为 0 。

举个例子,现在 sparse_copy 从源文件里读出 4k 的数据,发现全都是 0,那么目标文件对应的位置就不会写入,而是直接 punch hole 打洞,节省空间。

但是注意了,这种行为只有在激进的 sparse always 策略才是这样的。如果是其他策略,sparse_copy 不会做这样做,而是老老实实的拷贝数据,哪怕是全 0 的数据,也要如实的写入到目标文件。

所以,always 模式下,目标文件所占物理空间比源文件小的根本原因就在于 sparse_copy 这个函数的实现。


cp 快速的原因


梳理到这里,cp 的秘密已经彻底揭开了,cp 一个 100G 的文件为什么那么快?

因为源文件是稀疏文件啊,文件看似 100G,实际只占用了 2M 的物理空间。文件系统将文件大小和物理空间占用这两个概念解耦,使得有更灵活的使用姿势,更有效的使用物理空间。

cp 默认的情况下,通过文件系统提供的 fiemap 接口,获取到文件所有的空洞信息,然后跳过这些空洞,只 copy 有效的数据,极大的减少了磁盘 io 的数据量,所以才那么快。

总结下 cp --sparse 三个参数的特点:

  1. auto 模式:默认模式,一致的模式(如果没有用户全0 块数据,那么可能也是速度快的),会根据源文件的实际空间占用复制数据,目标文件和源文件一致。无论是文件 size 还是物理 blocks;
  2. always 模式:追求小空间占用的模式,就算源文件不是稀疏文件,而仅仅是有些连续大块的全 0 数据,也会尝试在目标文件上 punch hole,从而节省空间,这种方式会导致目标文件的物理 blocks 可能比源文件要小
  3. never 模式:低效,速度慢的方式。这种方式无论源文件是啥,全都是实打实的复制,不管是空洞还是全 0 数据,都会在目标文件写入;

动画演示(精髓)

精髓所在,前面知识点就算全都忘了,只记得这三张图,你也赚了。

cp src.txt dest.txt


cp --sparse=always src.txt dest.txt


cp --sparse=never src.txt dest.txt



稀疏文件的应用


稀疏文件在哪些地方有应用呢?

  1. 数据库快照:生成一个数据库快照时会生成一个稀疏文件,稀疏文件一开始并不会占用磁盘空间。当源数据库发生写操作时,就把修改前的原数据块复制且只复制一次到稀疏文件中;
  2. MySQL5.7 有一种数据压缩方式,其原理就是利用内核Punch hole特性,对于一个16kb的数据页,在写文件之前,除了 Page 头之外,其他部分进行压缩,压缩后留白的地方使用 punch hole 进行 “打洞”,在磁盘上表现为不占用空间,从而达到快速释放物理空间的目的;
  3. qemu 磁盘镜像文件的空间回收场景;


一起做个实验


后我们演示下实验,检验看下你懂了吗?找一台 linux 机器,跟着运行下面的命令。


初始条件准备


步骤一:创建一个文件(预期占用 1 个 block)。

echo =========== test ======= > test.txt

步骤二:truncate 成 1G 的稀疏文件。

truncate -s 1G ./test.txt

步骤三:把 1M 到 1M+4K 的位置预分配出来(并且是写 0 分配,预期到这里要占用 2 个 block,也就是 8K 数据)。

fallocate -o 1048576 -l 4096 -z ./test.txt

步骤四:stat 命令检查下情况。

sh-4.4stat test.txt
  Filetest.txt
  Size1073741824 Blocks16         IO Block4096   regular file
Device6ah/106d Inode3148347     Links1
Access: (0644/-rw-r--r--)  Uid: (    /    root)   Gid: (    /    root)
Access2021-03-12 15:37:54.427903000 +0000
Modify2021-03-12 15:46:00.456246000 +0000
Change2021-03-12 15:46:00.456246000 +0000
 Birth-

我们看到 Size: 1073741824 Blocks: 16 ,Size  大小等于 1G,stat 显示的 Blocks 是扇区(512字节)的个数,也就是说,物理空间占用 8K,符合预期

也就是说:

  1. 文件大小为 1G;
  2. 实际数据在 [0, 4K] 和 [1M, 1M+4K] 这两个位置才有写入;
  3. 其中 [0, 4K] 范围为正常数据, [1M, 1M+4K] 这段范围的数据为全 0 数据;

好,初始条件准备好了,下面我们开始对 cp --sparse 的三个行为做实验。

cp 的实验验证

默认策略:

cp ./test.txt ./test.txt.auto

always 策略:

cp --sparse=always ./test.txt ./test.txt.always

never 策略(这条命令敲下去可能有点慢哦,并且要预留好足够空间):

cp --sparse=never ./test.txt ./test.txt.never

以上三个命令敲完,生成了三个文件,给大家 1 秒钟的思考时间,思考下 test.txt.autotest.txt.alwaystest.txt.never,这三个文件的属性有何异同。

..... ..... .....

结果揭秘:

test.txt.auto

sh-4.4stat ./test.txt.auto
  File: ./test.txt.auto
  Size1073741824 Blocks16         IO Block4096   regular file
Device6ah/106d Inode3148348     Links1
Access: (0644/-rw-r--r--)  Uid: (    /    root)   Gid: (    /    root)
Access2021-03-13 15:58:57.395725000 +0000
Modify2021-03-13 15:58:57.395725000 +0000
Change2021-03-13 15:58:57.395725000 +0000
 Birth-
  • Size: 1073741824:文件大小 1G
  • Blocks: 8:物理空间占用 8K

test.txt.always

sh-4.4stat ./test.txt.always
  File: ./test.txt.always
  Size1073741824 Blocks8          IO Block4096   regular file
Device6ah/106d Inode3148349     Links1
Access: (0644/-rw-r--r--)  Uid: (    /    root)   Gid: (    /    root)
Access2021-03-13 15:59:01.064725000 +0000
Modify2021-03-13 15:59:01.064725000 +0000
Change2021-03-13 15:59:01.064725000 +0000
 Birth-
  • Size: 1073741824:文件大小 1G
  • Blocks: 8:物理空间占用 4K

test.txt.never

sh-4.4stat ./test.txt.never
  File: ./test.txt.never
  Size1073741824 Blocks2097160    IO Block4096   regular file
Device6ah/106d Inode3148350     Links1
Access: (0644/-rw-r--r--)  Uid: (    /    root)   Gid: (    /    root)
Access2021-03-13 15:59:04.774725000 +0000
Modify2021-03-13 15:59:05.977725000 +0000
Change2021-03-13 15:59:05.977725000 +0000
 Birth-
  • Size: 1073741824:文件大小 1G
  • Blocks: 2097160:物理空间占用 1G

所以,你学会了吗?


知识点总结


  1. 文件系统对外提供文件语义,本质只是管理磁盘空间的软件而已;
  2. 经典的文件系统主要划分 3 大块 superblock 区,inode 区,block 区(块描述区,bitmap区这里暂不介绍)。一个文件在文件系统的内部形态由一个 inode 记录元数据加上 block 存储用户存储用户数据样子;
  3. 文件系统的 size 是文件大小,是逻辑空间大小,文件大小 size 和真实的物理空间并不是一个概念
  4. 稀疏语义是文件系统提供的一种特性,根本用途是用来更有效的利用磁盘空间;
  5. 后分配空间是空间利用有效的方式,公有云的云盘靠什么赚钱?就是后分配,你买了 2T 的云盘,在没有写入数据的时候,一个字节都没给你分配,你却是付出 2T 的价格;
  6. stat 命令能够查看物理空间占用,Blocks 表示的是扇区(512字节)个数;
  7. 稀疏文件的空洞和用户真正的全 0 数据是无法区分的,因为对外表现是一样的(这点非常重要);
  8. cp 命令通过调用 ioctl(fiemap)系统调用,可以获取到文件空洞的分布情况,cp 过程中跳过这些空洞,极大的提高了效率(100G 的源文件,cp 只做了十几次 io 搞定了,所以 1 秒足以);
  9. cp 的 sparse 参数从速度快,空间省,数据拷贝多,各有特点,小小的 cp 命令出来的目标文件,其实和源文件并不相同,只不过你没注意到;
  10. 预分配和 punch hole 其实都是fallocate 调用,只是参数不同而已,调用的时候,注意要 4k 对齐才能达到目的
  11. 稀疏文件的 punch hole 应用有很多场景,通常是用来快速释放空间,比如镜像文件;

~完~




后记



本文通过一个日常随处可见、所有人都用过,但是都没有细想过的 cp 命令切入,通过一个常常被我们忽略的现象来剖析其中的原理,里面暗含的存储技术非常之丰富。这次通过分析 cp 的又获得一点秘密的知识点呢。

我把这点小知识给小伙伴讲了一小时,看到他感动欲哭的表情,我觉得他学fei了,非常满意。是我想太多了吗?中午吃饭都没叫我。

以上文章来源于奇伢云存储 ,作者奇伢  


分享好友

分享这个小栈给你的朋友们,一起进步吧。

Linux技术精选专区
创建时间:2020-07-08 10:30:23
Linux,全称GNU/Linux,是一套免费使用和自由传播的类UNIX操作系统,其内核由林纳斯·本纳第克特·托瓦兹于1991年次释出,它主要受到Minix和Unix思想的启发,是一个基于POSIX和Unix的多用户、多任务、支持多线程和多CPU的操作系统。它能运行主要的Unix工具软件、应用程序和网络协议。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

技术专家

查看更多
  • dapan
    专家
戳我,来吐槽~