ResearchandImplementationonofParallelMetadataSearchforLarge-scaleFileSystemAuthor:LiuTutor:RuanWiththeadventoftheeraofinformationexplosion,thescaleofdatatobeprocessedisgrowinglargerandlarger.Asoneofthemostimportanttechnicalwaytodealwithpresentlargedatastoragerequirements,themetadatamanagementoflarge-scalefilesystems ethedomesticandinternationalresearchhotspot.Amongthem,theperformanceofmetadatasearchwillhaveahugeimpactonmetadataaccessperformanceandevenoverallsystemperformanceoflarge-scalefilesystem.Therefore,Thereisaveryimportantsignificancetoimprovetheoverallperformanceoflarge-scalefilesystembyimprovingtheperformanceofmetadatasearch.Themainproblemofmetadatasearchinlarge-scalefilesystemfacedisthatthereisnometadatasearchalgorithmwithlessspaceoverheadcanachievebothhighsearchaccuracyandhighsearchrate.Tosolvethisproblem,thispaperdesignsandimplementsalightweightsearchmethodbasedonBloomfilter(MBFS)inordertoimprovetheperformanceofmetadatasearchinmultiplemetadataserverenvironment.Themainresearchworkinclude:UnderstandPVFSarchitecture,yzeitsmetadatastream,pickoutthecoderelatedtothedirectorytreeoperations,completetheoverallsystemdesign.Designandimplementmulti-dimensionalBloomfilter,createacorrespondingstructureforeachdirectoryentryineverymetadataserver.Thencompletethesearchmethodwhichcanlopquicklybyusingthestructureinsinglemetadataserverenvironment.Sendrequeststoeverymetadataserversatthesametime,completetheparallelmetadatasearchinmultiplemetadataserverenvironment.designandimplementsearchinterfacebychangingtheinterfacecalledPVFS2-ls.theperformanceofnewsearchmethodsthroughexperiments.Wefocusonperformancesearchaccuracy,searchrateandspaceAfterthesystemiscompleted,wedidperformancetestforMBFS.Comparedwiththesearchalgorithmbasedonsampling,MBFShashighersearchaccuracyandhighersearchrate.Meanwhile,ittakeslessspaceoverheadthanthesearchalgorithmbasedonindex.：PVFS2,Bloomfilter,Parallelization,Metadata 摘 緒 研究背 Bloomfilter結(jié) 3.4.1Bloomfilter結(jié)構(gòu)設(shè) 基于Bloomfilter結(jié)構(gòu)搜索方法設(shè) 本章小 4.2.1Bloomfilter結(jié)構(gòu)的實(shí) 在服務(wù)器端創(chuàng)建一一對(duì)應(yīng)的Bloomfilter結(jié) 工作總 工作展 致 參考文 進(jìn)入了ZB級(jí)，而由此導(dǎo)致文件系統(tǒng)的結(jié)構(gòu)逐步擴(kuò)大，嚴(yán)重影響了元數(shù)據(jù)的局臨的主要之一。 PVFS2是一種典型的并行文件系統(tǒng)，應(yīng)用于多機(jī)環(huán)境的網(wǎng)絡(luò)文件系統(tǒng)中，其主要功能依賴元數(shù)據(jù)服務(wù)器，I/O服務(wù)器，I/O庫(kù)libPVFS以及l(fā)inux內(nèi)核來(lái)實(shí)現(xiàn)[12]，文件具體分布在I/O服務(wù)器中，但其屬性信息于元數(shù)據(jù)服務(wù)器中，其間對(duì)文件的操作依賴于I/O服務(wù)器中與元數(shù)據(jù)服務(wù)器間的TCP/IP協(xié)議來(lái)實(shí)現(xiàn)。在傳統(tǒng)的PVFS2并行文件系統(tǒng)，采用romio來(lái)進(jìn)行數(shù)據(jù)篩選[3]，雖然基于元數(shù)據(jù)索引結(jié)構(gòu)的文件搜索有效避免了傳統(tǒng)分層大規(guī)模文件系統(tǒng)的搜索算法主要以下兩個(gè)：一是搜索速率與搜索準(zhǔn)確率之間的，二是搜索準(zhǔn)確率與額外開(kāi)銷之間的。因此，試圖尋找一種輕量級(jí)的搜索基于元數(shù)據(jù)索引結(jié)構(gòu)的文件搜索算法在文件系統(tǒng)中引入了索引結(jié)構(gòu)，通過(guò)抓取(crawl)等在文件系統(tǒng)或系統(tǒng)之上建立索引并文件的元數(shù)據(jù)，這樣在進(jìn)行文構(gòu)的文件搜索算法包括CMUSmartScan[12]，UCSCSpyglass[12]以及的屬性生成虛，再進(jìn)行檢索。基于語(yǔ)義相關(guān)性的文件搜索算法考慮了文件的屬性與數(shù)據(jù)，更好地切合了元數(shù)據(jù)管理方式，典型的研究包括SmartStore[12]、Rapport[12]、PageRank[12]以及Connections[12]等。然而，大部分基于語(yǔ)義相關(guān)性的文件搜索算法把注的各分支進(jìn)行采樣，根據(jù)采樣結(jié)果預(yù)估文件下的內(nèi)容，快速裁剪不相符的分支，從Glance搜索算法，然而其依然不可避免地在準(zhǔn)確性方面會(huì)有較大缺陷，此基于通知的文件搜索算1.1所示。這些算法無(wú)法索引獨(dú)立于文件系統(tǒng)，數(shù)據(jù)一致性需大量開(kāi)基于通知的搜索方隨著數(shù)據(jù)規(guī)模的增大，大規(guī)模文件系統(tǒng)的結(jié)構(gòu)也隨之?dāng)U展，元數(shù)據(jù)搜索的性能為解決上述兩個(gè)問(wèn)題，需設(shè)計(jì)并實(shí)現(xiàn)基于Bloomfilter的文件搜索方法，消除了解PVFS架構(gòu)，分析其元數(shù)據(jù)流，摘出 設(shè)計(jì)并實(shí)現(xiàn)可伸縮Bloomfilter結(jié)構(gòu)，在元數(shù)據(jù)服務(wù)器端為每個(gè) 本文的主要內(nèi)容是研究并實(shí)現(xiàn)一種基于Bloomfilter結(jié)構(gòu)的適用于多元數(shù)據(jù)服務(wù)器filter的相關(guān)知識(shí)BloomfilterBloomfilter結(jié)構(gòu)的Bloomfilter析了實(shí)驗(yàn)結(jié)果，對(duì)比本文實(shí)現(xiàn)的算法MBFS與其他搜索算法之間的優(yōu)劣。Bloomfilter的元數(shù)據(jù)搜索方法，消除結(jié)構(gòu)中的Bloomfilter以及實(shí)現(xiàn)該算法基于的集群并行文件系統(tǒng)PVFS2，下面對(duì)其進(jìn)行詳細(xì)介紹。BloomfilterBloomfilter是由HowardBloom[12]在1970年一種具有很好的空間和時(shí)間Bloomfiltermn個(gè)元素的集合，其所占的空間0，2.1nk個(gè)相互獨(dú)立的哈希函數(shù)映射到位數(shù)組哈希函數(shù)計(jì)算出一個(gè)哈希值，由第i個(gè)哈希函數(shù)計(jì)算得出的哈希值記作(e)，則將位數(shù)組的第(e)12.21的某一位之前已經(jīng)被其他哈希這樣，集合中的各個(gè)元素的信息均被存入了這個(gè)m位的位數(shù)組中。2.2e4個(gè)哈希函數(shù)加入BloomfilterBloomfilterak個(gè)獨(dú)立哈希函數(shù)分別計(jì)算哈希值即可，若所有(a)1a在該1不能判斷出該位是否會(huì)被其他元素映射到，因此加入Bloomfilter結(jié)構(gòu)的元素不能輕易刪除，否則有可能會(huì)影響到其他的元素。判定在集合內(nèi)的元素存在一定幾率并不在集合內(nèi)，稱為一個(gè)falsepositive。錯(cuò)誤率與集合內(nèi)元素?cái)?shù)n，位數(shù)組長(zhǎng)度m以及獨(dú)立哈希函數(shù)個(gè)數(shù)k有關(guān)，其概率p=（ 當(dāng)k=（m/n）時(shí)，錯(cuò)誤率最小，達(dá)到。盡管Bloomfilter結(jié)構(gòu)誤判問(wèn)題，但是通過(guò)該結(jié)構(gòu)判斷不在集合中的元素必Bloomfilter結(jié)構(gòu)對(duì)不符合搜索條件的文件進(jìn)行截枝，高搜索準(zhǔn)確率的搜索算法，十分符合本文所研究目標(biāo)。 理的句柄范圍不，因此每一個(gè)對(duì)象恰好由一個(gè)服務(wù)器進(jìn)行管理[12]。為了分配負(fù)載，會(huì)把文件分成多個(gè)64KB大小的文件塊，在不同的數(shù)據(jù)服務(wù)器上，除了第一個(gè)文件由一個(gè)物理元數(shù)據(jù)文件對(duì)象和多個(gè)物理數(shù)據(jù)文件對(duì)象（即文件塊）組成[12]2.3所 2.3在集群環(huán)境中，PVFS將節(jié)點(diǎn)分為三種，分別是計(jì)算節(jié)點(diǎn)，I/O節(jié)點(diǎn)以及管理節(jié)點(diǎn)，libPVFS函數(shù)庫(kù)以發(fā)送請(qǐng)求并接受返回；I\O節(jié)點(diǎn)具體的文件數(shù)據(jù)，即為數(shù)據(jù)服務(wù)器，各I\O具體分布如圖2.4所示。PVFS2文件系統(tǒng)，其每個(gè)元數(shù)據(jù)管理固定范圍的句柄。每次創(chuàng)建一個(gè)文件，則分配一個(gè)句柄號(hào)，若創(chuàng)建一個(gè)，則分配兩個(gè)句柄號(hào)，分配的

2.4集群環(huán)境下PVFS2.1Bloomfilter結(jié)構(gòu)的各種特性，重點(diǎn)分析了其空間開(kāi)銷，檢測(cè)時(shí)間以及誤判2.2節(jié)介紹了實(shí)現(xiàn)搜索算法尤其是在PVFS2并行文件系統(tǒng)中，中只本下的文件名，其他信息從相關(guān)的對(duì)象中獲取，因此元數(shù)據(jù)搜索只能遍歷到樹(shù)的葉節(jié)點(diǎn)，即需要整個(gè)計(jì)并實(shí)現(xiàn)一種基于Bloomfilter的文件搜索方法，在樹(shù)上快速截枝，在不犧牲PVFS2架構(gòu)，分析其元數(shù)據(jù)流，摘出樹(shù)操作相關(guān)代碼，完成系統(tǒng)的總體結(jié)構(gòu)設(shè)計(jì)；設(shè)計(jì)可伸縮Bloomfilter結(jié)構(gòu)，用以表示一個(gè)對(duì)象的元數(shù)據(jù)屬性，并利用此結(jié)構(gòu)將底層文件元數(shù)據(jù)信息浮于上層，在PVFS2服務(wù)PVFS2的客戶端設(shè)計(jì)搜索接PVFS2上設(shè)計(jì)搜索算法時(shí)，應(yīng)盡量避免更改元數(shù)據(jù)流，以并未獲取它的SleepycatPublicLicense，對(duì)其詳細(xì)的方式不了解，因此在添Bloomfilter 搜索算法。根據(jù)搜索算法的需求，我們想到了Bloomfilter結(jié)構(gòu)。其次，Bloomfilter結(jié)構(gòu)雖然有一定的誤判率，但是通過(guò)該結(jié)構(gòu)判斷不在集合中的元為了提高元數(shù)據(jù)搜索的速率，不遍歷整個(gè)文件系統(tǒng)的空間，須利用Bloomfilter結(jié)構(gòu)將原本于下層的元數(shù)據(jù)信息浮于上層，這樣雖然會(huì)增加空間開(kāi)銷，但是相對(duì)于其提高的搜索速度，這種額外開(kāi)銷是值得的。祖先節(jié)點(diǎn)已經(jīng)了其子孫節(jié)不符合條件，根據(jù)Bloomfilter結(jié)構(gòu)的特性，可以判定其子孫節(jié)點(diǎn)均不符合搜索條件，同時(shí)，由于祖先節(jié)點(diǎn)的Bloomfilter結(jié)構(gòu)會(huì)子孫節(jié)點(diǎn)的元數(shù)據(jù)信息，因此消除了搜索的關(guān)鍵路徑問(wèn)題，使得各個(gè)子樹(shù)可以同時(shí)搜索，從而更加有效地利用多元數(shù)pvfsBloomfilter結(jié)構(gòu)的元數(shù)據(jù)搜索算法，對(duì)總體架構(gòu)文件系統(tǒng)頂層，減少對(duì)數(shù)據(jù)庫(kù)中具體內(nèi)容的修改。SearchSearchMainSearch3.1SearchAPPMPI-IO接口與底層文件系統(tǒng)交互。所謂文件進(jìn)行操作。在系統(tǒng)接口以及線程分配模塊的下層，搜索請(qǐng)求的信息實(shí)際是由BMIBMI層將搜索請(qǐng)求通過(guò)網(wǎng)絡(luò)（TCP協(xié)議）發(fā)送到元數(shù)據(jù)服務(wù)器對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)，獨(dú)立于PVFS2并行文件系統(tǒng)，單獨(dú)在磁盤或內(nèi)存中，這包括Bloomfilter結(jié)構(gòu)的設(shè)計(jì)以及基于此結(jié)構(gòu)完成的元數(shù)據(jù)搜索算法的具體設(shè)計(jì)。Bloomfilter結(jié)構(gòu)設(shè)計(jì)元數(shù)據(jù)并行搜索方法需求，可用來(lái)表示元數(shù)據(jù)屬性。然而，基本的Bloomfilter需要提出一種的Bloomfilter結(jié)構(gòu)[8]。所謂的Bloomfilter結(jié)構(gòu)，是由p個(gè)獨(dú)立的BloomFilter結(jié)構(gòu)組成，分別用來(lái)表示p維屬性。假設(shè)是S的第i維屬性，使用[][]()( )Sij個(gè)哈希值，也就是說(shuō)，iBloomfilter結(jié)構(gòu)，將位數(shù)組的第[][]()位置1。因此，Bloomfilter采用個(gè)比特位去n個(gè)具有p維的實(shí)體。Bloomfilter結(jié)構(gòu)如圖3.2所示。圖3.2Bloomfilter結(jié)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)Bloomfilter數(shù)據(jù)結(jié)構(gòu)?；綛loomfilter數(shù)據(jù)結(jié)構(gòu)字段與Bloomfilter數(shù)據(jù)結(jié)構(gòu)字段分別如表3.1與表3.2所示。aunsignedcharhashfunc_thash表3.2Bloomfilter數(shù)據(jù)結(jié)Bloomfilter的數(shù)組n基于Bloomfilter結(jié)構(gòu)搜索方法設(shè)用Bloomfilter結(jié)構(gòu)并搜索文件的元數(shù)據(jù)信息，首先我們要知道需要的元數(shù)據(jù)。PVFS2并行文件系統(tǒng)中的對(duì)象包括文件， 對(duì)象有不同的元數(shù)據(jù)，不過(guò)他們有七種共有的元數(shù)據(jù)屬性，分別是uid，gid，其余六種共有的元數(shù)據(jù)屬性信息加上在數(shù)據(jù)服務(wù)器端通過(guò)累加得到的size屬性，用unsignedunsignedunsignedunsignedlongunsignedlongunsignedlongunsigned要利用Bloomfilter結(jié)構(gòu)進(jìn)行搜索，首先要在PVFS2并行文件系統(tǒng)中創(chuàng)Bloomfilter結(jié)構(gòu)。由于判 用Bloomfilter結(jié)構(gòu)反而需要多一次，效率不如直接文件的元數(shù)據(jù)，所以各葉節(jié)點(diǎn)上的元數(shù)據(jù)文件不需要?jiǎng)?chuàng)建Bloomfilter結(jié)構(gòu)，只需要對(duì)各個(gè)項(xiàng)創(chuàng)建一一對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)。創(chuàng)建過(guò)程中，先判斷創(chuàng)建對(duì)象的類型，若為對(duì)象類型為，則創(chuàng)建對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)，無(wú)論創(chuàng)建類型是什么，均遍歷其所有祖先f(wàn)ilter結(jié)構(gòu)中（按位取或）PVFS2并行文件系統(tǒng)創(chuàng)建對(duì)象同時(shí)完成，具體流程如圖3.3所示。結(jié)構(gòu)直接創(chuàng)建在元數(shù)據(jù)文件中或者在元數(shù)據(jù)文件中添加一個(gè)指向Bloomfilter結(jié)構(gòu)的指針。因此，為了能夠通過(guò)Bloomfilter結(jié)構(gòu)找到與其一一對(duì)應(yīng)的元數(shù)據(jù)文件，PVFS2并行文件指針。該映射表動(dòng)態(tài)創(chuàng)建以節(jié)約空間，并且按fs_id以及handle（連接）的大小是？否是否應(yīng)Bloomfilter圖3.3創(chuàng)建Bloomfilter流程BloomfilterBloomfilter結(jié)構(gòu)的拓?fù)浣Y(jié)構(gòu)隨文件樹(shù)拓?fù)浣Y(jié)構(gòu)的變化即時(shí)更新，所以我們隨時(shí)可以利用Bloomfilter進(jìn)行搜索。根據(jù)第3.1節(jié)所述，pvfs并行文件系統(tǒng)中的項(xiàng)只本下對(duì)象的文件名，其他信息從相關(guān)對(duì)象中獲取，因此信息是分層的，上層不可能知道其下層點(diǎn)，即遍歷整個(gè)空間，顯然，這樣的元數(shù)據(jù)搜索的時(shí)間性能非常差。要提高上述元數(shù)據(jù)搜索的性能，我們需要找到一種不需要遍歷整個(gè)空間，又不影響搜索準(zhǔn)確率的方法，因此我們想到了利用Bloomfilter結(jié)構(gòu)。根據(jù)上文所述的創(chuàng)建 不需要再它的葉節(jié)點(diǎn)，直接截枝即可，截枝示意圖如圖3.4所示。這樣，我們可以不用遍歷整個(gè)空間，又沒(méi)有損失搜索準(zhǔn)確性。同時(shí)，將底層元數(shù)據(jù)信息賦給頂層的Bloomfilter結(jié)構(gòu)，只是將兩者的位數(shù)組按位取或，并未擴(kuò)大整個(gè)數(shù)據(jù)結(jié)構(gòu)的空間，3.4MBFSBloomfilter結(jié)構(gòu)是否在集合里，若不在集合內(nèi)，則截枝，不再其下的對(duì)象；若在集合內(nèi)，則其目條件，如果對(duì)象是，則繼續(xù)檢測(cè)其一一對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)，重復(fù)上述否是 是否否否下是是否下是 否是 利用Bloomfilter結(jié)構(gòu)，底層的元數(shù)據(jù)信息浮于頂層，這樣做不但有利于快速截枝，提高搜索效率，而且還消除了文件系統(tǒng)按層次結(jié)構(gòu)組織的限制，將樹(shù)結(jié)構(gòu)扁平化，消除了關(guān)鍵路徑問(wèn)題。因?yàn)锽loomfilter結(jié)構(gòu)均含有下層的元數(shù)據(jù)信送到所有的元數(shù)據(jù)服務(wù)器，每臺(tái)元數(shù)據(jù)服務(wù)器以自己的子樹(shù)的根節(jié)點(diǎn)為起點(diǎn)，并行任務(wù)，實(shí)現(xiàn)了元數(shù)據(jù)并行化搜索，進(jìn)一步提高搜索效率。其基本結(jié)構(gòu)如圖3.6所示 3.6棵子樹(shù)在一個(gè)元數(shù)據(jù)服務(wù)器上，然后分別利用Bloomfilter結(jié)構(gòu)進(jìn)行快速截枝實(shí)現(xiàn)解析Tab文件， 解析Tab文件， 3.7接口只給出了四種參數(shù)，具體參數(shù)見(jiàn)表3.4所示。unsigned（197011日的秒數(shù)unsignedlong范圍測(cè)試（最小值到最大值unsignedint-unsignedBloomfilter3.13.2節(jié)我們給出PVFS23.33.5節(jié)，我們分別介紹了單元數(shù)據(jù)服務(wù)器環(huán)境中基于Bloomfilter結(jié)構(gòu)的快速截枝算法的設(shè)計(jì)，多元數(shù)據(jù)服務(wù)器環(huán)境中并行化搜索方法的設(shè)計(jì)以及客戶端搜索應(yīng)用的設(shè)計(jì)。其中著重分析了Bloomfilter結(jié)構(gòu)的設(shè)計(jì)以及在PVFS2并行文件系統(tǒng)中如何創(chuàng)建并利用Bloomfilter。Bloomfilter結(jié)構(gòu)的并行化搜索的具體實(shí)現(xiàn)。本章首先給出了并行化搜索方法的開(kāi)發(fā)環(huán)境，并說(shuō)明了在pvfs23.33.5節(jié)所做的設(shè)計(jì)，分別介紹單元數(shù)據(jù)服務(wù)器環(huán)境中Bloomfilter結(jié)構(gòu)的快速截枝算法的實(shí)現(xiàn)，多元數(shù)據(jù)服務(wù)器環(huán)境中并行化搜索方法Bloomfilter結(jié)構(gòu)的并行化搜索方法在pvfs2中的原型系統(tǒng)的實(shí)現(xiàn)。Linuxpvfs-2.8.2源代CC語(yǔ)言作為本原型系統(tǒng)的實(shí)現(xiàn)語(yǔ)言。此外，C語(yǔ)言是一種通用的計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言，且編譯產(chǎn)生的目標(biāo)代碼簡(jiǎn)潔，執(zhí)行效率快，適合做底層系統(tǒng)開(kāi)發(fā)。C語(yǔ)言具有豐富的數(shù)據(jù)類型和函數(shù)方法供系統(tǒng)開(kāi)發(fā)pvfs-2.8.2pvfs-2.8.2源代發(fā)，主要包括Vim編輯器的使用、Make工具使用，GDB調(diào)試工具的使用，s的編Bloomfilter結(jié)構(gòu)的實(shí)現(xiàn)要在單元數(shù)據(jù)服務(wù)器環(huán)境中實(shí)現(xiàn)MBFS搜索算法，首先要實(shí)現(xiàn)Bloomfilter結(jié)Bloomfilter結(jié)構(gòu)與元數(shù)據(jù)文件一一對(duì)應(yīng)，還要?jiǎng)?chuàng)建一張動(dòng)態(tài)生成的映射表indextable，這一部分的主要函數(shù)如表4.1所示。表4.1Bloomfilter實(shí)現(xiàn)相關(guān)函為Bloomfilter再創(chuàng)建一維初始的基本Bloom返回指向Bloomfilter的指刪除一個(gè)Bloomunsignedlonglongchar* ，元數(shù)據(jù) 在服務(wù)器端創(chuàng)建一一對(duì)應(yīng)的Bloomfilter結(jié)3.3.1節(jié)設(shè)計(jì)的流程可知，創(chuàng)建過(guò)程中，先判斷創(chuàng)建對(duì)象的類型，若為對(duì)象類型為，則創(chuàng)建對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)，無(wú)論創(chuàng)建類型是什么，均遍歷其所有祖先節(jié)Bloomfiltersrc/server下的三mkdir.c，create.clookup.c。這三個(gè)函數(shù)的功能分別是創(chuàng)建，創(chuàng)建邏輯文件以及按路徑查詢。顯然在創(chuàng)建的時(shí)候我們同時(shí)要?jiǎng)?chuàng)建一一對(duì)應(yīng)的BloomfilterBloomfilter。而在創(chuàng)將邏輯文件的過(guò)程中，則先創(chuàng)建一個(gè)臨時(shí)Bloomfilter結(jié)構(gòu)，這個(gè)元數(shù)據(jù)文件的信息。無(wú)論創(chuàng)建還是邏輯文件，都需要在一個(gè)固定路徑下創(chuàng)建，lookup提供了解析固定路徑，并從根一直到需創(chuàng)建對(duì)象的的功能，在其解析并固定路徑上所有Bloomfilterflag1。創(chuàng)建完成后，將所創(chuàng)建項(xiàng)對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)或所創(chuàng)建邏輯文件對(duì)應(yīng)的臨時(shí)Bloomfilter結(jié)構(gòu)與Bloomfilter4.1-圖4.3所示。create.c函數(shù)中，首先創(chuàng)建一個(gè)空的元數(shù)據(jù)文件，然后創(chuàng)建數(shù)據(jù)文件，創(chuàng)建數(shù)據(jù)bloom_add、mullti_addmulti_add_itemBloomfilter結(jié)構(gòu)，緊臨時(shí)Bloomfilter結(jié)構(gòu)刪除。4.1所示數(shù)據(jù)流圖中將其放在了setobj_attribs函數(shù)外面。create_local mkdir.c函數(shù)中，隨著創(chuàng)建multi_add函數(shù)創(chuàng)建一個(gè)對(duì)應(yīng)的Bloomfilterindextable_create函數(shù)將該Bloomfilter結(jié)構(gòu)的指針以及fs_idBloomfilter結(jié)構(gòu)中，緊接著根據(jù)之前所建的映射表，用一forBloomfilterBloomfilterflag1，則Bloomfilter結(jié)構(gòu)按位取或，更新為新的Bloomfilter，再將flag字段置為0。創(chuàng)建失敗會(huì)返回錯(cuò)誤處理err_msg，此時(shí)要調(diào)用multi_destroyBloomfiltercreate.c 置屬性 完對(duì)象元數(shù)據(jù)，即確定其葉節(jié)點(diǎn)作為下一個(gè)查詢對(duì)象之后，將對(duì)應(yīng)的Bloomfilter的flag字段置為1，標(biāo)記為創(chuàng)建對(duì)象的祖先節(jié)點(diǎn)。 create.c，mkdir.clookup.c三個(gè)文件的修改，我們已經(jīng)為整個(gè)文件系統(tǒng)中所有創(chuàng)建了Bloomfilter結(jié)構(gòu)，并且將他們所有子孫節(jié)點(diǎn)的七種元數(shù)據(jù)屬性BloomfilterBloomfilter結(jié)構(gòu)的快速截枝算法。點(diǎn)。從根節(jié)點(diǎn)開(kāi)始，每當(dāng)一個(gè)對(duì)象時(shí)，都將該對(duì)象的handle值和fs_id值存入棧中multi_check函數(shù)檢查其對(duì)應(yīng)Bloomfilter結(jié)構(gòu)是否符合搜索條件，符合條件則遞歸調(diào)用搜索函數(shù)DFS來(lái)繼續(xù)該下的下一個(gè)未子對(duì)象。若該對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)不符合搜索條件，意味著節(jié)點(diǎn)的下一個(gè)未節(jié)點(diǎn)，即下一個(gè)未的兄弟節(jié)點(diǎn)，這樣不再不符合搜索條件的的子孫節(jié)點(diǎn)，相當(dāng)于實(shí)現(xiàn)了截枝工作。若對(duì)象為元數(shù)據(jù)文件，則直接對(duì)比其均需出棧以下一個(gè)未的兄弟節(jié)點(diǎn)。boolboolvisited=realloc(visited,sizeof(bool)*indextable //boolStack voidDFS_BloomSearch(DirectoryTreeT,char//for(v=0;v<indextable->n;++vvisited[v]=//}voidDFS(DirectoryTreeT,intv,charPush(s,v);//入棧，暫 父節(jié)visited[v]=Bloomfilterfor(w=FirstNeighbor(T,v);w>=0;w=NextNeighbor(T,v,wvif(!visited[w]&&w->type==directory//若w為v尚 的DFS(T,welseif(w->type==metafile&&strcmp(w-////w% pop(s,v}elseif(w->type==pop(s,v pop(s//for(w=NextNeighbor(T,v,w);w>=0;w=NextNeighbor(T,v,w 到v的最后一個(gè)子節(jié)if(!visited[w]&&w->type==directoryDFS(T,welseif(w->type==metafile&&strcmp(w-//w% 在pvfs并行文件系統(tǒng)中具體實(shí)現(xiàn)的過(guò)程中，利用Bloomfilter結(jié)構(gòu)對(duì) 性進(jìn)行判斷在readdir.c函數(shù)中實(shí)現(xiàn)，當(dāng)其某一 時(shí)，我們同時(shí)獲取了其fs_id以 程則在lookup.c函數(shù)中實(shí)現(xiàn)，當(dāng)其按某條路徑查詢完成后不返回查詢結(jié)果，而是繼續(xù)按棵子樹(shù)在一個(gè)元數(shù)據(jù)服務(wù)器上，然后分別利用Bloomfilter結(jié)構(gòu)進(jìn)行快速截枝實(shí)現(xiàn)PVFS2并行文件系統(tǒng)劃分句柄的函數(shù)是在mon/misc/Pint-cached-config.c文PINT_cached_config_get_next_meta函數(shù)，其完全隨機(jī)的分配下一個(gè)元數(shù)據(jù)所在實(shí)現(xiàn)做好準(zhǔn)備。其具體流4.4所示。是否4.4如圖4.4所示，一個(gè)下的子樹(shù)存在了同一個(gè)元數(shù)據(jù)服務(wù)器下，并且記錄這些子樹(shù)采用MBFS算法進(jìn)行搜索，實(shí)現(xiàn)多元數(shù)據(jù)并行化搜索。1for循環(huán)，向所有的元數(shù)據(jù)服MBFS搜索，搜索結(jié)束就將結(jié)作量，我們沒(méi)有在/src/apps/admin中實(shí)現(xiàn)一個(gè)新的搜索應(yīng)用，而是將一個(gè)不常用的應(yīng)用pvfs2-ls改為搜索應(yīng)用的內(nèi)容（pvfs2-ls參數(shù)），實(shí)現(xiàn)搜索功能。搜索應(yīng)用的數(shù)據(jù)流圖如圖4.5所示。PVFS_sys_initializePVFSPVFS_sys_fs_addi小于掛載條目數(shù)的時(shí)候調(diào)用此函數(shù)，定義在Fs_add.c中。PVFS_sys_search_request函數(shù)：功能是向服務(wù)器端發(fā)送請(qǐng)求，并傳遞元數(shù)據(jù)屬性信息，定義在Pvfs2-util.c中。i<tab-YNi<YN4.55.1機(jī)器作為元數(shù)據(jù)服務(wù)器，其余七臺(tái)機(jī)器作為數(shù)據(jù)服務(wù)器。各臺(tái)機(jī)器均在數(shù)據(jù)服務(wù)器ip地址分別為7879，各數(shù)據(jù)服務(wù)器地址為CPU：AMD24硬盤：80GBSATA操作系統(tǒng)：ubuntuGDB：GDB cdcdpvfs-autoautoifaceeth1inetstaticnetmaskgatewaysudosudoifdownsudoifupmetadata_ EnterEnterhostnames[Defaultislocalhost]:data_server1,EnterEnterhostnames[Defaultislocalhost]:metadata_server1,metadata_將生成后的配置文件pvfs2-fs.conf拷貝到各個(gè)節(jié)點(diǎn)的/etc 各個(gè)節(jié)點(diǎn)/etc/hostname文件內(nèi)容為本節(jié)點(diǎn)名稱（如data_server1，重啟使更新生效。 編寫pvs_create.sh并執(zhí)行，在PVFS文件系統(tǒng)中創(chuàng)建一定規(guī)模的與文件，例如：在根下創(chuàng)建200個(gè)子，再在每個(gè)子下闖將4000的文件，用以測(cè)試搜索功能。pvs_create.sh文件內(nèi)容如下： 的文件，搜索結(jié)果如圖5.2所示：口PVFS2-ls改為搜索接口，從而快速方便的進(jìn)試。Bloomfilter的元數(shù)據(jù)搜索方法，是否在數(shù)據(jù)規(guī)模Bloomfilter的元數(shù)據(jù)搜索MBFSspyglass[12]以及基于1，故設(shè)定0.98，基于Bloomfilter的元數(shù)據(jù)搜索方法搜索準(zhǔn)確度設(shè)定為1。0DataDHarvardglance，MBFS能夠更快的達(dá)到固定搜索準(zhǔn)確度，搜10 10 110 time:10 Time110 glance，MBFS的搜索準(zhǔn)確率可以在很短的時(shí)間內(nèi)達(dá)0 spyglass[12]BloomAppNet[12]600030GB，共設(shè)計(jì)兩種搜索0 32321012約只占spyglass算法的40%，在空間開(kāi)銷性能方面具有明顯提升。spyglass，基于采樣的搜索算法glance以及基于Bloomfilter結(jié)構(gòu)的元數(shù)據(jù)搜索方法進(jìn)試，我們可以與基于采樣的搜索算法glance相比，基于Bloomfilter結(jié)構(gòu)的元數(shù)據(jù)搜索方法MBFS在搜索速率性能方面具有明顯的優(yōu)勢(shì)，達(dá)到相同的搜索準(zhǔn)確度所需時(shí)間可減少為搜索準(zhǔn)確率方面的問(wèn)題。然而，MBFSspyglass搜索方法慢，需多花費(fèi)約15%的時(shí)間才能完成搜索。均有較高要求，則可選用本文設(shè)計(jì)實(shí)現(xiàn)的MBFS搜索算法。BloomfilterMBFS進(jìn)行的的功能測(cè)試與性能中得到準(zhǔn)確的搜索結(jié)果。5.3MBFS與另外兩種典型的元數(shù)據(jù)搜索算法，對(duì)MBFS的搜索性能進(jìn)行了分析，基本達(dá)到了第三章所述的性能需求。設(shè)計(jì)并實(shí)現(xiàn)了一種基于Bloomfilter結(jié)構(gòu)的并行化元數(shù)據(jù)搜索算法，在不犧牲了解PVFS架構(gòu)，分析其元數(shù)據(jù)流，摘出 設(shè)計(jì)并實(shí)現(xiàn)可伸縮Bloomfilter結(jié)構(gòu)，在元數(shù)據(jù)服務(wù)器端為每個(gè) glanceMBFS達(dá)到相同的搜索準(zhǔn)確度所需時(shí)間可減少為原第一，由于Bloomfilter結(jié)構(gòu)不可輕易刪除的特性，每當(dāng)文件做一次修改或者，就會(huì)有新的修改時(shí)間和時(shí)間元數(shù)據(jù)屬性信息添加進(jìn)入相應(yīng)Bloomfilter結(jié)構(gòu)，然而舊的修改時(shí)間和時(shí)間元數(shù)據(jù)屬性信息并未刪除，所以隨著時(shí)間的推移，修改次數(shù)的增多，由于之前所有版本的元數(shù)據(jù)屬性信息均在對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)當(dāng)中，所以，Bloomfilter的誤判率會(huì)越來(lái)越高，截枝越來(lái)越少，搜索速率會(huì)越來(lái)越慢。這是本算，還需另建一張映射表查詢?cè)獢?shù)據(jù)文件對(duì)應(yīng)的Bloomfilter結(jié)構(gòu)，這樣必然導(dǎo)致搜第五，本文實(shí)現(xiàn)的元數(shù)據(jù)并行搜索前提條件是將一棵樹(shù)（根節(jié)點(diǎn)為第二層MBFS搜索算法進(jìn)行優(yōu)化，老師傳授給我的科研方法還是其人生感悟，都將在我的生涯繼續(xù)指引我前行。們?cè)谛薷牡倪^(guò)程中少做了很多無(wú)用功。肖老師雖然嚴(yán)肅，但確實(shí)是心中的頂當(dāng)編碼有不會(huì)的地方，每當(dāng)程序有調(diào)不出來(lái)的BUG，都是鐘師兄來(lái)幫忙，即使是他自1006大班的所有同學(xué)。在與一屆學(xué)生，謝謝教給我知識(shí)和人生道理?？飘厴I(yè)，今后是時(shí)候讓我挑起家庭的擔(dān)子，讓過(guò)回輕松愉快的生活了。肖利民.自主課題申請(qǐng)書-面向大數(shù)據(jù)的大規(guī)模文件系統(tǒng)元數(shù)據(jù)高效管理方法[D].航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家,2014.1.9.劉兆春,李光輝,王慶國(guó),等.并行文件系統(tǒng)PVFS[J].,2005,29(4):108-劉興宇.基于倒排索引的全文檢索技術(shù)研究[J]..:華技大學(xué), 凱.PVFS元數(shù)據(jù)服務(wù)器的并行化設(shè)計(jì)與實(shí)現(xiàn)[J].ComputerEngineering,2006,郭.搜索引擎中并行文件系統(tǒng)的研究[D].哈爾濱工業(yè)大學(xué),肖明忠,代亞非,李曉明.BloomFilter[JJ.GantzandD.Reinsel,“Thedigitaluniversein2020:Bigdata,biggerdigitalshadows,andbiggestgrowthinthefareast,”tech.rep.,2012RossRB,ThakurR.PVFS:AparallelfilesystemforLinuxclusters[C]//inProceedingsofthe4thAnnualLinuxShowcaseandConference.2000:391-430.GremillionLL.DesigningaBloomfilterfordifferentialfileaccess[J].CommunicationsoftheACM,1982,25(9):600-604.KuhnM,KunkelJM,LudwigT.DynamicfilesystemsemanticstoenablemetadataoptimizationsinPVFS[J].ConcurrencyandComputation:PracticeandExperience,2009,21(14):1775-1788.KuhnM,KunkelJ,LudwigT.Directory-basedmetadataoptimizationsforsmallfilesinLikunLiu,LianghongXu,YongweiWu,GuangwenYang,GregoryR.Ganger.SmartScan:MetadataCrawlforStorageManagementMetadataQueryinginLargeFileSystems[R].CarnegieMellonUniversity,CMU-PDL-10-112.2010.LeungA.,ShaoM.,BissonT.,PasupathyS.,MillerE.L.Spyglass:Fast,scalablemetadatasearchforlarge-scalestoragesystems[A].Proceedingsofthe7thUSENIXConferenceonFileandStorage[C].2009:153–166.LeiX.,HongJ.,XueL.,etal.Propeller:AScala