FRONT互聯(lián)網(wǎng)文件存儲(chǔ)與共享系統(tǒng)

1、FRONT互聯(lián)網(wǎng)文件存儲(chǔ)與共享系統(tǒng)劉斌 劉忠義網(wǎng)絡(luò)實(shí)驗(yàn)室夏冰數(shù)據(jù)庫(kù)實(shí)驗(yàn)室朱彬軟工實(shí)驗(yàn)室摘要 本文受FFreeneet項(xiàng)目的啟啟發(fā)，設(shè)計(jì)并并實(shí)現(xiàn)了一個(gè)個(gè)具備存儲(chǔ)和和共享功能的的互聯(lián)網(wǎng)分布布式文件系統(tǒng)統(tǒng)Filees Reiiable ON innTerneet (FRONNT)。FRRONT在操操作系統(tǒng)的文文件系統(tǒng)之上上提供了一層層新的虛擬文文件系統(tǒng)，上上傳到FROONT系統(tǒng)的的文件被適當(dāng)當(dāng)?shù)厍蟹植⒎址峙涞骄W(wǎng)絡(luò)中中某些節(jié)點(diǎn)上上。通過文件件分塊表或文文件塊復(fù)制和和緩存，用戶戶得以利用FFRONT實(shí)實(shí)現(xiàn)可用高效效的文件訪問問。FRONNT系統(tǒng)使用用磁盤配額和和固定共享空空間比例的技技術(shù)來配合這這個(gè)虛擬

2、文件件系統(tǒng)，來解解決P2P應(yīng)應(yīng)用中的Frree riider問題題。Fronnt使用Raandom Walk算算法進(jìn)行文件件定位，并且且在網(wǎng)路規(guī)模模變化時(shí)保持持系統(tǒng)中文件件的高可用性性和高性能。實(shí)實(shí)驗(yàn)表明本文文實(shí)現(xiàn)FROONT系統(tǒng)運(yùn)運(yùn)行正確，性性能有待進(jìn)一一步實(shí)驗(yàn)。關(guān)鍵詞 分布布式系統(tǒng)、PP2P、網(wǎng)絡(luò)絡(luò)存儲(chǔ)、文件件共享介紹 工作動(dòng)機(jī)今天互聯(lián)網(wǎng)上已已經(jīng)有許多成熟的的P2P文件件共享系統(tǒng)，例例如BT、迅迅雷、Mazze等，它們們的存在極大大地豐富了普普通網(wǎng)民可以以訪問的互聯(lián)聯(lián)網(wǎng)資源。這這些系統(tǒng)著重重于將互聯(lián)網(wǎng)網(wǎng)上的文件以以P2P的方方式共享給更更多用戶。幾乎在在這些P2PP共享協(xié)議在在開始被研究究

3、和應(yīng)用的同同時(shí)（20001年），學(xué)學(xué)術(shù)界也曾熱熱烈地討論過過在互聯(lián)網(wǎng)絡(luò)絡(luò)上提供開放的存儲(chǔ)服服務(wù)的分布式式文件系統(tǒng)，一一些著名的系系統(tǒng)包括CFFS、Gnuutellaa、FreeeNet等。今今天仍有一些些個(gè)人和組織織在這些協(xié)議議的基礎(chǔ)上開開發(fā)擴(kuò)展和應(yīng)應(yīng)用。但是由由于版權(quán)、用用戶激勵(lì)、網(wǎng)網(wǎng)絡(luò)封禁等等等原因，這些些系統(tǒng)一直停停留在研究階階段或者很小小規(guī)模的應(yīng)用用。隨著網(wǎng)絡(luò)的普及及和計(jì)算服務(wù)務(wù)的無所不在在，普通用戶戶開始在一個(gè)個(gè)以上的計(jì)算算機(jī)上進(jìn)行文文件存??；并并且越來越多多的群體或組織的成員參與到互聯(lián)網(wǎng)網(wǎng)上的協(xié)作和共共享。這樣的的需求可以使使用分布式的文件存儲(chǔ)和共共享技術(shù)來滿滿足。本文是幾位位研究

4、生在學(xué)學(xué)習(xí)分布式系系統(tǒng)課程之后后的一次嘗試試，希望開發(fā)發(fā)一個(gè)具有一一定可擴(kuò)展性性的分布式文文件系統(tǒng)FRRONT（FFiles Reliaable OON inTTernett），用戶可以使使用這個(gè)系統(tǒng)統(tǒng)實(shí)現(xiàn)高效的的文件存儲(chǔ)與訪訪問。 本文內(nèi)容FRONT文件件系統(tǒng)最主要要受到FreeeNet6項(xiàng)目的的啟發(fā)。FRRONT系統(tǒng)統(tǒng)無須依托任任何基礎(chǔ)設(shè)施施，當(dāng)文件存存儲(chǔ)或者共享享的需求產(chǎn)生生時(shí)，它即可可從一臺(tái)主機(jī)機(jī)的規(guī)模開始始擴(kuò)展，在網(wǎng)網(wǎng)絡(luò)規(guī)模和共共享空間逐漸漸擴(kuò)大的同時(shí)時(shí)，它可以持持續(xù)提供高可可用、高性能能的文件存儲(chǔ)儲(chǔ)與共享服務(wù)務(wù)。FRONNT采用用戶戶磁盤配額的的方式，讓每每一臺(tái)主機(jī)向向整個(gè)系統(tǒng)提提

5、供存儲(chǔ)空間間，并通過控控制共享空間間與用戶需求求空間的比例例來避免freee rideer問題。FFRONT系系統(tǒng)對(duì)用戶上上傳的文件進(jìn)進(jìn)行適當(dāng)?shù)厍星蟹郑怪成錇椴僮飨迪到y(tǒng)的文件系系統(tǒng)之上的虛虛擬文件系統(tǒng)統(tǒng)Frontt VFS中中的文件。文文件分塊的設(shè)設(shè)計(jì)讓用戶可可以上傳更大大的文件，并并且流行的文文件塊將被分配到更更多的機(jī)器上上，帶來更高高的訪問性能能。新的一層層虛擬文件系系統(tǒng)還造成了用戶對(duì)對(duì)磁盤空間使使用的不透明明性，又一次次保證了客戶戶端在使用系系統(tǒng)的同時(shí)提提供必要的服服務(wù)。在文件分塊后，系系統(tǒng)中需要存存儲(chǔ)的數(shù)據(jù)包包括文件的分分塊表和文件件塊兩種類型型。文件分塊表表使用“發(fā)布者用戶戶空間

6、”上的路徑來定位位，文件塊使使用對(duì)數(shù)據(jù)內(nèi)內(nèi)容的哈希來來定位。為了了提供高可用用性和高性能能，F(xiàn)RONNT在文件塊塊的級(jí)別在系系統(tǒng)中實(shí)現(xiàn)了了復(fù)制和緩存存。FRONNT對(duì)于局域域網(wǎng)構(gòu)成的網(wǎng)網(wǎng)絡(luò)還做了特別的的優(yōu)化處理，讓處在同一個(gè)以太網(wǎng)絡(luò)內(nèi)的本地用戶高效地利用網(wǎng)絡(luò)，并降低對(duì)整體網(wǎng)絡(luò)的負(fù)擔(dān)。另外，F(xiàn)RONT系統(tǒng)中節(jié)點(diǎn)的通訊組織方式提供了高效的文件查找功能。這些都將在下面的章節(jié)中系統(tǒng)介紹。下文的主要內(nèi)容容：第II部分描描述了Froont文件系系統(tǒng)對(duì)于應(yīng)用用場(chǎng)景的假設(shè)設(shè)，并分析在在假設(shè)情況下下的文件系需需要解決的問問題。第IIII部分是對(duì)對(duì)Frontt文件系統(tǒng)的的結(jié)構(gòu)設(shè)計(jì)。第第IV部分是是本文的主要要部分

7、，介紹紹了開發(fā)Frront文件件系統(tǒng)的細(xì)節(jié)節(jié)。第V部分分講述了Frront文件件系統(tǒng)的運(yùn)行行情況，分析析對(duì)比了與其其他文件系統(tǒng)統(tǒng)的區(qū)別和特特點(diǎn)。最后第第VI部分是是對(duì)本文工作作的總結(jié)和展展望。假設(shè)和問題我們基于互聯(lián)網(wǎng)網(wǎng)上的存儲(chǔ)和和共享需求設(shè)設(shè)計(jì)并實(shí)現(xiàn)了了Frontt網(wǎng)絡(luò)文件系系統(tǒng)，為互聯(lián)聯(lián)網(wǎng)用戶提供供了高效可靠靠的文件服務(wù)務(wù)。它適用于在下文文定義的一些些假設(shè)情況，我們認(rèn)為這這些假設(shè)有較較強(qiáng)的普遍性性和適應(yīng)性，滿滿足了很多應(yīng)應(yīng)用需求。這這些假設(shè)包括括以下幾點(diǎn)：互聯(lián)網(wǎng)中存在多多個(gè)節(jié)點(diǎn)，無無論它們是否否鄰近。它們們?cè)敢夤餐M織一個(gè)個(gè)文件存儲(chǔ)和和共享平臺(tái)。這個(gè)平臺(tái)可以選擇由預(yù)先定義的用戶組成，與Int

8、ernet上可能存在的其他front網(wǎng)絡(luò)沒有交互。每個(gè)參與的節(jié)點(diǎn)點(diǎn)提供存儲(chǔ)空空間和一定的的網(wǎng)絡(luò)帶寬。每個(gè)節(jié)點(diǎn)的空間組合起來構(gòu)成全局大容量的存儲(chǔ)共享空間。節(jié)點(diǎn)在自己的文件需要的容量之外還能夠提供一定比例的“服務(wù)空間”，用于存儲(chǔ)全局的其他文件，為別人提供服務(wù)。文件系統(tǒng)的文件件發(fā)布和下載載對(duì)于用戶來來說好像本地地的一樣。節(jié)點(diǎn)上的用用戶不用關(guān)心心文件傳輸?shù)牡氖虑?，包括括文件?nèi)容從從哪里獲得、發(fā)發(fā)往哪里。分分布式系統(tǒng)數(shù)數(shù)據(jù)復(fù)制和協(xié)協(xié)議通訊對(duì)用用戶都是不可可見的。一些節(jié)點(diǎn)組成的的分布式網(wǎng)絡(luò)絡(luò)中。發(fā)布和和下載的需求求并不一定是是對(duì)稱的。例例如在一個(gè)極端情況下，一一個(gè)網(wǎng)絡(luò)中總是由一個(gè)節(jié)節(jié)點(diǎn)在發(fā)布（上上傳）文件

9、，其其他節(jié)點(diǎn)都是是不同需要的的下載者。文件系統(tǒng)提供的的語義是只讀讀的。文件發(fā)發(fā)布后即可由由他人獲得，但不可修改。向Front網(wǎng)網(wǎng)絡(luò)上發(fā)布的的文件可能很很大，甚至大大于本地節(jié)點(diǎn)點(diǎn)提供的共享享空間容量。但但只要froont網(wǎng)絡(luò)平平臺(tái)上還有空空間，它就應(yīng)應(yīng)該上傳成功功。本文需要設(shè)計(jì)一一個(gè)網(wǎng)絡(luò)文件件系統(tǒng)，滿足足以上假設(shè)的的應(yīng)用場(chǎng)景，并并且保證這個(gè)個(gè)分布式文件件系統(tǒng)的高可可用和高性能能。需要解決決的問題有下下面3個(gè)方面：本地文件系統(tǒng)首先，為了在本本地保證用戶戶提供的“共享空間”比例，F(xiàn)rront在本本地磁盤上的的存取應(yīng)該對(duì)對(duì)用戶有一定定的不透明性性。也即用戶戶看不到是什什么數(shù)據(jù)（在在操作系統(tǒng)里里看就是文

10、件件）占用了本本地磁盤。一一種可行的方方案是，用戶戶在操作系統(tǒng)統(tǒng)里看到的存存儲(chǔ)文件不是是發(fā)布到Frront系統(tǒng)統(tǒng)的文件的直直接形式。發(fā)發(fā)布的文件可可以經(jīng)過某種種轉(zhuǎn)化后存在在磁盤上，用用戶不知道那那個(gè)什么文件件是自己需要要的還是提供供給他人的，因因此不太愿意意去冒險(xiǎn)刪掉其其中的一部分分。從這個(gè)角角度上可以部部分解決P22P系統(tǒng)的FFree Riderr問題。一種簡(jiǎn)單的磁盤盤存儲(chǔ)不透明明性可以用文文件分塊來實(shí)實(shí)現(xiàn)。通過把把文件切分成成一定大小的的文件塊，可可以自然的把把系統(tǒng)上的眾眾多文件數(shù)據(jù)據(jù)“混淆”在一起。把文文件分成塊，還可以簡(jiǎn)化一個(gè)節(jié)點(diǎn)上傳大于本地空間大小的文件的設(shè)計(jì)。另外，在分布式文件系統(tǒng)

11、中，我們希望資源（包括復(fù)本）可以均勻的分布在更多的節(jié)點(diǎn)上，這樣可以帶來更高的可用性和性能。顯然，當(dāng)文件分成較小的塊時(shí)，系統(tǒng)中的大文件也更加容易實(shí)現(xiàn)在網(wǎng)絡(luò)中的這種分布。文件分塊的一個(gè)額外開銷是需要在這個(gè)網(wǎng)絡(luò)中維護(hù)文件分塊信息，并且對(duì)文件的請(qǐng)求被分為多個(gè)不走。另一個(gè)需要在本地處理的問題是，當(dāng)資源請(qǐng)求超過了本地磁盤配額，如何權(quán)衡用戶的需要得到滿足和節(jié)點(diǎn)同時(shí)為網(wǎng)絡(luò)提供存儲(chǔ)服務(wù)的矛盾，F(xiàn)ront系統(tǒng)本地需要一個(gè)安全有效的數(shù)據(jù)替換算法。網(wǎng)絡(luò)互聯(lián)和文件件查詢網(wǎng)絡(luò)上需要協(xié)作作的Fronnt節(jié)點(diǎn)需要要一種辦法來來知道彼此的的存在。節(jié)點(diǎn)點(diǎn)加入和離開開對(duì)網(wǎng)絡(luò)的影影響不能太大大。因此當(dāng)網(wǎng)網(wǎng)絡(luò)規(guī)模較大大時(shí)，節(jié)點(diǎn)之之間不

12、可能兩兩兩可知的。相相互可知的節(jié)節(jié)點(diǎn)互為鄰居居，并且可以以彼此交換信信息，以增強(qiáng)強(qiáng)網(wǎng)絡(luò)連通性性或者傳遞查查詢請(qǐng)求等。一個(gè)理想的網(wǎng)絡(luò)連接情況是：臨近（IP或者地理位置）的節(jié)點(diǎn)盡可能互為鄰居，形成連通性較強(qiáng)的局部網(wǎng)絡(luò)；距離較遠(yuǎn)的節(jié)點(diǎn)之間保持一定的連通，這樣才能讓遠(yuǎn)處的查詢得到本地的信息，讓整個(gè)網(wǎng)絡(luò)的信息通暢。為了避免網(wǎng)絡(luò)中的節(jié)點(diǎn)孤島，需要一種方法顯式地加入已經(jīng)存在的網(wǎng)絡(luò)。文件的查詢涉及及命名和查詢路由。文件在系統(tǒng)統(tǒng)的命名最好好可閱讀的，并并且具有一定定的區(qū)分性。后者讓不同用戶發(fā)布文件較難產(chǎn)生命名沖突。對(duì)于系統(tǒng)內(nèi)部，對(duì)文件（可能被切分成文件塊）的識(shí)別應(yīng)該是唯一的，可以跟可閱讀的文件名一一對(duì)應(yīng)。另外，

13、不同的用戶可能發(fā)布完全一樣的文件，應(yīng)該被識(shí)別并且利用起來。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)向路由器一樣連接起來后，每個(gè)節(jié)點(diǎn)根據(jù)本地鄰居信息，以一定的方式將請(qǐng)求和應(yīng)答在分布式系統(tǒng)中傳播，最終使請(qǐng)求發(fā)起者獲得文件的信息。數(shù)據(jù)復(fù)制和傳輸輸系統(tǒng)中的文件數(shù)數(shù)據(jù)需要被合合理地分配在在分布式節(jié)點(diǎn)點(diǎn)上。這一點(diǎn)點(diǎn)保證系統(tǒng)中中的文件以盡盡可能大的概概率存在于網(wǎng)網(wǎng)絡(luò)中并且可可達(dá)。同時(shí)對(duì)對(duì)于文件的傳傳輸請(qǐng)求也可可以向傳統(tǒng)PP2P網(wǎng)絡(luò)中中那樣從多個(gè)個(gè)目標(biāo)節(jié)點(diǎn)同同時(shí)開始。當(dāng)當(dāng)文件被分塊塊后，文件的的結(jié)構(gòu)信息也也應(yīng)該被廣泛泛地分布于整整個(gè)網(wǎng)絡(luò)中，以以使得被更多多的節(jié)點(diǎn)可知知。數(shù)據(jù)復(fù)制制的觸發(fā)可以以放在發(fā)布時(shí)時(shí)，當(dāng)節(jié)點(diǎn)有有可能探測(cè)到到文件的復(fù)

14、本本可能在網(wǎng)絡(luò)絡(luò)中下降時(shí)，或或者很受歡迎迎被很多人請(qǐng)請(qǐng)求時(shí)，也應(yīng)應(yīng)該出發(fā)復(fù)制制（在后一種種情況中被稱稱為緩存）。系統(tǒng)結(jié)構(gòu)設(shè)計(jì)為了解決第III部分提出來來的幾點(diǎn)問題題，設(shè)計(jì)Fronnt網(wǎng)絡(luò)文件件系統(tǒng)需要考考慮的幾個(gè)模模塊的交互。FFront系系統(tǒng)及節(jié)點(diǎn)的的本地結(jié)構(gòu)如如圖表一所示示。圖表 SEQ 圖表 * CHINESENUM3 一 Frront系統(tǒng)統(tǒng)節(jié)點(diǎn)的本地地結(jié)構(gòu)系統(tǒng)中所共有的的Frontt結(jié)構(gòu)信息在在commoon strructuress里定義。FFront Virtuual Fiile Syystem是是本地與操作作系統(tǒng)的文件件系統(tǒng)交互的的唯一模塊，它它通過將文件件分塊，并維維持本地文件

15、件結(jié)構(gòu)表和本本地分塊表，來來向上層提供供一層虛擬的的文件系統(tǒng)。Networking component模塊負(fù)責(zé)與其他節(jié)點(diǎn)的通訊和數(shù)據(jù)傳輸。在FrontVFS和Networking componet之上的一層是Front文件系統(tǒng)的對(duì)外接口FSClientNode。FSClientNode就好像一層中間件，可以向上層提供可以實(shí)現(xiàn)網(wǎng)絡(luò)存儲(chǔ)和共享的文件系統(tǒng)。在我們的實(shí)現(xiàn)中，我們?cè)O(shè)計(jì)了用戶界面來調(diào)用FSClientNode，即實(shí)現(xiàn)了一個(gè)完整的客戶端。關(guān)于每個(gè)模塊的實(shí)現(xiàn)將在第IV部分介紹。實(shí)現(xiàn)FRONT互聯(lián)聯(lián)網(wǎng)文件存儲(chǔ)儲(chǔ)與共享系統(tǒng)統(tǒng)的實(shí)現(xiàn)，分分成以下5個(gè)個(gè)部分來介紹紹。 命名Front文件件系統(tǒng)的命名名問

16、題屬于第第V部分介紹紹的Fronnt commmon sstructtures部分。上文已已經(jīng)提到，每每個(gè)文件應(yīng)該該擁有一個(gè)可可閱讀（huuman rreadabble）的文文件路徑。這這個(gè)路徑在用用戶發(fā)布是制制定。有naamespaace域和ssystemmpath域域組成。文件系統(tǒng)內(nèi)部使使用的定位符符(idenntifieer)統(tǒng)一使使用128位位數(shù)據(jù)來表示示。針對(duì)文件件的定位符，根據(jù)據(jù)可閱讀的文文件路徑經(jīng)過過MD5計(jì)算算得到。因此此，請(qǐng)求文件件的用戶只要要知道這個(gè)可可閱讀的文件件路徑即可發(fā)發(fā)出請(qǐng)求。針針對(duì)文件塊的的定位符，根根據(jù)文件塊數(shù)數(shù)據(jù)內(nèi)容經(jīng)過過MD5計(jì)算算得到。這樣樣當(dāng)一個(gè)固定定的

17、文件被分分塊時(shí)，如果果能夠保證分分塊結(jié)構(gòu)總是是一致，那每每一塊計(jì)算得得到的定位符符也是相等的的。這個(gè)特性性有利于Frront系統(tǒng)統(tǒng)對(duì)發(fā)布相同同文件的識(shí)別別和利用。下下文將會(huì)提到到，F(xiàn)ronnt VFFS對(duì)于相同同的文件，分分塊的結(jié)果是是一致的。 本地文件系系統(tǒng)FRONNT VFSSFRONT VVFS是建立立在操作系統(tǒng)統(tǒng)文件系統(tǒng)之之上的一層文文件系統(tǒng)，用用戶與在整個(gè)個(gè)系統(tǒng)中與FFRONT VFS進(jìn)行行交互。對(duì)系統(tǒng)中存在的的文件我們選選擇了對(duì)其進(jìn)進(jìn)行分塊。分分塊的好處首首先在于一個(gè)個(gè)節(jié)點(diǎn)存放不下的文件件可以分開存存儲(chǔ)在多個(gè)節(jié)節(jié)點(diǎn)上。第二二，如果用戶戶修改某個(gè)文文件的一部分分，重新發(fā)布布時(shí)很可能有

18、有的塊并沒有變化，此此時(shí)只需發(fā)布布更改過的塊塊即可。第三個(gè)個(gè)好處在于可可以均衡負(fù)載載，用戶可以以同時(shí)從幾個(gè)個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)上上下載不同的的塊來達(dá)到加加速傳輸?shù)哪康??？伎紤]下面一種種情況：網(wǎng)絡(luò)絡(luò)中有三個(gè)節(jié)節(jié)點(diǎn)存儲(chǔ)三個(gè)個(gè)300M的的文件，每個(gè)個(gè)節(jié)點(diǎn)指定的的共享空間為為300M。那那么，如果我我們將三個(gè)文文件都分成三三個(gè)塊，分布布在三個(gè)節(jié)點(diǎn)點(diǎn)。這樣用戶戶下載每一個(gè)文件時(shí)時(shí)都可以從三個(gè)個(gè)節(jié)點(diǎn)同時(shí)下下載三個(gè)塊，比比文件不分塊塊時(shí)必須從單單個(gè)節(jié)點(diǎn)下載載的情況效率率要高。但是是，分塊同時(shí)時(shí)帶來了資源源存在的不確確定性。如果果存放一個(gè)文文件的某個(gè)塊塊的節(jié)點(diǎn)關(guān)機(jī)機(jī)，系統(tǒng)中又又沒有該塊的的備份，那么么這個(gè)文件就就無法被

19、完整整獲得。分塊塊越多分布越越廣越容易出出現(xiàn)這樣的問問題。除了采采取一定的復(fù)復(fù)制策略外，我我們的分塊算算法也保證一一個(gè)文件不要要分成太多的的塊。根據(jù)文文件大小所在在的不同區(qū)間間，我們對(duì)文文件采取不同同的分塊策略略。分塊算法法如下：intint chunkSize;int times = 1;int maxChunkNum = chunkNumStart;while(true)if( minChunkSize * times maxChunkSize )chunkSize = maxChunkSize;break;if( fileLength 00，則任選一一個(gè)鄰居把FFILEQUUERY發(fā)送送

20、出去。FILEQUEERY的發(fā)起起節(jié)點(diǎn)在啟動(dòng)動(dòng)RandoomWalkk之后，啟動(dòng)動(dòng)一個(gè)計(jì)時(shí)器器，在這個(gè)時(shí)時(shí)段內(nèi)系統(tǒng)收收集所有的應(yīng)應(yīng)答(FILLEREPLLY)。每個(gè)個(gè)應(yīng)答中包含含了文件的CChunk列列表和本地保保存的Chuunk的列表表。在計(jì)時(shí)器器到期時(shí)，如如果所有的cchunk的的信息都已經(jīng)經(jīng)可用，則把把結(jié)果顯示到到UI；否則則再依次搜索索每個(gè)未知未未知的chuunk。搜索索chunkk的方式也是是K-RanndomWaalk。收到收到FILEQUERY丟棄FILEQUERY任選鄰居轉(zhuǎn)發(fā)FILEQUERY本地保存有請(qǐng)求的文件信息？FILEQUERY.TTL0？YNYN發(fā)送應(yīng)答FILEQUE

21、RY.TTL-圖表 SEQ 圖表 * ARABIC 3 FIILEQUEERY的路由由PProcedure QueryFile(fileKey)BEGIN FOR i in 0,minK,neighborCount DO BEGINNeighbor = getRandomNeighbor();Send FILEQUERY to neighborENDStart_timer(T_Query, collectQueryResult) /waits T_Query secods and then collect the resultENDPProcedure recvFileQueryReply(r

22、eply)BEGINMerge reply.availiableChunks to receivedAvailiableChunks;Record chunk locations in receivedAvailiableChunks;ENDProcedure collectQueryResult()BEGINIF has full result THENDisplay result to UIELSE BEGIN Query remaining chunks like file query startTimer(T_chunk_Query, collectQueryResult) ENDEN

23、D 根據(jù)引文文10的的結(jié)論，在KK=16664的情況下下，K-RaandomWWalk能夠夠得到很好的的查詢效率。 然而，簡(jiǎn)簡(jiǎn)單的K-RRandommWalk可可能導(dǎo)致一定定的低效率，原原因包括：K次選擇隨即鄰鄰居有可能重重復(fù)選擇；有可能造成環(huán)狀狀搜索，即節(jié)節(jié)點(diǎn)A選擇了了鄰居B，BB又選擇了AA（或者A選選擇了B，BB選擇了C，CC又選擇了AA，等等）；不同的Walkker可能遍遍歷相同的節(jié)節(jié)點(diǎn)。其中，第一個(gè)問問題很容易解解決。然而，后后面兩個(gè)問題題則不那么簡(jiǎn)簡(jiǎn)單。事實(shí)上上，一個(gè)有意意思的研究問問題是，如何何使得K-RRandomm Walkk的效率最高高（遍歷的節(jié)節(jié)點(diǎn)最多）？如何避免重重復(fù)經(jīng)

24、過某些些節(jié)點(diǎn)？一個(gè)簡(jiǎn)單的解決決環(huán)狀搜索（第第二個(gè)問題）的的方法是在QQuery消消息中添加途途經(jīng)的節(jié)點(diǎn)列列表，然后每每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)點(diǎn)盡量選擇不不在途經(jīng)節(jié)點(diǎn)點(diǎn)列表中的鄰鄰居進(jìn)行轉(zhuǎn)發(fā)發(fā)。然而，更更進(jìn)一步，如如何使得不同同的Walkk之間的重疊疊盡可能的小小？我們提出出的解決方案案是：為每個(gè)FILEEQUERYY添加一個(gè)序序列號(hào)屬性，每每個(gè)FILEEQUERYY由唯一確確定；添加主動(dòng)HELLLO消息，每每當(dāng)有FILLEQUERRY經(jīng)過本節(jié)節(jié)點(diǎn)時(shí)就廣播播主動(dòng)HELLLO，主動(dòng)動(dòng)HELLOO中包含近期期所途經(jīng)的MM個(gè)Querry消息的，主動(dòng)HEELLO的信信息也添加到到鄰居表中；節(jié)點(diǎn)在進(jìn)行轉(zhuǎn)發(fā)發(fā)決策時(shí)，就

25、就可以選擇鄰鄰居列表中不不曾收到過待待轉(zhuǎn)發(fā)請(qǐng)求的的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)轉(zhuǎn)發(fā)。 文件塊的復(fù)復(fù)制和傳輸當(dāng)用戶發(fā)布文件件時(shí)，就需要要發(fā)起文件復(fù)復(fù)制。文件復(fù)復(fù)制包括了復(fù)復(fù)制觸發(fā)點(diǎn)、塊塊傳輸和文件件的復(fù)制策略略三方面。在在設(shè)計(jì)這一部部分時(shí)需要考考慮到實(shí)現(xiàn)的的靈活性和可可擴(kuò)展性。首先是復(fù)制觸發(fā)發(fā)點(diǎn)的設(shè)置。當(dāng)當(dāng)用戶發(fā)布文文件時(shí)，顯然然需要觸發(fā)文文件復(fù)制。然然后客戶端需需要主動(dòng)地定定時(shí)探測(cè)當(dāng)前前網(wǎng)絡(luò)該文件件的復(fù)制情況況，當(dāng)復(fù)本數(shù)數(shù)長(zhǎng)期小于額額定值時(shí)，也也是需要觸發(fā)發(fā)文件復(fù)制的的。當(dāng)出現(xiàn)替替換文件塊時(shí)時(shí)，就需要主主動(dòng)地發(fā)起復(fù)復(fù)制，最簡(jiǎn)單單的情況就是是將該塊復(fù)制制到某個(gè)其它它的節(jié)點(diǎn)，但但這樣的復(fù)制制沒有全局的的考慮。如果果

26、考慮了整個(gè)個(gè)文件當(dāng)前的的復(fù)制情況的的話，就可以以收到更好的的效果，例如如可以請(qǐng)求發(fā)發(fā)布文件的節(jié)節(jié)點(diǎn)重新發(fā)起起復(fù)制。其次，在考慮塊塊傳輸時(shí)，有有兩種實(shí)現(xiàn)的的方法：一種種是使用多線線程同步Soocket的的方法，一種種是使用異步步Sockeet的方法。使使用異步Soocket的的方法雖然在在效率上和多多線程相近，但但在代碼的簡(jiǎn)簡(jiǎn)潔性上顯然然不如多線程程的方法。因因此為了提高高塊傳輸?shù)男?，以及追追求代碼的簡(jiǎn)簡(jiǎn)潔，我們使使用了多線程程。每個(gè)塊的的傳輸都有一一個(gè)線程對(duì)應(yīng)應(yīng)，這樣很好好的減少了代代碼量和代碼碼的復(fù)雜性。文件復(fù)制時(shí)存在在很多的線程程同時(shí)在傳輸輸，這時(shí)就需需要有一個(gè)統(tǒng)統(tǒng)一的線程來來管理這些

27、塊塊傳輸?shù)木€程程。每個(gè)文件件復(fù)制的過程程由一個(gè)線程程控制，而每每個(gè)文件塊的的傳輸也都由由一個(gè)線程負(fù)負(fù)責(zé)，這樣的的實(shí)現(xiàn)可以保保證在用戶發(fā)發(fā)布文件時(shí)，不不用長(zhǎng)時(shí)間等等待文件復(fù)制制的完成，就就可以進(jìn)行下下一步的操作作。在實(shí)現(xiàn)之初，文文件復(fù)制需要要文件的本地地分塊完成之之后才開始，這這樣就要求用用戶的本地空空間足夠大，顯顯然這個(gè)要求求過于苛刻。為為了解決這個(gè)個(gè)問題，我們們需要在用戶戶本地空間不不夠放下整個(gè)個(gè)文件時(shí)，只只要用戶本地地空間能都放放下最大的文文件塊，用戶戶仍然可以發(fā)發(fā)布文件。在在分塊過程中中，如果發(fā)現(xiàn)現(xiàn)本地空間不不足時(shí)，就需需要等待當(dāng)前前文件塊復(fù)制制完成，再使使用相應(yīng)的替替換算法替換換不必要

28、的文文件塊。這樣樣的實(shí)現(xiàn)既提提高了文件復(fù)復(fù)制的效率，又又無需用戶長(zhǎng)長(zhǎng)時(shí)間的等待待，還能滿足足用戶發(fā)布大大文件的需求求。再次，可以將文文件的復(fù)制策策略從文件復(fù)復(fù)制中剝離出出來，通過定定義一個(gè)復(fù)制制策略的基類類，如果需要要新的復(fù)制策策略時(shí)，只需需要繼承這個(gè)個(gè)基類，實(shí)現(xiàn)現(xiàn)其中的方法法。這樣就可可以在只改變變少量代碼的的情況下就能能實(shí)現(xiàn)擴(kuò)展，定定義新的文件件復(fù)制策略。在實(shí)現(xiàn)具體的復(fù)復(fù)制策略時(shí)，需需要確定復(fù)制制中候選節(jié)點(diǎn)點(diǎn)的范圍、復(fù)復(fù)制節(jié)點(diǎn)的選選擇、文件塊塊在這些節(jié)點(diǎn)點(diǎn)的分配策略略以及復(fù)制份份數(shù)。這些方方面并非各自自獨(dú)立的，某某一方面的決決策可能會(huì)影影響另一方面面的策略。候選節(jié)點(diǎn)的范圍圍可以是在鄰鄰居節(jié)

29、點(diǎn)或者者整個(gè)網(wǎng)絡(luò)。如如果是鄰居節(jié)節(jié)點(diǎn)則較易實(shí)實(shí)現(xiàn)，如果是是在整個(gè)網(wǎng)絡(luò)絡(luò)則需要通過過鄰居節(jié)點(diǎn)來來試探整個(gè)網(wǎng)網(wǎng)絡(luò)，以得到到潛在的候選選節(jié)點(diǎn)，這些些節(jié)點(diǎn)需要能能夠均勻的分分布在網(wǎng)絡(luò)中中。在選擇候候選節(jié)點(diǎn)時(shí)，節(jié)節(jié)點(diǎn)之間的距距離（即兩個(gè)個(gè)節(jié)點(diǎn)間的最最短跳數(shù)）是是一個(gè)重要的的參考，不同同距離的節(jié)點(diǎn)點(diǎn)就是有代表表性的候選節(jié)節(jié)點(diǎn)。在一個(gè)個(gè)合理的網(wǎng)絡(luò)絡(luò)中，各種不不同距離的節(jié)節(jié)點(diǎn)可以認(rèn)為為是均勻分布布的，同時(shí)也也考慮了網(wǎng)絡(luò)絡(luò)的連通性，遠(yuǎn)遠(yuǎn)端節(jié)點(diǎn)也覆覆蓋到了。另另外節(jié)點(diǎn)的IIP地址也是是很好的參考考，通過IPP地址和子網(wǎng)網(wǎng)掩碼可以了了解節(jié)點(diǎn)之間間的關(guān)系，相相同網(wǎng)段的節(jié)節(jié)點(diǎn)可以認(rèn)為為具有較近的的地理位置，不不同網(wǎng)段的

30、節(jié)節(jié)點(diǎn)也是有代代表性的候選選節(jié)點(diǎn)。復(fù)制節(jié)點(diǎn)選擇的的復(fù)雜性同候候選節(jié)點(diǎn)的范范圍有關(guān)，當(dāng)當(dāng)候選節(jié)點(diǎn)的的范圍較小時(shí)時(shí)，復(fù)雜性相相對(duì)會(huì)低一點(diǎn)點(diǎn)。選擇復(fù)制制節(jié)點(diǎn)需要考考慮節(jié)點(diǎn)的網(wǎng)網(wǎng)絡(luò)帶寬、存存儲(chǔ)余額等，網(wǎng)網(wǎng)絡(luò)帶寬較大大或者存儲(chǔ)余余額較大的節(jié)節(jié)點(diǎn)較易被選選中，同時(shí)還還需要考慮節(jié)節(jié)點(diǎn)數(shù)，一種種策略是一個(gè)個(gè)文件復(fù)本應(yīng)應(yīng)盡量在少量量的節(jié)點(diǎn)上，以以確保文件的的可用性。除除此之外，選選擇有代表性性的節(jié)點(diǎn)也是是很重要的，能能夠考慮整個(gè)個(gè)網(wǎng)絡(luò)的全局局信息，選擇擇最佳的復(fù)制制節(jié)點(diǎn)也是需需要考慮的因因素。文件塊的分配策策略需要考慮慮到均衡性，盡盡量保證文件件塊均勻的放放置在這些節(jié)節(jié)點(diǎn)中，同時(shí)時(shí)還需保證相相同的文件塊塊復(fù)本不

31、應(yīng)放放在同一個(gè)節(jié)節(jié)點(diǎn)上。這樣樣的策略不僅僅是為了公平平而均勻的使使用用戶共享享的空間，同同時(shí)也是基于于多線程的考考慮，均勻的的分配有利于于充分利用網(wǎng)網(wǎng)絡(luò)帶寬，在在盡可能短的的時(shí)間內(nèi)完成成復(fù)制?？紤]慮到候選節(jié)點(diǎn)點(diǎn)的選擇策略略，距離較接接近的節(jié)點(diǎn)和和相同網(wǎng)段的的節(jié)點(diǎn)傾向于于擁有一個(gè)復(fù)復(fù)本，當(dāng)然兩兩個(gè)復(fù)本所占占用節(jié)點(diǎn)的交交集應(yīng)當(dāng)盡量量小，這些節(jié)節(jié)點(diǎn)往往連通通性較好，地地理位置較近近，這樣即使使網(wǎng)絡(luò)出現(xiàn)了了問題，在網(wǎng)網(wǎng)絡(luò)的某個(gè)局局部仍然可以以保證文件的的可用性。至于復(fù)制份數(shù)，可可以根據(jù)當(dāng)前前網(wǎng)絡(luò)的大小小和網(wǎng)絡(luò)存儲(chǔ)儲(chǔ)空間的大小小來確定，網(wǎng)網(wǎng)絡(luò)的大小可可以通過探測(cè)測(cè)節(jié)點(diǎn)之間的的距離和網(wǎng)絡(luò)絡(luò)中的節(jié)點(diǎn)數(shù)數(shù)來獲

32、得，網(wǎng)網(wǎng)絡(luò)的大小同同節(jié)點(diǎn)之間的的距離和網(wǎng)絡(luò)絡(luò)中的節(jié)點(diǎn)數(shù)數(shù)成正比，當(dāng)當(dāng)然其中節(jié)點(diǎn)點(diǎn)數(shù)的比重應(yīng)應(yīng)該更大。節(jié)節(jié)點(diǎn)數(shù)多、節(jié)節(jié)點(diǎn)間距離大大，那么復(fù)制制份數(shù)就可以以多一點(diǎn)。網(wǎng)網(wǎng)絡(luò)存儲(chǔ)空間間的大小可以以通過試探各各個(gè)節(jié)點(diǎn)的存存儲(chǔ)余額來估估算。在獲得得相當(dāng)數(shù)量的的存儲(chǔ)余額后后，通過簡(jiǎn)單單的求平均來來得到當(dāng)前網(wǎng)網(wǎng)絡(luò)中節(jié)點(diǎn)的的平均存儲(chǔ)余余額，余額越越多，那么復(fù)復(fù)制份數(shù)就可可以越多。性能與相關(guān)工作作由于Frontt文件系統(tǒng)和和其它類似系系統(tǒng)在應(yīng)用場(chǎng)場(chǎng)景的區(qū)別，難難以構(gòu)造同樣樣的環(huán)境對(duì)比比。并且由于于時(shí)間和網(wǎng)絡(luò)絡(luò)環(huán)境的限制制，我們只在在3個(gè)節(jié)點(diǎn)的的網(wǎng)絡(luò)規(guī)模上上進(jìn)行了測(cè)試試。實(shí)驗(yàn)中文文件發(fā)布、復(fù)復(fù)制和下載功功能均得到正

33、正確的結(jié)果。在本文之前的大大多數(shù)P2PP文件系統(tǒng)，例例如迅雷、BBt等，都提提供的是文件件共享的服務(wù)務(wù)。本文試圖圖使用文件分分塊的技術(shù)提提供具有一定定擴(kuò)展性的網(wǎng)網(wǎng)絡(luò)文件存儲(chǔ)儲(chǔ)和共享系統(tǒng)統(tǒng)。不同于使使用DHT結(jié)結(jié)構(gòu)的一些系系統(tǒng)，例如CChord等等，F(xiàn)ronnt系統(tǒng)的設(shè)設(shè)計(jì)目標(biāo)是盡盡可能地提供供高可靠、高性性能的文件服服務(wù)，同時(shí)降降低對(duì)網(wǎng)絡(luò)負(fù)負(fù)載的影響。Front文件件系統(tǒng)使用文文件分塊實(shí)現(xiàn)現(xiàn)了一層操作作系統(tǒng)文件系系統(tǒng)之上的文文件層。磁盤盤上文件的不不透明性一定定程度上促使使用戶向網(wǎng)絡(luò)絡(luò)提供一定比比例的空間服服務(wù)。Froont系統(tǒng)使使用Randdom Waalk算法進(jìn)進(jìn)行文件定位位，一定程度度上降低了網(wǎng)網(wǎng)絡(luò)開銷，但但查詢的時(shí)間間可能會(huì)較長(zhǎng)長(zhǎng)?？偨Y(jié)和展望從Front文文件存儲(chǔ)和共共享系統(tǒng)的運(yùn)運(yùn)行試驗(yàn)中我我們得知，F(xiàn)Front系系統(tǒng)的功能可可行，但是由由于時(shí)間和測(cè)測(cè)試的限制，系系統(tǒng)在較大網(wǎng)網(wǎng)絡(luò)規(guī)模上的的性能還未知知。之后的一一項(xiàng)重要工作作是進(jìn)行更多多的測(cè)試，發(fā)發(fā)現(xiàn)系統(tǒng)性能能在較大規(guī)模模網(wǎng)絡(luò)上的影影響因素，并并設(shè)計(jì)策略進(jìn)進(jìn)一步提高可可用性和性能能。其他一些已知的的需要改進(jìn)的的地方有：Front文件件系統(tǒng)是只讀讀的。無法顯顯式刪除一個(gè)個(gè)已經(jīng)發(fā)布的的文件，以釋釋放全局空間間。文件塊的復(fù)制，需需要在更多的的情況下觸發(fā)發(fā)。以避免文文件內(nèi)容慢慢慢地在網(wǎng)絡(luò)中中消