午夜视频在线网站,日韩视频精品在线,中文字幕精品一区二区三区在线,在线播放精品,1024你懂我懂的旧版人,欧美日韩一级黄色片,一区二区三区在线观看视频

分享

P2P網(wǎng)絡(luò)中DHT算法分析...

 coolper 2007-12-24

本文首先從P2P的定義出發(fā),介紹了結(jié)構(gòu)化P2P與非結(jié)構(gòu)化P2P的區(qū)別以及結(jié)構(gòu)化P2P的核心技術(shù)DHT。而后,本文深入介紹了幾種主流的DHT算法與協(xié)議并對(duì)每種協(xié)議進(jìn)行了討論。文章的最后展望了DHT在未來(lái)的發(fā)展趨勢(shì)。

對(duì)等網(wǎng)絡(luò)(Peer-to-Peer,簡(jiǎn)稱(chēng)P2P)是目前非常熱門(mén)的應(yīng)用,自1999年以來(lái),P2P的研究一直是國(guó)外知名學(xué)府(如美國(guó)麻省理工學(xué)院,加州 大學(xué)伯克利分校和萊斯大學(xué)等)以及知名企業(yè)的研發(fā)機(jī)構(gòu)(如微軟,諾基亞的研究院)關(guān)注的重點(diǎn)。它甚至被美國(guó)《財(cái)富》雜志稱(chēng)為改變因特網(wǎng)發(fā)展的四大新技術(shù)之 一,被認(rèn)為是代表無(wú)線(xiàn)寬帶互聯(lián)網(wǎng)未來(lái)的關(guān)鍵技術(shù)。

作為一項(xiàng)新興的技術(shù),目前學(xué)術(shù)界對(duì)P2P在技術(shù)層面上的定義尚未統(tǒng)一。Keith W. Ross (Polytechnic University)和Dan Rubenstein(Columbia University)在[9]中提到了對(duì)P2P系統(tǒng)的3個(gè)基本定義:

相比中央服務(wù)器而言有明顯的自治性(Autonomy)。

利用網(wǎng)絡(luò)邊緣的資源,如存儲(chǔ)/計(jì)算能力和信息資源。

網(wǎng)絡(luò)邊緣的資源處在動(dòng)態(tài)的變化中(新的資源加入,已有的資源消失)。

自治性的要求使得P2P系統(tǒng)不再需要特定的中央管理機(jī)制,所有節(jié)點(diǎn)之間擁有對(duì)等的關(guān)系。這一方面為系統(tǒng)帶來(lái)了自組織、容錯(cuò)性好、可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn);另一方面也提出了新的問(wèn)題:如何在沒(méi)有集中管理機(jī)制的情況下實(shí)現(xiàn)系統(tǒng)的自組織和自管理?

定義2,3中分布性和動(dòng)態(tài)性的特點(diǎn)使得上述問(wèn)題的實(shí)現(xiàn)具有更大的難度。在分布式系統(tǒng)中,過(guò)多過(guò)快的信息交互可能消耗大量的網(wǎng)絡(luò)資源;而為了實(shí)時(shí)反映系統(tǒng)的變化,又要求節(jié)點(diǎn)及時(shí)獲得更新信息,這就需要在節(jié)點(diǎn)之間進(jìn)行通信。

為了解決這一對(duì)矛盾,已經(jīng)有許多P2P的框架和協(xié)議被提出來(lái)并得到了很好的應(yīng)用。

結(jié)構(gòu)化與非結(jié)構(gòu)化P2P

依照節(jié)點(diǎn)信息存儲(chǔ)與搜索方式的不同,諸多P2P協(xié)議可以分為2大類(lèi):結(jié)構(gòu)化(Structured)的與非結(jié)構(gòu)化(Unstructured)的系統(tǒng)。

非結(jié)構(gòu)化P2P系統(tǒng)

在非結(jié)構(gòu)化的系統(tǒng)中,每個(gè)節(jié)點(diǎn)存儲(chǔ)自身的信息或信息的索引(如指針和IP地址)。當(dāng)用戶(hù)需要在P2P系統(tǒng)中獲取信息時(shí),他們預(yù)先并不知道這些信息(如某個(gè) 文件)會(huì)在那個(gè)節(jié)點(diǎn)上存儲(chǔ)。因此,在非結(jié)構(gòu)化P2P系統(tǒng)中,信息搜索的算法難免帶有一定的盲目性,例如最簡(jiǎn)單的泛洪式查找(類(lèi)似于廣播)和擴(kuò)展環(huán)查找(從 最近的n個(gè)節(jié)點(diǎn)開(kāi)始,層層轉(zhuǎn)發(fā)直到找到目標(biāo)或超出了跳數(shù)的上限為止)。

一些典型的應(yīng)用采用了一些優(yōu)化的辦法。如在Gnutella中,采用了等級(jí)制的組成結(jié)構(gòu):節(jié)點(diǎn)被分成超級(jí)節(jié)點(diǎn)(Super Node)和普通節(jié)點(diǎn)。普通節(jié)點(diǎn)必須依附于超級(jí)節(jié)點(diǎn),每個(gè)超級(jí)節(jié)點(diǎn)作為一個(gè)獨(dú)立的域管理者,負(fù)責(zé)處理域內(nèi)的查詢(xún)操作。在查找的過(guò)程中,查詢(xún)首先在域內(nèi)進(jìn)行,失敗后才會(huì)擴(kuò)展到超級(jí)節(jié)點(diǎn)之間。

非結(jié)構(gòu)化系統(tǒng)的優(yōu)點(diǎn)在于實(shí)現(xiàn)結(jié)構(gòu)簡(jiǎn)單:無(wú)須中央服務(wù)器,節(jié)點(diǎn)之間完全平等,網(wǎng)絡(luò)的層次是單一的,而且節(jié)點(diǎn)之間無(wú)需維護(hù)拓?fù)湫畔ⅰ?/p>

結(jié)構(gòu)化P2P系統(tǒng)

在結(jié)構(gòu)化P2P系統(tǒng)中,每個(gè)節(jié)點(diǎn)只存儲(chǔ)特定的信息或特定信息的索引。當(dāng)用戶(hù)需要在P2P系統(tǒng)中獲取信息時(shí),他們必須知道這些信息(或索引)可能存在于那些節(jié)點(diǎn)中。由于用戶(hù)預(yù)先知道應(yīng)該搜索哪些節(jié)點(diǎn),避免了非結(jié)構(gòu)化P2P系統(tǒng)中使用的泛洪式查找,因此提高了信息搜索的效率。

但是,結(jié)構(gòu)化P2P也引入了新的問(wèn)題:

首先,既然信息是分布存儲(chǔ)的,那么如何將信息分布存儲(chǔ)在重疊網(wǎng)中的節(jié)點(diǎn)上?

其次,由于節(jié)點(diǎn)動(dòng)態(tài)的加入和離開(kāi)重疊網(wǎng),如何將拓?fù)涞淖兏畔⑼ㄖ渌?jié)點(diǎn)?

DHT的引入基本解決了上述問(wèn)題,因此自從DHT協(xié)議出現(xiàn)以后,結(jié)構(gòu)化P2P的應(yīng)用得到了快速的發(fā)展。目前已經(jīng)有很多較為成熟的DHT協(xié)議被提出并且得到了應(yīng)用。其中比較有代表性的有:緩沖陣列路由協(xié)議(CARP);一致性哈希;Chord;內(nèi)容尋址網(wǎng)絡(luò);Pastry。

DHT簡(jiǎn)介

DHT使用分布式哈希算法來(lái)解決結(jié)構(gòu)化的分布式存儲(chǔ)問(wèn)題。分布式哈希算法的核心思想是通過(guò)將存儲(chǔ)對(duì)象的特征(關(guān)鍵字)經(jīng)過(guò)哈希運(yùn)算,得到鍵值(Hash Key),對(duì)象的分布存儲(chǔ)依據(jù)鍵值來(lái)進(jìn)行。具體來(lái)講,大致有以下步驟:

對(duì)存儲(chǔ)對(duì)象的關(guān)鍵字進(jìn)行哈希運(yùn)算,得到鍵值。這樣就將所有的對(duì)象映射到了一個(gè)具體的數(shù)值范圍中。

重疊網(wǎng)中的每個(gè)節(jié)點(diǎn)負(fù)責(zé)數(shù)值范圍中的特定段落。例如,節(jié)點(diǎn)A負(fù)責(zé)存儲(chǔ)鍵值從8000到8999的對(duì)象;而節(jié)點(diǎn)B負(fù)責(zé)7000~7999的對(duì)象。這樣就將對(duì)象集合分布地存儲(chǔ)在所有的節(jié)點(diǎn)中。

節(jié)點(diǎn)可以直接存儲(chǔ)對(duì)象本身,如文件中的一個(gè)片段;也可以存儲(chǔ)對(duì)象的索引,如該對(duì)象所在節(jié)點(diǎn)的IP地址。

結(jié)構(gòu)化的分布式存儲(chǔ)問(wèn)題解決后,剩下的問(wèn)題就是用戶(hù)如何才能找到存儲(chǔ)著目標(biāo)信息的節(jié)點(diǎn)。在有著大量節(jié)點(diǎn)(如100萬(wàn)個(gè))的P2P系統(tǒng)中,任何節(jié)點(diǎn)都不可能 擁有全部的節(jié)點(diǎn)?鍵值?內(nèi)容的對(duì)應(yīng)關(guān)系;因此用戶(hù)獲得了鍵值之后,如何找到該鍵值對(duì)應(yīng)的節(jié)點(diǎn)就被稱(chēng)為DHT的路由問(wèn)題。DHT協(xié)議必須定義優(yōu)化的查找(路 由)算法來(lái)完成這一搜尋的工作。不同的DHT協(xié)議之間區(qū)別很大程度上就在于定義了不同的路由算法。

DHT的應(yīng)用非常簡(jiǎn)潔----API簡(jiǎn)單到只有一項(xiàng)輸入和一項(xiàng)輸出:

應(yīng)用層將數(shù)據(jù)對(duì)象(文件、數(shù)據(jù)塊或索引)通過(guò)哈希算法獲得鍵值,將該鍵值提交給DHT后,返回結(jié)果就是鍵值所在節(jié)點(diǎn)的IP地址。圖1(來(lái)自[9])顯示了這種應(yīng)用結(jié)構(gòu):

圖 1 DHT的應(yīng)用結(jié)構(gòu)



在這樣的支持下,可以開(kāi)發(fā)多種P2P的應(yīng)用程序,如網(wǎng)絡(luò)存儲(chǔ)與文件共享、即時(shí)消息、音頻/視頻等。圖2(來(lái)自[9])顯示了這種應(yīng)用結(jié)構(gòu):

圖 2 DHT應(yīng)用的層次



主流DHT協(xié)議

緩沖陣列路由協(xié)議(CARP,Cache Array Routing Protocol)

協(xié)議簡(jiǎn)介

CARP是由微軟公司的Vinod Valloppillil和賓西法尼亞大學(xué)的Keith W. Ross在1997年提出的。該協(xié)議可以將URL空間映射到一個(gè)僅有松散關(guān)聯(lián)關(guān)系的Web cache 服務(wù)器(在協(xié)議中稱(chēng)為“代理”,Proxy)陣列中。支持該協(xié)議的HTTP客戶(hù)端可以根據(jù)要訪問(wèn)的URL智能選擇目標(biāo)代理。該協(xié)議解決了在代理陣列內(nèi)分布存儲(chǔ)內(nèi)容的問(wèn)題,避免了內(nèi)容的重復(fù)存儲(chǔ),提高了客戶(hù)端訪問(wèn)時(shí)Web Cache命中的概率。

哈希算法

哈希使用的關(guān)鍵字有2個(gè),一個(gè)是代理的標(biāo)識(shí)符(每個(gè)代理均有唯一的標(biāo)識(shí)),另一個(gè)是URL本身。存儲(chǔ)內(nèi)容時(shí),每個(gè)代理負(fù)責(zé)緩沖哈希鍵值最大的URL。這 樣,當(dāng)緩沖代理陣列發(fā)生少量變化時(shí)(新的代理加入或舊的代理退出),原有的URL還有可能仍然被映射到原來(lái)的代理上,仍可以按照原有的方式訪問(wèn)。

路由算法

客戶(hù)端(HTTP瀏覽器)首先加載一個(gè)代理配置文件,該文件中存儲(chǔ)了代理的標(biāo)識(shí)符和IP地址等用于哈希的關(guān)鍵參數(shù)。瀏覽器在訪問(wèn)網(wǎng)頁(yè)時(shí),可以根據(jù)URL和代理標(biāo)識(shí)獲得代理的位置信息(IP地址),從而可以直接訪問(wèn)緩沖代理中的頁(yè)面。

討論

CARP的哈希過(guò)程比較簡(jiǎn)單,路由查找更是簡(jiǎn)單到至多只有一跳(O(1))。但是CARP在P2P的應(yīng)用環(huán)境中有一些致命的缺陷:

每個(gè)節(jié)點(diǎn)必須知道其它所有節(jié)點(diǎn)的信息。在大規(guī)模的重疊網(wǎng)環(huán)境中,由于可能存在大量的(數(shù)百萬(wàn))節(jié)點(diǎn),加之節(jié)點(diǎn)都是動(dòng)態(tài)加入和退出網(wǎng)絡(luò),因此這一條件幾乎不可能滿(mǎn)足。

在緩沖陣列發(fā)生較大變化時(shí)(這在P2P網(wǎng)絡(luò)中非常常見(jiàn)),原有的URL和代理之間的對(duì)應(yīng)關(guān)系可能發(fā)生改變,從而使得原有的配置文件失效。

一致性哈希(Consistent Hash)

協(xié)議簡(jiǎn)介

一致性哈希算法在1997年由麻省理工學(xué)院提出(參見(jiàn)0),設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot pot)問(wèn)題,初衷和CARP十分類(lèi)似。一致性哈希修正了CARP使用的簡(jiǎn)單哈希算法帶來(lái)的問(wèn)題,使得DHT可以在P2P環(huán)境中真正得到應(yīng)用。

哈希算法

一致性哈希提出了在動(dòng)態(tài)變化的Cache環(huán)境中,哈希算法應(yīng)該滿(mǎn)足的4個(gè)適應(yīng)條件:

平衡性(Balance)

平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去,這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿(mǎn)足這一條件。

單調(diào)性(Monotonicity)

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中,又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去,而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)。

簡(jiǎn)單的哈希算法往往不能滿(mǎn)足單調(diào)性的要求,如最簡(jiǎn)單的線(xiàn)性哈希:

x → ax + b mod (P)

在上式中,P表示全部緩沖的大小。不難看出,當(dāng)緩沖大小發(fā)生變化時(shí)(從P1到P2),原來(lái)所有的哈希結(jié)果均會(huì)發(fā)生變化,從而不滿(mǎn)足單調(diào)性的要求。

哈希結(jié)果的變化意味著當(dāng)緩沖空間發(fā)生變化時(shí),所有的映射關(guān)系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi),緩沖的變化等價(jià)于Peer加入或退出系統(tǒng),這一情況在P2P系統(tǒng)中會(huì)頻繁發(fā)生,因此會(huì)帶來(lái)極大計(jì)算和傳輸負(fù)荷。單調(diào)性就是要求哈希算法能夠避免這一情況的發(fā)生。

分散性(Spread)

在分布式環(huán)境中,終端有可能看不到所有的緩沖,而是只能看到其中的一部分。當(dāng)終端希望通過(guò)哈希過(guò)程將內(nèi)容映射到緩沖上時(shí),由于不同終端所見(jiàn)的緩沖范圍有可 能不同,從而導(dǎo)致哈希的結(jié)果不一致,最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應(yīng)該避免的,因?yàn)樗鼘?dǎo)致相同內(nèi)容被存儲(chǔ)到不 同緩沖中去,降低了系統(tǒng)存儲(chǔ)的效率。分散性的定義就是上述情況發(fā)生的嚴(yán)重程度。好的哈希算法應(yīng)能夠盡量避免不一致的情況發(fā)生,也就是盡量降低分散性。

負(fù)載(Load)

負(fù)載問(wèn)題實(shí)際上是從另一個(gè)角度看待分散性問(wèn)題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中,那么對(duì)于一個(gè)特定的緩沖區(qū)而言,也可能被不同的用戶(hù)映射為不同的內(nèi)容。與分散性一樣,這種情況也是應(yīng)當(dāng)避免的,因此好的哈希算法應(yīng)能夠盡量降低緩沖的負(fù)荷。

從表面上看,一致性哈希針對(duì)的是分布式緩沖的問(wèn)題,但是如果將緩沖看作P2P系統(tǒng)中的Peer,將映射的內(nèi)容看作各種共享的資源(數(shù)據(jù),文件,媒體流等),就會(huì)發(fā)現(xiàn)兩者實(shí)際上是在描述同一問(wèn)題。

路由算法

在一致性哈希算法中,每個(gè)節(jié)點(diǎn)(對(duì)應(yīng)P2P系統(tǒng)中的Peer)都有隨機(jī)分配的ID。在將內(nèi)容映射到節(jié)點(diǎn)時(shí),使用內(nèi)容的關(guān)鍵字和節(jié)點(diǎn)的ID進(jìn)行一致性哈希運(yùn) 算并獲得鍵值。一致性哈希要求鍵值和節(jié)點(diǎn)ID處于同一值域。最簡(jiǎn)單的鍵值和ID可以是一維的,比如從0000到9999的整數(shù)集合。

根據(jù)鍵值存儲(chǔ)內(nèi)容時(shí),內(nèi)容將被存儲(chǔ)到具有與其鍵值最接近的ID的節(jié)點(diǎn)上。例如鍵值為1001的內(nèi)容,系統(tǒng)中有ID為1000,1010,1100的節(jié)點(diǎn),該內(nèi)容將被映射到1000節(jié)點(diǎn)。

為了構(gòu)建查詢(xún)所需的路由,一致性哈希要求每個(gè)節(jié)點(diǎn)存儲(chǔ)其上行節(jié)點(diǎn)(ID值大于自身的節(jié)點(diǎn)中最小的)和下行節(jié)點(diǎn)(ID值小于自身的節(jié)點(diǎn)中最大的)的位置信息 (IP地址)。當(dāng)節(jié)點(diǎn)需要查找內(nèi)容時(shí),就可以根據(jù)內(nèi)容的鍵值決定向上行或下行節(jié)點(diǎn)發(fā)起查詢(xún)請(qǐng)求。收到查詢(xún)請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自己擁有被請(qǐng)求的目標(biāo),可以直 接向發(fā)起查詢(xún)請(qǐng)求的節(jié)點(diǎn)返回確認(rèn);如果發(fā)現(xiàn)不屬于自身的范圍,可以轉(zhuǎn)發(fā)請(qǐng)求到自己的上行/下行節(jié)點(diǎn)。

為了維護(hù)上述路由信息,在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí),相鄰的節(jié)點(diǎn)必須及時(shí)更新路由信息。這就要求節(jié)點(diǎn)不僅存儲(chǔ)直接相連的下行節(jié)點(diǎn)位置信息,還要知道一定深度 (n跳)的間接下行節(jié)點(diǎn)信息,并且動(dòng)態(tài)地維護(hù)節(jié)點(diǎn)列表。當(dāng)節(jié)點(diǎn)退出系統(tǒng)時(shí),它的上行節(jié)點(diǎn)將嘗試直接連接到最近的下行節(jié)點(diǎn),連接成功后,從新的下行節(jié)點(diǎn)獲得 下行節(jié)點(diǎn)列表并更新自身的節(jié)點(diǎn)列表。同樣的,當(dāng)新的節(jié)點(diǎn)加入到系統(tǒng)中時(shí),首先根據(jù)自身的ID找到下行節(jié)點(diǎn)并獲得下行節(jié)點(diǎn)列表,然后要求上行節(jié)點(diǎn)修改其下行 節(jié)點(diǎn)列表,這樣就恢復(fù)了路由關(guān)系。

討論

一致性哈?;窘鉀Q了在P2P環(huán)境中最為關(guān)鍵的問(wèn)題——如何在動(dòng)態(tài)的網(wǎng)絡(luò)拓?fù)渲蟹植即鎯?chǔ)和路由。每個(gè)節(jié)點(diǎn)僅需維護(hù)少量相鄰節(jié)點(diǎn)的信息,并且在節(jié)點(diǎn)加入/退出系統(tǒng)時(shí),僅有相關(guān)的少量節(jié)點(diǎn)參與到拓?fù)涞木S護(hù)中。所有這一切使得一致性哈希成為第一個(gè)實(shí)用的DHT算法。

但是一致性哈希的路由算法尚有不足之處。在查詢(xún)過(guò)程中,查詢(xún)消息要經(jīng)過(guò)O(N)步(O(N)表示與N成正比關(guān)系,N代表系統(tǒng)內(nèi)的節(jié)點(diǎn)總數(shù))才能到達(dá)被查詢(xún) 的節(jié)點(diǎn)。不難想象,當(dāng)系統(tǒng)規(guī)模非常大時(shí),節(jié)點(diǎn)數(shù)量可能超過(guò)百萬(wàn),這樣的查詢(xún)效率顯然難以滿(mǎn)足使用的需要。換個(gè)角度來(lái)看,即使用戶(hù)能夠忍受漫長(zhǎng)的時(shí)延,查詢(xún) 過(guò)程中產(chǎn)生的大量消息也會(huì)給網(wǎng)絡(luò)帶來(lái)不必要的負(fù)荷。

下文中討論的幾種DHT協(xié)議都對(duì)路由做出了優(yōu)化,提出了各自的算法。

Chord協(xié)議

Chord在2001年由麻省理工學(xué)院提出(參見(jiàn)0),其核心思想就是要解決在P2P應(yīng)用中遇到的基本問(wèn)題:如何在P2P網(wǎng)絡(luò)中找到存有特定數(shù)據(jù)的節(jié)點(diǎn)。 與前兩種協(xié)議不同,Chord專(zhuān)門(mén)為P2P應(yīng)用設(shè)計(jì),因此考慮了在P2P應(yīng)用中可能遇到的特殊問(wèn)題,這些內(nèi)容將在路由的部分進(jìn)行討論。

哈希算法

Chord使用一致性哈希作為哈希算法。在一致性哈希協(xié)議中并沒(méi)有定義具體的算法,在Chord協(xié)議中將其規(guī)定為SHA-1。

路由算法

Chord在一致性哈希的基礎(chǔ)上提供了優(yōu)化的路由算法:

在Chord中,每個(gè)節(jié)點(diǎn)同樣需要存儲(chǔ)m個(gè)其他節(jié)點(diǎn)的信息,這些信息的集合被稱(chēng)為查詢(xún)表(Finger Table)。一致性哈希中的節(jié)點(diǎn)同樣具有這樣的表格,但在Chord中,表格中的節(jié)點(diǎn)不再是直接相鄰的節(jié)點(diǎn),它們的間距(ID間隔)將成2i 的關(guān)系排列(i 表示表中的數(shù)組下標(biāo))。這樣形成的節(jié)點(diǎn)之間路由關(guān)系實(shí)際上就是折半查找算法需要的排列關(guān)系。

在查詢(xún)的過(guò)程中,查詢(xún)節(jié)點(diǎn)將請(qǐng)求發(fā)送到與鍵值最接近的節(jié)點(diǎn)上。收到查詢(xún)請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自身存儲(chǔ)了被查詢(xún)的信息,可以直接回應(yīng)查詢(xún)節(jié)點(diǎn)(這與一致性哈希 完全相同);如果被查詢(xún)的信息不在本地,就根據(jù)查詢(xún)表將請(qǐng)求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點(diǎn)上。這樣的過(guò)程一直持續(xù)到找到相應(yīng)的節(jié)點(diǎn)為止。不難看出,查詢(xún)過(guò)程實(shí) 際上就是折半查找的過(guò)程。

經(jīng)過(guò)Chord的優(yōu)化后,查詢(xún)需要的跳數(shù)由O ( N)減少到O(log(N))。這樣即使在大規(guī)模的P2P網(wǎng)絡(luò)中(例如N=100,000,000),查詢(xún)的跳數(shù)也僅為O(8),每個(gè)節(jié)點(diǎn)僅需存儲(chǔ)27個(gè)(log2100000000)其他節(jié)點(diǎn)的信息。

Chord還考慮到多個(gè)節(jié)點(diǎn)同時(shí)加入系統(tǒng)的情況并對(duì)節(jié)點(diǎn)加入/退出算法作了優(yōu)化。

討論

Chord算法本身具有如下優(yōu)點(diǎn):

負(fù)載平衡

這一優(yōu)點(diǎn)來(lái)自于一致性哈希,也就是一致性哈希中提到的平衡性。所有的節(jié)點(diǎn)以同等的概率分擔(dān)系統(tǒng)負(fù)荷,從而可以避免某些節(jié)點(diǎn)負(fù)載過(guò)大的情況。

分布性

Chord是純分布式系統(tǒng),節(jié)點(diǎn)之間完全平等并完成同樣的工作。這使得Chord具有很高的魯棒性,可以抵御DoS攻擊。

可擴(kuò)展性

Chord協(xié)議的開(kāi)銷(xiāo)隨著系統(tǒng)規(guī)模(結(jié)點(diǎn)總數(shù)N)的增加而按照O(logN)的比例增加。因此Chord可以用于大規(guī)模的系統(tǒng)。

可用性

Chord協(xié)議要求節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)的變化動(dòng)態(tài)的更新查詢(xún)表,因此能夠及時(shí)恢復(fù)路由關(guān)系,使得查詢(xún)可以可靠地進(jìn)行。

命名的靈活性

Chord并未限制查詢(xún)內(nèi)容的結(jié)構(gòu),因此應(yīng)用層可以靈活的將內(nèi)容映射到鍵值空間而不受協(xié)議的限制。

Chord在CFS系統(tǒng)中得到了應(yīng)用,具體的介紹可參見(jiàn)[8]

內(nèi)容尋址網(wǎng)絡(luò)(Content-Addressable Network,CAN)

CAN在2001年由加州大學(xué)伯克利分校提出(參見(jiàn)[3])。與Chord一樣,CAN也是DHT的一個(gè)變種。

哈希算法

CAN的哈希算法與一致性哈希有所不同。Chord中,哈希得到的鍵值總是一維的,而在CAN中,哈希的結(jié)果由d維的笛卡爾空間來(lái)表示。d是一個(gè)由系統(tǒng)規(guī)模決定的常量。

路由算法

CAN的路由查詢(xún)將在d維笛卡爾空間中進(jìn)行。

在CAN中,每個(gè)節(jié)點(diǎn)自身的ID經(jīng)由哈希后得到的d維向量。經(jīng)過(guò)這樣的映射后,整個(gè)P2P系統(tǒng)將被映射到一個(gè)d維笛卡爾空間中,每個(gè)節(jié)點(diǎn)的位置由其自身 ID決定。CAN對(duì)鄰居節(jié)點(diǎn)的定義并不要求成2i的關(guān)系排列,而是改為用在笛卡爾空間上相鄰來(lái)表示:在d維笛卡爾空間中,2個(gè)節(jié)點(diǎn)的d維坐標(biāo)中有d-1維 是相等的,剩余的一維是相鄰的節(jié)點(diǎn)稱(chēng)之為相鄰節(jié)點(diǎn)。

CAN中的節(jié)點(diǎn)僅存儲(chǔ)相鄰節(jié)點(diǎn)表。由于在d維的空間中最多有2d個(gè)相鄰的節(jié)點(diǎn),因此節(jié)點(diǎn)的相鄰節(jié)點(diǎn)表最多有2d個(gè)表項(xiàng)。

在查詢(xún)的過(guò)程中,查詢(xún)節(jié)點(diǎn)首先計(jì)算被查詢(xún)內(nèi)容的鍵值(d維向量),然后在節(jié)點(diǎn)列表中查找在笛卡爾空間中與該鍵值最為接近的相鄰節(jié)點(diǎn),找到后向該節(jié)點(diǎn)發(fā)送查 詢(xún)請(qǐng)求(這一策略被稱(chēng)為貪婪策略)。查詢(xún)請(qǐng)求中將攜帶被查詢(xún)內(nèi)容的鍵值。收到查詢(xún)請(qǐng)求的節(jié)點(diǎn)如果發(fā)現(xiàn)自身存儲(chǔ)了被查詢(xún)的信息,可以直接回應(yīng)查詢(xún)節(jié)點(diǎn)(這與 一致性哈希完全相同);如果被查詢(xún)的信息不在本地,就根據(jù)相鄰節(jié)點(diǎn)表將請(qǐng)求轉(zhuǎn)發(fā)到與鍵值最接近的節(jié)點(diǎn)上。這樣的過(guò)程一直持續(xù)到找到相應(yīng)的節(jié)點(diǎn)為止。在查詢(xún) 過(guò)程中,被查詢(xún)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的笛卡爾空間距離單調(diào)地減少。

如果查詢(xún)節(jié)點(diǎn)或轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)現(xiàn)鄰居節(jié)點(diǎn)表中無(wú)法找到可用的下一跳節(jié)點(diǎn),則采用非結(jié)構(gòu)化P2P常用的擴(kuò)展環(huán)搜索(Expanding Ring Search,使用無(wú)狀態(tài),受控的泛洪算法在重疊網(wǎng)中搜索)以找到合適的(符合貪婪策略)下一節(jié)點(diǎn)。

經(jīng)過(guò)CAN的優(yōu)化后,查詢(xún)需要的跳數(shù)由O ( N)減少到均值為(d/4)(n1/d)的隨機(jī)制,考慮到d為常數(shù),這一值可以表示為O(n1/d)或O(dn1/d)。

討論

CAN和Chord的主要區(qū)別在于路由算法不同。相比之下,在節(jié)點(diǎn)數(shù)量非常大時(shí),CAN的平均查詢(xún)跳數(shù)要比Chord增加得更快。而且CAN查詢(xún)過(guò)程中需 要的運(yùn)算量也要高于Chord。但CAN使用的d為預(yù)先設(shè)置的常量,因此并不假設(shè)系統(tǒng)節(jié)點(diǎn)數(shù)量。在節(jié)點(diǎn)總數(shù)動(dòng)態(tài)變化范圍很大的系統(tǒng)中,CAN的相鄰節(jié)點(diǎn)表 結(jié)構(gòu)保持穩(wěn)定,這在P2P的應(yīng)用中也是很重要的優(yōu)點(diǎn)。

Pastry

Pastry在2001年由位于英國(guó)劍橋的微軟研究院和萊斯(Rice)大學(xué)提出(參見(jiàn)[4])。Pastry也是DHT的一個(gè)變種。

哈希算法

Pastry使用一致性哈希作為哈希算法。哈希所得的鍵值為一維(實(shí)際上使用的是128bit的整數(shù)空間)。Pastry也沒(méi)有規(guī)定具體應(yīng)該采用何種哈希算法。

路由算法

在Pastry協(xié)議中,每個(gè)節(jié)點(diǎn)都擁有一個(gè)128bit的標(biāo)識(shí)(Node Id)。為了保證Node ID的唯一性,一般由節(jié)點(diǎn)的網(wǎng)絡(luò)標(biāo)識(shí)(如IP地址)經(jīng)過(guò)哈希得到。

Pastry中的每個(gè)節(jié)點(diǎn)擁有一個(gè)路由表R(Routing table),一個(gè)鄰居節(jié)點(diǎn)集M(Neighborhood Set)和一個(gè)葉子節(jié)點(diǎn)集合L(Leaf set),它們一起構(gòu)成了節(jié)點(diǎn)的狀態(tài)表。

路由表R共有l(wèi)ogBN(B = 2b為系統(tǒng)參數(shù),典型值為16,N表示系統(tǒng)的節(jié)點(diǎn)總數(shù))行,每行包括B-1個(gè)表項(xiàng),每個(gè)表項(xiàng)記錄了一個(gè)鄰居節(jié)點(diǎn)的信息(節(jié)點(diǎn)標(biāo)識(shí)、IP地址、 當(dāng)前狀態(tài)等)。這樣就形成了擁有(B-1)logBN個(gè)條目的二維表格。路由表第n行的表項(xiàng)所記錄的鄰居節(jié)點(diǎn)的Node ID前n個(gè)數(shù)位和當(dāng)前節(jié)點(diǎn)的前n個(gè)數(shù)位相同,而第n+1個(gè)數(shù)位則分別取從0到B-1的值(除了與當(dāng)前節(jié)點(diǎn)第n+1數(shù)位的值)。這樣形成的路由表很類(lèi)似IP 路由中最長(zhǎng)掩碼匹配的算法。參數(shù)b(或B)大小非常關(guān)鍵:B過(guò)大則節(jié)點(diǎn)需要維護(hù)很大的路由表,可能超出節(jié)點(diǎn)的負(fù)載能力,但路由表大些可以存儲(chǔ)更多的鄰居節(jié) 點(diǎn),在轉(zhuǎn)發(fā)時(shí)更為精確。平均每次路由查找需要的跳數(shù)在Pastry中計(jì)算的結(jié)果是logBN,因此B的選擇反映了路由表大小和路由效率之間的折衷。

葉子節(jié)點(diǎn)集合L中存放的是在鍵值空間中與當(dāng)前節(jié)點(diǎn)距離最近的|L|個(gè)節(jié)點(diǎn)的信息,其中一半節(jié)點(diǎn)標(biāo)識(shí)大于當(dāng)前節(jié)點(diǎn),另一半節(jié)點(diǎn)標(biāo)識(shí)小于當(dāng)前節(jié)點(diǎn)。|L|的典型值為2b或者2*2b。

鄰居節(jié)點(diǎn)集合M中存放的是在真實(shí)網(wǎng)絡(luò)中與當(dāng)前節(jié)點(diǎn)“距離”最近的|M|個(gè)節(jié)點(diǎn)的信息。“距離”的定義在Pastry中非常類(lèi)似IP路由協(xié)議中對(duì)距離的定 義,也就是考慮到轉(zhuǎn)發(fā)跳數(shù)、傳輸路徑帶寬、QoS等綜合因素后所得的轉(zhuǎn)發(fā)開(kāi)銷(xiāo)(可以參見(jiàn)OSPF等路由協(xié)議)。Pastry并未提供距離信息的獲取方法, 而是假設(shè)應(yīng)用層可以通過(guò)某種手段(人工配制或自動(dòng)協(xié)商)得到信息并配置鄰居節(jié)點(diǎn)集合。|M|的典型值為2b或者2*2b。

圖 3給出了一個(gè)Pastry節(jié)點(diǎn)狀態(tài)表的例子,該圖來(lái)源于[4]。

在節(jié)點(diǎn)狀態(tài)表中,節(jié)點(diǎn)本身的ID為10233102。葉子集合中有8項(xiàng),每一項(xiàng)都代表一個(gè)當(dāng)前節(jié)點(diǎn)已知的其他節(jié)點(diǎn)的信息。路由表共有4*8項(xiàng),可以看出由上至下節(jié)點(diǎn)ID重合的位數(shù)(前綴)不斷增加。鄰居集合中的節(jié)點(diǎn)ID由于來(lái)源于應(yīng)用層,一般沒(méi)有規(guī)律性可循。

Pastry的路由過(guò)程如下:

首先,路由查詢(xún)消息中將攜帶被查詢(xún)對(duì)象ID(Object Id),又稱(chēng)消息鍵值。當(dāng)收到路由消息時(shí),節(jié)點(diǎn)首先檢查消息鍵值是否落在葉子節(jié)點(diǎn)集合的范圍內(nèi)。如果是,則直接把消息轉(zhuǎn)發(fā)給葉子節(jié)點(diǎn)集合中節(jié)點(diǎn)標(biāo)識(shí)和消息 鍵值最接近的節(jié)點(diǎn);否則就從路由表中根據(jù)最長(zhǎng)前綴優(yōu)先的原則選擇一個(gè)節(jié)點(diǎn)作為路由目標(biāo),轉(zhuǎn)發(fā)路由消息。如果不存在這樣的節(jié)點(diǎn),當(dāng)前節(jié)點(diǎn)將會(huì)從其維護(hù)的所有 鄰居節(jié)點(diǎn)集合(包括路由表葉子集合及鄰居集合中的節(jié)點(diǎn))中選擇一個(gè)距離消息鍵值最近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)目標(biāo)。

從上述過(guò)程中可以看出,每一步路由和上一步相比都更靠近目標(biāo)節(jié)點(diǎn),因此這個(gè)過(guò)程是收斂的。如果路由表不為空,每步路由至少能夠增加一個(gè)前綴匹配數(shù)位,因此在路由表始終有效時(shí),路由的步數(shù)至多為logBN。

討論

Pastry的路由利用了成熟的最大掩碼匹配算法,因此實(shí)現(xiàn)時(shí)可以利用很多現(xiàn)成的軟件算法和硬件框架,可以獲得很好的效率。

與Chord和CAN相比,Pastry引入了葉子節(jié)點(diǎn)和鄰居節(jié)點(diǎn)集合的概念。在應(yīng)用層能夠及時(shí)準(zhǔn)確地獲得這兩個(gè)集合的節(jié)點(diǎn)信息時(shí),可以大大加快路由查找的速度,同時(shí)降低因路由引起的網(wǎng)絡(luò)傳輸開(kāi)銷(xiāo);不過(guò)在動(dòng)態(tài)變化的P2P網(wǎng)絡(luò)中如何理想地做到這一點(diǎn)的確有很大的難度。

Pastry的典型應(yīng)用包括PAST(參見(jiàn)[5][6])和SCRIBE(參見(jiàn)[7])。

趨勢(shì)分析

目前DHT算法的發(fā)展方向非常多,不斷有新的改進(jìn)算法被提出來(lái)。就筆者目前了解到的信息而言,至少有以下一些方向:

接近性(Proximity)

文中提到的DHT算法中,除了Pasrty以外,均未考慮重疊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與真實(shí)的IP網(wǎng)絡(luò)之間的重合關(guān)系。節(jié)點(diǎn)之間進(jìn)行對(duì)等通信時(shí),不會(huì)考慮優(yōu)先選取距離自己最近的節(jié)點(diǎn)。這樣就使得最終形成的重疊網(wǎng)結(jié)構(gòu)混亂,效率低下。因此如何讓節(jié)點(diǎn)獲得并利用接近性信息就非常重要。

結(jié)構(gòu)化

目前基于DHT的應(yīng)用尚未大規(guī)模展開(kāi),很多工程上的細(xì)節(jié)問(wèn)題尚待解決。例如:目前有很多種類(lèi)的P2P應(yīng)用,如文件存儲(chǔ)和共享、電子郵件、流媒體等。這些應(yīng) 用在處理P2P路由算法、拓?fù)渚S護(hù)和信息檢索上使用的方法均有很大差別,導(dǎo)致即使是同類(lèi)的應(yīng)用也無(wú)法實(shí)現(xiàn)互通。如何為各種P2P的應(yīng)用抽象出一個(gè)通用的層 次,也是目前研究的熱點(diǎn)問(wèn)題之一。

信息查詢(xún)

基于分布式哈希表的查詢(xún)是一種單關(guān)鍵字的精確匹配,盡管相對(duì)于非結(jié)構(gòu)化系統(tǒng)它使得系統(tǒng)資源可被確定性地查詢(xún)到,但它也極大地限制了查詢(xún)的應(yīng)用范圍。目前有許多改進(jìn)的結(jié)構(gòu)化查詢(xún)算法已經(jīng)被提出來(lái)。

參考文獻(xiàn)

David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin, Rina Panigrahy "Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web". In Proceedings of the 29th Annual ACM Sym-posium on Theory of Computing (El Paso, TX, May 1997), pp. 654-663.

Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan_ "Chord: A Scalable Peertopeer Lookup Service for Internet Applications" SIGCOMM‘01, August 2731, 2001, San Diego, California, USA.

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker "A Scalable Content-Addressable Network" SIGCOMM‘01, August 27-31, 2001, San Diego, California, USA..

Antony Rowstron1 and Peter Druschel "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems" Appears in Proc. of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001). Heidelberg, Germany, November 2001.

P. Druschel and A. Rowstron. PAST: A large-scale, persistent peer-to-peer storage utility. In Proc. HotOS VIII, Schloss Elmau, Germany, May 2001.

A. Rowstron and P. Druschel. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In Proc. ACM SOSP‘01, Banff, Canada, Oct. 2001.

A. Rowstron, A.-M. Kermarrec, P. Druschel, and M. Castro. Scribe: The design of a large-scale event notification infrastructure. Submitted for publication. June 2001. http://www.research.microsoft.com/ antr/SCRIBE/.

F. Dabek, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica. Wide-area cooperative storage with CFS. In Proc. ACM SOSP‘01, Banff, Canada, Oct. 2001.

Keith W. Ross, Dan Rubenstein, "P2P Systems"

寧寧,“對(duì)等網(wǎng)絡(luò)組通信機(jī)制的位置感知技術(shù)研究Research on Location-Aware Tech-nology in Peer-to-Peer Group Com-munication Mechanism”,申請(qǐng)清華大學(xué)工學(xué)碩士學(xué)位論文,May.2005.

李祖鵬,黃建華,唐輝,“基于P2P計(jì)算模式的自組織網(wǎng)絡(luò)路由模型”,軟件學(xué)報(bào),1000-9825/2005/16(05)0916

胡進(jìn)鋒,鄭緯民(清華大學(xué)計(jì)算機(jī)系高性能計(jì)算研究所,北京,100084),“p2p系統(tǒng)結(jié)點(diǎn)信息收集算法 Node Collection Protocol in P2P Systems”

鄒福泰,馬范援(上海交通大學(xué)計(jì)算機(jī)科學(xué)與工程系),“基于分布式哈希表的對(duì)等系統(tǒng)關(guān)鍵技術(shù)研究RESEARCH ON THE KEY TECHNIQUE OF PEER-TO-PEER SYSTEMS BASED ON DISTRIBUTED HASH TABLE”,申請(qǐng)上海交通大學(xué)博士學(xué)位論文,二零零四年十一月

作者:陳嶺

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,所有內(nèi)容均由用戶(hù)發(fā)布,不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)點(diǎn)擊一鍵舉報(bào)。
    轉(zhuǎn)藏 分享 獻(xiàn)花(0

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶(hù) 評(píng)論公約

    類(lèi)似文章 更多