P2P网络-----------——结构化P2P体系

第四章第三代P2P网络——结构化P2P体系Chord、CAN、Tapestry、Pastry4.4Pastry与PAST：容错的混合式结构P2P网络Pastry结合了环形结构与超立方体结构（实际是Plaxtonmesh）的优点，提供高效的查询路由、确定性的对象定位和独立于具体应用的负载均衡与Tapestry的不同在于后者是尽可能找到最近的副本，前者则希望副本能均匀、分散的放置00年MicrosoftResearch与RiceUniv.开始设计，01年发表[Rowstron&Druschel,2001]Pastry的应用SCRIBE通用、可扩展的组通信和事件发布系统，提供应用层多播和任播PAST广域、安全的P2P归档存储系统SQUIRREL分布式的协同Web缓存，使得用户Web浏览器之间能共享缓存SplitStream基于Pastry的高带宽内容流化/发布系统POST提供通信、协同的消息框架，可用来支持安全E-mail、安全实时消息、分布式协同应用等Scrivener强调P2P系统资源公平共享的架构其他Pastry项目PASTA：剑桥大学开发的类似PAST的文件系统Herald：Microsoft开发的出版/订阅事件发布服务Pastiche：密西根大学开发的P2P备份系统DPSR：普度大学开发的有拓扑意识的结构化P2P架构与移动AdHoc网多跳路由协议之间的协同项目一、Pastry路由Pastry结点与数据对象使用128位的ID，对象索引由与对象ID最接近的结点负责Pastry采用前缀匹配（本质同Tapestry）每个结点维护一个路由表、一个叶集和一个邻居集；路由表分层，每列从上到下分别代表与当前节点ID前缀匹配对应位数的结点，其行数就是Pastry采用的进制数；与当前结点nodeID在该位恰好相等的项标为阴影，通常是空指针图中每项结点ID以X-Y-Z形式表示，其中X标识匹配的前缀，Y表示第一个不匹配位，Z则是结点ID的后几位Pastry结点状态叶集L中包含|L|个与当前结点ID最邻近的“叶结点”，其中|L|/2个比当前ID小，|L|/2个大；叶集的作用在于保证Pastry路由的正确性，类似Chord中的后继列表邻居集M中包含|M|个在网络物理层与当前结点临近的结点，其作用在于增强Pastry工作的局部性，路由过程中通常不使用MPastry结点状态=L+R+M，表中结点项数=|L|+B*logBN+|M|，B为进制，N为网络结点总数基于上述路由表，Pastry采用前缀逐位匹配路由，通常每一步至少比前一步多匹配一位前缀，直到无法匹配更多位数，此时的下一跳结点为ID与目的地最邻近的结点，更具体的说，是当前结点的叶集L中与目的ID最接近的结点显然，Pastry定位跳数为O(logBN)，由于叶集L的存在，其路由比Tapestry更快，更容错为提高安全性，防止恶意结点的破坏，Pastry采用“随机路由”来减少路由的确定性，如，当多个结点都符合下一跳的条件时，不一定选择最优的，而是随机选择一个，以牺牲性能来换取安全Pastry核心路由算法路由表R中第l行第Dl项T，D匹配的前缀长度Li指叶集L中离当前结点ID第i近的结点判断D是否在叶集L内路由表项空缺或不可达二、Pastry自组织和自适应Pastry结点加入网络的三项工作初始化路由表、叶集和邻居集，通知其他结点自己的到来，从现存结点获取需要负责的数据JOINSTEP1：初始化路由表、叶集和邻居集新结点X通过众所周知结点或者“扩展环”IP多播联系到一个现存结点A，通常在物理上离X很近X通过A发送一条以X为目的地的消息，按前缀匹配路由算法，最终到达nodeID离X最近的结点Z加入消息所走过路径上的每个结点将它们的路由表信息发给X，X接收并优化（类似Tapestry）X直接从Z获得叶集并作修正，直接从A获得邻居集JOINSTEP2：通知其它结点自己的到来比Tapestry简单，只需要把X的结点状态信息发给自己的路由表、叶集、邻居集中的结点收到更新消息的结点自己去选择用X替换表项JOINSTEP3：新结点获取需要负责的数据经典论文中未专门讲述，但类似于Tapestry，且更简单，只需要从叶集结点获取数据结点的正常离开处理很简单，只需要通知自己所知的结点结点失效的处理（周期性检测）FAILSTEP1：修正叶集某结点发现其叶集中某个结点失效，则向叶集中离失效结点最远的结点获取叶集，从中寻找最合适的结点来修正失效的叶集项由于叶集对Pastry正确工作有基础性的作用，因此对其修正是严格、频繁和高要求的FAILSTEP2：修正路由表路由表的修正要求比叶集低很多：路由表的错误只会导致效率下降；路由表项数很多，不宜频繁更新当结点发现路由表中第l行第d项失效，会发消息给第l行未失效的任一结点，获取其路由表的第l行第d项作为替代；如果路由表第l行所有项均失效，则联系第l+1行中的结点，迭代至替换成功FAILSTEP3：修正邻居集通常不使用，其修正更为松散，长周期，从未失效邻居集结点获取邻居集并替换三、Pastry的局部性分两步实现局部性部分体现在路由表的构造上，但其中的局部性并不准确，Pastry的局部性实际来源于邻居集M路由表初始化以后，新结点通过邻居集M来修正路由表项，用物理网上离自己确实很近的结点来替换原有项Pastry采用传统的ID邻近复制，同一数据对象被复制到与其ID相近的k个结点上，也提供了一定的数据存取局部性：因为ID相近的结点通常分散在整个网络中，总会有一两个离查询者很近四、Pastry实验分析Pastry平均路由跳数与网络结点数间关系，B=16，|L|=16，|M|=32Pastry路由路径长度（跳数）的相对距离与网络结点数的关系，黑线是理想的最优路由Pastry平均路由跳数与结点失效的关系，B=16，|L|=16，|M|=32，5000个结点，20万次查询Pastry总结Pastry是一个容错、高效、可扩展的混合式结构P2P网络，结合了环形结构与超立方体结构的优点，在物理网上构造了一个分布式、自组织、容错的覆盖网，提供高效的路由、确定性的对象定位和独立于具体应用的负载平衡，还提供了复制、缓存、错误复原等增强机制Pastry的定位、路由类似Tapestry，但采用前缀匹配路由，由于使用叶集，更快速Pastry结点的加入、失效算法由于叶集和邻居集的存在，比Tapestry能更简单、更快地达到自适应效果Pastry构建网络时考虑了局部性因素，来源于邻居集五、PAST简介以Pastry为底层架构的归档存储系统Rowstron&Druschel，2001，两篇论文负载均衡与结点能力差异：均匀未必是最好的六、PAST操作插入：fileID=Insert(name,owner-credentials,k,file)插入名为name的文件file，并保存k个副本，用户证书owner-credentials通常是用户的公钥，fileID一般是以上四个参数的安全散列值（有时加入salt）用户有存储限额（storagequota）插入文件有私钥签名的文件证书，包括fileID，文件内容散列值、副本数目、盐值、创建时间等文件证书与文件一起路由到ID最近的结点，该结点验证文件拥有者与文件完整性后，存储副本并将插入请求路由到其它负责存储文件的结点插入成功后，回发确认消息，每个存储结点都加入自己的存储收据（storagereceipt）查询：file=lookup(fileID)同时获得文件与文件证书多副本均匀分布使查询高效PAST查询只能基于fileID，不支持关键码查询，系统中的文件也没有目录结构回收：Reclaim(fileID,owner-credentials)为删除文件，回收者提供“回收证书”，存储文件的结点认证后，回发“回收收据”，回收者恢复“存储限额”，但并不真正删除文件七、PAST安全机制每个PAST用户有一个smartcard（智能卡，PAST安全机制的核心部件），带有一对密钥，其中的公钥带有smartcardissuer（发行者，权威的可信机构）的数字签名Smartcard的作用产生和验证各种各样的证书维护结点的存储限额安全性的前提系统中大多数的用户可信攻击者不能控制smartcard智能卡保证nodeID和fileID的完整性，从而防止攻击者控制nodeID邻近的多个结点以完全控制某个文件所有副本的可能存储收据防止攻击者欺骗文件插入者已存储k个副本，但实际上副本数远远不足k的可能文件证书使得存储文件的结点和获取文件的结点都能验证文件插入者的真实性和文件内容的完整性文件证书和回收证书配合实现存储限额机制PAST用户也可以将文件加密后再插入系统底层架构Pastry提供的安全性：随机路由，降低路由确定性对每个路由表项，或叶集、邻居集中的结点，Pastry可以要求相应结点签名后做验证、验证通过才加入表中的方法，防止恶意结点伪造表项的可能八、PAST存储管理目的在系统存储利用率逐步达到100%的过程中，不断平衡网络结点剩余的空闲存储空间维护PAST的复制不变属性——每个数据对象的k个副本被存放在nodeID相近的k个结点上方法转移(diversion)：副本(replica)转移；文件转移基于节点异构性，通过比较的方法控制“每结点存储容量”的分布。当新结点N加入时，PAST将N公布的存储能力与其叶集结点平均存储能力比较，高则以多个nodeID的形式加入，过低则可能被拒绝PAST的存储管理对文件不分片不足之处：大文件常常需要通过“副本转移”或者“文件转移”的方法存放；过大的文件经常因为放不下而被系统拒绝好处：实现简单；避免分片带来的开销和维护的复杂度副本转移PAST通常让nodeID与fileID最近的k个结点保存文件的k个副本，当其中某个结点A带宽、空间严重不足而文件f又很大时，“副本转移”允许结点A叶集中的结点B来代替地保存副本，A只保存到B的指针A将f的副本转移到B之后，必须确保（1）B的失效将自动导致一个新副本的创建（Pastry的机制保证）（2）A的失效不会导致B上的副本不可达（在nodeID离fileID第k+1近的结点C上保存副本指针）文件转移当“副本转移”仍不能完成保存任务时，即叶集结点也无法容纳文件，只能回发给文件插入者一个“消极确认”(negativeacknowledgement)消息插入者使用新的盐值(salt)为该文件产生新的fileID，并重新尝试插入，称为“文件转移”文件转移尝试四次后才放弃插入操作九、PAST缓存管理目的：减小文件查询时延；增加系统查询吞吐量；平衡系统查询负担方法：路径缓存（文件插入路径或查询路径）副本只是临时缓存，结点需要空间时可以自主替换缓存，PAST的缓存替换方法基于GD-S策略(GreedyDual-Size，原先用于缓存Web代理)GD-S为每个缓存的文件d维护一个权重H(d)，每当缓存命中，H(d)被设为c(d)/s(d)，c(d)代表和文件d相关联的某种开销，常设为1，s(d)代表文件大小；H最小的文件v首先被替换，替换后，当前每个缓存文件的H(d)被减去H(v)。该策略可最大化文件命中率PAST总结是一个以Pastry为底层架构的广域P2P归档存储系统，提供Internet上安全、高可用、持久性的数据存取服务PAST向其用户提供几个基本操作：插入、查询、回收。这些操作都需要相应的“证书”以检验其合法性，插入、回收时还需要“收据”确认每个PAST用户都有一个“智能卡”，由权威的可信机构发行，是PAST安全机制的核心部件PAST的存储管理采用了副本转移、文件转移、路径缓存等多种方法4.5其他著名结构化P2P网络理论模型：具有特殊性质的新型结构化P2P模型——常数度P2P网络，其路由、定位、自组织方式与过去的模型区别不大，但每个结点的“度”（即连