基于文件路徑的信息集群中重復數據消除研究

楊美艷，徐慶增

(天津科技大學人工智能學院，天津 300457)

1 引言

隨著信息化時代的高速發展，各類數據信息的數量均呈現出指數級增加趨勢，導致存放于計算機存儲系統中的數據信息規模日益擴大[1]。其中越來越多的冗余數據既占據了存儲空間、降低存儲系統的性能，也提高了數據的管理成本。因此，利用數據縮減方法來減少冗余數據、加強儲存系統性能具有重要的現實意義與理論意義[2]。作為數據縮減技術之一的重復數據消除方法，不僅能夠實現對冗余數據的大規模刪除，而且可以令存儲的空間利用率得以提升。因此，重復數據消除方法逐漸成為計算機存儲領域的一個熱點課題。

文獻[3]針對重復數據吞吐量不可控、相似判斷完成時間過長等問題，利用關聯規則提出一種海量重復數據消除系統，將硬件部分分解為重復數據檢測模塊，增加其吞吐總量與消除可靠性，采用融合TCP/IP、netBEUI以及IPX/SPX協議方案，通過基礎數據序列的關聯規則對重復數據檢測編碼進行改進，從而使消除高效性與穩定性得到保證；文獻[4]為了更好地控制重復數據消除算法中的可變長度分塊大小，降低指紋計算比較開銷，設計一種基于winnowing指紋串匹配的重復數據刪除算法，通過建立分塊大小的預測模型，依據運用場景對分塊大小進行精準計算，然后利用ASCⅡ/UNICODE編碼形式，完成數據塊指紋生成，采用指紋串匹配分塊算法，降低指紋計算與對比開銷；文獻[5]針對異構型物聯網中的重復數據，設計了一種多維數據聚類的重復數據清除方法，對所有感知數據屬性的連續值作離散化處理，提取全部數據文本特征向量并量化，再利用傅里葉轉換方法聯立字符關系矩陣，并形成數據與各字符之間的映射形式，根據各數據的傅里葉系數矢量獲取數據相似度判斷閾值，從而達成重復數據清除的目的。

上述消除方法存在的共性問題是重復數據消除比率與消除速度偏低，難以提升數據存儲空間的利用率。為此，本文利用文件路徑設計了一種信息集群中重復數據消除方法。

2 重復數據消除原理分析

利用數據壓縮技術的信息集群重復數據消除方法通過對比數據內容的哈希值，完成對相同數據的識別，對于重復副本，利用保留下來的唯一指向單一副本指針實施替換，從而實現冗余數據消除、降低存儲容量。

與數據壓縮過程不同的是，對信息集群中重復數據的消除是在存儲數據的過程中，對數據進行分塊篩選，從而實現對當前存在數據的檢查與對比。若數據相一致，則將該部分數據備份去除，并將其替換為指向唯一的實例指針。重復數據消除一般步驟如圖1所示。

圖1 重復數據消除一般步驟示意圖

在分塊篩選階段中，重復數據消除方法的三種分塊理念分別為內容分塊理念、整文件分塊理念以及固定規格分塊理念，其數據副本保存形式均通過單實例策略得以完成。

假設數據消除前與消除后的文件集合分別為F與F′，經過消除的塊數據集合為C′，文件或者塊數據及其儲存空間索引的集合表示為I，則集合I與輸入項文件集合F的表達式分別如下

F={f1，f2，…，fn}

(1)

I={fk→index|fk∈F′}

(2)

輸出項文件集合F′符合F′?F，各集合的初始狀態分別是F′=?、I=?以及fk→index∈I、?fk∈F。

在此基礎上，通過在同一節點上存儲近似數據或文件提升信息集群重復數據消除的效率。文件路徑也叫文件系統路徑，是一種文件系統語義，構成部分為文件系統中從根目錄到文件位置目錄的所有目錄名稱。一般情況下，數據連續備份版本的目錄結構具有一定的穩定性，也就是說，目錄名稱相同的副本極有可能與同一個初始目錄相對應，即目錄名稱一樣的文件集合極有可能含有一樣的數據[6]。

由于父目錄的更改不會影響到該目錄的子目錄。因此，當不同副本的子目錄被修改或者移動時，其父目錄也會保持不變，因此，在對信息集群的重復數據進行消除的過程中，無需運用整個文件目錄，只利用與文件最為趨近的部分父目錄數據即可。

假設文件的整個路徑為directory name，目錄深度是directory depth，表示文件位置目錄以上的目錄層次，get sub directory函數可依據文件目錄名稱知曉特定目錄深度子目錄名稱功能的是，則針對某一文件目錄為“/a/b/c/d.txt”的文件d.txt，“/b/c”為其目錄深度是2的子目錄名稱，同理可知，“/a/b/c”為其目錄深度是3的子目錄名稱。

文件路徑重復數據消除原理如圖2所示。

圖2 文件路徑重復數據消除原理圖

將文件目錄作為粒度，完成重復數據的查找與消除識別不同目錄下的相同文件，避免重復存儲相同文件[7]。然后依據整個文件的數據目錄名稱，對比存儲過的文件目錄名稱，若存在相同名稱，則文件為重復數據，利用指針對其進行替換，并存儲新的文件數據。

3 信息集群中重復數據消除的實現

尉氏縣重復數據消除、系統性能提升以及擴展，完成文件路徑下信息集群的重復數據消除方法的構建。

基于文件路徑的信息集群中重復數據消除方法主要由客戶端、元數據服務器以及存儲節點集群等模塊架構而成。對文件模塊與數據塊模塊的重復數據同時進行消除，以獲取更加理想的消除效果。通過架構多個存儲節點的文件路徑信息集群，并在各節點上實施重復數據檢測，更好地發揮消除方法的性能[8]；利用各節點間的整體重復數據消除，令消除方法適用于擴展的存儲節點個數，從而取得較好的消除結果。

3.1 元數據信息界定

由于重復數據消除是基于文件路徑上的數據目錄名稱或者數據塊的數據標簽得以完成的，因此，文件、數據塊與容器元數據信息的維護具有很明顯的重要性。

文件元數據信息的構成分別有文件目錄名稱、文件規格以及建立時間等，具體內容如表1所示。

表1 文件元數據信息統計表

數據塊元數據信息主要由數據塊標簽、數據塊規格以及數據塊存儲容器等構成，具體內容如表2所示。

表2 數據塊元數據信息統計表

表2中的容器是存儲節點磁盤系統內的一種文件，其功能是依據數據塊的邏輯順序存儲消除過的數據塊與元數據信息，其中元數據信息如表3所示。

表3 容器元數據信息統計表

3.2 信息集群重復數據消除流程

3.2.1 文件部分重復數據消除

在數據備份的過程中，按照以下步驟來完成對文件模塊的重復數據消除：

1)客戶端依據各文件的哈希值生成目錄名稱，并將其傳輸至元數據服務器；

2)元數據服務器根據存儲的文件元數據信息檢測重復數據，把非重復的新文件目錄名稱與存儲節點信息同步發送給客戶端，隨后客戶端將數據塊傳輸至每個存儲節點內，從而實現文件模塊的重復數據消除。

文件模塊重復數據消除過程如圖3所示。

圖3 文件模塊重復數據消除示意圖

3.2.2 數據塊模塊重復數據消除

基于文件模塊的重復數據消除結果，對信息集群中的多個重復文件進行消除，數據塊模塊重復數據消除則是實現文件內部的重復數據消除，其步驟如下：

1)客戶端分塊新文件后，對潛在冗余數據進行消除，以防止固定長度數據塊發生偏移，所以，當文件規格小于2kB時，不用實施分塊操作，可直接當做一個數據塊進行處理；

2)經過文件分塊，客戶端將各文件數據塊的哈希值作為數據塊標簽，把文件元數據信息與所含數據塊標簽列表同步傳輸至元數據服務器，從而達成數據存儲，為數據恢復階段的所有數據塊獲取奠定基礎，客戶端把所有數據塊標簽與不同存儲節點一一對應后，實施重復數據消除；

3)當存儲節點收到數據塊標簽，通過bloom filter法比較本地節點存儲的數據塊標簽[9]，進而完成全局范圍的重復數據消除，隨后存儲節點會發送給客戶端全部的非重復數據塊標簽；

4)客戶端通過把非重復數據塊以及相應的元數據信息傳輸至對應存儲節點，對其實施打包存儲，此時數據塊重復數據消除操作終止。

數據塊模塊重復數據消除過程如圖4所示。

圖4 數據塊模塊重復數據消除示意圖

3.3.3 數據恢復階段

為了使數據的可靠性得到保證，確保數據在出現損壞或者丟失的情況下，也可以隨時恢復、隨時可用，數據的可恢復性由文件路徑下信息集群重復數據消除方法存儲的元數據信息實現，其流程如下：

1)客戶端發送待恢復的文件目錄名稱給元數據服務器；

2)元數據服務器接收之后，對文件元數據信息表進行查詢，并將取得的數據塊標簽列表，返回客戶端；

3)依據文件名錄名稱對存儲節點個數的取模結果，客戶端對文件數據塊及其元數據信息的存儲節點進行存儲，且發送數據塊標簽列表給對應節點；

4)在接收到全部數據塊之后，客戶端開始重建操作，數據恢復階段結束。

數據恢復過程如圖5所示。

圖5 數據恢復示意圖

4 仿真與分析

為驗證上述設計的基于文件路徑的信息集群中重復數據消除方法的實際應用性能，設計如下仿真。

4.1 仿真環境設置

仿真的硬件環境為：英特爾至強E5502四核處理器、浪潮AS300N服務器，mellanox connectX 4X QDR單向40GBPS的infiniband網卡，LSI logic/symbios logic mega SAS RAID卡；軟件環境為：Red Hat Enterprise Linux(RHEL)操作系統，2.6.18-164.11.1.el5＿lustre.1.8.2內核。

信息集群分別選自企業系統的trace集合與Linux系統源代碼集合，表4為集群的相應參數。

表4 參數統計表

為突出本文方法的應用優勢，將傳統的基于winnowing指紋串匹配的重復數據刪除方法和基于關聯規則的海量重復數據消除方法作為對比，共同完成性能驗證。

為了評估不同的重復數據消除方法的性能，將評估指標設定為分塊大小的標準方差，表達式如下

(3)

其中，分塊大小的標準方差為σ，分塊個數為N，實際分塊大小為xi，期望分塊大小為μ。

4.2 消除效果對比分析

如圖6所示為不同方法的重復數據消除比率對比結果。重復數據消除比率越高，說明消除方法對重復數據的檢索、刪除能力越強。

圖6 重復數據消除比率對比圖

通過圖6可以看出，基于winnowing指紋串匹配方法的消除比率呈不斷上升趨勢，且消除比率始終在92%以上；基于關聯規則方法的消除比率先上升后下降，最大比率接近92%；本文方法的消除比率不斷下降，但整體來講，本文方法的消除比率在三種方法中為最高。由此可知，本文方法對重復數據的消除能力更強。

4.3 消除時長對比分析

進一步驗證不同方法對重復數據的消除時長，從而判斷不同方法的時效性。結果如圖7所示。

圖7 重復數據消除時長對比圖

根據圖7中的曲線走勢可以看出，隨著數據量的增加，不同方法對重復數據的消除時長也在不斷增加。相比之下，基于winnowing指紋串匹配方法的消除時長最多，始終保持在12s以上，基于關聯規則方法其次，本文方法的消除時長最少，始終保持在8s以下。由此可知，本文方法消除重復數據的時效性最高。

5 結束語

數字信息技術既改善了人們的生活方式，也推動了經濟社會的發展。在數據量呈爆炸式增長的環境下，數據存儲容量正面臨著一項巨大的挑戰。因此，為了使該領域問題得到有效解決，本研究提出一種基于文件路徑的信息集群中重復數據消除方法。將信息集群重復數據消除的基本流程與分塊思想引入文件系統中，根據根目錄到文件位置目錄的所有目錄名稱以及父目錄與子目錄關系，分析文件路徑的消除方法原理，通過同時消除文件模塊與數據塊模塊中的重復數據實現方法設計。該方法具有良好的發展前景，也為信息集群的后續處理奠定了基礎。