隨著個(gè)人電腦的進(jìn)步及價(jià)格的低廉

1、Background an Motivation隨著個(gè)人電腦的進(jìn)步及價(jià)格的低廉，幾乎每個(gè)家庭都有個(gè)人電腦，不過(guò)觀察一下生活週遭的電腦使用情況，不難發(fā)現(xiàn)其實(shí)電腦大部分的時(shí)間都是處?kù)栋l(fā)呆或是關(guān)閉狀態(tài)，使電腦不能真正的有效運(yùn)用；但隨著網(wǎng)路的頻寬增加以及蓬勃發(fā)展，可以利用網(wǎng)路的力量將大家的電腦資源給結(jié)合起來(lái)，是未來(lái)網(wǎng)路發(fā)展的一項(xiàng)重要趨勢(shì)，讓每臺(tái)電腦都將參與在網(wǎng)路之中主要的精神就是將分散在不同地理位置的電腦組織在一起，其中每一臺(tái)參與計(jì)算的電腦就是屬於整個(gè)系統(tǒng)上的一份子，如此整個(gè)分散式系統(tǒng)上的所有電腦資源就能夠互相分享、整個(gè)計(jì)算也是由所有系統(tǒng)上的電腦共同合力完成。簡(jiǎn)單地講，就是把整個(gè)網(wǎng)路上的電腦整合成一臺(tái)

2、巨大的超級(jí)電腦，實(shí)現(xiàn)計(jì)算資源、存儲(chǔ)資源、資料資源、資訊資源、知識(shí)資源的全面共用。而近年來(lái)，分散式系統(tǒng)蓬勃發(fā)展，究其原因，檔案分享的應(yīng)用就是讓他受到大家廣泛使用的重要因素，目前在網(wǎng)路上大家普遍使用到的分散式系統(tǒng)有eMule、eDonkey、kuro等系統(tǒng)，而在此類分散式系統(tǒng)中，使用者可以隨時(shí)加入或離開，將自己的一些檔案或資料分享給其他人，並且也可以透過(guò)此系統(tǒng)搜尋所想要的檔案，或是下載所需的檔案。不過(guò)上述的系統(tǒng)中，都有所謂的中央伺服器來(lái)記錄來(lái)自各地的使用者分享的資料，以成本的考量上來(lái)看，為了要達(dá)到如此大規(guī)模的檔案分享系統(tǒng)，是需要功能強(qiáng)大的電腦，並且需要人力來(lái)維持中央系統(tǒng)的正常運(yùn)作，所需資金不匪，故

3、我們希望能將資料分享的運(yùn)用建置在完全分散式的Peer-to-Peer系統(tǒng)上，如此即可以省掉購(gòu)買強(qiáng)大伺服器的必要，因?yàn)镻eer-to-Peer系統(tǒng)是不需要中央的伺服器來(lái)記錄或管理資料，而是由系統(tǒng)上的所有電腦來(lái)共同負(fù)責(zé)，彼此的檔案可以透過(guò)底層的邏輯架構(gòu)及路由的資訊，來(lái)將檔案的資訊存放在系統(tǒng)上，在藉由相同的演算法，而可以搜尋到相關(guān)的檔案資訊，藉此達(dá)到彼此檔案分享的需求。Project Goal完全分散式的peer-to-peer系統(tǒng)一個(gè)完全沒有中央控制機(jī)制的系統(tǒng)，網(wǎng)路上的每臺(tái)電腦扮演相同的腳色，因此不會(huì)因?yàn)椴糠蛛娔X的當(dāng)機(jī)而癱瘓整個(gè)系統(tǒng)，且系統(tǒng)中的使用者不需記住整個(gè)系統(tǒng)的所有電腦的資訊或位址，即可找到

4、系統(tǒng)中的任何一臺(tái)電腦。能提供檔案分享使用者可以自行將檔案分享給整個(gè)系統(tǒng)，而此系統(tǒng)會(huì)將相關(guān)的檔案訊息放置在系統(tǒng)中適當(dāng)?shù)碾娔X存放。快速的檔案查詢使用者可以不知道系統(tǒng)中各臺(tái)電腦的位址的情況下，而以檔名搜尋系統(tǒng)，並找到系統(tǒng)中此檔案的相關(guān)資訊，我們預(yù)計(jì)提供完整的檔名搜尋及關(guān)鍵字搜尋兩種不同的搜尋功能。能夠容許電腦動(dòng)態(tài)加入及離開、當(dāng)機(jī)容許許多臺(tái)電腦可以同時(shí)加入系統(tǒng)中，或是多臺(tái)電腦同時(shí)離開，或是多臺(tái)電腦的不正常離開系統(tǒng)，而系統(tǒng)還能正常運(yùn)作或是快速的恢復(fù)正常運(yùn)作。在電腦數(shù)目遽增的情況下還維持不錯(cuò)的效能當(dāng)有幾百萬(wàn)臺(tái)甚至幾億臺(tái)電腦加入系統(tǒng)時(shí)還能維持系統(tǒng)的效能，即可以有效率的分享檔案、搜尋檔案、加入系統(tǒng)或是離開系統(tǒng)

5、?？焖俚南螺d所需的檔案利用將一份檔案切割成數(shù)個(gè)區(qū)塊的技術(shù)，而能使下載者能同時(shí)從不同的來(lái)源下載不同的區(qū)塊，以加速檔案取得的時(shí)間。System ArchitectureObject ServiceObject Service LayerApplication LayerName resolution and routing serviceObject insert and delete serviceTopology construction and maintenanceObject migration and replication serviceObject access and locat

6、ion service Object sharingKey word searchingFile namesearchingObjectdownloadingP2P Base LayerApplication Layer:此層主要是與使用者直接溝通的介面，提供了使用者加入或離開整個(gè)系統(tǒng)，而當(dāng)使用者加入系統(tǒng)後，即可以分享自己的檔案、搜尋系統(tǒng)中想要的檔案以及下載所想要的檔案。Object Service Layer:此層主要是管理使用者的檔案分享及檔案下載，包含了記錄使用者分享的檔案資訊，而檔案下載時(shí)會(huì)若得知來(lái)源不只一臺(tái)電腦時(shí)，則會(huì)同時(shí)向不同的來(lái)源要求下載不同的檔案區(qū)塊，並將抓回的檔案區(qū)塊組合成原

7、本的檔案，最後再將抓取的檔案分享出去。P2P Base Layer:建置Peer-to-peer的分散式系統(tǒng)，包含節(jié)點(diǎn)的加入系統(tǒng)及離開系統(tǒng)、分享檔案資訊的插入及刪除，還有系統(tǒng)錯(cuò)誤的更正及修復(fù)等等，並提供節(jié)點(diǎn)的搜尋、檔案的搜尋等功能。Design and AlgorithmP2P Base LayerBase on ChordRouting Table：如同Chord的設(shè)計(jì)，每個(gè)節(jié)點(diǎn)會(huì)記錄與自己的ID相差2的i次方的ID的代理節(jié)點(diǎn)當(dāng)作自己的ith neighbor，並且會(huì)記錄自己的predecessor與successor的資訊，而不同的是本系統(tǒng)可以依照系統(tǒng)的特性來(lái)設(shè)定要記錄的predecess

8、or與successor的數(shù)目，記錄的越多系統(tǒng)會(huì)能容忍節(jié)點(diǎn)的不正常離開，但也因此必須再加入及離開時(shí)有較多的資訊交流。Routing Algorithm(Node LookupAlgorithm：首先先檢查欲查詢的目標(biāo)節(jié)點(diǎn)其ID是否在我與我的successors的ID的範(fàn)圍內(nèi)，若是即表示目標(biāo)ID的代理節(jié)點(diǎn)為我的successor，並從successors中找出此ID的代理節(jié)點(diǎn)；若否，則檢查是否我有predecessor，若沒有則檢查目標(biāo)ID是否座落在離我最遠(yuǎn)的successor與我的ID之間，若是則表示我自己即為此目標(biāo)ID的代理點(diǎn)。若非上述的情況，則尋找我的ith neighbor中，其ID最接

9、近目標(biāo)ID但又不超過(guò)目標(biāo)ID的節(jié)點(diǎn)，並且將尋找目標(biāo)ID的要求傳給該節(jié)點(diǎn)，由該節(jié)點(diǎn)採(cǎi)用相同的routing演算法直到找到目標(biāo)ID的代理節(jié)點(diǎn)為止。Node Join Algorithm: 若系統(tǒng)目前沒有任何節(jié)點(diǎn)，則自己成為系統(tǒng)的第一個(gè)節(jié)點(diǎn)，並等待別人來(lái)加入。 若欲加入的系統(tǒng)已經(jīng)有節(jié)點(diǎn)存在，則以其中一個(gè)已知的節(jié)點(diǎn)當(dāng)作gateway，由此節(jié)點(diǎn)詢問到目前系統(tǒng)中代理自己的ID的代理節(jié)點(diǎn)，並將此代理節(jié)點(diǎn)的predecessors與successors當(dāng)作自己的predecessors與successors，接著在詢問此代理節(jié)點(diǎn)得到我的ith neighbors。接著詢問我的predecessors與succ

10、essors所記錄的檔案資訊，並將該屬於自己記錄的資料記錄下來(lái)，接著告知我的代理節(jié)點(diǎn)有關(guān)我的加入，並再次詢問其predecessors的資訊，看看是否同時(shí)有新的節(jié)點(diǎn)加入，如果有則更新我的predecessors或successors的資訊。最後再告知我的predecessors與successors有關(guān)我的加入，使他們能更新其successors與predecessors的資訊，並且更新其ith neighbors的資訊。Node Leave Algorithm: 首先先將我自己分享的案檔的資料從系統(tǒng)中刪除，接著再將原本存放在我身上的檔案資訊傳給我的successor。 再來(lái)在告知我的pred

11、ecessors與successors有關(guān)我的離開，而收到此訊息的節(jié)點(diǎn)將會(huì)更新其predecessors與successors的資訊，以及更新其ith neighbor的資訊，最後就可以離開系統(tǒng)。Failure Detect Algorithm:為了增加系統(tǒng)的正確性，每個(gè)節(jié)點(diǎn)將會(huì)定期的檢查自己的routing table的資訊是否正確，即檢查位於自己routing table的節(jié)點(diǎn)是否都還存在：如果有predecessor掛掉了，則詢問其他還存活的predecessor其predecessor的資訊，以補(bǔ)充及更新自己的predecessor的資訊；如果有successor掛掉了，則詢問其他還存

12、活的successor其successor的資訊，以補(bǔ)充及更新自己的successor的資訊；若ith neighbor掛掉了，則重新lookup此ith neighbor的ID來(lái)找尋到新的代理者。Object Insert Algorithm:首先先將欲分享的檔案的檔名經(jīng)過(guò)SHA1 hash過(guò)，而得到此檔案的object ID，再經(jīng)由lookup的機(jī)制尋找到此ID的代理節(jié)點(diǎn)，接著告知此節(jié)點(diǎn)有關(guān)此案檔的資訊，資訊包含檔案的檔名、檔案大小及來(lái)源節(jié)點(diǎn)。而當(dāng)此負(fù)責(zé)此物件資訊的代理節(jié)點(diǎn)接到object insert的資訊後，會(huì)將此資訊記錄到自己負(fù)責(zé)的object的記錄中，接著再將此object ins

13、ert的資訊告訴其所有的predecessors與successors，而當(dāng)代理節(jié)點(diǎn)的predecessors與successors接到這樣的資訊後，會(huì)將這些資訊放入其cache中。Object Delete Algorithm:首先先將欲刪除且已分享的檔案的檔名經(jīng)過(guò)SHA1 hash過(guò)，得到此檔案的object ID，再經(jīng)由lookup的機(jī)制尋找到此ID的代理節(jié)點(diǎn)，接著告知此節(jié)點(diǎn)將有關(guān)此案檔的資訊移除。當(dāng)負(fù)責(zé)此物件資訊的代理節(jié)點(diǎn)接到object delete的資訊後，會(huì)搜尋自己負(fù)責(zé)的object的記錄檔，看看是否有這檔案的資料，如果有則刪除，接著再把此object delete的資訊告訴其所

14、有的predecessors與successors，而當(dāng)此代理節(jié)點(diǎn)的predecessors與successors接到這樣的資訊後，會(huì)將搜尋其cache看看是否有此資料存在，若有則刪除之。Object Search Algorithm:首先先將欲搜尋的檔案的檔名經(jīng)過(guò)SHA1 hash過(guò)，得到此檔案的object ID，再經(jīng)由lookup的機(jī)制尋找到此ID的代理節(jié)點(diǎn)，接著詢問此節(jié)點(diǎn)是否有有關(guān)此案檔的資訊。當(dāng)負(fù)責(zé)此物件資訊的代理節(jié)點(diǎn)接到object search的資訊後，會(huì)搜尋自己負(fù)責(zé)的object及cache的記錄檔，看看是否有這檔案的資料，如果有，則會(huì)先確認(rèn)檔案的來(lái)源節(jié)點(diǎn)是否活著，若活著則回傳

15、相關(guān)的檔案資訊；若來(lái)源節(jié)點(diǎn)已掛點(diǎn)，則會(huì)將此資料移除。Object Keyword Search Algorithm:詢問所有位於我的routing table的節(jié)點(diǎn)是否含有預(yù)搜尋的keyword的字串的檔案資訊。 而當(dāng)接收到此搜尋的要求時(shí)，節(jié)點(diǎn)會(huì)檢查自己的object與cache的記錄檔，看看是否記錄的檔案其檔名包含此keyword，如果有，則會(huì)先確認(rèn)檔案的來(lái)源節(jié)點(diǎn)是否活著，若活著則回傳相關(guān)的檔案資訊；若來(lái)源節(jié)點(diǎn)已掛點(diǎn)，則會(huì)將此資料移除。Object Download Algorithm:當(dāng)搜尋檔案得到檔案的來(lái)源資訊後，會(huì)檢查是否有許多不同的來(lái)源，若只有單一的來(lái)源則直接與來(lái)源節(jié)點(diǎn)要求下載檔案。

16、 若有多個(gè)來(lái)源，則會(huì)根據(jù)檔案的大小，將檔案分成許多固定大小的小區(qū)塊，而同時(shí)與不同的來(lái)源要求下載不同的檔案區(qū)塊，最後再將所有的區(qū)塊重新整合成完整的檔案，並將此檔案用object insert的方式分享出去。System CharacteristicsDynamics:因?yàn)楫?dāng)有節(jié)點(diǎn)要加入時(shí)，會(huì)先取得相關(guān)的資訊，才會(huì)告知系統(tǒng)新節(jié)點(diǎn)的加入，減少系統(tǒng)更正整個(gè)網(wǎng)路資訊的時(shí)間，並降低發(fā)生同時(shí)加入時(shí)的短暫更正時(shí)間；而離開前也是會(huì)先移除自己分享的檔案資訊，且將負(fù)責(zé)的資料傳給successor，然後告知系統(tǒng)其離開的資訊，可確保資料已經(jīng)正確傳給其他節(jié)點(diǎn)來(lái)負(fù)責(zé)，故此系統(tǒng)可容許節(jié)點(diǎn)動(dòng)態(tài)的加入或離開系統(tǒng)，或是同時(shí)的加入或

17、離開。Scalability: 因?yàn)槊總€(gè)節(jié)點(diǎn)要記錄的鄰居的資訊只是O(logN)，所以就算系統(tǒng)可容許264個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)要記錄的鄰居數(shù)也不到百個(gè)，故此系統(tǒng)可以有很好的擴(kuò)充性，可適用於目前整個(gè)網(wǎng)際網(wǎng)路。Fail Tolerance: 因?yàn)闀?huì)定期的確認(rèn)routing table的正確性，故當(dāng)有節(jié)點(diǎn)不正常離開系統(tǒng)時(shí)，可以被偵測(cè)到並且更正，再加上每個(gè)檔案的資訊不只是存在該檔案ID的代理節(jié)點(diǎn)上，還會(huì)被cache在代理節(jié)點(diǎn)的predecessors與successors上，故檔案資訊會(huì)存在代理節(jié)點(diǎn)的附近區(qū)域，故區(qū)域內(nèi)有節(jié)點(diǎn)不正常離開時(shí)，還可以從其他人身上得到檔案的資訊。On demand Correct

18、 Object Record:因?yàn)楫?dāng)有人與檔案的代理節(jié)點(diǎn)詢問有關(guān)檔案的資訊時(shí)，代理節(jié)點(diǎn)會(huì)先檢查是否檔案的來(lái)源還活著，故可以在需要的時(shí)候才更新檔案的資訊，減少平常網(wǎng)路的使用及節(jié)點(diǎn)本身的運(yùn)作，也可以增加回傳的資料的正確性。Quickly Download:若系統(tǒng)中存在許多節(jié)點(diǎn)分享共同的檔案，則可以加入檔案下載的速度，因?yàn)榭梢酝瑫r(shí)從不同的來(lái)源同時(shí)下載不同的檔案區(qū)塊，最後再組合回原本的檔案。Operation Procedure因?yàn)槭褂肑ava RMI作為middle ware，故首先必須執(zhí)行RMI Registry，然後在執(zhí)行本程式。Node Joining and Leaving:如圖一所示，首先

19、必須先加入網(wǎng)路系統(tǒng)，若是系統(tǒng)的第一點(diǎn)，則直接按connect即可，而若系統(tǒng)已有其節(jié)點(diǎn)存在，則在gateway處加入已存在的節(jié)點(diǎn)的ip與port，在按connect即可加入系統(tǒng)，當(dāng)加入後即可做檔案的分享與搜尋，而當(dāng)要離開系統(tǒng)時(shí)，按Disconnect即可，而status處會(huì)顯示目前節(jié)點(diǎn)的狀態(tài)即ID。圖一Objects Sharing and Deleting:如圖二所示，當(dāng)加入系統(tǒng)後即可做檔案的分享，只要按Open File即會(huì)彈出資料夾選擇視窗，讓使用這選擇要分享的檔案，My Share Files處即會(huì)列出目前已經(jīng)分享出來(lái)的檔案資訊，接著可以從此列表中選擇檔案，按Delete將此分享的檔案資訊從系統(tǒng)中移除。圖二Objects Searching and Keyword Searching:如圖三所示，可以選擇作檔名的搜尋或是關(guān)鍵字搜尋，即分別在Filename處或是Keyword處輸入檔名或是關(guān)鍵字，然後按下Start即可搜尋，搜尋的結(jié)果會(huì)列在Search Result處，而其中檔案搜尋是只要系統(tǒng)中有人分享及可以搜尋到，而關(guān)鍵字搜尋則只有作部分的搜尋，故可能系統(tǒng)中存在相關(guān)的資料，但是卻沒搜尋到，而按Remove即可清除搜尋的結(jié)果。圖三Objects Downl