基于ｈａｓｈ技術(shù)的ｅｘｔ３目錄索引機制的改進(jìn)

摘要:針對當(dāng)前廣泛應(yīng)用的ext3文件系統(tǒng)對超過一定長度的目錄進(jìn)行索引操作時，其性能明顯下降的現(xiàn)象，首先對其原因進(jìn)行了分析，提出一種基于hash技術(shù)的ext3目錄索引問題的解決方案，并在此基礎(chǔ)上給出了實現(xiàn)代碼#65377;通過幾種測試平臺所獲得的實驗數(shù)據(jù)證明了該hash技術(shù)對解決ext3性能瓶頸的有效性#65377;

關(guān)鍵詞:哈希技術(shù); ext3文件系統(tǒng); 目錄索引; B樹

中圖分類號:TP316.89文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2007)10-0229-03

0引言

Ext3作為RedHat公司默認(rèn)的日志文件系統(tǒng)，其穩(wěn)定性#65380;健壯行#65380;可恢復(fù)性都是被大家所公認(rèn)的#65377;但同時ext3也有其不可回避的性能瓶頸，即對大小超過一定限度的目錄(2.5 KB)進(jìn)行目錄索引操作時，性能會明顯下降#65377;其原因在于ext3在進(jìn)行目錄索引操作時，采用的是線性方式查找目錄項;在為新的目錄項分配磁盤空間時，也是采用線性方式，其時間復(fù)雜度為O(n)#65377;目錄項不多時性能影響不大，但是當(dāng)目錄的大小超過一定限度(2.5 KB)時，其性能下降明顯#65377;Ext3以后的文件系統(tǒng)(如JFS[1]#65380;ReiserFS[2]#65380;XFS[3])在其設(shè)計之初就把目錄索引問題考慮進(jìn)去#65377;JFS#65380;XFS采用的是B+樹的方式解決這個問題;ReiserFS采用的是更為快速的B*樹的方式組織目錄，時間復(fù)雜度均為O(log N)，其目錄結(jié)構(gòu)以B+或B*樹的形式在磁盤上進(jìn)行保存#65377;

針對ext3文件系統(tǒng)這個性能瓶頸，國內(nèi)外的一些文獻(xiàn)給出了解決方案#65377;Phillip的Htree[4]提出了一種樹與hash技術(shù)相結(jié)合的解決方式，但是這種方式為了保持向后兼容，把在磁盤上用于保存樹結(jié)構(gòu)的塊與原有ext3存放目錄項的塊混合;同時把保存樹結(jié)構(gòu)的塊的狀態(tài)標(biāo)志為已使用，從而達(dá)到隱藏這個塊的目的#65377;但是在系統(tǒng)崩潰或宕機時，采用上述處理方式，會使得系統(tǒng)恢復(fù)工具(如fsck等)在進(jìn)行系統(tǒng)恢復(fù)時變得非常困難#65377;國防科學(xué)技術(shù)大學(xué)的喬龍川等人[5]提出了一種擴展hash技術(shù)解決方法，但是他們并沒有給出具體實現(xiàn)以及評測，只是簡單地在理論上比較了B樹與hash技術(shù)的性能差異#65377;

在總結(jié)前人工作的基礎(chǔ)上，本文提出一種新的目錄索引機制(HashedDir)，避免了訪問大目錄時的線性查找#65377;HashedDir在第一次訪問超過一定限度大小的目錄時建立目錄項的hash表，下次再訪問相同的目錄時，通過HashedDir就可以大大減小CPU開銷以及查找時間#65377;相對于線性查找的時間復(fù)雜度O(n)，采用hash的方式，其時間復(fù)雜可以降為O(1)#65377;與此同時，對比JFS#65380;XFS#65380;ReiserFS等文件系統(tǒng)(其目錄結(jié)構(gòu)都是以B樹的形式記錄在磁盤上)，采用這樣的方式對原有ext3文件系統(tǒng)的目錄結(jié)構(gòu)沒有影響#65377;因為建立hash表的操作都是在內(nèi)存中進(jìn)行的，這樣設(shè)計也是向后兼容的#65377;

HashedDir的主要開銷在于第一次訪問目錄時，建立hash表所占用的時間及CPU開銷，以及維持這個hash 表所需要的內(nèi)存#65377;但如果這個目錄在隨后的過程中頻繁地被訪問，那么先前為了建立這個hash 表所付出的代價會隨著訪問次數(shù)的增加而逐漸被抵消#65377;

1HashedDir實現(xiàn)

HashedDir在第一次訪問大小超過一定限度的目錄時，會建立對應(yīng)于這個目錄的hash表;以后隨著目錄項的改變，對應(yīng)的hash 表會作相應(yīng)的調(diào)整#65377;使用這個hash 表進(jìn)行目錄索引時，性能會明顯提高#65377;同時每個HashedDir維護(hù)了一份針對本目錄內(nèi)每個目錄塊剩余空閑磁盤空間信息的數(shù)據(jù)結(jié)構(gòu)#65377;所以當(dāng)新增一個目錄項時，可以很快地為這個目錄項找到空閑磁盤空間#65377;

1.1Ext3傳統(tǒng)的目錄緩存name cache

如圖1所示，在傳統(tǒng)的ext3目錄緩存結(jié)構(gòu)中，最上層是name cache，它在vfs_cache.c中實現(xiàn)，提供一個全局意義上的的映射關(guān)系#65377;

當(dāng)成功訪問某一條路徑，這條路徑及其對應(yīng)的vnode結(jié)構(gòu)就會被加入到全局name cache中#65377;無論是成功還是失敗的訪問，在name cache中都會有記錄#65377;若下一次請求在name cache中存在，就會避免文件系統(tǒng)級的查找，從而提高性能#65377;

當(dāng)一個name cache緩存項的vnode被刪除后，這個緩存項在name cache中也會相應(yīng)地被刪除#65377;在name cache中，失敗訪問的緩存項在總緩存項中所占的比例不會超過1/16#65377;

Name cache對于那些經(jīng)常被訪問文件的查找，以及不存在的文件查找都很有用，但是對于那些隨機訪問目錄中某一目錄項的情況，命中率就會很低#65377;

1.2HashedDir與name cache的異同

HashedDir與name cache類似，都采用了hash表的方式把兩個關(guān)聯(lián)的部分聯(lián)系起來，但同時兩者也有所不同#65377;總的來說，HashedDir與name cache存在以下幾個方面的差異:

a)HashedDir把目錄項的名字作為hash表的key;name cache是將文件的整個路徑作為hash表的key#65377;

b)HashedDir是針對每個目錄建立一個hash表;name cache是針對全局建立的一個hash表#65377;

c)HashedDir在目錄vnode被訪問時建立其hash表，然后查詢這個目錄;而name cache是當(dāng)目標(biāo)目錄項查詢完成之后，才把加入到name cache的hash表中，以便下一次訪問相同文件/目錄時可以很快地得到其vnode信息#65377;

d)每個HashedDir將整個目錄的目錄項都放入hash表中，因此它能迅速地針對某個目錄項是否存在于hash表中給出準(zhǔn)確的回答;而name cache只能對它已經(jīng)緩存的文件/目錄進(jìn)行回答#65377;

e)對于HashedDir，它只映射，通過目錄項在目錄中的偏移量便能快速地定位到這個目錄項，進(jìn)而進(jìn)行下一步操作;而name cache則不同，相對于HashedDir來說，它更加重量級，作的是的映射#65377;

1.3對于hash表的考慮

由于HashedDir中只保存目錄項在目錄中對應(yīng)的偏移量，HashedDir的hash表是采用openstorage的方式(即一開始就固定了hash表所占用的內(nèi)存，不動態(tài)地增加)，不像name cache中采用的是動態(tài)增加的linkedlist方式#65377;對于hash函數(shù)，HashedDir選用的是FreeBSD操作系統(tǒng)fnv_hash.h頭文件中的fnv_32_buf函數(shù)#65377;通過這個函數(shù)，可以將目錄項名字的字符串均勻地hash到各個bucket中，從而最大限度地減小hash沖突#65377;在HashedDir中解決hash沖突是用線性探測的方式#65377;

1.4關(guān)于查詢的優(yōu)化

查詢某一文件時會首先在name cache中進(jìn)行#65377;如果在name cache中存在，立即返回結(jié)果，不再訪問HashedDir#65377;Name cache中設(shè)計了順序查找的優(yōu)化，即當(dāng)加入一個目錄項到name cache中時，同時把這個目錄項所在目錄中接下來的那個目錄項也加入到name cache中#65377;如果下一次是順序訪問，則可以很快地在name cache中找到目標(biāo)目錄項#65377;在HashedDir中也存在順序查找優(yōu)化，每次在HashedDir中查詢某一個目錄項，都會把這個目錄項緊接著的下一個目錄項在目錄中的偏移量保存下來#65377;如果下一次查詢目錄項的偏移量與保存的偏移量相等，順序優(yōu)化的選項就會被開啟#65377;當(dāng)優(yōu)化選項被開啟后再進(jìn)行查詢時，會首先檢查與上一次查詢保存的偏移量相等的目錄項是否存在#65377;如果找到的話，就會首先考慮使用這個偏移量來查找目標(biāo)目錄項#65377;

1.5在HashedDir中尋找空閑的目錄空間

圖2中的dir_blkfree[block]給出了block中空閑的磁盤空間大小;dir_firstfree[space]給出了第一個空閑磁盤空間大小剛好等于space的塊號#65377;如果dir_firstfree[space]的值為-1，代表剛好剩余space大小空閑空間的塊不存在，應(yīng)繼續(xù)順著這個slot往下找，直到找到為止#65377;Dir_firstfree的最后一塊給出了創(chuàng)建任意大小的目錄項的塊號#65377;

如圖2所示，HashedDir維護(hù)了兩個隊列來保存空閑的目錄塊空間信息#65377;第一個隊列dir_blkfree給出了每個目錄塊的空閑磁盤空間的大小#65377;由于在ext2/3中塊的大小可選范圍為1 024#65380;2 048#65380;4 096 Byte，它們都是4的倍數(shù)，在dir_blkfree中表示的塊的空閑空間也是以4的倍數(shù)來表示的#65377;例如在dir_blkfree位置為2(從0開始計數(shù))的地方的數(shù)字為3，表示目錄塊中第二個塊空閑的字節(jié)數(shù)為3×4=12 Byte#65377;第二個隊列dir_firstfree的作用在于:當(dāng)HashedDir需要分配一個指定大小的磁盤空間時，快速給出第一個足夠大空閑空間的塊號#65377;由于在ext2/3中文件的名字最長不超過255 Byte(除去最后一個結(jié)束符的空間)，加上其他的數(shù)據(jù)，一個目錄項數(shù)據(jù)結(jié)構(gòu)的長度不超過264 Byte#65377;根據(jù)這個限制，可以使得dir_firstfree的長度在一定的范圍之內(nèi)#65377;因為查找目錄內(nèi)空閑磁盤空間算法設(shè)計如下:當(dāng)需要一個240 Byte大小的目錄項數(shù)據(jù)結(jié)構(gòu)空間時，先對240除以4，找到dir_firstfree的第60個slot;然后檢查它的空閑空間是否符合要求，如果不符合，繼續(xù)尋找第61，…，直到找到第一個符合要求的目錄塊#65377;由于最長的目錄項的大小為264 Byte，dir_firstfree的長度不會超過66個slot，最后一個slot指向的目錄塊空閑空間保證了任意大小的目錄項空間都可以被分配#65377;

在上述結(jié)構(gòu)的基礎(chǔ)上，通過修改dir_blkfree這個隊列中某個slot的計數(shù)，來反映這個塊由于目錄項數(shù)據(jù)結(jié)構(gòu)空間被分配以及釋放其空閑磁盤空間的變化情況#65377;Dir_firstfree會根據(jù)dir_blkfree的變化進(jìn)行相應(yīng)的改變，使其指向正確的目錄塊號#65377;如圖2所示，如果在HashedDir中需要分配4 Byte空間，通過4/4=1找到dir_firstfree中第一個slot，發(fā)現(xiàn)它是-1;于是繼續(xù)往下找，在dir_firstfree第二個slot中找到足夠的空閑，在這個slot所指向的空閑空間為2×4=8 Byte，減去4 Byte的空間后，需要調(diào)整dir_firstfree隊列，使得dir_firstfree的第一個slot指向原來dir_firstfree第二個slot所指向的塊，即第五個目錄塊#65377;而原來的第二個slot則在后續(xù)目錄塊中檢查是否有剛好剩余8 Byte空閑空間的塊存在#65377;如果存在，則指向它;如果不存在，第二個slot標(biāo)記為-1#65377;

未加入HashedDir之前，當(dāng)要創(chuàng)建一個新的目錄entry時，先要遍歷這個目錄，看具有相同名字的目錄項是否存在#65377;與此同時，為這個新的目錄項分配空閑磁盤空間動作也在進(jìn)行#65377;分配的優(yōu)先級為:第一個足夠的連續(xù)空間的目錄塊;第一個足夠空間的目錄塊，但是需要壓縮;一個新的目錄塊#65377;

通過以上的分配方式，可以讓為新目錄項分配的磁盤空間盡量靠近目錄的開始處，減少磁頭運動的距離，縮短查詢時間#65377;加入HashedDir后，就不用通過遍歷的方式查詢是否存在相同名字的目錄項，同時為新的目錄項分配空間時，也可以馬上通過dir_firstfree來獲知第一個有足夠空間的目錄塊#65377;相對于未加入HashedDir之前的目錄操作，性能會有很大的提升#65377;

1.6內(nèi)存的使用，HashedDir的釋放

每個HashedDir是通過占用內(nèi)存來維護(hù)其本身的HashedDir結(jié)構(gòu)#65380;hash表以及空閑空間的信息#65377;對于每個HashedDir結(jié)構(gòu)，其構(gòu)成是3個pointer#65380;9個int#65380;1個off_t，還有dir_firstfree的66個int，總共大約要320 Byte#65377;

當(dāng)開始建立HashedDir時，按照當(dāng)前目錄塊能容納的最大目錄項個數(shù)的150%來建立HashedDir的hash表(最大目錄項個數(shù)是按照假設(shè)每個目錄項名字長度為1的情況下計算得到，即用目錄總?cè)萘砍陨鲜鲎钚∧夸涰椊Y(jié)構(gòu)長度得出的值)#65377;這是考慮到目錄項的個數(shù)會有一定程度上的動態(tài)變化而設(shè)定的比例值#65377;按照上述150%的比例，加上在設(shè)計中是以一個4 Byte的目錄偏移量對應(yīng)一個最小目錄項結(jié)構(gòu)(ext3中是16 Byte，13向上取4的倍數(shù))，可以算出比例值為4×(3/2)∶16=3∶8#65377;所以要建立一個HashedDir要花費的內(nèi)存大小，大約是當(dāng)前目錄總大小的3/8，再加上其他附屬數(shù)據(jù)結(jié)構(gòu)的266 Byte以及之前的320 Byte#65377;例如，一個要進(jìn)行HashedDir處理的目錄的大小為10 KB，處理過后HashedDir占用的總的內(nèi)存大約就是10 KB×(3/8)+266+320 Byte#65377;

HashedDir在以下情況被釋放:

a)當(dāng)目錄本身的vnode被釋放時，需要釋放這個目錄對應(yīng)的HashedDir#65377;

b)當(dāng)新增目錄項使得hash表總的bucket使用率超過75%時#65377;由于hash表解決沖突采用的是線性探測的方式，如果hash表過滿的話，會使得hash表的性能下降#65377;

c)當(dāng)目錄項增加，使得dir_blkfree不夠用時#65377;

d)當(dāng)目錄項數(shù)目減少為原來的1/8時#65377;為了節(jié)省內(nèi)存空間，就需要釋放該HashedDir，然后根據(jù)情況決定是否重建#65377;

e)當(dāng)HashedDir被標(biāo)上回收的標(biāo)記后#65377;一個HashedDir被標(biāo)明為回收是因為這時需要建立另外一個HashedDir，但所有HashedDir總的內(nèi)存占用已經(jīng)超過一定的上限(在這里內(nèi)存使用上限的初始值為2 MB)，這時就需要選擇一些HashedDir來進(jìn)行釋放#65377;為了避免抖動，在選擇被釋放的HashedDir時，通過LRU(leastrecentlyused)和LFU(leastfrequentlyused)兩者相結(jié)合的混合算法來選擇合適的HashedDir進(jìn)行釋放#65377;如果在1min之內(nèi)抖動的次數(shù)超過80次，將內(nèi)存使用的上限擴展為4 MB，再次是6#65380;8，直到10 MB的最終上限#65377;

2HashedDir性能評測

實現(xiàn)HashedDir比較簡單，大約需要1 000行的C語言代碼和100行的頭文件#65377;在ext3文件系統(tǒng)中，只需要在目錄查詢和修改的地方作少量的改動就可以將HashedDir代碼加入#65377;

實驗環(huán)境使用DELL PowerEdge1800 服務(wù)器，其配置如下:單CPU，Intel Xeon(TM) CPU 3.00 GHz，cache size為2 048 KB;1 GB內(nèi)存DDR 2 400 SDRAM;五個Sata磁盤，每個磁盤250 GB，轉(zhuǎn)速7 200 轉(zhuǎn)/s，采用Raid0，Stripe為64 KB#65377;使用的測試平臺有兩個，一個是自己編寫的測試程序，一個是國際上廣泛采用的文件系統(tǒng)評測工具Bonnie++[6]#65377;

在自己編寫的測試程序中，測試的案例為在一個目錄中試圖創(chuàng)建1~35 000個以它們自己數(shù)字編號為名字的文件，而這些文件在之前已經(jīng)被創(chuàng)建好;然后將1~35 000的文件重命名;最后隨機地將1~35 000文件全部刪除#65377;

Bonnie++是Bonnie測試平臺的改進(jìn)#65377;最初Bonnie 主要測試文件的讀#65380;寫#65380;定位等方面，改進(jìn)后的Bonnie++增加了文件的創(chuàng)建#65380;刪除#65380;Stat的測試功能#65377;它主要用來測試順序以及隨機訪問的情況，在這里使用的是Bonnie++ 1.03a版本#65377;

在本測試中主要測試以下幾個方面:大目錄中文件的隨機創(chuàng)建;大目錄中文件的隨機刪除;大目錄中文件的隨機Stat#65377;測試結(jié)果如圖3~5所示#65377;

通過測試可以發(fā)現(xiàn)，沒有加入HashedDir之前的ext3文件系統(tǒng)，在目錄大小超過2.5 KB之后，隨著目錄規(guī)模的增大，其創(chuàng)建#65380;刪除#65380;Stat文件的時間也線性地增加;而加入HashedDir之后的ext3文件系統(tǒng)，其創(chuàng)建#65380;刪除#65380;Stat文件的時間都保持在一個常數(shù)值#65377;創(chuàng)建一個目錄項的時間保持在40 ms左右;刪除一個目錄項的時間保持在45 ms左右;Stat一個目錄項的時間保持在10 ms左右#65377;其時間不隨目錄的增大而線性增加#65377;

3結(jié)束語

本文針對ext3文件系統(tǒng)中的目錄索引問題，提出了基于hash技術(shù)的解決方案，并對其實現(xiàn)細(xì)節(jié)作了較為詳細(xì)的闡述#65377;最后通過測試發(fā)現(xiàn)HashedDir相對于以前線性查找，在性能上有極大的提高，證明了本文所提出的方案對解決ext3的目錄索引問題具有現(xiàn)實意義#65377;

參考文獻(xiàn):

[1]BEST S. JFS overview[EB/OL].(2000).http://www106.ibm.com/developerworks/library/jfs.html.

[2]REISER H. ReiserFS[EB/OL]. http://www.namesys.com/.

[3]SGI Company.XFS[EB/OL].http://oss.sgi.com/projects/xfs/.

[4]PHILLIPS D. A directory index for ext2[C]//Proc of the 5th Anual Linux Showcase and Conference. 2001:77-87.

[5]喬龍川，羅軍. 采用擴展哈希技術(shù)實現(xiàn)ext2文件系統(tǒng)目錄索引[J]. 科技情報開發(fā)與經(jīng)濟， 2003，13(12):196198.

[6]COKER R. The Bonnie++ Benchmark[EB/OL]. http://www.coker.com.au/bonnie++/.

[7]RALITAS B， WATSON A. Accelerated performance for large directories， Technical Report 3006[R].[S.l.]:Network Appliance Inc， 1996.

第10期柳永坡，等:

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”