随著个人电脑的进步及价格的低廉

BackgroundanMotivation隨著個人電腦的進步及價格的低廉，幾乎每個家庭都有個人電腦，不過觀察一下生活週遭的電腦使用情況，不難發現其實電腦大部分的時間都是處於發呆或是關閉狀態，使電腦不能真正的有效運用；但隨著網路的頻寬增加以及蓬勃發展，可以利用網路的力量將大家的電腦資源給結合起來，是未來網路發展的一項重要趨勢，「讓每台電腦都將參與在網路之中」主要的精神就是將分散在不同地理位置的電腦組織在一起，其中每一台參與計算的電腦就是屬於整個系統上的一份子，如此整個分散式系統上的所有電腦資源就能夠互相分享、整個計算也是由所有系統上的電腦共同合力完成。簡單地講，就是把整個網路上的電腦整合成一台巨大的超級電腦，實現計算資源、存儲資源、資料資源、資訊資源、知識資源的全面共用。而近年來，分散式系統蓬勃發展，究其原因，「檔案分享」的應用就是讓他受到大家廣泛使用的重要因素，目前在網路上大家普遍使用到的分散式系統有eMule、eDonkey、kuro等系統，而在此類分散式系統中，使用者可以隨時加入或離開，將自己的一些檔案或資料分享給其他人，並且也可以透過此系統搜尋所想要的檔案，或是下載所需的檔案。不過上述的系統中，都有所謂的中央伺服器來記錄來自各地的使用者分享的資料，以成本的考量上來看，為了要達到如此大規模的檔案分享系統，是需要功能強大的電腦，並且需要人力來維持中央系統的正常運作，所需資金不匪，故我們希望能將資料分享的運用建置在完全分散式的Peer-to-Peer系統上，如此即可以省掉購買強大伺服器的必要，因為Peer-to-Peer系統是不需要中央的伺服器來記錄或管理資料，而是由系統上的所有電腦來共同負責，彼此的檔案可以透過底層的邏輯架構及路由的資訊，來將檔案的資訊存放在系統上，在藉由相同的演算法，而可以搜尋到相關的檔案資訊，藉此達到彼此檔案分享的需求。ProjectGoal一、完全分散式的peer-to-peer系統一個完全沒有中央控制機制的系統，網路上的每台電腦扮演相同的腳色，因此不會因為部分電腦的當機而癱瘓整個系統，且系統中的使用者不需記住整個系統的所有電腦的資訊或位址，即可找到系統中的任何一台電腦。二、能提供檔案分享使用者可以自行將檔案分享給整個系統，而此系統會將相關的檔案訊息放置在系統中適當的電腦存放。三、快速的檔案查詢使用者可以不知道系統中各台電腦的位址的情況下，而以檔名搜尋系統，並找到系統中此檔案的相關資訊，我們預計提供完整的檔名搜尋及關鍵字搜尋兩種不同的搜尋功能。四、能夠容許電腦動態加入及離開、當機容許許多台電腦可以同時加入系統中，或是多台電腦同時離開，或是多台電腦的不正常離開系統，而系統還能正常運作或是快速的恢復正常運作。五、在電腦數目遽增的情況下還維持不錯的效能當有幾百萬台甚至幾億台電腦加入系統時還能維持系統的效能，即可以有效率的分享檔案、搜尋檔案、加入系統或是離開系統。六、快速的下載所需的檔案利用將一份檔案切割成數個區塊的技術，而能使下載者能同時從不同的來源下載不同的區塊，以加速檔案取得的時間。SystemArchitectureApplicationLayer:此層主要是與使用者直接溝通的介面，提供了使用者加入或離開整個系統，而當使用者加入系統後，即可以分享自己的檔案、搜尋系統中想要的檔案以及下載所想要的檔案。ObjectServiceLayer:此層主要是管理使用者的檔案分享及檔案下載，包含了記錄使用者分享的檔案資訊，而檔案下載時會若得知來源不只一台電腦時，則會同時向不同的來源要求下載不同的檔案區塊，並將抓回的檔案區塊組合成原本的檔案，最後再將抓取的檔案分享出去。P2PBaseLayer:建置Peer-to-peer的分散式系統，包含節點的加入系統及離開系統、分享檔案資訊的插入及刪除，還有系統錯誤的更正及修復等等，並提供節點的搜尋、檔案的搜尋等功能。DesignandAlgorithmP2PBaseLayer─BaseonChordNameresolutionandroutingserviceObjectinsertanddeleteserviceTopologyconstructionandmaintenanceObjectmigrationandreplicationserviceObjectaccessandlocationserviceObjectsharingKeywordsearchingFilenamesearchingObjectdownloadingP2PBaseLayerApplicationLayerObjectServiceLayerRoutingTable：如同Chord的設計，每個節點會記錄與自己的ID相差2的i次方的ID的代理節點當作自己的ithneighbor，並且會記錄自己的predecessor與successor的資訊，而不同的是本系統可以依照系統的特性來設定要記錄的predecessor與successor的數目，記錄的越多系統會能容忍節點的不正常離開，但也因此必須再加入及離開時有較多的資訊交流。RoutingAlgorithm(NodeLookupAlgorithm：首先先檢查欲查詢的目標節點其ID是否在我與我的successors的ID的範圍內，若是即表示目標ID的代理節點為我的successor，並從successors中找出此ID的代理節點；若否，則檢查是否我有predecessor，若沒有則檢查目標ID是否座落在離我最遠的successor與我的ID之間，若是則表示我自己即為此目標ID的代理點。若非上述的情況，則尋找我的ithneighbor中，其ID最接近目標ID但又不超過目標ID的節點，並且將尋找目標ID的要求傳給該節點，由該節點採用相同的routing演算法直到找到目標ID的代理節點為止。NodeJoinAlgorithm:若系統目前沒有任何節點，則自己成為系統的第一個節點，並等待別人來加入。若欲加入的系統已經有節點存在，則以其中一個已知的節點當作gateway，由此節點詢問到目前系統中代理自己的ID的代理節點，並將此代理節點的predecessors與successors當作自己的predecessors與successors，接著在詢問此代理節點得到我的ithneighbors。接著詢問我的predecessors與successors所記錄的檔案資訊，並將該屬於自己記錄的資料記錄下來，接著告知我的代理節點有關我的加入，並再次詢問其predecessors的資訊，看看是否同時有新的節點加入，如果有則更新我的predecessors或successors的資訊。最後再告知我的predecessors與successors有關我的加入，使他們能更新其successors與predecessors的資訊，並且更新其ithneighbors的資訊。NodeLeaveAlgorithm:首先先將我自己分享的案檔的資料從系統中刪除，接著再將原本存放在我身上的檔案資訊傳給我的successor。再來在告知我的predecessors與successors有關我的離開，而收到此訊息的節點將會更新其predecessors與successors的資訊，以及更新其ithneighbor的資訊，最後就可以離開系統。FailureDetectAlgorithm:為了增加系統的正確性，每個節點將會定期的檢查自己的routingtable的資訊是否正確，即檢查位於自己routingtable的節點是否都還存在：如果有predecessor掛掉了，則詢問其他還存活的predecessor其predecessor的資訊，以補充及更新自己的predecessor的資訊；如果有successor掛掉了，則詢問其他還存活的successor其successor的資訊，以補充及更新自己的successor的資訊；若ithneighbor掛掉了，則重新lookup此ithneighbor的ID來找尋到新的代理者。ObjectInsertAlgorithm:首先先將欲分享的檔案的檔名經過SHA1hash過，而得到此檔案的objectID，再經由lookup的機制尋找到此ID的代理節點，接著告知此節點有關此案檔的資訊，資訊包含檔案的檔名、檔案大小及來源節點。而當此負責此物件資訊的代理節點接到objectinsert的資訊後，會將此資訊記錄到自己負責的object的記錄中，接著再將此objectinsert的資訊告訴其所有的predecessors與successors，而當代理節點的predecessors與successors接到這樣的資訊後，會將這些資訊放入其cache中。ObjectDeleteAlgorithm:首先先將欲刪除且已分享的檔案的檔名經過SHA1hash過，得到此檔案的objectID，再經由lookup的機制尋找到此ID的代理節點，接著告知此節點將有關此案檔的資訊移除。當負責此物件資訊的代理節點接到objectdelete的資訊後，會搜尋自己負責的object的記錄檔，看看是否有這檔案的資料，如果有則刪除，接著再把此objectdelete的資訊告訴其所有的predecessors與successors，而當此代理節點的predecessors與successors接到這樣的資訊後，會將搜尋其cache看看是否有此資料存在，若有則刪除之。ObjectSearchAlgorithm:首先先將欲搜尋的檔案的檔名經過SHA1hash過，得到此檔案的objectID，再經由lookup的機制尋找到此ID的代理節點，接著詢問此節點是否有有關此案檔的資訊。當負責此物件資訊的代理節點接到objectsearch的資訊後，會搜尋自己負責的object及cache的記錄檔，看看是否有這檔案的資料，如果有，則會先確認檔案的來源節點是否活著，若活著則回傳相關的檔案資訊；若來源節點已掛點，則會將此資料移除。ObjectKeywordSearchAlgorithm:詢問所有位於我的routingtable的節點是否含有預搜尋的keyword的字串的檔案資訊。而當接收到此搜尋的要求時，節點會檢查自己的object與cache的記錄檔，看看是否記錄的檔案其檔名包含此keyword，如果有，則會先確認檔案的來源節點是否活著，若活著則回傳相關的檔案資訊；若來源節點已掛點，則會將此資料移除。ObjectDownloadAlgorithm:當搜尋檔案得到檔案的來源資訊後，會檢查是否有許多不同的來源，若只有單一的來源則直接與來源節點要求下載檔案。若有多個來源，則會根據檔案的大小，將檔案分成許多固定大小的小區塊，而同時與不同的來源要求下載不同的檔案區塊，最後再將所有的區塊重新整合成完整的檔案，並將此檔案用objectinsert的方式分享出去。SystemCharacteristicsDynamics:因為當有節點要加入時，會先取得相關的資訊，才會告知系統新節點的加入，減少系統更正整個網路資訊的時間，並降低發生同時加入時的短暫更正時間；而離開前也是會先移除自己分享的檔案資訊，且將負責的資料傳給successor，然後告知系統其離開的資訊，可確保資料已經正確傳給其他節點來負責，故此系統可容許節點動態的加入或離開系統，或是同時的加入或離開。Scalability:因為每個節點要記錄的鄰居的資訊只是O(logN)，所以就算系統可容許264個節點，每個節點要記錄的鄰居數也不到百個，故此系統可以有很好的擴充性，可適用於目前整個網際網路。FailTolerance:因為會定期的確認routingtable的正確性，故當有節點不正常離開系統時，可以被偵測到並且更正，再加上每個檔案的資訊不只是存在該檔案ID的代理節點上，還會被cache在代理節點的predecessors與successors上，故檔案資訊會存在代理節點的附近區域，故區域內有節點不正常離開時，還可以從其他人身上得到檔案的資訊。Ondema