分布式系統(tǒng)命名部分PPT

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

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

3、置。2.注冊實體所在的遠(yuǎn)程主機。3.宿主與實體所在的遠(yuǎn)程主機保持聯(lián)系4.客戶首先與宿主建立連接，然后與遠(yuǎn)程主機連接。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位標(biāo)識符。n每個實體被賦予一個特定的m位鍵值。n含有鍵值K的實體位于含有最小標(biāo)識符ID=K的節(jié)點之內(nèi)（稱之為K的后繼者）。DHTs: Finger表原理l每個節(jié)點P維護(hù)一個最多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實體標(biāo)識符n實體的位置信息n別名目錄結(jié)點除了存儲目錄表外還能存儲其他屬性

5、。 5.3.2名稱解析n問題 解析名稱需要目錄結(jié)點的信息，如何找到該結(jié)點。n終止機制 終止機制如何處理從名稱空間中選擇初始結(jié)點。nwww.cs.vu.nl:從域名服務(wù)器開始n/home/steen.mbox:從命名圖的根結(jié)點的目錄表開始。n0031204447784：通過撥號n：路由到VU的web服務(wù)器n提問：為什么終止機制必須是隱式的？ 名稱鏈接n硬鏈接 路徑名：命名圖中每個路徑可以通過路徑中的邊的標(biāo)簽序列來指向，這樣的序列稱為路徑名。 名稱鏈接 注意 結(jié)點N5只有一個名稱。5.3.3名稱空間的實現(xiàn)n基礎(chǔ)問題 通過將命名圖結(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的響應(yīng)，然后發(fā)送給client. 遞歸名稱解析服務(wù)器緩存 可擴展性n規(guī)模的可擴展性 必須保證服務(wù)器在每個時間單元能處理大量的請求，特別對于高層的服務(wù)器。n解決方案 假設(shè)結(jié)點的信息穩(wěn)定。就可以通過將結(jié)點映射到多個服務(wù)器來增加副本數(shù)量，以至于可以從最近的服務(wù)器進(jìn)行名字解析。可擴展性n問題 通過將結(jié)點映射到服務(wù)器能定位到任何地方，我們引入隱含的位置從屬。n地理跨度 必須保證名字解析進(jì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負(fù)責(zé)處理前綴為321的鍵。如果獲得一個鍵值為3012的請求，它將轉(zhuǎn)發(fā)給結(jié)點N30。對于DNS：負(fù)責(zé)鍵值k的結(jié)點用一個哈希值存儲DNS記錄。 DNS記錄副本n定義 在i層被復(fù)制DNS記錄被復(fù)制到所有前綴為i的結(jié)點。注意：在i層被復(fù)制的記錄通常需要i個查找步驟。n結(jié)論 假設(shè)Xi是在i層被復(fù)制最多的記錄部分。那么：N為網(wǎng)絡(luò)中的結(jié)點數(shù)， d = b(1a)=a and a 1，假設(shè)a是

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