寬帶媒體服務(wù)技術(shù)之對(duì)等網(wǎng)絡(luò)

第四章第三代P2P網(wǎng)絡(luò)

——結(jié)構(gòu)化P2P體系Chord、CAN、Tapestry、Pastry第一頁(yè)，共八十九頁(yè)。章節(jié)內(nèi)容Chord與CFS：簡(jiǎn)單、精確的環(huán)形P2P網(wǎng)絡(luò)CAN：簡(jiǎn)單、容錯(cuò)的多維空間P2P網(wǎng)絡(luò)Tapestry與OceanStore：廣域的超立方體結(jié)構(gòu)P2P網(wǎng)絡(luò)Pastry與PAST：容錯(cuò)的混合式結(jié)構(gòu)P2P網(wǎng)絡(luò)其它結(jié)構(gòu)化P2P網(wǎng)絡(luò)：Kademlia、SkipNet等常數(shù)度P2P模型：Viceroy、Koorde和Cycloid結(jié)構(gòu)化P2P網(wǎng)絡(luò)的特點(diǎn)與分析第二頁(yè)，共八十九頁(yè)。概述2001年，學(xué)術(shù)界P2P歷史上的里程碑IEEE成立P2P專業(yè)會(huì)議、ACM會(huì)議專題等提出結(jié)構(gòu)化P2P的幾個(gè)經(jīng)典模型與應(yīng)用體系，如Chord、CAN、Tapestry、Pastry著名學(xué)術(shù)團(tuán)體與技術(shù)組織成立專門的P2P研究組，如MIT、UCBerkeley、Microsoft、Stanford第三頁(yè)，共八十九頁(yè)。4.1Chord與CFS：簡(jiǎn)單、精確的環(huán)形P2P網(wǎng)絡(luò)MIT與Berkeley的研究者01年正式發(fā)表第四頁(yè)，共八十九頁(yè)。Chord作為一個(gè)P2P網(wǎng)絡(luò)，是基于帶弦環(huán)拓?fù)浣Y(jié)構(gòu)的分布式系統(tǒng)，提供對(duì)象的存儲(chǔ)、查詢、復(fù)制、緩存，在其上可以架構(gòu)更高層的分布式數(shù)據(jù)存儲(chǔ)系統(tǒng)如協(xié)同文件系統(tǒng)CFSChord作為一個(gè)分布式散列表，只支持結(jié)構(gòu)化P2P最簡(jiǎn)單的功能：將結(jié)點(diǎn)和數(shù)據(jù)對(duì)象映射到覆蓋網(wǎng)中，但具有幾乎最優(yōu)的路由效率、確定性的對(duì)象查詢、負(fù)載均衡、高可靠性以及良好的容錯(cuò)性與自適應(yīng)，最主要的是：簡(jiǎn)單、優(yōu)美第五頁(yè)，共八十九頁(yè)。Chord的技術(shù)特點(diǎn)基于安全的一致性散列函數(shù)來(lái)分配結(jié)點(diǎn)ID和對(duì)象ID在一個(gè)有N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中，每個(gè)Chord結(jié)點(diǎn)保存O(logN)個(gè)其他結(jié)點(diǎn)的信息查詢數(shù)據(jù)對(duì)象需要的覆蓋網(wǎng)路由跳數(shù)也為O(logN)當(dāng)結(jié)點(diǎn)加入或者離開網(wǎng)絡(luò)時(shí)，為了維持網(wǎng)絡(luò)結(jié)構(gòu)、保持自適應(yīng)性所需要的消息數(shù)在O(log2N)第六頁(yè)，共八十九頁(yè)。一、Chord基礎(chǔ)工作原理Chord使用安全散列函數(shù)（如SHA-1）為每個(gè)網(wǎng)絡(luò)結(jié)點(diǎn)和數(shù)據(jù)對(duì)象分配唯一的IDnodeID=H(node屬性)，屬性可以是結(jié)點(diǎn)IP、port、公鑰、隨機(jī)數(shù)或它們的組合objectID=H(object屬性)，屬性可以是數(shù)據(jù)對(duì)象的名稱、內(nèi)容、大小、發(fā)布者或者它們的組合H是散列函數(shù)，SHA系列散列函數(shù)的Hash值長(zhǎng)度≥160，保證ID的唯一性第七頁(yè)，共八十九頁(yè)。Chord按照如下方法將數(shù)據(jù)對(duì)象（只是其索引）分配到網(wǎng)絡(luò)結(jié)點(diǎn)中所有的結(jié)點(diǎn)按照nodeID從小到大順時(shí)針排列在一個(gè)環(huán)上數(shù)據(jù)對(duì)象k（ObjectID）被分配到環(huán)上順時(shí)針方向緊隨k（包括與k相等）的第一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)稱為對(duì)象k的后繼，記做successor(k)Chord結(jié)點(diǎn)n的后繼是環(huán)上緊隨n（不等于n）的第一個(gè)結(jié)點(diǎn)，記做n.successor第八頁(yè)，共八十九頁(yè)。一個(gè)簡(jiǎn)單的Chord環(huán)（m=3）第九頁(yè)，共八十九頁(yè)。當(dāng)Chord中有新結(jié)點(diǎn)n加入時(shí)，為保持正確、一致的對(duì)象放置，原本由n的后繼結(jié)點(diǎn)負(fù)責(zé)的對(duì)象，其中一部分必須分配給n當(dāng)Chord中有舊結(jié)點(diǎn)n離開時(shí)，原本由n負(fù)責(zé)的所有對(duì)象，必須分配給n的后繼。除此以外，對(duì)象不需要再做移動(dòng)，這正是一致性散列函數(shù)所追求的性質(zhì)（問題：異常退出？）例：圖中新加入結(jié)點(diǎn)7第十頁(yè)，共八十九頁(yè)。單純的環(huán)可以工作，但效率太低為此，結(jié)點(diǎn)維護(hù)一個(gè)有m（ID位數(shù)）項(xiàng)的路由表，也稱“指向表”（fingertable），其中第i項(xiàng)指向結(jié)點(diǎn)s，s=successor(n+2i-1)，1≤i≤m，即s是在順時(shí)針方向到n的距離至少為2i-1的第一個(gè)結(jié)點(diǎn)，記做n.finger[i].nodeChord路由表的特點(diǎn)：每個(gè)結(jié)點(diǎn)只保存很少的其它結(jié)點(diǎn)信息，并且對(duì)離它越遠(yuǎn)的結(jié)點(diǎn)所知越少Chord結(jié)點(diǎn)不能從自己的路由表中看出對(duì)象k的后繼第十一頁(yè)，共八十九頁(yè)。為確定對(duì)象k的后繼（k所在的結(jié)點(diǎn)）,結(jié)點(diǎn)n在自己的路由表中查找在k之前且離k最近的結(jié)點(diǎn)j，讓j去找離k最近的結(jié)點(diǎn)，遞歸查找，最終可以找到對(duì)象k的前驅(qū)（在k之前離k最近的結(jié)點(diǎn)，記做predecessor(k)，類似，結(jié)點(diǎn)n的前驅(qū)記做n.predecessor）前驅(qū)中必然有后繼的路由表項(xiàng)，定位成功第十二頁(yè)，共八十九頁(yè)。Chord結(jié)點(diǎn)n的路由表各項(xiàng)屬性及其定義屬性定義finger[k].start(n+2k-1)mod2m,1≤k≤erval[finger[k].start,finger[k+1].start).node≥n.finger[k].start的第一個(gè)結(jié)點(diǎn)successor后繼結(jié)點(diǎn)，即finger[1].nodepredecessor前驅(qū)結(jié)點(diǎn)第十三頁(yè)，共八十九頁(yè)。二、Chord對(duì)象定位算法定位算法的三個(gè)函數(shù)的偽代碼//請(qǐng)求結(jié)點(diǎn)n尋找id的后繼

n.find_successor(id) n’=find_predecessor(id);returnn’.successor; //請(qǐng)求結(jié)點(diǎn)n尋找id的前驅(qū) n.find_predecessor(id) n’=n; while(id(n’,n’.sucessor]) n’=n’,closest_preceding_finger(id);

returnn’;第十四頁(yè)，共八十九頁(yè)。//返回id之前最近的finger

n.closest_preceding_finger(id) fori=mdownto1 if(finger[i].node∈(n,id)) returnfinger[i].node; returnn;該函數(shù)是在定位過程中真正被多次調(diào)用執(zhí)行的過程，其作用是：結(jié)點(diǎn)在自己的路由表中，從后往前找到在id前且與id最近的結(jié)點(diǎn)并返回由Chord路由表的構(gòu)造和定位算法可知：每次調(diào)用第三個(gè)函數(shù)，新找到的結(jié)點(diǎn)離對(duì)象id的距離通常比原來(lái)少一半，因此一般最多調(diào)用logN次即可定位成功第十五頁(yè)，共八十九頁(yè)。Chord路由表的簡(jiǎn)單示例假設(shè)結(jié)點(diǎn)3要找到對(duì)象1的后繼在結(jié)點(diǎn)3的路由表中，1屬于3.finger[3].interval即[7,3)結(jié)點(diǎn)3讓3.finger[3].node即結(jié)點(diǎn)0去找1結(jié)點(diǎn)0在路由表中發(fā)現(xiàn)自己的后繼1恰好是對(duì)象1的后繼，因此將1返回給結(jié)點(diǎn)3結(jié)點(diǎn)3由此知道對(duì)象1放在結(jié)點(diǎn)1中第十六頁(yè)，共八十九頁(yè)。三、Chord結(jié)點(diǎn)加入算法Chord的自適應(yīng)需要保持兩個(gè)不變的屬性每個(gè)結(jié)點(diǎn)的后繼始終正確對(duì)每個(gè)對(duì)象k，結(jié)點(diǎn)successor(k)始終負(fù)責(zé)k的索引為此，新結(jié)點(diǎn)n的加入需要完成三個(gè)任務(wù)初始化n的前驅(qū)和路由表項(xiàng)更新網(wǎng)絡(luò)其他結(jié)點(diǎn)的前驅(qū)和路由表項(xiàng)告訴其后繼將應(yīng)該由n負(fù)責(zé)的數(shù)據(jù)對(duì)象索引傳遞給n第十七頁(yè)，共八十九頁(yè)。新結(jié)點(diǎn)n連接到某個(gè)眾所周知結(jié)點(diǎn)n’，通過調(diào)用join(n’)初始化自己的狀態(tài)信息，并將自己加入到Chord網(wǎng)絡(luò)通過結(jié)點(diǎn)n’初始化n的路由表：請(qǐng)求n’幫自己查找后繼，從而更新自己的前驅(qū)，再通過多次調(diào)用n’的后繼查找函數(shù)來(lái)初始化自己的路由表第十八頁(yè)，共八十九頁(yè)。初始化本地結(jié)點(diǎn)的路由表第十九頁(yè)，共八十九頁(yè)。update_others()函數(shù)更新其他結(jié)點(diǎn)的狀態(tài)信息以反映n的加入，當(dāng)且僅當(dāng)滿足下面兩個(gè)條件時(shí)，結(jié)點(diǎn)n將成為結(jié)點(diǎn)p路由表的第i項(xiàng)：結(jié)點(diǎn)p在n之前至少2i-1結(jié)點(diǎn)p路由表的當(dāng)前第i項(xiàng)結(jié)點(diǎn)在n之后滿足這兩個(gè)條件的第一個(gè)結(jié)點(diǎn)p是結(jié)點(diǎn)(n-2i-1)的前驅(qū)，因此，update_others()首先找到該前驅(qū)，然后調(diào)用函數(shù)update_finger_table(n,i)，遞歸地更新Chord網(wǎng)中所有需要更新路由表第i項(xiàng)的結(jié)點(diǎn)信息通常情況下，一個(gè)新結(jié)點(diǎn)加入Chord網(wǎng)，需要更新信息的結(jié)點(diǎn)數(shù)為O(logN)，因此尋找和更新的時(shí)間復(fù)雜度為O(log2N)第二十頁(yè)，共八十九頁(yè)。相關(guān)偽代碼第二十一頁(yè)，共八十九頁(yè)。四、Chord自適應(yīng)算法以上算法完備、細(xì)致，但有未解決的問題：并發(fā)操作；不正常操作（如結(jié)點(diǎn)異常退出）解決方法：簡(jiǎn)化join函數(shù)，僅通過n’尋找n的后繼，其它什么也不做每個(gè)Chord結(jié)點(diǎn)周期性調(diào)用穩(wěn)定函數(shù)stabilize和路由表更新函數(shù)fix_fingers，前者修正結(jié)點(diǎn)后繼并通知其后繼修正前驅(qū)，后者在此基礎(chǔ)上隨機(jī)修正自己的路由表項(xiàng)通過合適的周期保持定位高效率第二十二頁(yè)，共八十九頁(yè)。第二十三頁(yè)，共八十九頁(yè)。五、Chord容錯(cuò)性和復(fù)制、緩存Chord中正確的后繼關(guān)系是一切工作的基礎(chǔ)無(wú)論機(jī)制如何完善，網(wǎng)絡(luò)的動(dòng)態(tài)性和不確定性都可以導(dǎo)致單后繼失效因此，實(shí)際的Chord給每個(gè)結(jié)點(diǎn)維護(hù)一個(gè)后繼列表，其中保存了該結(jié)點(diǎn)在Chord環(huán)上的r個(gè)后繼，典型地取r=O(logN)，即使結(jié)點(diǎn)失效概率為1/2，仍能正確定位將結(jié)點(diǎn)保存的數(shù)據(jù)對(duì)象復(fù)制到所有后繼中，可提高數(shù)據(jù)的可用性、持久性在Chord定位過程中，如每個(gè)中間結(jié)點(diǎn)緩存數(shù)據(jù)對(duì)象，可以提高獲取數(shù)據(jù)的速度第二十四頁(yè)，共八十九頁(yè)。六、Chord實(shí)驗(yàn)分析負(fù)載均衡負(fù)載均衡是使用一致性散列函數(shù)的結(jié)構(gòu)化P2P網(wǎng)絡(luò)的共同屬性對(duì)于Chord而言，由于數(shù)據(jù)對(duì)象被分配到其后繼中，而數(shù)據(jù)對(duì)象、結(jié)點(diǎn)的ID都是隨機(jī)、均勻產(chǎn)生的，因此每個(gè)結(jié)點(diǎn)所負(fù)擔(dān)的數(shù)據(jù)對(duì)象也應(yīng)該大致均衡此外，Chord還采用了“虛擬服務(wù)器”的方法，在一臺(tái)計(jì)算機(jī)上運(yùn)行多個(gè)Chord結(jié)點(diǎn)，可以使得結(jié)點(diǎn)各盡所能第二十五頁(yè)，共八十九頁(yè)。1萬(wàn)個(gè)結(jié)點(diǎn)，50萬(wàn)個(gè)數(shù)據(jù)對(duì)象第二十六頁(yè)，共八十九頁(yè)。第二十七頁(yè)，共八十九頁(yè)。定位路徑長(zhǎng)度理論量級(jí)為O(logN)跳實(shí)驗(yàn)中網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)取N=2k，數(shù)據(jù)對(duì)象數(shù)取100×2k，k從3取到14測(cè)量結(jié)果：路徑長(zhǎng)度平均約logN/2，是logN的一半，原因是Chord路由表的指數(shù)構(gòu)造，使其每次查找都能將目的ID與當(dāng)前結(jié)點(diǎn)ID之間的差距減小至少一半，可推導(dǎo)出平均路徑長(zhǎng)度正好是logN的一半第二十八頁(yè)，共八十九頁(yè)。第二十九頁(yè)，共八十九頁(yè)。網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)為212第三十頁(yè)，共八十九頁(yè)。七、Chord總結(jié)Chord采用帶弦環(huán)拓?fù)浣Y(jié)構(gòu)，通過一致性散列函數(shù)將結(jié)點(diǎn)、數(shù)據(jù)對(duì)象映射到覆蓋網(wǎng)上，數(shù)據(jù)對(duì)象（索引）由其后繼結(jié)點(diǎn)負(fù)責(zé)，簡(jiǎn)單、精確正是Chord最大的特點(diǎn)每個(gè)Chord結(jié)點(diǎn)維護(hù)一個(gè)很小的路由表，后繼關(guān)系是Chord定位的基礎(chǔ)，路由表可以將定位路徑長(zhǎng)度縮短為O(logN)跳Chord需要保持兩個(gè)不變的屬性才能正確工作：后繼正確、后繼對(duì)對(duì)象的索引正確Chord采用周期性的穩(wěn)定算法和路由表更新算法檢查和修正后繼關(guān)系及路由表項(xiàng)第三十一頁(yè)，共八十九頁(yè)。為保持高容錯(cuò)性，Chord采用后繼列表避免單后繼失效，此時(shí)可以對(duì)數(shù)據(jù)對(duì)象進(jìn)行復(fù)制和緩存，提高網(wǎng)絡(luò)效率第三十二頁(yè)，共八十九頁(yè)。八、CFS（Cooperative）CFS協(xié)同文件系統(tǒng)是以Chord為基礎(chǔ)的P2P協(xié)同只讀文件存儲(chǔ)系統(tǒng)，文件分塊存儲(chǔ)CFS由三層構(gòu)件組成Chord，底層定位散列表：維護(hù)路由表，定位數(shù)據(jù)塊所在的服務(wù)器DHash，分布式數(shù)據(jù)塊散列表：中間層，分布和緩存數(shù)據(jù)塊以平衡負(fù)載，復(fù)制數(shù)據(jù)塊以容錯(cuò)，并通過服務(wù)器選擇來(lái)減少時(shí)延；使用Chord定位數(shù)據(jù)塊FS，，文件系統(tǒng)：高層，從DHash層獲得數(shù)據(jù)塊并轉(zhuǎn)換為文件，給更高的應(yīng)用提供文件系統(tǒng)接口第三十三頁(yè)，共八十九頁(yè)。CFS文件系統(tǒng)類似UNIX文件目錄結(jié)構(gòu)，只是以根塊代替根目錄、以元數(shù)據(jù)塊代替子目錄、以數(shù)據(jù)塊代替文件，而以塊標(biāo)識(shí)代替文件地址CFS對(duì)Chord的改進(jìn)：采用前驅(qū)列表定位以提高定位容錯(cuò)性，使用服務(wù)器選擇減少定位時(shí)延，對(duì)結(jié)點(diǎn)ID認(rèn)證以防止ID偽造和IP虛報(bào)CFS對(duì)數(shù)據(jù)塊采用后繼復(fù)制以提高數(shù)據(jù)可用性，同時(shí)減少了客戶獲取數(shù)據(jù)的時(shí)延；采用路徑緩存提高系統(tǒng)工作效率，同時(shí)避免熱點(diǎn)數(shù)據(jù)的后繼結(jié)點(diǎn)負(fù)載過重；采用“虛擬結(jié)點(diǎn)”和“限額”方法提供負(fù)載均衡第三十四頁(yè)，共八十九頁(yè)。4.2CAN：簡(jiǎn)單、容錯(cuò)的多維空間P2P網(wǎng)絡(luò)ContentAddressableNetwork，內(nèi)容可尋址網(wǎng)絡(luò)，采用多維Torus環(huán)面拓?fù)浣Y(jié)構(gòu)，典型采用的二維空間網(wǎng)格，類似于笛卡爾平面，其結(jié)點(diǎn)編址方式也類似于點(diǎn)的編址01年[Ratnasamyetal.]在ACMSIGCOMM會(huì)議發(fā)表正式論文（與Chord同年同會(huì)）第三十五頁(yè)，共八十九頁(yè)。CAN的多維空間被動(dòng)態(tài)地分配給其網(wǎng)絡(luò)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)占有一個(gè)屬于自己的方塊并負(fù)責(zé)該方塊中所有的“點(diǎn)”（數(shù)據(jù)對(duì)象索引）第三十六頁(yè)，共八十九頁(yè)。每個(gè)結(jié)點(diǎn)維護(hù)一個(gè)路由表，記錄多維空間上的鄰居信息，如圖中結(jié)點(diǎn)D可以記錄B、C、E的ID和地址CAN采用逐步定位，每一步挑選當(dāng)前結(jié)點(diǎn)路由表中離目的結(jié)點(diǎn)最“近”的鄰居作為下一跳對(duì)一個(gè)d維CAN來(lái)說(shuō)，若維護(hù)一個(gè)有2d項(xiàng)的路由表，其定位效率為，取d=logN，即為O(logN)，其定位效率與其它結(jié)構(gòu)化P2P網(wǎng)絡(luò)一致第三十七頁(yè)，共八十九頁(yè)。以2維CAN為例，新結(jié)點(diǎn)加入時(shí)，被映射到一個(gè)點(diǎn)，其所在的方塊將一分為二，一半分給新結(jié)點(diǎn)負(fù)責(zé)，一半留給原來(lái)負(fù)責(zé)的結(jié)點(diǎn)；當(dāng)舊結(jié)點(diǎn)離開CAN時(shí)，某個(gè)鄰居必須接管它原來(lái)負(fù)責(zé)的區(qū)域，相當(dāng)于方塊合并CAN的容錯(cuò)性體現(xiàn)在路由選擇的靈活性上，由于其多維空間的拓?fù)浣Y(jié)構(gòu)，CAN不需要維護(hù)一些嚴(yán)格的不變屬性，每個(gè)鄰居對(duì)結(jié)點(diǎn)來(lái)說(shuō)都是同等地位的；在CAN中任意兩個(gè)點(diǎn)間存在多條路徑，即使很多鄰居失效，仍能以較快的速度定位目的結(jié)點(diǎn)目前還沒有基于CAN的應(yīng)用系統(tǒng)第三十八頁(yè)，共八十九頁(yè)。一、CAN網(wǎng)絡(luò)構(gòu)建結(jié)點(diǎn)加入步驟：自舉、尋找區(qū)域、加入路由表JOINSTEP1：自舉（bootstrap）新結(jié)點(diǎn)通過CAN的DNS域名獲得一個(gè)眾所周知結(jié)點(diǎn)（自舉結(jié)點(diǎn)、入口結(jié)點(diǎn)），后者提供一個(gè)列表，其中包含一些CAN現(xiàn)存結(jié)點(diǎn)的信息JOINSTEP2：尋找區(qū)域新結(jié)點(diǎn)n隨機(jī)選擇CAN空間中的一個(gè)點(diǎn)P并向P發(fā)送一個(gè)加入請(qǐng)求消息，該消息可通過列表中任意一個(gè)現(xiàn)存結(jié)點(diǎn)發(fā)送到CAN網(wǎng)絡(luò)中，并被逐步路由到P所在的區(qū)域，最終到達(dá)負(fù)責(zé)P所在區(qū)域的結(jié)點(diǎn)n’，n’按某種規(guī)則將負(fù)責(zé)區(qū)域分一半給n負(fù)責(zé)第三十九頁(yè)，共八十九頁(yè)。JOINSTEP3：加入路由表獲得自己的區(qū)域后，n從n’獲得其鄰居的IP地址等信息，并通知每個(gè)鄰居更新其路由表以反映n的存在CAN也采用了自適應(yīng)的周期性方法，每個(gè)結(jié)點(diǎn)定期向鄰居發(fā)送自己所負(fù)責(zé)的區(qū)域和自己的路由表信息，當(dāng)發(fā)現(xiàn)不一致時(shí)更新由于結(jié)點(diǎn)插入、離開或周期性更新時(shí)只需要通知鄰居結(jié)點(diǎn)，而每個(gè)結(jié)點(diǎn)的路由表記錄O(d)個(gè)鄰居，因此其自適應(yīng)開銷是O(d)的，通常比Chord和大多數(shù)P2P系統(tǒng)小得多第四十頁(yè)，共八十九頁(yè)。簡(jiǎn)單的CAN結(jié)點(diǎn)加入示例第四十一頁(yè)，共八十九頁(yè)。當(dāng)結(jié)點(diǎn)離開CAN時(shí)，通常應(yīng)顯式地將其區(qū)域及所負(fù)責(zé)數(shù)據(jù)交給一個(gè)鄰居，如果該鄰居可以合并一個(gè)規(guī)整的單區(qū)域，則完成合并，否則，離開結(jié)點(diǎn)只能將其區(qū)域交給占有最小區(qū)域的鄰居，由其暫時(shí)負(fù)責(zé)兩塊區(qū)域，但并不合并當(dāng)結(jié)點(diǎn)n失效時(shí)，依靠周期性檢測(cè)由鄰居結(jié)點(diǎn)接管其區(qū)域，解決沖突的方法：每個(gè)鄰居做完接管工作以后，向n的其它鄰居發(fā)送TAKEOVER消息，其中包括消息源的區(qū)域信息，收到該消息的結(jié)點(diǎn)比較消息源的區(qū)域和自己的區(qū)域，如果前者大，則回發(fā)TAKEOVER消息表明自己接管更合適，否則取消接管工作第四十二頁(yè)，共八十九頁(yè)。問題：隨著結(jié)點(diǎn)不斷加入、離開，CAN網(wǎng)絡(luò)的區(qū)域劃分將變得支離破碎，而且由一個(gè)結(jié)點(diǎn)負(fù)責(zé)多個(gè)結(jié)點(diǎn)的情況將越來(lái)越多，直到負(fù)載超過結(jié)點(diǎn)能力上限CAN采用“背景區(qū)域重分配”（backgroundzonereassignment）方法合并支離破碎的區(qū)域，并盡量讓一個(gè)結(jié)點(diǎn)只負(fù)責(zé)一塊區(qū)域，詳見論文[Ratnasamyetal.,2001]第四十三頁(yè)，共八十九頁(yè)。二、CAN增強(qiáng)機(jī)制：多維、多空間、多散列多維：d接近logN，路由效率高，容錯(cuò)性強(qiáng)多空間：使用多個(gè)不同的CAN空間，每個(gè)空間稱為一個(gè)“現(xiàn)實(shí)”（reality）；一個(gè)真實(shí)的網(wǎng)絡(luò)結(jié)點(diǎn)在每個(gè)CAN空間中都會(huì)被分配一塊區(qū)域，同一個(gè)數(shù)據(jù)對(duì)象的在每個(gè)空間中都會(huì)被分配給一個(gè)結(jié)點(diǎn)，從而起到復(fù)制作用，提高數(shù)據(jù)可用性；定位時(shí)，結(jié)點(diǎn)可以比較多個(gè)空間的鄰居，效率更高多散列：?jiǎn)慰臻g可以使用多散列，效果類似多空間第四十四頁(yè)，共八十九頁(yè)。三、CAN的“區(qū)域超載”區(qū)域超載：將一個(gè)區(qū)域分給多個(gè)結(jié)點(diǎn)負(fù)責(zé)一個(gè)結(jié)點(diǎn)除了維護(hù)原來(lái)的路由表，還需要維護(hù)一個(gè)“區(qū)域超載列表”，保存和自己共同負(fù)責(zé)同一區(qū)域的結(jié)點(diǎn)信息新結(jié)點(diǎn)A加入時(shí)，如果它所映射到的點(diǎn)原先由結(jié)點(diǎn)B負(fù)責(zé)，B首先檢查該區(qū)域的結(jié)點(diǎn)數(shù)是否超過上限，如未超過則不分割區(qū)域，而是將該區(qū)域也給A負(fù)責(zé)，同時(shí)A從B那里獲得“區(qū)域超載列表”；若超過上限，則進(jìn)行分割第四十五頁(yè)，共八十九頁(yè)。區(qū)域超載的好處減少定位跳數(shù)：讓多個(gè)結(jié)點(diǎn)負(fù)責(zé)同一區(qū)域等效于減少系統(tǒng)結(jié)點(diǎn)數(shù)減少每跳時(shí)延：在選擇下一跳時(shí)，由于鄰居區(qū)域由多個(gè)結(jié)點(diǎn)負(fù)責(zé)，可以從這多個(gè)結(jié)點(diǎn)中選出時(shí)延最短的作為下一跳提高容錯(cuò)性和可用性：一個(gè)區(qū)域只有在負(fù)責(zé)它的所有結(jié)點(diǎn)都失效時(shí)才不可達(dá)，且該區(qū)域的數(shù)據(jù)相當(dāng)于被復(fù)制到多個(gè)結(jié)點(diǎn)中第四十六頁(yè)，共八十九頁(yè)。CAN中的復(fù)制與緩存三種隱式復(fù)制：多空間、多散列、區(qū)域超載對(duì)熱點(diǎn)數(shù)據(jù)，CAN采用顯式復(fù)制到鄰居區(qū)域在定位路徑上放置熱點(diǎn)數(shù)據(jù)的緩存副本第四十七頁(yè)，共八十九頁(yè)。四、CAN總結(jié)CAN采用多維空間拓?fù)浣Y(jié)構(gòu)，簡(jiǎn)單、直觀，CAN空間被動(dòng)態(tài)分配給其網(wǎng)絡(luò)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)負(fù)責(zé)一塊，每個(gè)數(shù)據(jù)對(duì)象被映射到一個(gè)點(diǎn)，由負(fù)責(zé)該點(diǎn)所在區(qū)域的結(jié)點(diǎn)保持索引每個(gè)CAN結(jié)點(diǎn)維護(hù)一個(gè)路由表，記錄它在多維空間上的鄰居信息，d維CAN的定位效率為CAN的高容錯(cuò)性體現(xiàn)在其路由選擇的靈活性上：即任意兩個(gè)結(jié)點(diǎn)間存在多條路徑，部分鄰居信息的失效對(duì)定位效率影響很小新結(jié)點(diǎn)加入CAN分三步：自舉、尋找區(qū)域、加入路由表，從其加入?yún)^(qū)域中劃分一半進(jìn)行接管，采用“背景區(qū)域重分配”方法調(diào)整區(qū)域第四十八頁(yè)，共八十九頁(yè)。CAN采用多種增強(qiáng)機(jī)制提高系統(tǒng)性能，包括多維度、多空間、多散列、區(qū)域超載技術(shù)綜上所述，CAN簡(jiǎn)單、容錯(cuò)性好，可擴(kuò)展，高效率第四十九頁(yè)，共八十九頁(yè)。4.3Tapestry與OceanStore：廣域的超立方體結(jié)構(gòu)P2P網(wǎng)絡(luò)嚴(yán)格講，是基于PlaxtonMesh[1997]的網(wǎng)格形結(jié)構(gòu)，Pastry也基于此特點(diǎn)：構(gòu)建覆蓋網(wǎng)時(shí)考慮了拓?fù)湟恢滦詥栴}00年3月UCBerkeley的BenY.Zhao等成立Tapestry研究組，03年6月發(fā)布2.0版應(yīng)用廣泛，著名的OceanStore廣域存儲(chǔ)系統(tǒng)第五十頁(yè)，共八十九頁(yè)。Tapestry的應(yīng)用Bayeux提供高效、容錯(cuò)的應(yīng)用層多播Brocade提供界標(biāo)路由（LandmarkRouting）Cashmere提供匿名路由Fault-TolerantOverlayRouting基于Tapestry開發(fā)路由的冗余性，從而提供容錯(cuò)的覆蓋網(wǎng)路由OceanStore提供全球范圍內(nèi)廣域的、持久性數(shù)據(jù)存取服務(wù)SpamWatch基于Tapestry，使用基于內(nèi)容相似度的搜索引擎，提供分布式的Spam-FilteringWarp通過類型重定向提供快速移動(dòng)服務(wù)架構(gòu)第五十一頁(yè)，共八十九頁(yè)。一、Tapestry路由和定位每個(gè)結(jié)點(diǎn)有nodeID，數(shù)據(jù)對(duì)象有objectID，也稱為GUID（globallyuniqueID），每條消息有其特定應(yīng)用的AID（applicationID），類似于TCP協(xié)議中的端口號(hào)Tapestry為每個(gè)數(shù)據(jù)對(duì)象分配一個(gè)負(fù)責(zé)結(jié)點(diǎn)，稱為該對(duì)象的根（root），root(objectID)=最接近objectID的nodeIDTapestry中也采用了多散列以提高對(duì)象可用性與持久性第五十二頁(yè)，共八十九頁(yè)。Tapestry采用逐位匹配的后綴路由，每一跳匹配更多的后綴，如xxx8->xx98->x598->4598為適應(yīng)這種路由，每個(gè)Tapestry結(jié)點(diǎn)維護(hù)一個(gè)層次化的路由表（鄰居表），每一層代表與自身nodeID匹配一定位數(shù)后綴的結(jié)點(diǎn)路由的第n跳所到達(dá)的結(jié)點(diǎn)通常與目的結(jié)點(diǎn)ID至少匹配n位后綴，為找到下一跳結(jié)點(diǎn)，需要在當(dāng)前結(jié)點(diǎn)的路由表的第n+1層中，查找與目的結(jié)點(diǎn)ID匹配更多位后綴的結(jié)點(diǎn)，若找不到，則意味著定位即將完成第五十三頁(yè)，共八十九頁(yè)。結(jié)點(diǎn)0642的狀態(tài)信息，包括其對(duì)象索引、熱點(diǎn)數(shù)據(jù)管理器、對(duì)象存儲(chǔ)空間、路由表第五十四頁(yè)，共八十九頁(yè)。Tapestry路由示例，結(jié)點(diǎn)0325要發(fā)送一條消息給結(jié)點(diǎn)4598，粗線標(biāo)明了路由的每一跳第五十五頁(yè)，共八十九頁(yè)。Tapestry的路由表項(xiàng)有l(wèi)ogBN層，每層B項(xiàng)Tapestry的路由機(jī)制可以保證在N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中，任何一次定位一般都能在logBN跳之內(nèi)完成，其中B為ID編碼的進(jìn)制（base，也稱“基”）第五十六頁(yè)，共八十九頁(yè)。Tapestry結(jié)點(diǎn)S向網(wǎng)絡(luò)插入數(shù)據(jù)對(duì)象O時(shí)，要將其索引放到O的根結(jié)點(diǎn)上，為此，S向鄰居發(fā)送一條以objectID為目的地的消息，其中包含有對(duì)象索引信息如<objectID(O)，serverID(s)>，該消息逐步匹配對(duì)象ID直到?jīng)]有更多匹配位，此時(shí)即找到根結(jié)點(diǎn)，消息路徑上的所有結(jié)點(diǎn)都保存O的索引信息第五十七頁(yè)，共八十九頁(yè)。Tapestry結(jié)點(diǎn)查詢數(shù)據(jù)對(duì)象O時(shí)，也發(fā)送一條以objectID為目的地的定位消息，按后綴匹配方法逐步路由，若中間結(jié)點(diǎn)保存了索引，則定位結(jié)束，否則必將到達(dá)O的根結(jié)點(diǎn)（根結(jié)點(diǎn)可確保對(duì)象定位成功，也稱為對(duì)象的“代理”結(jié)點(diǎn)）由于一個(gè)Tapestry結(jié)點(diǎn)可能保存O的多個(gè)副本的索引，查詢時(shí)可從中找出自己認(rèn)為最近、最合適的來(lái)獲取數(shù)據(jù)，即Tapestry可以自動(dòng)幫助用戶獲取最鄰近副本第五十八頁(yè)，共八十九頁(yè)。二、Tapestry動(dòng)態(tài)結(jié)點(diǎn)算法利用反向指針和心跳消息保持路由表的更新和定位的容錯(cuò)性反向指針：backpointer，指向那些把自己作為路由表項(xiàng)的結(jié)點(diǎn)（反向結(jié)點(diǎn)）周期性發(fā)送Heartbeat消息至反向結(jié)點(diǎn)，確認(rèn)存在結(jié)點(diǎn)發(fā)現(xiàn)路由表某項(xiàng)失敗后并不立即替換它，而是過一段時(shí)間再檢測(cè)一次它是否在線，如果還不在才替換，稱為“二次機(jī)會(huì)”，防止“閃斷”路由表中每項(xiàng)保存一個(gè)“主項(xiàng)”和兩個(gè)“次要項(xiàng)”，以提高可用性第五十九頁(yè)，共八十九頁(yè)。新結(jié)點(diǎn)加入：初始化自己的路由表、更新相關(guān)結(jié)點(diǎn)的路由表、從相關(guān)結(jié)點(diǎn)移交對(duì)象索引JOINSTEP1：初始化路由表新結(jié)點(diǎn)N聯(lián)系到一個(gè)現(xiàn)存結(jié)點(diǎn)G，通過G發(fā)送以N為目的地的消息假設(shè)第i步路由到達(dá)結(jié)點(diǎn)Hi，根據(jù)后綴匹配路由算法，N和Hi應(yīng)該共享長(zhǎng)度i的后綴，則N從Hi那里獲得路由表的第i+1層項(xiàng)是合適的N對(duì)復(fù)制來(lái)的項(xiàng)進(jìn)行優(yōu)化，將更好的次要項(xiàng)結(jié)點(diǎn)改為主項(xiàng)，再查找新主項(xiàng)結(jié)點(diǎn)的路由表，比較N到每項(xiàng)的距離，迭代優(yōu)化至收斂第六十頁(yè)，共八十九頁(yè)。JOINSTEP2：更新其它結(jié)點(diǎn)路由表N通過G發(fā)送往N自己的消息，在logN跳之內(nèi)到達(dá)N的根結(jié)點(diǎn)RR首先計(jì)算它和N匹配的后綴位數(shù)p，然后通過自己路由表中的“反向指針”，告訴那些與R也匹配p位后綴的反向結(jié)點(diǎn)：如果N對(duì)它們是合適的，那么它們?cè)谧约旱穆酚杀碇刑砑覰或者用N替換原來(lái)的項(xiàng)第六十一頁(yè)，共八十九頁(yè)。JOINSTEP3：對(duì)象索引移交最初的設(shè)計(jì)：當(dāng)N發(fā)送給自己的消息到達(dá)根結(jié)點(diǎn)R時(shí)，認(rèn)為R正是需要移交對(duì)象索引給N的結(jié)點(diǎn)由于Tapestry沒有嚴(yán)格的結(jié)構(gòu)和必須維持的不變屬性，僅讓根結(jié)點(diǎn)R移交索引給N是不夠的后來(lái)的設(shè)計(jì)：將對(duì)象索引移交放在STEP2中完成，對(duì)于R所通知的反向結(jié)點(diǎn)，不僅用N更新自己的路由表，還將自己的對(duì)象索引中應(yīng)由N負(fù)責(zé)的那部分移交給N（維護(hù)拓?fù)浣Y(jié)構(gòu)）第六十二頁(yè)，共八十九頁(yè)。結(jié)點(diǎn)N的離開正常離開：N告訴自己的反向結(jié)點(diǎn)在路由表中去掉N，同時(shí)將自己負(fù)責(zé)的對(duì)象索引分別移交給它們的新根結(jié)點(diǎn)異常離開：周期性檢測(cè)并確認(rèn)N失效后，通過與結(jié)點(diǎn)加入過程中類似的多播方法更新路由表；對(duì)于對(duì)象索引，采用“軟狀態(tài)重發(fā)布”的方法：所謂“軟狀態(tài)”指對(duì)象索引都是暫時(shí)性的，“重發(fā)布”指讓數(shù)據(jù)對(duì)象的擁有者定期重新發(fā)布自己的對(duì)象索引信息，即為數(shù)據(jù)對(duì)象更新根結(jié)點(diǎn)第六十三頁(yè)，共八十九頁(yè)。三、Tapestry體系架構(gòu)第六十四頁(yè)，共八十九頁(yè)。TransportProtocols：封裝了網(wǎng)絡(luò)傳輸層，相當(dāng)于覆蓋網(wǎng)與物理網(wǎng)的中間層，典型地可以使用TCP或者UDP協(xié)議NeighborLinkManagement：鄰居鏈接管理向上層提供安全但不可靠的數(shù)據(jù)報(bào)服務(wù)，如長(zhǎng)消息的分片和組合；負(fù)責(zé)持續(xù)的鄰居鏈接管理和更新，如周期性的鄰居結(jié)點(diǎn)失效檢測(cè)、時(shí)延估計(jì)等，當(dāng)檢測(cè)到狀態(tài)變化時(shí)通知上層來(lái)處理Router：管理Tapestry結(jié)點(diǎn)路由表和對(duì)象指針數(shù)據(jù)庫(kù)，檢查所收到的消息的目的地，決定路由的下一跳；在新結(jié)點(diǎn)加入、舊結(jié)點(diǎn)離開時(shí)更新對(duì)象索引信息第六十五頁(yè)，共八十九頁(yè)。ApplicationInterface/UpcallAPI：Tapestry提供給其高層應(yīng)用的接口分布式文件系統(tǒng)/應(yīng)用層多播/協(xié)同文本過濾：基于Tapestry的各種上層應(yīng)用，不限于這三種第六十六頁(yè)，共八十九頁(yè)。四、Tapestry總結(jié)是一個(gè)面向廣域分布式數(shù)據(jù)存取、容錯(cuò)的超立方體結(jié)構(gòu)P2P模型，在構(gòu)建網(wǎng)絡(luò)時(shí)考慮了拓?fù)湟恢滦?；其最具特色的功能在于幫助用戶尋找最鄰近的?shù)據(jù)副本Tapestry中每個(gè)結(jié)點(diǎn)、數(shù)據(jù)對(duì)象、消息（應(yīng)用）都有一個(gè)全局唯一的ID，每個(gè)數(shù)據(jù)對(duì)象有一個(gè)根結(jié)點(diǎn)，它是網(wǎng)絡(luò)中nodeID與objectID最匹配的結(jié)點(diǎn)每個(gè)Tapestry結(jié)點(diǎn)維護(hù)一個(gè)路由表，其中第i層第j項(xiàng)表示與當(dāng)前nodeID后綴匹配位數(shù)為i-1位并且以j開頭的結(jié)點(diǎn)，由此實(shí)現(xiàn)效率為O(logN)跳的后綴匹配路由第六十七頁(yè)，共八十九頁(yè)。Tapestry路由表還維護(hù)“反向指針”項(xiàng)，很多重要操作如結(jié)點(diǎn)加入、離開、失效檢測(cè)和修復(fù)都用到它Tapestry體系架構(gòu)分為5層，分層有助于高層應(yīng)用的開發(fā)和各層的優(yōu)化完善第六十八頁(yè)，共八十九頁(yè)。五、OceanStore簡(jiǎn)介基于Tapestry的分布式數(shù)據(jù)存取系統(tǒng)，其目標(biāo)是提供全球范圍的廣域、持久性數(shù)據(jù)存取服務(wù)任何一臺(tái)計(jì)算機(jī)都可以加入到OceanStore系統(tǒng)，貢獻(xiàn)自己的存儲(chǔ)空間，同時(shí)獲得他人存儲(chǔ)的內(nèi)容OceanStore對(duì)數(shù)據(jù)提供傳統(tǒng)的復(fù)制、緩存功能，以提高存取速度和可用性O(shè)ceanStore建立在一個(gè)廣域、動(dòng)態(tài)、不可靠的網(wǎng)絡(luò)基礎(chǔ)上，因此對(duì)所有數(shù)據(jù)、元數(shù)據(jù)都提供了加密或者認(rèn)證的功能OceanStore采用“拜占庭式容錯(cuò)提交協(xié)議”保持副本間的強(qiáng)一致性第六十九頁(yè)，共八十九頁(yè)。OceanStore的數(shù)據(jù)持久性是通過基于版本的深度歸檔存儲(chǔ)方案來(lái)實(shí)現(xiàn)的，并以“冗余編碼”的方式分片存儲(chǔ)每個(gè)數(shù)據(jù)對(duì)象的每個(gè)版本，部分分片即可重構(gòu)原文件OceanStore通過“內(nèi)省”機(jī)制提高存取性能和容錯(cuò)性O(shè)ceanStore的構(gòu)想[Kubiatowiczetal.,2000]早于Tapestry，03年實(shí)現(xiàn)原型Pond[Rheaetal,2003]，04年6月在SourceForge上發(fā)布源碼第七十頁(yè)，共八十九頁(yè)。六、OceanStore的命名機(jī)制和存取控制OceanStore中數(shù)據(jù)對(duì)象是最基本的單元，類似于文件系統(tǒng)中的文件數(shù)據(jù)對(duì)象以只讀文件版本的方式按序保存在系統(tǒng)中，原則上每個(gè)對(duì)象的每個(gè)版本都是永久保存的，但通常只有最新版才有意義每個(gè)對(duì)象的每個(gè)版本包含著該版本數(shù)據(jù)和元數(shù)據(jù)（如目錄）以及指向其前一個(gè)版本的指針，每個(gè)版本有自己的標(biāo)識(shí)VGUIDi，對(duì)象的所有版本通過“反向指針”（與Tapestry中的不同）連成一個(gè)流，這串序列合起來(lái)有一個(gè)表示AGUID（ActiveGUID），唯一標(biāo)識(shí)一個(gè)有效的數(shù)據(jù)對(duì)象第七十一頁(yè)，共八十九頁(yè)。第七十二頁(yè)，共八十九頁(yè)。每個(gè)數(shù)據(jù)對(duì)象版本由許多塊組成，每塊有自己的標(biāo)識(shí)BGUID（BlockGUID），這些塊自頂向下組織成一棵類似B樹的結(jié)構(gòu)樹根為rootblock，保存該版本的元數(shù)據(jù)M和向下的指針，根塊的BGUID通常被作為該版本的VGUID中間塊為indirectblocks，只保存向下的指針樹底層的葉子叫做datablocks，保存真正的數(shù)據(jù)作為索引的根塊和數(shù)據(jù)塊里的指針，實(shí)際上是其子塊的BGUID，版本間可以通過BGUID共享數(shù)據(jù)（圖中copyonwrite）第七十三頁(yè)，共八十九頁(yè)。OceanStore有效對(duì)象AGUID的結(jié)構(gòu)：由對(duì)象擁有者的公鑰和可讀對(duì)象名拼接起來(lái)的安全散列值可避免對(duì)象名沖突，且起到完整性檢查的作用第七十四頁(yè)，共八十九頁(yè)。OceanStore的BGUID生成過程：由分片產(chǎn)生散列值，再逐層向上合并生成散列值每個(gè)分片除了存儲(chǔ)分片數(shù)據(jù)，還需要存儲(chǔ)它從底層到頂層所需的兄弟散列值（約logN個(gè)，N為分片數(shù)），以用于驗(yàn)證分片的數(shù)據(jù)完整性第七十五頁(yè)，共八十九頁(yè)。從對(duì)象的AGUID安全映射到其最新版本的VGUID的機(jī)制，兩種方法：每個(gè)數(shù)據(jù)對(duì)象在系統(tǒng)中對(duì)應(yīng)一個(gè)“主環(huán)”（primaryring），由多臺(tái)服務(wù)器組成，使用“拜占庭一致性協(xié)議”來(lái)維護(hù)映射，并將用戶發(fā)出的對(duì)象更新操作序列化執(zhí)行若某個(gè)對(duì)象沒有主環(huán)，則映射被存儲(chǔ)在稱為墓碑的結(jié)構(gòu)里（圖中）第七十六頁(yè)，共八十九頁(yè)。OceanStore墓碑結(jié)構(gòu)Active對(duì)象主環(huán)的公鑰和私鑰密文對(duì)象最新的VGUID負(fù)責(zé)方（responsibleparty）的公鑰和私鑰密文第七十七頁(yè)，共八十九頁(yè)。OceanStore對(duì)系統(tǒng)中數(shù)據(jù)對(duì)象提供兩種原始類型的“存取控制”：讀者限制和寫者限制讀者限制：為阻止不合法的讀者，OceanStore中所有非完全公開的數(shù)據(jù)都被加密，密鑰分發(fā)給那些允許讀的用戶。如果要撤銷原來(lái)發(fā)出的讀允許，對(duì)象擁有者要么刪除數(shù)據(jù)對(duì)象，要么用新密鑰加密原對(duì)象寫者限制：要求所有的寫操作都必須簽名，行為良好的服務(wù)器和客戶可以通過存取控制鏈（ACL,accesscontrollist）來(lái)驗(yàn)證寫操作。對(duì)象的存取控制鏈?zhǔn)怯蓪?duì)象擁有者所簽名的、授予特定用戶對(duì)該對(duì)象的操作特權(quán)第七十八頁(yè)，共八十九頁(yè)。七、OceanStore的路由和定位算法全局查詢Tapestry的后綴匹配路由算法，速度較慢，但保證成功概率查詢快速定位局部性的臨近數(shù)據(jù)對(duì)象，速度快，但不保證成功為網(wǎng)絡(luò)中每條有向邊保存一個(gè)AttenuatedBloomFilters數(shù)據(jù)結(jié)構(gòu)，以表示沿該邊可以定位到的對(duì)象信息，查詢消息在Bloomfilter的指導(dǎo)下沿著有向邊路由第七十九頁(yè)，共八十九頁(yè)。BloomFilter是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它利用位數(shù)組很簡(jiǎn)潔地表示一個(gè)集合，并能判斷一個(gè)元素是否屬于這個(gè)集合。BloomFilter的這種高效是有一定代價(jià)的：在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會(huì)把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合（falsepositive）。因此，BloomFilter不適合那些“零錯(cuò)誤”的應(yīng)用場(chǎng)合。而在能容忍低錯(cuò)誤率的應(yīng)用場(chǎng)合下，BloomFilter通過極少的錯(cuò)誤換取了存儲(chǔ)空間的極大節(jié)省。請(qǐng)自學(xué)BloomFilter的工作原理第八十頁(yè)，共八十九頁(yè)。概率查詢示例：n1查找對(duì)象XBloomFiltern1的有向邊Filter顯示n2可能是一個(gè)路由到X的中間結(jié)點(diǎn)第八十一頁(yè)，共八十九頁(yè)。八、OceanStore的更新模型任何一個(gè)數(shù)據(jù)對(duì)象都有一個(gè)“主副本環(huán)”（primaryreplica，也稱主環(huán)或者內(nèi)環(huán)），是數(shù)據(jù)對(duì)象歸檔存儲(chǔ)、更新、最新版本獲得的核心設(shè)施用戶更新對(duì)象時(shí)，首先發(fā)出更新請(qǐng)求，通過Tapestry底層網(wǎng)絡(luò)將請(qǐng)求發(fā)到對(duì)象主環(huán)，主環(huán)服務(wù)器之間序列化所收到的更新請(qǐng)求并執(zhí)行；然后，主環(huán)服務(wù)器將新數(shù)據(jù)對(duì)象深度歸檔存儲(chǔ)（提供數(shù)據(jù)持久性