畢業(yè)設(shè)計（論文）基于DHT的分布式文件系統(tǒng)研究

1、 學(xué)號： 信陽師范學(xué)院華銳學(xué)院 本科畢業(yè)論文（設(shè)計）專 業(yè) 計算機科學(xué)與技術(shù) 年 級 07級 姓 名 論文（設(shè)計）題目 基于dht的分布式文件系統(tǒng) 指導(dǎo)教師 職稱 講師 2011年4月18日目 錄摘 要.1第一章 緒論.3 1.1分布式系統(tǒng)的定義.3 1.2目標(biāo).5 1.2.1讓用戶連接到資源.5 1.2.2透明性.5 1.2.3開放性.61.2.4可擴展性.6 1.3分布式文件系統(tǒng).61.3.1 sun網(wǎng)絡(luò)文件系統(tǒng).61.3.2不同分布式文件系統(tǒng)對比.9第二章p2p技術(shù).10 2.1.1p2p技術(shù)的發(fā)展.10 2.1.2p2p技術(shù)的分類.11 2.1.3p2p的特性.15 2.2 p2p搜索

2、技術(shù).152.2.1非結(jié)構(gòu)化搜索技術(shù).152.2.2基于dht的搜索技術(shù).162.3chord.182.3.1 finger表.192.3.2 chord算法的查找過程.19第三章基于dht的chord算法的改進(jìn).22 3.1影響搜索算法性能的因素.22 3.2小世界現(xiàn)象對p2p搜索技術(shù)的啟示.23 3.3 nchord搜索算法.263.3.2節(jié)點加入時的策略.283.3.3節(jié)點退出時的策略.293.3.4節(jié)點失效時的策略.293.3.5 nchord算法原理.293.3.6nchord搜索算法的步驟.313.3.7nchord算法特點.32總結(jié).32參考文獻(xiàn).33致謝.33 標(biāo)題 基于dht

3、的分布式文件系統(tǒng)研究學(xué)生姓名： 學(xué)號：信陽師范學(xué)院華銳學(xué)院數(shù)計系 計算機科學(xué)與技術(shù)專業(yè) 指導(dǎo)教師： 職稱：講師摘 要：隨著信息時代的飛速發(fā)展，人們?nèi)找姘l(fā)現(xiàn)單個計算機的能力很是有限，于是自然而然想到把各個地方的計算機聯(lián)合起來處理信息，這就是分布式的提出，隨即涉及到資源共享的問題，這就是我們研究的分布式文件系統(tǒng),隨著p2p（即peer-to-peer）技術(shù)的發(fā)展，很好的解決了分布式存儲與計算方面的問題，它作為一種全新的互聯(lián)網(wǎng)技術(shù)，將傳統(tǒng)的以服務(wù)器為中心的互聯(lián)網(wǎng)應(yīng)用模式提升為以用戶為中心的對等模式。p2p在文件交換，對等計算，協(xié)同工作，搜索服務(wù)等方面都有著重要的應(yīng)用。p2p文件交換系統(tǒng)的發(fā)展也由最初

4、npaster的完全中心化模型，gnutella的完全非中心化模型，發(fā)展到現(xiàn)在的bittorrnet、emul/eedoknye、kzaza等混合模型。隨著近年來dht(disrtibuted hash table)技術(shù)的不斷發(fā)展，dht在p2p文件交換系統(tǒng)中扮演著越來越重要的角色，kdamelai作為覆蓋網(wǎng)絡(luò)被廣泛使用到p2p文件交換系統(tǒng)中。p2p網(wǎng)絡(luò)通常使用dht作為其路由表，比較典型的算法有chord、can、kademlia、tapestry、pastry等，這些算法不僅可靠性高，容錯性強，而且查找的效率非常高，查找算法的復(fù)雜度基本上都是o(logn)，被廣泛地應(yīng)用于各種各樣的分布式系

5、統(tǒng)中。本文將比較分析以上各算法的原理和差異，重點分析、研究和改進(jìn)chord算法，減少路由跳數(shù)和系統(tǒng)開支。關(guān)鍵詞：分布式;分布式文件系統(tǒng);p2p;dht;chordabstract：with the rapid development of information era, people increasingly find a single computer ability is very limited, naturally they tempted to connect with computers in every region to processing information,thus

6、 the distributed proposed,but then comes the resource sharing problem,thats the distributed file system here what we are talking about,as the development of p2p(peer-to-peer) technology,the problem of distributed storage and computing is well solved,the technology of p2p(peer-to-peer), as a new inte

7、rnet technology,promoting the traditional centralized server internet application modle to centralized user peer to peer modle.p2p is important in data-exchange,peer-to-peer computing,coordinated working,search service,etc,in p2p file-sharing systems,it is developing from the beginning centralized m

8、odel napster and decentralized model gnutella to the current mixed modle,such as bittorrent,emule,kazza,etc.as the dht(distrituted hash table) technology develops,it plays a more important role in p2p file-sharing system,kademlia is used widely in p2p file-sharing system as an overlay network. distr

9、ibuted architecture of the network is commonly used to build p2p networks using dht algorithm,forinstance,chord,can,kademlia,tapestry,pastry,etc.these algorithms not only possess high reliability and strong fault tolerance,but also have efficient look up.the complexity of search algorithm is basical

10、ly o(logn),so they are widely used in a variety of distributed storage systems. this paper study and compare the principles and differences of above dht algorithms,research、analysis and promote the chord algorithm more in-depth.thus decreasing the jump numbers during the process of searching and the

11、 cost of system.key words:distributed;distributed file system;p2p;dht;chord 第一章 緒 論 計算機系統(tǒng)正在經(jīng)歷一場革命。1945年是現(xiàn)代計算機時代的開始。從那時起一直到1985年，計算機一直是龐大笨重而昂貴的。即便是小型機每臺也要上萬美元，因而大多數(shù)機構(gòu)都只有很少的幾臺計算機。而且由于沒有把這些計算機連接起來的手段，所以只能單獨的使用它們。 然而，從20世紀(jì)80年代中期開始，技術(shù)領(lǐng)域中兩方面的進(jìn)步開始使這種局面有所改觀。第一項進(jìn)步是高性能處理器的開發(fā)。起初這些機器是8位機，但是很快16位、32位乃至64位的cpu紛至沓

12、來，得到了普及。很多使用這些cpu的機器的計算性能都可以與大型機相媲美，而價格卻比大型機便宜得多。 近半個世紀(jì)以來，在計算機技術(shù)改進(jìn)方面所取得的成果數(shù)量之多對于其他工業(yè)來說是完全無法想象的。一臺計算機的價格從1億美元下降到了1000美元，而運算速度卻從每秒一條指令提升到每秒1千萬條指令，性能價格比提升了大約 1012倍。如果汽車的性能價格比在同一時期以同樣的速率是提升，那么一輛“勞斯來斯”牌轎車現(xiàn)在只值1美元，而且每消耗1加侖（1加侖=4.5461升）汽油可以行駛10億英里（1英里=1.6093公里）。（不幸的是如果果真如此，光是說明如何打開車門這件事，就可能在用戶手冊中占用長達(dá)200頁得篇幅

13、。） 第二項進(jìn)步是高速計算機網(wǎng)絡(luò)的發(fā)明。利用局域網(wǎng)技術(shù)可以將位于同一建筑物里的數(shù)百臺計算機連接起來。使用這種連接方式可以在幾us內(nèi)將少量數(shù)據(jù)從一臺機器傳輸?shù)搅硪慌_機器。如果要傳輸大量的數(shù)據(jù)，傳輸數(shù)率可以達(dá)到101000mb/s。利用廣域網(wǎng)技術(shù)可以連接全球范圍內(nèi)數(shù)百萬臺機器，機器間的數(shù)據(jù)傳輸速率從64kb/s到若干gb/s不等。 現(xiàn)在，由于有以上這些技術(shù)可供使用，因此把若干由大量計算機組成的計算機系統(tǒng)彼此通過高速網(wǎng)絡(luò)相連接，不但是可行的，而且是很容易實現(xiàn)的。這種系統(tǒng)一般稱為計算機網(wǎng)絡(luò)或分布式系統(tǒng)，以突出其與傳統(tǒng)的集中式系統(tǒng)（centralized system，也稱為單處理器系統(tǒng)，single

14、processor system）的差異。傳統(tǒng)的集中式系統(tǒng)一般由單個計算機及其外圍設(shè)備構(gòu)成，也可以包含一些遠(yuǎn)程終端。 1.1分布式系統(tǒng)的定義 已經(jīng)有很多文獻(xiàn)給出了分布式系統(tǒng)的定義，但是不同文獻(xiàn)給出的定義彼此不盡相同，而且沒有一種令人滿意?？紤]到本文的目標(biāo)，我們只給出一個粗略的描述： 分布式系統(tǒng)是若干獨立計算機的集合，這些計算機對于用戶來說就像是單個相關(guān)系統(tǒng)。 這個定義包含了兩方面的內(nèi)容。第一方面是關(guān)于硬件的：機器本身是獨立的，第二個方面是關(guān)于軟件的：對用戶來說他們就像在與單個系統(tǒng)打交道。這兩個方面共同闡明了分布式系統(tǒng)的本質(zhì)，缺一不可。我們先介紹關(guān)于軟硬件的一些背景材料，與繼續(xù)探討分布式系統(tǒng)的定

15、義相比，把注意力集中在分布式系統(tǒng)的重要特性上可能更好一些。其重要特性之一是，各種計算機之間的差別以及計算機之間的通信方式的差別對用戶是隱藏的。同樣，用戶也看不到分布式系統(tǒng)的內(nèi)部組織結(jié)構(gòu)。另一重要特性是，用戶和應(yīng)用程序無論在何時何地都能夠以一種一致的統(tǒng)一的方式與分布式系統(tǒng)進(jìn)行交互。 分布式系統(tǒng)的擴展或者升級應(yīng)該是相對比較容易的。這一特性是由于下述原因：1、 分布式系統(tǒng)由獨立的計算機組成，但同時隱藏了其中單個計算機在系統(tǒng)里所承擔(dān)任務(wù)的細(xì)節(jié)。2、 即使分布式系統(tǒng)中某些部分可能暫時發(fā)生故障，但其整體在通常情況下總是保持可用。3、 用戶和應(yīng)用程序不會察覺到那些部分正在進(jìn)行替換和維修，以及加入了哪些新的部

16、分來為更多的用戶和應(yīng)用程序提供服務(wù)。 為了使種類各異的計算機和網(wǎng)絡(luò)都呈現(xiàn)為單個的系統(tǒng)，分布式系統(tǒng)常常通過一個“中件層”組織起來，該“軟件層”在邏輯上位于由用戶和應(yīng)用程序組成的高層與由操作系統(tǒng)組成的底層之間，如圖1.1所示。這樣的分布式系統(tǒng)有時又稱為中間件（middleware）。圖1.1作為中間件組織的分布式系統(tǒng)（請注意，中間件層延伸到了多臺機器上）現(xiàn)在我們考察一下分布式系統(tǒng)的幾個例子。第一個例子是位于一所大學(xué)或者某個公司部門的工作站網(wǎng)絡(luò)。該系統(tǒng)除了包括每個用戶自己的工作站以外，還應(yīng)該包括機房內(nèi)的一個處理器池。這些處理器并不分配給特定的用戶，而是根據(jù)需要進(jìn)行動態(tài)調(diào)配，這樣的系統(tǒng)可能包含一個單一

17、的文件系統(tǒng)，允許所有的機器通過相同的方法并且使用相同的路徑名來訪問所有的文件。并且，當(dāng)用戶鍵入一個命令的時候，系統(tǒng)將尋找執(zhí)行該命令的最佳位置，也許會在自己的工作站上直接執(zhí)行該命令，也可能會在別人的一個空閑的工作站上執(zhí)行，還有可能有機房中某個尚未分配的處理器執(zhí)行。如果系統(tǒng)整體外觀和行為與傳統(tǒng)的單處理器分時系統(tǒng)（即多用戶系統(tǒng)）相似，那么這個系統(tǒng)就可以看做是分布式系統(tǒng)。第二個例子是某個工作流信息系統(tǒng)，該系統(tǒng)支持對賬單的自動的處理。一般情況下，會有來自多個不同部門的人員在不同的地點使用這樣的系統(tǒng)。例如，銷售部的人員可能遍布在很大的一個區(qū)域，甚至全國?？梢酝ㄟ^電話網(wǎng)絡(luò)（或者蜂窩電話）連接到系統(tǒng)的膝上型計

18、算機下達(dá)訂單。收到的訂單由系統(tǒng)自動傳送到計劃部，接著新的內(nèi)部調(diào)貨訂單就會送達(dá)倉儲部，同時有財務(wù)部處理賬單。該系統(tǒng)自動將訂單傳送到相關(guān)人員手中。用戶根本就看不到系統(tǒng)中訂單處理的物理流程；對于用戶來說，這些訂單像是由一個集中式數(shù)據(jù)庫處理的一樣。 最后一個例子是萬維網(wǎng)。它提供了一種簡單、一致并且統(tǒng)一的分布式文檔模型。要查看某個文檔，用戶只須激活一個引用（即鏈接），文檔就會顯示在屏幕上。理論上（但目前在實際中并不是這樣）并不需要知道該文檔來自于哪個服務(wù)器，更用不著關(guān)心服務(wù)器所在的位置。要發(fā)布一個文檔也很簡單：只需要賦予它一個唯一的url名，讓該url指向包含文檔內(nèi)容的本地文件即可。如果萬維網(wǎng)向用戶呈現(xiàn)

19、的是一個龐大的集中式文檔系統(tǒng)，也可以認(rèn)為它是一個分布式系統(tǒng)。不幸的是，我們現(xiàn)在還無法做到這一點。例如，用戶明白這樣一個事實：文檔位于不同的地點，并由不同的服務(wù)器處理。 1.2 目 標(biāo) 分布式系統(tǒng)必須能夠讓用戶方便地與資源連接；必須隱藏資源在一個網(wǎng)絡(luò)分布這樣一個事實；必須是開放的；必須是可擴展的。 1.2.1 讓用戶連接到資源 分布式系統(tǒng)最主要目標(biāo)是使用戶能夠方便地訪問遠(yuǎn)程資源，并且以一種受控的方式與其他用戶共享這些資源。資源幾乎可以是任何東西，其典型例子包括打印機、計算機、存儲設(shè)備、數(shù)據(jù)、文件、web頁以及網(wǎng)絡(luò)，但這些只是資源中的一小部分。有很多理由要求資源共享，一個顯而易見的理由是降低經(jīng)濟成

20、本。例如，讓若干用戶共享一臺打印機比為每一位用戶購買并維護(hù)一臺打印機要劃算的多。基于同樣的原因，共享超級計算機和高性能存儲系統(tǒng)這樣昂貴資源也是很有意義的。 1.2.2 透明性 如果一個分布式系統(tǒng)能夠在用戶和應(yīng)用程序面前呈現(xiàn)為單個計算機系統(tǒng)，這樣的分布式系統(tǒng)就稱為透明的。 1分布式系統(tǒng)的透明性 透明性的概念可以運用到分布式系統(tǒng)中的各個方面，如圖1.2所示。 透明性說明訪問隱藏數(shù)據(jù)表示形式的不同以及資源訪問方式的不同位置隱藏資源所在位置遷移隱藏資源是否移動到另一個位置重定位隱藏資源是否在使用過程中移動到另一個位置復(fù)制隱藏是否資源進(jìn)行復(fù)制并發(fā)隱藏資源是否由若干相互競爭的用戶共享故障隱藏資源的故障和恢

21、復(fù)持久性隱藏資源（軟件）位于內(nèi)存中還是硬盤中圖1.2 分布式系統(tǒng)中不同形式的透明性（iso 1995） 訪問透明性指對不同數(shù)據(jù)表示形式以及資源訪問方式的隱藏。例如，要將一個整型數(shù)從基于intel處理器的工作站傳輸?shù)揭慌_sun sparc機器上，我們必須考慮到intel處理器傳輸數(shù)據(jù)字節(jié)的順序是little endian格式（先傳輸數(shù)據(jù)的高位字節(jié)），而sparc處理器卻使用big endian（先傳輸數(shù)據(jù)的低位字節(jié)）。在數(shù)據(jù)表示形式上還會存在其他的差別。例如，分布式系統(tǒng)中的多個計算機系統(tǒng)可能運行的是不同的操作系統(tǒng)，這些操作系統(tǒng)的文件命名方式不同。文件命名方式的差異以及由此引發(fā)的文件操作方式的差異

22、都應(yīng)該對用戶和應(yīng)用程序隱藏起來。2透明度 雖然對于任何分布式系統(tǒng)來說，實現(xiàn)分布透明性通常是可取的，但是在某些情況下，把所有分布情況都對用戶屏蔽得嚴(yán)嚴(yán)實實并不見得有好處。這樣的一個例子是，如果您訂閱了一份電子報刊，并且要求它在每天本地時間早上7點之前就寄到郵箱里，而您現(xiàn)在呆在地球另一端的不同時區(qū)，您就會發(fā)現(xiàn)“早報”不在是早上寄到的。 另外，還必須在高度的透明性和系統(tǒng)性能之間進(jìn)行權(quán)衡，得出折衷方案。例如，許多internet應(yīng)用程序會不斷嘗試連接到某臺服務(wù)器，多次失敗后才最終放棄。這種在用戶轉(zhuǎn)向另一臺服務(wù)器之前竭力隱藏服務(wù)器短暫故障的企圖會導(dǎo)致整個系統(tǒng)變慢。在這種情況下，最好還是讓用戶早一些放棄，

23、或者至少允許用戶取消這種連接的嘗試。 在設(shè)計并實現(xiàn)分布式系統(tǒng)時，把實現(xiàn)分布的透明性作為目標(biāo)是正確的，但是應(yīng)該將它和其他方面的問題（比如性能）結(jié)合起來考慮。1.2.3 開放性 開放的分布式系統(tǒng)的另一個重要目標(biāo)是，它必須是靈活的，要能夠方便的把由不同開發(fā)人員開發(fā)的不同組件組合成整個系統(tǒng)。同時，還必須能夠方便地添加新組件、替換現(xiàn)有的組件，而不會對那些無須改動的組件造成影響。換句話說，開放的分布式系統(tǒng)應(yīng)該是可擴充的。例如，在靈活的系統(tǒng)中，要添加可運行于另一個操作系統(tǒng)上的部件應(yīng)該是比較容易的，即使要更換整個文件系統(tǒng)也不應(yīng)該太對困難。但根據(jù)我們從日常實踐中得到的經(jīng)驗，要實現(xiàn)靈活性是比較困難的。1.2.4可

24、擴展性 通過互聯(lián)網(wǎng)，世界范圍的互聯(lián)正在變得像給世界任何地方的人寄張明信片一樣平常?？紤]到這種情況，分布式系統(tǒng)開發(fā)者都將可擴展性作為最重要的實際目標(biāo)之一。 系統(tǒng)的可擴展性至少可以通過三個方面來度量（neuman 1994）。首先，系統(tǒng)要能在規(guī)模上擴展，也就是說可以方便地把更多的用戶和資源加入到系統(tǒng)中去。其次，如果系統(tǒng)中的用戶和資源可以相隔極為遙遠(yuǎn)，這種系統(tǒng)就稱為地域上可擴展的系統(tǒng)。最后，系統(tǒng)在管理上是可擴展的，也就是說，即使該分布式系統(tǒng)跨越多個獨立的管理機構(gòu)，仍然可以方便地對其進(jìn)行管理。不幸的是，在以上這三個方面或其中某一兩個方面可擴展的系統(tǒng)常常在擴展之后表現(xiàn)出性能的下降。1.3 分布式文件系統(tǒng)

25、 鑒于共享數(shù)據(jù)是分布式系統(tǒng)的基礎(chǔ)，分布式文件系統(tǒng)是構(gòu)成許多分布式應(yīng)用程序的基礎(chǔ)就不足為奇了。分布式文件系統(tǒng)允許多個進(jìn)程在長時期內(nèi)以一種安全、可靠的方式共享數(shù)據(jù)。所以，它們已被用作分布式系統(tǒng)和分布式應(yīng)用程序的基礎(chǔ)層。在本節(jié)中，我們把分布式文件系統(tǒng)看作通用分布式系統(tǒng)的模型。 我們將詳細(xì)討論兩個不同的分布式文件系統(tǒng)。第一個實例是sun nfs(net work file system,網(wǎng)絡(luò)文件系統(tǒng))，它已經(jīng)得到了廣泛應(yīng)用，現(xiàn)在正逐漸向基于internet的大規(guī)模文件系統(tǒng)的方向發(fā)展。nfs的大多數(shù)實現(xiàn)基于其版本3規(guī)范。 另一個完全不同的分布式文件系統(tǒng)是coda。coda源于afs（andrew文件系統(tǒng)

26、），afs是一個在設(shè)計是就考慮到可擴展性的大規(guī)模系統(tǒng)。coda與許多其他文件系統(tǒng)的區(qū)別在于它在面對網(wǎng)絡(luò)分區(qū)時支持連續(xù)操作。特別是那些故意時常斷開網(wǎng)絡(luò)連接的移動用戶（比如，使用膝上型計算機的人們）會從中獲益。 我們也將簡要講述其他三個系統(tǒng)。plan9是一個將所有資源都視為文件的分布式系統(tǒng)。從這種意義上來說，它可以被視為一個基于文件的分布式系統(tǒng)。我們將講述的另一個系統(tǒng)是xfs，其與眾不同之處在于它沒有服務(wù)器，而是讓客戶實現(xiàn)文件系統(tǒng)。最后，我們會介紹sfs，該系統(tǒng)強調(diào)可擴展的安全性。1.3.1 sun網(wǎng)絡(luò)文件系統(tǒng) 我們以sun微系統(tǒng)的網(wǎng)絡(luò)文件系統(tǒng)（network file system），即通常所說

27、的nfs，開始討論分布式文件系統(tǒng)。nfs最初是sun為在它的基于unix的工作站上的使用而開發(fā)的，但是nfs已在許多其他系統(tǒng)中實現(xiàn)。nfs的基本思想是每臺文件服務(wù)器提供它的本地文件系統(tǒng)的標(biāo)準(zhǔn)化視圖。也就是說，它不關(guān)心如何實現(xiàn)本地文件系統(tǒng)，每臺nfs服務(wù)器支持相同的模型。這個模型帶有一個通信協(xié)議，該協(xié)議允許客戶訪問存儲在一臺服務(wù)器上的文件。這種方法允許大量異構(gòu)進(jìn)程共享一個公共的文件系統(tǒng)，其中的進(jìn)程可能運行于不同的操作系統(tǒng)和機器上。1nfs概述 與其說nfs是一個真正的文件系統(tǒng)，不如說它是共同為客戶提供分布式文件系統(tǒng)模型的協(xié)議的集合。nfs協(xié)議是以不同的實現(xiàn)之間應(yīng)該易于進(jìn)行互操作為目的而設(shè)計的。因

28、此，nfs可以運行于大量異構(gòu)計算機之上。2.nfs體系結(jié)構(gòu)nfs底層的模型是遠(yuǎn)程文件服務(wù)的模型。這個模型為客戶提供對遠(yuǎn)程服務(wù)器所管理的文件系統(tǒng)的透明訪問。但是，客戶通常不知道文件的實際位置，相反，nfs為客戶提供訪問此文件系統(tǒng)的接口，此接口類似于傳統(tǒng)本地文件系統(tǒng)所提供的接口。也就是說，客戶僅被提供包含多種文件操作的接口，而服務(wù)器負(fù)責(zé)實現(xiàn)這些操作。因此，這一模型也被稱為遠(yuǎn)程訪問模型（remote access model），如圖1.3.1（a）所示圖1.3.1（a）客戶服務(wù)器文件位于服務(wù)器上來自客戶的訪問遠(yuǎn)程文件的請求3.當(dāng)客戶程序被執(zhí)行后，文件返回服務(wù)器 舊文件新文件客戶服務(wù)器1.文件移動到客

29、戶2.在客戶上執(zhí)行訪問 1.3.1（b）上載/下載模型與之相對照，在上載、下載模型（upload/download model）中，客戶從服務(wù)器下載文件后，在本地訪問該文件，如圖1.3.1（b）所示。客戶完成對文件的訪問后，再將該文件上載回服務(wù)器，以便其他客戶使用該文件。當(dāng)客戶下載一個完整的文件，修改該文件，然后將其放回服務(wù)器時，可以使用internet的ftp服務(wù)。盡管nfs基于unix的版本占主流地位，但是nfs已開發(fā)了多種版本以用于許多不同的操作系統(tǒng)。實際上，對所有現(xiàn)代unix系統(tǒng)而言，nfs通常按照圖1.3.1（c）所示的層次體系結(jié)構(gòu)實現(xiàn)。 圖1.3.1（c）3.文件系統(tǒng)模型 nfs版

30、本四支持硬鏈接和符號鏈接。文件具有文件名，但是訪問它們是通過一種類似unix的文件句柄（file handle）實現(xiàn)的，為訪問一個文件，客戶必須現(xiàn)在命名服務(wù)器中搜索該文件的文件名，然后獲得該文件關(guān)聯(lián)的文件句柄。另外，每個文件有許多屬性，這些屬性是可以查詢和修改的。下表列出了nfs支持的通用文件操作。操作描述create創(chuàng)建一個非常規(guī)文件link創(chuàng)建一個文件的硬鏈接rename更改文件名remove從文件系統(tǒng)刪除一個文件open打開一個文件close關(guān)閉一個文件lookup根據(jù)文件名搜索文件readdir讀取一個目錄下的項目readlink讀取符號鏈接所存儲的路徑名getattr獲得文件的屬性值

31、setattr設(shè)置文件的一個或多個屬性值read 讀取文件中的數(shù)據(jù)write向文件寫入數(shù)據(jù)1.3.2不同分布式文件系統(tǒng)對比該表總結(jié)了5種不同分布式文件系統(tǒng)的各個要點： 要點nfscodaplan9xfsspf設(shè)計目標(biāo)訪問透明性高可用性統(tǒng)一性無服務(wù)器系統(tǒng)可擴展的安全性訪問模型遠(yuǎn)程上載/下載遠(yuǎn)程基于日志遠(yuǎn)程通信rpcrpc特殊方法活動消息rpc客戶進(jìn)程瘦/胖胖瘦胖中等服務(wù)器組無有無有無裝入粒度目錄文件系統(tǒng)文件系統(tǒng)文件系統(tǒng)目錄名稱空間每個客戶全局每個進(jìn)程全局全局文件id范圍文件服務(wù)器全局服務(wù)器全局文件系統(tǒng)共享語義會話事務(wù)處理unixunixn/s緩存單元文件文件文件塊n/s高速緩存一致性回寫式回寫式

32、直寫式回寫式回寫式復(fù)制最低限度rowa無帶區(qū)劃分無容錯可靠的通信復(fù)制與緩存可靠的通信帶區(qū)劃分可靠地通信恢復(fù)基于客戶重新合成n/s 檢查點和記錄日志n/s安全通道現(xiàn)存的機制重新合成n/s檢查點和記錄日志自證明訪問控制許多操作目錄操作基于unix基于unix基于nfs注：n/s表示無特殊規(guī)定第二章p2p技術(shù)2.1 p2p技術(shù)2.1.1 p2p的背景與發(fā)展 對等網(wǎng)絡(luò)p2p（peer to peer），維基百科是這樣定義的：p2p技術(shù)是一種網(wǎng)絡(luò)新技術(shù)，依賴網(wǎng)絡(luò)中參與者的計算能力和帶寬，而不是把依賴都聚集在較少的幾臺服務(wù)器上。在p2p網(wǎng)絡(luò)環(huán)境中，成千上萬臺彼此連接的計算機都處于平等的地位，整個網(wǎng)絡(luò)一般來

33、說不會依賴于專門的中央服務(wù)器。網(wǎng)絡(luò)中的每一臺計算機既能充當(dāng)網(wǎng)絡(luò)服務(wù)的請求者，又能對其他計算機的請求做出響應(yīng)，提供資源或其他服務(wù)。 p2p技術(shù)的發(fā)展可以追溯到上世紀(jì)九十年代，由一個叫肖恩的大一學(xué)生編寫的叫napster的程序，這個程序能搜索音樂文件并提供檢索功能。隨著互聯(lián)網(wǎng)的發(fā)展，尤其是上世紀(jì)90年代后期，計算機硬件的性能有了突飛猛進(jìn)的發(fā)展，而且網(wǎng)絡(luò)帶寬等基礎(chǔ)設(shè)施也大幅的改善，人們開始感到有必要而且能夠直接控制、修改和共享資源。隨后開始把服務(wù)器軟件也放在單獨的pc上，而且在pc與pc之間直接進(jìn)行通信，這就導(dǎo)致了p2p技術(shù)的復(fù)興。p2p技術(shù)主要指由硬件形成網(wǎng)絡(luò)連接后的信息控制技術(shù)，是應(yīng)用層上的一種

34、邏輯網(wǎng)絡(luò)，主要的代表就是在基于p2p網(wǎng)絡(luò)協(xié)議的各種客戶端軟件。由上文可知，p2p網(wǎng)絡(luò)是屬于疊加在底層通信網(wǎng)絡(luò)基礎(chǔ)之上的邏輯網(wǎng)絡(luò)，是應(yīng)用層的程序，也是一個分布式、具有互操作性的自組織系統(tǒng)。p2p網(wǎng)絡(luò)面臨的最大的挑戰(zhàn)之一就是如何在沒有集中式服務(wù)器的模式下維護(hù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，以及實現(xiàn)資源檢索等服務(wù)。在p2p網(wǎng)絡(luò)中，如何對資源進(jìn)行準(zhǔn)確的定位是最重要的問題。現(xiàn)階段p2p搜索技術(shù)的研究可以從兩個方面來進(jìn)行，第一個方面是從p2p搜索算法入手來進(jìn)行研究，第二個方面是從p2p的體系架構(gòu)入手進(jìn)行研究。p2p搜索算法包括：chord算法，pastry算法，tapestry算法，can算法和kademlia算法等等。p

35、2p體系架構(gòu)方面包括：集中式系統(tǒng)，分布式系統(tǒng)，混合式系統(tǒng)。2.1.2p2p技術(shù)的分類拓?fù)浣Y(jié)構(gòu)是指分布式系統(tǒng)中各個計算單元之間的物理或邏輯的互聯(lián)關(guān)系，節(jié)點之間的拓?fù)浣Y(jié)構(gòu)一直是確定系統(tǒng)類型的重要依據(jù)。p2p系統(tǒng)主要采用非集中式的拓?fù)浣Y(jié)構(gòu)，根據(jù)結(jié)構(gòu)關(guān)系可以將p2p系統(tǒng)細(xì)分為叫種結(jié)構(gòu)的拓?fù)湫问剑褐行幕負(fù)渚W(wǎng)絡(luò)、全分布式非結(jié)構(gòu)化拓?fù)渚W(wǎng)絡(luò)、全分布式結(jié)構(gòu)化拓?fù)渚W(wǎng)絡(luò)以及半分布式拓?fù)渚W(wǎng)絡(luò)。1. 中心化拓?fù)渚W(wǎng)絡(luò)中心化拓?fù)渚W(wǎng)絡(luò)最大的優(yōu)點是維護(hù)簡單，發(fā)現(xiàn)效率高。由于資源的發(fā)現(xiàn)依賴中心 化的目錄系統(tǒng)，發(fā)現(xiàn)算法靈活、高效并能夠?qū)崿F(xiàn)復(fù)雜查詢。最大的問題與傳統(tǒng)c/s結(jié)構(gòu)類似，容易造成單點故障，訪問的“熱點”現(xiàn)象和法律等相關(guān)問

36、題，這是第一代p2p網(wǎng)絡(luò)采用的結(jié)構(gòu)模式，經(jīng)典案例就是著名的mp3共享軟件napster。 在napster模型中，一群高性能的中央服務(wù)器保存著網(wǎng)絡(luò)中所有活動對等計算機共享資源的目錄信息。當(dāng)需要查詢某個文件時，對等機會向一臺中央服務(wù)器發(fā)出文件查詢請求。中央服務(wù)器進(jìn)行相應(yīng)的檢索和查詢后，會返回符合查詢要求的對等機地址信息列表。查詢發(fā)起對等機接收到應(yīng)答后，會根據(jù)網(wǎng)絡(luò)流量和延遲等信息進(jìn)行選擇和合適的對等機建立連接，并開始文件傳輸。napster的工作原理如圖2.1.2（1）所示。 圖2.1.2（1）napster網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)采用napster結(jié)構(gòu)的中心化拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)也存在一些問題，主要表現(xiàn)為： (1

37、) 中央服務(wù)器的癱瘓容易導(dǎo)致整個網(wǎng)絡(luò)的崩饋，可靠性和安全性較低； (2)隨著網(wǎng)絡(luò)規(guī)模的擴大，對中央索引服務(wù)器進(jìn)行維護(hù)和更新的費用將急劇增加，所需成本過高；（3）中央服務(wù)器的存在引起共享資源在版權(quán)問題上的糾紛，并因此被攻擊為非純粹意義上的p2p網(wǎng)絡(luò)模型。綜合上述優(yōu)缺點，對小型網(wǎng)絡(luò)而言，中心化網(wǎng)絡(luò)模型在管理和控制方面占一定優(yōu)勢。但鑒于其存在的種種缺陷，該模型并不適合大型的網(wǎng)絡(luò)應(yīng)用。2.全分布式非結(jié)構(gòu)化的p2p網(wǎng)絡(luò) 全分布式非結(jié)構(gòu)化剛絡(luò)采用了隨機圖的組織方式，結(jié)點度數(shù)服從powerlaw”規(guī)律，從而能夠較快發(fā)現(xiàn)目的結(jié)點，而對網(wǎng)絡(luò)的動態(tài)變化體現(xiàn)了較好的容錯能力，因此具有較好的可用性，同時可以支持復(fù)雜查

38、詢，如帶有規(guī)則表達(dá)式的多關(guān)鍵詞查詢，模糊查詢等，采用這種拓?fù)浣Y(jié)構(gòu)最典型的案例便是gnutella，如圖2.1.2（2）所示。 圖2.1.2（2）gnutella網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)gnutella是一個p2p文件共享系統(tǒng)，它和napster最大的區(qū)別在于gnutella是純粹的p2p系統(tǒng)，不存在集中式的目錄服務(wù)器，并且文件的發(fā)布和網(wǎng)絡(luò)拓?fù)渌缮⑾嚓P(guān)。 gnutella網(wǎng)絡(luò)具有以下特點： (1) 不存在中央服務(wù)器，完全依賴于網(wǎng)絡(luò)中的交互式個人成員而獨立存在；(2)在浚網(wǎng)絡(luò)模型中，每一個聯(lián)網(wǎng)計算機在功能上都是對等的，既是客戶機同時又是服務(wù)器，所以被稱為對等機。 發(fā)現(xiàn)的準(zhǔn)確性和可擴展性是非結(jié)構(gòu)化網(wǎng)絡(luò)面臨的兩

39、個重要問題。目前對此類結(jié)構(gòu)的研究主要集中于改進(jìn)發(fā)現(xiàn)算法和復(fù)制策略以提高發(fā)現(xiàn)的準(zhǔn)確率和性能。3全分布式結(jié)構(gòu)化的p2p網(wǎng)絡(luò) 在這類網(wǎng)絡(luò)中，不存在中心化的目錄服務(wù)器，因此屬于全分布式的p2p網(wǎng)絡(luò)。這種類型的網(wǎng)絡(luò)結(jié)構(gòu)，采用分布式散列表(distributed hash table，簡稱dht)的全分布式結(jié)構(gòu)化拓?fù)渚W(wǎng)絡(luò)。分布式散列表實際上是一個由廣域范圍大量結(jié)點共同維護(hù)的巨大散列表。散列表被分割成不連續(xù)的塊，每個結(jié)點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。 dht結(jié)構(gòu)能夠自適應(yīng)結(jié)點的動態(tài)加入與退出，有著良好的可擴展性、魯棒性、結(jié)點id分配的均勻性和自組織能力。最經(jīng)典的案例是tapestr

40、y、chord、can和pastry。這里主要介紹一下具有代表性的chord網(wǎng)絡(luò)模型，如圖2.1.2(3)。該網(wǎng)絡(luò)模型誕生于美國的麻省理工學(xué)院，它的目標(biāo)是提供適合于p2p環(huán)境的分布式資源發(fā)現(xiàn)服務(wù)，它通過使用dht技術(shù)使得發(fā)現(xiàn)指定對象只需要維護(hù)o(109n)長度的路由表。在dht技術(shù)中，網(wǎng)絡(luò)節(jié)點按照一定的方式分配一個唯一節(jié)點標(biāo)識符(node，id)，資源對象通過散列運算產(chǎn)生一個唯一的資源標(biāo)識符(obiect，id)，且該資源將存儲在節(jié)點id與之相等或者相近的節(jié)點上。需要查找該資源時，采用同樣的方法可定位到存儲該資源的結(jié)點。因此，chord的主要貢獻(xiàn)是提出了一個分布式查找協(xié)議，該協(xié)議可將指定的關(guān)鍵

41、字(key)映射到對應(yīng)的節(jié)點(node)。 圖2.1.2（3）chord網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)dht結(jié)構(gòu)最大的問題是dht的維護(hù)機制較為復(fù)雜，尤其是結(jié)點頻繁加入退出造成的網(wǎng)絡(luò)波動會極大增加dht的維護(hù)代價。dht所面臨的另外一個問題是dht僅支持精確關(guān)鍵詞匹配查詢，無法支持內(nèi)容、語義等復(fù)雜查詢。4半分布式的p2p網(wǎng)絡(luò) 半分布式結(jié)構(gòu)吸取了中心化結(jié)構(gòu)和全分布式非結(jié)構(gòu)化拓?fù)涞膬?yōu)點，選擇性能較高(處理、存儲、帶寬等方面性能)的節(jié)點作為超級節(jié)點，在各個超級節(jié)點上存儲了系統(tǒng)中其他部分節(jié)點的信息，發(fā)現(xiàn)算法僅在超級節(jié)點之間轉(zhuǎn)發(fā)，超級節(jié)點再將查詢請求轉(zhuǎn)發(fā)給適當(dāng)?shù)娜~子結(jié)點。半分布式結(jié)構(gòu)也是一個層次式結(jié)構(gòu)，超級節(jié)點之問構(gòu)成

42、一個高速轉(zhuǎn)發(fā)層，超級節(jié)點和所負(fù)責(zé)的普通節(jié)點構(gòu)成若干層次。最典型的案例就是kazaa網(wǎng)絡(luò)結(jié)構(gòu)如圖2.1.2（4）所示。 圖2.1.2（4）kazza網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu) kazaa結(jié)合了napster和gnutella共同的優(yōu)點。從結(jié)構(gòu)上來說，它使用了gnutella的全分布式的結(jié)構(gòu)，這樣可以使系統(tǒng)更好的擴展，因為它無需中央服務(wù)器存儲文件名,它是自動的把性能好的機器作為超級節(jié)點，它存儲著離它最近的葉子節(jié)點的文件信息，這些超級節(jié)點再連通起來形成一個重疊網(wǎng)。由于超級節(jié)點的索引功能，使搜索效率大大提高。 半分布式結(jié)構(gòu)的優(yōu)點是性能、可擴展展性較好，較容易管理，但對超級節(jié)點依賴性大，易于受到攻擊，容錯性也受到影

43、響。表2.1.2四種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的性能比較比較標(biāo)準(zhǔn)/拓?fù)浣Y(jié)構(gòu)中心化拓?fù)淙植际椒墙Y(jié)構(gòu)化拓?fù)淙植际浇Y(jié)構(gòu)化拓?fù)浒敕植际酵負(fù)淇蓴U展性差差好中可靠性差好好中可維護(hù)性最好最好好中發(fā)現(xiàn)算法效率最好中高中復(fù)雜查詢支持支持不支持支持2.1.3p2p的特性 與其它網(wǎng)絡(luò)相比，p2p具有以下特性：（1）非中心性網(wǎng)絡(luò)中的資源和服務(wù)分散在所有節(jié)點上，信息的傳輸和服務(wù)的實現(xiàn)都直接在節(jié)點之間進(jìn)行，可以無需中間環(huán)節(jié)和服務(wù)器的介入，避免了可能的瓶頸。 (2)可擴展性 p2p的分散化帶來的一個直接的好處就是提升了系統(tǒng)的可擴展性。在p2p網(wǎng)絡(luò)中，隨著用戶的加入，不僅服務(wù)的需求增加了，系統(tǒng)整體的資源和服務(wù)能力也在同步地擴充，始終能

44、較容易地滿足用戶的需要。 (3)匿名性 p2p中一個很重要的特性就是匿名性。匿名性的一個重要日標(biāo)就是讓用戶在使用系統(tǒng)的時候不必受各種法律問題的約束，進(jìn)一步的目標(biāo)就是保證審查機構(gòu)無法對數(shù)字內(nèi)容進(jìn)行審查。 (4)自組織性 在p2p系統(tǒng)中，由于可擴展性、支持容錯、資源不斷地連接斷開以及擁有的開銷等原因，使系統(tǒng)具有一定的自組織特性是必要的。 (5)健壯性 p2p架構(gòu)天生具有耐攻擊、高容錯的優(yōu)點。由于服務(wù)是分散在各個節(jié)點之間進(jìn)行的，部分節(jié)點或網(wǎng)絡(luò)遭到破壞對其它部分的影響很小。而且p2p模型般在部分節(jié)點失效時能夠自動調(diào)整整體拓?fù)洌３制渌?jié)點的連通性。 (6)高性能性 性能優(yōu)勢是p2p被廣泛關(guān)注的個重要原

45、因。采用p2p架構(gòu)可以有效地利用互聯(lián)網(wǎng)中散布的大量普通節(jié)點，將計算任務(wù)或存儲資料分布到所有節(jié)點上。利用其中閑置的計算能力或存儲空間，達(dá)到高性能計算和海量存儲的目的。2.2 p2p搜索技術(shù)p2p搜索技術(shù)也依據(jù)p2p網(wǎng)絡(luò)的體系結(jié)構(gòu)而異，不同的體系結(jié)構(gòu)有著完全不同的搜索算法。在此我們主要討論非結(jié)構(gòu)化p2p網(wǎng)絡(luò)和結(jié)構(gòu)化p2p網(wǎng)絡(luò)的搜索技術(shù)。2.2.1非結(jié)構(gòu)化搜索技術(shù)非結(jié)構(gòu)化分布式p2p網(wǎng)絡(luò)完全脫離了中心服務(wù)器，網(wǎng)絡(luò)中每一個節(jié)點的地位都是平等的，每一個節(jié)點既是客戶端又是服務(wù)器，而且它們與相鄰的節(jié)點具有相同的能力，以gnutella為典型代表的一種網(wǎng)絡(luò)結(jié)構(gòu)。非結(jié)構(gòu)化的p2p網(wǎng)絡(luò)路由技術(shù)可以分為兩類：盲目搜

46、索和利用網(wǎng)絡(luò)中資源的分布信息進(jìn)行搜索。盲目搜索是從任意一個節(jié)點出發(fā)定位目標(biāo)節(jié)點，而不利用網(wǎng)絡(luò)中資源的分布信息進(jìn)行搜索，特點是網(wǎng)絡(luò)中的每一個節(jié)點記錄以前接收過的請求和響答，當(dāng)開始搜索的時候可以根據(jù)記錄對后續(xù)路由做出啟發(fā)。非結(jié)構(gòu)化p2p網(wǎng)絡(luò)搜索技術(shù)中最典型的便是泛洪算法。泛洪算法是最早出現(xiàn)在非結(jié)構(gòu)化的p2p網(wǎng)絡(luò)搜索算法中，它的特點是搜索時對全網(wǎng)的節(jié)點進(jìn)行遍歷和搜索。在泛洪搜索技術(shù)中，消息像洪水一樣在網(wǎng)絡(luò)中的各個節(jié)點之間流動，所以被稱作泛洪算法。泛洪搜索技術(shù)具體方法如下所示：在整個p2p網(wǎng)絡(luò)中，某個節(jié)點要搜索某個資源時，首先它向相鄰的節(jié)點發(fā)送查詢消息。如果某個節(jié)點擁有這個資源，就向查詢節(jié)點返回一個消

47、息，告訴查詢節(jié)點自己有這個資源，否則相鄰節(jié)點就再次把查詢消息轉(zhuǎn)發(fā)給自己再相鄰的節(jié)點。在整個查詢過程中，因為怕消息發(fā)出后在一個循環(huán)的區(qū)域里傳送，所以節(jié)點通過查詢消息的ttl（time to live，生存時間）值或者跳轉(zhuǎn)數(shù)來判斷查詢消息是否過期，當(dāng)ttl或者跳轉(zhuǎn)數(shù)超過一定的數(shù)值時，接收到消息的端就舍棄該消息。泛洪搜索算法比較簡單，實現(xiàn)起來也相對容易，但它在每次搜索的時候都進(jìn)行全網(wǎng)的遍歷，這樣便給網(wǎng)絡(luò)帶來了很大負(fù)載，而且搜索效率也不高，算法的時間復(fù)雜率是o(n)，整個網(wǎng)絡(luò)擴展性也極差，安全性也不好。2.2.2基于dht的搜索技術(shù)分布式結(jié)構(gòu)化p2p網(wǎng)絡(luò)搜索主要采用分布式哈希表算法來組織p2p網(wǎng)絡(luò)中的

48、節(jié)點。首先介紹一下哈希的概念：因為dht算法是基于一致性哈希函數(shù)（consistent hashing）的一種資源定位及搜索算法。一致性哈希使用的是如md5、sha-1等哈希函數(shù)。我們先簡單介紹一下哈希函數(shù)的概念：哈希函數(shù)，就是把任意長度的輸入（又叫做預(yù)映射，pre-image），通過具體的哈希算法，轉(zhuǎn)換成固定長度的輸出，該輸出就是哈希值。這種轉(zhuǎn)換是一種壓縮映射，也就是，哈希值的空間通常遠(yuǎn)遠(yuǎn)小于輸入的空間，不同的輸入可能會哈希出相同的輸出，而不可能從哈希值來唯一的確定輸入值，也就是哈希函數(shù)是不可逆的。哈希函數(shù)具備以下性質(zhì)：(1）可以作用于一個任意長度的數(shù)據(jù)塊。(2）能產(chǎn)生一個固定長度的輸出。(

49、3）對任何給定的x，hash(x)計算相對容易，無論是用硬件或者軟件都能實現(xiàn)。 (4）對任何給定的碼h，尋找x滿足hash(x)=h在計算上是不可行的(哈希函數(shù)的單向性)。(5）對任何給定的數(shù)據(jù)塊，尋找不等于x的y，使得hash(y)=hash(x)在計算上是不可行的。有時將此稱為弱抗沖突（weak collision resistance）。(6）尋找任何的(x,y)對滿足hash(x)=hash(y)在計算上是不可行的，有時將此稱為強抗沖突（strong collision resistance）。基于以上的性質(zhì)我們可以得到，哈希函數(shù)可以保證數(shù)據(jù)的唯一性。比較著名并且常用的哈希算法有md5

50、和sha-1算法等等。這兩者可以說是目前應(yīng)用最為廣泛的哈希算法，而它們都是以md4為基礎(chǔ)設(shè)計的。下面將詳細(xì)的介紹dht算法，它是一種分布式的路由算法，在不需要服務(wù)器的情況下，每臺機器只負(fù)責(zé)一小段范圍的路由，并負(fù)責(zé)存儲一小部分的數(shù)據(jù)，從而實現(xiàn)整個dht網(wǎng)絡(luò)的查找和存儲。在實際的系統(tǒng)中，p2p網(wǎng)絡(luò)的邏輯地址通常是由哈希函數(shù)得到的，每臺機器都將保存其中的一部分哈希表用來路由，所以分布式結(jié)構(gòu)化p2p網(wǎng)絡(luò)通常也稱為dht網(wǎng)絡(luò)。在分布式結(jié)構(gòu)化p2p網(wǎng)絡(luò)中，網(wǎng)絡(luò)中的每一臺計算機稱為一個節(jié)點，每一個節(jié)點有一個唯一的值用來標(biāo)識該節(jié)點，對于一個節(jié)點來說典型的表示就是它的ip地址和端口號。在p2p網(wǎng)絡(luò)中，每一個節(jié)點和每一個資源都需要一個標(biāo)識符，標(biāo)識符必須是獨一無二的一組數(shù)字，節(jié)點的標(biāo)識符可以通過對一個節(jié)點的ip地址和端口號作為預(yù)映射進(jìn)行哈希計算來獲得；資源將其一組關(guān)鍵字作為預(yù)映射進(jìn)行哈希，其運算的結(jié)果便作為該資