宽带媒体服务技术之对等网络

第四章第三代P2P网络

——结构化P2P体系Chord、CAN、Tapestry、Pastry章节内容Chord与CFS：简单、精确的环形P2P网络CAN：简单、容错的多维空间P2P网络Tapestry与OceanStore：广域的超立方体结构P2P网络Pastry与PAST：容错的混合式结构P2P网络其它结构化P2P网络：Kademlia、SkipNet等常数度P2P模型：Viceroy、Koorde和Cycloid结构化P2P网络的特点与分析概述2001年，学术界P2P历史上的里程碑IEEE成立P2P专业会议、ACM会议专题等提出结构化P2P的几个经典模型与应用体系，如Chord、CAN、Tapestry、Pastry著名学术团体与技术组织成立专门的P2P研究组，如MIT、UCBerkeley、Microsoft、Stanford4.1Chord与CFS：简单、精确的环形P2P网络Chord作为一个P2P网络，是基于带弦环拓扑结构的分布式系统，提供对象的存储、查询、复制、缓存，在其上可以架构更高层的分布式数据存储系统如协同文件系统CFSChord作为一个分布式散列表，只支持结构化P2P最简单的功能：将结点和数据对象映射到覆盖网中，但具有几乎最优的路由效率、确定性的对象查询、负载均衡、高可靠性以及良好的容错性与自适应，最主要的是：简单、优美Chord的技术特点基于安全的一致性散列函数来分配结点ID和对象ID在一个有N个结点的网络中，每个Chord结点保存O(logN)个其他结点的信息查询数据对象需要的覆盖网路由跳数也为O(logN)当结点加入或者离开网络时，为了维持网络结构、保持自适应性所需要的消息数在O(log2N)一、Chord基础工作原理Chord使用安全散列函数（如SHA-1）为每个网络结点和数据对象分配唯一的IDnodeID=H(node属性)，属性可以是结点IP、port、公钥、随机数或它们的组合objectID=H(object属性)，属性可以是数据对象的名称、内容、大小、发布者或者它们的组合H是散列函数，SHA系列散列函数的Hash值长度≥160，保证ID的唯一性Chord按照如下方法将数据对象（只是其索引）分配到网络结点中所有的结点按照nodeID从小到大顺时针排列在一个环上数据对象k（ObjectID）被分配到环上顺时针方向紧随k（包括与k相等）的第一个结点，该结点称为对象k的后继，记做successor(k)Chord结点n的后继是环上紧随n（不等于n）的第一个结点，记做n.successor一个简单的Chord环（m=3）当Chord中有新结点n加入时，为保持正确、一致的对象放置，原本由n的后继结点负责的对象，其中一部分必须分配给n当Chord中有旧结点n离开时，原本由n负责的所有对象，必须分配给n的后继。除此以外，对象不需要再做移动，这正是一致性散列函数所追求的性质（问题：异常退出？）例：图中新加入结点7单纯纯的的环环可可以以工工作作，，但但效效率率太太低低为此此，，结结点点维维护护一一个个有有m（（ID位位数数））项项的的路路由由表表，，也也称称““指指向向表表””（（fingertable）），，其其中中第第i项项指指向向结结点点s，，s=successor(n+2i-1)，，1≤i≤m，，即即s是是在在顺顺时时针针方方向向到到n的的距距离离至至少少为为2i-1的第第一一个个结结点点，，记记做做n.finger[i].nodeChord路路由由表表的的特特点点：：每个个结结点点只只保保存存很很少少的的其其它它结结点点信信息息，，并并且且对对离离它它越越远远的的结结点点所所知知越越少少Chord结结点点不不能能从从自自己己的的路路由由表表中中看看出出对对象象k的的后后继继为确确定定对对象象k的的后后继继（（k所所在在的的结结点点））,结结点点n在在自自己己的的路路由由表表中中查查找找在在k之之前前且且离离k最最近近的的结结点点j，，让让j去去找找离离k最最近近的的结结点点，，递递归归查查找找，，最最终终可可以以找找到到对对象象k的的前前驱驱（（在在k之之前前离离k最最近近的的结结点点，，记记做做predecessor(k)，，类类似似，，结结点点n的的前前驱驱记记做做n.predecessor））前驱驱中中必必然然有有后后继继的的路路由由表表项项，，定定位位成成功功Chord结结点点n的的路路由由表表各各项项属属性性及及其其定定义义属性定义finger[k].start(n+2k-1)mod2m,1≤k≤erval[finger[k].start,finger[k+1].start).node≥n.finger[k].start的第一个结点successor后继结点，即finger[1].nodepredecessor前驱结点二、、Chord对对象象定定位位算算法法定位位算算法法的的三三个个函函数数的的伪伪代代码码//请请求求结结点点n寻寻找找id的的后后继继n.find_successor(id)n’’=find_predecessor(id);returnn’’.successor;//请请求求结结点点n寻寻找找id的的前前驱驱n.find_predecessor(id)n’’=n;while(id(n’’,n’’.sucessor])n’’=n’’,closest_preceding_finger(id);returnn’’;//返返回回id之之前前最最近近的的fingern.closest_preceding_finger(id)fori=mdownto1if(finger[i].node∈(n,id))returnfinger[i].node;returnn;该函函数数是是在在定定位位过过程程中中真真正正被被多多次次调调用用执执行行的的过过程程，，其其作作用用是是：：结结点点在在自自己己的的路路由由表表中中，，从从后后往往前前找找到到在在id前前且且与与id最最近近的的结结点点并并返返回回由Chord路路由由表表的的构构造造和和定定位位算算法法可可知知：：每每次次调调用用第第三三个个函函数数，，新新找找到到的的结结点点离离对对象象id的的距距离离通通常常比比原原来来少少一一半半，，因因此此一一般般最最多多调调用用logN次次即即可可定定位位成成功功Chord路路由由表表的的简简单单示示例例假设设结结点点3要要找找到到对对象象1的的后后继继在结结点点3的的路路由由表表中中，，1属属于于3.finger[3].interval即即[7,3)结点点3让让3.finger[3].node即即结结点点0去去找找1结点点0在在路路由由表表中中发发现现自自己己的的后后继继1恰恰好好是是对对象象1的的后后继继，，因因此此将将1返返回回给给结结点点3结点点3由由此此知知道道对对象象1放放在在结结点点1中中三、、Chord结结点点加加入入算算法法Chord的的自自适适应应需需要要保保持持两两个个不不变变的的属属性性每个个结结点点的的后后继继始始终终正正确确对每每个个对对象象k，，结结点点successor(k)始始终终负负责责k的的索索引引为此此，，新新结结点点n的的加加入入需需要要完完成成三三个个任任务务初始始化化n的的前前驱驱和和路路由由表表项项更新新网网络络其其他他结结点点的的前前驱驱和和路路由由表表项项告诉诉其其后后继继将将应应该该由由n负负责责的的数数据据对对象象索索引引传传递递给给n新结结点点n连连接接到到某某个个众众所所周周知知结结点点n’’，，通通过过调调用用join(n’’)初初始始化化自自己己的的状状态态信信息息，，并并将将自自己己加加入入到到Chord网网络络通过过结结点点n’’初初始始化化n的的路路由由表表：：请请求求n’’帮帮自自己己查查找找后后继继，，从而而更更新新自自己己的的前前驱驱，，再再通通过过多多次次调调用用n’’的的后后继继查查找找函数数来来初初始始化化自自己己的的路路由由表表初始始化化本本地地结结点点的的路路由由表表update_others()函函数数更更新新其其他他结结点点的的状状态态信信息息以以反反映映n的的加加入入，，当当且且仅仅当当满满足足下下面面两两个个条条件件时时，，结结点点n将将成成为为结结点点p路路由由表表的的第第i项项：：结点点p在在n之之前前至至少少2i-1结点点p路路由由表表的的当当前前第第i项项结结点点在在n之之后后满足足这这两两个个条条件件的的第第一一个个结结点点p是是结结点点(n-2i-1)的的前前驱驱，，因因此此，，update_others()首首先先找找到到该该前前驱驱，，然然后后调调用用函函数数update_finger_table(n,i)，，递递归归地地更更新新Chord网网中中所所有有需需要要更更新新路路由由表表第第i项项的的结结点点信信息息通常常情情况况下下，，一一个个新新结结点点加加入入Chord网网，，需需要要更更新新信信息息的的结结点点数数为为O(logN)，，因因此此寻寻找找和和更更新新的的时时间间复复杂杂度度为为O(log2N)相关关伪伪代代码码四、、Chord自自适适应应算算法法以上上算算法法完完备备、、细细致致，，但但有有未未解解决决的的问问题题：：并并发发操操作作；；不不正正常常操操作作（（如如结结点点异异常常退退出出））解决决方方法法：：简化化join函函数数，，仅仅通通过过n’’寻寻找找n的的后后继继，，其其它它什什么么也也不不做做每个个Chord结结点点周周期期性性调调用用稳稳定定函函数数stabilize和和路路由由表表更更新新函函数数fix_fingers，，前前者者修修正正结结点点后后继继并并通通知知其其后后继继修修正正前前驱驱，，后后者者在在此此基基础础上上随随机机修修正正自自己己的的路路由由表表项项通过过合合适适的的周周期期保保持持定定位位高高效效率率五、、Chord容容错错性性和和复复制制、、缓缓存存Chord中中正正确确的的后后继继关关系系是是一一切切工工作作的的基基础础无论机制如如何完善，，网络的动动态性和不不确定性都都可以导致致单后继失失效因此，实际际的Chord给每每个结点维维护一个后后继列表，，其中保存存了该结点点在Chord环上上的r个后后继，典型型地取r=O(logN)，，即使结点点失效概率率为1/2，仍能正正确定位将结点保存存的数据对对象复制到到所有后继继中，可提提高数据的的可用性、、持久性在Chord定位过过程中，如如每个中间间结点缓存存数据对象象，可以提提高获取数数据的速度度六、Chord实验验分析负载均衡负载均衡是是使用一致致性散列函函数的结构构化P2P网络的共共同属性对于Chord而言言，由于数数据对象被被分配到其其后继中，，而数据对对象、结点点的ID都都是随机、、均匀产生生的，因此此每个结点点所负担的的数据对象象也应该大大致均衡此外，Chord还还采用了““虚拟服务务器”的方方法，在一一台计算机机上运行多多个Chord结点点，可以使使得结点各各尽所能1万个结点点，50万万个数据对对象定位路径长长度理论量级为为O(logN)跳跳实验中网络络结点数取取N=2k，数据对象象数取100×2k，k从3取取到14测量结果：：路径长度度平均约logN/2，是logN的的一半，原原因是Chord路路由表的指指数构造，，使其每次次查找都能能将目的ID与当前前结点ID之间的差差距减小至至少一半，，可推导出出平均路径径长度正好好是logN的一半半网络结点数数为212七、Chord总结结Chord采用带弦弦环拓扑结结构，通过过一致性散散列函数将将结点、数数据对象映映射到覆盖盖网上，数数据对象（（索引）由由其后继结结点负责，，简单、精精确正是Chord最大的特特点每个Chord结点点维护一个个很小的路路由表，后后继关系是是Chord定位的的基础，路路由表可以以将定位路路径长度缩缩短为O(logN)跳Chord需要保持持两个不变变的属性才才能正确工工作：后继继正确、后后继对对象象的索引正正确Chord采用周期期性的稳定定算法和路路由表更新新算法检查查和修正后后继关系及及路由表项项为保持高容容错性，Chord采用后继继列表避免免单后继失失效，此时时可以对数数据对象进进行复制和和缓存，提提高网络效效率八、CFS（Cooperativefilesystem）CFS协同同文件系统统是以Chord为为基础的P2P协同同只读文件件存储系统统，文件分分块存储CFS由三三层构件组组成Chord，底层定定位散列表表：维护路路由表，定定位数据块块所在的服服务器DHash，分布式式数据块散散列表：中中间层，分分布和缓存存数据块以以平衡负载载，复制数数据块以容容错，并通通过服务器器选择来减减少时延；；使用Chord定定位数据块块FS，FileSystem，文件件系统：高高层，从DHash层获得数数据块并转转换为文件件，给更高高的应用提提供文件系系统接口CFS文件件系统类似似UNIX文件目录录结构，只只是以根块块代替根目目录、以元元数据块代代替子目录录、以数据据块代替文文件，而以以块标识代代替文件地地址CFS对Chord的改进：：采用前驱驱列表定位位以提高定定位容错性性，使用服服务器选择择减少定位位时延，对对结点ID认证以防防止ID伪伪造和IP虚报CFS对数数据块采用用后继复制制以提高数数据可用性性，同时减减少了客户户获取数据据的时延；；采用路径径缓存提高高系统工作作效率，同同时避免热热点数据的的后继结点点负载过重重；采用““虚拟结点点”和“限限额”方法法提供负载载均衡4.2CAN：简简单、容错错的多维空空间P2P网络ContentAddressableNetwork，内内容可寻址址网络，采采用多维Torus环面拓扑扑结构，典典型采用的的二维空间间网格，类类似于笛卡卡尔平面，，其结点编编址方式也也类似于点点的编址01年[Ratnasamyetal.]在ACMSIGCOMM会议发表表正式论文文（与Chord同同年同会））CAN的多多维空间被被动态地分分配给其网网络结点，，每个结点点占有一个个属于自己己的方块并并负责该方方块中所有有的“点””（数据对对象索引））每个结点维维护一个路路由表，记记录多维空空间上的邻邻居信息，，如图中结结点D可以以记录B、、C、E的的ID和地地址CAN采用用逐步定位位，每一步步挑选当前前结点路由由表中离目目的结点最最“近”的的邻居作为为下一跳对一个d维维CAN来来说，若维维护一个有有2d项的的路由表，，其定位效效率为，，取取d=logN，即即为O(logN)，其定位位效率与其其它结构化化P2P网网络一致以2维CAN为例，，新结点加加入时，被被映射到一一个点，其其所在的方方块将一分分为二，一一半分给新新结点负责责，一半留留给原来负负责的结点点；当旧结结点离开CAN时，，某个邻居居必须接管管它原来负负责的区域域，相当于于方块合并并CAN的容容错性体现现在路由选选择的灵活活性上，由由于其多维维空间的拓拓扑结构，，CAN不不需要维护护一些严格格的不变属属性，每个个邻居对结结点来说都都是同等地地位的；在在CAN中中任意两个个点间存在在多条路径径，即使很很多邻居失失效，仍能能以较快的的速度定位位目的结点点目前还没有有基于CAN的应用用系统一、CAN网络构建建结点加入步步骤：自举举、寻找区区域、加入入路由表JOINSTEP1：自举举（bootstrap）新结点通过过CAN的的DNS域域名获得一一个众所周周知结点（（自举结点点、入口结结点），后后者提供一一个列表，，其中包含含一些CAN现存结结点的信息息JOINSTEP2：寻找找区域新结点n随随机选择CAN空间间中的一个个点P并向向P发送一一个加入请请求消息，，该消息可可通过列表表中任意一一个现存结结点发送到到CAN网网络中，并并被逐步路路由到P所所在的区域域，最终到到达负责P所在区域域的结点n’，n’’按某种规规则将负责责区域分一一半给n负负责JOINSTEP3：加入入路由表获得自己的的区域后，，n从n’’获得其邻邻居的IP地址等信信息，并通通知每个邻邻居更新其其路由表以以反映n的的存在CAN也采采用了自适适应的周期期性方法，，每个结点点定期向邻邻居发送自自己所负责责的区域和和自己的路路由表信息息，当发现现不一致时时更新由于结点插插入、离开开或周期性性更新时只只需要通知知邻居结点点，而每个个结点的路路由表记录录O(d)个邻居，，因此其自自适应开销销是O(d)的，通通常比Chord和和大多数P2P系统统小得多简单的CAN结点加加入示例当结点离开开CAN时时，通常应应显式地将将其区域及及所负责数数据交给一一个邻居，，如果该邻邻居可以合合并一个规规整的单区区域，则完完成合并，，否则，离离开结点只只能将其区区域交给占占有最小区区域的邻居居，由其暂暂时负责两两块区域，，但并不合合并当结点n失失效时，依依靠周期性性检测由邻邻居结点接接管其区域域，解决冲冲突的方法法：每个邻邻居做完接接管工作以以后，向n的其它邻邻居发送TAKEOVER消消息，其中中包括消息息源的区域域信息，收收到该消息息的结点比比较消息源源的区域和和自己的区区域，如果果前者大，，则回发TAKEOVER消消息表明自自己接管更更合适，否否则取消接接管工作问题：随着着结点不断断加入、离离开，CAN网络的的区域划分分将变得支支离破碎，，而且由一一个结点负负责多个结结点的情况况将越来越越多，直到到负载超过过结点能力力上限CAN采用用“背景区区域重分配配”（backgroundzonereassignment）方方法合并支支离破碎的的区域，并并尽量让一一个结点只只负责一块块区域，详详见论文[Ratnasamyetal.,2001]二、CAN增强机制制：多维、、多空间、、多散列多维：d接接近logN，路由由效率高，，容错性强强多空间：使使用多个不不同的CAN空间，，每个空间间称为一个个“现实””（reality）；一个个真实的网网络结点在在每个CAN空间中中都会被分分配一块区区域，同一一个数据对对象的在每每个空间中中都会被分分配给一个个结点，从从而起到复复制作用，，提高数据据可用性；；定位时，，结点可以以比较多个个空间的邻邻居，效率率更高多散列：单单空间可以以使用多散散列，效果果类似多空空间三、CAN的“区域域超载”区域超载：：将一个区区域分给多多个结点负负责一个结点除除了维护原原来的路由由表，还需需要维护一一个“区域域超载列表表”，保存存和自己共共同负责同同一区域的的结点信息息新结点A加加入时，如如果它所映映射到的点点原先由结结点B负责责，B首先先检查该区区域的结点点数是否超超过上限，，如未超过过则不分割割区域，而而是将该区区域也给A负责，同同时A从B那里获得得“区域超超载列表””；若超过过上限，则则进行分割割区域超载的的好处减少定位跳跳数：让多多个结点负负责同一区区域等效于于减少系统统结点数减少每跳时时延：在选选择下一跳跳时，由于于邻居区域域由多个结结点负责，，可以从这这多个结点点中选出时时延最短的的作为下一一跳提高容错性性和可用性性：一个区区域只有在在负责它的的所有结点点都失效时时才不可达达，且该区区域的数据据相当于被被复制到多多个结点中中CAN中的的复制与缓缓存三种隐式复复制：多空空间、多散散列、区域域超载对热点数据据，CAN采用显式式复制到邻邻居区域在定位路径径上放置热热点数据的的缓存副本本四、CAN总结CAN采用用多维空间间拓扑结构构，简单、、直观，CAN空间间被动态分分配给其网网络结点，，每个结点点负责一块块，每个数数据对象被被映射到一一个点，由由负责该点点所在区域域的结点保保持索引每个CAN结点维护护一个路由由表，记录录它在多维维空间上的的邻居信息息，d维CAN的定定位效率为为CAN的高高容错性体体现在其路路由选择的的灵活性上上：即任意意两个结点点间存在多多条路径，，部分邻居居信息的失失效对定位位效率影响响很小新结点加入入CAN分分三步：自自举、寻找找区域、加加入路由表表，从其加加入区域中中划分一半半进行接管管，采用““背景区域域重分配””方法调整整区域CAN采用用多种增强强机制提高高系统性能能，包括多多维度、多多空间、多多散列、区区域超载技技术综上所述，，CAN简简单、容错错性好，可可扩展，高高效率4.3Tapestry与与OceanStore：广广域的超立立方体结构构P2P网网络严格讲，是是基于PlaxtonMesh[1997]的网格形形结构，Pastry也基于于此特点：构建建覆盖网时时考虑了拓拓扑一致性性问题00年3月月UCBerkeley的的BenY.Zhao等等成立Tapestry研究究组，03年6月发发布2.0版应用广泛，，著名的OceanStore广域存存储系统Tapestry的的应用Bayeux提供高效、容错的应用层多播Brocade提供界标路由（LandmarkRouting）Cashmere提供匿名路由Fault-TolerantOverlayRouting基于Tapestry开发路由的冗余性，从而提供容错的覆盖网路由OceanStore提供全球范围内广域的、持久性数据存取服务SpamWatch基于Tapestry，使用基于内容相似度的搜索引擎，提供分布式的Spam-FilteringWarp通过类型重定向提供快速移动服务架构一、Tapestry路由和和定位每个结点有有nodeID，数数据对象有有objectID，也称为为GUID（globallyuniqueID）），每条消消息有其特特定应用的的AID（（applicationID），，类似于TCP协议议中的端口口号Tapestry为为每个数据据对象分配配一个负责责结点，称称为该对象象的根（root）），root(objectID)=最接近objectID的的nodeIDTapestry中中也采用了了多散列以以提高对象象可用性与与持久性Tapestry采采用逐位匹匹配的后缀缀路由，每每一跳匹配配更多的后后缀，如xxx8->xx98->x598->4598为适应这种种路由，每每个Tapestry结点维维护一个层层次化的路路由表（邻邻居表），，每一层代代表与自身身nodeID匹配配一定位数数后缀的结结点路由的第n跳所到达达的结点通通常与目的的结点ID至少匹配配n位后缀缀，为找到到下一跳结结点，需要要在当前结结点的路由由表的第n+1层中中，查找与与目的结点点ID匹配配更多位后后缀的结点点，若找不不到，则意意味着定位位即将完成成结点0642的状态态信息，包包括其对象象索引、热热点数据管管理器、对对象存储空空间、路由由表Tapestry路路由示例，，结点0325要发发送一条消消息给结点点4598，粗线标标明了路由由的每一跳跳Tapestry的的路由表项项有logBN层，每层层B项Tapestry的的路由机制制可以保证证在N个结结点的网络络中，任何何一次定位位一般都能能在logBN跳之内完完成，其中中B为ID编码的进进制（base，，也称“基基”）Tapestry结结点S向网网络插入数数据对象O时，要将将其索引放放到O的根根结点上，，为此，S向邻居发发送一条以以objectID为目的地地的消息，，其中包含含有对象索索引信息如如<objectID(O)，serverID(s)>，该消消息逐步匹匹配对象ID直到没没有更多匹匹配位，此此时即找到到根结点，，消息路径径上的所有有结点都保保存O的索索引信息Tapestry结结点查询数数据对象O时，也发发送一条以以objectID为目的地地的定位消消息，按后后缀匹配方方法逐步路路由，若中中间结点保保存了索引引，则定位位结束，否否则必将到到达O的根根结点（根根结点可确确保对象定定位成功，，也称为对对象的“代代理”结点点）由于一个Tapestry结结点可能保保存O的多多个副本的的索引，查查询时可从从中找出自自己认为最最近、最合合适的来获获取数据，，即Tapestry可以自自动帮助用用户获取最最邻近副本本二、Tapestry动态结结点算法利用反向指指针和心跳跳消息保持持路由表的的更新和定定位的容错错性反向指针：：backpointer，指向那那些把自己己作为路由由表项的结结点（反向向结点）周期性发送送Heartbeat消息至至反向结点点，确认存存在结点发现路路由表某项项失败后并并不立即替替换它，而而是过一段段时间再检检测一次它它是否在线线，如果还还不在才替替换，称为为“二次机机会”，防防止“闪断断”路由表中每每项保存一一个“主项项”和两个个“次要项项”，以提提高可用性性新结点加入入：初始化化自己的路路由表、更更新相关结结点的路由由表、从相相关结点移移交对象索索引JOINSTEP1：初始始化路由表表新结点N联联系到一个个现存结点点G，通过过G发送以以N为目的的地的消息息假设第i步步路由到达达结点Hi，根据后后缀匹配路路由算法，，N和Hi应该共享享长度i的的后缀，则则N从Hi那里获得得路由表的的第i+1层项是合合适的N对复制来来的项进行行优化，将将更好的次次要项结点点改为主项项，再查找找新主项结结点的路由由表，比较较N到每项项的距离，，迭代优化化至收敛JOINSTEP2：：更新其它结结点路由表N通过G发送送往N自己的的消息，在logN跳之之内到达N的的根结点RR首先计算它它和N匹配的的后缀位数p，然后通过过自己路由表表中的“反向向指针”，告告诉那些与R也匹配p位位后缀的反向向结点：如果果N对它们是是合适的，那那么它们在自自己的路由表表中添加N或或者用N替换换原来的项JOINSTEP3：：对象索引移移交最初的设计：：当N发送给给自己的消息息到达根结点点R时，认为为R正是需要要移交对象索索引给N的结结点由于Tapestry没没有严格的结结构和必须维维持的不变属属性，仅让根根结点R移交交索引给N是是不够的后来的设计：：将对象索引引移交放在STEP2中中完成，对于于R所通知的的反向结点，，不仅用N更更新自己的路路由表，还将将自己的对象象索引中应由由N负责的那那部分移交给给N（维护拓拓扑结构）结点N的离开开正常离开：N告诉自己的的反向结点在在路由表中去去掉N，同时时将自己负责责的对象索引引分别移交给给它们的新根根结点异常离开：周周期性检测并并确认N失效效后，通过与与结点加入过过程中类似的的多播方法更更新路由表；；对于对象索索引，采用““软状态重发发布”的方法法：所谓“软软状态”指对对象索引都是是暂时性的，，“重发布””指让数据对对象的拥有者者定期重新发发布自己的对对象索引信息息，即为数据据对象更新根根结点三、Tapestry体体系架构TransportProtocols：封封装了网络传传输层，相当当于覆盖网与与物理网的中中间层，典型型地可以使用用TCP或者者UDP协议议NeighborLinkManagement：邻邻居链接管理理向上层提供供安全但不可可靠的数据报报服务，如长长消息的分片片和组合；负负责持续的邻邻居链接管理理和更新，如如周期性的邻邻居结点失效效检测、时延延估计等，当当检测到状态态变化时通知知上层来处理理Router：管理Tapestry结点路由由表和对象指指针数据库，，检查所收到到的消息的目目的地，决定定路由的下一一跳；在新结结点加入、旧旧结点离开时时更新对象索索引信息ApplicationInterface/UpcallAPI：Tapestry提供给其高高层应用的接接口分布式文件系系统/应用层层多播/协同同文本过滤：：基于Tapestry的各种上层层应用，不限限于这三种四、Tapestry总总结是一个面向广广域分布式数数据存取、容容错的超立方方体结构P2P模型，在在构建网络时时考虑了拓扑扑一致性；其其最具特色的的功能在于帮帮助用户寻找找最邻近的数数据副本Tapestry中每个个结点、数据据对象、消息息（应用）都都有一个全局局唯一的ID，每个数据据对象有一个个根结点，它它是网络中nodeID与objectID最最匹配的结点点每个Tapestry结结点维护一个个路由表，其其中第i层第第j项表示与与当前nodeID后缀缀匹配位数为为i-1位并并且以j开头头的结点，由由此实现效率率为O(logN)跳的的后缀匹配路路由Tapestry路由表表还维护“反反向指针”项项，很多重要要操作如结点点加入、离开开、失效检测测和修复都用用到它Tapestry体系架架构分为5层层，分层有助助于高层应用用的开发和各各层的优化完完善五、OceanStore简介基于Tapestry的的分布式数据据存取系统，，其目标是提提供全球范围围的广域、持持久性数据存存取服务任何一台计算算机都可以加加入到OceanStore系统，，贡献自己的的存储空间，，同时获得他他人存储的内内容OceanStore对对数据提供传传统的复制、、缓存功能，，以提高存取取速度和可用用性OceanStore建建立在一个广广域、动态、、不可靠的网网络基础上，，因此对所有有数据、元数数据都提供了了加密或者认认证的功能OceanStore采采用“拜占庭庭式容错提交交协议”保持持副本间的强强一致性OceanStore的的数据持久性性是通过基于于版本的深度度归档存储方方案来实现的的，并以“冗冗余编码”的的方式分片存存储每个数据据对象的每个个版本，部分分分片即可重重构原文件OceanStore通通过“内省””机制提高存存取性能和容容错性OceanStore的的构想[Kubiatowiczetal.,2000]早于于Tapestry，03年实现原原型Pond[Rheaetal,2003]，04年6月在在SourceForge上发布源六、OceanStore的命名机机制和存取控控制OceanStore中中数据对象是是最基本的单单元，类似于于文件系统中中的文件数据对象以只只读文件版本本的方式按序序保存在系统统中，原则上上每个对象的的每个版本都都是永久保存存的，但通常常只有最新版版才有意义每个对象的每每个版本包含含着该版本数数据和元数据据（如目录））以及指向其其前一个版本本的指针，每每个版本有自自己的标识VGUIDi，对象的所有有版本通过““反向指针””（与Tapestry中的不同））连成一个流流，这串序列列合起来有一一个表示AGUID（ActiveGUID），唯一标标识一个有效效的数据对象象每个数据对象象版本由许多多块组成，每每块有自己的的标识BGUID（BlockGUID），，这些块自顶顶向下组织成成一棵类似B树的结构树根为rootblock，保存存该版本的元元数据M和向向下的指针，，根块的BGUID通常常被作为该版版本的VGUID中间块为indirectblocks，只只保存向下的的指针树底层的叶子子叫做datablocks，保保存真正的数数据作为索引的根根块和数据块块里的指针，，实际上是其其子块的BGUID，版版本间可以通通过BGUID共享数据据（图中copyonwrite）OceanStore有有效对象AGUID的结结构：由对象象拥有者的公公钥和可读对对象名拼接起起来的安全散散列值可避免对象名名冲突，且起起到完整性检检查的作用OceanStore的的BGUID生成过程：：由分片产生生散列值，再再逐层向上合合并生成散列列值每个分片除了了存储分片数数据，还需要要存储它从底底层到顶层所所需的兄弟散散列值（约logN个，，N为分片数数），以用于于验证分片的的数据完整性性从对象的AGUID安全全映射到其最最新版本的VGUID的的机制，两种种方法：每个数据对象象在系统中对对应一个“主主环”（primaryring），由多台台服务器组成成，使用“拜拜占庭一致性性协议”来维维护映射，并并将用户发出出的对象更新新操作序列化化执行若某个对象没没有主环，则则映射被存储储在称为墓碑碑的结构里（（图中）OceanStore墓墓碑结构Active对象主环的公公钥和私钥密密文对象最新的VGUID负责方（responsibleparty）的公钥和和私钥密文OceanStore对对系统中数据据对象提供两两种原始类型型的“存取控控制”：读者者限制和写者者限制读者限制：为为阻止不合法法的读者，OceanStore中中所有非完全全公开的数据据都被加密，，密钥分发给给那些允许读读的用户。如如果要撤销原原来发出的读读允许，对象象拥有者要么么删除数据对对象，要么用用新密钥加密密原对象写者限制：要要求所有的写写操作都必须须签名，行为为良好的服务务器和客户可可以通过存取取控制链（ACL,accesscontrollist）来验验证写操作。。对象的存取取控制链是由由对象拥有者者所签名的、、授予特定用用户对该对象象的操作特权权七、OceanStore的路由和和定位算法全局查询Tapestry的后缀缀匹配路由算算法，速度较较慢，但保证证成功概率查询快速定位局部部性的临近数数据对象，速速度快，但不不保证成功为网络中每条条有向边保存存一个AttenuatedBloomFilters数据结构构，以表示沿沿该边可以定定位到的对象象信息，查询询消息在Bloomfilter的指导下沿沿着有向边路路由BloomFilter是一种空空间效率很高高的随机数据据结构，它利利用位数组很很简洁地表示示一个集合，，并能判断一一个元素是否否属于这个集集合。BloomFilter的的这种高效是是有一定代价价的：在判断断一个元素是是否属于某个个集合时，有有可能会把不不属于这个集集合的元素误误认为属于这这个集合（falsepositive）。。因此，BloomFilter不适合那些些“零错误””的应用场合合。而在能容容忍低错误率率的应用场合合下，BloomFilter通通过极少的错错误换取了存存储空间的极极大节省。请自学BloomFilter的的工作原理概率查询示例例：n1查找对象XBloomFiltern1的有向边Filter显显示n2可能是一个路由到到X的中间结结点八、OceanStore的更新模模型任何一个数据据对象都有一一个“主副本本环”（primaryreplica，也也称主环或者者内环），是是数据对象归归档存储、更更新、最新版版本获得的核核心设施用户更新对象象时，首先发发出更新请求求，通过Tapestry底层网络络将请求发到到对象主环，，主环服务器器之间序列化化所收到的更更新请求并执执行；然后，，主环服务器器将新数据对对象深度归档档存储（提供供数据持久性性），并通过过“分发树””（disseminationtree））将更新分发发到对象的““次级副本””服务器以更更新缓存（加加快数据定位位与获取速度度）九、OceanStore的深度归归档存储使用“冗余编编码”（erasurecode）将数据对对象分片冗余余地存储在网网络的多个结结点中，只要要获得一部分分分片就可以以重构原文件件冗余编码：一一种提高数据据可用性的数数学编码方法法。假设编码码前数据被分分成互相独立立的n片，冗冗余编码将这这n片转换成成更多相关的的分片，如kn片，1/k称为冗余余编码率，这这些冗余、相相关的分片散散布到网络中中后，任何时时刻只要用户户能取得其中中任意n片，，即可重构原原对象假设系统中共共有n个结点点，某个时刻刻有m个结点点失效，f是是对象的分片片数，rf是最大容许的的不可用分片片数（指丢失失掉的分片数数不足以导致致对象不能重重构），则对对象可用的概概率为假定n取100万，m取取10万，即即10%的结结点失效，简简单复制方法法提供的对象象可用性是99%；而采采用1/2的的冗余编码，，在消耗相同同存储容量的的前提下，对对象可用性将将达到99.9994%十、OceanStore的内省优优化优化目标基于网络动态态性，保持结结点状态的自自适应更新基于网络异构构性，利用复复制、集群等等方法开发结结点能力内省优优化包包括三三个循循环的的操作作观察：：observation，，监控控系统统活动动并记记录活活动信信息优化：：optimization，利利用观观察的的信息息调整整计算算计算：：computation，，完成成通信信、数数据交交换、、本地地计算算等实实际的的系统统工作作数据对对象的的集群群识别别与流流动副副本管管理OceanStore总总结OceanStore是是一个个基于于Tapestry的分分布式式数据据存取取系统统，其其目标标是提提供全全球范范围的的广域域、持持久性性数据据存取取服务务数据对对象以以只读读文件件版本本的方方式保保存，，使用用AGUID标标识可可用对对象，，VGUID标标识对对象的的各个个版本本，BGUID标识识数据据块，，这些些ID之间间以类类似B树的的方式式组织织OceanStore采采用两两种路路由和和定位位算法法：概概率查查询，，局部部，快快速，，但不不保证证成功功；全全局查查询，，后缀缀路由由匹配配，速速度慢慢，保保证成成功任何一一个数数据对对象都都对应应一个个主副副本环环，是是数据据对象象归档档存储储、更更新、、最新新版本本获得得的核核心设设施用户更更新对对象时时，数数据一一方面面被深深度归归档存存储，，一方方面被被分发发到对对象的的次级级副本本服务务器以以更新新缓存存OceanStore建建立在在广域域、动动态、、不可可靠的的网络络基础础上，，系统统中每每个结结点都都不可可靠，，因此此对所所有数数据提提供加加密或或认证证使用拜拜占庭庭式容容错提提交协协议保保持副副本间间的强强一致致性深度归归档存存储方方案中中，数数据以以冗余余编码码的方方式分分片冗冗余地地存储储在网网络的的多个个服务务器中中，仅仅利用用部分分分片片即可可重构构原文文件，，数据据是高高可用用、高高持久久性的的通过内内省机机制提提高存存取性性能和和自适适应性性9、静夜夜四无无邻，，荒居居旧业业贫。。。12月月-2212月