【導讀】論文題目基于DHT的分布式文件系統(tǒng)

　　

【正文】 是 finger 表的第一項 key 值就 大，則返回 finger 表的最后一個表項標識符的后繼節(jié)點地址作為下一跳地址； (5）發(fā)送查找請求給下一跳地址，重復過程 (2）到 (5），直到進入過程 (3）則 結(jié)束。 由此 可見， Chord 算法的查找過程是一個遞歸的過程，遞歸的結(jié)束條件是查 找到該資源關鍵字的 key 值所在的節(jié)點。 圖 查找過程 29 Hash 節(jié)點 IP地址－ m位節(jié)點 ID(表示為 NID) Hash 內(nèi)容關鍵字－ 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)容關鍵字－ 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算法的改進 影響搜索算法性能的因素 P2P 搜索算法與 P2P 網(wǎng)絡拓撲結(jié)構(gòu)有著 密切的關系 [7]，針對不同的 P2P網(wǎng)絡拓撲結(jié)構(gòu)，有著不同的搜索算法。對于集中式的網(wǎng)絡拓撲結(jié)構(gòu)，如圖 (a)，由于存在中央服務器，整個系統(tǒng)對中央服務器的依賴度很高，一旦中央服務器受到黑客攻擊出問題，整個網(wǎng)絡系統(tǒng)將立即崩潰。 圖 （ a）集中式網(wǎng)絡拓撲結(jié)構(gòu) 對于非結(jié)構(gòu)化的 P2P 網(wǎng)絡拓撲結(jié)構(gòu)，大多采用的是泛洪搜索算法。這種搜索算法雖然搜索范圍很廣，但是因為網(wǎng)絡拓撲結(jié)構(gòu)的原因，在搜索過程中會產(chǎn)生大量的消息冗余，另外搜索廣度也不易控制，造成了資源的浪費。具體搜索 過程如圖 (b)所示。 32 圖 （ b）消息冗余圖示 如圖 3— 2，當網(wǎng)絡中的節(jié)點 A 要在 j 網(wǎng)絡中搜索目標對象資源的時候，它首先會向自己的鄰居節(jié)點 B 和 c 發(fā)送搜索消息，當 B 和 c 接收到這個消息后，同時又會向自己的鄰居節(jié)點 D、 E 以及 E、 F 發(fā)送廣播消息，在這樣一個非結(jié)構(gòu)化網(wǎng)絡拓撲中，搜索過程中就會產(chǎn)生大量的消息冗余，如節(jié)點 B 在收到搜索請求后，同樣也會向節(jié)點 c 發(fā)送消息 (冗余搜索消息為圖中虛線所示 )，嚴重影響搜索效率，同時也造成了資源的浪費。 對于結(jié)構(gòu)化 P2P 網(wǎng)絡搜索算法，比如傳統(tǒng)的 Chord 算法。由于整個網(wǎng)絡拓撲成 一個環(huán)形狀，當要在該網(wǎng)絡中搜索目標對象資源時，搜索方向足按照順時針的方向進行搜索的，如要從 N8 這個節(jié)點開始搜索 K54 這個資源，那么搜索過程中所遍歷的網(wǎng)絡節(jié)點將會很多，雖然也能搜索到需要的資源，但是效率不高。 綜上所述，本文發(fā)現(xiàn)影響 P2P 搜索算法性能主要有以下兩個因素： (1)P2P 網(wǎng)絡拓撲結(jié)構(gòu)，網(wǎng)絡的穩(wěn)定性，包括節(jié)點的加入與退出。 (2)搜索消息在網(wǎng)絡中的路由尋址策略，即搜索算法。 小世界現(xiàn)象對 P2P 搜索技術的啟示 所謂小世界現(xiàn)象，或稱“六度分離 (six degrees of separation)”，是社會網(wǎng)絡中的基本問題，即每個人只需要很少的中間人 (平均 6 個 )就可以和全世界的 33 人建立起聯(lián)系。在這一理淪中，每個人可看作是圖的節(jié)點 [14]，并有大量路徑連接著他們，相連接的節(jié)點表示互相認識的人。這是一個涉及社會學，數(shù)學和計算科學問題的多學科交叉問題。該問題源于社會心理學家 Stanley Milgram 上世紀 60年代做的實驗：“追蹤美國社交網(wǎng)絡中的最短路徑”。他要求每個參與者寄信給一個住在波士頓附近的“目標人物”，規(guī)定每個參與者只能轉(zhuǎn)發(fā)給一個他們認識的人，Mil 腫 m 發(fā)現(xiàn)完整的鏈平均長度為 6個人，如圖所 示 (a) 圖 （ a） 社會網(wǎng)絡中的小世界現(xiàn)象 Milgmm 的研究有兩大發(fā)現(xiàn)，社交網(wǎng)絡中短路徑的存在僅是其一，其二是社會中的人們，他們僅知道自己認識的人，就能很快地把信件轉(zhuǎn)發(fā)到任何遠方目標。用計算術語來講，就是關于路由算法 (routing algorithm)的效率問題，這一算法可完全依靠本地信息來找到到達目的地的有效路徑。這一分散路由方案也有力的揭示了計算機網(wǎng)絡中一些潛在的驚人特點。 最近，應用數(shù)學家 Duncan Watts 和 Steve Strogatz 提 出利用小世界性質(zhì)來研究網(wǎng)絡：一個高度聚集的包含了“局部連接”節(jié)點的子網(wǎng)，連同一些隨機的有助于產(chǎn)生短路徑的長距離無規(guī)連接 (random long— range short cuts)。除了對社會、技術和生物網(wǎng)絡的唯象研究 (empirical studies)， Watts 和 Strogatz 還考慮 34 了以下簡單模型系統(tǒng) :以一個 d 維格點網(wǎng)絡開始 (ddimensional lattice work)，給每個節(jié)點添加一些少量隨機長距離連接，把它們連接到隨機選擇的一些終點上。這樣構(gòu)建的網(wǎng)絡將會有局域聚集現(xiàn)象及短的路徑， 如圖 (b)(c)所示。 （ b）單個隨機連接的二維節(jié)點網(wǎng)絡 （ c）多個隨機連接的二維節(jié)點網(wǎng)絡 然而，更進一步研究，發(fā)現(xiàn)對 WattsStrogatz 模型做一些微小改動就會使搜索更有效：不是均勻地加入長距離連接，而是按某種分布率在網(wǎng)絡結(jié)點問添加連接，即讓在 d 維空間中節(jié)點連接的幾率隨距離的增大以 d 次冪衰減。實際上，隨距離的 d次冪幾率衰減統(tǒng)一了所有距離的“尺度” —— 與一個節(jié)點距離為 1— 10節(jié)點構(gòu)成連接的數(shù)目大致和它與距離為 10100， 100 一 1000 等的節(jié)點構(gòu)成 連接的數(shù)目一樣，如圖 (d) 圖 (d)按 d 次冪衰減帶有多個不同距離的隨機連接生成的節(jié)點 35 在 P2P 系統(tǒng)中，這一利用連接幾率隨距離衰減的連接方式能夠建立搜索得到了證明。在 P2P 中，文件內(nèi)容需要通過一個節(jié)點以分散方式檢索另一節(jié)點。換句話說，結(jié)點執(zhí)行搜索協(xié)議時就像是在參與 Milgram 的實驗一樣。 通過研究小世界現(xiàn)象的規(guī)律，可以得出兩個結(jié)論： (1)冪規(guī)律分布指出，在實際網(wǎng)絡中，有少數(shù)節(jié)點擁有較高的“度”，而多數(shù)節(jié)點的“度”較低?！岸取贝砉?jié)點同其它節(jié)點的聯(lián)系程度。因此 ，通過“度”較高的節(jié)點找到待查找信息的概率也較高； (2)小世界模型特征指出，網(wǎng)絡拓撲具有高聚集度和短鏈的特性。在以小世界特征為基礎的網(wǎng)絡模型中，節(jié)點按照節(jié)點的聚集度被劃分為若干簇，在每個簇中至少存在一個度最高的節(jié)點為中心節(jié)點。大量的研究表明， P2P 網(wǎng)絡符合小世界的特征，這意味著網(wǎng)絡中存在大量的高連通節(jié)點，部分節(jié)點之間存在“短鏈”現(xiàn)象。 圖 (e)P2P網(wǎng)絡的小世界現(xiàn)象 因此，對 P2P 搜索算法的研究 [15]，從如何縮短路徑長度的問題變成了如何找到 這些“短鏈”的問題。尤其是在 DHT 搜索算法中，如何產(chǎn)生和找到“短鏈”是搜索算法設計的一個新思路，小世界模型的引入對 P2P 路由算法產(chǎn)生了重大的影響。 36 針對以上分析，有必要對現(xiàn)有的分布式 P2P 搜索算法進行改進，本文提出了一種分布式結(jié)構(gòu)化的 P2P 網(wǎng)絡拓撲，且對傳統(tǒng)的 Chord 搜索算法進行了擴展改進，并把這種分布式 P2P 搜索算法命名為 Nchord 搜索算法。 NChord 搜索算法 本節(jié)提出了一種分布式結(jié)構(gòu)化 P2P搜索算法，這種搜索算法首先對現(xiàn)有的 P2P 網(wǎng)絡拓撲結(jié)構(gòu)進行了改造，然后在現(xiàn)有的傳統(tǒng) Chord 搜 索算法的基礎上進行了擴充與改進，并提出了一種算法，命名為 NChord 搜索算法。 Nchord 算法網(wǎng)絡拓撲結(jié)構(gòu) 在 5． 1 節(jié)中，本文得出了一個結(jié)論：影響 P2P 搜索算法效率的主要因素包括 P2P 的網(wǎng)絡拓撲結(jié)構(gòu)。中心化網(wǎng)絡拓撲結(jié)構(gòu)以及全分布式網(wǎng)絡拓撲結(jié)構(gòu)都有它們固有的缺陷，前者對中心化服務器的依賴度非常大，后者在泛洪搜索過程中要產(chǎn)生大量的冗余消息，搜索量很大。因此，本節(jié)針對 P2P 網(wǎng)絡的特點，結(jié)合小世界現(xiàn)象規(guī)律，在傳統(tǒng)的 Chord 搜索模型基礎上提出了一種 NChord 網(wǎng)絡模型，如圖(a)所 示。 37 圖 (a)Nchord網(wǎng)絡拓撲結(jié)構(gòu)模型 該網(wǎng)絡拓撲結(jié)構(gòu)由內(nèi)外兩個環(huán)形網(wǎng)絡組成，采用分布式散列表(Distributed Hash Table，簡稱 DHT)的分布式網(wǎng)絡結(jié)構(gòu)。散列表被分割成不連續(xù)的塊，每個結(jié)點被分配給一個屬于自己的散列塊，并成為這個散列塊的管理者。DHT 的結(jié)點既是動態(tài)的，結(jié)點數(shù)量也是巨大的，因此非中心化和原子自組織成為這種網(wǎng)絡的重要特點 由小世界現(xiàn)象規(guī)律可知， P2P 網(wǎng)絡中的每個節(jié)點都表現(xiàn)出了某些可以被捕捉到的興趣，而興趣相近的節(jié)點保存的內(nèi)容和提交的查詢也呈現(xiàn)出一定的相關性。通過挖掘每個節(jié)點的興趣，將節(jié)點按照它們所表現(xiàn)出的相關性組成網(wǎng)絡，使得相關性高的節(jié)點在網(wǎng)絡中比較接近，這樣對提高查詢檢索效率是非常有效的。 網(wǎng)絡中的各個節(jié)點按照活躍程度分布在不同的網(wǎng)絡環(huán)中，外環(huán)上的節(jié)點屬于普通節(jié)點，內(nèi)環(huán)上的節(jié)點屬于超級節(jié)點，內(nèi)環(huán)中的節(jié)點都是系統(tǒng)中比較活躍的節(jié)點，表現(xiàn)為經(jīng)常在線，而且所存儲的數(shù)據(jù)對象都是當前網(wǎng)絡中很流行的，熱度較高的資源。 不管是普通節(jié)點還是超級節(jié)點，節(jié)點在加入該網(wǎng)絡的時候，根據(jù)特定的散列函數(shù)計算后，得到一個唯一的鍵值，散列函數(shù)可以做到負載平衡，使網(wǎng)絡中節(jié)點的分稚達到均衡，各節(jié)點 通過該鍵值知道自己所在的區(qū)域。如圖 中的 1， 2， 3，4， 5 代表各個區(qū)號，即各個超級節(jié)點在內(nèi)環(huán)網(wǎng)中的具體位置。每個節(jié)點都維護著自己的一張路由信息表，該表中保存了節(jié)點的一些相關信息，包括節(jié)點存儲的資源，資源的流行性以及熱門度。搜索資源的時候，各節(jié)點按照自己的這張路由索引表進行消息的路由。 從上圖可以看出，該網(wǎng)絡拓撲結(jié)構(gòu)不同于中心化的網(wǎng)絡拓撲結(jié)構(gòu)，因此在單個重要節(jié)點受攻擊或是退出的時候，對整個網(wǎng)絡來說影響是非常有限的；比較全分布式的 P2P 網(wǎng)絡結(jié)構(gòu)，由于 Nchord 網(wǎng)絡是環(huán)形結(jié)構(gòu)，在搜索資源時，不會像有很多聯(lián)通 路徑的三角圖或樹形圖，在廣播泛洪過程中會產(chǎn)生大量的冗余消息。 38 節(jié)點加入時的策略 當一個新節(jié)點 n加入 NChord 網(wǎng)絡時，需要按照以下幾個步驟完成工作： (1)初始化本地節(jié)點查詢表。節(jié)點 n加入網(wǎng)絡時，通過散列函數(shù)的計算，得到網(wǎng)絡中一個唯一的 ID值，根據(jù)該 lD 值， n 與內(nèi)環(huán)網(wǎng)絡中的某個超級節(jié)點 n’ 建立連接。這時，為了初始化 n 的路由索引表， n將要求超級節(jié)點 n’為它查找路由索引表中的其它表項： (2)更新網(wǎng)絡中其它節(jié)點的路由索引表。節(jié)點加入網(wǎng)絡后，將通知其它節(jié)點，讓其它節(jié)點及時的更新自己的路由索引表。在更 新路由索引表的時候，新節(jié)點應該參照網(wǎng)絡中已有的路由索引表，查看自己是否存儲有熱門數(shù)據(jù)對象，按照資源的熱門度對索引表進行更新； (3)轉(zhuǎn)移關鍵字信息。其它節(jié)點將所有鍵值歸屬于 n的關鍵字 (即后繼節(jié)點是 n的關鍵字 )轉(zhuǎn)移到節(jié)點 n上，更新完成后，節(jié)點 n將向網(wǎng)絡中的其它節(jié)點發(fā)送新的路由索引表，各鄰居節(jié)點收到更新消息后，同時也向自己的鄰居節(jié)點發(fā)送新的路由索引表，直至整個系統(tǒng)更新完畢； (4)在更新路由索引表的過程中，如果遇到網(wǎng)絡堵塞或是延時，可以選擇合適的時機重新更新； (5)如果加入失敗，重新選擇另一個較近的超級節(jié)點 n”進行連接，重復上述步驟； (6)節(jié)點 n 完成節(jié)點加入流程。 節(jié)點退出時的策略 當網(wǎng)絡中的一個節(jié)點退出 Nchord 網(wǎng)絡時，需要完成以下幾個工作： (1)向鄰居節(jié)點發(fā)送消息，告知對方自己將退出系統(tǒng)； 39 (2)鄰居節(jié)點收到退出消息后，立即更新自己的路由索引表，同時也向自己的鄰居節(jié)點發(fā)送此消息，直至整個系統(tǒng)都已收到該消息，并更新成功； (3)保存自己的路由索引表，當再次進入該網(wǎng)絡的時候，可以減少需要維護的路由索引表項目，下次只需要對最新的信息進行更新就可以了； (4)該節(jié)點完成退出流程。 節(jié)點失效時的策略 當一個節(jié)點在加入 NChord 網(wǎng)絡或退出 NChord 網(wǎng)絡時，如果發(fā)送更新消息失敗， 則需要做如下處理： 不管是加入還是退出時發(fā)送更新消息，節(jié)點向網(wǎng)絡中自己的鄰居節(jié)點發(fā)送更新消息后，鄰居節(jié)點如果收到了消息，應該向發(fā)送消息的節(jié)點發(fā)送一個收到確認碼。比如節(jié)點 n 向節(jié)點 nr 發(fā)送一個更新路由索引表的消息， n 如果沒有收到 n’的確認碼，說明可能是發(fā)送失敗，那么這個時候節(jié)點 n就應該等待一段時問，重新向 n’節(jié)點發(fā)送更新消息，直到收到 n’的確認消息為止；如果 n總是沒有收到 n’的確認消息， 說明這個時候 n’節(jié)點可能已經(jīng)失效， n節(jié)點應該修改自己的路由索引表，向其它節(jié)點發(fā)送更新請求。 NChord 算法原理 在 Ncho