摘要: EXT4文件系统可管理高达248块的存储容量，但是搜索块组位图依然沿用EXT2的线性索引方案，从而导致EXT4的可用性随着空闲空间的减少断崖式降低。针对该问题本文提出一种多级块组的文件系统结构，并建立多级位图树索引替代当前EXT4的线性索引方案，以便减少无效索引，提高其可用性。使EXT4文件系统在扩大存储容量的同时能够确保文件系统依然是高效可用的。
关键词：EXT4;树型检索;多级位图;存储容量;
0引言
EXT4文件系统可管理的存储容量从EXT3[1]的最大32TB扩展到1EB，单个文件尺寸也从最大2TB扩展到16TB，但是在实际应用中，EXT4的这些优势并未给用户带来真正的价值，反而一些其他新兴文件系统，比如BTRFS[2]超越EXT4成为下一代文件系统的潜在竞争者。阻碍EXT4应用的一个重要的原因是它的元数据仅仅改变了目录和i-node[3]的结构，使其在单个分区内可拥有几乎不受限制的文件数量和几乎不受限制的单个文件尺寸[4]，而其余元数据比如块、块组和块位图，仍然沿用EXT2/3的结构。因此EXT4在申请或释放一个存储块资源时，依然需要遍历所有块组。对于早于EXT4的文件系统，块组数目最多是217个，采用线性方式检索块组描述符已经不堪重负，而EXT4的块组数目最多是233个，继续采用线性搜索方式将导致灾难性的后果。本文提出了一种EXT4元数据的多级块组结构，在此基础上建立了位图索引树，引入一种树形搜索块组的解决方案，最多增加2次比较就可以命中空闲的块资源，有效改善了EXT4文件系统的可用性。
1 Linux元数据及索引方式
1.1Linux的块/块组/块位图
块是Linux文件系统可访问的最小逻辑单位[5]，8个扇区（4KByte或215bit）是Linux块尺寸的上限。因此，以下讨论固定块尺寸为4KB，若存储空间容量增大，只能扩展块索引的地址位数。
元数据是描述数据的数据，位图[6]是Linux文件系统标识1个块是否被占用的数据，因此是一种元数据。1个位图是1个块，该块的215个比特分别标识215个块的状态（0：空闲，1：占用）。1个块位图所标记的块的集合（尺寸总计128MB），组成Linux文件系统的1个块组。对于超过128MB的存储空间，Linux文件系统依次将其划分成若干块组，每个块组拥有1个块位图，部署在该块组固定的位置上，标识该块组内各个块的状态；每个块组还有1个块组描述符，其中有一个16位整数寄存器bg_free_blocks_count，记录块组内空闲块的数量，它和位图都是Linux的元数据。早于EXT4的Linux版本中，块地址索引的范围限定在32bit，可访问的存储空间最多为232个块或217个块组，容量最高可达232×4KB=16TB。EXT4将块地址索引的范围扩展到48bit，使可访问的存储空间扩展为248个块或233个块组，容量最高可达248×4KB=1EB，可以满足现阶段市场需求。
作者：胡 月