分布式系統(tǒng)命名部分PPT_第1頁
分布式系統(tǒng)命名部分PPT_第2頁
分布式系統(tǒng)命名部分PPT_第3頁
分布式系統(tǒng)命名部分PPT_第4頁
分布式系統(tǒng)命名部分PPT_第5頁
已閱讀5頁,還剩37頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

1、第5章 命名系統(tǒng)第5章 命名系統(tǒng)n名稱、標識符和地址n無層次命名n結(jié)構(gòu)化命名n基于屬性的命名命名系統(tǒng)n位置無關(location independent)n用戶友好(human-friendly name)n高效搜索(effectively search)名稱、標識符和地址n名稱的實質(zhì) 在分布式系統(tǒng)中,名稱用來指向一個實體。要對實體進行操作,就需要訪問實體,因此需要一個訪問點。訪問點是另一種特殊的實體,它的名稱稱為地址。n注意 對于實體E,一個與位置無關的名稱,是獨立于E的訪問點的地址。 標識符n純名稱 純名稱是一些沒有任何意義的名稱;是一些隨機的字符串。純名稱只是起區(qū)分的作用。n標識符 標識

2、符是具有以下屬性的名稱: P1:一個標識符最多引用一個實體。 P2:每個實體最多由一個標識符引用。 P3:一個標識符始終引用同一個實體(就是說標識符永遠不會重新使用)。5.2無層次命名n問題提出 當只給出非結(jié)構(gòu)化的名稱(比如說一個標識符),我們?nèi)绾味ㄎ凰脑L問點?l簡單方法:廣播和多播,轉(zhuǎn)發(fā)指針l基于宿主位置的方法l分布式散列表l分層方法n廣播和多播 5.2.1簡單方法l不能超出局域網(wǎng)l要求所有的進程監(jiān)聽定位請求 廣播一個包含實體的標識符,要求擁有該實體的機器返回它當前的地址。n轉(zhuǎn)發(fā)指針當實體移動時,它留下一個指針指向下一個位置。5.2.2基于宿主位置的方法利用宿主追蹤實體的位置1.注冊宿主位

3、置。2.注冊實體所在的遠程主機。3.宿主與實體所在的遠程主機保持聯(lián)系4.客戶首先與宿主建立連接,然后與遠程主機連接。5.2.2基于宿主位置的方法5.2.2基于宿主位置的方法n基于宿主位置的方法的問題n宿主地址必須在實體的生存期內(nèi)有效。n宿主地址是固定的。n可擴展性差。n問題 我們?nèi)绾谓鉀Q永轉(zhuǎn)移的問題?5.2.3分布式散列表(DHT)Chord 將節(jié)點組織成邏輯環(huán)n各個節(jié)點被賦予一個隨機的m位標識符。n每個實體被賦予一個特定的m位鍵值。n含有鍵值K的實體位于含有最小標識符ID=K的節(jié)點之內(nèi)(稱之為K的后繼者)。DHTs: Finger表原理l每個節(jié)點P維護一個最多M個實體的指狀表FTp。 FTp

4、i = succ(p+2i-1)l要查找鍵k,節(jié)點P立即把該請求轉(zhuǎn)發(fā)給在P的指狀表中索引為J的節(jié)點Q。 q = FTpj k FTpj +1l如果p k 跟隨向下查找指針,如果沒有E的位置記錄繼續(xù)下一步。l向父節(jié)點所在域查找實體E的位置信息,以此類推。HLS:插入操作 5.3 結(jié)構(gòu)化命名n命名空間本質(zhì) 名稱空間是一個有向圖,其中葉節(jié)點代表一個實體。目錄節(jié)點是指向其他葉節(jié)點的實體。n 注意目錄節(jié)點用于存儲一個表,其中每條分支邊用一個 對來表示。 5.3.1名稱空間n結(jié)點通過名稱存儲各種屬性,描述實體的各方面信息。n實體類型n實體標識符n實體的位置信息n別名目錄結(jié)點除了存儲目錄表外還能存儲其他屬性

5、。 5.3.2名稱解析n問題 解析名稱需要目錄結(jié)點的信息,如何找到該結(jié)點。n終止機制 終止機制如何處理從名稱空間中選擇初始結(jié)點。nwww.cs.vu.nl:從域名服務器開始n/home/steen.mbox:從命名圖的根結(jié)點的目錄表開始。n0031204447784:通過撥號n:路由到VU的web服務器n提問:為什么終止機制必須是隱式的? 名稱鏈接n硬鏈接 路徑名:命名圖中每個路徑可以通過路徑中的邊的標簽序列來指向,這樣的序列稱為路徑名。 名稱鏈接 注意 結(jié)點N5只有一個名稱。5.3.3名稱空間的實現(xiàn)n基礎問題 通過將命名圖結(jié)點分布存儲實現(xiàn)分布式名稱解析。n命名空間分層n

6、全局層:由最高級別的結(jié)點組成。n行政層:由那些在單個組織內(nèi)一起被管理的目錄結(jié)點組成。n管理層:由那些經(jīng)常改變的結(jié)點組成。5.3.3名稱空間的實現(xiàn)5.3.3名稱空間的實現(xiàn) 迭代名稱解析n 解析程序?qū)⑼暾Q(dir,name1,namek)發(fā)給server0。n Server0將(dir,name)解析為dir1,返回sever1(存儲dir1)的地址。n Client發(fā)送解析(dir,name1,namek)請求給sever1。 遞歸名稱解析n 解析程序?qū)⑼暾Q(dir,name1,namek)發(fā)給server0。n Server0將(dir,name)解析為dir1,發(fā)送解析(dir,na

7、me1,namek)請求給sever1返回sever1(存儲dir1)的地址。n Server0等待server1的響應,然后發(fā)送給client. 遞歸名稱解析服務器緩存 可擴展性n規(guī)模的可擴展性 必須保證服務器在每個時間單元能處理大量的請求,特別對于高層的服務器。n解決方案 假設結(jié)點的信息穩(wěn)定。就可以通過將結(jié)點映射到多個服務器來增加副本數(shù)量,以至于可以從最近的服務器進行名字解析??蓴U展性n問題 通過將結(jié)點映射到服務器能定位到任何地方,我們引入隱含的位置從屬。n地理跨度 必須保證名字解析進程能跨越很大的地理空間。 示例:分布式域名系統(tǒng)n基本思想 將DNS全名哈希成一個鍵值k,然后在基于DHT的

8、系統(tǒng)中查詢k值。缺點:不能再子域中查詢所有的結(jié)點。n結(jié)點信息DNS on PastrynPastry 帶有前綴的鍵值構(gòu)成的基于DHT的系統(tǒng)??紤]一個4位鍵值的系統(tǒng)。一個ID為3210追蹤以下的結(jié)點。 n注意 結(jié)點3210負責處理前綴為321的鍵。如果獲得一個鍵值為3012的請求,它將轉(zhuǎn)發(fā)給結(jié)點N30。對于DNS:負責鍵值k的結(jié)點用一個哈希值存儲DNS記錄。 DNS記錄副本n定義 在i層被復制DNS記錄被復制到所有前綴為i的結(jié)點。注意:在i層被復制的記錄通常需要i個查找步驟。n結(jié)論 假設Xi是在i層被復制最多的記錄部分。那么:N為網(wǎng)絡中的結(jié)點數(shù), d = b(1a)=a and a 1,假設a是

9、ZipF分布的參數(shù)。 DNS記錄副本n意圖 當查找DNS記錄是,如果你要達到平均為1跳的要求,令b=4,a=0.9,N=10,000,并且有1000000條記錄。5.4基于屬性的命名n概論 在分布式系統(tǒng)中,描述實體最常用的方法是利用屬性。n問題查找操作很耗時,因為它要求匹配請求的屬性值而不是實際的值。n解決方案結(jié)合傳統(tǒng)的結(jié)構(gòu)化命名,將目錄服務作為數(shù)據(jù)庫5.4.1 目錄服務n是指基于屬性的命名系統(tǒng),而支持結(jié)構(gòu)化命名的系統(tǒng)通常稱為命名系統(tǒng)n屬性設計因人而異n引入資源描述框架(resource description framework RDF) 基于屬性的命名系統(tǒng)基本上要求對所有資源描述進行窮舉搜索。5.4.2分層實現(xiàn):LDAP5

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論