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

第5章命名系統(tǒng)第5章命名系統(tǒng)名稱、標識符和地址無層次命名結構化命名基于屬性的命名命名系統(tǒng)位置無關（locationindependent）用戶友好（human-friendlyname）高效搜索（effectivelysearch）名稱、標識符和地址名稱的實質

在分布式系統(tǒng)中，名稱用來指向一個實體。要對實體進行操作，就需要訪問實體，因此需要一個訪問點。訪問點是另一種特殊的實體，它的名稱稱為地址。注意

對于實體E，一個與位置無關的名稱，是獨立于E的訪問點的地址。標識符純名稱

純名稱是一些沒有任何意義的名稱；是一些隨機的字符串。純名稱只是起區(qū)分的作用。標識符

標識符是具有以下屬性的名稱：P1：一個標識符最多引用一個實體。

P2：每個實體最多由一個標識符引用。

P3：一個標識符始終引用同一個實體（就是說標識符永遠不會重新使用）。5.2無層次命名問題提出

當只給出非結構化的名稱（比如說一個標識符），我們?nèi)绾味ㄎ凰脑L問點？簡單方法：廣播和多播，轉發(fā)指針基于宿主位置的方法分布式散列表分層方法廣播和多播

5.2.1簡單方法不能超出局域網(wǎng)要求所有的進程監(jiān)聽定位請求廣播一個包含實體的標識符，要求擁有該實體的機器返回它當前的地址。轉發(fā)指針當實體移動時，它留下一個指針指向下一個位置。5.2.2基于宿主位置的方法利用宿主追蹤實體的位置注冊宿主位置。注冊實體所在的遠程主機。宿主與實體所在的遠程主機保持聯(lián)系客戶首先與宿主建立連接，然后與遠程主機連接。5.2.2基于宿主位置的方法5.2.2基于宿主位置的方法基于宿主位置的方法的問題宿主地址必須在實體的生存期內(nèi)有效。宿主地址是固定的?？蓴U展性差。問題我們?nèi)绾谓鉀Q永轉移的問題？5.2.3分布式散列表（DHT）Chord將節(jié)點組織成邏輯環(huán)各個節(jié)點被賦予一個隨機的m位標識符。每個實體被賦予一個特定的m位鍵值。含有鍵值K的實體位于含有最小標識符ID>=K的節(jié)點之內(nèi)（稱之為K的后繼者）。DHTs:Finger表原理每個節(jié)點P維護一個最多M個實體的指狀表FTp[]。FTp[i]=succ(p+2i-1)要查找鍵k，節(jié)點P立即把該請求轉發(fā)給在P的指狀表中索引為J的節(jié)點Q。q=FTp[j]k<FTp[j+1]如果p<k<FTp[1]，請求也要轉發(fā)給FTp[1]。DHTs:Finger表利用網(wǎng)絡鄰近潛在問題

請求跨因特網(wǎng)進行路由時不穩(wěn)定:結點k和后繼結點(k+1)可能相距很遠。基于拓撲的結點標識符賦值：在標識符賦值時，兩個鄰近結點所賦給的標識符也是靠近的。很難實現(xiàn)。鄰近路由：每個結點維護多個后繼者，轉發(fā)給最近者。例：FTq[i]指向[p+2i-1;p+2i-1]區(qū)間內(nèi)的第一個結點。

結點P也能跟蹤該區(qū)間的其他結點。鄰近鄰結點選擇：選擇最近的結點作為鄰結點。5.2.4分層方法（HLS）基本思想將底層網(wǎng)絡劃分為一組域，構建一個大規(guī)模的搜索樹。每個域都擁有關聯(lián)的目錄節(jié)點DIR。

HLS：目錄樹組織不變性實體E的地址存儲在葉域或者中間節(jié)點。中間節(jié)點含有一個指向更底層子域目錄節(jié)點的指針。根節(jié)點掌握所有實體的信息。HLS：查找操作基本原理首先在客戶所在葉域的目錄節(jié)點查找實體E。節(jié)點里含有實體E的位置記錄=>跟隨向下查找指針，如果沒有E的位置記錄繼續(xù)下一步。向父節(jié)點所在域查找實體E的位置信息，以此類推。HLS：插入操作5.3結構化命名命名空間本質

名稱空間是一個有向圖，其中葉節(jié)點代表一個實體。目錄節(jié)點是指向其他葉節(jié)點的實體。注意目錄節(jié)點用于存儲一個表，其中每條分支邊用一個對來表示。

5.3.1名稱空間結點通過名稱存儲各種屬性，描述實體的各方面信息。實體類型實體標識符實體的位置信息別名目錄結點除了存儲目錄表外還能存儲其他屬性。

5.3.2名稱解析問題

解析名稱需要目錄結點的信息，如何找到該結點。終止機制終止機制如何處理從名稱空間中選擇初始結點。www.cs.vu.nl:從域名服務器開始/home/steen.mbox:從命名圖的根結點的目錄表開始。0031204447784：通過撥號：路由到VU的web服務器提問：為什么終止機制必須是隱式的？

名稱鏈接硬鏈接

路徑名：命名圖中每個路徑可以通過路徑中的邊的標簽序列來指向，這樣的序列稱為路徑名。

名稱鏈接注意結點N5只有一個名稱。5.3.3名稱空間的實現(xiàn)基礎問題

通過將命名圖結點分布存儲實現(xiàn)分布式名稱解析。命名空間分層全局層：由最高級別的結點組成。行政層：由那些在單個組織內(nèi)一起被管理的目錄結點組成。管理層：由那些經(jīng)常改變的結點組成。5.3.3名稱空間的實現(xiàn)5.3.3名稱空間的實現(xiàn)

迭代名稱解析解析程序將完整名稱(dir,[name1,…namek])發(fā)給server0。Server0將(dir,name)解析為dir1,返回sever1(存儲dir1)的地址。Client發(fā)送解析(dir,[name1,…namek])請求給sever1。遞歸名稱解析解析程序將完整名稱(dir,[name1,…namek])發(fā)給server0。Server0將(dir,name)解析為dir1,發(fā)送解析(dir,[name1,…namek])請求給sever1返回sever1(存儲dir1)的地址。Server0等待server1的響應，然后發(fā)送給client.

遞歸名稱解析服務器緩存

可擴展性規(guī)模的可擴展性

必須保證服務器在每個時間單元能處理大量的請求，特別對于高層的服務器。解決方案

假設結點的信息穩(wěn)定。就可以通過將結點映射到多個服務器來增加副本數(shù)量，以至于可以從最近的服務器進行名字解析。可擴展性問題

通過將結點映射到服務器能定位到任何地方，我們引入隱含的位置從屬。地理跨度

必須保證名字解析進程能跨越很大的地理空間。

示例：分布式域名系統(tǒng)基本思想

將DNS全名哈希成一個鍵值k，然后在基于DHT的系統(tǒng)中查詢k值。缺點：不能再子域中查詢所有的結點。結點信息DNSonPastryPastry

帶有前綴的鍵值構成的基于DHT的系統(tǒng)?？紤]一個4位鍵值的系統(tǒng)。一個ID為3210追蹤以下的結點。

注意

結點3210負責處理前綴為321的鍵。如果獲得一個鍵值為3012的請求，它將轉發(fā)給結點N30。對于DNS：負責鍵值k的結點用一個哈希值存儲DNS記錄。

DNS記錄副本定義

在i層被復制—DNS記錄被復制到所有前綴為i的結點。注意：在i層被復制的記錄通常需要i個查找步驟。結論

假設Xi是在i層被復制最多的記錄部分。那么：N為網(wǎng)絡中的結點數(shù)，d=b(1

a)=aanda1，假設a是ZipF分布的參數(shù)。

DNS記錄副本意圖

當查找DNS記錄是，如果你要達到平均為1跳的要求，令b=4,a=0.9,N=10，000，并且有1000000條記錄。5.4基于屬性的命名概論

在分布式系統(tǒng)中，描述實體最常用的方法是利用屬性。問題 查找操作很耗時，因為它要求匹配請求的屬性值而不是實際的值。解決方案 結合傳統(tǒng)的結構化命名，將目錄服務作為數(shù)據(jù)庫5.4.1目錄服務是指基于屬性的命名系統(tǒng)，而支持結構化命名的系統(tǒng)通常稱為命名系統(tǒng)屬性設計因人而異引入資源描述框架（resourcedescriptionframeworkRDF）

基于屬性的命名系統(tǒng)基本上要求對所有資源描述進行窮舉搜索。5.4.2分層實現(xiàn)：LDAP5.4.3非集中式實現(xiàn)映射到分布式散列表語義覆蓋網(wǎng)絡映射到分布式散列表 將資源描述給出的（屬性，值）對轉換為DHT的一個鍵值，鍵值中的某些位用于表示屬性，某些位用于表示值。語義覆蓋網(wǎng)絡（semanticoverlaynetwork） 語義相近的鄰結點