ext2在设计之初的时候就是通过链表的方式管理目录下的文件项目,ext3,ext4也是直接继承过来了,但随着单个目录下管理的文件越来越多到几十万个,线性的链表查找文件,创建文件(先要查找同名文件)越来越慢,时间复杂的达到了O(n)的级别,尤其对于当前云存储大数据等概念,读写速度是不能接受的。

dirlist_oenhan

为了能快速查找,内核开发人员设计了一个B树索引结构,称为HTree,也就是基于Hash作为键值的索引树,之所以采用hash键值,应该是因为基于文件名做键值可能会导致树分布不均,而且键值长度不一,索引效果差。

查看一个分区是否启用了hash目录索引的方式如下,存在dir_index即是启动目录索引。

1.Hash索引的存储形式

正常情况下目录作为一个inode节点存在存储方式如下:

oenhan

以上是正常的inode和具体数据块之间的关系,目录项是放到数据块里面存储的,如果系统启用了dir_index,整个inode结果不变,变得是内部数据块。部分数据块存储不再是ext3_dir_entry,而是dx_entry。

hash是根据从需要查找的文件名生成的值,block则对应ext3_dir_entry存储到具体的那个物理块上。如下图:

oenhan-目录索引

目录索引的B树结构图如下:

htree-dir index

树的根就是存储在目录的第一个数据块,即dx_root,其中叶节点存储的目录项的内容,当前目录项并非按照线性排序了,而是hash值处于某一个范围内的目录项存储在一个目录项块中;中间节点存储的是存储的是索引项,内容和第一个目录数据块块内容基本一致。

当前每个索引项dx_entry占8个字节,索引树根部dx_root占32个字节,对于一个4KB大小的块,即如图的第一索引,可以索引508个叶块或节点块,第二层索引可以索引511个块,那么目录索引树支持目录大小为508×511×4KB=1014MB,假定一个目录下文件名平均由22个字符长度,那么一个目录项即30B,那么二级索引树最大支持约34M个文件,即3400万个文件,满足了绝大部分的存储场景需求。

具体的结构呈现也是可以通过debugfs工具中的htree看到的:
篇幅原因,日志贴出部分

目录索引的整个结构保持不变,如此,fsck修复的时候可以越过dir_index的机制,避免了复杂的修复机制,但实际修复的时候,索引数据又和具体的目录项数据不同,在每个索引块的前8个字节伪造成0进行区分,即inode为0,相当于被删除的目录项。

2.具体代码实现

2.1 在目录中查找文件

在ext3_find_entry调用中

调用dx_probe获取文件对应目录项的块,使用ext3_bread获取块内容,解析成功目录项。

dx_probe主要内容:

1.将目录文件的第一个数据块读取到内存中,解析成第一层索引。

2.通过循环2次,就可以找到对应的目录项,因为索引信息是根据hash值大小不同进行排列的,可以直接使用折半查找法进行查找。

2.2 在目录里面删除文件

ext3_delete_entry完成这一个动作

2.3 在目录里面新增文件

ext3_add_entry调用ext3_dx_add_entry实现具体索引项中更改,通过dx_probe获取hash值所在块,通过ext3_bread获取块内容后用add_dirent_to_buf完成目录项的添加。

add_dirent_to_buf在解析的目录项中寻找合适的空间,主要有两种:1.目录数据块中有没有使用的空间,2.部分目录项由于其旁边删除目录项而没有使用的空间。如果仍没有空间,返回ENOSPC,存在同名文件,返回EEXIST。

返回ENOSPC后,ext3_dx_add_entry重新申请物理块作为索引块,将原来一个块分裂成两个块,新增的文件仍然按照hash值大小添加到顺序位置,具体参考ext3_dx_add_entry代码。


ext3目录索引机制分析来自于OenHan

链接为:http://oenhan.com/ext3-dir-hash-index

发表评论