基于Linux文件检索方法的改进研究

庞海飞，常青，张刚

（太原理工大学信息工程学院，太原030024）

基于Linux文件检索方法的改进研究

庞海飞，常青，张刚

（太原理工大学信息工程学院，太原030024）

随着磁盘容量的急剧增大，文件系统的性能以及文件系统的效率会急剧下降，这是因为文件列表过于庞大，传统的文件系统在检索文件时采用的线性搜索方式带来的检索效率低下导致。对Linux虚拟文件系统进行深入剖析，阐述了VFS打开以及新建文件的机制，指出其存在的缺陷及问题。在Linux文件系统的基础上，参考暴雪游戏公司解决hash冲突的blizzard算法，提出一种通过在磁盘上建立文件目录项的哈希表来提高文件查找效率的方法。

Linux，虚拟文件系统，blizzard算法，哈希表

0 引言

Linux系统因其开放性的源代码以及其稳定性广受厂商的热爱，成为目前热门的操作系统之一。Linux下默认的单级子目录数量是31 998，随着磁盘容量的不断扩大，单级目录下可存储的文件数目会越来越多，检索起来相当耗时。导致文件系统性能大幅度下降。因此，对Linux的文件检索速度的提高具有重要意义。

1 Linux文件系统检索文件的机制

1.1 概述

Linux最初采用minix的文件系统，其大小仅限于64 M，文件名长度限于14个字符。经过一段时间的改进与发展，现在的Linux文件系统支持文件名长达255字符［1］。在ext2文件系统中，文件名存储在目录项结构ext2_dir_entry_2中，同一目录下的文件及目录的目录项按线性方式存储。对于常规文件或目录，其数据存储在磁盘介质上面，为了减少对磁盘的操作，内核允许将一部分数据存储在RAM中，当要对文件进行读写操作的时候，则先在内存中做相应的操作，最后再将所做的修改同步更新到磁盘上［2］。

1.2 Linux文件系统打开文件机制分析

Ext2文件系统采用索引节点位图来管理磁盘上的数据块，使用索引节点来管理磁盘上的元数据，每个文件或目录都唯一的对应一个索引节点，当用户要访问文件的时候，需要获取得到该文件的索引节点信息，通过索引节点获得该文件的数据块存储位置。然而索引节点由该文件对应的目录项结构存储，用户首先需要获取得到文件对应的目录项结构［3］。

以下是虚拟文件系统打开文件的流程，在此仅仅是列出关键的几条流程［4］。

（1）获取父目录的inode结构。

（2）解析给定路径分量，计算分量的hash值。

（3）根据父目录的dentry和上面（2）中得到的hash值在dentry_hashtable中查询该路径分量的dentry结构。

（4）如若没找到，则在dentry_cache中分配一个可用dentry，初始化它且将其链入父目录的dentry_subdirs队列中。

（5）将父目录在磁盘上的数据分页提取到页高速缓存中，查找对应的路径分量的ext2_dir_entry_2结构，获取得到该分量的ino号。

（6）通过super_block地址和ino在inode_hashtable中获取该分量的inode结构。

1.3 Linux文件系统检索文件的缺点

本文分析的关键在于1.1中第5点提到的在父目录的目录项下面查找给定文件名的目录项，由ext2_find_entry实现。其具体流程如图1所示：

图1 Linux在页高速中查找文件目录项流程图

Linux2.6.11的源代码中采用循环结构，通过字符串比较来查找给定文件名在父目录下的对应目录项。显然，在单个目录下子文件及子目录数量较多的时候显得力不从心，相当耗时。

2 基于Linux的文件快速检索方法的研究

2.1 Linux下的哈希算法

Linux内核中有两个杂凑表，分别是dentry_hashtable和inode_hashtable，是list_head指针数组，一旦在内存中建立起一个目录节点的dentry结构或索引节点的inode结构，就根据其节点名的杂凑值挂入杂凑表中的某个队列。需要寻找时就根据杂凑值从杂凑表入手［5］，为了解决相同hash值带来的冲突，dentry结构的hash值计算时将该目录项的父目录dentry的地址加进去，而inode结构的hash值计算时将该inode对应的super_block的地址加进去以解决相同hash带来的冲突［6］。

2.2 blizzard算法

基于Linux内核对在vfs下的目录项和索引节点运用了hash表的算法来快速定位目录项和索引节点，于是本文提出一种通过运用blizzard算法构造一张磁盘上的目录项结构ext2_dir_entry_2对应的hash表来快速定位给定文件的目录项在磁盘上的位置。

2.2.1 blizzard算法的优势

所谓hash，即将字符串压缩成一个整数，即所谓的hash值，通过hash值在hash数组里找到对应项，然而由于hash表大小的限制与输入量的未知避免不了不同字符串经过hash函数后得到相同的hash值，为了避免冲突有很多经典的方法，Linux内核就是运用了拉链法［7］。

Blizzard算法没有使用拉链法而是在哈希表中用3个哈希值来校验字符串。两个不同字符串hash成3个相同hash值几乎不可能。

2.2.2 blizzard算法基本原理

（1）将给定字符串分别与3个不同的数值作为形参传入hash函数中得到3个hash值，Hash确定该字符串在hash数组的位置，hashA和hashB作为校验值。

（2）查看hash表中的这个位置。

（3）检验该位置的exsists是否为0，如果为0表示该字符串不存在。

（4）若不为空，则校验hashA和hashB是否匹配，如果匹配，则找到该字符串。

（5）若不匹配则顺延。

3 Blizzard算法在Linux中的具体实现方法

3.1 hash表的数据结构描述

在Linux文件系统中，同一目录下不允许同名文件，但不同目录下可以有同名文件。因此，blizzard算法不完全适用于Linux，因此，如何使得hash表的结构对于相同的文件名有其特殊之处成为一个重点。根据Linux2.6.11的源代码，本文提出如下hash数据结构：

该结构与暴雪公司MPQHASHTABLE的数据结构不同之处在于多了两个字段，parent_offset和offset。尽管Linux文件系统允许同名文件，这导致同名字符串计算出3个相同的hash值引起冲突，但是相同文件名的父目录在其上层父目录的目录项中的偏移量依然相同的概率尤为低。

3.2 offset从何而来

Linux文件系统在新建文件的时候，需要往磁盘上父目录下的数据块里找到一个可用的目录项结构。然后将该文件的信息，如文件名，该文件对应的ino号等填写进该目录项结构，Linux新建文件时调用ext2_add_link（）函数在父目录的数据块里查询一个可用目录项给给定文件。其流程如图2所示。

由于struct blizzard_hash的offset字段是4字节大小，然而最高位并不会用到，因此，将其最高位设置为bool exsists字段，这样节省了空间。该bit为0表示hash表的该位置为空。

3.3 hash表的大小以及存储

文件在新建的同时计算得到该文件的hash值将其填充进hash表对应位置。Struct blizzard_hash结构占16 bytes，该表的大小以及存储位置是一个关键，表太小冲突的概率就变大。

在Linux内核中为dentry_hashtable提供的空间默认每M RAM提供256个索引值，2 G内存则共2*1 024*256=524 288个索引值，因此，本文将blizzard_hash表初始化为524 288大小，所以该表总共占用524 288*16 bytes=8 M，其实该hash表的大小应根据需求设置，若磁盘文件数目很多，则该hash表可设置的大些。

图2 新建文件查找空闲目录项流程图

本文将hash表存储在第一个剩余空间大于hash表大小的块组里。且在系统初始化的时候将该hash表占据的数据块所在的块位图对应位标志为1。以防后面写数据的时候往hash表的位置写进了数据。其位置如图3所示：

图3 hash表在磁盘的存储位置

3.4改进后的Linux文件系统定位文件流程分析

①在新建文件的时候将该文件的struct blizzard_hash结构存储到相应位置，若hash为下标的位置已经存有数则顺延。

②打开文件的时候，计算文件名的3个哈希值，hash定位数组下标。

③如果该位置offset字段的最高位为0.表示文件不存在。若不为0.则校验两个hash值与parent_offset是否匹配。

④若匹配则提取该父目录的page-＞index=offset＞＞page_shift的页到页高速缓存中，到该页的offset%page_size偏移量处获取该文件的目录项。

⑤若不匹配，则顺延，查看hash+1的下标位置，重复③，④步骤直到查询到该文件对应的目录项为止。

4 结论

通过在新建文件时将其目录项结构在父目录中的偏移量offset映射成hash表存储在磁盘上，在下一次打开文件的时候直接计算文件的哈希值，将该哈希值作为哈希表索引值找到该文件的blizzard_hash结构，通过该结构的offset直接提取该文件父目录的offset偏移处的page就可获得该文件在磁盘上的目录项结构，提高了文件定位的效率。

［1］毛德操，胡希明.Linux内核源代码情景分析［M］.杭州：浙江大学出版社，2001.

［2］顾喜梅，顾宝根.基于Linux的文件系统机制的研究及实现方法［J］.计算机工程与技术，2002，23（7）：20-22，25.

［3］陈莉君，张琼声，张宏伟.深入理解Linux文件系统内核［M］.北京：中国电力出版社，2007.

［4］张荣亮，余敏，余文斌.Linux文件系统内核机制分析与研究［J］.计算机与现代化，2007（12）：14-17，21.

［5］梁琛，陈莉君.Linux内核链表及其在虚拟文件系统中的应用［J］.西安邮电学院学报，2011，16（2）：29-33.

［6］夏煜，郎荣玲，戴冠中.Linux文件系统数据缓冲区的分析研究［J］.计算机工程与应用，2001，37（17）：126-128.

［7］LEVEL C，ALLIANCE S N.Linux kernel hash table behavior：Analysis and Improvements［C］//Proceedings of the 4th AnnualLinuxShowcase&Conference，Atlanta，Georgia，USA，2000.

Research on Improvement of File Retrieval Method Based on Linux

PANG Hai-fei，CHANG Qing，ZHANG Gang
（School of Information Engineering，Taiyuan University of Technology，Taiyuan 030000，China）

With the continuous expansion of the disk capacity，the number of files stored in a single disk is increasing.The performance of the file system and the efficiency of the file system will drop sharply.It’s because that the traditional file system using linear search way to retrieve files.In this paper，the Linux virtual file system is deeply analyzed，the mechanism of VFS opening and creating the new file is described，and the defects and problems are pointed out.On the basis of Linux file system，referring to the blizzard algorithm of Blizzard game company which is used to solve the hash conflict，proposing a method to improve the efficiency of file search by establishing a hash table on disk.

Linux，VFS，blizzard algorithm，hash table

TP316

A

1002-0640（2017）02-0145-04

2016-01-08

2016-02-19

庞海飞（1992-），女，广西玉林人，硕士研究生。研究方向：基于Linux的磁盘阵列设计。