楊美艷，徐慶增

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

1 引言

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

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

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

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

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

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

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

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

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

F={f1，f2，…，fn}

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

仿真的硬件環(huán)境為：英特爾至強(qiáng)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)計(jì)表

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

為了評(píng)估不同的重復(fù)數(shù)據(jù)消除方法的性能，將評(píng)估指標(biāo)設(shè)定為分塊大小的標(biāo)準(zhǔn)方差，表達(dá)式如下

(3)

其中，分塊大小的標(biāo)準(zhǔn)方差為σ，分塊個(gè)數(shù)為N，實(shí)際分塊大小為xi，期望分塊大小為μ。

4.2 消除效果對(duì)比分析

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

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

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

4.3 消除時(shí)長(zhǎng)對(duì)比分析

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

圖7 重復(fù)數(shù)據(jù)消除時(shí)長(zhǎng)對(duì)比圖

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

5 結(jié)束語(yǔ)

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