內容分塊算法中預期分塊長度對重復數據刪除率的影響

王龍翔,董小社,張興軍,王寅峰,公維峰,魏曉林

(1.西安交通大學電子與信息工程學院,710049,西安;2.深圳信息職業技術學院軟件學院,518172,廣東深圳;3.浪潮集團高效能服務器和存儲技術國家重點實驗室,250101,濟南)

?

內容分塊算法中預期分塊長度對重復數據刪除率的影響

王龍翔1,董小社1,張興軍1,王寅峰2,公維峰3,魏曉林1

(1.西安交通大學電子與信息工程學院,710049,西安;2.深圳信息職業技術學院軟件學院,518172,廣東深圳;3.浪潮集團高效能服務器和存儲技術國家重點實驗室,250101,濟南)

針對基于內容分塊重復數據刪除方法缺少能夠定量分析預期分塊長度與重復數據刪除率之間關系的數學模型,導致難以通過調整預期分塊長度優化重復數據刪除率的問題,提出了一種基于Logistic函數的數學模型。在大量真實數據測觀察基礎上,提出了通過Logistic函數描述非重復數據的“S”形變化趨勢,解決了該數據難以從理論上推導、建模的問題,證明了基于內容分塊過程服從二項分布,并從理論上推導出了元數據大小模型。基于上述兩種數據模型,通過數學運算最終推導得到重復數據刪除率模型,并利用收集到的3組真實數據集對模型進行了實驗驗證。實驗結果表明:反映數學模型擬合優度的R2值在0.9以上,說明該模型能夠準確地反映出預期分塊長度與重復數據刪除率之間的數學關系。該模型為進一步研究如何通過調整預期分塊長度使重復數據刪除率最優化提供了理論基礎。

基于內容分塊;重復數據刪除率;Logistic函數

重復數據刪除是一種數據精簡技術,是應對大數據時代下數據存儲規模越來越龐大這一問題的重要解決方案,目前在備份、歸檔等二級存儲系統中得到了廣泛應用[1-5],并有逐漸在文件系統等主存儲系統中大量應用的趨勢[6-7]。基于內容的分塊算法[8]能夠避免數據更新敏感問題,顯著提高重復數據識別效率,是目前基于重復數據刪除存儲系統應用最廣泛的分塊算法。重復數據刪除率反映了重復數據刪除能夠消除的重復數據比例,是衡量重復數據刪除去重效果的基本指標,因此,提高重復數據刪除率成為了一項重要研究。在進行重復數據刪除后主要需要存儲兩類數據:非重復數據與元數據。非重復數據是指經過重復數據檢測被判定為存儲系統尚未存儲過的數據;元數據是為了重構數據流需要保存的數據塊在存儲系統中的地址信息。預期分塊長度是基于內容分塊算法中需要預先設置的參數值,該值設置越小,所形成的數據塊粒度越小,重復數據檢測效率越高,但是也會產生更多的分塊,使得元數據存儲大小增加。因此,預期分塊長度會顯著影響重復數據刪除率,該參數是基于內容分塊算法中需要預先設置的一個重要參數[9],研究者指出通過合理設置預期分塊長度能夠顯著提高重復數據刪除率[10]。然而,已有研究主要通過改進基于內容分塊算法來提高重復數據刪除率,如何合理設置預期分塊長度以提高重復數據刪除率,卻未引起研究者的重視。目前,研究者普遍根據經驗認為4 kB[11]或者8 kB[5,8,12-13]是預期分塊長度的合理值,但是這種設置方法既缺少理論上的證明也沒有通過真實數據集進行驗證。為了驗證預期分塊長度設置為4 kB或者8 kB在實際中能否使重復數據刪除率最優,本文收集了3組真實數據集用于實驗驗證,分別為:①Linux內核源代碼;②維基百科網頁轉儲數據;③SQLite備份數據集。實驗結果表明,預期分塊長度設置為4 kB或者8 kB并不能使重復數據刪除率最優。為了揭示預期分塊長度與重復數據刪除率之間隱含的數學關系從而更加合理地設置預期分塊長度,本文提出了一種基于Logistic函數的數學模型描述預期分塊長度與重復數據刪除率之間的數學關系。基于3組真實數據集對數學模型進行了驗證,結果表明,反映數學模型擬合優度的R2值基本在0.9以上,說明本文數學模型能夠準確地描述預期分塊長度與重復數據刪除率之間的關系。

1 基于內容分塊算法的原理

基于內容分塊算法的主要原理如圖1所示。通過設置大小為48 B的滑動窗口,從數據流的起始處開始滑動,并計算窗口內數據的Rabin指紋值[14];通過將Rabin指紋值和掩碼值進行“與”操作,判斷所得結果是否等于一個預先設定的魔數。如果以上條件成立,則將當前窗口的最后一個字節作為分塊的邊界點,當窗口在數據流中滑動結束后,所形成的邊界點將數據流劃分為長度不同的一系列數據塊集合。為了避免出現分塊過大或過小的情況,可設置分塊大小的最小值與最大值,當分塊大小小于最小值時,舍棄當前邊界點;當分塊大小大于最大值時,強制設置當前窗口最后一個字節為邊界點。

在基于內容分塊算法中,預期分塊長度μ由掩碼長度x決定,兩者存在指數關系。

圖1 基于內容分塊算法的原理

2 重復數據刪除率與預期分塊長度的建模

在進行重復數據刪除后需要存儲的數據為:①非重復數據塊,即經過基于內容分塊算法分塊后判定為尚未存儲過的數據塊;②元數據,為了重構數據流需要保存的數據塊實際存儲地址信息。③指紋值,所有非重復數據塊對應的MD5/SHA-1指紋值信息。與前兩種數據相比,由于指紋值存儲空間很小,對重復數據刪除率的影響可忽略不計,因此本文的建模中忽略指紋值。

2.1 元數據大小建模

經過分塊算法對數據流進行切分后所形成的每一個數據塊,無論其是否重復都需要保存對應的元數據信息。元數據主要是當前數據塊在重復數據刪除系統中的實際存儲地址信息,用于在系統進行恢復時取回對應的數據塊。數據流對應的元數據數量Nm等于總分塊數量

(1)

式中:So代表原始數據大小;μ代表預期分塊長度;x代表基于內容分塊算法中設置的掩碼長度。

假設每條元數據大小為m,則元數據大小為

(2)

2.2 非重復數據大小建模

非重復數據大小與預期分塊長度之間的關系無法從理論上直接進行推導。本文通過對大量真實數據集進行實驗觀察后發現:非重復數據與預期分塊長度之間的關系曲線呈現S型,增長率表現出先急后緩的趨勢,并且曲線有上界,該曲線符合Logistic函數曲線的特征。圖2是本文所觀察的真實數據集中非重復數據大小與預期分塊長度(該長度是掩碼長度的指數函數)之間關系曲線的典型代表,3組數據分別是Linux內核310個版本數據、維基百科網站12次轉儲數據、SQLite 90次備份數據。

Logistic函數的定義為

Logistic(x)=L/(1+exp(-k(x-x0)))

(3)

式中:L是Logistic函數的上界;k為函數陡峭程度;x0是函數增長率發生變化的橫坐標值。

在基于內容分塊算法中,非重復數據大小的上界為去重前的數據大小So,因此,非重復數據大小Su的數學模型為

(4)

2.3 重復數據刪除率建模

進行重復數據刪除處理后需要存儲的數據總大小Sd等于元數據大小Sm與非重復數據大小Su之和,其數學關系為

Sd=Su+Sm=

(5)

根據重復數據刪除率的定義,可推導重復數據刪除率D與預期分塊長度μ關系的數學模型為

(6)

(a)Linux內核數據集3.0～3.5.2

(b)維基百科數據集

(c)SQLite數據集圖2 真實數據集中非重復數據大小與基于內容分塊算法中設置的掩碼長度之間的關系

式中:m為單個元數據大小,其數值取決于具體的系統實現,為常量。k與x0在式(6)中屬于需要確定的參數。式(6)分母中1/(1+exp(-k(x-x0)))隨著x的增大而增大,m/2x隨著x的增大而減小,并且減小速率會逐漸變小。因此,式(6)分母的變化趨勢在x值較小時由m/2x決定,隨著x的增大而減小;之后由1/(1+exp(-k(x-x0)))決定,隨著x的增大而增大。D則先隨著x的增大而增大,后隨著x的增大而減小。這種變化趨勢符合實際中重復數據刪除率的變化規律,因此,從理論上分析,式(6)可作為重復數據刪除的數學模型。

3 實 驗

3.1 實驗環境

本文采用開源重復數據刪除軟件deduputil[15]作為測試程序,deduputil軟件支持多種分塊方式,包括基于內容分塊。

測試所使用服務器配置為:2個IntelE5-2650v2(2.6GHz/8c)/8GT/20M處理器;128GBDDR3內存;1.2TMLCSSDPCIe接口磁盤;CentOSrelease6.5(Final)操作系統。

3.2 數據集

本文收集了3組真實數據集用于實驗測試,分別為:①Linux內核源碼數據集[16],總大小為233.95GB,包括版本3.0～3.4.63,共260個版本;②維基百科轉儲數據集[17],來自于Wikipedia網站部分頁面定期的轉儲數據,總大小為11GB,共12次轉儲;③SQLite備份數據集[18],即SQLite數據庫在運行TPC-C[19]測試程序后自動備份得到的數據集,總大小為148GB,共90次備份。

由于真實存儲系統中數據規模會不斷增大,為了更全面地觀察實驗結果,本文模擬了真實存儲系統中數據的特點,將3組數據集的數據規模由小到大分別進行了測試。在Linux內核測試中,將前60個版本作為第一次測試,之后每間隔100個版本進行一次測試,即分別測試前60個版本,前160個版本,最后的260個版本;Wikipedia數據集前4個轉儲數據作為第一次測試,之后每間隔4個轉儲數據進行一次測試;SQLite數據集前10個備份數據作為第一次測試,之后每間隔40個備份數據進行一次測試。在基于內容的分塊算法中需要設置分塊最小值與最大值參數,本文設置最小值為64B,最大值為32MB。因此,實驗中設置需要觀察的預期分塊長度范圍為64B～32MB,對應x范圍為5～25。

3.3 實驗結果

實驗結果如圖3～5所示,結果表明:在所有測試中,將預期分塊長度設置為4kB或者8kB都不能使重復數據刪除率最優。此外,實驗結果還表明,不同類型數據集,重復數據刪除率最優的預期分塊長度不同,即使同一類型數據集,隨著數據規模的增大,最優重復數據刪除率對應的預期分塊長度也會發生變化,因此,按照經驗將預期分塊長度設置為某個固定值無法使重復數據刪除率最優。

本文通過R2值反映所提出重復數據刪除率數學模型與實際曲線的擬合程度,其取值范圍為0～1,越接近于1說明數學模型擬合效果越好。圖3～5表明,測試結果的R2值均在0.9以上,并且數據規模越大,擬合程度越高,說明本文所提出的重復數據刪除率的數學模型能夠準確反映出真實數據集中重復數據刪除率與預期分塊長度之間的數學關系。

(a)Linux內核源碼3.0～3.0.60 (b)Linux內核源碼3.0～3.2.47 (c)Linux內核源碼3.0～3.4.63(共60個版本),R2=0.986 (共160個版本),R2=0.995 (共260個版本),R2=0.955圖3 Linux內核數據集實驗結果

(a)4次轉儲數據集,R2=0.920 (b)8次轉儲數據集,R2=0.944 (c)12次轉儲數據集,R2=0.951圖4 維基百科轉儲數據集實驗結果

(a)10次備份數據集,R2=0.977 (b)50次備份數據集,R2=0.991 (c)90次備份數據集,R2=0.993圖5 SQLite備份數據集實驗結果

4 結 論

本文通過3組真實數據集Linux內核源代碼、維基百科轉儲數據、SQLite備份數據,對目前研究者認為合理的預期分塊長度值4 kB以及8 kB進行了實驗驗證,結果表明4 kB或者8 kB不能使基于內容分塊算法的重復數據刪除率最優。為了揭示預期分塊長度與重復數據刪除率之間隱含的數學關系,從而合理設置預期分塊長度值,本文提出了一種基于Logistic函數的數學模型來描述預期分塊長度與重復數據刪除率之間的數學關系,并基于3組真實數據集對數學模型進行了驗證。實驗結果表明,反映數學模型擬合優度的R2值在0.9以上,說明所提數學模型能夠準確地描述預期分塊長度與重復數據刪除率之間的關系。該模型為將來進一步研究能使重復數據刪除率接近最優的預期分塊長度設置方法奠定了理論基礎。

[1] EMC. EMC data domain white paper [EB/OL]. (2014-07-01)[2016-04-20]. http: ∥www.emc.com/collateral/software/white-papers/h7219-data-domain-data-invul-arch-wp.pdf.

[2] DUBNICKI C, GRYZ L, HELDT L, et al. Hydrastor: a scalable secondary storage [C]∥Proceedings of the USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2009: 197-210.

[3] 王龍翔, 張興軍, 朱國峰, 等. 重復數據刪除中的無向圖遍歷分組預測方法 [J]. 西安交通大學學報, 2013, 47(10): 51-56. WANG Longxiang, ZHANG Xingjun, ZHU Guofeng, et al. A grouping prediction method based on undirected graph traversal in de-duplication system [J]. Journal of Xi’an Jiaotong University, 2013, 47(10): 51-56.

[4] QUINLAN S, DORWARD S. Venti: a new approach to archival data storage [C]∥Proceedings of the First USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2002: 89-101.

[5] MIN J, YOON D, WON Y. Efficient deduplication techniques for modern backup operation [J]. IEEE Transactions on Computers, 2011, 60(6): 824-840.

[6] TSUCHIYA Y, WATANABE T. DBLK: deduplication for primary block storage [C]∥Proceedings of the Symposium on Mass Storage Systems. Piscataway, NJ, USA: IEEE, 2011: 1-5.

[7] SRINIVASAN K, BISSON T, GOODSON G, et al. iDedup: latency-aware, inline data deduplication for primary storage [C]∥Proceedings of the USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2012: 24-35.

[8] MUTHITACHAROEN A, CHEN B, MAZIERES D. A low-bandwidth network file system [C]∥Proceedings of the 18th ACM Symposium on Operating Systems Principles. New York, USA: ACM, 2001: 174-187.

[9] YOU L L, KARAMANOLIS C. Evaluation of efficient archival storage techniques [C]∥Proceedings of the 21st IEEE/12th NASA Goddard Conference on Mass Storage Systems and Technologies. Piscataway, NJ, USA: IEEE, 2004: 227-232.

[11]LILLIBRIDGE M, ESHGHI K, BHAGWAT D, et al. Sparse indexing: large scale, inline deduplication using sampling and locality [C]∥Proceedings of the USENIX Conference on File and Storage Technologies. Berkeley, CA, USA: USENIX Association, 2009: 111-123.

[12]DEBNATH B, SENGUPTA S, LI J. ChunkStash: speeding up inline storage deduplication using flash memory [C]∥Proceedings of the 2010 USENIX Conference on USENIX Annual Technical Conference. Berkeley, CA, USA: USENIX Association, 2010: 1-16.

[13]付印金, 肖儂, 劉芳, 等. 基于重復數據刪除的虛擬桌面存儲優化技術 [J]. 計算機研究與發展, 2012, 49(S1): 125-130. FU Yinjin, XIAO Nong, LIU Fang, et al. Deduplication based storage optimization technique for virtual desktop [J]. Journal of Computer Research and Development, 2012, 49(S1): 125-130.

[14]RABIN M O. Department of computer science: TR-15-81 [R]. Cambridge, MA, USA: Havard University, 1981.

[15]LIU A. Dedup util homepage [EB/OL]. (2010-06-07)[2016-04-20]. http: ∥sourceforge.net/projects/dedu putil/.

[16]TORVALDS L. The linux kernel archives. [EB/OL]. (2016-04-02)[2016-04-20]. http: ∥kernel.org/.

[17]WIKIPEDIA. Svwiki dump [EB/OL]. (2016-01-11)[2016-04-20]. http: ∥dumps.wikimedia.org/svwiki/.

[18]RICHARDHIPP D. SQLite homepage [EB/OL]. (2016-03-02)[2016-04-20]. http: ∥sqlite.org/.

[19]TPCC. TPC BENCHMARKTMC Standard Specification [EB/OL]. (2009-02-11)[2016-04-20]. http: ∥www.tpc.org/tpc_documents_current_versions/pdf/tpc-c_v5.11.0.pdf.

(編輯 武紅江)

Influence of Expected Chunk Size on Deduplication Ratio in Content Defined Chunking Algorithm

WANG Longxiang1,DONG Xiaoshe1,ZHANG Xingjun1,WANG Yinfeng2,GONG Weifeng3,WEI Xiaolin1

(1. School of Electronic and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China;2. School of Software, Shenzhen Institute of Information Technology, Shenzhen, Guangdong 518172, China;3. Inspur Group Co. Ltd., State Key Laboratory of High-End Server and Storage Technology, Jinan 250101, China)

A logistic function based mathematical model is proposed to solve the problem that, mathematical model is not used to quantitatively analyze the relationship between the expected chunk size and the deduplication ratio in the content defined chunking (CDC) based deduplication method, resulting in the difficulty in optimizing the deduplication ratio by adjusting the expected chunk size. The logistic function is used to describe the S-shaped variation trend of unique data on the basis of observation on a large number of real data sets, and the problem that the unique data is hard to be modeled by theoretical derivation is solved. It is assumed that the CDC process fits a binomial distribution, and based on the assumption two metadata models are deduced theoretically. The deduplication ratio model is finally deduced based on these two data models. Three realistic datasets are used to verify the deduplication ratio model. Experimental results show that theR2value, which denotes the goodness of fit of the model, is greater than 0.9 in most results inferring the correctness of the model. The mathematical model may facilitate the study on optimization of deduplication ratio by reasonably setting the expected chunk size.

content defined chunking; deduplication ratio; logistic function

2016-5-20。 作者簡介:王龍翔(1988—),男,博士生;張興軍(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金資助項目(61572394);國家重點研究發展計劃資助項目(2016YFB1000303);深圳市基礎研究資助項目(JCYJ20120615101127404,JSGG20140519141854753)。

時間:2016-09-22

10.7652/xjtuxb201612012

TP333

A

0253-987X(2016)12-0073-06

網絡出版地址:http: ∥www.cnki.net/kcms/detail/61.1069.T.20160922.1205.006.html