【正文】 2P 網(wǎng)絡(luò)符合小世界的特征，這意味著網(wǎng)絡(luò)中存在大量的高連通節(jié)點，部分節(jié)點之間存在“短鏈”現(xiàn)象。 通過研究小世界現(xiàn)象的規(guī)律，可以得出兩個結(jié)論： (1)冪規(guī)律分布指出，在實際網(wǎng)絡(luò)中，有少數(shù)節(jié)點擁有較高的“度”，而多數(shù)節(jié)點的“度”較低。 （ b）單個隨機(jī)連接的二維節(jié)點網(wǎng)絡(luò) （ c）多個隨機(jī)連接的二維節(jié)點網(wǎng)絡(luò) 然而，更進(jìn)一步研究，發(fā)現(xiàn)對 WattsStrogatz 模型做一些微小改動就會使搜索更有效：不是均勻地加入長距離連接，而是按某種分布率在網(wǎng)絡(luò)結(jié)點問添加連接，即讓在 d 維空間中節(jié)點連接的幾率隨距離的增大以 d 次冪衰減。這一分散路由方案也有力的揭示了計算機(jī)網(wǎng)絡(luò)中一些潛在的驚人特點。這是一個涉及社會學(xué)，數(shù)學(xué)和計算科學(xué)問題的多學(xué)科交叉問題。 綜上所述，本文發(fā)現(xiàn)影響 P2P 搜索算法性能主要有以下兩個因素： (1)P2P 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，網(wǎng)絡(luò)的穩(wěn)定性，包括節(jié)點的加入與退出。具體搜索 過程如圖 (b)所示。 圖 查找過程 29 Hash 節(jié)點 IP地址－ m位節(jié)點 ID(表示為 NID) Hash 內(nèi)容關(guān)鍵字－ m 位 K(表示為 KID) 節(jié)點按 ID 從小到大順序排列在一個邏輯環(huán)上 K, V存儲在后繼節(jié)點上， Successor (K)：從 K 開始順時針方向距離 K最近的節(jié)點 Hash 節(jié)點 IP地址－ m位節(jié)點 ID(表示為 NID) Hash 內(nèi)容關(guān)鍵字－ m 位 K(表示為 KID) 節(jié)點按 ID 從小到大順序排列在一個邏輯環(huán)上 K, V存儲在后繼節(jié)點上 Successor (K)：從 K開始順時針方向距離 K 最近的節(jié)點 下面以查找 K54 為例，過程如下： （ a） (b) 30 (c) (d) 31 3 基于 DHT 的 Chord算法的改進(jìn) 影響搜索算法性能的因素 P2P 搜索算法與 P2P 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有著 密切的關(guān)系 [7]，針對不同的 P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，有著不同的搜索算法。 finger 表的大小是由哈希空間的大小決定的，如果哈希空間的大小是 2 的 m 次冪，那么 finger 表的大小即為 m， 也就是說一共有 finger 表上一共有 m 個表項，分別記錄的是節(jié)點的標(biāo)識符加 2i（ i=0,2,? m– 1） mod 2m的和的值的后繼節(jié)點地址。這個方法的基礎(chǔ)就是將要介紹的 finger 表。哈希函數(shù)通常是采用 SHA1 算法，生成 160位的標(biāo)識符 [11]。目前使用的一些互聯(lián)網(wǎng)上的共享資源的軟件，一般會查找到很多節(jié)點，再用一定的策略從各個節(jié)點同時下載。 NodeID 和 KeyID 兩者本質(zhì)上是一樣的類型，用有可能產(chǎn)生沖突的哈希函數(shù)計算出來有可能相同，將會對系統(tǒng)產(chǎn)生嚴(yán)重的影響，所以在哈希算法的選擇上有一定的要求。在 P2P 網(wǎng)絡(luò)中，每一個節(jié)點和每一個資源都需要一個標(biāo)識符，標(biāo)識符必 須是獨一無二的一組數(shù)字，節(jié)點的標(biāo)識符可以通過對一個節(jié)點的 IP地址和端口號作為預(yù)映射進(jìn)行哈希計算來獲得；資源將其一組關(guān)鍵字作為預(yù)映射進(jìn)行哈希，其運算的結(jié)果便作為該資源的標(biāo)識符，也由此標(biāo)識符決定此關(guān)鍵字對應(yīng)的那條信息由哪個節(jié)點負(fù)責(zé)儲存。這兩者可以說是目前應(yīng)用最為廣泛的哈希算法，而它們都是以 MD4 為基礎(chǔ)設(shè)計的。有時將此稱為弱抗沖突（ weak collision resistance）。 (2）能產(chǎn)生一個固定長度的輸出。一致性哈希使用的是如 MD SHA1等哈希函數(shù)。在整個查詢過程中，因為怕消息發(fā)出后在一個循環(huán)的區(qū)域里傳送，所以節(jié)點通過查詢消息的 TTL（ Time To Live，生存時間）值或者跳轉(zhuǎn)數(shù)來判斷查詢消息是否過期，當(dāng) TTL 或者跳轉(zhuǎn)數(shù)超過一定的數(shù)值時，接收到消息的端就舍棄該消息。泛洪算法是最早出現(xiàn)在非結(jié)構(gòu)化的 P2P 網(wǎng)絡(luò)搜索算法中，它的特點是搜索時對全網(wǎng)的節(jié)點進(jìn)行遍歷和搜索。 非結(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)。采用 P2P 架構(gòu)可以有效地利用互聯(lián)網(wǎng)中散布的大量普通節(jié)點，將計算任務(wù)或存儲資料分布到所有節(jié)點 上。 21 (5)健壯性 P2P 架構(gòu)天生具有耐攻擊、高容錯的優(yōu)點。在 P2P 網(wǎng)絡(luò)中，隨著用戶的加入，不僅服務(wù)的需求增加了，系統(tǒng)整體的資源和服務(wù)能力也在同步地擴(kuò)充，始終能較容易地滿足用戶的需要。由于超級節(jié)點的索引功能，使搜索效率大大提高。半分布式結(jié)構(gòu)也是一個層次式結(jié)構(gòu)，超級節(jié)點之問構(gòu)成一個高速轉(zhuǎn)發(fā)層，超級節(jié)點和所負(fù)責(zé)的普通節(jié)點構(gòu)成若干層次。因此， Chord 的主要貢獻(xiàn)是提出了一個分布式查找協(xié)議，該協(xié)議可將指定的關(guān)鍵字 (Key)映射到對應(yīng)的節(jié)點 (Node)。 這里主要介紹一下具有代表性的 chord 網(wǎng)絡(luò)模型，如圖 (3)。分布式散列表實際上是一個由廣域范圍大量結(jié)點共同維護(hù)的巨大散列表。 發(fā)現(xiàn)的準(zhǔn)確性和可擴(kuò)展性是非結(jié)構(gòu)化網(wǎng)絡(luò)面臨的兩個重要問 題。但鑒于其存在的種種缺陷，該模型并不適合大型的網(wǎng)絡(luò)應(yīng)用。查詢發(fā)起對等機(jī)接收到應(yīng)答后，會根據(jù)網(wǎng)絡(luò)流量和延遲等信息進(jìn)行選擇和合適的對等機(jī)建立連接 ，并開始文件傳輸。最大的問題與傳統(tǒng) c/s 結(jié)構(gòu)類似，容易造成單點故障，訪問的“熱點”現(xiàn)象和法律等相關(guān)問題，這是第一代 p2p 網(wǎng)絡(luò)采用的結(jié)構(gòu)模式，經(jīng)典案例就是著名的 MP3 共享軟件Napster。 . p2p 技術(shù)的分類 拓?fù)浣Y(jié)構(gòu)是指分布式系統(tǒng)中各個計算單元之間的物理或邏輯的互聯(lián)關(guān)系 [9]，節(jié)點之間的拓?fù)浣Y(jié)構(gòu)一直是確定系統(tǒng)類型的重要依據(jù)。在 P2P 網(wǎng)絡(luò)中，如何對資源進(jìn)行準(zhǔn)確的定位是最重要的問 題。隨后開始把服務(wù)器軟件也放在單獨的 PC上，而且在 PC與 PC之間直接進(jìn)行通信，這就導(dǎo)致了 P2P 技術(shù)的復(fù)興。在 P2P 網(wǎng)絡(luò)環(huán)境中，成千上萬臺彼此連接的計算機(jī)都處于平等的地位，整個網(wǎng)絡(luò)一般來說不會依賴于專門的中央服務(wù)器。文件具有文件名，但是訪問它們是通過一種類似 UNIX 的文件句柄（ file handle）實現(xiàn)的，為訪問一個文件，客戶必須現(xiàn)在命名服務(wù)器中搜索該文件的文件名，然后獲得該文件關(guān)聯(lián)的文件句柄。當(dāng)客戶下載一個完整的文件，修改該文件，然后將其放回服務(wù)器時，可以使用 Inter 的 FTP服務(wù)。但是，客戶通常不知道文件的實際位置，相反，NFS 為客戶提供訪問此文件系統(tǒng)的接口，此接口類似于傳統(tǒng)本地文件系統(tǒng)所提供的接口。 NFS 協(xié)議是以不同的實現(xiàn)之間應(yīng)該易 于進(jìn)行互操作為目的而設(shè)計的。也就是說，它不關(guān)心如何實現(xiàn)本地文件系統(tǒng)，每臺 NFS 服務(wù)器支持相同的模型。最后，我們會介紹 SFS，該系統(tǒng)強(qiáng)調(diào)可擴(kuò)展的安全性 [3]。 我們也將簡要講述其他三個系統(tǒng)。 另一個完全不同的分布式文件系統(tǒng)是 Coda。在本節(jié)中，我們把分布式文件系統(tǒng)看作通用分布式系統(tǒng)的模型 [2]。不幸的是，在以上這三個方面或其中某一兩個方面可擴(kuò)展的系統(tǒng)常常在擴(kuò)展之后表現(xiàn)出性能的下降。 系統(tǒng)的可擴(kuò)展性至少可以通過三個方面來度量（ Neuman 1994）。例如，在靈活的系統(tǒng)中，要添加可運行于另一個操作系統(tǒng)上的部件應(yīng)該是比較容易的，即使要更換整個文件系統(tǒng)也 不應(yīng)該太對困難。 在設(shè)計并實現(xiàn)分布式系統(tǒng)時，把實現(xiàn)分布的透明性作為目標(biāo)是正確的，但是應(yīng)該將它和其他方面的問題（比如性能）結(jié)合起來考慮。 另外，還必須在高度的透明性和系統(tǒng)性能之間進(jìn)行權(quán)衡，得出折衷方案。例如，分布式系統(tǒng)中的多個計算機(jī)系統(tǒng)可能運行的是不同的操作系統(tǒng)，這些操作系統(tǒng)的文件命名方式不同。 (1)分布式 系統(tǒng)的透明性 透明性的概念可以運用到分布式系統(tǒng)中的各個方面，如圖 所示。有很多理由要求資源共享，一個顯而易見的理由是降低經(jīng)濟(jì)成本。例如，用戶明白這樣一個事實：文檔位于不同的地點，并由不同的服務(wù)器處理。理論上（但目前在實際中并不是這樣）并不需要知道該文檔來自于哪個服務(wù)器，更用不著關(guān)心服務(wù)器所在的位置。用戶根本就看不到系統(tǒng)中訂單處理的物理流程；對于用戶來說，這些訂單像是由一個集中式數(shù)據(jù)庫處理的一樣。例如，銷售部的人員可能遍布在很大的一個區(qū)域，甚至全國。并且，當(dāng)用戶鍵入一個命令的時候，系統(tǒng)將尋找執(zhí)行該命令的最佳位置，也許會在自己的工作站上直接執(zhí)行該命令，也可能會在別人的一個空閑的工作站上執(zhí)行，還有可能有機(jī)房中某個尚未分配的處理器執(zhí)行。 圖 作為中間件組織的分布式系統(tǒng)（請注意，中間件層延伸到了多臺機(jī)器上） 現(xiàn)在我們考察一下分布式系統(tǒng)的幾個例子。 即使分布式系統(tǒng)中某些部分可能暫時發(fā)生故障，但其整體在通常情況下總是保持可用。同樣，用戶也看不到分布式系統(tǒng)的內(nèi)部組織結(jié)構(gòu)。第一方面是關(guān)于硬件的：機(jī)器本身是獨立的，第二個方面是關(guān)于軟件的：對用戶來說他們就像在與單個系統(tǒng)打交道。傳統(tǒng)的集中式系統(tǒng)一般由單個計算機(jī)及其外圍設(shè)備構(gòu)成，也可以包含一些遠(yuǎn)程終端。如果要傳輸大量的數(shù)據(jù)，傳輸數(shù)率可以達(dá)到 10～1000Mb/s。（不幸的是如果果真如此，光是說明如何打開車門這件事，就可能在用戶手冊中占 用長達(dá) 200 頁得篇幅。很多使用這些 cpu 的機(jī)器的計算性能都可以與大型機(jī)相媲美，而價格 卻比大型機(jī)便宜得多。而且由于沒有把這些計算機(jī)連接起來的手段，所以只能單獨的使用它們。Chord 論 計算機(jī) 系統(tǒng)正在經(jīng)歷一場革命。Chord Abstract： With the rapid development of information era, People increasingly find a single puter ability is very limited, Naturally they tempted to connect with puters in every region to processing information,thus the distributed proposed,but then es the resource sharing problem,that’s the Distributed File System here what we are talking about,as the development of p2p(peertopeer) technology,the problem of distributed storage and puting is well solved,the technology of p2p(peertopeer), as a new Inter technology,promoting the traditional centralized server Inter 2 Application Modle to centralized user Peer to Peer is important in DataExchange,PeertoPeer Computing,Coordinated Working,Search Service,etc,In P2P filesharing systems,it is developing from the beginning centralized model Napster and decentralized model Gnutella to the current mixed modle, such as BitTorrent,eMule,Kazza, the DHT(Distrituted Hash Table) technology develops,it plays a more important role in P2P filesharing system,Kademlia is used widely in P2P filesharing system as an overlay work. Distributed architecture of the work is monly used to build P2P works using DHT algorithm,forinstance,Chord, CAN,Kademlia,Tapestry,Pastry, algorithms not only possess high reliability and strong fault tolerance,but also have efficient look plexity of search algorithm is basically O(LogN),so they are widely used in a variety of distributed storage systems. This paper study and pare the principles and differe nces of above DHT algorithms,research、 analysis and promote the Chord algorithm more decreasing the jump num