賀秦祿,邊根慶,邵必林,賈雷剛

(1.西安建筑科技大學(xué)信息與控制工程學(xué)院,710055,西安;2.西安建筑科技大學(xué)管理學(xué)院,710055,西安)

重復(fù)數(shù)據(jù)刪除技術(shù)是將數(shù)據(jù)分解成塊,使用數(shù)據(jù)塊的哈希指紋來檢測和刪除重復(fù)塊以節(jié)省存儲(chǔ)空間。重刪技術(shù)在備份及歸檔系統(tǒng)中得到廣泛應(yīng)用[1-2]。根據(jù)重復(fù)數(shù)據(jù)刪除執(zhí)行的方式可分為兩類:在線重復(fù)數(shù)據(jù)刪除[3]和離線重復(fù)數(shù)據(jù)刪除[4-5]。前者在I/O寫請(qǐng)求路徑上執(zhí)行重復(fù)數(shù)據(jù)刪除,以立即檢測和刪除重復(fù)數(shù)據(jù),而后者在后臺(tái)進(jìn)行重刪,以避免對(duì)I/O性能的影響。然而,這兩種方式都存在效率不高的問題。

對(duì)于在線重復(fù)數(shù)據(jù)刪除,指紋查找是主要的性能瓶頸,因?yàn)橹讣y索引表通常超過內(nèi)存的大小,只能部分存儲(chǔ)在內(nèi)存,剩余部分存儲(chǔ)在磁盤,雖然備份系統(tǒng)可以容忍基于磁盤指紋查找的延遲,但是在云存儲(chǔ)系統(tǒng)上可以采用緩存來解決應(yīng)用程序的延遲問題。iDedup[6]和POD[7]機(jī)制進(jìn)行選擇性在線重刪。iDedup機(jī)制實(shí)現(xiàn)了在不同閾值下I/O性能、空間效率和資源消耗之間的均衡;POD機(jī)制采用恒定閾值長度為3進(jìn)行分析驗(yàn)證。本文根據(jù)數(shù)據(jù)流的特征動(dòng)態(tài)調(diào)整閾值,以提高系統(tǒng)重刪的性能。

離線重復(fù)數(shù)據(jù)刪除技術(shù)存在兩個(gè)缺點(diǎn):第一,在重刪之前將所有的數(shù)據(jù)塊寫入磁盤,這對(duì)于采用SSD作為緩存介質(zhì)的系統(tǒng),重刪將影響SSD的使用壽命[8];第二,當(dāng)需要進(jìn)行大量的重復(fù)數(shù)據(jù)刪除時(shí),離線重刪技術(shù)存在著與其他應(yīng)用競爭系統(tǒng)資源的問題,影響整個(gè)系統(tǒng)的性能。AA-Dedupe機(jī)制[9]是應(yīng)用源端感知的重刪方法,基于不同的分塊和哈希方案將整個(gè)索引劃分為更小的子集進(jìn)行重刪指紋匹配。與AA-Dedupe機(jī)制不同,本文機(jī)制根據(jù)應(yīng)用類型將整個(gè)索引分為不同的子集進(jìn)行數(shù)據(jù)重刪,并利用空間位置來解決讀取放大問題。

將在線和離線處理融合在一起可以使每個(gè)階段相互補(bǔ)充并解決單獨(dú)處理的局限性。在線階段可以刪除具有良好時(shí)間局部性的重復(fù)塊,而將其余重復(fù)塊保留到離線階段進(jìn)行精確重刪[10]。在這種方式下,負(fù)載的指紋緩存扮演著重要的角色,在線階段高效的緩存機(jī)制能夠識(shí)別大量的重復(fù)塊,減少寫入磁盤的數(shù)據(jù)量[11],從而提高I/O性能并減少離線重刪階段的工作量。

1 Hy-Dedup機(jī)制的設(shè)計(jì)

傳統(tǒng)的在線或離線處理重復(fù)數(shù)據(jù)刪除難以滿足云存儲(chǔ)系統(tǒng)對(duì)的重刪率和延遲要求。本文提出了Hy-Dedup機(jī)制,結(jié)合在線重刪和離線重刪的兩種方式,能夠?qū)崿F(xiàn)系統(tǒng)I/O性能和重刪率之間的平衡,這對(duì)云存儲(chǔ)系統(tǒng)的在線重刪是至關(guān)重要的。

圖1 Hy-Dedup機(jī)制系統(tǒng)架構(gòu)

1.1 Hy-Dedup機(jī)制系統(tǒng)架構(gòu)

圖1給出了Hy-Dedup機(jī)制系統(tǒng)架構(gòu)。Hy-Dedup機(jī)制部署在存儲(chǔ)節(jié)點(diǎn)上,數(shù)據(jù)流的I/O讀寫操作通過與文件系統(tǒng)接口進(jìn)行交互,可以兼容任何類型存儲(chǔ)系統(tǒng)并進(jìn)行性能優(yōu)化。此外,與全文重復(fù)數(shù)據(jù)刪除的iDedup[6]和POD[7]機(jī)制相比,Hy-Dedup機(jī)制又獨(dú)立于文件系統(tǒng),具有較好的靈活性和可擴(kuò)展性。Hy-Dedup機(jī)制也可以部署在虛擬機(jī)管理程序中,例如VDI、XEN等。虛擬機(jī)鏡像中存在大量重復(fù)數(shù)據(jù)塊,對(duì)于在同一主機(jī)上運(yùn)行的多個(gè)容器,可以在塊設(shè)備上部署Hy-Dedup機(jī)制,進(jìn)行重復(fù)數(shù)據(jù)刪除。

在線重刪階段首先根據(jù)應(yīng)用類型對(duì)寫數(shù)據(jù)流中的數(shù)據(jù)塊的指紋索引進(jìn)行聚類分組,之后定期評(píng)估不同數(shù)據(jù)流的時(shí)間局部性,優(yōu)先考慮將緩存分配給具有良好時(shí)間局部性的數(shù)據(jù)流。通過這樣的方式,在線重刪階段可以有效地減少寫入數(shù)據(jù)量,實(shí)時(shí)更新指紋索引,保證數(shù)據(jù)一致性,減少存儲(chǔ)和查詢哈希索引表所引起的內(nèi)存和CPU開銷,同時(shí)減少離線重刪階段的工作量。其次,離線重刪階段僅處理在線重刪階段中未檢測出的重復(fù)塊,采用延遲觸發(fā)的思想進(jìn)行設(shè)計(jì),當(dāng)重復(fù)數(shù)據(jù)塊達(dá)到設(shè)定的閾值時(shí)才會(huì)進(jìn)行離線重刪,根據(jù)重刪結(jié)果置換內(nèi)存中相應(yīng)的索引項(xiàng)。與單純離線處理的重刪系統(tǒng)相比,高效的在線重刪流程大大降低了對(duì)存儲(chǔ)容量和系統(tǒng)資源的占用。此外,Hy-Dedup機(jī)制根據(jù)數(shù)據(jù)流特征動(dòng)態(tài)調(diào)整閾值的策略,不僅可以保證重刪率,同時(shí)也減少了數(shù)據(jù)碎片的產(chǎn)生,不影響后續(xù)數(shù)據(jù)恢復(fù)的性能。

1.2 在線重復(fù)數(shù)據(jù)刪除階段

在線重刪階段,Hy-Dedup機(jī)制維護(hù)一個(gè)數(shù)據(jù)塊指紋緩存和物理塊地址(PBA)映射,以避免指紋表檢索的磁盤瓶頸,同時(shí)也建立數(shù)據(jù)塊的邏輯塊地址(LBA)和PBA之間的映射關(guān)系。此外,具有相同內(nèi)容和局部一致性的I/O請(qǐng)求僅在映射表中記錄一項(xiàng),這將減少實(shí)際應(yīng)用中的內(nèi)存開銷。首先,計(jì)算數(shù)據(jù)流中的數(shù)據(jù)塊哈希值,在重刪引擎的緩存中查詢塊指紋進(jìn)行匹配;其次,數(shù)據(jù)流局部一致性估計(jì)器負(fù)責(zé)監(jiān)視和估計(jì)來自不同應(yīng)用數(shù)據(jù)流的時(shí)間和空間局部一致性。時(shí)間局部一致性估計(jì)用于優(yōu)化緩存的命中率,而空間局部一致性用于估計(jì)動(dòng)態(tài)調(diào)整數(shù)據(jù)流的重刪閾值以減少磁盤碎片。

當(dāng)緩存命中了輸入數(shù)據(jù)塊指紋、這個(gè)數(shù)據(jù)塊不存在于映射表時(shí),則將創(chuàng)建LBA和對(duì)應(yīng)的PBA項(xiàng),并將其添加到LBA映射表中;若緩存中沒有命中數(shù)據(jù)塊指紋,則將數(shù)據(jù)塊直接寫入底層存儲(chǔ),該數(shù)據(jù)塊相關(guān)聯(lián)的數(shù)據(jù)塊指紋、LBA和PBA映射以及引用計(jì)數(shù)的對(duì)應(yīng)元數(shù)據(jù)在3個(gè)表中同步更新。緩存未命中的數(shù)據(jù)塊將在離線階段再次進(jìn)行重刪。

1.2.1 數(shù)據(jù)流的時(shí)間局部一致性估計(jì) 重復(fù)塊的時(shí)間局部一致性特征表示在數(shù)據(jù)流中重復(fù)塊可能達(dá)到系統(tǒng)的時(shí)間。良好的時(shí)間局部一致性表示重復(fù)塊通常彼此接近,而弱局部一致性表示重復(fù)塊通常彼此遠(yuǎn)離或數(shù)據(jù)流中幾乎不存在重復(fù)塊。為了計(jì)算重復(fù)塊的時(shí)間局部一致性,本文引入局部重復(fù)集合的度量(LDS,定義為L)表示數(shù)據(jù)流在給定時(shí)間之前多個(gè)連續(xù)數(shù)據(jù)塊中重復(fù)塊的數(shù)量,根據(jù)緩存分配情況,通過L預(yù)測在未來即將到達(dá)數(shù)據(jù)流中重復(fù)塊。常見的方法是使用歷史L來進(jìn)行預(yù)測,為了從數(shù)據(jù)流中獲得歷史L,通常是對(duì)數(shù)據(jù)流中所有的指紋及其在估計(jì)間隔內(nèi)出現(xiàn)的次數(shù)進(jìn)行計(jì)數(shù),然而,記錄所有的數(shù)據(jù)指紋將產(chǎn)生很高的內(nèi)存開銷。為了解決這個(gè)問題,數(shù)據(jù)流局部一致性估計(jì)器使用存儲(chǔ)采樣算法[12]從數(shù)據(jù)流中采樣指紋,然后使用不可見的估計(jì)算法[13]對(duì)樣本進(jìn)行L估計(jì)。

假設(shè)系統(tǒng)處理M個(gè)數(shù)據(jù)流,估計(jì)間隔大小為a,時(shí)間局部一致性估計(jì)的目標(biāo)是從最近m個(gè)寫請(qǐng)求中收集k個(gè)指紋樣本,每個(gè)數(shù)據(jù)流基于指紋樣本計(jì)算其對(duì)應(yīng)的L。在采樣之后,用Ni表示在估計(jì)區(qū)間內(nèi)來自i數(shù)據(jù)流寫請(qǐng)求的數(shù)量,估計(jì)在數(shù)據(jù)流中最后t個(gè)寫請(qǐng)求中可實(shí)際寫入的數(shù)量。通過空間局部一致性估算Li的過程如下:首先定義指紋采樣函數(shù)(FFH)設(shè)為F,用來估算數(shù)據(jù)流i的Li;用Hi′表示樣本的采樣結(jié)果,H表示數(shù)據(jù)流i在整個(gè)估計(jì)間隔的F,計(jì)算任意一項(xiàng)在特定時(shí)間間隔內(nèi)被采樣的概率。采樣數(shù)據(jù)塊預(yù)期結(jié)果Hi′可以通過Hi′=MH/(T+H)計(jì)算得到,之后通過計(jì)算Hi和Hi′之間的距離平均值得到H,進(jìn)而代入計(jì)算就可以得到數(shù)據(jù)流的Li。對(duì)于在估計(jì)間隔期間只有少量寫請(qǐng)求的情況,不需要通過上述過程來估計(jì)L,只需要將L設(shè)置為一個(gè)較小的定值即可。

1.2.2 數(shù)據(jù)流的空間局部一致性估計(jì) 為解決數(shù)據(jù)流重刪后引起數(shù)據(jù)碎片問題,Hy-Dedup機(jī)制定義兩個(gè)變量Vw和Vr。Vw記錄連續(xù)重復(fù)塊最大長度值出現(xiàn)的次數(shù),Vr記錄順序讀的長度值出現(xiàn)的次數(shù)。例如,Vw[3]=100,表示存在長度為3的100個(gè)連續(xù)重復(fù)塊;如果Vr[3]=100,則表示有100次長度為3順序讀請(qǐng)求。初始階段閾值定義為z0,初值設(shè)定為20,兩個(gè)變量在請(qǐng)求到達(dá)時(shí)收集數(shù)據(jù)。當(dāng)閾值更新被觸發(fā)時(shí),閾值Z的計(jì)算公式為

(4)在砂土中進(jìn)行靜壓沉樁時(shí),樁-土界面土體與樁體共同下沉約0.2 mm即開始脫離樁體逐步穩(wěn)定,因此樁體受到的樁側(cè)摩阻力主要來自樁與土的摩擦力.

Z=∑(RLd+(1-r)Lr)/N

(1)

式中:Ld和Lr分別是重復(fù)序列的平均長度和平均讀取長度;Z是讀和寫延遲的平衡點(diǎn);r是所有請(qǐng)求之間的寫比率;N為估算間隔。Ld和Lr分別根據(jù)在Vw和Vr中收集的數(shù)據(jù)進(jìn)行計(jì)算,為了應(yīng)對(duì)每個(gè)數(shù)據(jù)流重復(fù)模式的變化,自上一個(gè)閾值更新以來重刪率減少超過50%時(shí),兩個(gè)變量將全被重置為0。

1.3 離線重復(fù)數(shù)據(jù)刪除階段

在離線重刪階段,通過匹配磁盤上存儲(chǔ)的指紋索引表進(jìn)行數(shù)據(jù)塊重刪。與傳統(tǒng)離線重刪不同,Hy-Dedup機(jī)制以延遲方式運(yùn)行,只有當(dāng)重復(fù)數(shù)據(jù)塊達(dá)到設(shè)定的閾值時(shí),才會(huì)觸發(fā)重刪操作。這種策略為讀請(qǐng)求節(jié)省空間,對(duì)于延遲敏感云存儲(chǔ)負(fù)載有利。首先,對(duì)于在線階段沒有緩存命中的數(shù)據(jù)塊在索引表中創(chuàng)建一個(gè)新條目,屬性包含數(shù)據(jù)塊ID、哈希值和塊大小,當(dāng)新增加的條目數(shù)達(dá)到預(yù)設(shè)值時(shí),離線重刪模塊會(huì)生成一個(gè)名為Targets[]的列表,同時(shí),離線重刪模塊會(huì)將每個(gè)數(shù)據(jù)塊的LBA和最后訪問時(shí)間戳(LAT)插入到其相應(yīng)的條目中。其次,根據(jù)重刪優(yōu)先級(jí)來重新分配最近訪問的數(shù)據(jù)塊的次序,當(dāng)緩存區(qū)存儲(chǔ)的指紋數(shù)大于設(shè)定的閾值時(shí),重刪模塊才允許完全遍歷Targets[]中所有的目標(biāo);否則僅處理Targets[]中的一半項(xiàng)即可。最后,按照哈希值的匹配進(jìn)行數(shù)據(jù)重刪。

2 Hy-Dedup機(jī)制的實(shí)驗(yàn)分析

首先描述實(shí)驗(yàn)參數(shù)和方法,然后通過實(shí)驗(yàn)來驗(yàn)證Hy-Dedup機(jī)制的性能。

2.1 實(shí)驗(yàn)環(huán)境

在ADMAD平臺(tái)[14]的基礎(chǔ)上實(shí)現(xiàn)了Hy-Dedup機(jī)制原型。Hy-Dedup機(jī)制是云存儲(chǔ)環(huán)境中應(yīng)用感知的重復(fù)數(shù)據(jù)刪除機(jī)制,通過聚類應(yīng)用中的數(shù)據(jù)指紋索引以實(shí)現(xiàn)高重刪效率,它適用于不同的分塊算法,如變長分塊(CDC)、靜態(tài)分塊(SC)、整個(gè)文件分塊(WFC)以及不同類型文件和應(yīng)用的哈希函數(shù),如SHA-1、MD5和Rabin哈希。Hy-Dedup機(jī)制是在Lessfs系統(tǒng)[15]上進(jìn)行搭建,在實(shí)驗(yàn)中使用真實(shí)數(shù)據(jù)集重放來驗(yàn)證Hy-Dedup機(jī)制的緩存命中率和重刪率。具體實(shí)驗(yàn)環(huán)境由10個(gè)節(jié)點(diǎn)組成,每個(gè)節(jié)點(diǎn)配置信息見表1。

表1 實(shí)驗(yàn)環(huán)境配置信息

表2給出了3個(gè)實(shí)際應(yīng)用數(shù)據(jù)集(VM鏡像[16]、Firefox安裝鏡像[17]和Linux內(nèi)核源碼[18])的存儲(chǔ)數(shù)據(jù)大小和當(dāng)數(shù)據(jù)塊大小為16 KB時(shí)數(shù)據(jù)集的內(nèi)部重復(fù)率。

表2 3種數(shù)據(jù)集的數(shù)據(jù)特征

表3給出了這3種應(yīng)用數(shù)據(jù)之間的冗余特性,每個(gè)單元格表示共享重復(fù)率,由垂直應(yīng)用和水平應(yīng)用之間的冗余數(shù)據(jù)除以水平應(yīng)用的總數(shù)據(jù)計(jì)算得到。如果單元格中的兩個(gè)應(yīng)用相同,則表示應(yīng)用程序中的數(shù)據(jù)冗余。從表3可以看出,任何兩種不同的應(yīng)用之間,只有少于1%數(shù)據(jù)塊是重復(fù)塊。因此,當(dāng)這3種負(fù)載根據(jù)請(qǐng)求到達(dá)時(shí)間的順序進(jìn)行排序和合并時(shí),生成的數(shù)據(jù)集與原始數(shù)據(jù)集具有相同的I/O模式,這表明對(duì)于從相同數(shù)據(jù)源生成的數(shù)據(jù)集,設(shè)置內(nèi)容隨機(jī)重復(fù)率為0～36%,將代表用戶使用的典型負(fù)載類型。

表3 3種不同應(yīng)用的數(shù)據(jù)局部一致性

通過上述結(jié)果表明,不同應(yīng)用之間共享的冗余數(shù)據(jù)量可以忽略不計(jì),原因是不同應(yīng)用具有不同的數(shù)據(jù)內(nèi)容和數(shù)據(jù)格式,因此可以將相同應(yīng)用的指紋索引有效地組合在一起,并根據(jù)應(yīng)用類型將整個(gè)指紋索引進(jìn)行聚類分組。

實(shí)驗(yàn)的整體思路如下:在初始狀態(tài)下,后端存儲(chǔ)是基于HDD的RAID10,包括具有128 MB緩存和16 KB數(shù)據(jù)塊大小的4個(gè)HDD。通過在iDedup和Hy-Dedup機(jī)制中重放3個(gè)數(shù)據(jù)集來驗(yàn)證系統(tǒng)吞吐量,同時(shí)通過改變緩存和負(fù)載的局部性比率來驗(yàn)證重刪機(jī)制的性能敏感度。

2.2 寫性能對(duì)比

在由4個(gè)HDD組成的RAID10系統(tǒng)上設(shè)置不同大小的緩存分別進(jìn)行實(shí)驗(yàn)。圖2給出了Hy-Dedup、iDedup和POD機(jī)制隨著緩存的增加對(duì)系統(tǒng)寫吞吐量的影響。與iDedup和POD機(jī)制相比,Hy-Dedup機(jī)制將寫吞吐量最高提高了6.9倍,寫吞量平均提高了3.2倍,這表明Hy-Dedup機(jī)制的寫吞吐量對(duì)緩存不太敏感,由于Hy-Dedup機(jī)制所需的索引緩存小,在云儲(chǔ)存環(huán)境下應(yīng)用Hy-Dedup機(jī)制時(shí)將會(huì)獲得更好的可擴(kuò)展性。O分析原因有兩個(gè)方面:①iDedup和POD機(jī)制寫吞吐量由指紋索引緩存中數(shù)據(jù)冗余度決定,雖然iDedup機(jī)制將相同分塊方案的指紋分組在一起,但索引緩存仍然太大,無法存儲(chǔ)在內(nèi)存中,后端存儲(chǔ)和內(nèi)存之間的頁面置換將影響系統(tǒng)性能;②由于Hy-Dedup機(jī)制只將應(yīng)用聚類分組后的指紋索引加載到內(nèi)存中,重刪時(shí)所需的緩存和查詢大小都減少了,即使使用較小的索引緩存,寫吞吐量也呈線性增長。

圖2 3種方法寫吞吐量隨緩存的變化

2.3 在線重刪緩存命中率比較

圖3給出了Hy-Dedup、iDedup和POD機(jī)制在線重刪率與緩存的關(guān)系。對(duì)于每種類型數(shù)據(jù)流都存在不同的緩存替換策略,文獻(xiàn)[5]實(shí)驗(yàn)分析得出,LRU算法是iDedup和POD機(jī)制較好的緩存替換方法,因此Hy-Dedup機(jī)制也使用LRU算法作為緩存替換方法,方便進(jìn)行實(shí)驗(yàn)對(duì)比。對(duì)于負(fù)載A、B和C,具有良好局部性分部(G)和弱局部性能部分(N)之間的數(shù)據(jù)大小比例分別為3∶1、1∶1和1∶3。

如圖3所示,隨著局部一致性差的負(fù)載量增加,iDedup、POD和Hy-Dedup機(jī)制之間的重刪率的差距增加,Hy-Dedup機(jī)制顯著地提高在線重刪率。對(duì)于負(fù)載A,Hy-Dedup機(jī)制比POD和iDedup機(jī)制重刪率提高了7.14%～22.18%;對(duì)于負(fù)載B,提高了8.32%～23.9%;對(duì)于負(fù)載C,提高了16.7%～35.9%。隨著非本地負(fù)載量的增加(從負(fù)載A到C),負(fù)載的弱局部一致性導(dǎo)致在線重刪率較低。Hy-Dedup機(jī)制利用局部一致性估計(jì)算法,并結(jié)合重復(fù)塊指紋索引聚類動(dòng)態(tài)分配緩存,可以提高云存儲(chǔ)中多個(gè)應(yīng)用重刪的整體緩存命中率。

(a)負(fù)載A(G∶N=3∶1)

(b)負(fù)載B(G∶N=2∶2)

(c)負(fù)載C(G∶N=1∶3)圖3 3種機(jī)制重刪率隨緩存的變化

圖4 3種機(jī)制磁盤空間需求隨不同負(fù)載類型的變化

2.4 磁盤空間需求分析

如圖4所示,對(duì)比Hy-Dedup、AA-Dedupe機(jī)制和傳統(tǒng)重刪機(jī)制在重刪過程中對(duì)磁盤空間的需求。在實(shí)驗(yàn)中,Hy-Dedup機(jī)制在線重刪的緩存設(shè)置為200 MB,使用LRU算法作為緩存替換方法。

由圖4可以看出,針對(duì)不同負(fù)載Hy-Dedup機(jī)制明顯降低了磁盤空間需求,與AA-Dedupe機(jī)制相比,磁盤空間需求分別下降了41.36%、27.88%和11.95%。結(jié)果表明,負(fù)載的局部性越好,通過Hy-Dedup機(jī)制兩階段的重刪可以發(fā)現(xiàn)更多的重復(fù)塊,同時(shí)減少數(shù)據(jù)塊的寫入量。Hy-Dedup機(jī)制這種混合重刪架構(gòu),只需要維護(hù)200 MB的指紋索引緩存就可以減少數(shù)百GB的數(shù)據(jù)寫入。

2.5 系統(tǒng)開銷分析

2.5.1 計(jì)算的開銷 Hy-Dedup機(jī)制的計(jì)算開銷主要來自時(shí)間局部性估算,包含兩部分:指紋生成函數(shù)Y的時(shí)間和時(shí)間局部性估計(jì)算法執(zhí)行時(shí)間。為了計(jì)算Y,需掃描采樣緩沖區(qū)并計(jì)算指紋發(fā)生的情況,時(shí)間復(fù)雜度是O(n),其中n是樣本數(shù)。如圖5所示,當(dāng)采樣率為20%時(shí)1 000個(gè)數(shù)據(jù)塊的估計(jì)間隔計(jì)算時(shí)間少于2 ms;對(duì)于每個(gè)估計(jì)間隔,每個(gè)數(shù)據(jù)流時(shí)間局部性估計(jì)大約需要17 ms。該進(jìn)程在后臺(tái)執(zhí)行并且不影響系統(tǒng)寫性能,因此這樣的計(jì)算開銷是可接受的。

圖5 Hy-Dedup機(jī)制計(jì)算開銷

2.5.2 內(nèi)存開銷分析 Hy-Dedup機(jī)制的內(nèi)存開銷主要來自樣本采樣緩存。利用估算間隔N和采樣率p,內(nèi)存開銷q計(jì)算如下

q=Np(fsize+csize)

(2)

式中fsize和csize分別是用于存儲(chǔ)指紋和發(fā)生計(jì)數(shù)的內(nèi)存開銷。例如,當(dāng)緩存為200 MB時(shí),將有大約2.8 MB的緩存項(xiàng)。對(duì)于20%的采樣率,即使選擇較大的估計(jì)間隔因子(例如負(fù)載C,間隔因子為0.6),內(nèi)存開銷只有4.6 MB(緩存為2.89%)。在實(shí)驗(yàn)中,對(duì)于具有較好的時(shí)間局部一致性的數(shù)據(jù)流,可以將估計(jì)間隔因子設(shè)置為較小的值,內(nèi)存開銷減少很多(例如負(fù)載A為2.13 MB,負(fù)載B為2.87 MB),與具有200 MB緩存的兩個(gè)負(fù)載的在線重刪率(18.36%～22.51%)相比,Hy-Dedup機(jī)制的內(nèi)存開銷是完全可以接受的。

2.6 離線重刪階段的效率

對(duì)比Hy-Dedup、AA-Dedupe和iDedup機(jī)制不同后端存儲(chǔ)的寫吞吐量,在由4個(gè)HDD(HDD-RAID10)、4個(gè)HDD(HDD-RAID5)和4個(gè)SSD(SSD-RAID5)分別組成的RAID5和RAID10系統(tǒng)上進(jìn)行實(shí)驗(yàn),結(jié)果如圖6所示。

圖6 寫吞吐量隨不同后端存儲(chǔ)環(huán)境的變化

從圖6可以看出,HDD-RAID5寫吞吐量高于HDD-RAID10。原因是4個(gè)HDD組成的RAID5系統(tǒng)比4個(gè)HDD組成的RAID10系統(tǒng)具有更好的訪問并行性,因此可提供更高的寫吞吐量。SSD-RAID5的寫吞吐量是情況最好的,其原因?yàn)槿缦聝牲c(diǎn):①SSD的性能優(yōu)于HDD,從而具有較高的性能;②內(nèi)存和SSD之間的置換操作比內(nèi)存和HDD之間的置換操作快得多,從而提高了索引存儲(chǔ)和查詢的效率,文獻(xiàn)[4]的研究結(jié)果已經(jīng)證明了這一結(jié)論。另一方面,與iDedup、AA-Dedupe機(jī)制相比,Hy-Dedup機(jī)制在HDD-RAID10、HDD-RAID5和SSD-RAID5上的性能高出1.8～3.6倍。

3 結(jié) 論

本文提出了一種混合重刪機(jī)制(Hy-Dedup),根據(jù)應(yīng)用負(fù)載類型對(duì)指紋索引進(jìn)行聚類分組,估計(jì)數(shù)據(jù)流中重復(fù)塊的局部一致性,使用動(dòng)態(tài)局部一致性估計(jì)算法來提高在線緩存命中率,并將沒有被緩存命中的相對(duì)數(shù)量較少的重復(fù)塊在離線重刪階段進(jìn)行處理。通過這種方式,Hy-Dedup機(jī)制能夠在云存儲(chǔ)系統(tǒng)中實(shí)現(xiàn)精確的重刪,提升系統(tǒng)I/O性能,節(jié)省存儲(chǔ)空間。與現(xiàn)有的在線重刪機(jī)制相比,Hy-Dedup機(jī)制顯著地提高在線緩存效率,從而實(shí)現(xiàn)了高效在線重刪率。未來還需要在以下兩個(gè)方面展開研究:設(shè)計(jì)具有高查詢效率的兼容性索引結(jié)構(gòu);利用機(jī)器學(xué)習(xí)實(shí)現(xiàn)自適應(yīng)調(diào)整控制參數(shù)的策略。