林国庆，王 静，陈汝伟

（1.长安大学 汽车学院，陕西 西安 710064；2.长安大学 信息学院，陕西 西安 710064；3.桂林电子科技大学 数学与计算科学学院，广西 桂林 541004）

数据备份[1]是在现时使用的数据之外，实现或设置另外一份不同物理体现、内容相同的有效数据拷贝，以提高数据的安全性。传统数据备份方案是将多个主机通过局域网或存储网络[2-3]与备份服务器相连，备份时各主机将需备份数据传输到备份服务器上独立存储。节省磁盘存储空间是众多备份软件的共同目标之一。现有的备份软件多是通过各种方式压缩以减少备份所需空间[4]。而这种方式只是对文件个体的缩小，对空间的节省是有限的。同时，在备份服务器上，会有大量的属于不同备份用户或文件夹的相同文件存在，比如某些库文件、系统文件、软件安装文件等。为此，提出了一种新的针对文件的数据备份方案，对相同的文件只存储一个副本，减少存储中的冗余，从而节省存储空间。

1 基于索引的文件备份方案

基于索引的文件备份方案包括以下几个部分:相同文件的识别、文件的存储、文件夹的处理、文件备份过程和备份的更新。

1.1 基于索引的文件备份方案实现原理

基于索引的文件备份方案原理就是：对备份服务器中的文件进行鉴别和排序，相同文件只存储一个副本，从而达到节省存储空间的目的。

文件夹A上有文件a、b，文件夹B上有文件b、c。 文件大小都为1。现将4个文件在备份服务器S上备份，传统备份方案如图1（a）所示，所占备份空间为4。 新的备份方案如图1（b）所示，新方案对相同的两个文件b只存储一个副本，所占总备份空间为3。显然，新方案比传统方案节省了25%的备份空间。

图1 相同文件只存储一个副本Fig.1 Only stored a copy for the same files

1.2 相同文件的识别

对相同文件的识别务必严格，否则可能导致文件的丢失。在文中用以下参数作为判定标准：文件名称、文件大小、修改时间。3个参数完全相同则可被认为是同一个文件。

1.3 备份文件链表

对备份文件建立索引，具体就是先对文件类型进行分类，按文件类型名的字典顺序排序；而后将同类型的文件按文件名的字典顺序进行排序。

用二维链表[5]的形式具体实现对文件进行索引排序，该链表叫做备份文件链表。如图2所示，横向链表为文件类型链表，每个文件类型节点含有该文件类型的相应信息，并对应着一个纵向链表，即文件指针链表。文件指针链表的节点叫做文件指针节点。每个文件指针节点含有该文件的相应信息并含有一个文件指针指向该文件的存储位置。这些文件指针节点也是按照对应文件名的字典顺序排列构建纵向链表的。

图2 备份文件链表Fig.2 Chain for backup file

文件类型节点数据结构定义如下:

文件指针节点数据结构如下:

1.4 文件的备份过程

下面介绍文件的具体备份过程，文件夹A中有文件a，首先，将文件夹A拷贝到备份服务器S上，然后将该文件夹中文件放入备份文件链表中。将文件a加入链表的过程如下：1）将的文件类型名用折半查找法[6]对照横向链表各节点，选择对应的纵向链表，转2）。若无相应的文件类型节点，则按字典顺序在相应位置新建一个该文件类型的节点和对应的纵向链表，并在纵向链表中加入一个对应文件a的文件指针节点，结束处理。2）用折半查找法按文件名查询对应的纵向链表即文件指针链表，若有文件名大小和修改时间与a完全相同的节点，则认为a与之对应文件为相同文件，此时删除文件a，并将该文件的文件指针放入到文件夹A中，完成处理。若无相同文件存在，则新建一个指向a的文件指针节点，插入到文件指针链表中的相应位置（同名文件依次按修改时间先后排列），完成处理。文件指针节点中的归属文件夹数量参数随实际情况变化。在a被纳入到备份文件链表后，文件夹A中仅保留指向a存储地址的指针。文件a加入链表的过程如图3所示。

图3 文件加入链表的过程Fig.3 Process of added file into chain

1.5 备份文件的更新

备份文件在一段时间后可能需要进行更新。此时需用新文件a′代替旧文件a。具体操作如下：查询对应文件指针链表，若存在与a′相同的文件则将对应文件指针放入文件夹A中，并删除A中对应a的指针文件，将对应文件指针节点中的归属文件数量减1；若无相同，则新建一个指向a′的文件指针节点，加入到文件指针链表中的相应位置，将对应文件指针放入文件夹A中，并删除A中对应a的文件指针，将a的文件指针节点中的归属文件数量减1，完成处理。a的文件指针节点中的归属文件夹数量参数为0时，则删除a文件和对应文件指针节点。在删除文件夹A时，若a的文件指针节点中的归属文件夹数量参数大于1，则只需删除A和其中的指向a存储地址的指针；若等于1，则还要删除a文件和对应文件指针节点。

1.6 验证实验

实验方案1：在多台主机上随机选取多个文件夹用传统方式和基于索引的方式进行备份，备份过程中均不采用压缩，对比两者占用存储空间的大小，并观察备份过程中的内存和CPU使用情况和备份过程所需时间。

局域网中有主机A、B和C，选取主机C作为备份服务器，随机选取A上的文件夹D、E、F和B上的文件夹G、H、I在C上备份。采用传统方式和基于索引的方式分别进行备份。

实验数据如表1、表2所示。

实验说明:

1）两备份过程先后独立进行，各备份文件夹顺次单个传输，备份位置为相同硬盘分区。

2）C机内存使用量和CPU平均使用率的统计包含相同的系统进程的消耗量。

表1 文件夹大小和文件数Tab.1 The size of folder and the number of files

3）传统备份持续时间为所有文件夹通过网络拷贝所需时间；索引备份采用双线程方式进行，即拷贝和加入链表两线程同时工作，持续时间为所有操作完成所需时间。

4）索引备份完成后相关链表等数据结构约占存储空间40 KB，计入总存储空间中。

表2 实验1结果Tab.2 The results of the first experiment

实验方案2：利用传统方式和基于索引的方式对文件夹数量不同的多个组文件夹进行备份，对比各自相对传统方式占用存储空间的大小和节省存储空间比例的情况。

第一组:选择文件F和I进行备份；

第二组:选择文件E，F，H和I进行备份；

第三组:选择文件D，E，F，G，H和I进行备份；

实验数据如表3所示。

表3 实验2结果Tab.3 The results of the second experiment

1.7 性能分析

结合实验对基于索引的文件备份方案进行性能分析，该方案在性能上有以下特点。

1）节省了存储空间

实验1显示，新方案相对于传统方法节省了存储空间，这是因为新方案减少了因相同文件重复存储而产生的冗余。

2）文件数量增多，重复文件出现的几率增大

实验2显示，随着文件数量的增多新方案相对于传统方法节省存储空间的比例增大。这是因为文件数增多，重复文件出现的几率增大，相应的节省存储空间就越多。但也不排除在某些情况下文件数增多但无更多重复文件出现，而造成节省比例降低的可能。

3）系统负载和备份过程持续时间增加

实验1显示，新方案中备份时服务器的内存使用量和CPU使用率增加，这是因为新方案增加了文件加入链表的处理过程。它占用了系统资源，同时也增加了备份过程持续的时间。

2 结 论

文中提出了一种基于索引的文件备份方案，主要内容是用链表形式对备份文件建立索引，并对相同的文件只存储一个副本，消除了重复文件的冗余，从而达到节省备份空间的目的。实验证明基于索引的文件备份方案较传统方法节省了存储空间，但备份过程中的系统负载和消耗时间有所增加。后续研究将考虑如何减少备份所需时间。备份时间较长主要是由于加入文件时对链表的顺序查询、定位和判别相同文件等操作所消耗时间较多造成的。初步的考虑是用更高效的索引方式代替二维链表或引入比折半查找更高效的算法加快文件在二维链表中的定位，以达到节省时间的目的。同时，还将考虑将基于索引的备份原理应用到数据库备份中以达到减少相同数据冗余的目的。

[1]熊琦，王丽娜，王德军，等.基于磁盘和SAN的网络数据备份模型[J].计算机工程，2007，33（4）:233-238.XIONG Qi，WANG Li-na，WANG De-jun，et al.Network data backup model based on hard disk and SAN[J].Computer Engineering，2007，33（4）:233-238.

[2]余寅辉，余镇危，杨传栋，等.SAN存储系统的性能分析模型[J].计算机工程，2007，33（10）:271-273.YUYin-hui， YUZhen-wei， YANGChuan-dong， etal.Performance analysismodelofSANStoragesystem[J].ComputerEngineering，2007，33（10）:271-273.

[3]Mesnier M，Ganger G R，Riedel E.Object-based storage[J].IEEE Comm Mag，2003，41（8）:84-90.

[4]陈飞翔，周治武，张建兵.基于动态规划算法的矢量数据压缩改进算法[J].计算机应用，2008，28（2）:168-170.CHEN Fei-xiang，ZHOU Zhi-wu， ZHANG Jian-bing.Improved algorithm for vector data compression based on dynamic programming[J].Journal of Computer Applications，2008，28（2）:168-170.

[5]唐正军.入侵检测技术导论[M].北京:机械工业出版社，2004.

[6]严蔚敏，吴伟民，数据结构[M].C语言版.北京:清华大学出版社，1997.