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

楊美艷，徐慶增

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

1 引言

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

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

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

2 重復數(shù)據(jù)消除原理分析

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

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

圖1 重復數(shù)據(jù)消除一般步驟示意圖

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

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

F={f1，f2，…，fn}

(1)

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

(2)

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

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

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

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

文件路徑重復數(shù)據(jù)消除原理如圖2所示。

圖2 文件路徑重復數(shù)據(jù)消除原理圖

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

3 信息集群中重復數(shù)據(jù)消除的實現(xiàn)

尉氏縣重復數(shù)據(jù)消除、系統(tǒng)性能提升以及擴展，完成文件路徑下信息集群的重復數(shù)據(jù)消除方法的構(gòu)建。

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

3.1 元數(shù)據(jù)信息界定

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

文件元數(shù)據(jù)信息的構(gòu)成分別有文件目錄名稱、文件規(guī)格以及建立時間等，具體內(nèi)容如表1所示。

表1 文件元數(shù)據(jù)信息統(tǒng)計表

數(shù)據(jù)塊元數(shù)據(jù)信息主要由數(shù)據(jù)塊標簽、數(shù)據(jù)塊規(guī)格以及數(shù)據(jù)塊存儲容器等構(gòu)成，具體內(nèi)容如表2所示。

表2 數(shù)據(jù)塊元數(shù)據(jù)信息統(tǒng)計表

表2中的容器是存儲節(jié)點磁盤系統(tǒng)內(nèi)的一種文件，其功能是依據(jù)數(shù)據(jù)塊的邏輯順序存儲消除過的數(shù)據(jù)塊與元數(shù)據(jù)信息，其中元數(shù)據(jù)信息如表3所示。

表3 容器元數(shù)據(jù)信息統(tǒng)計表

3.2 信息集群重復數(shù)據(jù)消除流程

3.2.1 文件部分重復數(shù)據(jù)消除

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

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

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

文件模塊重復數(shù)據(jù)消除過程如圖3所示。

圖3 文件模塊重復數(shù)據(jù)消除示意圖

3.2.2 數(shù)據(jù)塊模塊重復數(shù)據(jù)消除

基于文件模塊的重復數(shù)據(jù)消除結(jié)果，對信息集群中的多個重復文件進行消除，數(shù)據(jù)塊模塊重復數(shù)據(jù)消除則是實現(xiàn)文件內(nèi)部的重復數(shù)據(jù)消除，其步驟如下：

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

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

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

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

數(shù)據(jù)塊模塊重復數(shù)據(jù)消除過程如圖4所示。

圖4 數(shù)據(jù)塊模塊重復數(shù)據(jù)消除示意圖

3.3.3 數(shù)據(jù)恢復階段

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

1)客戶端發(fā)送待恢復的文件目錄名稱給元數(shù)據(jù)服務(wù)器；

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

3)依據(jù)文件名錄名稱對存儲節(jié)點個數(shù)的取模結(jié)果，客戶端對文件數(shù)據(jù)塊及其元數(shù)據(jù)信息的存儲節(jié)點進行存儲，且發(fā)送數(shù)據(jù)塊標簽列表給對應(yīng)節(jié)點；

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

數(shù)據(jù)恢復過程如圖5所示。

圖5 數(shù)據(jù)恢復示意圖

4 仿真與分析

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

4.1 仿真環(huán)境設(shè)置

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

信息集群分別選自企業(yè)系統(tǒng)的trace集合與Linux系統(tǒng)源代碼集合，表4為集群的相應(yīng)參數(shù)。

表4 參數(shù)統(tǒng)計表

為突出本文方法的應(yīng)用優(yōu)勢，將傳統(tǒng)的基于winnowing指紋串匹配的重復數(shù)據(jù)刪除方法和基于關(guān)聯(lián)規(guī)則的海量重復數(shù)據(jù)消除方法作為對比，共同完成性能驗證。

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

(3)

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

4.2 消除效果對比分析

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

圖6 重復數(shù)據(jù)消除比率對比圖

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

4.3 消除時長對比分析

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

圖7 重復數(shù)據(jù)消除時長對比圖

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

5 結(jié)束語

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