1.2.4 數(shù)據(jù)縮減技術(shù)

當(dāng)前數(shù)據(jù)量以指數(shù)級速度迅猛增長，但是數(shù)據(jù)管理投資預(yù)算的增長率遠(yuǎn)遠(yuǎn)低于數(shù)據(jù)增長速度，以至于各種存儲媒體介質(zhì)的總?cè)萘吭鲩L慢于數(shù)字世界的數(shù)據(jù)增長率，造成全世界絕大部分生成的數(shù)據(jù)無法保存起來進(jìn)行處理分析。著名國際咨詢機(jī)構(gòu)IDC公司統(tǒng)計表明2013年全世界可用的存儲容量只占整個數(shù)據(jù)產(chǎn)生量的33%，預(yù)計到2020年這個比例將降低至15%[1]。因此，提高數(shù)據(jù)存儲空間利用率的數(shù)據(jù)縮減技術(shù)對當(dāng)前大數(shù)據(jù)存儲管理至關(guān)重要。

數(shù)據(jù)縮減技術(shù)是指一類能夠有效地刪除數(shù)據(jù)冗余提升存儲空間利用率的技術(shù)，主要包括：數(shù)據(jù)壓縮（Data Compression）[9]、差分編碼（Delta Encoding）[10]和重復(fù)數(shù)據(jù)刪除（Data Deduplication）[11]這三類經(jīng)典技術(shù)。

數(shù)據(jù)壓縮是指采用編碼方式用更少的比特位來表示數(shù)據(jù)對象內(nèi)原始信息的技術(shù)。數(shù)據(jù)壓縮的方式非常多，根據(jù)壓縮后是否損失信息可分為無損壓縮和有損壓縮兩大類。無損壓縮是通過確定和刪除統(tǒng)計冗余來減少數(shù)據(jù)對象存儲的比特位。由于數(shù)據(jù)統(tǒng)計冗余度的理論限制，無損壓縮的壓縮比一般比較低，被廣泛應(yīng)用于文本數(shù)據(jù)、程序和特殊應(yīng)用場合的圖像數(shù)據(jù)等需要精確存儲數(shù)據(jù)的壓縮。典型的無損壓縮算法有：香農(nóng)-范諾編碼（Shannon-Fano coding）、霍夫曼編碼（Huffman coding）、算術(shù)編碼（arithmetic coding）、游程編碼（run-length coding）、詞典編碼（dictionary coding）等；詞典編碼算法中的Lempel-Ziv（LZ）壓縮方法[15]是最流行的無損壓縮算法，被廣泛應(yīng)用于WinRAR、GZIP和GIF等壓縮軟件。

有損壓縮通過發(fā)現(xiàn)和刪除數(shù)據(jù)對象中不重要的信息來減少存儲所需的比特位。它利用人類視覺、聽覺對圖像、聲音中的某些頻率成分不敏感的特性，允許壓縮的過程中損失一定的信息。雖然不能完全恢復(fù)原始數(shù)據(jù)，但是所損失的部分對理解原始圖像的影響較小，卻換來了比較大的壓縮比，被廣泛應(yīng)用于語音、圖像和視頻數(shù)據(jù)的壓縮。由于刪除數(shù)據(jù)對象內(nèi)部冗余的本質(zhì)，數(shù)據(jù)壓縮僅能獲得有限的數(shù)據(jù)縮減率。經(jīng)典的有損壓縮算法有：圖像壓縮領(lǐng)域的JPEG標(biāo)準(zhǔn)和視頻壓縮領(lǐng)域的MPEG標(biāo)準(zhǔn)等。

差分編碼是通過開發(fā)數(shù)據(jù)對象間相似性來壓縮數(shù)據(jù)對象存儲空間的技術(shù)。它能夠定位兩個相似的數(shù)據(jù)對象中的共同數(shù)據(jù)內(nèi)容，并按它們存儲的先后分為舊版本和新版本。通過差分算法可以獲得反映數(shù)據(jù)對象新舊版本之間差異的Delta對象，數(shù)據(jù)對象的新版本可以由它們之間差異的數(shù)據(jù)內(nèi)容與舊版本聯(lián)合生成。由于Delta對象編碼后往往可以遠(yuǎn)小于原數(shù)據(jù)對象，Delta編碼能夠有效地縮減數(shù)據(jù)對象的存儲空間。為了確定兩個數(shù)據(jù)對象是否相似的算法有很多，比如計算數(shù)據(jù)對象內(nèi)所有固定窗口內(nèi)容中的弱哈希值，選取幾個最小或最大的哈希值作為特征來比較和判斷兩個數(shù)據(jù)對象是否相似。如果兩個數(shù)據(jù)對象有相同的相似特征則認(rèn)為它們的內(nèi)容十分相似。相比于數(shù)據(jù)壓縮，Delta編碼通過額外的計算開銷和內(nèi)存資源開銷能夠發(fā)現(xiàn)和消除更多的數(shù)據(jù)冗余。

重復(fù)數(shù)據(jù)刪除技術(shù)是一種能消除粗粒度數(shù)據(jù)冗余的特殊數(shù)據(jù)縮減技術(shù)，被廣泛應(yīng)用于基于硬盤的備份系統(tǒng)。它通過將數(shù)據(jù)流劃分為若干數(shù)據(jù)對象，并對各個數(shù)據(jù)對象進(jìn)行加密哈希指紋計算，基于數(shù)據(jù)對象指紋的索引查詢檢測出數(shù)據(jù)流中相同的數(shù)據(jù)對象，只傳輸或者存儲唯一的數(shù)據(jù)對象副本，并使用指向唯一副本的指針替換其他副本。基于不同的區(qū)分原則，我們可以對重復(fù)數(shù)據(jù)刪除技術(shù)進(jìn)行不同的分類。根據(jù)進(jìn)行重復(fù)數(shù)據(jù)刪除操作位置的不同，可以分為源端重復(fù)數(shù)據(jù)刪除和目標(biāo)端重復(fù)數(shù)據(jù)刪除。根據(jù)進(jìn)行重復(fù)數(shù)據(jù)刪除操作時機(jī)的不同，可以分為在線重復(fù)數(shù)據(jù)刪除和離線重復(fù)數(shù)據(jù)刪除。按進(jìn)行重復(fù)數(shù)據(jù)刪除操作粒度的差異，可以分為文件級、塊級和字節(jié)／比特位級重復(fù)數(shù)據(jù)刪除。根據(jù)進(jìn)行重復(fù)數(shù)據(jù)刪除處理的節(jié)點數(shù)目差異，可以分為單節(jié)點重復(fù)數(shù)據(jù)刪除和分布式重復(fù)數(shù)據(jù)刪除。根據(jù)重復(fù)數(shù)據(jù)刪除操作范圍的不同，可以分為全局重復(fù)數(shù)據(jù)刪除和局部重復(fù)數(shù)據(jù)刪除。根據(jù)重復(fù)數(shù)據(jù)匹配效果的差異，可以分為精確重復(fù)數(shù)據(jù)刪除和近似重復(fù)數(shù)據(jù)刪除。目前，重復(fù)數(shù)據(jù)刪除技術(shù)不僅應(yīng)用于備份、容災(zāi)和歸檔等二級存儲中，還應(yīng)用于虛擬化環(huán)境下的主存儲系統(tǒng)。

如圖1-7所示，數(shù)據(jù)縮減技術(shù)可以將數(shù)據(jù)集中重復(fù)數(shù)據(jù)塊、相似數(shù)據(jù)塊甚至重復(fù)字節(jié)分別通過重復(fù)數(shù)據(jù)刪除、Delta編碼和壓縮分別進(jìn)行存儲空間縮減。在邏輯空間內(nèi)，文件1劃分為1號和2號數(shù)據(jù)塊，文件2劃分為3號、4號、5號數(shù)據(jù)塊，塊2和塊3內(nèi)容相同，塊1和塊5相似，塊4含有大量重復(fù)字節(jié)。在物理空間里，重復(fù)數(shù)據(jù)刪除可以避免存儲塊2，差分壓縮可以根據(jù)塊5計算出塊1的差分塊，只需對差分塊進(jìn)行壓縮存儲，并可與塊4的壓縮內(nèi)容存儲在同一數(shù)據(jù)塊空間內(nèi)。

圖1-7 數(shù)據(jù)縮減技術(shù)原理

隨著人們不斷利用其數(shù)據(jù)縮減優(yōu)勢來改進(jìn)和優(yōu)化現(xiàn)有存儲和網(wǎng)絡(luò)系統(tǒng)，數(shù)據(jù)縮減技術(shù)的應(yīng)用將會越來越廣泛。近年來，工業(yè)界和學(xué)術(shù)界都對數(shù)據(jù)縮減技術(shù)進(jìn)行了深入的探討和研究，其應(yīng)用范圍正在從二級存儲向主存儲延伸，從存儲領(lǐng)域向通信領(lǐng)域擴(kuò)展。隨著綠色I(xiàn)T進(jìn)程的不斷推進(jìn)，數(shù)據(jù)縮減技術(shù)已成為云計算中的核心技術(shù)。比較傳統(tǒng)的數(shù)據(jù)壓縮技術(shù)，重復(fù)數(shù)據(jù)刪除技術(shù)不僅可以消除數(shù)據(jù)對象內(nèi)部的冗余，還能消除數(shù)據(jù)對象之間的冗余。而相比于差分編碼，重復(fù)數(shù)據(jù)刪除能夠以更低的系統(tǒng)開銷獲得高數(shù)據(jù)縮減率。