P2P网络缓存协作的研究

P2P网络缓存协作的研究 贾磊 , 张新有 ()西南交通大学 信息科学与技术学院 , 四川 成都 610031 E 2m a il: sfw 123817 @ gm a il. com 摘 要 : 为了提高 P2P网络的数据性能和提高节点的缓存利用率 , 提出一种实施在应用层的缓存协作 R /W GCC , 它由分 组协议和缓存协作协议两部分组成 . 根据 P2 P网络中节点不稳定的特点 , 分组协议分析了节点的四种不同的状态 , 把一个 节点的邻居结点分为只读组和读写组 , 并提出一种区分节点状态的分组算法 . 缓存管理协议利用缓存替换算法中产生的信息并 根据节点所在的分组 , 管理组内的缓存资源 . R /W GCC 平衡了各节点的缓存利用率 , 提高了缓存的命中率 , 有效的提高缓存的 效率 . 关 键 词 : 缓存利用率 ; 缓存协作 ; 节点分组协议 ; 缓存管理 ( ) 文 章 编 号 : 100021220 2011 04 20701207 中图分类号 : TP393 文献标识码 : A C oopera t ive Ca che for P2 P Ne t work Re sea rch J I A L e i, ZHAN G X in2you ( )Sou thw es t J ia o tong U n ive rs ity, Schoo l of Info rm a tion Sc ience a nd Techno logy, C hengdu 6100031, C h ina ( A b stra c t: To im p rove the da ta p e rfo rm ance and C ache U tiliza tion of the P2 P ne tw o rk, a nove l C oop e ra tive C ache P ro toco l R / ) W GCC is p resen ted, w h ich inc ludes a G roup ing P ro toco l and a C oop e ra tive C ache M anagem en t P ro toco l. Fo r the uns tead iness of the p ee r in P2 P ne t w o rk, fou r d iffe ren t s ta tus of the p ee r a re ana lyzed, and the ne ighbo rs of a p ee r a re g roup ing to R ead G roup and W rite G roup by G roup ing P ro toco l. A nd a nove l g roup ing a rithm e tic w h ich d is tingu ishes p ee r s ta tus is p resen ted. The C oop e ra tive C ache M anagem en t P ro toco l use the info rm a tion gene ra ted f rom C ache rep lacem en t a lgo rithm and the g roup w h ich the p ee r be long to, to m anagem en t the C ache resou rce. C ache U tiliza tion of the p ee r is ba lanced, C ache H it is p rom o ted and the eff ic iency of the C ache is im p roved by R /W GCC. Key word s: cache u tiliza tion; coop e ra tive cache; g roup ing p ro toco l; cache m anagem en t [ 2 ] 高 P2 P系统的数据性能 . 1 介 绍 现存的缓存协作大多是根据某种算法将网络上所有的节 P2 P技术在内容共享 、分布式计算 、信息检索等应用领域 点分为若干个缓存组 , 然后网络中的节点再根据某种协议或 [ 325 ] 都有很广泛的应用 . 但是无论它应用在那个领域 , 数据的获取 来获取组外或组内成员节点缓存的数据 . 但是有两都是非常关键的环节 , 并且也是最容易造成系统瓶颈的环节 . 个问题它们都没有考虑到 : 首先是对节点进行分组时并没有 缓存技术是提高数据性能的一种非常有效的技术 , 这在传统考虑到对网络不同状态的节点作区分对待 . 网络上的节点有 的单机系统中 , 无论是在硬件上和软件上都得到了很好的验 的是活跃的 、有的是不活跃 的 、有的 是稳定长期存在的 、而证 . 但是在 P2P系统中单个的主机不仅是以一个独立的实体 有的只是一闪而过 , 它们对数据和缓存的需求都不一样 . 对节 [ 1 ] 而存在 , 而且是以系统中的一 个节点而存在 . 它作为系统点良好地分组是提高缓存协作管理效率的有效方法 , 所以以 的一部分不仅要从自身的软硬件上获取数据 、要从网络中的 上这些因素都应该在节点分组的时候进行考虑 , 以便使其以 其他节点上获取数据 、更要为其他节点提供数据 . 这时传统的 最大限度地提高缓存协作的效率 ; 其次是没有考虑到当一个 缓存技术便不能很好的适应多个网络节点共享数据或进行分 活跃的节点其自身数据需求量比较大而其缓存又不够使用的 布式计算的需要 , 于是网络缓存协作就产生出来了 . 所谓网络 时候 , 它可以向组内其他不活跃节点的缓存中写数据的情况 . 缓存协作就是指在 P2 P网络中 , 一个节点不仅能从自身的缓 考虑这种情况 :在一个组中并不是每一个节点都会有频繁的 存中缓存和获取数据 , 而且能够从其他 Pee r节点的缓存中缓 存和获取数据 . 这种情况下就需要各个 Pee r节点在进行缓存 数据请求 , 总有些节点是属于空闲状态的 , 这在实际网络中这 替换时不仅要考虑到自身数据的需求 , 而且还要考虑到网络 也是很常见的 , 把这部分节点利用起来能提高组内缓存的利 中其他节点的数据需求 . 网络缓存协作的应用可以显著的提 用率 . 本文首先分析了现有的缓存协作方案 , 并提出一种新的 ( ) 收稿日期 : 2010 205 221 收修改稿日期 : 2010 203 223 基金项目 : 国家自然科学基金项目 U 0970122 资助. 作者简介 : 贾 磊 , 男 , 1984 年 生 , 硕士研究生 , 研究方向为 P2 P 网络 、P2 P缓存协作 ; 张新有 , 男 , 1971 年生 , 博士研究生 , 副教授 , 研究方向为 P2 P 技术 、新型网络体系结构 、网 络管理. 702 小 型 微 型计 算 机 系 统2011年 缓存协作方案 : R ead /W rite G roup B ased C oop e ra tive C ache 简文献 [ 5 ]提出的节点分组方案 , 在两节点之间传送 H e llo 称 R /W GCC. R /W GCC 包括两部分 : 第一部分是区分不同节 消息并根据接收到 H e llo消息的情况来决定两个 p ee r节点之 点类型的节点分组协议 . 这个协议会根据网络中节点的不同 间的关系来分组是一种较好的分组方案 , 这种方案能准确 、快 类型 , 把一个节点的邻居节点分为只读组和读写组两部分 ; 第 速反应出当前网络的状态 , 并有一定的自适应性 . 但是其方案二部分是节点的缓存管理协议 . 这个协议把组内节点的缓存 中有太多的中间状态转换 , 这会增加协议的复杂度 , 而且它也 资源统一管理 , 利用缓存替换算法计算缓存中每块数据的使 没有利用这些中间状态的信息来细化分组 . 本文借鉴了其主 用概率值 , 当需要进行缓存替换的时候 , 替换组内使用概率值 要思想 , 设计出了一种新的分组方案 , 减少了状态数量并根据 最小的数据 . 这样可以平衡各个节点对缓存的利用率 , 提高组 这些状态细化了分组的粒度 , 充分利用节点之间的状态信息 , 能更准确的反映当前网络的状态 .内整体的缓存利用率 . 2 相关工作3 分组协议 目前对于 P2 P 网络缓存协作策略的研究越来越受到人分组协议的目的是根据某种算法将网络上所有的节点分 们的关注 , 并且提出了一些缓存协作协议和缓存替换策略 . 文 为若干个缓存组 , 以便于缓存管理协议能够管理组内或组间 献 [ 3 ]在有 基 站 的 移 动 网 络 中 , 提 出 了 一 种 缓 存 协 作 方 案 节点的缓存使用和缓存协作 . 一个完善的分组协议能提高缓 ( ) CO CA , 移动节点可以通过 P2P 信道从邻居节点的缓存内 存协作的效率 . 获取所需的数据 , 并将这种从邻居节点的缓存内获取数据的 现有的分组的策略以两种基本分组方式为主 : 一种是基 方式称为 G loba l C ache. 基站会定期向其覆 盖范围内的节点 于对不同数据的感兴趣程度来划分 , 就是对同类型的数据感 [ 7 ] 推送一些访问率较高的数据以提高 G loba l C ache 的命中率 .兴趣的节点被分成一组 ; 另一种是 基于地理位置划分 , 就[ 3 ] () 是把距离相近 或是在同一区域中 的节点分为一组 . 一般 文献 [ 6 ]扩展了文献 [ 3 ]的缓存协作方案 , 设计了一种缓存协 (有两种衡量距离的方式 : 第一 种是由节点的位置 这个位置 作中使用的 C ache 签名的机制 . C ache 签名就是使用哈希函 )可由 G PS 测量获得 来计算两个节点间的距离 , 然后根据这 数对缓存中的数据进行哈希计算得出一个哈希值 , 然后把各[ 4 ] 个距离来判断这两个节点是否属于同一组 ; 第二种是由节 个数据的哈希值进行叠加运算 , 最后得出的数值就能以一定 点定期的发送 H e llo消息 、监听并记录从别的节点来的 H e llo 的概率示其 C ache中的数据 . 这个签名被压缩以后在移动 消息 , 一旦受到回应或是收到 从别的节点来的 H e llo 消息就 节点间传递 , 使得各个移动节点能够了解需要的数据是否被[ 5 ] 把该节点记录下来 , 这个节点就成为其组内成员 . 邻居节点缓存 . 文献 [ 4 ]扩展了文献 [ 3 ]的缓存协作方案 , 提 出了一种基于组的缓存协作方案 . 该方案根据节点的移动特 虽然基于对不同类型数据感兴趣程度来划分的组 , 能把性和对数据的感兴趣的程度 , 把网络中的节点分成组 . 并提出 对同类型的数据感兴趣的节点分到一个组中 . 这样组内节点 的缓存中会集中的缓存本节点或组内节点需要的数据 , 从而 了一个缓存协作的管理协议 , 这个协议用来协调 、管理本地缓 提高 C ache 的命中率 . 但是在 P2P网络环境中 , 对相同类型的 存和全局缓存 . 文献 [ 5 ]扩展了文献 [ 3 ]提出了一种新的节点 数据感兴趣的节点很有可能距离上离得非常远并且分布的很 分组算法 , 避免了文献 [ 4 ]中的节点分组算 法需要一个中心 分散 , 这种情况下既使组内节点的缓存中有本节点需要的数 服务站支持的缺陷 . 文献 [ 7 ]提 出一种新的应用 在 移 动 P2P ( 据 , 也很有可能连不上这个节点或者要取到这些数据所需的 网络中 的 缓 存 协 作 方 案 2邻 近 区 域 缓 存 协 作 的 方 案 PR e2 () ) C inC t. 它把网络划分成不同的区域 , 每个区域负责存储一组 代价比从数据中心 或数据源 取数据的代价还大 , 这就得不 偿失了 . 数据和其关键值 , 当某个节点需要数据时会根据数据的关键 () 值来找到这个数据可能所在的区域 , 然后发请求给该区域的 基于距离的 或是区域的 组就能很好的避免这个问题 , 因为距离近的点 , 第一能连接上的可能性会很大 ; 第二从缓 节点从 而 获 取 数 据 . 其 使 用 的 C ache 策 略 不 仅 考 虑 到 该 C ache 数据块对自身节点重要性 , 也考虑该 C ache 数据块对 存中取数据并通过网络传输 , 所需的代价也更小 . 但是距离 别的节点的重要性 , 使用效用函数来进行衡量 . 文献 [ 8 ]提出 近的节点不一定会对类似的数据感兴趣 , 或许它们会对根本 不同类型的数据感兴趣 . 所以又有第三种分组方式 : 综合考 了一种在使用 p ush方式的内容分发网络中的一种缓存协作 .[ 4 ] 虑节点的距离和对数据的感兴趣程度来划分 , 但是它需要 文献 [ 9, 10, 11 ]提出了一种在 A d H oc 网络 中使用的缓存协 一个中心节点来计算一个既能衡量距离又能衡量对数据感兴 作协议 . 文献 [ 12 ]提出了一种缓存协作的优化策略 . 趣的程度的值 , 然后根据这个值做出判断 , 但这又会引起单 上述移动 P2P 网 络 的 缓 存 协 作 策 略 的 研 究 成 果 给 P2P 点故障问题 .缓存协作的研究带来了很多的启示 , 但是也存在着许多的问 本文提出了一种新的基于距离的节点分组方式 , 并且区 题 . 比如文献 [ 4 ]提到的缓存协作方案就需要通过一个中心 分节点的不 同 状 态 把 组 分 为 只 读 组 和 读 写 组 , 分 别 命 名 为 服务器来辅助 , 这就存在着如单点故障等隐患 . 而且也没有 解决如何把协作的内容缓存到多个移动节点上来 , 实现由移 R ead G roup 和 W rite G roup. 一个节点会以自己为中心把其邻动节点支撑的缓存协作方案 . 比如文献 [ 7 ]提出的基于区域 居节点划分为只读组和读写组两部分 . 由于基于绝对位置的 ( ) 距离衡量方式太过僵化 , 获取节点地理位置 G PS 的代价较 的缓存协作协议 , 把数据固定在了某个区域内从而限制了灵 活性 .大 , 并且地理位置近的节点不一定就是可以稳定连接的节点 . ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. 703 4期贾 磊 等 : P2P网络缓存协作的研究 所以本方案采用定期发送和记录节点之间发送的 H e llo 消息.把它用不了的缓存资源拿出来让需要的节点使用 和 R ep ly消息的方式来衡量两个节点是否在一个组 , 这样可 3. 3 分组算法 节点的分组算法就是区分不同类型的节点 , 并根据节点 以保证组内节点是一个可以连接的有效节点 . 3. 1 节点的分类的类型把它们分到不同的组中 . 首先一个节点应该知道其自 根据 P2 P网络中节点的稳定特性来划分 , 网络中一般会 身是否是活跃的 , 即其是否有比较大的数据需求 , 这个可以由 有四种类型节点 : 节点应用层的应用程序获取 . 其次是稳定性 , 这里借鉴了文献 第一种是稳定的活跃节点 , 所谓活跃是指它有比较大的[ 5 ]提出的方案并对其做了适当的修 改 , 既在两个 节点之间数据需求量 . 这种节点会有比较大的缓存和数据需求量并且 相互传送 H e llo 和 R ep ly 消息 , 根据接收到的 H e llo 和 R ep ly 会在比较长时间内的存在于 P2P 网络中 . 它一方面需要其他 消息的情况来判断其稳定性 . 具体的操作在下面的分组算法 节点提供的缓存资源 , 另一方面也为其他节点提供比较稳定 中描述 . 的缓存资源 , 为提高缓存的利用率提供一定的贡献 . 节点定期的向其邻居节点广播一个跳数限制为 2的 H e l2 第二种是稳定的不活跃节点 , 这种节点没有太大的数据 lo消息 . 将这个消息的跳数限制为 2有两个原因 :首先是在一 和缓存需求 , 但会在比较长的时间内存在于网络中 . 这种节点 定程度上扩大组的范围 . 因为一个节点的邻居节点是有限的 , 既可以为网络提供比较稳定的缓存数据资源 , 又可能为其他 而缓存组中的节点数目 越多其能够用来协作的缓 存也就多 节点提供一定的缓存资源供其使用 , 这里的使用既包括读也大 . 把广播的跳数设定为 2 就是它的缓存组包括它的邻包括写 , 也就是说它可以把自己用不了的缓存资源拿出来让 居和它邻居的邻居 ; 其次是为了防止广播泛洪造成的网络拥 组内其他需要缓存资源的节点使用 . 堵 , 并控制组的范围不使其太大 . 可以认为从这个范围内的节 () 第三种是不稳定的活跃节点 , 这种节点只会在较短的时 点的缓存中取数据的代价将比从数据中心 或数据源 中取 间内存在于网络中 , 比如以较快的速度在网络中移动或是在 数据的代价要小 . 接收到 H e llo消息的节点会向发送 H e llo 消 连接上以后很快的断开网络 . 而且它有比较大的数据和缓存 息的源节点返回一个 R ep ly消息 . 并且节点维护两张表 , 这两 需求 . 它主要需要其他节点为它提供缓存数据资源 , 而很难为 张表分别记录了其只读组和读写组成员 . 其他的节点提供缓存资源 . 节点与它的某个邻居节点之间有三种关系 , 它们分别是 : ?U nknow n: 它没有收到来自其邻近节点的 H e llo 或 R e2 第四种是不稳定的不活跃节点 , 这种节点在网络中存在 的时间比较短 , 而且没有太大的数据和缓存需求 . 它既不需要 p ly消息 ; ?R ead G roup :它与其邻居节点的关系是只读 关系并且 其他节点的缓存资源 , 也很难为其他节点提供缓存资源 ; 缓存分组协议中应当充分的考虑到以上四种类型节点的 该邻居节点是它的只读组内的成员 , 它只能读取该邻居节点 不同特性 , 加以区分对待 , 这样才能最大限度的提高整体的缓 的缓存中的数据 ; 存利用率 , 提高 P2 P网络的整体效率 . ?W rite G roup :它与其邻居节点的关系是读写关系并且 3. 2 组的分类该邻居节点是它的读写组内的成员 , 它不仅能读取该邻居节 点缓存中的数据 , 而且还能向该邻居节点的缓存中写入数据 . 根据节点的不同类型 , 应将组分为两类 : 第一类为只读组 , 称为 R ead G roup. 一个节点只能读取其 一个节点根据其邻居节点与它的关系 , 把邻居节点分为 只读组内节点的缓存中的数据 , 而不能向只读组内的节点的 只读组或读写组 . 图 1展示了这三种关系状态之间的转换 .缓存中写数据 . 稳定的活跃节点 , 不稳定的活跃节点和不稳定 的不活跃节点都要被分到只读组中 . 对于稳定的活跃节点虽 然它能为其他节点提供较为稳定的缓存资源 , 但是由于其自 身对缓存的需求比较大 , 这就导致其缓存中的数据被再次使 用的概率较大 , 所以它无法再拿出缓存资源给其他节点进行 写操作 . 而对于不稳定的节点 , 由于其无法稳定的存在于网络 中 , 如果其他节点把其需要缓存的数据写到这种节点的缓存 中的话 , 那当它需要这个数据并要通过网络从这种节点的缓 存中取所需数据的时候 , 这个缓存了其他节点的数据的不稳 定节点很可能就断开了网络 , 从而导致无法的得到所需的缓 存数据 , 造成缓存失效 . 所以它们只能为其他节点提供只读的 图 1 状态转换图 缓存资源 , 从而被分到只读组中 . F ig. 1 S ta te trans ition d iag ram s 第二类为读写组 , 称为 W rite G roup. 一 个节点既能读取 首先一个节点的 某个邻居 节 点 与 它 的 关 系 为 U nknow n 其读写组内的节点的缓存中的数据 , 又能向读写组内的节点 关系 . 当它第一次收到从其某个邻居节点发来的 H e llo 或 R e2 的缓存中写入数据 . 稳定的不活跃节点会被分到读写组中 , 因 p ly消息时 , 该邻居节点与它的关系就提升为 R ead G roup , 它 为它能比较稳定的存在于网络中从而能为其他节点提供较稳 会把该邻居 节 点 记 录 到 其 只 读 组 表 中 . 当 它 能 在 一 段 时 间 定的缓存资源 , 而且由于其对数据和缓存的需求不大 , 它可以 ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. 704 小 型 微 型计算机 系 统2011年 17: next tim eou Wt 内均能收到从其某个邻居节点发来的 H e llo 或 R e2 end if p ly消息并且该邻居节点是不活跃节点的话 , 该邻居节点与它 18: 19: end if 的关系就提升为 W rite G roup , 它会把该邻居节点从其只读组 20: end fo r 表中删除并把它记录到其读写组表中 . 相反如果在 tim eou W t 对于两个节点 m 和 m 来说 , 它们开始时是 U nknow n 的 i j 时间内均没有收到读写组内的节点发来的 H e llo 消息或 R e2 关系 . m 会定期向 m 发送 H e llo消息 , 当它第一次收到从 m i j j p ly消息 , 它们 的 关 系 就 会 下 降 为 R ead G roup , 进 而 如 果 在 发来的 R ep ly消息时 , m 就把 m 记录到其 R ead G roup 表中 , i j tim eou tR 时间内均没有收到从只读组的节点发来的 H e llo 消这样 m 在 m 的 R ead G roup 组内 . 当 m 在 T im eO u Wt 时间 j i i 息或 R ep ly消息 , 它们的关系就下降为 U nknow n. 并且当收到 从只读组或读写组成员节点发来的结束消息时它们的关系会 直接下降为 U nknow n. 算法 1和算法 2描述了该分组算法 . 算 ()法 1. 节点分组算法 收到 H e llo或 R ep ly消息时 ( )re l i, j表示节点 m 和 m 当前的关系 ; i j R表示 m 的所有的只读组关系 , 初始化的时候 R为空 ; i i i W 表示 m 的所有的读 写 组 关 系 , 初 始 化 的 时 候 W 为 i i i 空 ; la s t_bea con _ t表示最后一次从 m 来的 H e llo 消息的时 j j 间 ; now 返回当前的时间 ; N on2A c tive表示该节点是否是活跃节点 . 图 2 节点拓扑图 ( )1: Rece iveH e llo F ig. 2 N ode top o logy d iag ram s / / m 收到一个来自于 m 的 H e llo或 R ep ly消息i j )then ( ( ) ( )2: if re l i, j Ra nd re l i , j W i i 内能收到来自 m 的 H e llo消息或 R ep ly 消息并且 m 为不活 j j ( ) 3: re l i, j?R ea d G roup跃节点时 , m 就会把 m 从 m 的 R ead G roup 表中 删除并把 i j i ( ) 4: R? R ?{ re l i, j} i i m 添 加 到 m 的 W riteG roup 表 中 , 这 时 m 就 成 了 m 的 j i j i ) ( ( )( ( tim eou tW a nd re l i, j 5: e lse if now 2la s t_bea con _ t< j W riteG roup 的成员 . ) (( ) ) )then ?Ra nd re l i, j W a nd m is N on 2A c tive i i j 表 1 节点 A 内维护的读写组 ( ) 6: re l i, j?W r ite G roupTab le 1 W rite g roup of p ee r A ( ) 7: R ?R?{ re l i, j} i i A 2W rite G roup 节点 ( ) 8: W ?W ?{ re l i , j} i i B 9: end if C D 10: la s t_bea con _ t?nowj H (算法 2. 定时刷新只读组和 读 写 组 内 的 节 点 的 状 态 时 间 轮 )询 与此相反 , 当 在 T im eO u tW 时 间 内 m 没 有 收 到 任 何 从 i ( )1: loop m 来的消息时 , m 就会把 m 从 W riteG roup 表中删除 , 放入 j i j ( ) 2: fo r a ll re l i, j?W doi R eadG roup 表中 , 这时 m 就降为了 m 的 R ead G roup 的成员 . j i then 3: ) ( ( )if now 2 la s t_bea con_ ts> Tim eO u tW j 当在 T im eO u tR 时间内 m 没有收到任何从 m 来的消息时 , i j ( ( ) )then 4: = W r ite G roup if re l i, j m 就会把 m 从 R ead G roup 中删除 , 这时 m 和 m 的关系就 i j i j ( ) 5: re l i, j= Rea d G roup 降为 U nknow n, m 不在网络上了 . j ( ) 6: W ? W 2 { re l i, j}i i 表 2 节点 A 内维护的只读组 ( ) 7: re l i, j} R? R?{ i i Tab le 2 R ead g roup of p ee r A 8: next 9: end if 节点 A 2R ead G roup F 10: end if G 11: end fo r E ) ( j?Rdo12: fo r a ll re l i, I i J ) ( ( ) 13: if now 2 la s t_bea con _ ts> Tim eO u tR then j ( ) if re l i, j= Rea d then 14: 下面举例说明 , 节点拓扑图如图 2 所示 , 节点 A 维护的 ( ) 15: re l i, j= U nKnow n 只读组和读写组成员表如表 1、表 2所示 .( ) 16: R ?R2 { re l i, j}i i ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. 705 4期贾 磊 等 : P2P网络缓存协作的研究 节点 A 的邻居节点为 B , C , D , G , H , I, 节点 A 定期向其利用缓存替换替换算法产生的信息 , 把缓存中使用概率最低 邻居节点发送一个 H e llo 消息 , 这个消息的 TTL 值被限制在 的数据的概率值及其大小放到 R ep ly 包中 , 将其返回给原请 两跳 . 在图 1中 , 节点 A 的两跳范围之内的节点是 B , C , D , E, 求节点 . 原请求节点收到 R ep ly后会把其中的信息提取出来 , H , F, G , I, J. 经过一段时间后由上面给出的分组算法 , 节点 A 填入其维护的读写组表中 , 如表 3所示 . 会得到表 1、表 2中的内容 . 表 1 和表 2 两个表分别记录了节 4. 2 节点收到数据时 点 A 的只读组和读写组成员的信息 : B , C , D , H 为节点 A 的 当一个节点通过网络接收到所请求的数据后 , 节点分析 这个数据是从哪里来的 . 如果这个数据来自于其读写组或只 读写组成员 , 而 F, G , E, I, J 为节点 A 的只读组成员 . 读组成员节点的话 , 我们假设在一段时间内这个数据是可以 4 缓存协作管理协议 以比较小的代价从组内成员的缓存中获取 , 就不对它进行缓 存而直接使用 , 并且这还可以避免因同一个数据在组内被多 缓存协作管理协议的作用是管理本地和组内的缓存数资 [ 13 ] 次缓存而造成缓存资源浪费的问题 . 如果它来自于组外节 源 . 根据缓存被使用的场景其操作主要分为三类 :首先当本地 点的话 , 就需要把这个数据保存到缓存中以备以后使用 . 虽然 应用程序需要数据时 , 本地应用程序会首先向节点的本地缓 这样可能会造成同一份数据被缓存到多了节点的问题 , 但是 存发送数据请求 , 当本地缓存没有所请求的数据时才会再向 这样可以提高整体网络的数据性能 , 而且在这里缓存数据被 服务器发送数据请求 , 这时缓存协作管理协议就要处理这个 复制的数量是受到控制的 : 即只缓存来自于读写组和只读组从本地应用程序发来的数据请求 . 其次网络中的一个节点作 外的数据 . 算法 3描述了节点收到数据后保存数据的过程 . 为缓存组的一部分 , 它会收到从缓存组的其他节点发来的对 算法 3. 数据缓存处理算法 :该节点缓存中的缓存数据的请求 , 这时缓存协作管理协议就 / / m 收到从 m 来的数据包 i j 要处理该数据请求 ; 最后当节点通过网络接收到其所需数据 ( )1: ca che (时 既包括从邻居节点的缓存中 获取的数据 , 也包括从资源 ( ) 2: ?W thenif re l i, j i ) 节点获取的数据 , 它一方面要把这个数据 交付给本地应用 ( ) 3: use _da ta ; 程序使用 , 另一方面也要缓存该数据以方便下次使用 , 这时缓 ( ( ) ( ( ) ( )4: e lse if re l i, j?Ro r re l i, jRa nd re l i , ji i 存协作管理协议就要处理如何缓存该数据 . ) )W then i 4. 1 节点收到从邻居节点来的对缓存数据的请求 5: ( ) if p a ck. s ize < s ize _ lim it then 当一个节点收到从邻居节点发来的缓存数据请求时 , 它 6: ( ) fo r a ll re l i, j?W do i 会查它维护的只读组成员表和读写组成员表 , 如果发现发出 7: ( ( ) )if ca che = id le a nd s ize > p a ck. s ize 缓存数据请求的 Pee r节点是其只读组内的成员 , 该节点就会 then 搜索缓存看是否有其需要的数据 . 如果有就返回一个有其所 8: ) ( send _da ta p a ck, m ; j 需缓存数据的响应给缓存数据请求节点 , 并等待对此响应的 9: end if 确认消息 、准备发送缓存数据 . 如果发现发出缓存数据请求的 ( ) 10: if no t ha s such node then 节点是其读写组的成员 , 该节点同样搜索缓存 , 看是否有其需 do ca che ins tea d 11: 要的数据 . 如果有就返回一个该节点有其所需缓存数据的响 12: ( ) fo r a ll re l i, j?W do i 应 , 并等待对此响应的确认消息准备发送缓存数据 . 如果没有 ( ) 13: if p < p then j 它会给请求缓存数据的节点返回一个 R ep ly 包 , 这个包中包) ( 14: send _da ta p a ck, m ; j 含该节点缓存的使用情况 . e lse 15: 表 3 节点的读写组成员表 ( ) 16: ca che_da ta ; Tab le 3 W rite G roup next 17: 节点名 数据 空间大小 18: end if 3 K B 有空余 19: end if 0. 11 1 K C 数据缓存处理过程 : D 0. 013 0. 5 K )1检查数据的大小是否超过一个被限定的界限 s ize_ lim 2 H it. 如果数据的体积过大就不对它进行缓存操作 , 因为首先对 返回的节点的缓存的使用情况包括 : 第一如果该节点的 它进行缓存的效率不高 , 其次在节点之间传输这种体积大且 缓存还有空闲空间则返回该节点缓存有空闲空间的消息 , 和 缓存效率不高的数据会降低网络效率 ; 其剩余空闲缓存空间的大小 ; 其次如果该节点的缓存没有空 )2搜索读写组成员表 , 看其是否存在有空闲缓存空间且 闲空间 , 则返回其缓存中使用概率最小的数据的信息 , 这个概 空闲空间大于或等于要被缓存的数据的读写组成员 , 如果有 率值是由缓存替换算法在进行缓存替换的时候计算出来的 . 就 把该数据通过 网 络 传 送 给 它 , 让 对 方 把 数 据 保 持 到 其 缓 缓存替换算法会把缓存中的数据按照这个值排序 , 以便在进 存中 ; ) 行缓存替换时把缓存中使用概率最低的数据替换出去 . 这里3如果不存在有空 闲缓存空间并且空间大于 或等于要 ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. 706 小 型 微 型计算 机 系 统2011年 被缓存的数据的读写组成员 , 就执行缓存替换算法 . 缓存替换R /W GCC 的节点的缓存命中率为 :没有实现 L oca l_C a ched算法会更新节点内所有缓存中的数据的状态 、计算出其使用 C a che _h it = ( )1 Sum _ requ res t 概率 、然后进行排序 , 这样可以得到缓存中使用概率最小的数 实现了 R /W GCC 的节点的缓存命中率为 :据 , 它的概率值为 p _m in. 然后搜索读写组成员表看是否有某 L oca l_C a ched + R ea dG roup +W r iteG roup个读写组内的成员其缓存中的数据的使用概率小于 p _m in 并 ( )C a che _h it = 2 Sum _ requ res t 且其体积大于或等于要被缓存的数据 . 如果有就把这个数据 R eadG roup 为能从 只 读 组 中 获 取 的 缓 存 的 数 目 , W rite2 发送给找到的读写组内成员 , 并在对方的缓存中进行缓存替G roup 为能 从 读 写 组 中 获 取 的 缓 存 的 数 目 , R eadG roup + 换 , 否则就在本地的缓存中进行缓存替换 .( ) ( ) W riteG roup > = 0, 所以公式 2 的值要比公式 1 的大 . 最坏 4. 3 缓存收到本节点应用程序的数据请求时( ) 情况下 readG roup + W riteG roup 的 值 为 0, 这 时 2 的 值 与 当一个节点收到从应用程序发来的数据请求时 , 它首先 ( )1的值相等 . 查找它自身的缓存中是否有所请求的数据 , 如果有就直接从 缓存中读取 , 如果没有就向只读组和读写组内的成员发送缓 5 仿真分析 存数据请求消息并 设置一个 tim eou t. 在 tim eou t过后如果还 5. 1 仿真环境 没有收到只读组或读写组内的成员对此缓存数据请求的响应 为了证明 R /W GCC 的 可 行 性 和 对 数 据 性 能 的 提 高 , 参 消息就说明组内没有成员缓存这个数据 , 它就向数据源或数 考了文献 [ 12 ]的仿真方法 , 对 R /W GCC 进行了仿真 . 考虑到 据中心发送数据请求 . 如果收到了只读组或读写组内的成员 仿真实现的简便性和仿真的有效性 , 本仿真实验分为两部分 . 对此请求的响应消息 , 就向第一个发来响应的邻居结点发送 第一部分使用 O p ne t为仿真工具 , 仿真无线网络环境和在无 对此响应的确认消息并准备接受数据 . 线网络环境下分组协议的运行 . 这部分仿真产生一个文件 , 它 4. 4 性能分析 记录了在仿真过程中节点的分组情况 . 第二部分使用由 C #代 R /W GCC 带来的好处是 : 第一能充分利用组内空闲的缓 码编写的仿真工具来模拟缓存的替换算法和缓存协作管理操 存资源 , 把尽可能多的数据放到缓存中以提高整体的缓存命 作的实现 , 它使用由第一部分仿真产生的节点的分组情况构中率 ; 第二把组内的缓存资源统一起来管理 , 一段时间后组内 建网络中的节点和和它们的只读组和读写组的内容 , 并在此 各个 Pee r节点的缓存中都会保存使用的概率较高的数据 , 平 基础之上实现缓存算法 、缓存协作管理和一个随机数据产生 衡了各个节点的缓存使用情况 . 器 . 随机数据产生器用来模拟应用程序 , 它向节点发出请求 4. 4. 1 平衡各个节点缓存的使用 数据 . m 为 m 的读写组成员 , m 对数据的需求比较活跃而 m j i i j 仿真实验中在 1500m ×1000m 的矩形区域里随机放置了对数据的需求比较少 . 这样一段时间以后 , m 缓存中保存数 i ( 30个移动 节 点 , 节 点 的 移 动 模 式 符 合 随 机 停 靠 点 random 据的都是使用概率较大的数据 , 而 m 的缓存中保存的数据只 j )w ayp o in t模型 , 节点在进行再次移动之前停留 100 s, 节点的 有一部分是使用的概率较大的数据 . 这时如果按照传统的方 移动速度为 0 ,10m / s, 每个节点信道的带宽为 2M bp s, 无线式 m 的缓存会由于频繁的缓存替换而降低性能 , 而 m 的缓 i j 传输距离为 300m. 各节点产生数据请求的时间间隔服从参数 存却没有被充分的利用起来 . 按照本文提出的新的方式来处 为 5的指数分 布 , 每 个 节 点 对 数 据 项 的 访 问 服 从 参 数 为 1. 理 , 当 m 需要进行缓存替换的时候它会把要缓存的数据发送 i 001的 Z ip f分布 , 节点的缓存替换算法采用 L RU.给 m , 并由 m 来进行缓存替换 . 这样一段时间以后 m 和 m j j i j 仿真实验过程中每过一段时间对网络中每个节点的缓存 的缓存中都会保存使用概率较大的数据 , 从而提高缓存的性 命中率进行计算和记录 . 能和利用率 . 5. 2 仿真结果分析 4. 4. 2 提高整体的缓存命中率 图 5 不同缓存容量下 图 3 缓存容量为能存放 10时 ,图 4 缓存容量为能存放 30时 , 节点的平均缓存命中率 某一节点的 C ache H it某一节点的 C ache H itF ig. 5 The ave rage C ache h it F ig. 3 The cache h it fo r cache s ize is 10 F ig. 4 The cache h it fo r cache s ize is 30 fo r each cache s ize 由图 3、图 4 可以看出 , 在开始阶段实现了 R /W GCC 的节点和没有实现 R /W GCC 的节点 的缓存命中 率 差 别 不 大 , ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved. 707 4期贾 磊 等 : P2P网络缓存协作的研究 M on trea l, C anada, 2004, 179 2191. 这是因为邻居结点还没有缓存到足够的内容 , 无法为本节点 [ 5 ] C h i2Y in C how , H ong V a L eong, A lv in T S chan. D is tribu ted ( ) 提供缓存数 据 , 相 当 于 公 式 2 中 readG roup + W riteG roup g roup 2based coop e ra tive cach ing in a m ob ile b roadcas t env ironm en t 的值为 0. 而过了一段时间以后 , 网络上各个节点的缓存中都 [ J ]. IEEE J ou rna l on S e lec ted A reas in C omm un ica tions, J anuna2 保存了足够多的缓存数据 , 这时邻居结点就可以为本节点提 ( ) ry 2007, 25 1 : 97 2106. ( )供缓存数据 , 这就相当于公式 2 中 readG roup + W riteG roup [ 6 ] C h i2Y in C how , H ong V a L eong , e t a l. C ache s igna tu res fo r p ee r2 的值大于 0. 这时实现了 R /W GCC 的节点的缓存命中率就自 to 2p ee r coop e ra tive cach ing in m ob ile env ironm en ts [ C ] In the 18 th 然比没有实现 R /W G CC 的节点的缓存命中率高 .In t′1 C onf on A dvanced Info rm a tion N e tw o rk ing and A pp lica tion () A INA ′04 , Fukuoka, J ap an, 2004. 由图 5可以看出随着缓存容量的提升 , 实现了 R /W GCC [ 7 ] S hen H ua2p ing, M a ry S uch itha J osep h, M ohan Kum a r, e t a l. PR e2 的节点的缓存命中率 稳定提升 , 没有实 现 R /W GCC 的 节 点 C inC t: a schem e fo r coop e ra tive cach ing in m ob ile p ee r2to2p ee r 的缓存命中率提升缓慢 , 而且在缓存容量为 40、50 的时候缓 sys tem s [ C ]. In the 19 th IEEE In t′l Pa re lle l and D is tribu ted P ro2 存命中率几乎没有提升 . ) ( cess ing S ym p os ium IPD PS ′05 , D enve r, U SA , 2005. [ 8 ] H a ra T. C oop e ra tive cach ing by m ob ile c lien ts in p ush 2based info r2 6 总 结 m a tion sys tem s [ C ]. In P roceed ings of the 11 th In te rna tiona l C on2 ( ) fe rence on Info rm a tion and Know ledge M anagem en t C IKM , N o2 本文讨论了现有的缓存协作方案 , 并在此基础之上提出 vem be r 2002, 186 2193. 了一种新的缓存协作方案 R /W GCC , 在 R /W G CC 的节点分 [ 9 ] Y in L , C ao G. S upp o rting coop e ra tive cach ing in ad hoc ne tw o rks 组算法中 , 根据 P2 P网络中的节点不稳定的特点区分节点的 [ C ]. In P roceed ings of the 23 rd A nnua l J o in t C onfe rence of the 不同状态 , 把邻居结点分为只读组和读写组 . 在 R /W GCC 的 ( ) IEEE C om p u te r and C omm un ica tions S oc ie ties IN FO COM , 缓存协作管理协议使用缓存替换算法中产生的信息 , 管理组 M a rch, 2004. 内的缓存资源 , 并把同在读写组内的节点的缓存资源统一起 [ 10 ] N a ro ttam C hand, J osh i R C , M ano j M is ra. Eff ic ien t coop e ra tive 来管理 , 平衡各个节点的缓存利用率 , 提高整体的缓存性能 . cach ing in A d H oc ne tw o rks [ C ]. In C omm un ica tion S ys tem S of t2 R /W GCC 中一个节点利用邻居结点的缓存来进行缓存协作 , w a re and M idd lew a re, 2006. 但是如何选用一个更好的缓存替换算法来为 R /W GCC 提供 [ 11 ] Yu D u, S andeep K S. G up ta COO P 2A coop e ra tive cach ing se rv2 更有效的信息和如何在 P2 P 网络中获取性 能比较好的邻居 ice in M AN ETs [ C ]. In P roceed ings of the J o in t In te rna tiona l 结点是有待解决的问题 . C onfe rence on A u tonom ic and A u tonom ous S ys tem s and In te rna2 ) ( tiona l C onfe rence on N e tw o rk ing and S e rv ice ICA S / ICN S 2005 , Referen ce s: 2005. [ 1 ] Zhao Zh i2feng, Zheng S hao2ren. A d hoc ne tw o rk [ J ]. 2 C h ina N ew [ 12 ] N iu X in2zheng, Q in Ke, Zhou M ing 2tian, e t a l. A coop e ra tive cac2 ( ) E lecomm un ica tions, 2002, 4 9 : 1 25. h ing op tim ized p o licy of m ob ile p ee r2to 2p ee r ne tw o rk [ J ]. J ou rna l [ 2 ] M ichae l D D ah lin, R ando lp h Y W ang, Thom as E. A nde rson coop 2 ( ) of C om p u te r R esea rch and D eve lopm en t, 2008, 45 4 : 656 2665. e ra tive cach ing: us ing rem o te c lien t m em o ry to im p rove f ile sys tem [ 13 ] L akshm ish R am asw am y, L ing L iu. A new docum en t p lacem en t p e rfo rm ance [ J ]. P roc. F irs t S ym p os ium on O p e ra ting S ys tem s schem e fo r coop e ra tive cach ing on in te rne t[ C ]. In P roceed ings of D es ign and Im p lem en ta tion, 1994, 11: 267 2280. the 22 nd In te rna tiona l C onfe rence on D is tribu ted C om p u ting S ys2 [ 3 ] C h i2Y in C how , H ong V a L eong , A lv in C han. Pee r2to 2p ee r coop 2 ) ( tem s ICD CS ′02 , 2002, 1 29. e ra tive cach ing in m ob ile env ironm en ts [ C ]. In the 24 th In t′1 C onf on D is tribu ted C om p u ting S ys tem s W o rkshop s ( ′ ICD CSW 附中文参考文献 : ) 04 , H ach io ji, J ap an, 2004. [ 1 ] 赵志峰 , 郑少仁. A d hoc 网络 [ J ]. 中国数据通信 , 2002, 9: 1 25.2based co2 G roup 4 ] C h i2Y in C how , H ong V a L eong, A lv in T S chan. [ [ 12 ] 牛新征 , 秦 科 , 周明天 , 等. 移动 P2 P 网络的协作缓存优化策 op e ra tive cache m anagem en t fo r m ob ile c lien ts in a m ob ile env iron2 ( ) 略 [ J ]. 计算机研究与发展 , 2008, 45 4 : 656 2665. ) ( m en t[ C ]. In the 2004 In t′l C onf on Pa ra lle l P rocess ing IC PP′04, ? 1994-2013 China Academic Journal Electronic Publishing House. All rights reserved.