《宽带媒体服务技术之对等网络》由会员分享，可在线阅读，更多相关《宽带媒体服务技术之对等网络（88页珍藏版）》请在金锄头文库上搜索。
1、宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络科大科大10系系 王雷王雷第四章 第三代P2P网络 结构化P2P体系Chord、CAN、Tapestry、Pastry1宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络章节内容nChord与CFS：简单、精确的环形P2P网络nCAN：简单、容错的多维空间P2P网络nTapestry与OceanStore：广域的超立方体结构P2P网络nPastry与PAST：容错的混合式结构P2P网络n其它结构化P2P网络：Kademlia、SkipNet等n常数度P2P模型：Viceroy、Koorde和Cycloidn结构化P2P网络的特点与分析2宽带
2、媒体服务技术之对等网络宽带媒体服务技术之对等网络概述n2001年，学术界P2P历史上的里程碑nIEEE成立P2P专业会议、ACM会议专题等n提出结构化P2P的几个经典模型与应用体系，如Chord、CAN、Tapestry、Pastryn著名学术团体与技术组织成立专门的P2P研究组，如MIT、UC Berkeley、Microsoft、Stanford3宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络4.1 Chord与CFS：简单、精确的环形P2P网络nMIT与Berkeley的研究者01年正式发表4宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nChord作为一个P2P网络，是基于
3、带弦环拓扑结构的分布式系统，提供对象的存储、查询、复制、缓存，在其上可以架构更高层的分布式数据存储系统如协同文件系统CFSnChord作为一个分布式散列表，只支持结构化P2P最简单的功能：将结点和数据对象映射到覆盖网中，但具有几乎最优的路由效率、确定性的对象查询、负载均衡、高可靠性以及良好的容错性与自适应，最主要的是：简单、优美5宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nChord的技术特点q基于安全的一致性散列函数来分配结点ID和对象IDq在一个有N个结点的网络中，每个Chord结点保存O(logN)个其他结点的信息q查询数据对象需要的覆盖网路由跳数也为O(logN)q当结点加入
4、或者离开网络时，为了维持网络结构、保持自适应性所需要的消息数在O(log2N)6宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、Chord基础工作原理nChord使用安全散列函数（如SHA-1）为每个网络结点和数据对象分配唯一的IDqnodeID=H(node属性)，属性可以是结点IP、port、公钥、随机数或它们的组合qobjectID=H(object属性)，属性可以是数据对象的名称、内容、大小、发布者或者它们的组合qH是散列函数，SHA系列散列函数的Hash值长度160，保证ID的唯一性7宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nChord按照如下方法将数据对象（只是
5、其索引）分配到网络结点中q所有的结点按照nodeID从小到大顺时针排列在一个环上q数据对象k（ObjectID）被分配到环上顺时针方向紧随k（包括与k相等）的第一个结点，该结点称为对象k的后继，记做successor(k)nChord结点n的后继是环上紧随n（不等于不等于n）的第一个结点，记做n.successor8宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一个简单的Chord环（m=3）9宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n当Chord中有新结点n加入时，为保持正确、一致的对象放置，原本由n的后继结点负责的对象，其中一部分必须分配给nn当Chord中有旧结点n离开
6、时，原本由n负责的所有对象，必须分配给n的后继。除此以外，对象不需要再做移动，这正是一致性散列函数所追求的性质（问题：异常退出？）n例：图中新加入结点710宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n单纯的环可以工作，但效率太低n为此，结点维护一个有m（ID位数）项的路由表，也称“指向表”（finger table），其中第i项指向结点s，s=successor(n+2i-1)，1im，即s是在顺时针方向到n的距离至少为2i-1的第一个结点，记做n.fingeri.nodenChord路由表的特点：q每个结点只保存很少的其它结点信息，并且对离它越远的结点所知越少qChord结点不能从
7、自己的路由表中看出对象k的后继11宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n为确定对象k的后继（k所在的结点）,结点n在自己的路由表中查找在k之前且离k最近的结点j，让j去找离k最近的结点，递归查找，最终可以找到对象k的前驱（在k之前离k最近的结点，记做predecessor(k)，类似，结点n的前驱记做n.predecessor）n前驱中必然有后继的路由表项，定位成功12宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nChord结点n的路由表各项属性及其定义属性定义fingerk.start(n+2k-1)mod2m, 1km.intervalfingerk.start,
8、fingerk+1.start).noden.fingerk.start的第一个结点successor后继结点，即finger1.nodepredecessor前驱结点13宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、Chord对象定位算法n定位算法的三个函数的伪代码q/请求结点n寻找id的后继 n.find_successor(id) n=find_predecessor(id); return n.successor;/请求结点n寻找id的前驱n.find_predecessor(id) n=n; while(id (n,n.sucessor)n=n,closest_preced
9、ing_finger(id); return n;14宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络q/返回id之前最近的finger n.closest_preceding_finger(id) for i=m downto 1 if (fingeri.node(n,id)return fingeri.node;return n;q该函数是在定位过程中真正被多次调用执行的过程，其作用是：结点在自己的路由表中，从后往前找到在id前且与id最近的结点并返回n由Chord路由表的构造和定位算法可知：每次调用第三个函数，新找到的结点离对象id的距离通常比原来少一半，因此一般最多调用logN次即
10、可定位成功15宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络Chord路由表的简单示例假设结点3要找到对象1的后继n在结点3的路由表中，1属于3.finger3.interval即7,3)n结点3让3.finger3.node即结点0去找1n结点0在路由表中发现自己的后继1恰好是对象1的后继，因此将1返回给结点3n结点3由此知道对象1放在结点1中16宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、Chord结点加入算法nChord的自适应需要保持两个不变的属性q每个结点的后继始终正确q对每个对象k，结点successor(k)始终负责k的索引n为此，新结点n的加入需要完成三个任务
11、q初始化n的前驱和路由表项q更新网络其他结点的前驱和路由表项q告诉其后继将应该由n负责的数据对象索引传递给n17宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n新结点n连接到某个众所周知结点n，通过调用join(n)初始化自己的状态信息，并将自己加入到Chord网络通过结点n初始化n的路由表：请求n帮自己查找后继，从而更新自己的前驱，再通过多次调用n的后继查找函数来初始化自己的路由表18宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络q初始化本地结点的路由表19宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nupdate_others()函数更新其他结点的状态信息以反映n的加入
12、，当且仅当满足下面两个条件时，结点n将成为结点p路由表的第i项：q结点p在n之前至少2i-1q结点p路由表的当前第i项结点在n之后n满足这两个条件的第一个结点p是结点(n-2i-1)的前驱，因此，update_others()首先找到该前驱，然后调用函数update_finger_table(n,i)，递归地更新Chord网中所有需要更新路由表第i项的结点信息n通常情况下，一个新结点加入Chord网，需要更新信息的结点数为O(logN)，因此寻找和更新的时间复杂度为O(log2N)20宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络相关伪代码21宽带媒体服务技术之对等网络宽带媒体服务技术之
13、对等网络四、Chord自适应算法n以上算法完备、细致，但有未解决的问题：并发操作；不正常操作（如结点异常退出）n解决方法：q简化join函数，仅通过n寻找n的后继，其它什么也不做q每个Chord结点周期性调用稳定函数stabilize和路由表更新函数fix_fingers，前者修正结点后继并通知其后继修正前驱，后者在此基础上随机修正自己的路由表项n通过合适的周期保持定位高效率22宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络23宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络五、Chord容错性和复制、缓存nChord中正确的后继关系是一切工作的基础n无论机制如何完善，网络的动态性和
14、不确定性都可以导致单后继失效n因此，实际的Chord给每个结点维护一个后继列表，其中保存了该结点在Chord环上的r个后继，典型地取r=O(logN)，即使结点失效概率为1/2，仍能正确定位n将结点保存的数据对象复制到所有后继中，可提高数据的可用性、持久性n在Chord定位过程中，如每个中间结点缓存数据对象，可以提高获取数据的速度24宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络六、Chord实验分析n负载均衡q负载均衡是使用一致性散列函数的结构化P2P网络的共同属性q对于Chord而言，由于数据对象被分配到其后继中，而数据对象、结点的ID都是随机、均匀产生的，因此每个结点所负担的数据对
15、象也应该大致均衡q此外，Chord还采用了“虚拟服务器”的方法，在一台计算机上运行多个Chord结点，可以使得结点各尽所能25宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络1万个结点，50万个数据对象26宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络27宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n定位路径长度q理论量级为O(logN)跳q实验中网络结点数取N=2k，数据对象数取1002k，k从3取到14q测量结果：路径长度平均约logN/2，是logN的一半，原因是Chord路由表的指数构造，使其每次查找都能将目的ID与当前结点ID之间的差距减小至少一半，可推导出平均路径
16、长度正好是logN的一半28宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络29宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络网络结点数为21230宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络七、Chord总结nChord采用带弦环拓扑结构，通过一致性散列函数将结点、数据对象映射到覆盖网上，数据对象（索引）由其后继结点负责，简单、精确正是Chord最大的特点n每个Chord结点维护一个很小的路由表，后继关系是Chord定位的基础，路由表可以将定位路径长度缩短为O(logN)跳nChord需要保持两个不变的属性才能正确工作：后继正确、后继对对象的索引正确nChord采用周期性的
17、稳定算法和路由表更新算法检查和修正后继关系及路由表项31宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n为保持高容错性，Chord采用后继列表避免单后继失效，此时可以对数据对象进行复制和缓存，提高网络效率32宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络八、CFS（Cooperative ）nCFS协同文件系统是以Chord为基础的P2P协同只读文件存储系统，文件分块存储nCFS由三层构件组成qChord，底层定位散列表：维护路由表，定位数据块所在的服务器qDHash，分布式数据块散列表：中间层，分布和缓存数据块以平衡负载，复制数据块以容错，并通过服务器选择来减少时延；使用Chor
18、d定位数据块qFS，文件系统：高层，从DHash层获得数据块并转换为文件，给更高的应用提供文件系统接口33宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nCFS文件系统类似UNIX文件目录结构，只是以根块代替根目录、以元数据块代替子目录、以数据块代替文件，而以块标识代替文件地址nCFS对Chord的改进：采用前驱列表定位以提高定位容错性，使用服务器选择减少定位时延，对结点ID认证以防止ID伪造和IP虚报nCFS对数据块采用后继复制以提高数据可用性，同时减少了客户获取数据的时延；采用路径缓存提高系统工作效率，同时避免热点数据的后继结点负载过重；采用“虚拟结点”和“限额”方法提供负载均衡34
19、宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络4.2 CAN：简单、容错的多维空间P2P网络nContent Addressable Network，内容可寻址网络，采用多维Torus环面拓扑结构，典型采用的二维空间网格，类似于笛卡尔平面，其结点编址方式也类似于点的编址n01年Ratnasamy et al.在ACM SIGCOMM会议发表正式论文（与Chord同年同会）35宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nCAN的多维空间被动态地分配给其网络结点，每个结点占有一个属于自己的方块并负责该方块中所有的“点”（数据对象索引）36宽带媒体服务技术之对等网络宽带媒体服务技术之
20、对等网络n每个结点维护一个路由表，记录多维空间上的邻居信息，如图中结点D可以记录B、C、E的ID和地址nCAN采用逐步定位，每一步挑选当前结点路由表中离目的结点最“近”的邻居作为下一跳n对一个d维CAN来说，若维护一个有2d项的路由表，其定位效率为 ，取d=logN，即为O(logN)，其定位效率与其它结构化P2P网络一致37宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n以2维CAN为例，新结点加入时，被映射到一个点，其所在的方块将一分为二，一半分给新结点负责，一半留给原来负责的结点；当旧结点离开CAN时，某个邻居必须接管它原来负责的区域，相当于方块合并nCAN的容错性体现在路由选择的
21、灵活性上，由于其多维空间的拓扑结构，CAN不需要维护一些严格的不变属性，每个邻居对结点来说都是同等地位的；在CAN中任意两个点间存在多条路径，即使很多邻居失效，仍能以较快的速度定位目的结点n目前还没有基于CAN的应用系统38宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、CAN网络构建n结点加入步骤：自举、寻找区域、加入路由表nJOIN STEP1：自举（bootstrap）q新结点通过CAN的DNS域名获得一个众所周知结点（自举结点、入口结点），后者提供一个列表，其中包含一些CAN现存结点的信息nJOIN STEP2：寻找区域q新结点n随机选择CAN空间中的一个点P并向P发送一个加入
22、请求消息，该消息可通过列表中任意一个现存结点发送到CAN网络中，并被逐步路由到P所在的区域，最终到达负责P所在区域的结点n，n按某种规则将负责区域分一半给n负责39宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nJOIN STEP3：加入路由表q获得自己的区域后，n从n获得其邻居的IP地址等信息，并通知每个邻居更新其路由表以反映n的存在qCAN也采用了自适应的周期性方法，每个结点定期向邻居发送自己所负责的区域和自己的路由表信息，当发现不一致时更新q由于结点插入、离开或周期性更新时只需要通知邻居结点，而每个结点的路由表记录O(d)个邻居，因此其自适应开销是O(d)的，通常比Chord和大多
23、数P2P系统小得多40宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络简单的CAN结点加入示例41宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n当结点离开CAN时，通常应显式地将其区域及所负责数据交给一个邻居，如果该邻居可以合并一个规整的单区域，则完成合并，否则，离开结点只能将其区域交给占有最小区域的邻居，由其暂时负责两块区域，但并不合并n当结点n失效时，依靠周期性检测由邻居结点接管其区域，解决冲突的方法：每个邻居做完接管工作以后，向n的其它邻居发送TAKEOVER消息，其中包括消息源的区域信息，收到该消息的结点比较消息源的区域和自己的区域，如果前者大，则回发TAKEOVER消息表
24、明自己接管更合适，否则取消接管工作42宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n问题：随着结点不断加入、离开，CAN网络的区域划分将变得支离破碎，而且由一个结点负责多个结点的情况将越来越多，直到负载超过结点能力上限nCAN采用“背景区域重分配”（background zone reassignment）方法合并支离破碎的区域，并尽量让一个结点只负责一块区域，详见论文Ratnasamy et al.,200143宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、CAN增强机制：多维、多空间、多散列n多维：d接近logN，路由效率高，容错性强n多空间：使用多个不同的CAN空间，每
25、个空间称为一个“现实”（reality）；一个真实的网络结点在每个CAN空间中都会被分配一块区域，同一个数据对象的在每个空间中都会被分配给一个结点，从而起到复制作用，提高数据可用性；定位时，结点可以比较多个空间的邻居，效率更高n多散列：单空间可以使用多散列，效果类似多空间44宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、CAN的“区域超载”n区域超载：将一个区域分给多个结点负责n一个结点除了维护原来的路由表，还需要维护一个“区域超载列表”，保存和自己共同负责同一区域的结点信息n新结点A加入时，如果它所映射到的点原先由结点B负责，B首先检查该区域的结点数是否超过上限，如未超过则不分割区
26、域，而是将该区域也给A负责，同时A从B那里获得“区域超载列表”；若超过上限，则进行分割45宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n区域超载的好处q减少定位跳数：让多个结点负责同一区域等效于减少系统结点数q减少每跳时延：在选择下一跳时，由于邻居区域由多个结点负责，可以从这多个结点中选出时延最短的作为下一跳q提高容错性和可用性：一个区域只有在负责它的所有结点都失效时才不可达，且该区域的数据相当于被复制到多个结点中46宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nCAN中的复制与缓存q三种隐式复制：多空间、多散列、区域超载q对热点数据，CAN采用显式复制到邻居区域q在定位路径上
27、放置热点数据的缓存副本47宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络四、CAN总结nCAN采用多维空间拓扑结构，简单、直观，CAN空间被动态分配给其网络结点，每个结点负责一块，每个数据对象被映射到一个点，由负责该点所在区域的结点保持索引n每个CAN结点维护一个路由表，记录它在多维空间上的邻居信息，d维CAN的定位效率为nCAN的高容错性体现在其路由选择的灵活性上：即任意两个结点间存在多条路径，部分邻居信息的失效对定位效率影响很小n新结点加入CAN分三步：自举、寻找区域、加入路由表，从其加入区域中划分一半进行接管，采用“背景区域重分配”方法调整区域48宽带媒体服务技术之对等网络宽带媒体
28、服务技术之对等网络nCAN采用多种增强机制提高系统性能，包括多维度、多空间、多散列、区域超载技术n综上所述，CAN简单、容错性好，可扩展，高效率49宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络4.3 Tapestry与OceanStore：广域的超立方体结构P2P网络n严格讲，是基于Plaxton Mesh1997的网格形结构，Pastry也基于此n特点：构建覆盖网时考虑了拓扑一致性问题n00年3月UC Berkeley的Ben Y. Zhao等成立Tapestry研究组，03年6月发布2.0版n应用广泛，著名的OceanStore广域存储系统50宽带媒体服务技术之对等网络宽带媒体服务
29、技术之对等网络Tapestry的应用Bayeux提供高效、容错的应用层多播Brocade提供界标路由（Landmark Routing）Cashmere提供匿名路由Fault-Tolerant Overlay Routing基于Tapestry开发路由的冗余性，从而提供容错的覆盖网路由OceanStore提供全球范围内广域的、持久性数据存取服务SpamWatch基于Tapestry，使用基于内容相似度的搜索引擎，提供分布式的Spam-FilteringWarp通过类型重定向提供快速移动服务架构51宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络一、Tapestry路由和定位n每个结点有no
30、deID，数据对象有objectID，也称为GUID（globally unique ID），每条消息有其特定应用的AID（application ID），类似于TCP协议中的端口号nTapestry为每个数据对象分配一个负责结点，称为该对象的根（root），root(objectID)=最接近objectID的nodeIDnTapestry中也采用了多散列以提高对象可用性与持久性52宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTapestry采用逐位匹配的后缀路由，每一跳匹配更多的后缀，如xxx8-xx98-x598-4598n为适应这种路由，每个Tapestry结点维护一个层次化
31、的路由表（邻居表），每一层代表与自身nodeID匹配一定位数后缀的结点n路由的第n跳所到达的结点通常与目的结点ID至少匹配n位后缀，为找到下一跳结点，需要在当前结点的路由表的第n+1层中，查找与目的结点ID匹配更多位后缀的结点，若找不到，则意味着定位即将完成53宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络结点0642的状态信息，包括其对象索引、热点数据管理器、对象存储空间、路由表54宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络Tapestry路由示例，结点0325要发送一条消息给结点4598，粗线标明了路由的每一跳55宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTap
32、estry的路由表项有logBN层，每层B项nTapestry的路由机制可以保证在N个结点的网络中，任何一次定位一般都能在logBN跳之内完成，其中B为ID编码的进制（ base，也称“基”）56宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTapestry结点S向网络插入数据对象O时，要将其索引放到O的根结点上，为此，S向邻居发送一条以objectID为目的地的消息，其中包含有对象索引信息如，该消息逐步匹配对象ID直到没有更多匹配位，此时即找到根结点，消息路径上的所有结点都保存O的索引信息57宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTapestry结点查询数据对象O时，
33、也发送一条以objectID为目的地的定位消息，按后缀匹配方法逐步路由，若中间结点保存了索引，则定位结束，否则必将到达O的根结点（根结点可确保对象定位成功，也称为对象的“代理”结点）n由于一个Tapestry结点可能保存O的多个副本的索引，查询时可从中找出自己认为最近、最合适的来获取数据，即Tapestry可以自动帮助用户获取最邻近副本58宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络二、Tapestry动态结点算法n利用反向指针和心跳消息保持路由表的更新和定位的容错性q反向指针：back pointer，指向那些把自己作为路由表项的结点（反向结点）q周期性发送Heartbeat消息至反
34、向结点，确认存在n结点发现路由表某项失败后并不立即替换它，而是过一段时间再检测一次它是否在线，如果还不在才替换，称为“二次机会”，防止“闪断”n路由表中每项保存一个“主项”和两个“次要项”，以提高可用性59宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n新结点加入：初始化自己的路由表、更新相关结点的路由表、从相关结点移交对象索引nJOIN STEP1：初始化路由表q新结点N联系到一个现存结点G，通过G发送以N为目的地的消息q假设第i步路由到达结点Hi，根据后缀匹配路由算法，N和Hi应该共享长度i的后缀，则N从Hi那里获得路由表的第i+1层项是合适的qN对复制来的项进行优化，将更好的次要项
35、结点改为主项，再查找新主项结点的路由表，比较N到每项的距离，迭代优化至收敛60宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nJOIN STEP2：更新其它结点路由表qN通过G发送往N自己的消息，在logN跳之内到达N的根结点RqR首先计算它和N匹配的后缀位数p，然后通过自己路由表中的“反向指针”，告诉那些与R也匹配p位后缀的反向结点：如果N对它们是合适的，那么它们在自己的路由表中添加N或者用N替换原来的项61宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nJOIN STEP3：对象索引移交q最初的设计：当N发送给自己的消息到达根结点R时，认为R正是需要移交对象索引给N的结点q由于
36、Tapestry没有严格的结构和必须维持的不变属性，仅让根结点R移交索引给N是不够的q后来的设计：将对象索引移交放在STEP2中完成，对于R所通知的反向结点，不仅用N更新自己的路由表，还将自己的对象索引中应由N负责的那部分移交给N（维护拓扑结构）62宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n结点N的离开q正常离开：N告诉自己的反向结点在路由表中去掉N，同时将自己负责的对象索引分别移交给它们的新根结点q异常离开：周期性检测并确认N失效后，通过与结点加入过程中类似的多播方法更新路由表；对于对象索引，采用“软状态重发布”的方法：所谓“软状态”指对象索引都是暂时性的，“重发布”指让数据对象
37、的拥有者定期重新发布自己的对象索引信息，即为数据对象更新根结点63宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络三、Tapestry体系架构64宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTransport Protocols：封装了网络传输层，相当于覆盖网与物理网的中间层，典型地可以使用TCP或者UDP协议nNeighbor Link Management：邻居链接管理向上层提供安全但不可靠的数据报服务，如长消息的分片和组合；负责持续的邻居链接管理和更新，如周期性的邻居结点失效检测、时延估计等，当检测到状态变化时通知上层来处理nRouter：管理Tapestry结点路由表和对
38、象指针数据库，检查所收到的消息的目的地，决定路由的下一跳；在新结点加入、旧结点离开时更新对象索引信息65宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nApplication Interface/Upcall API：Tapestry提供给其高层应用的接口n分布式文件系统/应用层多播/协同文本过滤：基于Tapestry的各种上层应用，不限于这三种66宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络四、Tapestry总结n是一个面向广域分布式数据存取、容错的超立方体结构P2P模型，在构建网络时考虑了拓扑一致性；其最具特色的功能在于帮助用户寻找最邻近的数据副本nTapestry中每个结
39、点、数据对象、消息（应用）都有一个全局唯一的ID，每个数据对象有一个根结点，它是网络中nodeID与objectID最匹配的结点n每个Tapestry结点维护一个路由表，其中第i层第j项表示与当前nodeID后缀匹配位数为i-1位并且以j开头的结点，由此实现效率为O(logN)跳的后缀匹配路由67宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nTapestry路由表还维护“反向指针”项，很多重要操作如结点加入、离开、失效检测和修复都用到它nTapestry体系架构分为5层，分层有助于高层应用的开发和各层的优化完善68宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络五、OceanSto
40、re简介n基于Tapestry的分布式数据存取系统，其目标是提供全球范围的广域、持久性数据存取服务n任何一台计算机都可以加入到OceanStore系统，贡献自己的存储空间，同时获得他人存储的内容nOceanStore对数据提供传统的复制、缓存功能，以提高存取速度和可用性nOceanStore建立在一个广域、动态、不可靠的网络基础上，因此对所有数据、元数据都提供了加密或者认证的功能nOceanStore采用“拜占庭式容错提交协议”保持副本间的强一致性69宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nOceanStore的数据持久性是通过基于版本的深度归档存储方案来实现的，并以“冗余编码”
41、的方式分片存储每个数据对象的每个版本，部分分片即可重构原文件nOceanStore通过“内省”机制提高存取性能和容错性nOceanStore的构想Kubiatowicz et al., 2000早于Tapestry，03年实现原型PondRhea et al, 2003，04年6月在SourceForge上发布源码70宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络六、OceanStore的命名机制和存取控制nOceanStore中数据对象是最基本的单元，类似于文件系统中的文件n数据对象以只读文件版本的方式按序保存在系统中，原则上每个对象的每个版本都是永久保存的，但通常只有最新版才有意义n
42、每个对象的每个版本包含着该版本数据和元数据（如目录）以及指向其前一个版本的指针，每个版本有自己的标识VGUIDi，对象的所有版本通过“反向指针”（与Tapestry中的不同）连成一个流，这串序列合起来有一个表示AGUID（Active GUID），唯一标识一个有效的数据对象71宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络72宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n每个数据对象版本由许多块组成，每块有自己的标识BGUID（Block GUID），这些块自顶向下组织成一棵类似B树的结构q树根为root block，保存该版本的元数据M和向下的指针，根块的BGUID通常被作为该
43、版本的VGUIDq中间块为indirect blocks，只保存向下的指针q树底层的叶子叫做data blocks，保存真正的数据n作为索引的根块和数据块里的指针，实际上是其子块的BGUID，版本间可以通过BGUID共享数据（图中copy on write）73宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络OceanStore有效对象AGUID的结构：由对象拥有者的公钥和可读对象名拼接起来的安全散列值可避免对象名冲突，且起到完整性检查的作用74宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络OceanStore的BGUID生成过程：由分片产生散列值，再逐层向上合并生成散列值n每个分片
44、除了存储分片数据，还需要存储它从底层到顶层所需的兄弟散列值（约logN个，N为分片数），以用于验证分片的数据完整性75宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n从对象的AGUID安全映射到其最新版本的VGUID的机制，两种方法：q每个数据对象在系统中对应一个“主环”（primary ring），由多台服务器组成，使用“拜占庭一致性协议”来维护映射，并将用户发出的对象更新操作序列化执行q若某个对象没有主环，则映射被存储在称为墓碑的结构里（图中）76宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络OceanStore墓碑结构Active对象主环的公钥和私钥密文对象最新的VGUID负
45、责方（responsible party）的公钥和私钥密文77宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nOceanStore对系统中数据对象提供两种原始类型的“存取控制”：读者限制和写者限制n读者限制：为阻止不合法的读者，OceanStore中所有非完全公开的数据都被加密，密钥分发给那些允许读的用户。如果要撤销原来发出的读允许，对象拥有者要么删除数据对象，要么用新密钥加密原对象n写者限制：要求所有的写操作都必须签名，行为良好的服务器和客户可以通过存取控制链（ACL,access control list）来验证写操作。对象的存取控制链是由对象拥有者所签名的、授予特定用户对该对象的操
46、作特权78宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络七、OceanStore的路由和定位算法n全局查询qTapestry的后缀匹配路由算法，速度较慢，但保证成功n概率查询q快速定位局部性的临近数据对象，速度快，但不保证成功q为网络中每条有向边保存一个Attenuated Bloom Filters数据结构，以表示沿该边可以定位到的对象信息，查询消息在Bloom filter的指导下沿着有向边路由79宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络nBloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloo
47、m Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。n请自学请自学Bloom Filter的工作原理的工作原理80宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络概率查询示例：n1查找对象XBloom Filtern1的有向边Filter显示n2可能是一个路由到X的中间结点81宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络八
48、、OceanStore的更新模型n任何一个数据对象都有一个“主副本环”（primary replica，也称主环或者内环），是数据对象归档存储、更新、最新版本获得的核心设施n用户更新对象时，首先发出更新请求，通过Tapestry底层网络将请求发到对象主环，主环服务器之间序列化所收到的更新请求并执行；然后，主环服务器将新数据对象深度归档存储（提供数据持久性），并通过“分发树”（dissemination tree）将更新分发到对象的“次级副本”服务器以更新缓存（加快数据定位与获取速度）82宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络83宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络
49、九、OceanStore的深度归档存储n使用“冗余编码”（erasure code）将数据对象分片冗余地存储在网络的多个结点中，只要获得一部分分片就可以重构原文件n冗余编码：一种提高数据可用性的数学编码方法。假设编码前数据被分成互相独立的n片，冗余编码将这n片转换成更多相关的分片，如kn片，1/k称为冗余编码率，这些冗余、相关的分片散布到网络中后，任何时刻只要用户能取得其中任意n片，即可重构原对象84宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n假设系统中共有n个结点，某个时刻有m个结点失效，f是对象的分片数，rf是最大容许的不可用分片数（指丢失掉的分片数不足以导致对象不能重构），则对
50、象可用的概率为n假定n取100万，m取10万，即10%的结点失效，简单复制方法提供的对象可用性是99%；而采用1/2的冗余编码，在消耗相同存储容量的前提下，对象可用性将达到99.9994%85宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络十、OceanStore的内省优化n优化目标q基于网络动态性，保持结点状态的自适应更新q基于网络异构性，利用复制、集群等方法开发结点能力n内省优化包括三个循环的操作q观察：observation，监控系统活动并记录活动信息q优化：optimization，利用观察的信息调整计算q计算：computation，完成通信、数据交换、本地计算等实际的系统工作n
51、数据对象的集群识别与流动副本管理86宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络OceanStore总结nOceanStore是一个基于Tapestry的分布式数据存取系统，其目标是提供全球范围的广域、持久性数据存取服务n数据对象以只读文件版本的方式保存，使用AGUID标识可用对象，VGUID标识对象的各个版本，BGUID标识数据块，这些ID之间以类似B树的方式组织nOceanStore采用两种路由和定位算法：概率查询，局部，快速，但不保证成功；全局查询，后缀路由匹配，速度慢，保证成功n任何一个数据对象都对应一个主副本环，是数据对象归档存储、更新、最新版本获得的核心设施87宽带媒体服务技术之对等网络宽带媒体服务技术之对等网络n用户更新对象时，数据一方面被深度归档存储，一方面被分发到对象的次级副本服务器以更新缓存nOceanStore建立在广域、动态、不可靠的网络基础上，系统中每个结点都不可靠，因此对所有数据提供加密或认证n使用拜占庭式容错提交协议保持副本间的强一致性n深度归档存储方案中，数据以冗余编码的方式分片冗余地存储在网络的多个服务器中，仅利用部分分片即可重构原文件，数据是高可用、高持久性的n通过内省机制提高存取性能和自适应性88
