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

宽带媒体服务技术之对等网络科大10系王雷第四章第三代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、Stanford宽带媒体服务技术之对等网络4.1Chord与CFS：简单、精确的环形P2P网络MIT与Berkeley的研究者01年正式发表宽带媒体服务技术之对等网络Chord作为一个P2P网络，是基于带弦环拓扑结构的分布式系统，提供对象的存储、查询、复制、缓存，在其上可以架构更高层的分布式数据存储系统如协同文件系统CFSChord作为一个分布式散列表，只支持结构化P2P最简单的功能：将结点和数据对象映射到覆盖网中，但具有几乎最优的路由效率、确定性的对象查询、负载均衡、高可靠性以及良好的容错性与自适应，最主要的是：简单、优美宽带媒体服务技术之对等网络Chord的技术特点基于安全的一致性散列函数来分配结点ID和对象ID在一个有N个结点的网络中，每个Chord结点保存O(logN)个其他结点的信息查询数据对象需要的覆盖网路由跳数也为O(logN)当结点加入或者离开网络时，为了维持网络结构、保持自适应性所需要的消息数在O(log2N)宽带媒体服务技术之对等网络一、Chord基础工作原理Chord使用安全散列函数（如SHA-1）为每个网络结点和数据对象分配唯一的IDnodeID=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].nodeChord路由表的特点：每个结点只保存很少的其它结点信息，并且对离它越远的结点所知越少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≤m.interval[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：简单、容错的多维空间P