DHT網(wǎng)絡(luò)的搜索技術(shù)解析課件

DHT網(wǎng)絡(luò)的搜索技術(shù)哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心

姚亮DHT網(wǎng)絡(luò)的搜索技術(shù)哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心

1P2P網(wǎng)絡(luò)的分類Hash函數(shù)概述DHT原理幾種典型的DHT網(wǎng)絡(luò)總結(jié)主要內(nèi)容主要內(nèi)容21.P2P網(wǎng)絡(luò)分類非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)涫侨我獾膬?nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)錈o(wú)關(guān)結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是有規(guī)律的每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)內(nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)湎嚓P(guān)內(nèi)容的存儲(chǔ)位置與節(jié)點(diǎn)標(biāo)識(shí)之間存在著映射關(guān)系1.P2P網(wǎng)絡(luò)分類非結(jié)構(gòu)化P2P3P2P網(wǎng)絡(luò)分類在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，內(nèi)容一般使用內(nèi)容索引來(lái)表示,內(nèi)容索引包括key和value兩部分,其中key是內(nèi)容的關(guān)鍵字,value是存放內(nèi)容的實(shí)際位置,因此內(nèi)容索引也表示為<key,value>對(duì)內(nèi)容索引<夜宴,/yeyan.avi>表示電影夜宴可以從/yeyan.avi處獲得P2P網(wǎng)絡(luò)分類在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，內(nèi)容一般使用內(nèi)容索引來(lái)表42.Hash函數(shù)概述Hash函數(shù)可以根據(jù)給定的一段任意長(zhǎng)的消息計(jì)算出一個(gè)固定長(zhǎng)度的比特串，通常稱為消息摘要（MD：MessageDigest），一般用于消息的完整性檢驗(yàn)。Hash函數(shù)有以下特性：給定P，易于計(jì)算出MD（P）只給出MD（P），幾乎無(wú)法找出P無(wú)法找到兩條具有同樣消息摘要的不同消息Hash函數(shù)MD5：消息摘要長(zhǎng)度固定為128比特SHA-1：消息摘要長(zhǎng)度固定為160比特2.Hash函數(shù)概述Hash函數(shù)可以根據(jù)給定的一段任意長(zhǎng)的消5Hash函數(shù)應(yīng)用于P2P的特性唯一性：不同的輸入明文，對(duì)應(yīng)著不同的輸出摘要將節(jié)點(diǎn)IP地址的摘要作為節(jié)點(diǎn)ID，保證了節(jié)點(diǎn)ID在P2P環(huán)境下的唯一性SHA-1(“”)=24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1(“”)=e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27Hash函數(shù)應(yīng)用于P2P的特性唯一性：不同的輸入明文，對(duì)應(yīng)著63.DHT原理(1)將內(nèi)容索引抽象為<K,V>對(duì)K是內(nèi)容關(guān)鍵字的Hash摘要K=Hash(key)V是存放內(nèi)容的實(shí)際位置，例如節(jié)點(diǎn)IP地址等所有的<K,V>對(duì)組成一張大的Hash表，因此該表存儲(chǔ)了所有內(nèi)容的信息每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)，把Hash表分割成許多小塊，按特定規(guī)則(即K和節(jié)點(diǎn)ID之間的映射關(guān)系)分布到網(wǎng)絡(luò)中去，節(jié)點(diǎn)按這個(gè)規(guī)則在應(yīng)用層上形成一個(gè)結(jié)構(gòu)化的重疊網(wǎng)絡(luò)給定查詢內(nèi)容的K值，可以根據(jù)K和節(jié)點(diǎn)ID之間的映射關(guān)系在重疊網(wǎng)絡(luò)上找到相應(yīng)的V值，從而獲得存儲(chǔ)文件的節(jié)點(diǎn)IP地址3.DHT原理(1)將內(nèi)容索引抽象為<K,V>對(duì)7DHT原理(2)內(nèi)容內(nèi)容關(guān)鍵字key內(nèi)容存儲(chǔ)位置等信息value內(nèi)容索引K=Hash(key)提取kvHash表電影夜宴電影、夜宴/yeyan.avi內(nèi)容索引K=hash(電影,夜宴)V=/yeyan.aviDHT原理(2)內(nèi)容內(nèi)容關(guān)鍵字key內(nèi)容存儲(chǔ)位置等信息內(nèi)容索8DHT原理(3)kva.Hash表b.分布式Hash表規(guī)則?KVN1N48N16N32N8KVKVKVKVChord、CAN、Tapestry、Pastry在許多情況下,節(jié)點(diǎn)ID為節(jié)點(diǎn)IP地址的Hash摘要DHT原理(3)kva.Hash表b.分布式Hash表9DHT原理(4)插入

(K1,V1)KVKVKVKVKVKVKVKVKVKVKV(K1,V1)查詢(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3C索引發(fā)布和內(nèi)容定位DHT原理(4)插入

(K1,V1)KVKVKV10DHT原理(5)定位(Locating)節(jié)點(diǎn)ID和其存放的<K,V>對(duì)中的K存在著映射關(guān)系，因此可以由K獲得存放該<K,V>對(duì)的節(jié)點(diǎn)ID路由(Routing)在重疊網(wǎng)上根據(jù)節(jié)點(diǎn)ID進(jìn)行路由，將查詢消息最終發(fā)送到目的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)需要有到其鄰近節(jié)點(diǎn)的路由信息，包括節(jié)點(diǎn)ID、IP等網(wǎng)絡(luò)拓?fù)渫負(fù)浣Y(jié)構(gòu)由節(jié)點(diǎn)ID和其存放的<K,V>對(duì)中的K之間的映射關(guān)系決定拓?fù)鋭?dòng)態(tài)變化，需要處理節(jié)點(diǎn)加入/退出/失效的情況在重疊網(wǎng)上節(jié)點(diǎn)始終由節(jié)點(diǎn)ID標(biāo)識(shí)，并且根據(jù)ID進(jìn)行路由DHT原理(5)定位(Locating)在重疊網(wǎng)上節(jié)點(diǎn)始終由114.Chord：概述Berkeley和MIT共同提出采用環(huán)形拓?fù)?Chord環(huán))應(yīng)用程序接口Insert(K,V)將<K,V>對(duì)存放到節(jié)點(diǎn)ID為Successor(K)上Lookup(K)根據(jù)K查詢相應(yīng)的VUpdate(K,new_V)根據(jù)K更新相應(yīng)的VJoin(NID)節(jié)點(diǎn)加入Leave()節(jié)點(diǎn)主動(dòng)退出4.Chord：概述Berkeley和MIT共同提出12Chord：Hash表分布規(guī)則Hash算法SHA-1Hash節(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)ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6Chord：Hash表分布規(guī)則Hash算法SHA-1ID=h13Chord：簡(jiǎn)單查詢過(guò)程每個(gè)節(jié)點(diǎn)僅維護(hù)其后繼節(jié)點(diǎn)ID、IP地址等信息查詢消息通過(guò)后繼節(jié)點(diǎn)指針在圓環(huán)上傳遞直到查詢消息中包含的K落在某節(jié)點(diǎn)ID和它的后繼節(jié)點(diǎn)ID之間速度太慢O(N)，N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6Chord：簡(jiǎn)單查詢過(guò)程每個(gè)節(jié)點(diǎn)僅維護(hù)其后繼節(jié)點(diǎn)ID、IP地14Chord：指針表N56指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42節(jié)點(diǎn)S的第i個(gè)指針successor[n+2^(i-1)],1≤i≤m

Chord：指針表N56指針表N8+1N8+2N8+4N8+15Chord：基于指針表的擴(kuò)展查找過(guò)程指針表中有O(logN)個(gè)節(jié)點(diǎn)查詢經(jīng)過(guò)大約O(logN)跳N56K54指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42Lookup(K54)指針表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14Chord：基于指針表的擴(kuò)展查找過(guò)程指針表中有O(log16Chord：網(wǎng)絡(luò)波動(dòng)(Churn)Churn由節(jié)點(diǎn)的加入、退出或者失效所引起每個(gè)節(jié)點(diǎn)都周期性地運(yùn)行探測(cè)協(xié)議來(lái)檢測(cè)新加入節(jié)點(diǎn)或退出/失效節(jié)點(diǎn)，從而更新自己的指針表和指向后繼節(jié)點(diǎn)的指針Chord：網(wǎng)絡(luò)波動(dòng)(Churn)Churn由節(jié)點(diǎn)的加入、退17Chord：節(jié)點(diǎn)加入新節(jié)點(diǎn)N事先知道某個(gè)或者某些結(jié)點(diǎn)，并且通過(guò)這些節(jié)點(diǎn)初始化自己的指針表，也就是說(shuō)，新節(jié)點(diǎn)N將要求已知的系統(tǒng)中某節(jié)點(diǎn)為它查找指針表中的各個(gè)表項(xiàng)在其它節(jié)點(diǎn)運(yùn)行探測(cè)協(xié)議后，新節(jié)點(diǎn)N將被反映到相關(guān)節(jié)點(diǎn)的指針表和后繼節(jié)點(diǎn)指針中新結(jié)點(diǎn)N的第一個(gè)后繼結(jié)點(diǎn)將其維護(hù)的小于N節(jié)點(diǎn)的ID的所有K交給該節(jié)點(diǎn)維護(hù)；Chord：節(jié)點(diǎn)加入新節(jié)點(diǎn)N事先知道某個(gè)或者某些結(jié)點(diǎn)，并且通18Chord：節(jié)點(diǎn)退出/失效當(dāng)Chord中某個(gè)結(jié)點(diǎn)M退出/失效時(shí)，所有在指針表中包含該結(jié)點(diǎn)的結(jié)點(diǎn)將相應(yīng)指針指向大于M結(jié)點(diǎn)ID的第一個(gè)有效結(jié)點(diǎn)即節(jié)點(diǎn)M的后繼節(jié)點(diǎn)為了保證節(jié)點(diǎn)M的退出/失效不影響系統(tǒng)中正在進(jìn)行的查詢過(guò)程，每個(gè)Chord節(jié)點(diǎn)都維護(hù)一張包括r個(gè)最近后繼節(jié)點(diǎn)的后繼列表。如果某個(gè)節(jié)點(diǎn)注意到它的后繼節(jié)點(diǎn)失效了，它就用其后繼列表中第一個(gè)正常節(jié)點(diǎn)替換失效節(jié)點(diǎn)Chord：節(jié)點(diǎn)退出/失效當(dāng)Chord中某個(gè)結(jié)點(diǎn)M退出/失效19Chord：拓?fù)涫鋯栴}O(LogN)邏輯跳數(shù)，但是每一邏輯跳可能跨越多個(gè)自治域，甚至是多個(gè)國(guó)家的網(wǎng)絡(luò)重疊網(wǎng)絡(luò)與物理網(wǎng)絡(luò)脫節(jié)實(shí)際的尋路時(shí)延較大Chord：拓?fù)涫鋯栴}O(LogN)邏輯跳數(shù)，但是每一邏輯20Chord：總結(jié)算法簡(jiǎn)單可擴(kuò)展：查詢過(guò)程的通信開銷和節(jié)點(diǎn)維護(hù)的狀態(tài)隨著系統(tǒng)總節(jié)點(diǎn)數(shù)增加成對(duì)數(shù)關(guān)系(O(logN)數(shù)量級(jí))存在拓?fù)涫鋯栴}Chord：總結(jié)算法簡(jiǎn)單21Pastry：概述英國(guó)劍橋Microsoft研究院和Rice大學(xué)共同提出考慮網(wǎng)絡(luò)的本地性,解決物理網(wǎng)絡(luò)和邏輯網(wǎng)絡(luò)的拓?fù)涫涞膯栴}基于應(yīng)用層定義的鄰近性度量,例如IP路由跳數(shù)、地理距離、往返延時(shí)等節(jié)點(diǎn)ID分布采用環(huán)形結(jié)構(gòu)Pastry：概述英國(guó)劍橋Microsoft研究院和Rice22Pastry：Hash表分布規(guī)則Hash算法SHA-1Hash節(jié)點(diǎn)IP地址－>m位節(jié)點(diǎn)ID(表示為NID)Hash內(nèi)容關(guān)鍵字－>m位K(表示為KID)NID和KID是以2b為基的數(shù),共有m/b個(gè)數(shù)位b是一個(gè)配置參數(shù),一般為4節(jié)點(diǎn)按ID從小到大順序排列在一個(gè)邏輯環(huán)上<K,V>存儲(chǔ)在NID與KID數(shù)值最接近的節(jié)點(diǎn)上N0002N0201N0322N1331N1113N2120N2222N3001N3033N3200m=8K1320K1201K0220K2120K31222m-1 0b=2Pastry：Hash表分布規(guī)則Hash算法SHA-1N023Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(1)路由表R路由表包括log2bN(m/b)行，每行包括2b-1個(gè)表項(xiàng)路由表第n行與節(jié)點(diǎn)ID的前n個(gè)數(shù)位相同，但是第n+1個(gè)數(shù)位不同，也稱為n數(shù)位前綴相同路由表中的每項(xiàng)包含節(jié)點(diǎn)ID，IP地址等根據(jù)鄰近性度量選擇距離本節(jié)點(diǎn)近的節(jié)點(diǎn)鄰居節(jié)點(diǎn)集M鄰居節(jié)點(diǎn)集包含|M|個(gè)在鄰近性度量上最接近于本節(jié)點(diǎn)的節(jié)點(diǎn)，|M|為2b或者2X2b,鄰近性度量指的是物理上相鄰節(jié)點(diǎn)鄰居節(jié)點(diǎn)集通常不用于路由查詢消息，而是用來(lái)維護(hù)本地性葉子節(jié)點(diǎn)集L葉子節(jié)點(diǎn)集包含|L|個(gè)節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)，也就是邏輯地址上的相鄰節(jié)點(diǎn),其中|L|/2個(gè)節(jié)點(diǎn)的ID大于本節(jié)點(diǎn)，|L|/2個(gè)ID小于本節(jié)點(diǎn)，|L|為2b或者2X2b

Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(1)路由表R24Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(2)NodeID10233102LeafsetRoutingTableNeighborhoodset0022121021223012033120320311301233122302031302102221003120310132102103233023310222302102002301021130210230322102310001023212110233001102331201023323210213021022102002301130123331301233022121022230120331203203332133211023303310233021102331201023312210233001102330001023323010233232<SMALLERLARGER>節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)b=2，因此節(jié)點(diǎn)ID的基數(shù)為4(16bits)m/b行依據(jù)鄰近性度量最接近本節(jié)點(diǎn)的節(jié)點(diǎn)每行2b-1個(gè)表項(xiàng)第n行的前n個(gè)數(shù)位與本節(jié)點(diǎn)相同[相同前綴下一數(shù)位其它]當(dāng)前節(jié)點(diǎn)的第n個(gè)數(shù)位沒有合適節(jié)點(diǎn)的表項(xiàng)為空b=2m=16Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(2)NodeID1023325Pastry：查詢過(guò)程當(dāng)一個(gè)K為D的查詢消息到達(dá)節(jié)點(diǎn)A節(jié)點(diǎn)A首先看D是否在當(dāng)前節(jié)點(diǎn)的葉子節(jié)點(diǎn)集中，如果是，則查詢消息直接被轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，也就是葉子節(jié)點(diǎn)集中節(jié)點(diǎn)ID與D數(shù)值最接近的那個(gè)節(jié)點(diǎn)(有可能就是當(dāng)前節(jié)點(diǎn))，否則進(jìn)行下一步在路由表中查找與D具有更長(zhǎng)相同前綴的表項(xiàng)，如果該表項(xiàng)不為空，則將查詢消息直接轉(zhuǎn)發(fā)到該節(jié)點(diǎn)，否則進(jìn)行下一步例如路由D=0629的查詢消息5324→

0748→

0605→

0620→

0629如果不存在這樣的節(jié)點(diǎn),當(dāng)前節(jié)點(diǎn)將會(huì)從其維護(hù)的所有鄰居節(jié)點(diǎn)集合中選擇一個(gè)距離該鍵值最接近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)目標(biāo)路由查詢消息的邏輯跳數(shù)：O(log2bN)

Pastry：查詢過(guò)程當(dāng)一個(gè)K為D的查詢消息到達(dá)節(jié)點(diǎn)A路由查26Pastry：節(jié)點(diǎn)狀態(tài)表和查詢節(jié)點(diǎn)路由表R中的每行與本節(jié)點(diǎn)具有相同的n數(shù)位長(zhǎng)度前綴，但是下一個(gè)數(shù)位不同例如，對(duì)于節(jié)點(diǎn)N0201：

N-:N1???,N2???,N3???

N0:N00??,N01??,N03??

N02:N021?,N022?,N023?

N020:N0200,N0202,N0203當(dāng)有多個(gè)節(jié)點(diǎn)時(shí)，根據(jù)鄰近性度量選擇最近的節(jié)點(diǎn)維持了較好的本地性N0002N0201N2001N1113N2120N2222N3001N3033N3200m=82m-1 0b=2N0122N0212N0221N0233RoutingtableK2120lookup(K2120)N0322Pastry：節(jié)點(diǎn)狀態(tài)表和查詢節(jié)點(diǎn)路由表R中的每行與本節(jié)點(diǎn)具272.2.4Pastry：節(jié)點(diǎn)加入(1)初始化狀態(tài)表新節(jié)點(diǎn)開始時(shí)知道一個(gè)根據(jù)鄰近性度量接近自己的節(jié)點(diǎn)A節(jié)點(diǎn)A可以通過(guò)使用擴(kuò)展環(huán)IP組播等機(jī)制自動(dòng)定位，或者由系統(tǒng)管理員通過(guò)其它手段獲得新節(jié)點(diǎn)通過(guò)運(yùn)行SHA-1算法計(jì)算自己的IP地址的摘要得到節(jié)點(diǎn)ID為X節(jié)點(diǎn)X向節(jié)點(diǎn)A發(fā)送join消息，Pastry將該消息路由到節(jié)點(diǎn)ID在數(shù)值上最接近X的節(jié)點(diǎn)Z接收到j(luò)oin消息的節(jié)點(diǎn)，包括A、Z，以及A到Z路徑上所有的節(jié)點(diǎn)將發(fā)送它們的狀態(tài)表給X，X檢查這些信息，然后節(jié)點(diǎn)根據(jù)下面的過(guò)程初始化狀態(tài)表:由于A與X在鄰近性度量上接近,所以使用A的鄰居節(jié)點(diǎn)集來(lái)初始化X的鄰居節(jié)點(diǎn)集由于Z的節(jié)點(diǎn)ID與X最相近,因此使用Z的葉子節(jié)點(diǎn)集來(lái)初始化X的葉子節(jié)點(diǎn)集X將join消息經(jīng)過(guò)的第i個(gè)節(jié)點(diǎn)的路由表的第i行作為自己路由表的第i行Join消息經(jīng)過(guò)的第i個(gè)節(jié)點(diǎn)與X的前i個(gè)數(shù)位相同向其它相關(guān)節(jié)點(diǎn)通告自己的到來(lái)新節(jié)點(diǎn)向鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集和路由表中的每個(gè)節(jié)點(diǎn)發(fā)送自己的狀態(tài)，以更新這些節(jié)點(diǎn)的狀態(tài)表2.2.4Pastry：節(jié)點(diǎn)加入(1)初始化狀態(tài)表282.2.4Pastry：節(jié)點(diǎn)加入(2)X0629節(jié)點(diǎn)加入Join消息A5324X知道A(A與X鄰近)C0605Z0620B0748路由消息到節(jié)點(diǎn)ID在數(shù)值上最接近X的節(jié)點(diǎn)A鄰居節(jié)點(diǎn)集Z的葉子節(jié)點(diǎn)集A0

—????B1

—0???C2

—06??Z4

—062?0629’sroutingtable2.2.4Pastry：節(jié)點(diǎn)加入(2)X節(jié)點(diǎn)加入Join消292.2.4Pastry：節(jié)點(diǎn)退出/失效葉子節(jié)點(diǎn)集L中的節(jié)點(diǎn)退出機(jī)制：本地節(jié)點(diǎn)要求當(dāng)前葉子節(jié)點(diǎn)集合L中的ID最大的節(jié)點(diǎn)或ID最小的節(jié)點(diǎn)把它的葉子節(jié)點(diǎn)集合L1發(fā)送過(guò)來(lái),如果L1中存在L中沒有的節(jié)點(diǎn),則從中選擇一個(gè)替代失效節(jié)點(diǎn).除非|L|/2個(gè)節(jié)點(diǎn)同時(shí)失效，否恢復(fù)過(guò)程始終是有效的失效檢測(cè)：和葉子節(jié)點(diǎn)集中的節(jié)點(diǎn)周期性交互存活消息路由表R中的節(jié)點(diǎn)退出機(jī)制：如果失效節(jié)點(diǎn)對(duì)應(yīng)的表項(xiàng)為Rdl(第l行第d列)，則聯(lián)系同一行中的Ril,id所指向的存活節(jié)點(diǎn)并且獲取該節(jié)點(diǎn)的Rdl表項(xiàng)，如果l行中沒有存活節(jié)點(diǎn)，則從下一行選擇一個(gè)節(jié)點(diǎn)失效檢測(cè)：和路由表中的節(jié)點(diǎn)聯(lián)系(例如發(fā)送查詢消息)如果無(wú)反應(yīng)則檢測(cè)到節(jié)點(diǎn)失效2.2.4Pastry：節(jié)點(diǎn)退出/失效葉子節(jié)點(diǎn)集L中的節(jié)點(diǎn)30Pastry：總結(jié)邏輯網(wǎng)絡(luò)路由跳數(shù)O(log2bN)

路由表開銷log2bN*(2b-1)路由本地性：狀態(tài)表(路由表、鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集)中的表項(xiàng)選擇在鄰近性度量上與本節(jié)點(diǎn)相近的節(jié)點(diǎn)穩(wěn)健性：只有在|L|/2個(gè)葉子節(jié)點(diǎn)完全失效時(shí)才會(huì)路由失敗Pastry：總結(jié)邏輯網(wǎng)絡(luò)路由跳數(shù)O(log2bN)31基于DHT的結(jié)構(gòu)化P2P比較ChordPastry拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)ID分布在單向環(huán)形空間節(jié)點(diǎn)ID分布在單向環(huán)形空間，并且表示為以2b為基的數(shù)<K,V>存儲(chǔ)儲(chǔ)存在K的后繼節(jié)點(diǎn)即節(jié)點(diǎn)ID大于K的第一個(gè)節(jié)點(diǎn)上存儲(chǔ)在節(jié)點(diǎn)ID與K最接近的節(jié)點(diǎn)上路由查詢消息通過(guò)后繼節(jié)點(diǎn)指針或者指針表找到K的后繼節(jié)點(diǎn)比較K和節(jié)點(diǎn)ID的前綴，下一跳節(jié)點(diǎn)的ID具有更長(zhǎng)的前綴或者在數(shù)值上更接近K節(jié)點(diǎn)維護(hù)狀態(tài)后繼節(jié)點(diǎn)指針或者指針表：O(logN)葉子節(jié)點(diǎn)集、鄰居節(jié)點(diǎn)集：2b或者2*2b路由表：log2bN*(2b-1)路由性能O(logN)O(loglog2bN)穩(wěn)健性維護(hù)r個(gè)最近的后繼節(jié)點(diǎn)只有在|L|/2個(gè)葉子節(jié)點(diǎn)完全失效時(shí)才會(huì)路由失敗路由本地性狀態(tài)表(路由表、鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集)中表項(xiàng)選擇在鄰近性度量上與本節(jié)點(diǎn)相近的節(jié)點(diǎn)基于DHT的結(jié)構(gòu)化P2P比較ChordPastry拓?fù)浣Y(jié)構(gòu)節(jié)325.總結(jié)

今天給大家介紹了結(jié)構(gòu)化p2p網(wǎng)絡(luò)中的幾種搜索技術(shù),對(duì)比較了他們的性能，其實(shí)本來(lái)想給大家介紹BiTtorrent的DHT算法---Kademlia協(xié)議原理，但目前有三個(gè)關(guān)鍵問題我還沒有搞懂，目前還在研究中，再有就是它是一種改進(jìn)了的DHT技術(shù)，所以一定要先介紹DHT，等搞明白了再和大家一起探討，最后謝謝大家！5.總結(jié)

今天給大家介紹了結(jié)構(gòu)化p2p網(wǎng)絡(luò)中的幾種搜索技術(shù),33P2P重疊網(wǎng)P2P重疊網(wǎng)絡(luò)構(gòu)筑在已有的Internet基礎(chǔ)設(shè)施網(wǎng)絡(luò)之上，也稱為應(yīng)用層網(wǎng)絡(luò)

返回InternetP2P網(wǎng)絡(luò)

(overlayNetwork)P2P重疊網(wǎng)P2P重疊網(wǎng)絡(luò)構(gòu)筑在已有的Internet基礎(chǔ)設(shè)34DHT網(wǎng)絡(luò)的搜索技術(shù)哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心

姚亮DHT網(wǎng)絡(luò)的搜索技術(shù)哈爾濱理工大學(xué)網(wǎng)絡(luò)信息中心

35P2P網(wǎng)絡(luò)的分類Hash函數(shù)概述DHT原理幾種典型的DHT網(wǎng)絡(luò)總結(jié)主要內(nèi)容主要內(nèi)容361.P2P網(wǎng)絡(luò)分類非結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)涫侨我獾膬?nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)錈o(wú)關(guān)結(jié)構(gòu)化P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是有規(guī)律的每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)內(nèi)容的存儲(chǔ)位置與網(wǎng)絡(luò)拓?fù)湎嚓P(guān)內(nèi)容的存儲(chǔ)位置與節(jié)點(diǎn)標(biāo)識(shí)之間存在著映射關(guān)系1.P2P網(wǎng)絡(luò)分類非結(jié)構(gòu)化P2P37P2P網(wǎng)絡(luò)分類在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，內(nèi)容一般使用內(nèi)容索引來(lái)表示,內(nèi)容索引包括key和value兩部分,其中key是內(nèi)容的關(guān)鍵字,value是存放內(nèi)容的實(shí)際位置,因此內(nèi)容索引也表示為<key,value>對(duì)內(nèi)容索引<夜宴,/yeyan.avi>表示電影夜宴可以從/yeyan.avi處獲得P2P網(wǎng)絡(luò)分類在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，內(nèi)容一般使用內(nèi)容索引來(lái)表382.Hash函數(shù)概述Hash函數(shù)可以根據(jù)給定的一段任意長(zhǎng)的消息計(jì)算出一個(gè)固定長(zhǎng)度的比特串，通常稱為消息摘要（MD：MessageDigest），一般用于消息的完整性檢驗(yàn)。Hash函數(shù)有以下特性：給定P，易于計(jì)算出MD（P）只給出MD（P），幾乎無(wú)法找出P無(wú)法找到兩條具有同樣消息摘要的不同消息Hash函數(shù)MD5：消息摘要長(zhǎng)度固定為128比特SHA-1：消息摘要長(zhǎng)度固定為160比特2.Hash函數(shù)概述Hash函數(shù)可以根據(jù)給定的一段任意長(zhǎng)的消39Hash函數(shù)應(yīng)用于P2P的特性唯一性：不同的輸入明文，對(duì)應(yīng)著不同的輸出摘要將節(jié)點(diǎn)IP地址的摘要作為節(jié)點(diǎn)ID，保證了節(jié)點(diǎn)ID在P2P環(huán)境下的唯一性SHA-1(“”)=24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1(“”)=e1d9b25dee874b0c51db4c4ba7c9ae2b766fbf27Hash函數(shù)應(yīng)用于P2P的特性唯一性：不同的輸入明文，對(duì)應(yīng)著403.DHT原理(1)將內(nèi)容索引抽象為<K,V>對(duì)K是內(nèi)容關(guān)鍵字的Hash摘要K=Hash(key)V是存放內(nèi)容的實(shí)際位置，例如節(jié)點(diǎn)IP地址等所有的<K,V>對(duì)組成一張大的Hash表，因此該表存儲(chǔ)了所有內(nèi)容的信息每個(gè)節(jié)點(diǎn)都隨機(jī)生成一個(gè)標(biāo)識(shí)(ID)，把Hash表分割成許多小塊，按特定規(guī)則(即K和節(jié)點(diǎn)ID之間的映射關(guān)系)分布到網(wǎng)絡(luò)中去，節(jié)點(diǎn)按這個(gè)規(guī)則在應(yīng)用層上形成一個(gè)結(jié)構(gòu)化的重疊網(wǎng)絡(luò)給定查詢內(nèi)容的K值，可以根據(jù)K和節(jié)點(diǎn)ID之間的映射關(guān)系在重疊網(wǎng)絡(luò)上找到相應(yīng)的V值，從而獲得存儲(chǔ)文件的節(jié)點(diǎn)IP地址3.DHT原理(1)將內(nèi)容索引抽象為<K,V>對(duì)41DHT原理(2)內(nèi)容內(nèi)容關(guān)鍵字key內(nèi)容存儲(chǔ)位置等信息value內(nèi)容索引K=Hash(key)提取kvHash表電影夜宴電影、夜宴/yeyan.avi內(nèi)容索引K=hash(電影,夜宴)V=/yeyan.aviDHT原理(2)內(nèi)容內(nèi)容關(guān)鍵字key內(nèi)容存儲(chǔ)位置等信息內(nèi)容索42DHT原理(3)kva.Hash表b.分布式Hash表規(guī)則?KVN1N48N16N32N8KVKVKVKVChord、CAN、Tapestry、Pastry在許多情況下,節(jié)點(diǎn)ID為節(jié)點(diǎn)IP地址的Hash摘要DHT原理(3)kva.Hash表b.分布式Hash表43DHT原理(4)插入

(K1,V1)KVKVKVKVKVKVKVKVKVKVKV(K1,V1)查詢(K1)ABK1=Hash(xyz.mp3)V1=xyz.mp3C索引發(fā)布和內(nèi)容定位DHT原理(4)插入

(K1,V1)KVKVKV44DHT原理(5)定位(Locating)節(jié)點(diǎn)ID和其存放的<K,V>對(duì)中的K存在著映射關(guān)系，因此可以由K獲得存放該<K,V>對(duì)的節(jié)點(diǎn)ID路由(Routing)在重疊網(wǎng)上根據(jù)節(jié)點(diǎn)ID進(jìn)行路由，將查詢消息最終發(fā)送到目的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)需要有到其鄰近節(jié)點(diǎn)的路由信息，包括節(jié)點(diǎn)ID、IP等網(wǎng)絡(luò)拓?fù)渫負(fù)浣Y(jié)構(gòu)由節(jié)點(diǎn)ID和其存放的<K,V>對(duì)中的K之間的映射關(guān)系決定拓?fù)鋭?dòng)態(tài)變化，需要處理節(jié)點(diǎn)加入/退出/失效的情況在重疊網(wǎng)上節(jié)點(diǎn)始終由節(jié)點(diǎn)ID標(biāo)識(shí)，并且根據(jù)ID進(jìn)行路由DHT原理(5)定位(Locating)在重疊網(wǎng)上節(jié)點(diǎn)始終由454.Chord：概述Berkeley和MIT共同提出采用環(huán)形拓?fù)?Chord環(huán))應(yīng)用程序接口Insert(K,V)將<K,V>對(duì)存放到節(jié)點(diǎn)ID為Successor(K)上Lookup(K)根據(jù)K查詢相應(yīng)的VUpdate(K,new_V)根據(jù)K更新相應(yīng)的VJoin(NID)節(jié)點(diǎn)加入Leave()節(jié)點(diǎn)主動(dòng)退出4.Chord：概述Berkeley和MIT共同提出46Chord：Hash表分布規(guī)則Hash算法SHA-1Hash節(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)ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6Chord：Hash表分布規(guī)則Hash算法SHA-1ID=h47Chord：簡(jiǎn)單查詢過(guò)程每個(gè)節(jié)點(diǎn)僅維護(hù)其后繼節(jié)點(diǎn)ID、IP地址等信息查詢消息通過(guò)后繼節(jié)點(diǎn)指針在圓環(huán)上傳遞直到查詢消息中包含的K落在某節(jié)點(diǎn)ID和它的后繼節(jié)點(diǎn)ID之間速度太慢O(N)，N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6Chord：簡(jiǎn)單查詢過(guò)程每個(gè)節(jié)點(diǎn)僅維護(hù)其后繼節(jié)點(diǎn)ID、IP地48Chord：指針表N56指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42節(jié)點(diǎn)S的第i個(gè)指針successor[n+2^(i-1)],1≤i≤m

Chord：指針表N56指針表N8+1N8+2N8+4N8+49Chord：基于指針表的擴(kuò)展查找過(guò)程指針表中有O(logN)個(gè)節(jié)點(diǎn)查詢經(jīng)過(guò)大約O(logN)跳N56K54指針表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42Lookup(K54)指針表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14Chord：基于指針表的擴(kuò)展查找過(guò)程指針表中有O(log50Chord：網(wǎng)絡(luò)波動(dòng)(Churn)Churn由節(jié)點(diǎn)的加入、退出或者失效所引起每個(gè)節(jié)點(diǎn)都周期性地運(yùn)行探測(cè)協(xié)議來(lái)檢測(cè)新加入節(jié)點(diǎn)或退出/失效節(jié)點(diǎn)，從而更新自己的指針表和指向后繼節(jié)點(diǎn)的指針Chord：網(wǎng)絡(luò)波動(dòng)(Churn)Churn由節(jié)點(diǎn)的加入、退51Chord：節(jié)點(diǎn)加入新節(jié)點(diǎn)N事先知道某個(gè)或者某些結(jié)點(diǎn)，并且通過(guò)這些節(jié)點(diǎn)初始化自己的指針表，也就是說(shuō)，新節(jié)點(diǎn)N將要求已知的系統(tǒng)中某節(jié)點(diǎn)為它查找指針表中的各個(gè)表項(xiàng)在其它節(jié)點(diǎn)運(yùn)行探測(cè)協(xié)議后，新節(jié)點(diǎn)N將被反映到相關(guān)節(jié)點(diǎn)的指針表和后繼節(jié)點(diǎn)指針中新結(jié)點(diǎn)N的第一個(gè)后繼結(jié)點(diǎn)將其維護(hù)的小于N節(jié)點(diǎn)的ID的所有K交給該節(jié)點(diǎn)維護(hù)；Chord：節(jié)點(diǎn)加入新節(jié)點(diǎn)N事先知道某個(gè)或者某些結(jié)點(diǎn)，并且通52Chord：節(jié)點(diǎn)退出/失效當(dāng)Chord中某個(gè)結(jié)點(diǎn)M退出/失效時(shí)，所有在指針表中包含該結(jié)點(diǎn)的結(jié)點(diǎn)將相應(yīng)指針指向大于M結(jié)點(diǎn)ID的第一個(gè)有效結(jié)點(diǎn)即節(jié)點(diǎn)M的后繼節(jié)點(diǎn)為了保證節(jié)點(diǎn)M的退出/失效不影響系統(tǒng)中正在進(jìn)行的查詢過(guò)程，每個(gè)Chord節(jié)點(diǎn)都維護(hù)一張包括r個(gè)最近后繼節(jié)點(diǎn)的后繼列表。如果某個(gè)節(jié)點(diǎn)注意到它的后繼節(jié)點(diǎn)失效了，它就用其后繼列表中第一個(gè)正常節(jié)點(diǎn)替換失效節(jié)點(diǎn)Chord：節(jié)點(diǎn)退出/失效當(dāng)Chord中某個(gè)結(jié)點(diǎn)M退出/失效53Chord：拓?fù)涫鋯栴}O(LogN)邏輯跳數(shù)，但是每一邏輯跳可能跨越多個(gè)自治域，甚至是多個(gè)國(guó)家的網(wǎng)絡(luò)重疊網(wǎng)絡(luò)與物理網(wǎng)絡(luò)脫節(jié)實(shí)際的尋路時(shí)延較大Chord：拓?fù)涫鋯栴}O(LogN)邏輯跳數(shù)，但是每一邏輯54Chord：總結(jié)算法簡(jiǎn)單可擴(kuò)展：查詢過(guò)程的通信開銷和節(jié)點(diǎn)維護(hù)的狀態(tài)隨著系統(tǒng)總節(jié)點(diǎn)數(shù)增加成對(duì)數(shù)關(guān)系(O(logN)數(shù)量級(jí))存在拓?fù)涫鋯栴}Chord：總結(jié)算法簡(jiǎn)單55Pastry：概述英國(guó)劍橋Microsoft研究院和Rice大學(xué)共同提出考慮網(wǎng)絡(luò)的本地性,解決物理網(wǎng)絡(luò)和邏輯網(wǎng)絡(luò)的拓?fù)涫涞膯栴}基于應(yīng)用層定義的鄰近性度量,例如IP路由跳數(shù)、地理距離、往返延時(shí)等節(jié)點(diǎn)ID分布采用環(huán)形結(jié)構(gòu)Pastry：概述英國(guó)劍橋Microsoft研究院和Rice56Pastry：Hash表分布規(guī)則Hash算法SHA-1Hash節(jié)點(diǎn)IP地址－>m位節(jié)點(diǎn)ID(表示為NID)Hash內(nèi)容關(guān)鍵字－>m位K(表示為KID)NID和KID是以2b為基的數(shù),共有m/b個(gè)數(shù)位b是一個(gè)配置參數(shù),一般為4節(jié)點(diǎn)按ID從小到大順序排列在一個(gè)邏輯環(huán)上<K,V>存儲(chǔ)在NID與KID數(shù)值最接近的節(jié)點(diǎn)上N0002N0201N0322N1331N1113N2120N2222N3001N3033N3200m=8K1320K1201K0220K2120K31222m-1 0b=2Pastry：Hash表分布規(guī)則Hash算法SHA-1N057Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(1)路由表R路由表包括log2bN(m/b)行，每行包括2b-1個(gè)表項(xiàng)路由表第n行與節(jié)點(diǎn)ID的前n個(gè)數(shù)位相同，但是第n+1個(gè)數(shù)位不同，也稱為n數(shù)位前綴相同路由表中的每項(xiàng)包含節(jié)點(diǎn)ID，IP地址等根據(jù)鄰近性度量選擇距離本節(jié)點(diǎn)近的節(jié)點(diǎn)鄰居節(jié)點(diǎn)集M鄰居節(jié)點(diǎn)集包含|M|個(gè)在鄰近性度量上最接近于本節(jié)點(diǎn)的節(jié)點(diǎn)，|M|為2b或者2X2b,鄰近性度量指的是物理上相鄰節(jié)點(diǎn)鄰居節(jié)點(diǎn)集通常不用于路由查詢消息，而是用來(lái)維護(hù)本地性葉子節(jié)點(diǎn)集L葉子節(jié)點(diǎn)集包含|L|個(gè)節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)，也就是邏輯地址上的相鄰節(jié)點(diǎn),其中|L|/2個(gè)節(jié)點(diǎn)的ID大于本節(jié)點(diǎn)，|L|/2個(gè)ID小于本節(jié)點(diǎn)，|L|為2b或者2X2b

Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(1)路由表R58Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(2)NodeID10233102LeafsetRoutingTableNeighborhoodset0022121021223012033120320311301233122302031302102221003120310132102103233023310222302102002301021130210230322102310001023212110233001102331201023323210213021022102002301130123331301233022121022230120331203203332133211023303310233021102331201023312210233001102330001023323010233232<SMALLERLARGER>節(jié)點(diǎn)ID最接近本節(jié)點(diǎn)的節(jié)點(diǎn)b=2，因此節(jié)點(diǎn)ID的基數(shù)為4(16bits)m/b行依據(jù)鄰近性度量最接近本節(jié)點(diǎn)的節(jié)點(diǎn)每行2b-1個(gè)表項(xiàng)第n行的前n個(gè)數(shù)位與本節(jié)點(diǎn)相同[相同前綴下一數(shù)位其它]當(dāng)前節(jié)點(diǎn)的第n個(gè)數(shù)位沒有合適節(jié)點(diǎn)的表項(xiàng)為空b=2m=16Pastry：節(jié)點(diǎn)維護(hù)狀態(tài)表(2)NodeID1023359Pastry：查詢過(guò)程當(dāng)一個(gè)K為D的查詢消息到達(dá)節(jié)點(diǎn)A節(jié)點(diǎn)A首先看D是否在當(dāng)前節(jié)點(diǎn)的葉子節(jié)點(diǎn)集中，如果是，則查詢消息直接被轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，也就是葉子節(jié)點(diǎn)集中節(jié)點(diǎn)ID與D數(shù)值最接近的那個(gè)節(jié)點(diǎn)(有可能就是當(dāng)前節(jié)點(diǎn))，否則進(jìn)行下一步在路由表中查找與D具有更長(zhǎng)相同前綴的表項(xiàng)，如果該表項(xiàng)不為空，則將查詢消息直接轉(zhuǎn)發(fā)到該節(jié)點(diǎn)，否則進(jìn)行下一步例如路由D=0629的查詢消息5324→

0748→

0605→

0620→

0629如果不存在這樣的節(jié)點(diǎn),當(dāng)前節(jié)點(diǎn)將會(huì)從其維護(hù)的所有鄰居節(jié)點(diǎn)集合中選擇一個(gè)距離該鍵值最接近的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)目標(biāo)路由查詢消息的邏輯跳數(shù)：O(log2bN)

Pastry：查詢過(guò)程當(dāng)一個(gè)K為D的查詢消息到達(dá)節(jié)點(diǎn)A路由查60Pastry：節(jié)點(diǎn)狀態(tài)表和查詢節(jié)點(diǎn)路由表R中的每行與本節(jié)點(diǎn)具有相同的n數(shù)位長(zhǎng)度前綴，但是下一個(gè)數(shù)位不同例如，對(duì)于節(jié)點(diǎn)N0201：

N-:N1???,N2???,N3???

N0:N00??,N01??,N03??

N02:N021?,N022?,N023?

N020:N0200,N0202,N0203當(dāng)有多個(gè)節(jié)點(diǎn)時(shí)，根據(jù)鄰近性度量選擇最近的節(jié)點(diǎn)維持了較好的本地性N0002N0201N2001N1113N2120N2222N3001N3033N3200m=82m-1 0b=2N0122N0212N0221N0233RoutingtableK2120lookup(K2120)N0322Pastry：節(jié)點(diǎn)狀態(tài)表和查詢節(jié)點(diǎn)路由表R中的每行與本節(jié)點(diǎn)具612.2.4Pastry：節(jié)點(diǎn)加入(1)初始化狀態(tài)表新節(jié)點(diǎn)開始時(shí)知道一個(gè)根據(jù)鄰近性度量接近自己的節(jié)點(diǎn)A節(jié)點(diǎn)A可以通過(guò)使用擴(kuò)展環(huán)IP組播等機(jī)制自動(dòng)定位，或者由系統(tǒng)管理員通過(guò)其它手段獲得新節(jié)點(diǎn)通過(guò)運(yùn)行SHA-1算法計(jì)算自己的IP地址的摘要得到節(jié)點(diǎn)ID為X節(jié)點(diǎn)X向節(jié)點(diǎn)A發(fā)送join消息，Pastry將該消息路由到節(jié)點(diǎn)ID在數(shù)值上最接近X的節(jié)點(diǎn)Z接收到j(luò)oin消息的節(jié)點(diǎn)，包括A、Z，以及A到Z路徑上所有的節(jié)點(diǎn)將發(fā)送它們的狀態(tài)表給X，X檢查這些信息，然后節(jié)點(diǎn)根據(jù)下面的過(guò)程初始化狀態(tài)表:由于A與X在鄰近性度量上接近,所以使用A的鄰居節(jié)點(diǎn)集來(lái)初始化X的鄰居節(jié)點(diǎn)集由于Z的節(jié)點(diǎn)ID與X最相近,因此使用Z的葉子節(jié)點(diǎn)集來(lái)初始化X的葉子節(jié)點(diǎn)集X將join消息經(jīng)過(guò)的第i個(gè)節(jié)點(diǎn)的路由表的第i行作為自己路由表的第i行Join消息經(jīng)過(guò)的第i個(gè)節(jié)點(diǎn)與X的前i個(gè)數(shù)位相同向其它相關(guān)節(jié)點(diǎn)通告自己的到來(lái)新節(jié)點(diǎn)向鄰居節(jié)點(diǎn)集、葉子節(jié)點(diǎn)集和路由表中的每個(gè)節(jié)點(diǎn)發(fā)送自己的狀態(tài)，以更新這些節(jié)點(diǎn)的狀態(tài)表2.2.4Pastry：節(jié)點(diǎn)加入(1)初始化狀