基于索引的文件備份方案

林國慶，王 靜，陳汝偉

（1.長安大學 汽車學院，陜西 西安 710064；2.長安大學 信息學院，陜西 西安 710064；3.桂林電子科技大學 數(shù)學與計算科學學院，廣西 桂林 541004）

數(shù)據(jù)備份[1]是在現(xiàn)時使用的數(shù)據(jù)之外，實現(xiàn)或設(shè)置另外一份不同物理體現(xiàn)、內(nèi)容相同的有效數(shù)據(jù)拷貝，以提高數(shù)據(jù)的安全性。傳統(tǒng)數(shù)據(jù)備份方案是將多個主機通過局域網(wǎng)或存儲網(wǎng)絡(luò)[2-3]與備份服務(wù)器相連，備份時各主機將需備份數(shù)據(jù)傳輸?shù)絺浞莘?wù)器上獨立存儲。節(jié)省磁盤存儲空間是眾多備份軟件的共同目標之一。現(xiàn)有的備份軟件多是通過各種方式壓縮以減少備份所需空間[4]。而這種方式只是對文件個體的縮小，對空間的節(jié)省是有限的。同時，在備份服務(wù)器上，會有大量的屬于不同備份用戶或文件夾的相同文件存在，比如某些庫文件、系統(tǒng)文件、軟件安裝文件等。為此，提出了一種新的針對文件的數(shù)據(jù)備份方案，對相同的文件只存儲一個副本，減少存儲中的冗余，從而節(jié)省存儲空間。

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

基于索引的文件備份方案包括以下幾個部分:相同文件的識別、文件的存儲、文件夾的處理、文件備份過程和備份的更新。

1.1 基于索引的文件備份方案實現(xiàn)原理

基于索引的文件備份方案原理就是：對備份服務(wù)器中的文件進行鑒別和排序，相同文件只存儲一個副本，從而達到節(jié)省存儲空間的目的。

文件夾A上有文件a、b，文件夾B上有文件b、c。 文件大小都為1?，F(xiàn)將4個文件在備份服務(wù)器S上備份，傳統(tǒng)備份方案如圖1（a）所示，所占備份空間為4。 新的備份方案如圖1（b）所示，新方案對相同的兩個文件b只存儲一個副本，所占總備份空間為3。顯然，新方案比傳統(tǒng)方案節(jié)省了25%的備份空間。

圖1 相同文件只存儲一個副本Fig.1 Only stored a copy for the same files

1.2 相同文件的識別

對相同文件的識別務(wù)必嚴格，否則可能導(dǎo)致文件的丟失。在文中用以下參數(shù)作為判定標準：文件名稱、文件大小、修改時間。3個參數(shù)完全相同則可被認為是同一個文件。

1.3 備份文件鏈表

對備份文件建立索引，具體就是先對文件類型進行分類，按文件類型名的字典順序排序；而后將同類型的文件按文件名的字典順序進行排序。

用二維鏈表[5]的形式具體實現(xiàn)對文件進行索引排序，該鏈表叫做備份文件鏈表。如圖2所示，橫向鏈表為文件類型鏈表，每個文件類型節(jié)點含有該文件類型的相應(yīng)信息，并對應(yīng)著一個縱向鏈表，即文件指針鏈表。文件指針鏈表的節(jié)點叫做文件指針節(jié)點。每個文件指針節(jié)點含有該文件的相應(yīng)信息并含有一個文件指針指向該文件的存儲位置。這些文件指針節(jié)點也是按照對應(yīng)文件名的字典順序排列構(gòu)建縱向鏈表的。

圖2 備份文件鏈表Fig.2 Chain for backup file

文件類型節(jié)點數(shù)據(jù)結(jié)構(gòu)定義如下:

文件指針節(jié)點數(shù)據(jù)結(jié)構(gòu)如下:

1.4 文件的備份過程

下面介紹文件的具體備份過程，文件夾A中有文件a，首先，將文件夾A拷貝到備份服務(wù)器S上，然后將該文件夾中文件放入備份文件鏈表中。將文件a加入鏈表的過程如下：1）將的文件類型名用折半查找法[6]對照橫向鏈表各節(jié)點，選擇對應(yīng)的縱向鏈表，轉(zhuǎn)2）。若無相應(yīng)的文件類型節(jié)點，則按字典順序在相應(yīng)位置新建一個該文件類型的節(jié)點和對應(yīng)的縱向鏈表，并在縱向鏈表中加入一個對應(yīng)文件a的文件指針節(jié)點，結(jié)束處理。2）用折半查找法按文件名查詢對應(yīng)的縱向鏈表即文件指針鏈表，若有文件名大小和修改時間與a完全相同的節(jié)點，則認為a與之對應(yīng)文件為相同文件，此時刪除文件a，并將該文件的文件指針放入到文件夾A中，完成處理。若無相同文件存在，則新建一個指向a的文件指針節(jié)點，插入到文件指針鏈表中的相應(yīng)位置（同名文件依次按修改時間先后排列），完成處理。文件指針節(jié)點中的歸屬文件夾數(shù)量參數(shù)隨實際情況變化。在a被納入到備份文件鏈表后，文件夾A中僅保留指向a存儲地址的指針。文件a加入鏈表的過程如圖3所示。

圖3 文件加入鏈表的過程Fig.3 Process of added file into chain

1.5 備份文件的更新

備份文件在一段時間后可能需要進行更新。此時需用新文件a′代替舊文件a。具體操作如下：查詢對應(yīng)文件指針鏈表，若存在與a′相同的文件則將對應(yīng)文件指針放入文件夾A中，并刪除A中對應(yīng)a的指針文件，將對應(yīng)文件指針節(jié)點中的歸屬文件數(shù)量減1；若無相同，則新建一個指向a′的文件指針節(jié)點，加入到文件指針鏈表中的相應(yīng)位置，將對應(yīng)文件指針放入文件夾A中，并刪除A中對應(yīng)a的文件指針，將a的文件指針節(jié)點中的歸屬文件數(shù)量減1，完成處理。a的文件指針節(jié)點中的歸屬文件夾數(shù)量參數(shù)為0時，則刪除a文件和對應(yīng)文件指針節(jié)點。在刪除文件夾A時，若a的文件指針節(jié)點中的歸屬文件夾數(shù)量參數(shù)大于1，則只需刪除A和其中的指向a存儲地址的指針；若等于1，則還要刪除a文件和對應(yīng)文件指針節(jié)點。

1.6 驗證實驗

實驗方案1：在多臺主機上隨機選取多個文件夾用傳統(tǒng)方式和基于索引的方式進行備份，備份過程中均不采用壓縮，對比兩者占用存儲空間的大小，并觀察備份過程中的內(nèi)存和CPU使用情況和備份過程所需時間。

局域網(wǎng)中有主機A、B和C，選取主機C作為備份服務(wù)器，隨機選取A上的文件夾D、E、F和B上的文件夾G、H、I在C上備份。采用傳統(tǒng)方式和基于索引的方式分別進行備份。

實驗數(shù)據(jù)如表1、表2所示。

實驗說明:

1）兩備份過程先后獨立進行，各備份文件夾順次單個傳輸，備份位置為相同硬盤分區(qū)。

2）C機內(nèi)存使用量和CPU平均使用率的統(tǒng)計包含相同的系統(tǒng)進程的消耗量。

表1 文件夾大小和文件數(shù)Tab.1 The size of folder and the number of files

3）傳統(tǒng)備份持續(xù)時間為所有文件夾通過網(wǎng)絡(luò)拷貝所需時間；索引備份采用雙線程方式進行，即拷貝和加入鏈表兩線程同時工作，持續(xù)時間為所有操作完成所需時間。

4）索引備份完成后相關(guān)鏈表等數(shù)據(jù)結(jié)構(gòu)約占存儲空間40 KB，計入總存儲空間中。

表2 實驗1結(jié)果Tab.2 The results of the first experiment

實驗方案2：利用傳統(tǒng)方式和基于索引的方式對文件夾數(shù)量不同的多個組文件夾進行備份，對比各自相對傳統(tǒng)方式占用存儲空間的大小和節(jié)省存儲空間比例的情況。

第一組:選擇文件F和I進行備份；

第二組:選擇文件E，F(xiàn)，H和I進行備份；

第三組:選擇文件D，E，F(xiàn)，G，H和I進行備份；

實驗數(shù)據(jù)如表3所示。

表3 實驗2結(jié)果Tab.3 The results of the second experiment

1.7 性能分析

結(jié)合實驗對基于索引的文件備份方案進行性能分析，該方案在性能上有以下特點。

1）節(jié)省了存儲空間

實驗1顯示，新方案相對于傳統(tǒng)方法節(jié)省了存儲空間，這是因為新方案減少了因相同文件重復(fù)存儲而產(chǎn)生的冗余。

2）文件數(shù)量增多，重復(fù)文件出現(xiàn)的幾率增大

實驗2顯示，隨著文件數(shù)量的增多新方案相對于傳統(tǒng)方法節(jié)省存儲空間的比例增大。這是因為文件數(shù)增多，重復(fù)文件出現(xiàn)的幾率增大，相應(yīng)的節(jié)省存儲空間就越多。但也不排除在某些情況下文件數(shù)增多但無更多重復(fù)文件出現(xiàn)，而造成節(jié)省比例降低的可能。

3）系統(tǒng)負載和備份過程持續(xù)時間增加

實驗1顯示，新方案中備份時服務(wù)器的內(nèi)存使用量和CPU使用率增加，這是因為新方案增加了文件加入鏈表的處理過程。它占用了系統(tǒng)資源，同時也增加了備份過程持續(xù)的時間。

2 結(jié) 論

文中提出了一種基于索引的文件備份方案，主要內(nèi)容是用鏈表形式對備份文件建立索引，并對相同的文件只存儲一個副本，消除了重復(fù)文件的冗余，從而達到節(jié)省備份空間的目的。實驗證明基于索引的文件備份方案較傳統(tǒng)方法節(jié)省了存儲空間，但備份過程中的系統(tǒng)負載和消耗時間有所增加。后續(xù)研究將考慮如何減少備份所需時間。備份時間較長主要是由于加入文件時對鏈表的順序查詢、定位和判別相同文件等操作所消耗時間較多造成的。初步的考慮是用更高效的索引方式代替二維鏈表或引入比折半查找更高效的算法加快文件在二維鏈表中的定位，以達到節(jié)省時間的目的。同時，還將考慮將基于索引的備份原理應(yīng)用到數(shù)據(jù)庫備份中以達到減少相同數(shù)據(jù)冗余的目的。

[1]熊琦，王麗娜，王德軍，等.基于磁盤和SAN的網(wǎng)絡(luò)數(shù)據(jù)備份模型[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]余寅輝，余鎮(zhèn)危，楊傳棟，等.SAN存儲系統(tǒng)的性能分析模型[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]陳飛翔，周治武，張建兵.基于動態(tài)規(guī)劃算法的矢量數(shù)據(jù)壓縮改進算法[J].計算機應(yīng)用，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]唐正軍.入侵檢測技術(shù)導(dǎo)論[M].北京:機械工業(yè)出版社，2004.

[6]嚴蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)[M].C語言版.北京:清華大學出版社，1997.