快速文件备份软件的设计和实现

胡平平，王晶杰

（北京信息科技大学 自动化学院，北京100192）

0 引 言

操作系统提供的文件复制功能虽然可以实现文件备份，但功能简单，使用时操作繁琐，尤其是备份分散在不同文件夹下的多个文件时，更是存在下述问题：①需逐个确认每一个文件是否复制，需要人为干预因此延长了备份时间，一旦选错还会导致新文件被旧文件覆盖的严重后果；②若选择全部复制，则不仅会导致新文件被旧文件覆盖的后果，且会复制很多没必要复制的文件，延长了备份时间；③对于文件夹的复制，只能选择全部覆盖或放弃，同样存在②中的问题。微软的免费同步软件SyncToy和Usov Lab的同步软件AllwaySync功能强大，用于文件备份时虽没有上述问题，但使用前都需要配置，过程繁琐，修改不方便，还需要在计算机中保存较大的配置文件 （大小和所备份的文件数量有关），每次使用时也需要多次操作才能完成备份。为解决上述问题，本文提出了快速文件备份的思想，并依此实现了快速备份软件。它只需一个简单且很小的文本配置文件，运行后无需人工干预，便可自动快速完成多个保存在不同位置的文件到多个目标的备份。

速度、安全性和可靠性是备份处理的重要指标。为了提高速度，文献 ［1－4］采用差异传输的方法，备份时只复制文件变化的部分，通过减少复制数据量提高备份速度，该方法非常适合于备份大型文件和远程备份，但处理复杂且需要保存差异文件，不适合小文件本地备份；文献 ［5－8］采用监控的方法，随时记录文件的改变情况，备份改动的文件，目的是为了数据安全或实时备份；文献 ［9］采用多路编码传输备份文件，主要特点是备份的可靠性，在部分数据丢失时，由编码数据和部分原数据可恢复丢失的数据；文献 ［10］以 “簇”为单位监控文件的变化，实现基于扇区重组的文件级快速备份和恢复；文献 ［11］用两级链表管理备份文件的信息，通过消除备份服务器上重复文件的方法节省存储空间。上述备份方法均不适合本文的情况。

本文提出的文件备份思想除了通过自动判断无需复制的文件、“单源多目的”复制和简化操作来实现快速备份外，还在备份处理的实现中采用高效的数据结构、分级存储和动态存储再分配等技术，不仅高效、快速地的实现了海量文件信息的存储，而且最大限度地降低了系统存储空间的使用量，进一步提高了处理速度。此外，通过充分使用操作系统内嵌的文件处理功能完成文件的复制操作，保证了文件备份的可靠性和安全性。

1 快速文件备份软件设计

快速文件备份的主要思想是自动判断所有要备份文件的复制必要性，自动跳过无需复制的相同文件，并支持多种备份方式以进一步提高备份速度。在处理实现上，通过使用高效数据结构和高效的动态存储策略，尽可能降低了系统内存的使用量，在保证复制文件数量不受限的实用性前提下，最大限度地提高了处理速度。

快速文件备份处理遵循以下原则：①文件名相同的文件为同一个文件；②修改时间晚的文件是新文件；③修改时间相同时，长度大的文件是新文件。

1.1 备份方式

快速备份处理由独立的备份任务构成，每个任务可以指定一个源文件夹 （或磁盘）和最多5个目标文件夹 （或磁盘），除了能够完成普通意义上的备份外，还可以通过命令行参数或配置文件支持多种备份方式，具体是：

普通备份：这是默认的备份方式，将指定源文件夹中指定类型的所有文件复制到指定的多个目标文件夹中，如果目标文件夹中存在该文件，则只复制更新的文件；否则在目标文件夹中生成该文件。

含文件夹备份：在普通备份方式的基础上，复制对象包含指定源文件夹中的所有子文件夹和这些文件夹中的所有文件。

确认备份：在普通备份方式的基础上，对要进行复制的文件提请用户确认。该功能是为了在用户不确定时，防止新文件覆盖更重要的旧文件而设，提高安全性。

测试备份：在普通备份方式的基础上，只显示要复制文件的信息，而不进行实际的复制操作。

指定日期备份：在普通备份方式的基础上，只复制指定日期以后修改的文件。时间选项的输入方式简单灵活，单字母O 表示日期是当天，可只输入日、日和月或日月年。

更新备份：在普通备份方式的基础上，只复制目标文件夹中已经存在的文件或文件夹的更新版本。

同步备份：在普通备份方式的基础上，将目标文件夹中指定类型的所有文件复制到源文件夹中。实际上是双向备份，即保证所有文件夹中的文件或文件夹都是最新的。

排除备份：在普通备份方式的基础上，将目标文件夹中有但源文件夹中没有的文件删除，即保证目标文件夹中的文件和源文件夹中的一致。

配置文件备份：通过指定的配置文件进行备份处理。配置文件是普通的文本文件，可以一次完成多个备份任务，每个备份任务可选不同的多种备份方式。

上面的各种备份方式中，除了同步备份和更新备份及排除备份不能共存外，其它备份方式均可以并存。如更新备份和排除备份选项同时有效时，备份完成后，目标文件夹中将只剩在源文件夹也存在的文件。

1.2 文件信息的数据结构

在快速文件备份软件中，由于文件内容的复制处理是调用系统函数完成的，软件运行时需要存储的只是文件和文件夹的信息。为了实现不限量文件备份和快速处理，仅存储备份处理必须的文件信息，以保证备份处理所需存储空间的最小化。

存储文件和文件夹信息的数据结构如下所示：

该结构占用20字节。

众所周知Windows操作系统中文件和文件夹名称字符串长度在1至255字节之间，VC 系统中也定义了值为256的常量＿MAX＿PATH 作为其最大存储长度，用该长度的字符串数组来存储文件或文件夹名是最简单且不会出错的处理方法。但作者对各类磁盘中文件和文件夹名称长度的统计表明，实际的文件名称平均长度在14至23字节之间，如果按上述方式存储，上面的每个结构都要增加252字节，平均浪费在241 至232 字节之间，占结构本身的82%至88%。这就造成存储空间的巨大浪费。在文件数量多时，甚至会使备份处理因存储空间不够而失败，严重影响了实用性。为此，上面两个结构中仅设置了文件和文件夹名称字符串指针，实际字符串内容则采用动态存储再分配策略，连续地存储在其它的动态空间中。这样可以极大地减少所需的存储空间。例如，某系统盘文件数量为60 851个，名称字符串总长度为907 274字节，平均长度14.9字节。若用通常的存储方式需要15 577 856 （60 851×256）字节，而本文的方法只用了476 个2KB 存储块，共计1 218 252（60 851×4＋2048×476），节省了92.2%的空间。

1.3 动态存储再分配方案

除了上面通过数据结构的设计减少存储空间的需求外，用分级存储和动态存储再分配策略，还可以进一步减少存储文件和文件夹信息的空间，且极大地提高动态存储分配的处理速度。

在备份软件处理之前，文件和文件夹的数量是未知的，因此必须用动态存储方式储放文件信息。但备份处理的过程又有其特殊性，即从第一个对象开始，依次为每一个对象申请空间，直到搜索完所有的对象为止，此过程不需要释放任何申请到的空间，所有申请的空间是在使用完后一次性全部释放。

系统的动态存储管理 （DMM）是为空间的可随意申请和释放而优化设计的，每申请一个空间，除了所申请的空间外，还需要额外的空间存放管理信息，且申请时为了最佳匹配，还要进行大量的存储空间搜索处理。以VC＋＋中malloc（）函数为例，DEBUG 版本 （以下简称D 版）下，如果要申请长度L 的空间，则所需的实际空间AL 为8＋（36＋L＋15）＆～15，每次内存分配的浪费空间AL－L 在44 （L%16＝12时）至59 （L%16＝13时）之间。类似地，RE LEASE版本 （以下简称R 版）下，AL 为8＋ （L＋15）＆～15，每次内存分配的浪费空间在8 （L%16＝0 时）至23 （L%16＝1时）之间。而申请长度L 在1至255之间的处理平均需执行的汇编语句：D 版2089 条，R 版1781 条（这些数据是对代码的分析和统计计算所得，由于篇幅所限，详细的分析过程省略，下文同）。可见，直接使用系统提供的动态空间申请函数为每一个文件和文件夹信息申请空间不仅浪费大，而且处理时间长。为此，本文设计了动态存储再分配方案来解决这个问题。

所谓动态存储再分配 （DMRA）方案是将零散的动态存储申请转换为集中申请，并利用简单的本地分配策略对已申请的存储空间进行有效的再分配。现以短数据连续动态存储为例加以说明。

图1是用malloc（）连续为N 个短数据单独申请存储空间的分布情况。其中P1至PN为申请到的N 个数据存储区域的指针，每个实箭头线表示对malloc （）函数的一次调用，得到的存储区域用粗线矩形表示，其阴影部分为DMM 占用的额外空间。

图1 为N 个短数据单独申请存储空间的分布

图2是用DMRA 方案为N 个短数据进行存储分配的分布情况。BP1至BPM为调用malloc（）函数得到的存储空间指针，虚箭头线表示本地分配策略为N 个数据进行的分配。

图2 DMRA 方法为N 个短数据申请存储空间的分布

从上图中可以看出，DMRA 方案具有更高的存储空间利用率和较少的malloc（）调用次数，而本地分配处理非常简单，因此DMRA 具有更快的速度。DMRA 仅需实现一个和malloc（）完全相同函数，其原型为：void＊DMRAalloc（size＿t size）。

DMRA 分两级管理存储空间，第一级是存储块指针（即上述BP1至BPM），它们被存储在一个线性动态指针数组中；第二级是对应的存储块，每个块的长度是固定的2 KB，为实际申请的存储空间。DMRAalloc（）函数被第一次调用时会为BPi申请一个初始长度的指针数组空间，并用malloc（）申请第一个存储块作为当前存储块BPcnt，然后返回其起始地址作为所申请的存储空间指针，当前分配位置为size。后续调用DMRAalloc（）时，如果BPcnt当前分配位置到块尾的空间大于size，则返回BPcnt的当前分配位置，当前分配位置后移size；否则用malloc（）申请一个新存储块作为BPcnt，并按前述方法再分配。如果存储块数量超过了其动态指针数组的长度，则用realloc（）延长该指针数组的长度，继续处理直到所有的对象都分配了空间。由于大部分情况下只需返回当前存储块的当前分配位置，因此DMRA 的本地分配处理仅需很少的指令，D 版为47条，R 版为14条。是直接调用malloc （）的近44 （2089／47）和127 （1781／14）倍。可见DMRA 有非常快的速度。

一般情况下，一个备份任务完成后，可以一次性地释放所有的存储块和动态指针空间，但本文的快速备份一次可能处理多个备份任务，因此可对上述DMRA 进行改进，在处理下一个备份任务完前，仅需记住已经申请的存储块数量M，将当前块设置为BP0，当前分配位置清零，便可继续使用DMRAalloc（）函数，只在需要使用新的存储块且存储块数量超过M 时，才申请新的存储块并递增M。改进的DMRA 在大多数情况下无需申请存储块，其本地分配处理D 版为61条指令，R 版为24条指令。

为了验证DMRA 在存储空间和处理速度方面的效果，作者专门编制了用DMRA 方法存储磁盘上所有文件和文件夹名称字符串的测试程序，表1是该程序对某计算机4个磁盘的实际测试结果。其中的空间比就是程序的实际数据，而速度比则是根据DMRA 实际的本地分配次数和调用malloc（）次数，按前面的代码量统计分析结果计算的。可以看出，D 版DMRA 使用的空间几乎是直接分配方法的1／4（25%至33.4%），R 版则是一半左右 （54%至63%）。速度方面，DMRA 在各种情况下都有较大的优势，D 版DMRA 的速度是直接分配方法的23至28倍，R 版则是更高的37至50倍。

表1 4个不同磁盘的实际测试数据

1.4 文件信息存储结构

快速备份软件需要存储的动态数据有3类：文件夹信息DIR 结构、文件信息FILEINFO 结构和名称字符串。前两个分别是长20B和28B的固定长度对象，后一个是长度在2B至256B之间 （含字符串的结束符）的变长度对象。为了方便处理并充分发挥DMRA 的作用，将这3个对象分两级用两套独立的DMRA 区存储，其存储结构如图3所示。

图3 快速备份软件中文件信息的存储结构

图3中DIR 和FILEINFO 数据存储在第一级DMRA区，存储块指针为BPAi，所有的字符串则存储在第二级DMRA 区，存储块指针为BPm。第一级DMRA 区中，Dj为J 个链式结构的DIR 数据，Fk为K 个链式结构的FILEINFO 数据；第二级DMRA 区中，Sj为J 个DIR 数据的文件夹名称字符串，而sk为K 个FILEINFO 数据的文件名称字符串。

为了实现快速处理，FILEINFO 数据中既有文件信息，也有非空的文件夹信息。若某个FILEINFO 数据中存放的是文件夹信息，则其后连续存放的就是该文件夹下所有文件的信息。如此设计，这些文件可共用一个文件夹数据作为它们的全路径信息，而不用在文件信息中存储路径信息，也不用为每一个文件求解全路径，从而加快了处理速度。

2 快速文件备份软件实现方法

快速备份软件主处理算法流程如图4所示。图4中每次搜索源文件夹中所有文件或文件夹信息之前，都要复位DMRA 的当前块和当前分配位置。图5是快速备份软件将源文件夹中所有匹配文件向指定的目标文件夹复制处理算法流程图。图5 中的F ［i］就是FILEINFO 的第i个数据信息。

需要注意的是，图5 中创建CDP 前还要排除CDP 是“X：＼”（X 是盘符）的情况，另外所有的文件操作都可能出现错误，必须根据错误的情况决定是否继续处理，如：若是目标磁盘空间不够的错误，则可以继续进行其余文件的复制。为了突出重点，这些处理都没有在流程图中画出。

3 快速备份软件的使用方法

为了方便使用，快速备份软件在使用方法上最大限度地和Windows的控制台复制命令xcopy兼容。配置文件的设计也非常简单，只有3个关键字 “Src＝”、“Dest＝”和“Opt＝”，分别用以指定源文件夹、目标文件夹和选项参数。由这3个关键字开始的连续文本行即构成一个参数块，各参数块之间至少空一行，任何行中从符号 “；”开始的内容为注释内容。每个参数块构成一个独立的备份任务，参数块中关键字的数量和顺序不限，大小写不限，但以最后一个有效的 “Src＝”为源文件夹参数，以最后5个有效的“Dest＝”为目标文件夹参数，以多个 “Opt＝”参数中有效的内容为选项。下面是配置文件一个参数块的示例：

图4 快速备份软件主处理算法

图5 快速备份软件文件复制处理算法

上述备份任务是将D 盘temp文件夹下所有子文件夹中的所有后缀为TXT 的文件以更新备份的方式同时备份到E盘temp文件夹和C盘temp＼temp文件夹下，复制前需要确认，且文件的日期是今年9月10日以后的。

快速备份软件可以在Windows的控制台下直接键入带参数的命令使用，如：

HpBk d：＼temp〔.txt e：＼temp c：＼temp＼temp／r／s／a／10－9

将完成和上面配置文件中相同的备份任务，其中假设快速备份软件的可执行文件名是“HpBk.exe”。

最简单且最快捷的使用方法是将所有的备份任务编写在配置文件中 （设配置文件名是BkCfg.txt），在该配置文件所在文件夹中建立一个后缀为 “BAT”的批处理文件（如 “MyBk.bat”），该批处理文件也是一个文本文件，且只有一行：

HpBk／fBkCfg.txt

在系统菜单或桌面创建一个MyBk.bat文件的快捷方式，需要备份时，运行这个快捷方式即可完成所有的备份任务。

4 结束语

本文针对大量分散存储文件的备份问题进行了探讨，提出了快速备份方法，并给出了实现该方法的备份软件详细设计方法。设计中提出的动态存储再分配方案能够将内存需求量减少1／2至3／4，且处理速度提高了20至50倍，该方法对解决类似情况的动态存储问题也有一定的参考价值。文中给出的快速备份软件的处理方法具有较好的实用性和较高的可靠性，所设计的软件在多年的使用过程中效果良好。

［1］REN Xin，LI Tao，HU Xiaoqin.Design and implementation of remote file backup and restore system ［J］.Computer Engineering，2009，35 （10）：112－114 （in Chinese）. ［任欣，李涛，胡晓勤.远程文件备份与恢复系统的设计与实现 ［J］.计算机工程，2009，35 （10）：112－114.］

［2］HE Yuping，LI Tao，HU Xiaoqin，et al.Design and implementation of remote file backup system based on Windows［J］.Computer Security，2008 （11）：22－25 （in Chinese）. ［何宇平，李涛，胡晓勤，等.基于Windows的远程文件备份系统的设计与实现 ［J］.计算机安全，2008 （11）：22－25.］

［3］HE Yuping，LI Tao，HU Xiaoqin，et al.Key technologies applied into remote file backup system ［J］.Application Research of Computers，2009，26 （1）：361－363 （in Chinese）.［何宇平，李涛，胡晓勤，等.应用于远程文件备份系统的关键技术 ［J］.计算机应用研究，2009，26 （1）：361－363.］

［4］ZHAO Haohan，HU Xiaoqin，DENG Hongmin，et al.Highefficiency file backup method based on internet［J］.Computer Engineering，2010，36 （2）：247－248 （in Chinese）. ［赵昊汉，胡晓勤，邓洪敏，等.基于Internet的高效文件备份方法［J］.计算机工程，2010，36 （2）：247－248.］

［5］GENG Zhenmin，ZENG Shu.Design and implementation of guarantee system on integrity of file backup ［J］.Information Security and Communications Privacy，2012 （7）：123－125 （in Chinese）.［耿振民，曾曙.文件备份完整性保证系统的设计与实现 ［J］.信息安全与通信保密，2012 （7）：123－125.］

［6］TANG Zuquan，QU Minshen，XU Zhijing.Design of files backup system based on filesystem watcher［J］.Electronic Design Engineering，2010，18 （3）：12－13 （in Chinese）. ［唐祖权，屈敏申，徐志京.基于FileSystemWatcher的文件备份系统设计 ［J］.电子设计工程，2010，18 （3）：12－13］

［7］LI Yiran，LI Tao，HU Xiaoqin，et al.Research and implementation of file backup method based on event［J］.Computer Engineering and Design，2010，31 （18）：3957－3959 （in Chinese）.［李夷苒，李涛，胡晓勤，等.基于事件的文件备份方法研究与实现 ［J］.计算机工程与设计，2010，31 （18）：3957－3959.］

［8］BIAN Xia，ZHAO Kui，HU Xiaoqin，et al.Design and implementation of backstage management system of backup system based on MVC architecture ［J］.Computer Engineering and Design，2011，32 （9）：3195－3198 （in Chinese）. ［边霞，赵奎，胡晓勤，等.基于MVC的文件备份后台管理系统的设计与实现［J］.计算机工程与设计，2011，32 （9）：3195－3198.］

［9］LIN Guoqing， WANG Jing，CHEN Ruwei.File backup scheme based on index ［J］.Electronic Design Engineering，2011，19 （19）：165－167 （in Chinese）. ［林国庆，王静，陈汝伟.基于索引的文件备份方案 ［J］.电子设计工程，2011，19 （19）：165－167.］

［10］WU Jiangjiang，MA Jun，WANG Zhiying，et al.The research and implementation of a data backup and recovery technologies supporting service recovery ［J］.Journal of Computer Research and Development，2011，48 （Suppl）：161－168 （in Chinese）.［伍江江，马俊，王志英，等.一种支持服务恢复的文件备份恢复技术研究与实现 ［J］.计算机研究与发展，2011，48 （Suppl）：161－168.］

［11］LIN Guoqing，CHEN Ruwei，LI Ying，et al.Data backup scheme based on network coding ［J］.Computer Science，2010，37 （2）：116－119 （in Chinese）. ［林国庆，陈汝伟，李颖，等.基于网络编码的文件备份方案.计算机科学，2010，37 （2）：116－119.］