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

　　

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