《《精编》第三代P2P网络之结构化P2P体系》由会员分享，可在线阅读，更多相关《《精编》第三代P2P网络之结构化P2P体系（88页珍藏版）》请在金锄头文库上搜索。
1、第四章第三代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 C
2、AN Tapestry Pastry著名学术团体与技术组织成立专门的P2P研究组 如MIT UCBerkeley Microsoft Stanford 4 1Chord与CFS 简单 精确的环形P2P网络 MIT与Berkeley的研究者01年正式发表http pdos csail mit edu chord Chord作为一个P2P网络 是基于带弦环拓扑结构的分布式系统 提供对象的存储 查询 复制 缓存 在其上可以架构更高层的分布式数据存储系统如协同文件系统CFSChord作为一个分布式散列表 只支持结构化P2P最简单的功能 将结点和数据对象映射到覆盖网中 但具有几乎最优的路由效率 确定性的
3、对象查询 负载均衡 高可靠性以及良好的容错性与自适应 最主要的是 简单 优美 Chord的技术特点基于安全的一致性散列函数来分配结点ID和对象ID在一个有N个结点的网络中 每个Chord结点保存O logN 个其他结点的信息查询数据对象需要的覆盖网路由跳数也为O logN 当结点加入或者离开网络时 为了维持网络结构 保持自适应性所需要的消息数在O log2N 一 Chord基础工作原理 Chord使用安全散列函数 如SHA 1 为每个网络结点和数据对象分配唯一的IDnodeID H node属性 属性可以是结点IP port 公钥 随机数或它们的组合objectID H object属性 属性
4、可以是数据对象的名称 内容 大小 发布者或者它们的组合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的后继结点负责的对象 其中
5、一部分必须分配给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
6、的后继 为确定对象k的后继 k所在的结点 结点n在自己的路由表中查找在k之前且离k最近的结点j 让j去找离k最近的结点 递归查找 最终可以找到对象k的前驱 在k之前离k最近的结点 记做predecessor k 类似 结点n的前驱记做n predecessor 前驱中必然有后继的路由表项 定位成功 Chord结点n的路由表各项属性及其定义 二 Chord对象定位算法 定位算法的三个函数的伪代码 请求结点n寻找id的后继n find successor id n find predecessor id returnn successor 请求结点n寻找id的前驱n find predecesso
7、r 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的距离通常比原来少一半 因此一般最多调
8、用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负责的数据对象索引传递给
9、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 fing
10、er table n i 递归地更新Chord网中所有需要更新路由表第i项的结点信息通常情况下 一个新结点加入Chord网 需要更新信息的结点数为O logN 因此寻找和更新的时间复杂度为O log2N 相关伪代码 四 Chord自适应算法 以上算法完备 细致 但有未解决的问题 并发操作 不正常操作 如结点异常退出 解决方法 简化join函数 仅通过n 寻找n的后继 其它什么也不做每个Chord结点周期性调用稳定函数stabilize和路由表更新函数fix fingers 前者修正结点后继并通知其后继修正前驱 后者在此基础上随机修正自己的路由表项通过合适的周期保持定位高效率 五 Chord容错
11、性和复制 缓存 Chord中正确的后继关系是一切工作的基础无论机制如何完善 网络的动态性和不确定性都可以导致单后继失效因此 实际的Chord给每个结点维护一个后继列表 其中保存了该结点在Chord环上的r个后继 典型地取r O logN 即使结点失效概率为1 2 仍能正确定位将结点保存的数据对象复制到所有后继中 可提高数据的可用性 持久性在Chord定位过程中 如每个中间结点缓存数据对象 可以提高获取数据的速度 六 Chord实验分析 负载均衡负载均衡是使用一致性散列函数的结构化P2P网络的共同属性对于Chord而言 由于数据对象被分配到其后继中 而数据对象 结点的ID都是随机 均匀产生的 因
12、此每个结点所负担的数据对象也应该大致均衡此外 Chord还采用了 虚拟服务器 的方法 在一台计算机上运行多个Chord结点 可以使得结点各尽所能 1万个结点 50万个数据对象 定位路径长度理论量级为O logN 跳实验中网络结点数取N 2k 数据对象数取100 2k k从3取到14测量结果 路径长度平均约logN 2 是logN的一半 原因是Chord路由表的指数构造 使其每次查找都能将目的ID与当前结点ID之间的差距减小至少一半 可推导出平均路径长度正好是logN的一半 网络结点数为212 七 Chord总结 Chord采用带弦环拓扑结构 通过一致性散列函数将结点 数据对象映射到覆盖网上 数
13、据对象 索引 由其后继结点负责 简单 精确正是Chord最大的特点每个Chord结点维护一个很小的路由表 后继关系是Chord定位的基础 路由表可以将定位路径长度缩短为O logN 跳Chord需要保持两个不变的属性才能正确工作 后继正确 后继对对象的索引正确Chord采用周期性的稳定算法和路由表更新算法检查和修正后继关系及路由表项 为保持高容错性 Chord采用后继列表避免单后继失效 此时可以对数据对象进行复制和缓存 提高网络效率 八 CFS Cooperativefilesystem CFS协同文件系统是以Chord为基础的P2P协同只读文件存储系统 文件分块存储CFS由三层构件组成Cho
14、rd 底层定位散列表 维护路由表 定位数据块所在的服务器DHash 分布式数据块散列表 中间层 分布和缓存数据块以平衡负载 复制数据块以容错 并通过服务器选择来减少时延 使用Chord定位数据块FS FileSystem 文件系统 高层 从DHash层获得数据块并转换为文件 给更高的应用提供文件系统接口 CFS文件系统类似UNIX文件目录结构 只是以根块代替根目录 以元数据块代替子目录 以数据块代替文件 而以块标识代替文件地址CFS对Chord的改进 采用前驱列表定位以提高定位容错性 使用服务器选择减少定位时延 对结点ID认证以防止ID伪造和IP虚报CFS对数据块采用后继复制以提高数据可用性
15、同时减少了客户获取数据的时延 采用路径缓存提高系统工作效率 同时避免热点数据的后继结点负载过重 采用 虚拟结点 和 限额 方法提供负载均衡 4 2CAN 简单 容错的多维空间P2P网络 ContentAddressableNetwork 内容可寻址网络 采用多维Torus环面拓扑结构 典型采用的二维空间网格 类似于笛卡尔平面 其结点编址方式也类似于点的编址01年 Ratnasamyetal 在ACMSIGCOMM会议发表正式论文 与Chord同年同会 CAN的多维空间被动态地分配给其网络结点 每个结点占有一个属于自己的方块并负责该方块中所有的 点 数据对象索引 每个结点维护一个路由表 记录多维
16、空间上的邻居信息 如图中结点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空间中的一个
