前切换：P2P 共享文件备份技术研究

郑晓健，李 彤

（1.昆明理工大学津桥学院电气与信息工程学院，云南昆明 650106；2.云南农业大学大数据学院，云南昆明 650201）

0 引言

让用户能够持续有效地共享网络资源是P2P 网络研究重点，然而在非结构化P2P 网络中，由于提供共享文件资源的节点频繁而自由地加入和退出网络，对系统的共享文件服务质量产生影响，尤其是节点退出网络可能会减少网络中的共享资源量，造成资源需求节点查询不到共享文件资源情况，降低了系统查询成功率，也影响到系统可用性［1］。有研究提出采用文件备份技术，将共享文件资源的多个备份分布到网络中，以形成一定程度的有效冗余［2］，通过提高文件备份在网络节点中的占有率来改善文件查询成功率［3-7］，同时提高系统可用性。

通常P2P 架构的文件共享系统采用被动式方法实现文件备份［8-10］，在节点加入网络时就选择合适的备份节点并进行文件备份。如果备份节点先于主节点退出网络，还应该寻找其它节点作为备份节点。为使共享文件在网络中持续存在，设置系统服务节点监测网络中节点的在线状况。各节点定期向系统服务节点发送心跳信号通报在线状态，系统服务节点在规定的心跳周期时间内未接收到节点的心跳信号即可断定该节点已经退出网络。系统服务节点会将主节点的服务切换到备份节点，让备份节点接替其服务成为新的主节点，而后再选择新的备份节点。

系统服务节点按照设定的监测周期，在每个监测周期末期通过检查各共享文件节点是否存在超期未发送心跳信号现象来发现节点的退出工况。从节点退出到系统服务节点发现节点退出这段时间存在一段检索服务盲区。如果节点退出发生在系统服务节点监测周期开始阶段，要经过几乎整个监测周期直到监测周期末才会发现节点离线，再加上节点切换所耗时间，盲区时间甚至会超过一个监测周期。在此期间网络周期节点对退出节点文件的请求都会失败，原因是系统服务节点返回的节点检索信息为已离线节点的连接信息。本文将这种在被动式系统中存在的检索服务暂时性失败或检索时间延长现象称为“颠簸问题”（Bumpy Problem）。实验显示，颠簸事件发生的几率较低，所以未引起人们重视。

本文对颠簸问题进行研究，提出一种更加简便实用的改进方法，即前切换方法（PreSwitching Mechanism，PSM）。通过对混合型P2P 架构的共享文件系统网络中节点的停留时间预测节点的动态特征，对在线节点提前进行主备份节点切换，切换完成后备份节点可以接替主节点向网络提供服务。为了降低节点切换频度，在备份节点选择可能会有更长存留时间的节点，以有效减少系统颠簸发生，减少资源消耗。

1 相关工作

采用备份技术提高共享文件的占有率是有效提高文件查询成功率［11-12］和资源可用性的重要方法。在非结构化P2P 网络环境中，文献［1］采用主动策略搜索识别稀有共享文件，在搜索过程中获取共享文件的局部需求信息，然后按照用户的需求信息备份共享文件，有针对性地提高文件在网络中的流行度，从而提高稀有资源查询的点击率和可用性，但是获取共享文件资源的整体流行度不容易；文献［2］提出一种主动复制资源技术，用随机漫步的方式对节点上的共享资源进行自搜索，用探测函数确定资源的稀有性，各节点用保存资源的需求阈值确定是否对资源进行搜索和复制，该方式有效降低了资源探测和复制的额外网络开销；文献［3］根据待选节点的存储能力及与主节点的物理距离作为选择节点条件，将备份文件布置到存储空间充足和物理位置更近的节点上，使维护消耗更低，检索成功率得到改善；文献［4］将备份文件保存到能够长时间存留于网络的节点上，提高系统在动态变化时的适应性。还有研究将文件备份布置到以往成功检索所形成的路径上，即放在检索需求点和目标文件节点之间，以提高资源在网络中的流行度，降低网络资源消耗。文献［5］提出采用基于位置信息和流行度的备份资源管理算法PLAR，利用混合式服务器选择策略以及远程增强策略，使资源下载平均速率明显提高，有效提高共享速度并减少带宽消耗；文献［6］提出一种动态备份文件资源分布方法，即按所设计的备份文件目录和信息的获取方法获得资源的所有备份信息，并对访问频率高和平均响应时间长的资源进行备份，提供用户访问特征和节点的实时带宽等信息，计算存放备份的节点，使备份的分布能够适应访问请求和网络带宽的动态变化；文献［7］提出将备份文件部署到网络的骨干节点或骨干链路上，提高检索成功率，但是识别这些特殊路径开销较大。

以上备份方法主要采用被动式方法备份文件，重点解决的是文件检索成功率，这些方法确实能够改善系统检索性能并在一定程度上提高系统可用性，但由于P2P 网络的动态性，主备份节点都可能退出系统，使花费大量时间布置的备份文件随节点的退出而减少，造成检索失败，所以采用持续备份技术机制很有必要。

2 检索文件时的颠簸问题

2.1 场景描述

以下将P2P 网络中自主产生和提供共享文件的节点称为主节点，存放主节点的备份文件节点称为备份节点，对主节点提出资源请求的节点称为需求节点。主节点和备份节点在资源服务方面形成互补和相互依存关系。为了快速方便地搜寻到主节点或备份节点，在混合型P2P 网络中，系统服务节点存储各主节点以及对应的备份节点网络连接信息和共享文件目录信息，并向所有资源需求节点提供共享文件检索服务。资源需求节点从系统服务节点检索到主节点的网络连接信息和共享文件信息后，就可向主节点发出文件请求消息，再通过文件交换，资源需求节点就可获得文件资源。系统服务节点还负责在主节点退出网络后刷新节点连接信息，使主节点提供的服务切换到备份节点上。

在混合型P2P 网络中，一些网络事件会导致节点的状态发生变化，呈现为加入、在线、刷新、颠簸和离线5 种状态，形成节点的生命周期。

（1）加入状态。当节点进入网络时，先向系统服务节点发送加入网络请求，在等待对方回复的这段时间节点处于加入状态。此时系统将节点的连接信息和共享文件信息记录下来，准备为其它资源需求节点提供检索服务。

（2）在线状态。节点收到系统服务节点的回复消息后进入在线状态。

（3）刷新状态。在线状态下的主节点和备份节点均可能转变为刷新状态。如果本节点是主节点，当它共享的文件内容发生变化时须通知系统服务节点和备份节点，刷新文件信息和内容，以便保持主节点和备份节点文件一致；如果节点是备份节点，在收到主节点发送过来的刷新消息后即开始与主节点交换备份文件内容，以上两种情况下节点都处于刷新状态。

（4）颠簸状态。在线状态下的需求节点向系统服务节点发出检索共享文件消息，系统服务节点收到消息后查询共享文件，向需求节点回复提供共享文件的主节点连接信息和相关信息。假设主节点在此前已经退出网络，离线时又没有通知系统服务节点，而系统服务节点的监测周期还未结束就不能发现该主节点已经退出，所以它回复的依旧是主节点退出前的信息，按此状态去连接主节点将失败，这时节点处于颠簸状态。

（5）离线状态。即节点退出网络时的状态。P2P 节点退出和加入网络是自由的，加入和退出网络时是否通知系统服务节点不确定。

5 种节点状态相互变换过程如图1 所示。

Fig.1 Node lifetime process图1 节点生命期过程

P2P 网络中节点具有动态性［13-14］，节点的加入和退出对网络共享文件资源分布及数量状况产生明显影响，从而对网络中相关资源的服务产生影响。因此，P2P 网络是一个资源动态变化的网络。

2.2 问题定义

主节点退出网络时，网络中需求节点对主节点的共享文件请求会失败。随着系统将主节点服务转移到备份节点上，之前的服务将恢复并延续。本文通过对颠簸、后切换、前切换等概念和性质的讨论得出前切换策略。

定义1（颠簸）将从主节点退出网络到系统完成主节点至备份节点的切换这一时段内，资源需求节点对主节点的服务请求出现暂时性失败的现象称为服务颠簸或颠簸。

定义2（后切换）将系统服务节点发现主节点退出后再安排主节点服务切换到备份节点的切换方法称为被动式切换或后切换。

定义3（前切换）将节点未发生退出事件前就进行主节点到备份节点的切换方法称为主动式切换或前切换。

2.3 颠簸事件性质

在P2P 网络中，节点退出和节点被检索都是随机发生的，所以颠簸的发生也具有随机性，产生颠簸的时间是连续型随机变量。下面从备份过程分析颠簸产生的原因和概率相关因素。

引理1主节点退出和需求节点对主节点共享文件的检索是相互独立事件。

定理1从主节点退出网络到系统服务节点发现主节点退出，再到启动并完成节点的切换，这段时间内对节点文件的检索和访问会失败。

证明：设∀a∈Node，Node 为网络节点集合，时间段(0,tq]为节点a 两次心跳之间的时间间隔，其中tq＞0，tq是节点的心跳周期。

（1）若t0∈(0,tq]时节点a 退出，那么系统服务节点在[t0,tq]不会接收到节点a 的心跳信号，因而(0,tq]期间不能断定节点是否已经退出；tq时刻之后，系统服务节点将可以推断节点a 已经退出网络。

（2）在(tq,th],tq＜th时段，系统服务节点将节点a 的服务切换到备份节点。

（3）若其他资源需求节点检索节点a 文件的事件在(t0,th]时间内发生，那么由（1）可知系统服务节点在[t0,tq]期间还没有发现节点a 退出，所以提供的还是节点a 的检索信息。由（2）可知系统服务节点在(tq,th]时间内尽管已经发现节点退出，但还没有完成节点a 到备份节点的切换，所以不能提供节点a 的备份节点正确信息，因此在[t0,th]时段内，资源需求节点对节点a 文件的检索将失败。

本文将时间段[t0,tq]称为退出节点发现期，(tq,th]时间段称为节点切换期。

定理2当节点退出网络时，检索该节点文件失败的概率只与节点退出的概率密度函数以及从节点退出到完成节点切换的时间长短有关。

证明：设∀a∈Node，Node 为网络节点集合，节点a 退出网络的时间为连续型随机变量Q，且Q 在(t1,t2),t1＜t2上的概率密度函数为（fq）。这里以节点退出网络为前提条件，所以P（Q）＞0，∃b∈Node，节点b 向节点a 发送检索文件消息，检索时间为连续型随机变量R，R 在(t1,t2)上的概率密度函数为h（r），t1＜q＜t2，t1＜r＜t2，同时∀t∈(t1,t2)，且(t,t+ε)⊆(t1,t2)，其中t 是节点b 检索节点a 的时间，ε=th-t，th是节点切换结束的时间，则节点在(t,t+ε)期间节点a 退出网络的概率为：

在（t，t+ε）期间，网络中节点b 检索节点a 的文件概率为：

在（t，t+ε）期间，当节点a 退出网络时，节点b 检索节点a 的文件概率为：

在式（3）中，由引理1 知R 和Q 相互独立，即：

而由定理1，（t，t+ε）时间段内如果发生对节点a 的检索事件则检索失败。由式（4）可知检索失败的概率等于检索事件发生的概率。由式（2）可知，从节点退出网络到节点切换完成期间，检索节点a 中文件的概率只与其概率密度函数、发现节点退出和切换所用的时间有关。

3 前切换策略

通过对颠簸问题的分析和实验验证，本文提出一种新的主节点和备份节点切换方法，即前切换算法PSM。在系统服务节点控制下，从在线节点中预测即将退出的节点，提前进行节点切换，由备份节点继续提供服务。

有些方法可保持检索服务成功率，但是要付出一定代价。如系统服务节点回应资源需求节点检索时，同时向其提供主节点和备份节点的网络连接信息。资源需求节点对主节点和备份节点同时发起资源请求，收到它们反馈的检索结果后进行仲裁，再选择利用，或者采用一些无需检索信息支持的搜索方法，如洪泛、随机漫步等搜索方式。这些方法带来的问题是产生大量的网络带宽消耗或更长的检索时间［15］。

3.1 前切换性质

由引理1 可知节点退出事件和对节点共享文件的检索事件独立，但不能保证它们的交事件为空，即存在节点退出事件和对节点共享文件的检索事件同时发生的可能性。尽管前切换算法也有产生颠簸的风险，但是前切换与后切换产生颠簸的概率呈现下面性质。

定理3节点前切换时发生颠簸的概率小于等于后切换时发生颠簸的概率。

证明：前切换算法的颠簸来自于节点切换期(tq,th]，即在切换过程中如果遇到节点退出将产生颠簸。后切换发生颠簸的时段包括退出节点发现期和节点切换期，即[t0,th]，而(tq,th]⊆[t0,th]，且(tq,th]∩[t0,th]=∅，由概率的有限可加性得：

式（5）中P{t0＜R＜tq}≥0，则有：

即前切换遇到颠簸概率小于等于后切换。

3.2 前切换机制

前切换需完成两个阶段任务：

（1）第一阶段完成共享文件的备份和一致性维护。①共享文件备份。节点加入和退出网络要由系统服务节点按照备份节点选择算法寻找合适的备份节点，记录主备份节点的连接信息和共享文件信息，然后向主节点和备份节点发送消息，将主节点文件发送到备份节点，使得共享文件在2 个或以上节点中存在；②共享文件一致性维护。当主节点的共享文件发生变化时，通过系统服务节点的备份节点连接信息向备份节点发送消息，刷新备份节点文件内容，以保持主节点和备份节点文件的一致性。

（2）第二阶段进行主节点和备份节点的前切换。系统服务节点预测即将退出网络主节点，在它退出前，通过更新系统服务节点信息表将主节点转换为备份节点，以实现节点切换。切换完成后，所有对主节点的共享文件检索将提供备份节点连接信息，需求节点可继续访问共享文件。

在切换中主节点与备份节点间的共享文件交换需要消耗网络带宽及备份节点存储的资源，频繁切换会增大资源消耗，甚至丢失备份文件［8-10］。根据文献［4］的研究，节点存留于网络的时间对于系统可用性有影响，即节点存留于网络的时间长度与保存在节点上的文件可用性成正比。通过统计设定在线节点集合的平均存留时间作为衡量指标，找到存留时间更长的节点使节点切换延后。

设在系统服务节点各监测周期∑t时段内，∀ai∈Node，i=1，2，…，n，Node为有n 个网络节点的集合。

定义4（节点存留时间）时间∆t内，节点ai在网络中的存留时间为∆ti=tie-tis，其中tis为ai加入网络的时间，tie为ai退出网络的时间。

定义5（节点平均存留时间）时间∆t内，网络节点的平均存留时间为：

其中,∆ti为ai的节点存留时间，fi是节点存留时间为∆ti的节点数。

定义6（节点在线时间）时刻t网络中在线节点ai的在线时间为∆tiL=t-tis，其中tis为节点ai加入网络的时间。

定义7（节点平均在线时间）设t时刻网络在线节点平均在线时间为：

其中，∆tiL为节点ai的在线时间，fi是在线时间为∆tiL的节点数。

系统服务节点为了记录节点和共享文件信息，设置节点信息表NIT、备份节点表CIT、共享文件信息表SIT。NIT的每个记录为＜ai，s，t1，t2＞，其中ai为节点号，s 为状态，加入时间为t1，当前在线时间为t2。CIT的每个记录为＜am，ab＞，其中am为主节点号，ab为备份节点号，SIT的每个记录为＜ID，file，am，t＞，其中ID为记录编号，file为共享文件名，am为主节点号，t为更新时间。

共享文件备份和一致性维护［14-15］时，选择备份节点以存留时间超过网络的平均存留时间为条件。在线节点的存留时间由系统服务节点的存留时间算法实现。当系统服务节点接收到节点的心跳信号时会更新节点信息表NIT的信息，然后按照定义5 计算并刷新网络的节点平均存留时间E，以提供给备份节点选择算法使用。

算法1 备份节点选择算法

输入：节点信息表NIT，T时间段内网络节点平均存留时间E

输出：选择出的备份节点

步骤1：按条件ai.s=0 且ai.tie-ai.tis＞E查询节点信息表NIT，得节点记录集NTiL：

如果NTiL≠ ∅，则执行步骤2；

如果NTiL=∅，则amax=∅，执行步骤6；

步骤2：移动到NTiL的第一个记录ak∈NTiL；

步骤3：amax=ak；

步骤4：移动到NTiL的下一个记录ak∈NTiL；

步骤5：如果amax.tie-amax.tis＜ak.tie-ak.tis，则amax=ak，执行步骤4；

否则执行步骤6；

步骤6：返回amax。

系统服务节点心跳周期结束时执行前切换算法。

算法2 前切换算法

输入：节点信息表NIT，节点平均在线时间EL

输出：选出的节点切换到备份节点

步骤1：按条件ai.s=1 且t-ai.tiL＞EL查询节点信息表NIT，得节点记录集NITs：

如果NITs≠ ∅则执行步骤2；

如果NITs=∅则执行步骤8；

步骤2：移动到NITs的第一个记录aj∈NITs；

步骤3：更新SIT 的所有记录rec∈SIT,rec.am=aj,aj∈NITs，为rec.am=aj；

步骤4：调用备份节点选择算法，选择备份节点an；

如果an=∅，则执行步骤7；

如果an≠ ∅，则执行步骤5；

步骤5：更新CIT 的记录＜am，ab＞，am=aj,ab=an；

步骤6：发送消息给节点am，通知它可以退出网络；

步骤7：移动到NITs的下一个记录：如果NITs≠ ∅则执行步骤3；

如果NITs=∅则执行步骤8；

步骤8：返回切换节点数量。

4 实验与结果分析

4.1 实验设置

先验证不同网络规模下［16］节点退出网络时检索该节点文件失败的概率与节点退出的概率，用后切换作对比，对前切换算法进行性能测试，以检验本文提出的前切换算法降低颠簸事件的有效性。系统仿真环境为：操作系统Windows VistaTHHome Basic，处理器Intel（R）Core（TH）2 Duo CPU P8600 @2.40GHz 2.40GHz，内存2.0GB。测试平台采用VB6.0 编程实现。

4.2 颠簸事件性质验证

为清晰呈现发生颠簸事件情况，测试参数设置如下：节点加入和退出网络事件的频度为1 节点/s，退出节点随机产生；随机挑选在线节点发送检索请求事件，检索事件产生频度为10 次/s；系统服务节点的心跳周期设置为0.5s；所有节点规模的测试时间长度均为1 800s。模拟测试节点数量规模分别为100 个、500 个、1 000 个、2 000 个；颠簸事件测试结果如图2 所示。

测试结果证实了定理2，即在不同网络规模情况下产生颠簸的概率只与节点退出的概率密度函数以及从节点退出到完成节点切换的时间长短有关。当网络节点规模较小而节点退出切换到备份节点完成时间较长时，发生颠簸几率较大，颠簸发生次数增长较快。当网络中节点规模逐渐增大时，节点退出到切换到备份节点完成时间即便较长，颠簸事件发生的几率仍在增长，但增长速度会比较平缓。颠簸事件发生几率与检索事件发生率直接相关。

Fig.2 Turbulence event test results图2 颠簸事件测试结果

4.3 前切换算法有效性验证

为评价减少颠簸事件时前切换算法的有效性，将它与后切换进行对比。设置测试参数如下：节点加入和退出网络事件的频度为1 节点/s，退出节点随机产生；随机选择在线节点发送检索资源请求，检索事件产生频度为10 次/s；系统服务节点的心跳周期和节点切换处理周期设为1s，各种节点规模测试时间长度均设为1 800s。模拟测试节点数量分别为100 个、500 个、1 000 个、1 500 个、2 000 个；将前切换和后切换发生颠簸事件切换处理时间为1、3 和5s 时测试结果进行比较，如图3、图4、图5 所示。

Fig.3 Comparison of pre-switching Switch before and after switching turbulence event（1 second switching time）图3 前切换与后切换颠簸事件比较（1s 切换时间）

Fig.4 Comparison of pre-switching and after switching turbulence event（3 seconds switching time）图4 前切换与后切换颠簸事件比较（3s 切换时间）

从图中可以看出，前切换测试结果比较稳定，后切换方法存在明显的颠簸现象，随着节点数量的增加颠簸事件发生有所减少，但是发生率仍然很高。前切换方法颠簸事件发生率比较低且保持稳定状态，主要原因在于前切换排除了节点退出发现期的颠簸事件问题。实验证实了定理3的结果，即在不同网络规模下，节点前切换时发生颠簸的概率明显小于等于后切换，而且随着网络规模的增大，颠簸事件的发生几率也在下降。所以，前切换在避免颠簸事件上效果较好。

Fig.5 Comparison of pre-switching and after switching turbulence event（5 seconds switching time）图5 前切换与后切换颠簸事件比较（5s 切换时间）

5 结语

为提高非结构P2P 网络［17-18］中共享文件系统可用性，本文从共享文件备份技术着手，对主、备份节点的切换技术进行了研究。发现影响系统可用性［19-20］的主要因素是颠簸事件的发生，而颠簸产生在系统节点退出时段和切换处理时段。为了减少颠簸现象发生，提出一种基于主动切换策略的前切换方法，它比后切换方法减少了系统服务节点退出这一过程。实验结果证实前切换方法在降低颠簸事件发生方面明显优于后切换方法。后续将在网络节点退出的预测方法上进一步研究以提高预测准确性，从而进一步降低节点切换频度和资源消耗，提高系统可用性。