主存儲(chǔ)服務(wù)系統(tǒng)中高I-O性能的重復(fù)數(shù)據(jù)刪除技術(shù)研究.pdf

1、隨著數(shù)字信息量的爆炸式增長(zhǎng)，數(shù)據(jù)占用的空間越來(lái)越大，存儲(chǔ)系統(tǒng)的容量從數(shù)十GB發(fā)展到數(shù)百TB、甚至PB量級(jí)。面對(duì)數(shù)據(jù)量的急劇膨脹，企業(yè)需要不斷購(gòu)置大量的存儲(chǔ)設(shè)備來(lái)應(yīng)對(duì)不斷增長(zhǎng)的存儲(chǔ)需求，管理和保存數(shù)據(jù)的成本急劇上升，存儲(chǔ)技術(shù)和存儲(chǔ)產(chǎn)業(yè)正面臨著由龐大需求而帶來(lái)的巨大挑戰(zhàn)。重復(fù)數(shù)據(jù)刪除技術(shù)是存儲(chǔ)系統(tǒng)中的關(guān)鍵技術(shù)，通過檢測(cè)并刪除冗余數(shù)據(jù)來(lái)優(yōu)化存儲(chǔ)空間、提高網(wǎng)絡(luò)帶寬利用率和降低運(yùn)營(yíng)成本。在需求的推動(dòng)下，重復(fù)數(shù)據(jù)刪除技術(shù)成為近幾年學(xué)術(shù)界和工業(yè)界的研

2、究熱點(diǎn)，并正被愈加廣泛地應(yīng)用到各種信息存儲(chǔ)系統(tǒng)。目前，大多數(shù)重復(fù)數(shù)據(jù)刪除產(chǎn)品針對(duì)備份和歸檔存儲(chǔ)服務(wù)系統(tǒng)，用于節(jié)省空間和優(yōu)化性能。然而，隨著社交網(wǎng)絡(luò)、云存儲(chǔ)服務(wù)模式的興起，主存儲(chǔ)服務(wù)系統(tǒng)中越來(lái)越多的數(shù)據(jù)被共享，如文件、圖片和視頻等，在線服務(wù)的數(shù)據(jù)量日益增大，同樣面臨著重復(fù)數(shù)據(jù)刪除的需求。與備份和歸檔存儲(chǔ)服務(wù)系統(tǒng)不同，主存儲(chǔ)服務(wù)系統(tǒng)具有數(shù)據(jù)規(guī)模巨大、數(shù)據(jù)訪問復(fù)雜多樣和高I/O性能需求的特征。然而，重復(fù)數(shù)據(jù)刪除過程中的數(shù)據(jù)檢測(cè)處理需要占用系統(tǒng)

3、大量的CPU和I/O資源，極大地影響數(shù)據(jù)寫操作的性能；同時(shí)，重復(fù)數(shù)據(jù)刪除會(huì)使得文件數(shù)據(jù)存儲(chǔ)碎片化，嚴(yán)重影響I/O讀操作的性能。這些都給重復(fù)數(shù)據(jù)刪除技術(shù)在主存儲(chǔ)服務(wù)系統(tǒng)中的應(yīng)用帶來(lái)了很多挑戰(zhàn)性問題：第一，主存儲(chǔ)服務(wù)系統(tǒng)中的數(shù)據(jù)訪問模式不同于備份存儲(chǔ)服務(wù)系統(tǒng)，其I/O寫操作的特征復(fù)雜多樣，導(dǎo)致在主存儲(chǔ)服務(wù)系統(tǒng)中進(jìn)行重復(fù)數(shù)據(jù)檢測(cè)將會(huì)帶來(lái)極大地I/O開銷。第二，現(xiàn)有的重復(fù)數(shù)據(jù)檢測(cè)算法主要關(guān)注于如何快速定位和降低檢測(cè)范圍，沒有充分利用已有的并行計(jì)

4、算架構(gòu)來(lái)加速問題求解。第三，現(xiàn)有的研究未考慮到主存儲(chǔ)服務(wù)系統(tǒng)中I/O緩存對(duì)數(shù)據(jù)讀取操作的優(yōu)化作用，從而在衡量重復(fù)數(shù)據(jù)碎片對(duì)I/O性能的影響時(shí)，應(yīng)綜合考慮系統(tǒng)的各個(gè)層面，做出更高效的決策。第四，現(xiàn)有的數(shù)據(jù)碎片整理方法未能充分利用數(shù)據(jù)訪問的動(dòng)態(tài)信息，嚴(yán)重受限于重復(fù)數(shù)據(jù)刪除系統(tǒng)中大量的數(shù)據(jù)共享關(guān)聯(lián)，難以提高磁盤文件存儲(chǔ)的連續(xù)性。
　　本文系統(tǒng)地研究了主存儲(chǔ)服務(wù)系統(tǒng)中高I/O性能的重復(fù)數(shù)據(jù)刪除技術(shù)，針對(duì)主存儲(chǔ)服務(wù)系統(tǒng)復(fù)雜的I/O訪問模式，

5、深入研究了典型系統(tǒng)中重復(fù)數(shù)據(jù)寫操作的時(shí)間及空間局部性特征?；谛D(zhuǎn)樹數(shù)據(jù)結(jié)構(gòu)理論，本文設(shè)計(jì)了自適應(yīng)指紋緩存Leach。Leach自動(dòng)學(xué)習(xí)目標(biāo)系統(tǒng)重復(fù)數(shù)據(jù)寫操作的時(shí)空局部性信息，動(dòng)態(tài)地將熱點(diǎn)及其關(guān)聯(lián)數(shù)據(jù)指紋放入緩存，提高數(shù)據(jù)檢測(cè)的緩存命中率；同時(shí)，針對(duì)自適應(yīng)學(xué)習(xí)的I/O開銷，提出了基于工作集特征的優(yōu)化機(jī)制，進(jìn)一步提高數(shù)據(jù)檢測(cè)的效率。針對(duì)重復(fù)數(shù)據(jù)檢測(cè)任務(wù)的可并行性問題，本文基于CPU+GPU的異構(gòu)并行計(jì)算框架，通過將數(shù)據(jù)指紋索引組織成前綴樹

6、結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)了一種具有高并行度的重復(fù)數(shù)據(jù)檢測(cè)方法G-Paradex。針對(duì)CPU與GPU之間數(shù)據(jù)傳輸?shù)钠款i，提出了數(shù)據(jù)指紋重組和近似檢測(cè)的優(yōu)化方法，減少前綴樹占用的存儲(chǔ)空間，降低CPU與GPU之間的數(shù)據(jù)傳輸量；針對(duì)GPU的硬件架構(gòu)和并行編程特性進(jìn)行了適配，提出了重復(fù)數(shù)據(jù)檢測(cè)剪枝策略，大幅度降低數(shù)據(jù)檢測(cè)的計(jì)算量，快速定位重復(fù)數(shù)據(jù)。針對(duì)已有算法未能充分認(rèn)識(shí)重復(fù)數(shù)據(jù)碎片影響的問題，本文發(fā)現(xiàn)在具有I/O緩存的主存儲(chǔ)服務(wù)系統(tǒng)中，重復(fù)數(shù)據(jù)碎片未必

7、完全對(duì)I/O性能產(chǎn)生負(fù)面影響，在一定訪問模式下反而會(huì)提升I/O性能?；谝陨习l(fā)現(xiàn)，本文設(shè)計(jì)和實(shí)現(xiàn)了一種I/O緩存感知的重復(fù)數(shù)據(jù)碎片優(yōu)化方法CareDedup。通過對(duì)塊設(shè)備層I/O訪問信息的監(jiān)測(cè)，CareDedup分析了I/O緩存對(duì)重復(fù)數(shù)據(jù)碎片的優(yōu)化以及重復(fù)數(shù)據(jù)碎片本身對(duì)數(shù)據(jù)布局的破壞，綜合評(píng)估重復(fù)數(shù)據(jù)碎片對(duì)I/O性能的影響。通過建模分析，本文將面向I/O讀性能的重復(fù)數(shù)據(jù)刪除優(yōu)化問題歸約到0/1背包問題，并采用貪婪算法在給定存儲(chǔ)空間優(yōu)化的

8、前提下最大化數(shù)據(jù)讀取性能。針對(duì)已有算法未能充分考慮重復(fù)數(shù)據(jù)碎片訪問特征的問題，本文探索了基于I/O訪問記錄的重復(fù)數(shù)據(jù)碎片布局策略ReDedup，大幅降低了重復(fù)數(shù)據(jù)碎片對(duì)I/O性能的影響。文章通過對(duì)典型系統(tǒng)中文件之間的共享關(guān)聯(lián)度和文件數(shù)據(jù)碎片的訪問頻度進(jìn)行統(tǒng)計(jì)和挖掘，發(fā)現(xiàn)主存儲(chǔ)服務(wù)系統(tǒng)中對(duì)重復(fù)數(shù)據(jù)文件（重復(fù)數(shù)據(jù)文件指該文件中存在重復(fù)數(shù)據(jù)，與其它文件共享數(shù)據(jù)）的訪問服從典型的冪律分布，即存在一小部分重復(fù)數(shù)據(jù)文件受到的訪問次數(shù)較多且開銷較大，