云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)的研究與設(shè)計(jì)

　　隨著各行各業(yè)信息化的要求越來越高，需要存儲(chǔ)的數(shù)據(jù)量越來越龐大，然而，已經(jīng)存儲(chǔ)的數(shù)據(jù)中有相當(dāng)一部分是重復(fù)的，這樣既浪費(fèi)存儲(chǔ)空間又增加了存儲(chǔ)的工作量。為了緩解存儲(chǔ)系統(tǒng)的空間增長(zhǎng)問題，重復(fù)數(shù)據(jù)刪除技術(shù)已成為一個(gè)熱門的研究課題。

　　云存儲(chǔ)技術(shù)以提供數(shù)據(jù)存儲(chǔ)服務(wù)來解決存儲(chǔ)設(shè)備管理維護(hù)、安全穩(wěn)定和成本問題，實(shí)現(xiàn)存儲(chǔ)設(shè)備向存儲(chǔ)服務(wù)的轉(zhuǎn)變。重復(fù)數(shù)據(jù)刪除技術(shù)旨在消除數(shù)據(jù)大量冗余，縮減存儲(chǔ)空間。兩種技術(shù)的結(jié)合，充分將兩種技術(shù)的優(yōu)勢(shì)發(fā)揮得淋漓盡致，既能將海量數(shù)據(jù)存儲(chǔ)在云端，又能充分利用云端的存儲(chǔ)資源。兩者結(jié)合有很大的應(yīng)用價(jià)值。

　　本文通過研究重復(fù)數(shù)據(jù)刪除和云存儲(chǔ)，提出了一個(gè)基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)， 使得海量數(shù)據(jù)能夠存儲(chǔ)在云中并且擁有重復(fù)數(shù)據(jù)刪除的能力。它采用In-line方式對(duì)文件進(jìn)行數(shù)據(jù)塊級(jí)與字節(jié)級(jí)相結(jié)合的重復(fù)數(shù)據(jù)刪除，使用MD5算法計(jì)算數(shù)據(jù)塊的哈希值并與已存在的數(shù)據(jù)哈希值對(duì)比來判斷上傳的數(shù)據(jù)是否存在于云中。

　　1.云存儲(chǔ)簡(jiǎn)介

　　云存儲(chǔ)是在云計(jì)算（cloud computing）概念上延伸和發(fā)展出來的一個(gè)新的概念，是指通過集群應(yīng)用、網(wǎng)格技術(shù)和分布式文件系統(tǒng)等功能將網(wǎng)絡(luò)中大量各種不同類型的存儲(chǔ)設(shè)備通過應(yīng)用軟件集合起來協(xié)同工作，共同對(duì)外提供數(shù)據(jù)存儲(chǔ)和業(yè)務(wù)訪問功能的一個(gè)系統(tǒng)。

　　1.1 云存儲(chǔ)結(jié)構(gòu)模型

　　云存儲(chǔ)是一個(gè)網(wǎng)絡(luò)設(shè)備、存儲(chǔ)設(shè)備、服務(wù)器、應(yīng)用軟件、公用訪問接口、接入網(wǎng)、和客戶端程序等多個(gè)部分組成的復(fù)雜系統(tǒng)。各部分以存儲(chǔ)設(shè)備為核心，通過應(yīng)用軟件來對(duì)外提供數(shù)據(jù)存儲(chǔ)和業(yè)務(wù)訪問服務(wù)。現(xiàn)有的云存儲(chǔ)結(jié)構(gòu)模型如圖1所示。

圖1 云存儲(chǔ)結(jié)構(gòu)模型圖

　　1.2 云存儲(chǔ)與重復(fù)數(shù)據(jù)刪除

　　云存儲(chǔ)是將使用了彈性配置和按需付費(fèi)的因特網(wǎng)技術(shù)的可擴(kuò)展、彈性的存儲(chǔ)能力作為一種服務(wù)在服務(wù)提供商和用戶之間傳輸。因?yàn)樵拼鎯?chǔ)提供了完整和安全的訪問控制機(jī)制， 所以大部分用戶都愿意將數(shù)據(jù)存儲(chǔ)任務(wù)交予云存儲(chǔ)。

　　重復(fù)數(shù)據(jù)刪除是高性能和高效存儲(chǔ)的一種有效途徑，尤其是在云計(jì)算環(huán)境下使用。這是因?yàn)榉?wù)的存儲(chǔ)空間可能成為成本負(fù)擔(dān)，利用存儲(chǔ)效率技術(shù)（如重復(fù)數(shù)據(jù)刪除）的能力逐漸成為判斷服務(wù)是否合格的一個(gè)關(guān)鍵指標(biāo)。

　　2.重復(fù)數(shù)據(jù)刪除技術(shù)分析

　　2.1 重復(fù)數(shù)據(jù)刪除策略分析

　　目前重復(fù)數(shù)據(jù)策略主要分為三種： 文件級(jí)的重復(fù)數(shù)據(jù)刪除，數(shù)據(jù)塊級(jí)的重復(fù)數(shù)據(jù)刪除和字節(jié)級(jí)的重復(fù)數(shù)據(jù)刪除。它們根據(jù)檢測(cè)刪除重復(fù)數(shù)據(jù)的單位不同而不同。通過研究和比較發(fā)現(xiàn)，文件級(jí)刪除策略雖然計(jì)算速度快，但粒度太粗無法精確識(shí)別重復(fù)數(shù)據(jù)。數(shù)據(jù)塊級(jí)刪除策略較精確，但因?yàn)橐詳?shù)據(jù)塊為單位故需計(jì)算的哈希值較多，且可能產(chǎn)生哈希沖突。字節(jié)級(jí)刪除策略以字節(jié)為單位進(jìn)行對(duì)比不涉及哈希算法，所以可以避免碰撞，能夠?qū)崿F(xiàn)更高的精度，但是花費(fèi)的時(shí)間太多。

　　為了保證重復(fù)數(shù)據(jù)刪除的精確性和計(jì)算時(shí)間相對(duì)平衡，本架構(gòu)選擇了數(shù)據(jù)塊級(jí)與字節(jié)級(jí)策略相結(jié)合的重復(fù)數(shù)據(jù)刪除策略。先將文件分割成數(shù)據(jù)塊，以數(shù)據(jù)塊為單位計(jì)算其哈希值。如果新數(shù)據(jù)塊的哈希值與設(shè)備散列索引中的某個(gè)散列匹配時(shí)，將新數(shù)據(jù)塊與已有的與它哈希值相同的數(shù)據(jù)塊進(jìn)行字節(jié)級(jí)的對(duì)比，若完全相同時(shí)僅存入指針并指向存儲(chǔ)相同數(shù)據(jù)塊的原始位置，否則，如果數(shù)據(jù)塊是唯一的，就被寫入磁盤，其哈希值也存入索引中。這種方法的優(yōu)點(diǎn)是有效的使用數(shù)據(jù)塊級(jí)策略的優(yōu)勢(shì)又能利用字節(jié)級(jí)策略避免哈希沖突時(shí)帶來的數(shù)據(jù)丟失。

　　2.2 重復(fù)數(shù)據(jù)刪除算法分析

　　現(xiàn)有的重復(fù)數(shù)據(jù)刪除算法大致分為兩類，分別是hash 算法和基于內(nèi)容識(shí)別的算法，與其對(duì)應(yīng)的是文件級(jí)或數(shù)據(jù)塊級(jí)的刪除策略和字節(jié)級(jí)策略。

　　Hash 算法的數(shù)學(xué)表述為： CA=Hc（content）。其中content表示任意長(zhǎng)度字符串，CA 表示經(jīng)過哈希變化之后得到的哈希值。Hash 算法在信息安全領(lǐng)域中廣泛應(yīng)用，現(xiàn)在最常用的哈希算法是MD5和SHA-1 算法。本架構(gòu)采用的是MD5 算法。

　　2.3 重復(fù)數(shù)據(jù)刪除實(shí)現(xiàn)方式分析

　　重復(fù)數(shù)據(jù)刪除主要有兩種實(shí)現(xiàn)方式—前臺(tái)處理方式和后臺(tái)處理方式。前臺(tái)采用純軟件的方式進(jìn)行，而后臺(tái)采用軟硬件相結(jié)合的方式，其中又分為In-lineDeduplication 、Post-Processing Deduplication 以及Adaptative Data Deduplication 三種。

　　通過研究比較發(fā)現(xiàn)In-line 方式更適合云存儲(chǔ)系統(tǒng)。數(shù)據(jù)傳輸之前，裝有重復(fù)數(shù)據(jù)刪除應(yīng)用程序的客戶端先對(duì)其進(jìn)行操作之后再傳給數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)處理。它在數(shù)據(jù)塊寫入前檢測(cè)是否已有相似數(shù)據(jù)塊存在，這樣可以避免磁盤數(shù)據(jù)寫入，提高云存儲(chǔ)系統(tǒng)的空間存儲(chǔ)效率并減少網(wǎng)絡(luò)傳輸。

　　2.4 小結(jié)

　　本架構(gòu)采用了數(shù)據(jù)塊級(jí)與字節(jié)級(jí)相結(jié)合的刪除策略，運(yùn)用MD5 算法對(duì)要存儲(chǔ)在云中的文件進(jìn)行In-line方式的刪除操作，是本文研究的一個(gè)創(chuàng)新點(diǎn)。較之現(xiàn)有的在云存儲(chǔ)中使用文件級(jí)或數(shù)據(jù)塊級(jí)策略的操作，精確性上有所提高；較之使用Post-processing 方式的刪除有時(shí)間和空間上的優(yōu)勢(shì)。另外，在云存儲(chǔ)上使用該方法，結(jié)合云的虛擬化和分布式計(jì)算存儲(chǔ)的特性很好的解決了In-line 方式使主機(jī)I/O 負(fù)載過大的問題。

　　3.基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)

　　基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)由兩部分組成，由于使用的是In-line 方式進(jìn)行重復(fù)數(shù)據(jù)刪除，則第一部分是安裝了重復(fù)數(shù)據(jù)刪除應(yīng)用程序的客戶端；另一部分是Hadoop Distribute File System 分布式文件系統(tǒng)和HBase數(shù)據(jù)庫(kù)系統(tǒng)?？蛻舳丝煞謩e與HDFS、HBase相互通信。

　　3.1 數(shù)據(jù)存儲(chǔ)

　　在基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)中進(jìn)行文件存儲(chǔ)時(shí)需要存儲(chǔ)兩類數(shù)據(jù)： 海量的原始數(shù)據(jù)和指針?biāo)饕畔ⅰ?br>

　　3.1.1 海量數(shù)據(jù)存儲(chǔ)

　　原始數(shù)據(jù)包括源數(shù)據(jù)塊和數(shù)據(jù)塊鏈接文件。源數(shù)據(jù)塊是指首次上傳并存儲(chǔ)在系統(tǒng)中的數(shù)據(jù)塊，數(shù)據(jù)塊鏈接文件是系統(tǒng)中已存在的數(shù)據(jù)塊再次上傳時(shí)，不再進(jìn)行存儲(chǔ)操作轉(zhuǎn)而使用鏈接文件的形式來存儲(chǔ)。每個(gè)鏈接文件都記錄了它對(duì)應(yīng)源數(shù)據(jù)塊的哈希值和邏輯路徑。

　　3.1.2 索引信息存儲(chǔ)

　　HBase 中有一張數(shù)據(jù)表來存儲(chǔ)索引信息。此表有四列，分別是hash_value，count， path 和source_file，記錄每個(gè)數(shù)據(jù)塊的哈希值，被索引值、源數(shù)據(jù)塊邏輯路徑和它隸屬的文件名。其中hash_value 是主鍵。

　　3.2 文件存儲(chǔ)

　　在基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除架構(gòu)中存儲(chǔ)文件主要分為四步：

　?、?在重復(fù)數(shù)據(jù)刪除客戶端上用戶選擇要上傳的文件，客戶端上的重復(fù)數(shù)據(jù)刪除應(yīng)用程序先將文件分割成數(shù)據(jù)塊，運(yùn)用MD5算法來計(jì)算每個(gè)數(shù)據(jù)塊的哈希值。隨之傳給HBase 進(jìn)行記錄。

　?、?Hbase 某個(gè)數(shù)據(jù)塊的hash 值，若該值不存在則將其記錄，轉(zhuǎn)向第3步；否則，HDFS 檢查此數(shù)據(jù)塊被索引值是否為0，若不為0 則count 值加1，HDFS告知客戶端此數(shù)據(jù)塊已經(jīng)存在；若為0 則轉(zhuǎn)向第3 步。count的值隨被索引的次數(shù)變動(dòng)而變動(dòng)。

　?、?HDFS 存儲(chǔ)該數(shù)據(jù)塊并且將其與鏈接文件關(guān)聯(lián)起來，同時(shí)存儲(chǔ)它的哈希值和邏輯地址。

　　④ 重復(fù)2，3步的操作直至上傳文件的所有數(shù)據(jù)塊都存儲(chǔ)完畢。其UML活動(dòng)圖如圖2所示。

圖2 云存儲(chǔ)重復(fù)數(shù)據(jù)刪除架構(gòu)中文件存儲(chǔ)的Active圖

　　3.3 文件訪問

　　當(dāng)客戶端發(fā)起訪問請(qǐng)求時(shí)，HDFS 會(huì)找到該文件各個(gè)數(shù)據(jù)塊的鏈接文件，鏈接文件將邏輯地址傳遞給HDFS。之后HDFS 詢問主節(jié)點(diǎn)數(shù)據(jù)塊的位置，客戶端得到塊地址，最后從數(shù)據(jù)節(jié)點(diǎn)中取回源數(shù)據(jù)塊。依次訪問所有數(shù)據(jù)塊完畢后訪問文件成功。訪問文件的UML活動(dòng)圖如圖3所示。

圖3 云存儲(chǔ)重復(fù)數(shù)據(jù)刪除架構(gòu)中文件訪問的Active 圖

　　3.4 文件刪除

　　一個(gè)源數(shù)據(jù)塊可以被多個(gè)鏈接文件索引，刪除鏈接文件對(duì)數(shù)據(jù)塊毫無影響。當(dāng)刪除指向的最后一個(gè)鏈接文件后，即count 值為0，源數(shù)據(jù)塊的存在也沒有了意義，所以在此時(shí)該源文件也會(huì)被刪除。系統(tǒng)中不同用戶有權(quán)利訪問相同的文件，但是不允許某個(gè)用戶刪除另一用戶分享的源文件。鏈接文件可以很好的起到保護(hù)源文件不被其他用戶刪除的作用。刪除文件主要分為三步：

　?、?HDFS命令刪除數(shù)據(jù)塊的鏈接文件。

　?、?HBase中count值減1。檢查count 若為0 則刪除該源數(shù)據(jù)塊。

　?、?重復(fù)1，2 直至要被刪除的文件所有數(shù)據(jù)塊完成刪除操作。刪除文件的UML 活動(dòng)圖如圖4所示。

圖4 云存儲(chǔ)重復(fù)數(shù)據(jù)刪除架構(gòu)中文件刪除的Active圖

　　4.測(cè)試與分析

　　在Vmware7.10workstation 上搭建起了的云存儲(chǔ)平臺(tái)。平臺(tái)中有1 臺(tái)主機(jī)和4臺(tái)虛擬機(jī)使用的主機(jī)的配置如下：CPU 為3.0GHZ，內(nèi)存4G，硬盤320G。四臺(tái)虛擬機(jī)的配置一樣，CPU2.8GHz，內(nèi)存512Mb，內(nèi)存120G。實(shí)驗(yàn)上傳了1000 個(gè)文件，共占19.8Gb。在一個(gè)普通的存儲(chǔ)系統(tǒng)中，這1000 個(gè)文件肯定會(huì)占19.8Gb 的容量；在本架構(gòu)中，存儲(chǔ)在云中的文件只占6.93Gb。在容量上確實(shí)有節(jié)省空間的效果。

　　5.結(jié)語

　　本文通過利用數(shù)據(jù)塊的hash值作為索引存儲(chǔ)在HBase來獲取高性能的查詢同時(shí)在HDFS 中使用link文件來管理海量數(shù)據(jù)來實(shí)現(xiàn)云環(huán)境下的重復(fù)數(shù)據(jù)刪除。通過數(shù)據(jù)塊級(jí)與字節(jié)級(jí)相結(jié)合的重復(fù)數(shù)據(jù)刪除策略提高了數(shù)據(jù)重復(fù)刪除粒度，減少了數(shù)據(jù)存儲(chǔ)空間，并用實(shí)驗(yàn)證明了其刪除的能力。

　　另外，基于云存儲(chǔ)的重復(fù)數(shù)據(jù)刪除比普通重復(fù)數(shù)據(jù)更有優(yōu)勢(shì)。1.重復(fù)數(shù)據(jù)刪除的關(guān)鍵技是數(shù)據(jù)分塊與數(shù)據(jù)指紋計(jì)算。雖然MD5算法的計(jì)算復(fù)雜性非常高以至于占用很多的CPU 資源，且數(shù)據(jù)指紋需要保存和檢索使得索引表越來越大。但是將重復(fù)數(shù)據(jù)刪除應(yīng)用在云存儲(chǔ)上即可以發(fā)揮云存儲(chǔ)虛擬化和云計(jì)算分布式計(jì)算的優(yōu)勢(shì)，構(gòu)建集群的重復(fù)數(shù)據(jù)刪除架構(gòu)，為用戶提供多倍的吞吐及處理能力。2.單點(diǎn)故障時(shí)其他設(shè)備可自動(dòng)接管其工作以保證處理的連續(xù)性。由于集群仍然保留的是單個(gè)Hash表所以它不僅提高了系統(tǒng)性能而且不會(huì)影響到重復(fù)數(shù)據(jù)刪除比率。3.云存儲(chǔ)融合云災(zāi)備技術(shù)可以解決軟硬件損壞造成的數(shù)據(jù)損壞和丟失問題。

來源：CIO時(shí)代網(wǎng)

　　版權(quán)及免責(zé)聲明：凡本網(wǎng)所屬版權(quán)作品，轉(zhuǎn)載時(shí)須獲得授權(quán)并注明來源“中國(guó)產(chǎn)業(yè)經(jīng)濟(jì)信息網(wǎng)”，違者本網(wǎng)將保留追究其相關(guān)法律責(zé)任的權(quán)力。凡轉(zhuǎn)載文章，不代表本網(wǎng)觀點(diǎn)和立場(chǎng)。版權(quán)事宜請(qǐng)聯(lián)系：010-65363056。

延伸閱讀