[發(fā)明專利]一種基于文件內(nèi)容類型的重復數(shù)據(jù)刪除方法

無效

• 申請?zhí)枺?/td>: 200910273171.0
• 申請日: 2009-12-10
• 公開（公告）號: CN101706825A
• 公開（公告）日: 2010-05-12
• 發(fā)明（設(shè)計）人: 周敬利;秦磊華;曾東;聶雪軍;劉科;朱建峰
• 申請（專利權(quán)）人: 華中科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F11/14
• 代理公司: 華中科技大學專利中心 42201
• 代理人: 方放

技術(shù)領(lǐng)域

本發(fā)明屬于計算機數(shù)據(jù)備份的重復數(shù)據(jù)刪除方法，具體涉及一種基于文件內(nèi)容類型(Content?Type)的重復數(shù)據(jù)刪除方法，適用于基于磁盤的備份系統(tǒng)。

背景技術(shù)

進入到21世紀以后，隨著信息時代的加速，數(shù)據(jù)呈現(xiàn)出爆炸性增長的趨勢，用戶存儲容量日趨緊張、數(shù)據(jù)管理難度日益加大、存儲支出逐漸增加。為了應對這些問題，提出了重復數(shù)據(jù)刪除技術(shù)，以有效地減少用戶日常備份中的重復數(shù)據(jù)，使得備份數(shù)據(jù)大大減少，從而為用戶節(jié)省了存儲容量，并降低了數(shù)據(jù)管理工作的難度。許多存儲廠商都推出了基于重復數(shù)據(jù)刪除的備份系統(tǒng)或軟件，例如EMC公司的Avamar?Data?Store備份存儲系統(tǒng)，Data?Domain公司的DDX陣列以及SEPATON公司的DeltaStor軟件。

根據(jù)重復數(shù)據(jù)識別的粒度，重復數(shù)據(jù)刪除技術(shù)可分為文件級重復數(shù)據(jù)刪除和數(shù)據(jù)塊級重復數(shù)據(jù)刪除，在備份環(huán)境下通常采用后者。數(shù)據(jù)塊級重復數(shù)據(jù)刪除技術(shù)是指將備份文件劃分為多個數(shù)據(jù)塊，然后判斷每個數(shù)據(jù)塊是否已處于存儲池中，如果發(fā)現(xiàn)某一數(shù)據(jù)塊已經(jīng)存在，則會在備份文件的索引節(jié)點中插入指向已存在數(shù)據(jù)塊的指針；只有不重復的數(shù)據(jù)塊才會被寫入磁盤的相應區(qū)域。存儲池是由硬盤、磁帶或光盤構(gòu)成的計算機虛擬存儲設(shè)備，用于存儲海量數(shù)據(jù)。

在數(shù)據(jù)塊級重復數(shù)據(jù)刪除技術(shù)中，關(guān)鍵問題在于如何將備份文件劃分為數(shù)據(jù)塊，即如何確定數(shù)據(jù)塊的邊界特征。目前的分塊技術(shù)有兩種，定長分塊和變長分塊。定長分塊是指將文件分塊為同一大小的數(shù)據(jù)塊，例如4K、8K等；變長分塊是采用滑動窗口對備份文件做整體掃描，如果滑動窗口中的內(nèi)容滿足預定的數(shù)據(jù)塊邊界條件，則被識別為一個邊界，兩個邊界之間的所有字節(jié)被分塊為一個數(shù)據(jù)塊。

對于數(shù)據(jù)塊級重復數(shù)據(jù)刪除技術(shù)而言，目前存在的主要問題是：對備份系統(tǒng)中的所有文件采用單一的塊邊界特征，而沒有考慮重復數(shù)據(jù)塊的數(shù)量會因文件內(nèi)容性質(zhì)(包括文件類型與采用的編碼方式等)的不同而存在較大差異，單一塊邊界特征的策略不能使不同內(nèi)容類型文件的重復數(shù)據(jù)刪除率都達到最優(yōu)。因此，需要根據(jù)內(nèi)容類型對文件進行分類，并采用復合策略來分別處理不同內(nèi)容類型的備份文件。

發(fā)明內(nèi)容

本發(fā)明提供一種基于文件內(nèi)容類型的重復數(shù)據(jù)刪除方法，解決現(xiàn)有重復數(shù)據(jù)刪除方法存在的分塊策略單一，不能根據(jù)文件內(nèi)容類型進行優(yōu)化的問題。

備份系統(tǒng)定期執(zhí)行備份過程，每次備份過程都得到一個備份文件集合。

在存儲池中，每個文件都以一個索引節(jié)點來標識。文件被劃分為多個數(shù)據(jù)塊，每個數(shù)據(jù)塊都通過計算得到一個哈希值；在索引節(jié)點中包含了每個數(shù)據(jù)塊對應的哈希值；在哈希值表中包含了所有數(shù)據(jù)塊的哈希值以及數(shù)據(jù)塊在磁盤上的存儲地址；通過哈希值表可以找到文件中每個數(shù)據(jù)塊的地址。

本發(fā)明的一種基于文件內(nèi)容類型的重復數(shù)據(jù)刪除方法，預先進行塊邊界特征計算步驟：在備份系統(tǒng)中采集樣本文件集合，提取樣本文件的元數(shù)據(jù)，并根據(jù)元數(shù)據(jù)確定樣本文件的內(nèi)容類型，再根據(jù)樣本文件的內(nèi)容類型將樣本文件集合分類為多個子集合，計算每個子集合的塊邊界特征值，將各個子集合的塊邊界特征值保存在塊邊界特征庫中；

以下順序包括：

A.內(nèi)容類型識別步驟：提取用戶輸入文件的元數(shù)據(jù)，并根據(jù)元數(shù)據(jù)確定文件的內(nèi)容類型，根據(jù)文件的內(nèi)容類型在塊邊界特征庫中尋找對應的塊邊界特征值；

B.文件分塊步驟：根據(jù)步驟A中尋找到的塊邊界特征值，采用滑動窗口對用戶輸入文件整體進行掃描，將用戶輸入文件劃分為多個數(shù)據(jù)塊；

C.數(shù)字指紋計算步驟：對步驟B中產(chǎn)生的每個數(shù)據(jù)塊，計算其哈希(HASH)值作為該數(shù)據(jù)塊的數(shù)字指紋，轉(zhuǎn)步驟D；

D.重復數(shù)據(jù)塊判斷步驟：將步驟C中生成的哈希值與存儲池中的哈希值表中的哈希值進行比較，判斷是否相同，是則僅將該哈希值存入文件的索引節(jié)點中，轉(zhuǎn)步驟E；否則把該哈希值存入哈希值表以及文件的索引節(jié)點中，并將對應的數(shù)據(jù)塊寫入存儲池中，轉(zhuǎn)步驟E；

E.結(jié)束步驟：當前文件重復數(shù)據(jù)刪除結(jié)束，當用戶輸入下一文件時，轉(zhuǎn)步驟A；

所述存儲池存儲哈希值表和數(shù)據(jù)塊，該哈希值表中包含所存儲每個數(shù)據(jù)塊的哈希值以及在磁盤上的地址，所存儲的所有數(shù)據(jù)塊不重復；

所述文件的元數(shù)據(jù)包括文件的內(nèi)容類型、文件擴展名、生成文件的應用程序以及文件內(nèi)容的編碼方式，其中，文件擴展名、生成文件的應用程序以及文件內(nèi)容的編碼方式三種元數(shù)據(jù)構(gòu)成一個元數(shù)據(jù)三元組，形為{擴展名，應用程序，編碼方式}。

所述的重復數(shù)據(jù)刪除方法，其特征在于：

所述塊邊界特征計算步驟，包括下述子步驟：