《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx

《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx

ID:59593088

大?。?.10 MB

頁數(shù):35頁

時(shí)間:2020-11-14

《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx_第1頁
《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx_第2頁
《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx_第3頁
《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx_第4頁
《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx_第5頁
資源描述:

《《云計(jì)算(第三版)》配套之35:第10章云計(jì)算核心算法(二).pptx》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)210.2DHT算法Chord中DHT的具體實(shí)現(xiàn)ChordChord環(huán)Chord中所有節(jié)點(diǎn)按節(jié)點(diǎn)ID大小順時(shí)針排列并首尾相接組成一個(gè)擁有2m(m一般為160)個(gè)節(jié)點(diǎn)的環(huán)空間后繼節(jié)點(diǎn)successor消息的目標(biāo)節(jié)點(diǎn)就是節(jié)點(diǎn)ID大于或者等于消息Key值的節(jié)點(diǎn)中節(jié)點(diǎn)ID最小的一個(gè)完全分布可擴(kuò)展性可用性好負(fù)載均衡3Chord模型示意圖10.2DHT算法Chord中DHT的具體實(shí)現(xiàn)m=6且只

2、有10個(gè)節(jié)點(diǎn)的查找示意圖,其中節(jié)點(diǎn)標(biāo)識(shí)前加上N而關(guān)鍵字標(biāo)識(shí)前加上K加以區(qū)別,圖中給出了節(jié)點(diǎn)N8、N42、N51的finger表。410.2DHT算法Chord中DHT的具體實(shí)現(xiàn)節(jié)點(diǎn)N的加入過程初始化新節(jié)點(diǎn)的指針表更新現(xiàn)有其他節(jié)點(diǎn)的指針表從后繼節(jié)點(diǎn)把關(guān)鍵字傳遞到節(jié)點(diǎn)N節(jié)點(diǎn)的退出過程在Chord中,當(dāng)節(jié)點(diǎn)N失效時(shí),所有指針表中包括N的節(jié)點(diǎn)都必須把N替換成N的后繼節(jié)點(diǎn)。在失效處理中最關(guān)鍵的步驟是維護(hù)正確的后繼指針10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tape

3、stry中DHT的具體實(shí)現(xiàn)610.2DHT算法Pastry中DHT的具體實(shí)現(xiàn)1.節(jié)點(diǎn)的加入假定新加入節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)為N,節(jié)點(diǎn)號(hào)的分配過程是由應(yīng)用程序決定的。N的加入過程主要包括初始化自己的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu),并通知其他節(jié)點(diǎn)自己已經(jīng)加入系統(tǒng)。N在加入Pastry之前,需要知道一個(gè)相鄰節(jié)點(diǎn)A的位置信息。2.節(jié)點(diǎn)的退出Pastry網(wǎng)絡(luò)中的節(jié)點(diǎn)可能會(huì)隨時(shí)失效或者不發(fā)出通知離開系統(tǒng)。當(dāng)相鄰節(jié)點(diǎn)不能和某個(gè)Pastry節(jié)點(diǎn)通信時(shí),就認(rèn)為該節(jié)點(diǎn)發(fā)生了失效。10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具

4、體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)810.2DHT算法CAN中DHT的具體實(shí)現(xiàn)CAN是內(nèi)容可編址網(wǎng)絡(luò)(Content-AddressableNetwork)的縮寫CAN可以在Internet規(guī)模的大型對(duì)等網(wǎng)絡(luò)上提供類似哈希表的功能。CAN具有可擴(kuò)展、容錯(cuò)和完全自組織等特點(diǎn)。CAN類似于一張大哈希表,基本操作包括插入、查找和刪除。CAN由大量自治的節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)保存哈希表的一部分,稱為一個(gè)區(qū)。CAN的設(shè)計(jì)完全是分布式的,不需要任何形式的中央控制點(diǎn)。CAN具有很好的可擴(kuò)展性,節(jié)點(diǎn)只需要維護(hù)少量的控制狀態(tài)而且狀態(tài)數(shù)量獨(dú)立于系統(tǒng)中的節(jié)點(diǎn)數(shù)量。CAN支持容錯(cuò)特性,節(jié)點(diǎn)可以繞

5、過錯(cuò)誤節(jié)點(diǎn)進(jìn)行路由。9二維坐標(biāo)空間中CAN的節(jié)點(diǎn)示意圖10.2DHT算法CAN中DHT的具體實(shí)現(xiàn)C(0-0.5,0.5-1.0)D(0.5-0.75,0.5-1.0)E(0.75-1.0,0.5-1.0)A(0-0.5,0-0.5)B(0.5-1.0,0-0.5)0.01.01.0整個(gè)區(qū)域坐標(biāo)由5個(gè)節(jié)點(diǎn)A,B,C,D,E組成,每個(gè)節(jié)點(diǎn)負(fù)責(zé)部分區(qū)域,CAN中通過哈希函數(shù)把資源映射到d維空間中的一點(diǎn),資源對(duì)象就發(fā)布在該節(jié)點(diǎn)上。10CAN路由模型的路由過程10.2DHT算法CAN中DHT的具體實(shí)現(xiàn)(0,1)(1,0)(0,0)(1,1)Key=(0,8,0,9)Node=(0.75,0,0.

6、75,1)查詢操作通過在d維笛卡兒坐標(biāo)空間中轉(zhuǎn)發(fā)查詢消息被執(zhí)行,轉(zhuǎn)發(fā)從查詢初始化點(diǎn)沿著坐標(biāo)系上最接近直線的路徑到達(dá)存儲(chǔ)關(guān)鍵字的節(jié)點(diǎn)。10.2DHT算法10.2.1DHT原理介紹10.2.2Chord中DHT的具體實(shí)現(xiàn)10.2.3Pastry中DHT的具體實(shí)現(xiàn)10.2.4CAN中DHT的具體實(shí)現(xiàn)10.2.5Tapestry中DHT的具體實(shí)現(xiàn)1210.2DHT算法Tapestry中DHT的具體實(shí)現(xiàn)Tapestry分層路由和組織結(jié)構(gòu)的查詢算法,它為面向廣域網(wǎng)的分布式應(yīng)用提供了一個(gè)分布式查找和路由定位基礎(chǔ)平臺(tái)。Tapestry網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)和文檔通過哈希變換得到各自160位比特的唯一標(biāo)識(shí)符Ta

7、pestry基于文檔標(biāo)識(shí)符的后綴進(jìn)行路由Tapestry基于Plaxton中提出的定位和路由機(jī)制進(jìn)行優(yōu)化Tapestry采用的基本定位和路由機(jī)制和Plaxton很類似Tapestry中的每個(gè)節(jié)點(diǎn)都可以用Plaxton中描述的算法轉(zhuǎn)發(fā)消息1310.2DHT算法Tapestry中DHT的具體實(shí)現(xiàn)1.節(jié)點(diǎn)的加入Tapestry的節(jié)點(diǎn)加入算法和Pastry很類似。構(gòu)造完自己的數(shù)據(jù)結(jié)構(gòu)后,節(jié)點(diǎn)N將通知網(wǎng)絡(luò)中的其他節(jié)點(diǎn),自己已經(jīng)加入網(wǎng)絡(luò)。構(gòu)造過程中還需要進(jìn)

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。