【正文】 點(diǎn)值的一半；把原最小節(jié)點(diǎn)上值小于現(xiàn)最小節(jié)點(diǎn)值的索引記錄，轉(zhuǎn)移到現(xiàn)最小節(jié)點(diǎn)；ELSEFOR i=N to (k+1) EACH LNIA[i] in GHN 把每個(gè)節(jié)點(diǎn)值從大到小依次賦給比它大的那個(gè)；j=i+1。LNIA[j+1]= LNIA[j]+( LNIA[j] LNIA[k])。轉(zhuǎn)移LNIA[j+2]上值小于最后加入節(jié)點(diǎn)值的定位信息到最后加入節(jié)點(diǎn)；更新最后加入節(jié)點(diǎn)和最小節(jié)點(diǎn)信息；總節(jié)點(diǎn)數(shù)＋1；當(dāng)某個(gè)宿主結(jié)點(diǎn)要退出系統(tǒng)時(shí)，把最后加入的節(jié)點(diǎn)地址i改為當(dāng)前要退出的節(jié)點(diǎn)的地址，并把i上維護(hù)的信息遷移到比它地址大的第一個(gè)結(jié)點(diǎn)上。要退出的節(jié)點(diǎn)上維護(hù)的信息遷移到i上。如果要退出的節(jié)點(diǎn)為新加入的結(jié)點(diǎn)，則把在它之前加入的結(jié)點(diǎn)作為最后加入的結(jié)點(diǎn)重復(fù)上述步驟。LLN節(jié)點(diǎn)是副本定位查詢?nèi)肟?，?dāng)一個(gè)LLN接收到對(duì)數(shù)據(jù)元LDN副本的查詢請(qǐng)求后，首先查詢域內(nèi)是否有LDN的本地副本信息，如果有并且個(gè)數(shù)滿足要求，則自己返回對(duì)應(yīng)PRN信息；否則通過(guò)域間動(dòng)態(tài)均衡映射策略得到LDN的宿主節(jié)點(diǎn)GHN，到GHN上查詢LDN的宿主目錄信息，得到存儲(chǔ)有LDN副本信息的全部本地定位節(jié)點(diǎn)：；后到上查詢LDN的域內(nèi)副本信息，返回各副本物理名。：把復(fù)雜的網(wǎng)絡(luò)拓?fù)鋭澐譃橛騼?nèi)、域間兩部分，根據(jù)局部性原理，采用不同的定位方法進(jìn)行映射。LLN節(jié)點(diǎn)有效支持域內(nèi)副本的本地查詢。通過(guò)GHN與LLN節(jié)點(diǎn)的配合完成域間副本信息的定位，有效的完成多個(gè)副本信息在域間的查詢。：域內(nèi)副本每次使用時(shí)動(dòng)態(tài)讀入表中，并且定時(shí)刷新，保證數(shù)據(jù)的實(shí)時(shí)性和準(zhǔn)確性。域內(nèi)每個(gè)節(jié)點(diǎn)記錄本機(jī)副本信息，本域的LLN發(fā)生故障失靈時(shí)，系統(tǒng)根據(jù)每個(gè)節(jié)點(diǎn)信息，可重組域內(nèi)副本映射信息，有效的防止了諸如DSRL系統(tǒng)的單點(diǎn)失效問(wèn)題。：采用分布式副本定位機(jī)制，使用動(dòng)態(tài)均衡映射技術(shù)，將副本信息均衡的定位在各宿主節(jié)點(diǎn)上，并可以動(dòng)態(tài)更新記錄，對(duì)數(shù)據(jù)元以及副本數(shù)目的可擴(kuò)展性較好的支持。DDRL方法對(duì)LLN以及GHN節(jié)點(diǎn)的數(shù)目完全沒(méi)有限制，可根據(jù)系統(tǒng)需要?jiǎng)討B(tài)加入和撤銷GHN節(jié)點(diǎn)。這種情況下系統(tǒng)中只需要移動(dòng)很少的一部分相應(yīng)的定位信息，其他的宿主節(jié)點(diǎn)和副本定位信息不變。：采用的動(dòng)態(tài)映射方法，簡(jiǎn)單易實(shí)現(xiàn)。又可以均衡的分布副本信息，與平衡二叉樹(shù)、二叉樹(shù)、Huffman編址等方法相比，實(shí)現(xiàn)起來(lái)要簡(jiǎn)易的多。提高了運(yùn)行效率。有效保持了動(dòng)態(tài)均衡的特性。本章圍繞怎樣在復(fù)雜的網(wǎng)絡(luò)中快速查詢副本問(wèn)題，首先研究了DSRL分層定位模型，針對(duì)這種模型的實(shí)現(xiàn)方法以及評(píng)價(jià)。在DSRL結(jié)構(gòu)的啟發(fā)下，提出了一種基于域的思想的改進(jìn)的分布式動(dòng)態(tài)副本定位方法DDRL，并通過(guò)對(duì)DDRL實(shí)現(xiàn)過(guò)程的具體介紹，分析了DDRL定位機(jī)制的有效可行性。5數(shù)據(jù)復(fù)制管理系統(tǒng)原型設(shè)計(jì)實(shí)現(xiàn)原型系統(tǒng)采用C++開(kāi)發(fā)。測(cè)試的環(huán)境是在同一個(gè)局域網(wǎng)內(nèi)的多臺(tái)節(jié)點(diǎn)機(jī)上進(jìn)行。服務(wù)器、客戶端兩臺(tái)機(jī)器進(jìn)行相互訪問(wèn)。所有機(jī)器通過(guò)100Mbps以太網(wǎng)進(jìn)行連接。每臺(tái)機(jī)器上的操作系統(tǒng)可互不相同，系統(tǒng)實(shí)現(xiàn)不同系統(tǒng)的互操作。原型系統(tǒng)實(shí)驗(yàn)的硬、。 系統(tǒng)實(shí)驗(yàn)的軟硬件環(huán)境硬件環(huán)境類別臺(tái)式微機(jī)CPUPentium(R) 4 內(nèi)存512 MB硬盤80 GB軟件環(huán)境操作系統(tǒng)Windows XP ( Professional )開(kāi)發(fā)工具Visual C++ 本原型系統(tǒng)分為客戶端和服務(wù)器端兩部分，每個(gè)節(jié)點(diǎn)既可以是服務(wù)器又可以是客戶端，資源請(qǐng)求方即為客戶端，資源提供方為服務(wù)器端。系統(tǒng)初始狀態(tài)均默認(rèn)為服務(wù)器狀態(tài)。當(dāng)某個(gè)節(jié)點(diǎn)需要請(qǐng)求資源時(shí)，自動(dòng)轉(zhuǎn)換為客戶端。并且動(dòng)態(tài)選擇服務(wù)器端，進(jìn)行資源的訪問(wèn)與副本的創(chuàng)建。，描述了兩種節(jié)點(diǎn)不同角色之間的域內(nèi)定位副本、創(chuàng)建副本的詳細(xì)過(guò)程。其中客戶端、服務(wù)器采用同一個(gè)程序，根據(jù)不同需要選擇每個(gè)節(jié)點(diǎn)是服務(wù)器還是客戶端。達(dá)到了完全對(duì)等的域內(nèi)副本管理效果。刷新模塊讀入本地磁盤文件數(shù)據(jù)庫(kù)服務(wù)器IP創(chuàng)建模塊查詢關(guān)鍵字創(chuàng)建副本定位模塊共享文件網(wǎng)絡(luò)文件服務(wù)器端數(shù)據(jù)庫(kù)本地磁盤文件注冊(cè)表注冊(cè)表定位模塊共享文件網(wǎng)絡(luò)文件刷新模塊邏輯與物理地址映射表返回創(chuàng)建消息客戶端關(guān)鍵字創(chuàng)建副本 系統(tǒng)結(jié)構(gòu)圖，實(shí)現(xiàn)對(duì)本地資源的查詢和更新。并且用戶可以從界面動(dòng)態(tài)選擇其共享到網(wǎng)絡(luò)中的文件夾，然后動(dòng)態(tài)刷新數(shù)據(jù)庫(kù)中的信息。當(dāng)文件夾中添加、刪除文件等事件發(fā)生時(shí)即自動(dòng)觸發(fā)數(shù)據(jù)庫(kù)刷新消息。 資源注冊(cè)信息表字段Data_idData_fileNameData_ipData_path，客戶端可以動(dòng)態(tài)選擇服務(wù)器，請(qǐng)求資源。通過(guò)設(shè)定服務(wù)器端IP來(lái)決定選擇哪個(gè)服務(wù)器端訪問(wèn)資源。有兩種選擇可以獲得服務(wù)器端資源：第一，把服務(wù)器端共享文件夾中的資源注冊(cè)到本地?cái)?shù)據(jù)庫(kù)，查看有沒(méi)有客戶端需要的資源。第二，在客戶端輸入需要的資源名，發(fā)送給服務(wù)器端，服務(wù)器反饋信息，通知客戶端請(qǐng)求的資源是否存在，并告知資源的具體位置。然后客戶端通過(guò)與服務(wù)器建立的Socket連接，下載所需資源。分別建立客戶和服務(wù)器端類，封裝其基本操作，在主窗口建立m_Client,m_Server分別封裝客戶端類CClient, 和服務(wù)器端類CServer的對(duì)象。服務(wù)器對(duì)象m_ServerDataBaseDataBase創(chuàng)建套接字socket發(fā)出連接請(qǐng)求connect接受連接請(qǐng)求acceptBind綁定socket監(jiān)聽(tīng)狀態(tài)listen創(chuàng)建套接字socket通訊send/recv客戶端對(duì)象m_Client 客戶端與服務(wù)器通訊圖，實(shí)現(xiàn)域內(nèi)所有資源邏輯文件名到物理文件名的映射；客戶端資源訪問(wèn)時(shí)，首先查找隨機(jī)指定的服務(wù)器，指定服務(wù)器不能滿足資源需求時(shí)，再求助于域內(nèi)服務(wù)器的信息登記表，查詢資源所在的具體服務(wù)器的IP地址?？蛻舳烁鶕?jù)得到的IP地址，連接相關(guān)服務(wù)器進(jìn)行資源訪問(wèn)。本原型系統(tǒng)分為客戶端和服務(wù)器端兩部分，每個(gè)節(jié)點(diǎn)既可以是服務(wù)器又可以是客戶端，資源請(qǐng)求方即為客戶端，資源提供方為服務(wù)器端。為了減少代碼重用，提高程序的可讀性，把系統(tǒng)劃分為資源管理、更新控制、副本創(chuàng)建和副本定位四個(gè)不同的模塊對(duì)復(fù)制管理器的功能分類描述。，描述了此數(shù)據(jù)復(fù)制管理系統(tǒng)的各個(gè)模塊，以及每個(gè)模塊實(shí)現(xiàn)的功能。復(fù)制管理器資源管理模塊服務(wù)器IP資源信息注冊(cè)表更新控制模塊副本創(chuàng)建模塊副本定位模塊本地資源網(wǎng)絡(luò)資源查詢控制傳輸控制本地?cái)?shù)據(jù)服務(wù)器端 系統(tǒng)單點(diǎn)結(jié)構(gòu)圖資源管理模塊負(fù)責(zé)對(duì)服務(wù)器IP地址、資源信息定義、注冊(cè)表組織等資源相關(guān)模塊進(jìn)行分別管理。下面是對(duì)三個(gè)功能的分類介紹?？蛻舳诵枰W(wǎng)絡(luò)資源時(shí)，會(huì)選擇服務(wù)器進(jìn)行通訊。服務(wù)器IP地址模塊正是對(duì)客戶輸入的IP地址進(jìn)行解析，然后發(fā)送給下層。下層根據(jù)其獲得的IP地址，啟動(dòng)TCP/IP協(xié)議與相應(yīng)的服務(wù)器進(jìn)行連接通訊?？蛻舳诵枰W(wǎng)絡(luò)提供資源時(shí)，會(huì)向服務(wù)器發(fā)送資源請(qǐng)求消息，服務(wù)器根據(jù)當(dāng)前自己的資源狀況作出相應(yīng)的反饋信息?？蛻舳耸艿娇隙ǖ姆答佇畔⒑螅蚍?wù)器發(fā)送傳輸文件的請(qǐng)求，服務(wù)器如同意則建立連接通訊進(jìn)行資源下載。為了便于對(duì)方識(shí)別本地發(fā)出信息和準(zhǔn)確的識(shí)別收到的信息，必須事先約定客戶端的請(qǐng)求信息以及服務(wù)器的應(yīng)答信息的格式。資源信息類正是管理保證服務(wù)器與客戶端正確通訊的信息格式。每個(gè)節(jié)點(diǎn)擁有自己的共享文件夾指定本地共享到網(wǎng)絡(luò)上的資源，通過(guò)小型數(shù)據(jù)庫(kù)記錄這些資源注冊(cè)信息。當(dāng)資源被增加、刪除、修改時(shí)促觸發(fā)更新控制消息，刷新數(shù)據(jù)庫(kù)中資源登記信息。注冊(cè)表管理注冊(cè)資源的格式，注冊(cè)模式，以及資源在數(shù)據(jù)庫(kù)中的存在形式。每個(gè)節(jié)點(diǎn)擁有自己的共享文件夾指定本地共享到網(wǎng)絡(luò)上的資源。共享文件夾可以根據(jù)用戶的需要?jiǎng)討B(tài)更改；共享文件夾中的文件可以根據(jù)用戶的需要?jiǎng)討B(tài)增刪；本地資源不滿足用戶需求時(shí)，需要通過(guò)網(wǎng)絡(luò)連接，下載服務(wù)器資源到共享文件夾。以上幾類共享資源的改變都需要通過(guò)某種途徑通知數(shù)據(jù)庫(kù)以及界面注冊(cè)表，以保持實(shí)時(shí)的數(shù)據(jù)一致性。更新控制類封裝了對(duì)發(fā)生這些事件時(shí)，觸發(fā)的反饋策略函數(shù)。這些函數(shù)對(duì)發(fā)生的共享資源的更新事件，作出響應(yīng)和相關(guān)處理。當(dāng)本地資源無(wú)法滿足用戶需求時(shí)，需要連接相關(guān)服務(wù)器。通過(guò)直接指定文件名發(fā)送到服務(wù)器端查找資源是否存在、或者把服務(wù)器資源注冊(cè)表下載到本地然后點(diǎn)擊下載資源，兩種方法進(jìn)行資源訪問(wèn)。當(dāng)選擇第二種資源訪問(wèn)方法時(shí)，本地注冊(cè)表就同時(shí)維護(hù)了本地資源和網(wǎng)絡(luò)資源兩種信息。這時(shí)刷新控制類除了要及時(shí)響應(yīng)本地資源的更新以外還要維護(hù)網(wǎng)絡(luò)資源的增、刪、改的更新控制。本系統(tǒng)主要實(shí)現(xiàn)了域內(nèi)副本創(chuàng)建功能，采用快速傳播策略，即：客戶端請(qǐng)求資源訪問(wèn)時(shí)，一律把所需資源從服務(wù)器下載到本地再進(jìn)行直接訪問(wèn)。采用這種策略主要考慮到域內(nèi)各節(jié)點(diǎn)一般都屬于局域網(wǎng)內(nèi)的范疇，下載資源對(duì)帶寬和訪問(wèn)時(shí)間的消耗要求都比較低，不會(huì)阻止或者阻礙網(wǎng)絡(luò)的暢通。反而如果不直接下載，會(huì)造成大量資源的相互訪問(wèn)；或者是對(duì)同一資源的超負(fù)荷訪問(wèn)，這樣可能造成系統(tǒng)訪問(wèn)瓶頸，增加網(wǎng)絡(luò)傳輸負(fù)荷，從而影響了資源訪問(wèn)效率。副本創(chuàng)建模塊管理客戶端請(qǐng)求資源訪問(wèn)時(shí)，從服務(wù)器下載資源的過(guò)程?？蛻舳诵枰W(wǎng)絡(luò)提供資源時(shí)，會(huì)向服務(wù)器發(fā)送資源請(qǐng)求消息，服務(wù)器根據(jù)當(dāng)前自己的資源狀況作出相應(yīng)的反饋。客戶端受到肯定的反饋信息后，向服務(wù)器發(fā)送傳輸文件的請(qǐng)求，服務(wù)器如同意則建立連接通訊進(jìn)行資源下載。這個(gè)通訊過(guò)程以及期間產(chǎn)生的一系列可能事件都是由副本創(chuàng)建模塊的傳輸控制方面的函數(shù)進(jìn)行管理。S：客戶端結(jié)點(diǎn)D：資源名T：時(shí)間閾值L：負(fù)載閾值T`：訪問(wèn)D次數(shù)L`：當(dāng)前負(fù)載NNNYYY轉(zhuǎn)到域間副本創(chuàng)建環(huán)節(jié)域內(nèi)存在在S上創(chuàng)建D的副本S對(duì)D的副本請(qǐng)求T`TL`L放棄D副本創(chuàng)建，直接訪問(wèn)開(kāi)始結(jié)束 副本創(chuàng)建流程圖上一小節(jié)提到客戶端可以通過(guò)直接指定文件名發(fā)送到服務(wù)器查找資源是否存在、或者把服務(wù)器資源注冊(cè)表下載到本地然后點(diǎn)擊下載資源，兩種方法進(jìn)行資源訪問(wèn)。查詢控制模塊就是處理采用第一種資源訪問(wèn)方法產(chǎn)生的查詢控制方面的事件?？蛻舳舜_定資源存在于服務(wù)器時(shí)，通過(guò)傳輸控制模塊對(duì)資源進(jìn)行從服務(wù)器到客戶端的傳輸。副本定位解決的問(wèn)題是怎樣找到所需資源的具體物理位置。本系統(tǒng)主要針對(duì)域內(nèi)副本定位問(wèn)題，給出本地資源、服務(wù)器資源的副本定位機(jī)制。副本定位模塊完成資源定位方面的功能。對(duì)于本地資源，每個(gè)節(jié)點(diǎn)擁有一個(gè)數(shù)據(jù)庫(kù)注冊(cè)本地共享到網(wǎng)絡(luò)上的資源，并通過(guò)更新控制模塊保持資源的實(shí)時(shí)一致性。根據(jù)第四章給出的域內(nèi)副本定位方法，每個(gè)域的服務(wù)器維護(hù)一張域內(nèi)信息登記表，實(shí)現(xiàn)域內(nèi)所有資源邏輯文件名到物理文件名的映射；客戶端資源訪問(wèn)時(shí)，首先查找隨機(jī)指定的服務(wù)器，指定服務(wù)器不能滿足資源需求時(shí)，求助于域內(nèi)服務(wù)器的信息登記表，查詢資源所在的具體服務(wù)器的IP地址。NYYN副本請(qǐng)求找到信息查詢本地LLN查詢對(duì)應(yīng)GHN找到相應(yīng)LLN返回PRN信息本地復(fù)制到充足數(shù)量充足開(kāi)始結(jié)束 DDRL系統(tǒng)副本定位流程圖為了對(duì)動(dòng)態(tài)區(qū)間映射原算法及改進(jìn)算法進(jìn)行測(cè)試，現(xiàn)給出其測(cè)試環(huán)境如下。1. 主機(jī)：Intel Pentium 4, 2. 操作系統(tǒng)：Microsoft Windows XP Professional3. 測(cè)試環(huán)境：VC 4. 網(wǎng)絡(luò)：，按照第三章、第四章中的算法實(shí)現(xiàn)，給出在不同網(wǎng)絡(luò)環(huán)境下進(jìn)行測(cè)試的結(jié)果，從而可以清晰的檢測(cè)出本文給出算法和參照算法的性能差異。 環(huán)境配置參數(shù)實(shí)驗(yàn)參數(shù)參數(shù)值域內(nèi)站點(diǎn)之間的帶寬2000Mbps域間站點(diǎn)之間的帶寬100Mbps～1000Mbps文件訪問(wèn)頻率閾值20節(jié)點(diǎn)數(shù)目100網(wǎng)絡(luò)延遲20ms磁盤訪問(wèn)時(shí)間19ms以100個(gè)PC機(jī)器作為節(jié)點(diǎn)構(gòu)建一個(gè)P2P實(shí)驗(yàn)網(wǎng)絡(luò)。系統(tǒng)初始保持一份副本，設(shè)定文件訪問(wèn)頻率閾值為20，表示當(dāng)文件的訪問(wèn)頻率超過(guò)20時(shí)觸發(fā)副本創(chuàng)建模塊，逐漸增加文件的訪問(wèn)頻率，測(cè)試文件的平均訪問(wèn)延遲和平均副本數(shù)。 訪問(wèn)延遲隨訪問(wèn)頻率的變化 副本隨訪問(wèn)頻率的變化情況，初始階段，文件只有一個(gè)副本，平均訪問(wèn)延遲較大，隨著訪問(wèn)熱度的提升，副本隨之增加，表現(xiàn)在明顯降低訪問(wèn)延遲，但副本數(shù)達(dá)到一定程度后，副本總數(shù)和訪問(wèn)延遲維持在一個(gè)穩(wěn)定的水平，副本沒(méi)有無(wú)謂的增加。下面以10個(gè)節(jié)點(diǎn)為例，比較分析域內(nèi)副本衍生和域間副本創(chuàng)建相結(jié)合的副本創(chuàng)建策略與快速擴(kuò)散策略以及瀑布策略[16]訪問(wèn)200次文件所花費(fèi)的全部時(shí)間，以及200次文件訪問(wèn)網(wǎng)絡(luò)傳輸節(jié)省的總時(shí)間。 200次文件訪問(wèn)所花費(fèi)的全部時(shí)間，本文提出的域內(nèi)副本衍生和域間副本創(chuàng)建相結(jié)合的副本創(chuàng)建策略總是能保持最快的訪問(wèn)響應(yīng)時(shí)間和最低的帶寬消耗。在創(chuàng)建相同數(shù)目副本的條件下比較三種策略，域內(nèi)副本衍生和域間副本創(chuàng)建相結(jié)合的策略比其他兩種策略能節(jié)省更多的網(wǎng)絡(luò)傳輸時(shí)間，給用戶帶來(lái)更快的文件訪問(wèn)速度。所以，此策略在更新較少的數(shù)據(jù)網(wǎng)格環(huán)境中是系統(tǒng)副本創(chuàng)建策略的較佳選擇。 200次文件訪問(wèn)網(wǎng)絡(luò)傳輸節(jié)省時(shí)間(1)負(fù)載均衡性設(shè)網(wǎng)格系統(tǒng)中有N個(gè)宿主節(jié)點(diǎn)和I個(gè)邏輯文件，各個(gè)宿主結(jié)點(diǎn)維護(hù)的最大邏輯文件數(shù)為n，最小邏輯文件數(shù)為P，則。特性說(shuō)明：由第4章可知，系統(tǒng)初始分配情況下，每個(gè)宿主節(jié)點(diǎn)上維護(hù)的邏輯文件個(gè)數(shù)為或者，即要么每個(gè)宿主節(jié)點(diǎn)上維護(hù)的邏輯文件數(shù)相等都為，要么一部分是另一部分是，顯然滿足負(fù)載均衡要求。新節(jié)點(diǎn)加入的規(guī)則是對(duì)現(xiàn)有的節(jié)點(diǎn)從小到大依次進(jìn)行中間插入的規(guī)則，由于宿主節(jié)點(diǎn)總數(shù)有所增加，但是沒(méi)有增加到原來(lái)結(jié)點(diǎn)的2倍，所以被二次分割的節(jié)點(diǎn)上維護(hù)的信息量一定小于或等于，沒(méi)有被二次分割的節(jié)點(diǎn)上維護(hù)的信息量小于或等于2P。(2)動(dòng)態(tài)遷移性設(shè)網(wǎng)格系統(tǒng)中有N個(gè)宿主節(jié)點(diǎn)和I個(gè)邏輯文件，當(dāng)有節(jié)點(diǎn)加入時(shí)，索引信息發(fā)生遷移的邏輯文件個(gè)數(shù)小于或等于。節(jié)點(diǎn)退出系統(tǒng)時(shí)，索引信息發(fā)生遷移的邏輯文件個(gè)數(shù)小于或等于3。特性說(shuō)明：新節(jié)點(diǎn)加入系統(tǒng)時(shí)，只是把此節(jié)點(diǎn)維護(hù)的信息量進(jìn)行了遷移，所以一定滿足要求。當(dāng)有節(jié)點(diǎn)退出系統(tǒng)時(shí)，最后加入的節(jié)點(diǎn)上維護(hù)的信息量一定滿足小于或等于，而當(dāng)前要退出的節(jié)點(diǎn)所維護(hù)的信息量一定滿足小于或等于2，所以節(jié)點(diǎn)退出時(shí)發(fā)生遷移的邏輯文件個(gè)數(shù)小于或等于3。(3)可擴(kuò)展性由第4章宿主節(jié)點(diǎn)的