多路恢复数据流并行传输与控制方法.doc

第3期张冰等：多路恢复数据流并行传输与控制方法59多路恢复数据流并行传输与控制方法张冰1，卢正添2，李涛2（1. 国家计算机网络应急技术处理协调中心，北京 100029；2. 四川大学 计算机学院，四川 成都 610065）摘 要：为有效缩短灾难恢复时间，提出了一种多路恢复数据流并行传输与控制方法（MRPTC）。首先，待恢复服务器与多个备用服务器建立连接，将当前破损数据与原始的完好数据（备份数据）做差异比较，获得两者的差异数据，然后从各备用服务器处动态并行下载差异数据的不同部分，再在本地进行拼合，获得完整的数据，从而实现数据的快速恢复。该方法具有多点协同差异恢复、恢复速度快、带宽利用率高、传输网络要求低等优点。理论分析和实验结果表明，该方法是快速灾难恢复的一种有效的新途径。关键词：灾难恢复；多源恢复；差异恢复；并行传输中图分类号：TP309.3 文献标识码：A 文章编号：1000-436X(2009)03-0054-05Multi-channel recovery data flow paralleltransmission and control methodZHANG Bing1, LU Zheng-tian2, LI Tao2(1. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China;2. Computer School, Sichuan University, Chengdu 610065, China)Abstract: In order to shorten the time for disaster recovery, a multi-channel recovery data flow parallel transmission and control (MRPTC)method was presented. First, the connections between the server to be recovered and the several standby servers were established, the difference comparison between the current damaged data and the original intact data(the backup data) was completed, the differences were obtained. Then the different parts of the differences were dynamically downloaded from the standby servers in the parallel mode, these parts were united locally, the whole data was finally obtained, and the fast disaster recovery of the data was achieved. The theoretical analysis and the experiment results show that the proposed method has the features of multi-point collaborative difference recovery, high recovery speed, full bandwidth utilization, and low network requirement. Therefore, this method is a new good approach of fast disaster recovery.收稿日期：2008-11-12；修回日期：2009-01-05基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）；国家高技术发展计划（“863”计划）基金资助项目（2006AA01Z435）；国家自然科学基金资助项目（60873246）；国家信息安全计划（“242”计划）基金资助项目（2005A04）Foundation Items: The National Basic Research Program of China (973 Program) (2007CB311100); The National High Technology Research and Development Program of China (863 Program)(2006AA01Z435); The National Natural Science Foundation of China (60873246); The National Information Security Program of China (242 Program) (2005A04)Key words: disaster recovery; multi-source recovery; difference recovery; parallel transmission1 引言在“911事件”之后，信息系统的容灾抗毁建设受到人们的高度重视，相关容灾抗毁理论及其应用技术的研究已成为当前信息安全领域一个备受瞩目的研究热点1,2。在灾难发生后，如何尽快恢复数据、完成灾后重建是信息系统容灾抗毁研究领域中一个极为重要的问题。1999年，Tridgell提出了Rsync恢复算法3，利用滚动校验和等技术串行地寻找破损数据和备份数据的差异，然后进行单点差异恢复。2007年，文献4提出了一种基于逻辑卷的快速灾难恢复方法，通过跟踪并记录增量变化等手段，使用备用系统数据，快速恢复主系统数据。2007年，文献5提出了一种网络信息系统数据异地快速恢复方法，通过对备份端数据与恢复端数据进行差异比较，根据备份端数据对恢复端数据进行差异恢复，缩短灾难恢复时间。上述方法研究主要集中在“一对一”模式下，即利用一份备份数据进行灾难恢复6,7。因为只有一份备份数据，灾难恢复时可靠性较差。此外，在网络环境复杂、恢复数据量大的情况下，这类方法的效果较差。鉴于此，本文提出了一种多路恢复数据流并行传输与控制（MRPTC, multi-channel recovery data flow parallel transmission and control）方法，该方法具有以下优点：1）灾难恢复时，仅传输差异数据，减少了数据传输量，提高了传输效率；2）通过与多个备用服务器建立连接，从各备用服务器处并行下载数据的不同部分，再在本地进行拼合，获得完整的数据，汇聚了多条网络线路的带宽，同时提高了可靠性；3）根据多个备用服务器不同的传输速度情况，动态划分数据块，选择对应的服务器下载，充分利用了网络带宽，加快了传输速度；4）动态调整分配给各备用服务器的分块大小，让速度快的备用服务器分担速度慢的备用服务器的任务，使得各备用服务器可以根据自己的能力承担到相应比例的下载任务，合理分担了负载，也最大限度地利用了备用服务器能力；5）对传输网络要求低，无需专线，能够适应复杂的网络环境，如Internet。2 MRPTC方法2.1 术语定义为了便于讨论，这里先定义一些术语。定义1 源服务器和备用服务器：在容灾备份传输过程中，若将服务器P的数据备份到服务器S1、S2、S3，则服务器P处于“传输”的源头位置，称之为源服务器；服务器S1、S2、S3保存P的备份数据（亦称数据副本），称之为备用服务器。定义2 待恢复服务器：在灾难恢复过程中，若服务器P的数据遭到破坏，就需要用保存在服务器S1、S2、S3的备份数据对其进行恢复，将其还原为完好状态，此时称服务器P为待恢复服务器。2.2 模型基础及分析设待恢复服务器P的完好数据为D，大小为d，D在容灾系统中存在n个副本，分别存放在n个备用服务器上，数据D遭到破坏后变为E。在需要进行灾难恢复时，E与D之间可能存在相同的部分，2者的差异部分仅为F，即差异部分F大小为f，有(1)从式(1)可知，在进行灾难恢复时，仅传输F，可以减少数据传输量，提高传输效率，缩短灾难恢复时间。在并行传输模式下，待恢复服务器P同时打开n条连接，同时从备用服务器下载差异部分F，设P到Si的下载速度为，设到下载结束时，P从各个备用服务器下载的数据分别为，即可以求得P从Si处下载完Fi需要的时间ti(2)平均速度为式(2)中，为P与Si建立连接所需的时间。为P与Si关闭连接所需的时间。为每次数据请求的响应时间，即P向Si发送数据请求到开始接收到数据之间的时间。在这段时间中，数据连接处于空闲状态，带宽没有得到利用。qi为P从Si处下载Fi的数据需要发送的数据请求次数。在实际网络中，等于P到Si的RTT（round trip time），这个值和一样，无法被人为控制。而与P的性能有关，同样无法被人为控制。所以，为了尽量缩短ti，减少连接空闲时间，并行传输算法必须减少P向Si发送的数据请求次数，尽量不打断一个连续的传输过程。知道了每条连接下载完成的时间，可以求出P从n个备用服务器并行下载完差异数据F所需的时间TT (3)从式(3)可知，当时，T达到最小值，即当所有的连接同时结束下载时，总的下载时间最短。所以，并行传输算法优化传输时间的核心就在于合理分配从各备用服务器处下载的数据量，使传输数据量的比例接近或等于从各备用服务器平均传输速度的比例，达到同时完成下载的目的。2.3 算法流程在复杂网络环境中，要想在下载之初就精确预测各连接的传输速度是一件非常困难的事情，而且，各连接的传输速度在数据传输期间也可能时刻处于变化之中。因此，为了使传输数据量的比例接近或等于各连接的平均传输速度的比例，让各连接同时完成差异数据的传输，必须要尽可能细致地划分分配给各条连接的传输数据量。要达到这个目的，并行传输算法必须使用更小的数据分块，这又将带来数据请求次数的增加。为了解决这个矛盾，MRPTC方法并不预先确定固定的数据分块大小，而是先将数据平分，为每条连接分配相等大小的数据块进行并行传输，当速度快的连接先传输完自己的那部分数据后，再从比它慢的连接那里分担一部分数据的传输任务。这样，通过快慢协作，可以达到提高传输速度并减少数据请求次数的效果。下面详细描述MRPTC的算法流程。设完好数据D大小为d，在容灾系统中有n个副本，设待恢复服务器P上的数据D遭到破坏后变为E，P到每个备用服务器的下载速度为，速度处于动态变化中。P按照如下算法流程，同时打开n条连接从各备用服务器并行下载差异数据。1) P根据数据大小d，将破损数据E平均分为n块，即。2) 各备用服务器Si根据数据大小d，分别将数据副本D平均分为n块，即。3) P计算各块破损数据Ei的摘要值，其中H为摘要计算函数，如MD5、SHA-1等。4) 备用服务器Si只计算第i块数据副本Di的摘要值，。5) P与各备用服务器Si分别比较对应数据块的差异：若，则两端数据不一致，该块数据需要恢复，否则，转7）。6) 从备用服务器Si处下载Di。7) 在时刻t，当某条连接i完成自己的任务后，P选择一条连接，将其未完成的数据按照一定比例划分一部分，分给连接i继续下载。划分比例和分配步骤如下。计算各连接的下载速度vj，公式如下。，其中，Dj是到目前为止，连接j下载完成的总数据量，则为连接j的平均下载速度，是连接当前的下载速度。决定了平均速度在vj中所占的权重。vj的计算结果是对连接未来下载速度的一个大致预测。设连接j尚未完成的下载任务为。记速度比连接i慢的连接集合为M， 。若，计算M中各条连接完成目前剩下的下载任务量所需的时间tj，选择M中剩余时间最长的连接j：，有。将该连接剩下的任务量划分为2块、，重新分配给连接i、j，分配公式如下。，(4)若，设为所有速度比连接快的连接集合。选择中速度最慢的一条连接j，按照式(4)重新为连接i、j分配下载任务。8) 重新分配任务后，连接i、j分别根据、与破损数据E对应的数据块做差异比较，在数据不一致的情况下，才下载数据，否则不进行下载。9) 为避免数据分块过细，设置一个分块大小的阈值。如果一个连接j剩下任务量，则 如果有速度比自己慢的连接要求分担自己的任务，连接j拒绝这个要求。 如果有速度比自己快的连接k要求分担自己的任务，连接j放弃自己剩下的下载任务，交给比自己快的连接k下载。而连接k在下载数据之前，先进行对应数据块的差异比较，在数据不一致的情况下，才下载数据，否则不进行下载。10) 当各连接下载完毕，P重组获得的数据分块，得到完整数据。3 算法分析MRPTC方法在从各备用服务器处下载数据分块之前，将破损数据分块与对应的数据副本分块做差异比较，若2者是一致的，则不下载该数据副本分块，而只有在2者不一致的情况下，才进行下载，能够有效减少数据传输量，提高传输效率。MRPTC实现了数据分块大小的动态调整：在传输之初采用大的分块，随着传输的进行，分块逐渐变小，最大可能地解决了数据请求次数与传输任务分配精度之间的矛盾。MRPTC的动态分块方法也保证了每条连接尽可能地连续传输，不被打断。预先分配的一块大的传输任务不断被速度快的连接分担，任务量逐渐减少。在这种情况下，速度慢的连接通常不需要发送新的数据请求，只需要连续地传输自己的任务直到结束，这样可以有效地避免慢速连接的数据请求延迟带来的传输平均速度降低。而对于速度快的连接来说，则可以在不受影响的情况下连续传输完分给自己的第一块数据，然后在之后的每一次请求中都尽可能多地分担速度慢的连接的任务，传输的连续性得到了最大程度的满足，同时也大大减少了发送数据请求的次数。MRPTC也能根据连接之间的速度的比例，动态精确地调整传输任务，以充分利用带宽。如果一条连接在传输期间速度变化比较大，可能会造成原来的任务分配不合理，MRPTC可以通过分担别人的任务或者被别人分担来动态地调节任务分配比例，尽可能达到各连接同时完成传输任务的目的。MRPTC通过第2.3节中第9)步的操作，可以使得数据的最后一块始终由速度快的连接来传输，这就避免了可能出现的由慢连接传输最后的数据块引起的速度减慢，增加等待时间的弊端。4 实验结果及分析实验环境配置如表1所示，包括1台待恢复服务器，13台备用服务器。待恢复服务器网卡带宽为1Gbit/s，备用服务器网卡带宽为100Mbit/s。表1实验环境的基本配置待恢复服务器备用服务器处理器内存操作系统处理器内存操作系统Pentium D 2.80GHz512MBWindows Server 2003Celeron 3.33GHz512MBWindows Server 2003为了验证MRPTC方法的有效性和性能，通过实验测试单路、多路环境下的恢复数据流传输速度。实验结果如图1所示，恢复数据流的传输速度随路数的增加成线性增长趋势，最后达到待恢复服务器的网卡带宽值。该实验结果表明MRPTC方法充分利用了数据的多个副本，汇聚了多条网络线路的带宽，最大可能地加快了传输速度，取得了较好的效果。图1 单路、多路环境下的恢复数据流传输速度为进一步检验本方法的先进性，与国内外同类典型方法进行比较，如表2所示。本方法比Rsync具有多点协同差异恢复、高可靠性、高带宽利用率等优势，比FDRM具有多点协同差异恢复、高可靠性、高带宽利用率、传输网络要求低等优势。表2本方法与国内外同类典型方法的比较方法多点协同差异恢复可靠性带宽利用率传输网络要求Rsync3不支持较低较低低FDRM4不支持较低较低较高本方法支持高高低5 结束语本文提出了一种多路恢复数据流并行传输与控制（MRPTC）方法，通过与多个备用服务器建立连接，将当前破损数据与原始的完好数据（备份数据）做差异比较，获得2者的差异数据，然后从各备用服务器处动态并行下载差异数据的不同部分，再在本地进行拼合，获得完整的数据，从而实现数据的快速恢复。理论分析和实验结果表明该方法有效减少了数据传输量，提高了传输效率，充分利用了数据的多个副本，汇聚了多条网络线路的带宽，提高了可靠性，加快了传输速度，缩短了灾难恢复时间，是快速灾难恢复一种有效的新途径。参考文献：1沈昌祥, 张焕国, 冯登国等. 信息安全综述J. 中国科学(E辑: 信息科学), 2007, 37(2): 129-150.SHEN C X, ZHANG H G, FENG D G, et al. Survey of information securityJ. Science in China(Series E:Information Sciences), 2007, 37(2): 129-150. 2李涛, 刘晓洁, 曾金全等. 信息系统容灾抗毁原理与应用M. 北京: 人民邮电出版社, 2007. LI T, LIU X J, ZENG J Q, et al. Disaster Recovery Principles and Applications of Information SystemsM. Beijing: Posts & Telecommunications Press, 2007. 3TRIDGELL A. Efficient Algorithms for Sorting and SynchronizationD. Australia: The Australian National University, 1999.4WANG Y L, LI Z H, LIN W. A fast disaster recove