基于分布式查詢服務Chord的P2P系統構FrankDabek,EmmaBrunskill,M.FransKaashoek,DavidKargerRobertMorris,IonStoica:HariBalakrishnan我們認為，一個P2P系統的問題在于去中心化的網絡中定位文件，并據此提出了一種分布式查詢系統原型Chord。通過對應用程序施加一定的約束， 簡 Chord系統概 后繼計算函 節點插 算法的附加細 ChordAPI Chord的設計方 分布式哈希服 可靠性的實 性能的提 服務均衡負載的系統設 可信 研究現 開放性問 相關工 總 參考文 P2P架構承諾為廣大因特網用戶提供資源，這一架構面對的主要，我們認為，近期的P2P系統有許多屬性值得關注，包括冗余，持久性，高效的數據定位，出系統可擴展性和魯棒性減弱的代價。例如，net[5][6]的設計使之很難檢測到哪一臺客戶機了哪一部分的數據，這一點影響了net檢索數據的能力。rd的設計目的在于提供必要的功能以實現通用系統，同時保持盡可能大的靈活性。d是一個基于一致性哈希]的高效分布式查詢系統，它在D空間和節點之間提供特定的映，一個節可以是一主機或是地址和端標識進程，每個rdI關聯。r將每一個映射到值大于通過使用可以將次的名稱轉換成ChordID的附加層，Chord可以提供功能強大的查找服務。根據Chord原型和P2P給出一個分布式哈希表（DHASH）的大致設計，圖1.1給出了應用的功能分布。1圖1.1層次化的ChordChord是高效的：在網絡中有N臺服務器的情況下，有很大的概率在O(logN)級的消1.2(a)1.2(b)1.2(c)ChordIDaIDaIDa為實現后繼功能，所有節點共同一個被稱作指針表的m項路由表，該路由表O(logN)m的間隔范圍內對m項的查詢應答。節點r的k階間隔如下定義：[(r+2k-1)mod2m,(r2k)mod2m)。圖1.2(a)給出了一個簡單的例子，m=3，節2,5,7被標明，節5的直接后繼即(5+20)mod23=6，或節點7。每個節點還一個指向自己前驅的指針，出于對稱性考慮，我們還定義了相應的直接后繼(指針表中的第一項)。總之，每個節點至多為O(logN)個其他節點指針表，相對于傳統一致性哈希中每個節點其他所有節點而言，這是一項顯著的優勢如果是，搜索終止，返回r的后繼節點；否則，rf的前驅中最大的節s，重復上述過程直至搜索結束。舉例來說，假設系統處于穩定狀態（所有路由表中包含正確的信息-2(a)2ID6的后6ID567定義的間隔n步的起始節點即第(n-1)步的搜索結果。后繼計算函數也可以迭代實現，在迭代實現將有詳細描述它們的指針表以反映r的存在（1.2(b)1.2(c)。rrk可以由r的路由表或前驅指針確定，這些節點在r的指導下更新指針表。時間推移而收斂。故障處理也需節點除直接后繼之外的k個后繼。圖2.2：DHASHAPI(a)根據鍵值插入(b)，鍵值存在則返回與之相關的值，不存在返回ChordAPI的層次架構：最小化功能和信息為使這種可行但仍保留抽象的，我們允許層為它們感的活動回調函數（見圖21并且對后繼函數進行計算。Nexthop(j,k)向節點j請求其指針表中大于k的最小項，這樣使得調用者可以單步執行Chord查詢算法。例如，當節點加入或離開系統時，DHASH層（在3.1節中描述）使用回調接口改變相應的值。DHASH同樣對后繼函數逐步計算以對搜索路徑進行緩存。能在大型P2P文件共享應用中得到使用。這種應用允許一組合作用戶他們的網絡Chord并不是一個系統，它的鍵與節點關聯而非與值關聯，Chord系統的一個有用的初級擴展就是分布式哈希（DHASH）,此層的API如圖2.2所示。DHASH::insert160ChordIDkk的后繼中Chord接口分離的RPC接口完成。為使在與鍵相關聯的后繼節點中的值不變，DHASH利用Chord提供的回調接口監控節點的到來和離開，并適當地轉移值。例如，如果與鍵7相關的值被在節點1099Chord，DHASH繼承ChordO(logN)RPC來執行，不需要集中控制。DHASHChord的特性實現更好的可靠性和性能，為確保遇到節點故障的情況下查詢也能成功，DHASH會在某個鍵的直接后繼和以下r個后繼中與之相關聯的值，為滿足冗余的要求，參數r的值可以改變。，而這正是我們在Chord與其的交互中希望看到的。DHASHChord的每個節點上，以便確定鍵的后繼（路徑由Chord的后繼計算函數返回。函數，如果某個中間節點能夠返回此前緩存的v，則查找提前結束。Chord的高度分布性有助于抵擋大量但不是全部的服務，例如，Chord對定位。對于其他的，我們需要采取額外的對策。基于Chord的系統可能遭到大量無用數據的導致合法的文件被去除。通ID，這些節點可以用以下的方法刪除一部分數據：把自IDIP地址的哈希值，并由系統中其余節點給予證實的方法加以防御。節點不能正確執行導致任意行為的指令，一個節點可以通過驗證其詢問其前驅是否為l，一組這樣的節點可以將合法節點排除在外而構成自穩定的均衡負載的系統設在將Chord作為設計P2P系統時，我們著如何在不考慮文件頻我們是否可以直接把DHASH用作P2P文件系統呢？如果這樣設計，文件的文件被越來越頻繁地，傳送這一文件的負擔是無法被分流的。3.3節中提到的緩存策略只對處理小型文件有幫助，對于大型文件則為力。一種可行的方案是間接使用DHASH：DHASH將文件標識映射到一個由可文IPDHASHDNS的功能但并不依賴IP地址被選定，可以使用其他傳輸協議（HTTPSSLSFS等）進行我們可以為文件一個動態更新的潛在服務器列表，這樣我們就可以在這些服頻度的解決方案和Chord協議機制之間實現更緊的耦合。唯一的名稱。這樣一個等效的文件系統也可以包含：在我們的原型實現中，文件目錄被映射到用戶的本地命名空間中，文件名又被映射到文件中。們分發這些文件，并在文件被頻繁時分流負載。S字節的文件可能需要????????B是塊大小，L 前文描述的系統目前正在研發，Chord協議已經完成了設計、實現和測試1。在BerkeleyMillenniumCluster進行的多達1000節點的測試證明在這一規模的系統中Chord1Chord系統上覆蓋一個混合式網絡[4]可能允許閱讀和。提供查詢操作給我們留下了一個開放性問題，作為一種選擇，我們可以向網提供Chord服務，這樣我們就可以依靠網的索引服務進行索引。度量變得。GRID系統[12]的一維近似實現。OceanStore[11]使用了由xton等人提出的，比Chord更復雜但能提供更可靠保障的分布式數據。CAN運用d爾坐標系來實現分布式哈希表[16]，CAN的操作很容易實現，但需要額外的協議將ID空間定期重映射到節點上。Chord算法也與PAST定位算法極為相似。化系統，以net[15]，Publius[13]，HavenProject[8]為例，使用加密的 Chord的定位算法較之Gnula基于路由的廣播更為有效，Chord的去中心化屬性可以避免Nasper中單一節點失效而造成的查找失敗Ohaha系統[3]使用類似于一致性哈希的算法進行ID映射，使用類似于 net的方法進行文件檢索，也因此與 net具有相來，Chord系統可以對他們進行取舍，以提供更好的性能、可靠性和可信度。Gnulawebsite. Napster. Ohaha. DavidChaum.Untraceableelectronicmail,returnaddressesanddigitalCommunicationsoftheA.C.M.,24(2):84-88,IanClarke.Adistributeddecentralisedinformationstorageandretrievalsystem.Master'sthesis,UniversityofEdinburgh,1999.IanClarke,OscarSandberg,BrandonWiley,andThreW.H:Adistributedanonymousinformationstorageandretrievalsystem.InProceedingsoftheWorkshoponDesignIssuesinAnonymityandUnobservability,Berkeley,California,JuneC.xton,R.Rajaraman,andA.Richa.Accessingnearbycopiesofreplicatedobjectsinadistributedenvironment.InProceedingsoftheACMSPAA,pages311-320,Newport,RhodeIsland,June1997.RogerDingledine,DavidMolnar,andMichaelJ. dman.The Havenproject:Distributedanonymousstorageservice.InProceedingsoftheWorkshoponDesignIssuesinAnonymityandUnobservability,July2000.KevinFu,M.FransKaashoek,andDavidMazikres.Fastandsecuredistributedread-onlyfilesystem.InProceedingsofthe4thUSENIXSymposiumonOperatingSystemsDesignandImplementation(OSDI2000),pages181-196,SanDiego,California,October2000.D.Karger,E.Lehman,ELeighton,M.Levine,D.Lewin,andR.Panigrahy.Consistenthashingandrandomtrees:Distributedcachingprotocolsforrelievinghotspotsontheworldwideweb.InProceedingsofthe29thAnnualACMSymposiumonTheoryofComputing,pages654-663,May1997.JohnKubiatowicz,DavidBindel,YanChen,StevenCzerwinski,PatrickEaton,Geels,RamakrishnaGummadi,SeanRhea,HakimWeatherspoon,WestleyWeimer,ChrisWells,andBenZhao.Oceanstore:Anarchitectureforglobal-scalepersistentstorage.InProceeedingsoftheNinthinternationalConferenceonArchitecturalSupportforProgrammingLanguagesandOperatingSystems(ASPLOS2000),Boston,MA,November2000.JinyangLi,JohnJannotti,DouglasS.J.DeCouto,DavidR.Karger,andRobertMorris.Ascalablelocationserviceforgeographicadhocrouting.InProceedingsofthe6thACIMInternationalConferenceonComputingandNetworking( '00),pages120-130,Boston,Massachusetts,AugustAvielD.RubinMarcWaldmanandLorrieFaithCranor.Publius:Atamper-evident,censorship-resistant,webpublishingsystem.InProc.9thUSENIXSecuritySymposium,pages59-72,August2000.DavidMazieres,MichaelKaminsky,M.FransKaashoek,andEmmettWitchel.Separatingkeymanagementfromfilesystemsecurity.InProceedingsofthe17thACMSymposiumonOperat