命名與資源統(tǒng)一定位

1、1 實體命名2 移動實體的定位3 無引用實體的刪除為什么要命名？名稱的形式？命名的方式有哪些？對實體進行操作就需要一個訪問點.訪問點的名稱稱為地址。一個實體的訪問點的地址也簡稱為實體的地址。這種命名方式的缺點： 訪問點隨時會發(fā)生改變或者重新分配給另一實體，我們就得到一個無效的查詢結果。 一個實體可能有多個訪問點，哪個地址用來作為引用是不清楚的。標識符是用來唯一標識實體的名稱。標識符具有以下屬性：一個標識符最多指向一個實體；每個實體最多由一個標識符指向；一個標識符始終指向同一個實體（即不會重新使用）。例如：圖書ISBN編號、硬盤序列號等由自然語言定義的名稱，即用戶自己定義的名稱。例如：Windo

2、ws系統(tǒng)中的文件名定義：一個系統(tǒng)中的所有實體的名稱的集合以及其相互的關系表示方式：帶有標注的具有兩種類型節(jié)點的有向圖l葉節(jié)點：表示一個命名的實體，其性質是不具有分支邊l目錄節(jié)點：具有一定數(shù)量的分支邊，每條邊用一個名稱標注。用于存儲一個表，其中每條分支邊用一個（邊標簽，節(jié)點標識符）對來表示。l特殊的節(jié)點根節(jié)點：只具有分支邊，不具有進入邊n0：home,steen,mbox這樣的序列稱為路徑名。 絕對路徑路徑名 相對路徑在圖中通常不使用路徑名n0：home,steen,mbox而是使用其字符串表示法/home/steen/mbox來表示。全局與局部名稱n全局名稱：絕對名稱，無論在何處使用，都標識同

3、一實體n局部名稱：相對名稱，其所標識的實體依賴于使用上下文根節(jié)點：根目錄目錄節(jié)點：文件目錄（文件夾）葉節(jié)點：文件 在邏輯磁盤的連續(xù)磁盤塊上實現(xiàn)的文件系統(tǒng)的一般組織結構如圖所示：n名稱解析：查詢名稱的過程 考慮路徑名N: 解析過程：1.解析從命名圖的節(jié)點N開始2.在N的目錄表查詢名稱label-1，并返回label-1所指向的節(jié)點的標識符3.解析過程在標示出的節(jié)點目錄表中查詢名稱label-2，4.以此類推5.直到解析會在由label-n所指向的最后一個節(jié)點上停止，并返回該節(jié)點的內容n問題一：從哪里開始解析名稱？n問題二：怎么開始解析名稱？知道如何啟動以及在何處啟動名稱解析通常稱為終止機制。從本

4、質上講，終止機制處理從名稱空間中選擇初始節(jié)點，名稱解析從初始節(jié)點開始。解析文件名需要事先實現(xiàn)一些機制，通過他們解析程序才可以啟動。例如：一個字符串“12345678901”，很多人都不知道如何處理這些數(shù)字，除非告訴他們這個數(shù)列是電話號碼。該信息足夠啟動解析程序。別名：是同一個實體的另一個名稱別名的實現(xiàn)方式：（1）硬連接：允許多個絕對路徑名來指向命名圖中的同一個節(jié)點（2）符號連接：用葉節(jié)點來表示實體，而不是存儲實體的地址或位置，該節(jié)點存儲絕對路徑名。 由于在分布式系統(tǒng)中名稱空間分布在不同的機器上，因此在進行名稱解析之前需要想辦法將不同機器上的名稱空間“合并”。方法：（1）掛載； （2）全局名稱服

5、務。定義：用一個目錄節(jié)點來存儲一個外部名稱空間的一個目錄節(jié)點的標識符。存儲節(jié)點標識符的目錄節(jié)點稱為掛接點；外部名稱空間的目錄節(jié)點稱為掛載點。 在分布式系統(tǒng)中掛載外部名稱空間需要的信息：（1）訪問協(xié)議的名稱；（2）服務器的名稱；（3）外部名稱空間中掛載點的名稱。存在的問題：現(xiàn)有名稱都發(fā)生變化；如果合并的名稱空間太多將導致性能問題。n名稱空間的分類（分層）：1. 全局層：由最高級的節(jié)點組成。特點：穩(wěn)定，很少變化。2. 行政層：由在單個組織內一起被管理的目錄節(jié)點組成。特點：相對穩(wěn)定3. 管理層：由經(jīng)常改變的節(jié)點組成。http:/ （2）不使用客戶端緩存； （3）可以聯(lián)系根服務器的地址是眾所周知的。方

6、法一：迭代名稱解析root:方法二：遞歸名稱解析遞歸名稱解析直接將結果發(fā)送給它找到的下一個名稱服務器。內容內容迭代名稱解析迭代名稱解析遞歸名稱解析遞歸名稱解析通信開銷大小緩存結果較有效非常有效 進行長距離通信時，迭代名稱解析需要和服務器進行3次遠程通信，而遞歸名稱解析只需要進行一次遠程通信和兩次本地或近程通信，總開銷大約是迭代名稱解析的通信開銷的1/3. 通信開銷： 緩存結果： 由于全局層和行政層節(jié)點不會經(jīng)常改變，所以名稱服務器可以有效地緩存返回的地址。此外，由于地址也被遞歸返回負責實現(xiàn)vu節(jié)點以及nl節(jié)點的名稱服務器，所以可以同時緩存地址。還可以緩存中間名稱查詢結果。 例如例如另一個用戶后來

7、請求解析路徑名另一個用戶后來請求解析路徑名root:root: 。該。該名稱被傳遞名稱被傳遞給根服給根服務器后，會被直接轉發(fā)給用于務器后，會被直接轉發(fā)給用于cscs節(jié)點的名稱服務器，節(jié)點的名稱服務器，并請求他解析剩下的名稱。并請求他解析剩下的名稱。1.DNS名稱空間標識符：區(qū)分大小寫的字符串，字符串由字母和數(shù)字組成。字符串的最大長度63個字符，完整的路徑名最大長度255個字符。例：路徑名root:DNS表示：flits.cs.vu.nl.（最后一個點通常省略）概念：域：子樹域名：指向根節(jié)點的路徑名（有絕對和相對之分）記錄類型記錄類型相關實體相關實體內容內容SOA（授權起點）區(qū)域文件的信息A（地

8、址）主機允許通信的主機所用的IP地址MX（郵件交換）域指向郵件服務器，該服務器處理發(fā)往該節(jié)點的郵件SRV域包含處理特定服務的服務器名稱NS（名稱服務器）區(qū)域包含一個服務器名稱CNAME（規(guī)范名稱）節(jié)點包含主機的規(guī)范名稱或者說主名PTR（指針）主機維護IP地址到主機名稱之間的反向映射HINFO（主機信息）主機存儲所代表主機的信息TXT任意類型容納任何被認為有用的、特定于實體的信息 節(jié)點的內容由一組資源記錄組成。各種不同類型的資節(jié)點的內容由一組資源記錄組成。各種不同類型的資源記錄如下表所示：源記錄如下表所示：2.DNS的實現(xiàn)DNS名稱空間劃分為：全局層和行政層。為了更好的理解實現(xiàn)方式，下圖顯示了一

9、個文件的部分內容：n命名命名/ /定位實體定位實體n簡單方法簡單方法n基于起始位置的方法基于起始位置的方法n層次方法層次方法創(chuàng)建分布式系統(tǒng)的目的是讓人使用，同時實體也必須有地址，因而命名系統(tǒng)實質上都要維護易于理解的名稱與地址之間的映射。為什么大型名稱系統(tǒng)實現(xiàn)方式能夠高效運行？例：更新ftp.cs.vu.nl的地址，假設名稱不發(fā)生改變 （1）如果FTP服務器被轉移到另一臺機器上，且這臺機器和cs.vu.nl同域。 那么更新地址只需要修改DNS數(shù)據(jù)庫。由此看出，如果全局層和行政層節(jié)點不經(jīng)常變化，更新限于一個服務器，就可以高效地實現(xiàn)DNS這樣的命名系統(tǒng)。 （2）如果轉移到名為ftp.cs.unisa

10、.edu.au的機器(不同域)上。假設ftp.cs.vu.nl不變，因為這個名稱可能被作為標識符了。在ftp.cs.vu.nl的DNS數(shù)據(jù)庫中記錄新機器的地址；記錄新機器的名稱而不是它的地址，同時有效地把ftp.cs.vu.nl轉化成一個符號連接。記錄新機器的地址的缺點： 查詢操作時不受影響，當再次把ftp.cs.vu.nl轉移到另一臺機器上時，必須同時更新它在cs.vu.nl所用DNS數(shù)據(jù)庫中的項，但這種更新不再是本地操作，完成更新操作可能需要幾百ms。違背了對管理層節(jié)點進行的操作是高效的假設。新機器的名稱的缺點： 查詢操作變得比較低效，每次查詢都會被分成兩步：（1）找到機器的名稱；（2）查

11、找與該名稱相關聯(lián)的地址。另一個嚴重問題：名稱不能改變出現(xiàn)問題的原因：命名服務維護著易于理解的名稱與實體地址之間的直接映射。每當名稱或地址發(fā)生變化時，映射也同樣需要修改。解決方法：引入標識符來把命名實體與查找實體分開 在通過命名服務查找實體時，命名服務會返回一個標識符。 實體的定位由獨立的定位服務處理。定位服務實際上是以標識符為輸入，然后返回被表示實體的地址。假設這樣一個分布式系統(tǒng)：它創(chuàng)建于一個能夠提供高效廣播功能的計算機網(wǎng)絡之中。這種功能由局域網(wǎng)提供，在這種網(wǎng)絡中所有的機器都鏈接在一根電纜上。原理：將包含該實體所用標識符的信息廣播到每臺機器上，并要求每臺機器查看它是否擁有該實體。只有能夠為該實

12、體提供訪問點的機器才會發(fā)送回復信息，回復信息中包含訪問點的地址。缺點：隨著網(wǎng)絡的擴大，廣播變得低效。通過使用多播，只有符合條件的一組主機才能接受到請求。l多播組：符合條件的一組主機系統(tǒng)負責將信息發(fā)送給所有的組成員l多播地址的使用方式（1）用作對多播實體的通用定位服務（2）可以將多播地址與多個復制的實體相關聯(lián)，并使用多播查找一個最近的副本（選擇最先回復的復制實體）。原理：當實體從A移動到B時，它將在后面留下一個指針，這個指針指向它在B中的新位置。優(yōu)點：簡單，一旦找到實體以后，客戶就可以順著轉發(fā)指針形成的鏈查找實體的當前地址。缺點：l 如果不采取特殊措施，那么鏈可能會特別長，以致定位實體的開銷會很

13、變得很大。l 鏈中的所有中間位置必須維護轉發(fā)指針鏈l 鏈很脆弱，容易斷開按照SSP鏈的方法，每個轉發(fā)指針都以（代理，骨架）對的形式實現(xiàn)。骨架要么包含實際對象的本地引用，要么包含該對象所用代理的本地引用。 為了簡化（代理，骨架）值對組成的鏈，即縮短鏈，調用會攜帶一個代理的標識符，這個代理是調用開始的地方。當調用到達位于當前位置的對象以后，會向發(fā)起調用的代理反饋一個答復。答復包含了對象的當前位置信息，然后代理會把自己的對應骨架調整為對象當前位置中的那一個骨架.由于使用廣播、多播和轉發(fā)指針帶來了可擴展性問題。且在大型網(wǎng)絡中很難實現(xiàn)廣播和多播，而過長的轉發(fā)指針鏈會帶來性能問題，并且容易受到鏈斷開的影響

14、。為了解決這些問題，引入了起始位置的方法。這種方法持續(xù)跟蹤實體的當前位置，可以使用特殊的技術來預防網(wǎng)絡故障或進程失效。起始位置的選擇：在實踐中，通常選擇創(chuàng)建實體的位置作為起始位置。 每個移動主機都是用固定的IP地址，所有與該IP地址通信一開始都被轉發(fā)到移動主機的起始位置代理中。 缺點:(1)增加了通信延遲，因為需要先與起始位置進行聯(lián)系； 保證起始位置始終存在，否則無法聯(lián)系(2)使用了固定的起始位置 實體永久移動到一個其他網(wǎng)絡，每次聯(lián)系都經(jīng)過起始位置在分層設計中，網(wǎng)絡被劃分為一組域。最底層的域稱為葉域。每個域都擁有關聯(lián)的目錄節(jié)點，用來持續(xù)跟蹤域的實體。頂級域的目錄節(jié)點稱為根節(jié)點，它包括全部實體。

15、為了持續(xù)跟蹤實體的位置，每個目前位于域D中的實體都由一條在目錄節(jié)點N內的位置記錄來代表。位置記錄包含該實體當前在域中的位置。根節(jié)點擁有每個實體的位置記錄，其中每條位置記錄都存儲一個指向更低一層子域目錄節(jié)點的指針。實體可以有多個地址，如果實體分別在域D1和D2中擁有地址，那么同時包含D1和D2的最小域的目錄節(jié)點將包含兩個指針，每個 指針都指向 一個包含地 址的子域。查詢操作的實現(xiàn)查詢操作是在局部進行的，查詢區(qū)域可能逐步擴大，最壞的情況是搜索到達根節(jié)點。更新操作：插入和刪除插入方式：高級域指向低級域、顛倒的順序只有緩存數(shù)據(jù)很少發(fā)生變化時，采用緩存會變得很有效。假設移動實體E經(jīng)常在域D中移動，那么E

16、的當前地址是經(jīng)常改變的，但是有關E的信息不變的位置就是目錄節(jié)點D。在D中而不是其他任何節(jié)點中查找E的當前位置有是有意義的，這種方法被稱為指針緩存。原則上，從發(fā)起查詢的葉節(jié)點開始，一路上經(jīng)過的所有節(jié)點都可以緩存指向目錄節(jié)點D的引用。目錄節(jié)點D存儲E的實際地址而不是E所在的子域的指針。查找步驟：（1）查詢本地指針緩存,找到正確的目錄節(jié)點.（2）要求這個節(jié)點返回E的當前地址。案例：用戶在舊金山和洛杉磯之間移動如何找到最適合的目錄節(jié)點來存儲移動實體的當前地址？什么時候讓緩存項失效？分層定位服務存在的一個主要問題是根節(jié)點需要存儲所有實體的位置記錄并為每個實體處理請求。如果不采取特殊技術，根節(jié)點需要處理太

17、多的查找和更新請求，以至于它會成為瓶頸。解決方案：把根節(jié)點以及其他高層目錄節(jié)點劃分成多個子節(jié)點，每個子節(jié)點負責處理與定位服務支持的所有實體的特定子集相關的請求。出現(xiàn)的問題：在定位服務覆蓋的網(wǎng)絡中，在物理上如何放置每個子節(jié)點？ 方案一：集中放置子節(jié)點，各個節(jié)點相互保持近距離，這就可以用一臺并行計算機有效的實現(xiàn)根節(jié)點。 處理能力已經(jīng)足夠，但與根節(jié)點之間的網(wǎng)絡連接可能沒有足夠的能力來處理全部請求。 方案二：把子節(jié)點均勻的擴散到網(wǎng)絡中。 如果處理不當，這種方法有可能產生可擴展性問題。根節(jié)點已經(jīng)被劃分成多個子節(jié)點，現(xiàn)在需要解決的是如何分配合適的子節(jié)點負責該用戶？一種可能的解決方案是使用創(chuàng)建實體一種可能的

18、解決方案是使用創(chuàng)建實體E E的位置，如果根節(jié)點的一個的位置，如果根節(jié)點的一個子節(jié)點與創(chuàng)建子節(jié)點與創(chuàng)建E E的位置很近，那么它就負責處理根一級的、與的位置很近，那么它就負責處理根一級的、與E E相關相關的請求。但僅適用于實體停留在離創(chuàng)建它的位置的請求。但僅適用于實體停留在離創(chuàng)建它的位置很近很近的情況，若的情況，若實實體體移動到很遠的位置，那么問題還未得到解決。移動到很遠的位置，那么問題還未得到解決。n無引用對象的問題無引用對象的問題n引用計數(shù)引用計數(shù)n引用列表引用列表n標識不可到達標識不可到達實體實體1.無引用對象的問題原因：如果一個實體不再被引用，若不刪除就會浪費系統(tǒng)的資源。 在分布式系統(tǒng)中，

19、不能確定一個實體的引用是否存在，也不知道以后是否還會通過這個引用來訪問這個實體。分布式提供了一種自動刪除實體的功能：分布式垃圾收集器假設只要不存在遠程引用的對象就應該在系統(tǒng)中刪除；對象之間相互引用，導致對象循環(huán)引用，應該檢測到這種現(xiàn)象并刪除它們?？梢杂孟聢D來表示這種情況：2.引用計數(shù)原理：創(chuàng)立對象引用時，用于該對象的引用計數(shù)就遞增；在刪除引用時，引用計數(shù)就遞減，當計數(shù)為0就刪除該對象。2.1簡單的引用計數(shù) 在分布式系統(tǒng)中，這種方法產生的問題大多是由于通信的可靠性引起的。（假設對象把它的引用計數(shù)存儲在關聯(lián)的骨架中） 在創(chuàng)建引用和刪除引用時可能產生的問題：確認信息丟失，代理會重新發(fā)送信息，導致計數(shù)

20、多加或減。 解決方案：檢測重復信息，使用可靠的通信復制引用時產生的問題如圖（a）解決方案如圖（b），此外，在骨架確認它已經(jīng)知道引用的存在之前禁止進程刪除引用。傳遞引用現(xiàn)在需要三條信息，在大型分布式系統(tǒng)中很容易產生性能問題。2.2高級引用計數(shù) 簡單的分布式引用在遞增和遞減引用計數(shù)之間造成了一種競爭狀態(tài)。 改進：只采用遞減操作 加權引用計數(shù) 原理：每個對象擁有一個固定的總權數(shù)，在創(chuàng)建對象時，總權數(shù)連同一個部分權數(shù)一起存儲在與它關聯(lián)的骨架中，部分權數(shù)被初始化成總權數(shù)。（假設信息不回丟失或多次發(fā)送）創(chuàng)建新的遠程引用如圖（b），復制遠程引用如圖（c）在刪除引用時，一條遞減消息被發(fā)送給對象的骨架，然后對象

21、的骨架會從總權數(shù)中減去被刪除引用的部分權數(shù)。一旦總權數(shù)為0，就可以安全的刪除對象。加權引用計數(shù)存在的問題：只能創(chuàng)建有限的引用數(shù)量。解決方案：使用間接權數(shù)使用間接權數(shù)的缺點：如果骨架S的總權數(shù)為1，那么這種方法與創(chuàng)建從進程P2到進程P1的轉發(fā)指針相同。以此類推，如果需要傳遞它的引用，那么它必須創(chuàng)建另一個轉發(fā)指針。當指針連鏈過長時會嚴重地降低性能，同時，指針鏈容易受到故障的影響。使用世代引用計數(shù)假定每個遠程引用都由（代理，骨架）值對構成，骨架和對象位于相同的地址空間中。每個代理還存儲著一個復制計數(shù)器和一個世代標志，復制計數(shù)器用來記錄代理被復制的次數(shù)，世代標志代表的是世代數(shù)。3.引用列表原理：讓骨架

22、持續(xù)跟蹤引用它的代理，骨架不是對引用計進行數(shù)，而是維護一張明確的列表，列表中列出了所有指向它的代理。特征：如果一個代理被列出，那么把它添加到引用表中不會產生任何影響。刪除列表中不存在的代理也不會產生任何影響。添加或刪除代理都是冪等操作。冪等操作的特征是它們在不影響最終結果的情況下重復進行。優(yōu)點：（1）不再需要可靠的通訊，也不需要檢測和丟棄重復消息。（只需要對插入和刪除操作進行確認）。 （2）進程發(fā)生故障時，更容易保持引用表的一致性。缺點：如果骨架需要跟蹤很多引用的話，引用列表的規(guī)?？赡軙乐氐臄U張。4.標識不可到達實體 分布式系統(tǒng)中存在循環(huán)引用的情況，實體相互引用，但是它們無法從根集中的一個實體到達，這樣的實體也要刪除?；诟櫟睦占和ㄟ^查看哪些實體能夠從根集實體到達并刪除無法到達的實體。4.1簡單跟蹤跟蹤方式：標記-清除收集器 標記階段：使用源于根集實體的引用鏈對實體進行跟蹤，能夠到達的實體被作上標記。 清除