[發(fā)明專利]一種適應(yīng)大數(shù)據(jù)應(yīng)用的快速重復(fù)數(shù)據(jù)刪除方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310228696.9
• 申請(qǐng)日: 2013-06-08
• 公開（公告）號(hào): CN103324699A
• 公開（公告）日: 2013-09-25
• 發(fā)明（設(shè)計(jì)）人: 張興軍;朱國(guó)峰;董小社;朱躍光;王龍翔;姜曉夏
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06F11/14
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 蔡和平

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

本發(fā)明屬于計(jì)算機(jī)信息存儲(chǔ)技術(shù)領(lǐng)域，特別涉及一種適應(yīng)大數(shù)據(jù)應(yīng)用的快速重復(fù)數(shù)據(jù)刪除方法。

背景技術(shù)

信息時(shí)代，隨著數(shù)據(jù)的裂變式增長(zhǎng)，導(dǎo)致大數(shù)據(jù)時(shí)代來臨。所謂大數(shù)據(jù)，即滿足以下特點(diǎn)：數(shù)據(jù)體量巨大、類型繁多、價(jià)值密度低和產(chǎn)生速度快等。大數(shù)據(jù)時(shí)代，在數(shù)據(jù)的備份和存儲(chǔ)過程中存在著大量冗余數(shù)據(jù)，如何消除備份過程中的重復(fù)數(shù)據(jù)以減少存儲(chǔ)空間和網(wǎng)絡(luò)帶寬消耗已經(jīng)成為存儲(chǔ)領(lǐng)域一個(gè)熱門研究課題。

消除備份過程中的冗余數(shù)據(jù)最有效的方式是采用重復(fù)數(shù)據(jù)刪除技術(shù)。一般認(rèn)為，重復(fù)數(shù)據(jù)刪除技術(shù)包括面向文件級(jí)別的全文件去重技術(shù)和面向塊級(jí)別的固定長(zhǎng)度分塊技術(shù)及變長(zhǎng)分塊去重技術(shù)。全文件去重技術(shù)通過比較文件的元數(shù)據(jù)信息，對(duì)整個(gè)文件進(jìn)行去重檢測(cè)，僅存儲(chǔ)多個(gè)相同文件中的一個(gè)副本，冗余文件通過指針映射到該副本文件。其僅能識(shí)別文件之間的冗余數(shù)據(jù)，去重速率快但去重率低，較適用于E-mail系統(tǒng)、文件系統(tǒng)等存在大量相同文件的應(yīng)用環(huán)境中。固定長(zhǎng)度分塊去重技術(shù)通告一個(gè)固定長(zhǎng)度對(duì)文件流進(jìn)行分塊，計(jì)算分塊后的hash值，然后通過查找hash表對(duì)hash值進(jìn)行去重檢測(cè)，存儲(chǔ)節(jié)點(diǎn)僅存儲(chǔ)hash值不存在的數(shù)據(jù)塊。其可同時(shí)識(shí)別文件內(nèi)部和文件之間的冗余數(shù)據(jù)，但對(duì)數(shù)據(jù)修改敏感，即數(shù)據(jù)一經(jīng)修改便無法有效檢測(cè)出冗余信息，去重速率快但去重率仍偏低。變長(zhǎng)分塊技術(shù)主要是指一種基于內(nèi)容識(shí)別的分塊技術(shù)，它由一個(gè)固定大小窗口按字節(jié)在文件流上滑動(dòng)，每滑動(dòng)一個(gè)字節(jié)計(jì)算一次該窗口內(nèi)數(shù)據(jù)的弱hash值，同時(shí)判斷該弱hash值是否滿足預(yù)先設(shè)定的條件，若滿足，則記錄該偏移位置，并且設(shè)其為一個(gè)邊界點(diǎn)；否則，繼續(xù)滑動(dòng)窗口。直到找到兩個(gè)邊界點(diǎn)，取兩個(gè)邊界點(diǎn)之間的數(shù)據(jù)形成一個(gè)數(shù)據(jù)塊，計(jì)算該數(shù)據(jù)塊的強(qiáng)hash值，然后對(duì)該強(qiáng)hash值進(jìn)行去重檢測(cè)，僅存儲(chǔ)該hash值不存在的數(shù)據(jù)塊且更新hash表。其針對(duì)易修改數(shù)據(jù)，能夠有效檢測(cè)出冗余數(shù)據(jù)，但由于窗口滑動(dòng)過程中頻繁計(jì)算指紋值，去重速率低，不適宜大數(shù)據(jù)應(yīng)用環(huán)境。

綜上所述，上述去重方法均有自己的局限性，單一的去重方法不能有效適應(yīng)復(fù)雜多變的應(yīng)用環(huán)境。

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

本發(fā)明針對(duì)復(fù)雜多變的備份應(yīng)用環(huán)境，提出了一種適應(yīng)大數(shù)據(jù)應(yīng)用的快速重復(fù)數(shù)據(jù)刪除方法，通過調(diào)節(jié)去重因子和加速因子，可以快速消除文件內(nèi)部和文件之間的冗余數(shù)據(jù)，從而降低了備份去重系統(tǒng)的備份窗口和存儲(chǔ)開銷。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

一種適應(yīng)大數(shù)據(jù)應(yīng)用的快速重復(fù)數(shù)據(jù)刪除方法，包括以下步驟：

（1）用戶定制備份任務(wù)，形成備份文件流；

（2）通過一個(gè)固定長(zhǎng)度窗口在備份文件流上按字節(jié)進(jìn)行滑動(dòng)，每滑動(dòng)一個(gè)字節(jié)就采用RabinHash函數(shù)計(jì)算一次窗口內(nèi)數(shù)據(jù)指紋值，記為rhashvalue；

（3）判斷步驟（2）所計(jì)算的指紋值是否滿足邊界點(diǎn)條件：rhashvalue%D=r；其中，D為除數(shù)，其值隨機(jī)確定；r為模數(shù)，取值為D-1；若不滿足，則轉(zhuǎn)入步驟（2）繼續(xù)進(jìn)行滑動(dòng)窗口；若滿足，則轉(zhuǎn)入步驟（4）；

（4）以步驟（3）找到的滿足邊界點(diǎn)條件的窗口位置為界對(duì)備份文件流進(jìn)行劃分，形成CDC變長(zhǎng)塊，同時(shí)記錄變長(zhǎng)塊個(gè)數(shù)以及當(dāng)前邊界點(diǎn)位置，同時(shí)進(jìn)入步驟（5）和（8）；

（5）判斷備份文件流是否劃分結(jié)束，若結(jié)束，則整個(gè)分塊過程結(jié)束；若未結(jié)束，則進(jìn)入步驟（6）；

（6）判斷CDC變長(zhǎng)塊個(gè)數(shù)是否等于去重因子，若不相等，則轉(zhuǎn)入步驟（2）繼續(xù)滑動(dòng)窗口；若相等，則進(jìn)入步驟（7）；

（7）清零CDC變長(zhǎng)塊個(gè)數(shù)，即重新開始計(jì)數(shù)，并且從上一個(gè)劃分的塊的邊界點(diǎn)位置開始按加速因子進(jìn)行固定長(zhǎng)度分塊，同時(shí)進(jìn)入步驟（5）和步驟（8）；

（8）計(jì)算CDC變長(zhǎng)塊或定長(zhǎng)塊hash值，并進(jìn)入步驟（9）去重檢測(cè)過程；

（9）檢索hash表，查詢hash值是否存在，若存在，則更新hash表對(duì)應(yīng)hash值引用次數(shù)；若不存在，則存儲(chǔ)hash值及相應(yīng)數(shù)據(jù)塊內(nèi)容。

本發(fā)明進(jìn)一步的改進(jìn)在于：步驟（2）中所述固定長(zhǎng)度窗口的長(zhǎng)度為48bytes或50bytes。

本發(fā)明進(jìn)一步的改進(jìn)在于：步驟（6）中所述去重因子為1、2、3或4。

本發(fā)明進(jìn)一步的改進(jìn)在于：步驟（7）中所述加速因子為4KB、8KB、16KB、32KB、64KB或128KB。

本發(fā)明一種適應(yīng)大數(shù)據(jù)應(yīng)用的快速重復(fù)數(shù)據(jù)刪除方法中分塊具體為：

（1）在定制備份任務(wù)過程中，用戶根據(jù)其當(dāng)前應(yīng)用環(huán)境設(shè)置不同的去重因子和加速因子（去重因子范圍為1～4，與去重率成正比；加速因子范圍為8KB～128KB，與備份窗口成反比）；