基于Linux文件檢索方法的改進(jìn)研究

龐海飛，常青，張剛

（太原理工大學(xué)信息工程學(xué)院，太原030024）

基于Linux文件檢索方法的改進(jìn)研究

龐海飛，常青，張剛

（太原理工大學(xué)信息工程學(xué)院，太原030024）

隨著磁盤容量的急劇增大，文件系統(tǒng)的性能以及文件系統(tǒng)的效率會急劇下降，這是因?yàn)槲募斜磉^于龐大，傳統(tǒng)的文件系統(tǒng)在檢索文件時采用的線性搜索方式帶來的檢索效率低下導(dǎo)致。對Linux虛擬文件系統(tǒng)進(jìn)行深入剖析，闡述了VFS打開以及新建文件的機(jī)制，指出其存在的缺陷及問題。在Linux文件系統(tǒng)的基礎(chǔ)上，參考暴雪游戲公司解決hash沖突的blizzard算法，提出一種通過在磁盤上建立文件目錄項(xiàng)的哈希表來提高文件查找效率的方法。

Linux，虛擬文件系統(tǒng)，blizzard算法，哈希表

0 引言

Linux系統(tǒng)因其開放性的源代碼以及其穩(wěn)定性廣受廠商的熱愛，成為目前熱門的操作系統(tǒng)之一。Linux下默認(rèn)的單級子目錄數(shù)量是31 998，隨著磁盤容量的不斷擴(kuò)大，單級目錄下可存儲的文件數(shù)目會越來越多，檢索起來相當(dāng)耗時。導(dǎo)致文件系統(tǒng)性能大幅度下降。因此，對Linux的文件檢索速度的提高具有重要意義。

1 Linux文件系統(tǒng)檢索文件的機(jī)制

1.1 概述

Linux最初采用minix的文件系統(tǒng)，其大小僅限于64 M，文件名長度限于14個字符。經(jīng)過一段時間的改進(jìn)與發(fā)展，現(xiàn)在的Linux文件系統(tǒng)支持文件名長達(dá)255字符［1］。在ext2文件系統(tǒng)中，文件名存儲在目錄項(xiàng)結(jié)構(gòu)ext2_dir_entry_2中，同一目錄下的文件及目錄的目錄項(xiàng)按線性方式存儲。對于常規(guī)文件或目錄，其數(shù)據(jù)存儲在磁盤介質(zhì)上面，為了減少對磁盤的操作，內(nèi)核允許將一部分?jǐn)?shù)據(jù)存儲在RAM中，當(dāng)要對文件進(jìn)行讀寫操作的時候，則先在內(nèi)存中做相應(yīng)的操作，最后再將所做的修改同步更新到磁盤上［2］。

1.2 Linux文件系統(tǒng)打開文件機(jī)制分析

Ext2文件系統(tǒng)采用索引節(jié)點(diǎn)位圖來管理磁盤上的數(shù)據(jù)塊，使用索引節(jié)點(diǎn)來管理磁盤上的元數(shù)據(jù)，每個文件或目錄都唯一的對應(yīng)一個索引節(jié)點(diǎn)，當(dāng)用戶要訪問文件的時候，需要獲取得到該文件的索引節(jié)點(diǎn)信息，通過索引節(jié)點(diǎn)獲得該文件的數(shù)據(jù)塊存儲位置。然而索引節(jié)點(diǎn)由該文件對應(yīng)的目錄項(xiàng)結(jié)構(gòu)存儲，用戶首先需要獲取得到文件對應(yīng)的目錄項(xiàng)結(jié)構(gòu)［3］。

以下是虛擬文件系統(tǒng)打開文件的流程，在此僅僅是列出關(guān)鍵的幾條流程［4］。

（1）獲取父目錄的inode結(jié)構(gòu)。

（2）解析給定路徑分量，計(jì)算分量的hash值。

（3）根據(jù)父目錄的dentry和上面（2）中得到的hash值在dentry_hashtable中查詢該路徑分量的dentry結(jié)構(gòu)。

（4）如若沒找到，則在dentry_cache中分配一個可用dentry，初始化它且將其鏈入父目錄的dentry_subdirs隊(duì)列中。

（5）將父目錄在磁盤上的數(shù)據(jù)分頁提取到頁高速緩存中，查找對應(yīng)的路徑分量的ext2_dir_entry_2結(jié)構(gòu)，獲取得到該分量的ino號。

（6）通過super_block地址和ino在inode_hashtable中獲取該分量的inode結(jié)構(gòu)。

1.3 Linux文件系統(tǒng)檢索文件的缺點(diǎn)

本文分析的關(guān)鍵在于1.1中第5點(diǎn)提到的在父目錄的目錄項(xiàng)下面查找給定文件名的目錄項(xiàng)，由ext2_find_entry實(shí)現(xiàn)。其具體流程如圖1所示：

圖1 Linux在頁高速中查找文件目錄項(xiàng)流程圖

Linux2.6.11的源代碼中采用循環(huán)結(jié)構(gòu)，通過字符串比較來查找給定文件名在父目錄下的對應(yīng)目錄項(xiàng)。顯然，在單個目錄下子文件及子目錄數(shù)量較多的時候顯得力不從心，相當(dāng)耗時。

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

2.1 Linux下的哈希算法

Linux內(nèi)核中有兩個雜湊表，分別是dentry_hashtable和inode_hashtable，是list_head指針數(shù)組，一旦在內(nèi)存中建立起一個目錄節(jié)點(diǎn)的dentry結(jié)構(gòu)或索引節(jié)點(diǎn)的inode結(jié)構(gòu)，就根據(jù)其節(jié)點(diǎn)名的雜湊值掛入雜湊表中的某個隊(duì)列。需要尋找時就根據(jù)雜湊值從雜湊表入手［5］，為了解決相同hash值帶來的沖突，dentry結(jié)構(gòu)的hash值計(jì)算時將該目錄項(xiàng)的父目錄dentry的地址加進(jìn)去，而inode結(jié)構(gòu)的hash值計(jì)算時將該inode對應(yīng)的super_block的地址加進(jìn)去以解決相同hash帶來的沖突［6］。

2.2 blizzard算法

基于Linux內(nèi)核對在vfs下的目錄項(xiàng)和索引節(jié)點(diǎn)運(yùn)用了hash表的算法來快速定位目錄項(xiàng)和索引節(jié)點(diǎn)，于是本文提出一種通過運(yùn)用blizzard算法構(gòu)造一張磁盤上的目錄項(xiàng)結(jié)構(gòu)ext2_dir_entry_2對應(yīng)的hash表來快速定位給定文件的目錄項(xiàng)在磁盤上的位置。

2.2.1 blizzard算法的優(yōu)勢

所謂hash，即將字符串壓縮成一個整數(shù)，即所謂的hash值，通過hash值在hash數(shù)組里找到對應(yīng)項(xiàng)，然而由于hash表大小的限制與輸入量的未知避免不了不同字符串經(jīng)過hash函數(shù)后得到相同的hash值，為了避免沖突有很多經(jīng)典的方法，Linux內(nèi)核就是運(yùn)用了拉鏈法［7］。

Blizzard算法沒有使用拉鏈法而是在哈希表中用3個哈希值來校驗(yàn)字符串。兩個不同字符串hash成3個相同hash值幾乎不可能。

2.2.2 blizzard算法基本原理

（1）將給定字符串分別與3個不同的數(shù)值作為形參傳入hash函數(shù)中得到3個hash值，Hash確定該字符串在hash數(shù)組的位置，hashA和hashB作為校驗(yàn)值。

（2）查看hash表中的這個位置。

（3）檢驗(yàn)該位置的exsists是否為0，如果為0表示該字符串不存在。

（4）若不為空，則校驗(yàn)hashA和hashB是否匹配，如果匹配，則找到該字符串。

（5）若不匹配則順延。

3 Blizzard算法在Linux中的具體實(shí)現(xiàn)方法

3.1 hash表的數(shù)據(jù)結(jié)構(gòu)描述

在Linux文件系統(tǒng)中，同一目錄下不允許同名文件，但不同目錄下可以有同名文件。因此，blizzard算法不完全適用于Linux，因此，如何使得hash表的結(jié)構(gòu)對于相同的文件名有其特殊之處成為一個重點(diǎn)。根據(jù)Linux2.6.11的源代碼，本文提出如下hash數(shù)據(jù)結(jié)構(gòu)：

該結(jié)構(gòu)與暴雪公司MPQHASHTABLE的數(shù)據(jù)結(jié)構(gòu)不同之處在于多了兩個字段，parent_offset和offset。盡管Linux文件系統(tǒng)允許同名文件，這導(dǎo)致同名字符串計(jì)算出3個相同的hash值引起沖突，但是相同文件名的父目錄在其上層父目錄的目錄項(xiàng)中的偏移量依然相同的概率尤為低。

3.2 offset從何而來

Linux文件系統(tǒng)在新建文件的時候，需要往磁盤上父目錄下的數(shù)據(jù)塊里找到一個可用的目錄項(xiàng)結(jié)構(gòu)。然后將該文件的信息，如文件名，該文件對應(yīng)的ino號等填寫進(jìn)該目錄項(xiàng)結(jié)構(gòu)，Linux新建文件時調(diào)用ext2_add_link（）函數(shù)在父目錄的數(shù)據(jù)塊里查詢一個可用目錄項(xiàng)給給定文件。其流程如圖2所示。

由于struct blizzard_hash的offset字段是4字節(jié)大小，然而最高位并不會用到，因此，將其最高位設(shè)置為bool exsists字段，這樣節(jié)省了空間。該bit為0表示hash表的該位置為空。

3.3 hash表的大小以及存儲

文件在新建的同時計(jì)算得到該文件的hash值將其填充進(jìn)hash表對應(yīng)位置。Struct blizzard_hash結(jié)構(gòu)占16 bytes，該表的大小以及存儲位置是一個關(guān)鍵，表太小沖突的概率就變大。

在Linux內(nèi)核中為dentry_hashtable提供的空間默認(rèn)每M RAM提供256個索引值，2 G內(nèi)存則共2*1 024*256=524 288個索引值，因此，本文將blizzard_hash表初始化為524 288大小，所以該表總共占用524 288*16 bytes=8 M，其實(shí)該hash表的大小應(yīng)根據(jù)需求設(shè)置，若磁盤文件數(shù)目很多，則該hash表可設(shè)置的大些。

圖2 新建文件查找空閑目錄項(xiàng)流程圖

本文將hash表存儲在第一個剩余空間大于hash表大小的塊組里。且在系統(tǒng)初始化的時候?qū)⒃揾ash表占據(jù)的數(shù)據(jù)塊所在的塊位圖對應(yīng)位標(biāo)志為1。以防后面寫數(shù)據(jù)的時候往hash表的位置寫進(jìn)了數(shù)據(jù)。其位置如圖3所示：

圖3 hash表在磁盤的存儲位置

3.4改進(jìn)后的Linux文件系統(tǒng)定位文件流程分析

①在新建文件的時候?qū)⒃撐募膕truct blizzard_hash結(jié)構(gòu)存儲到相應(yīng)位置，若hash為下標(biāo)的位置已經(jīng)存有數(shù)則順延。

②打開文件的時候，計(jì)算文件名的3個哈希值，hash定位數(shù)組下標(biāo)。

③如果該位置offset字段的最高位為0.表示文件不存在。若不為0.則校驗(yàn)兩個hash值與parent_offset是否匹配。

④若匹配則提取該父目錄的page-＞index=offset＞＞page_shift的頁到頁高速緩存中，到該頁的offset%page_size偏移量處獲取該文件的目錄項(xiàng)。

⑤若不匹配，則順延，查看hash+1的下標(biāo)位置，重復(fù)③，④步驟直到查詢到該文件對應(yīng)的目錄項(xiàng)為止。

4 結(jié)論

通過在新建文件時將其目錄項(xiàng)結(jié)構(gòu)在父目錄中的偏移量offset映射成hash表存儲在磁盤上，在下一次打開文件的時候直接計(jì)算文件的哈希值，將該哈希值作為哈希表索引值找到該文件的blizzard_hash結(jié)構(gòu)，通過該結(jié)構(gòu)的offset直接提取該文件父目錄的offset偏移處的page就可獲得該文件在磁盤上的目錄項(xiàng)結(jié)構(gòu)，提高了文件定位的效率。

［1］毛德操，胡希明.Linux內(nèi)核源代碼情景分析［M］.杭州：浙江大學(xué)出版社，2001.

［2］顧喜梅，顧寶根.基于Linux的文件系統(tǒng)機(jī)制的研究及實(shí)現(xiàn)方法［J］.計(jì)算機(jī)工程與技術(shù)，2002，23（7）：20-22，25.

［3］陳莉君，張瓊聲，張宏偉.深入理解Linux文件系統(tǒng)內(nèi)核［M］.北京：中國電力出版社，2007.

［4］張榮亮，余敏，余文斌.Linux文件系統(tǒng)內(nèi)核機(jī)制分析與研究［J］.計(jì)算機(jī)與現(xiàn)代化，2007（12）：14-17，21.

［5］梁琛，陳莉君.Linux內(nèi)核鏈表及其在虛擬文件系統(tǒng)中的應(yīng)用［J］.西安郵電學(xué)院學(xué)報，2011，16（2）：29-33.

［6］夏煜，郎榮玲，戴冠中.Linux文件系統(tǒng)數(shù)據(jù)緩沖區(qū)的分析研究［J］.計(jì)算機(jī)工程與應(yīng)用，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的磁盤陣列設(shè)計(jì)。