王龍翔,董凱,王鵬博,董小社,張興軍,朱正東,張利平

(1.西安交通大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,710049,西安;2.西安美術(shù)學(xué)院信息中心,710065,西安)

近年來,隨著半導(dǎo)體技術(shù)的不斷發(fā)展,固態(tài)硬盤(SSD)的每字節(jié)存儲(chǔ)成本在不斷下降。無論是個(gè)人計(jì)算機(jī)還是數(shù)據(jù)中心服務(wù)器,SSD正在逐漸取代機(jī)械硬盤(HDD)成為主要存儲(chǔ)設(shè)備。與HDD相比,SSD具有更高的性能和更低的功耗,并且更加抗振動(dòng)干擾。隨著3DXpoint等新型非易失性介質(zhì)(NVM)的發(fā)展,基于NVM的新一代SSD將具有更加優(yōu)異的性能。

重復(fù)數(shù)據(jù)刪除作為一項(xiàng)高效的數(shù)據(jù)精簡(jiǎn)技術(shù),在存儲(chǔ)系統(tǒng)中得到了廣泛應(yīng)用[1]。隨著SSD成為了主流的存儲(chǔ)設(shè)備,如何針對(duì)SSD的特點(diǎn)優(yōu)化重復(fù)數(shù)據(jù)刪除方法的性能成為了研究者關(guān)注的問題[2-5]。Gupta等指出,在普通文件系統(tǒng)的I/O負(fù)載中存在重復(fù)數(shù)據(jù),對(duì)SSD寫入數(shù)據(jù)進(jìn)行重復(fù)數(shù)據(jù)刪除是有效的[6]。Chen等提出CaFTL方法,在SSD內(nèi)部FTL層實(shí)現(xiàn)了重復(fù)數(shù)據(jù)刪除[7]。通過在SSD的寫入路徑中識(shí)別重復(fù)數(shù)據(jù),避免這些數(shù)據(jù)寫入flash介質(zhì)中,可以延長(zhǎng)SSD壽命。重復(fù)數(shù)據(jù)刪除需要對(duì)數(shù)據(jù)塊計(jì)算SHA-1哈希值作為指紋進(jìn)行數(shù)據(jù)查重操作。然而,計(jì)算SHA-1哈希值是一項(xiàng)計(jì)算密集型任務(wù),在SSD的寫入路徑中加入重復(fù)數(shù)據(jù)刪除會(huì)增加寫入延遲,降低數(shù)據(jù)寫入吞吐率。在基于NVM的SSD中,由于數(shù)據(jù)I/O操作延遲不斷降低,吞吐率不斷增加,該問題會(huì)更加嚴(yán)重。文獻(xiàn)[8]指出,在傳統(tǒng)HDD設(shè)備中,基于SHA-1的指紋計(jì)算執(zhí)行時(shí)間約占重復(fù)數(shù)據(jù)刪除操作總時(shí)間的21%,在NVM存儲(chǔ)系統(tǒng)中,這一比例上升至44%。因此,如何降低SHA-1指紋計(jì)算開銷成為了提高高性能SSD中重復(fù)數(shù)據(jù)刪除性能的關(guān)鍵問題。

為了降低SHA-1指紋計(jì)算時(shí)間開銷,CaFTL提出了采樣和預(yù)哈希方法[7]。該方法假設(shè)上層負(fù)載中只存在少量重復(fù)數(shù)據(jù),因此每次請(qǐng)求都會(huì)被抽樣,只有當(dāng)某次寫入請(qǐng)求中被抽樣數(shù)據(jù)塊為重復(fù)時(shí)才進(jìn)行重復(fù)數(shù)據(jù)刪除操作,否則認(rèn)為該次請(qǐng)求包含重復(fù)數(shù)據(jù)的概率較低,不對(duì)該次請(qǐng)求進(jìn)行重復(fù)數(shù)據(jù)刪除。同樣,Wang等提出了類似的思想,在執(zhí)行重復(fù)數(shù)據(jù)刪除之前,對(duì)數(shù)據(jù)集進(jìn)行采樣,以獲得估計(jì)的重復(fù)數(shù)據(jù)刪除率[8]。只有重復(fù)率高的數(shù)據(jù)集才會(huì)執(zhí)行重復(fù)數(shù)據(jù)刪除,而重復(fù)率低的數(shù)據(jù)集則不會(huì)執(zhí)行。采樣方法通過減少需要進(jìn)行重復(fù)數(shù)據(jù)刪除操作的數(shù)據(jù)量來降低指紋計(jì)算開銷,存在的問題是會(huì)降低重復(fù)數(shù)據(jù)刪除率。Chen等提出的NF-Dedup用弱哈希算法(如CRC)替代SHA-1作為數(shù)據(jù)塊指紋,以此來減少指紋計(jì)算開銷[9]。該方法的原理是CRC等弱哈希算法的計(jì)算開銷遠(yuǎn)小于SHA-1這類強(qiáng)哈希函數(shù)的。當(dāng)弱哈希在指紋庫中檢索不到時(shí),可以確定對(duì)應(yīng)的數(shù)據(jù)塊不存在,但是當(dāng)檢索到弱哈希存在時(shí),不能確定對(duì)應(yīng)的數(shù)據(jù)塊是否存在。這是由于弱哈希具有較高的哈希碰撞率,即若干個(gè)不同的數(shù)據(jù)塊可能具有相同的弱哈希值。因此,NF-Dedup通過逐字節(jié)比較所有具有相同CRC指紋的數(shù)據(jù)塊來判斷是否為重復(fù)數(shù)據(jù)塊。該方法隨著存儲(chǔ)數(shù)據(jù)量的增大,產(chǎn)生哈希碰撞的幾率會(huì)持續(xù)上升。例如:在存儲(chǔ)數(shù)據(jù)量較小時(shí),可能存在兩個(gè)數(shù)據(jù)塊具有相同的CRC哈希值,當(dāng)存儲(chǔ)數(shù)據(jù)量增大后,具有相同CRC哈希值的數(shù)據(jù)塊可能上升為10。此時(shí),需要對(duì)10個(gè)數(shù)據(jù)塊都進(jìn)行逐字節(jié)對(duì)比才能判斷數(shù)據(jù)塊是否重復(fù),這會(huì)顯著增加數(shù)據(jù)寫入延遲。

為了解決上述問題,本文在弱哈希方法思想基礎(chǔ)上,提出了面向基于內(nèi)容分塊算法(CDC)的重復(fù)數(shù)據(jù)刪除指紋計(jì)算的優(yōu)化方法R-dedup。CDC能夠?qū)崿F(xiàn)可變長(zhǎng)度分塊,是目前應(yīng)用最廣泛的重復(fù)數(shù)據(jù)刪除分塊算法[10-11]。在此算法基礎(chǔ)上,又衍生出了許多改進(jìn)算法,如TTTD[12]、Bimodal CDC[13]、fastCDC[14]等。由于這些算法都是基于CDC進(jìn)行的改進(jìn),因此R-dedup也可應(yīng)用于這些算法。R-dedup的核心思想是將數(shù)據(jù)塊劃分為更小粒度的48 B等長(zhǎng)數(shù)據(jù)片,利用CDC滑動(dòng)窗口過程中已計(jì)算的數(shù)據(jù)片Rabin指紋,替代原始數(shù)據(jù)作為SHA-1函數(shù)的輸入,計(jì)算數(shù)據(jù)塊對(duì)應(yīng)的SHA-1指紋。因?yàn)镽abin指紋長(zhǎng)度通常為10 B,遠(yuǎn)小于48 B,因此R-dedup減少了SHA-1函數(shù)的輸入數(shù)據(jù)量。Rabin指紋可以直接利用CDC算法滑動(dòng)窗口過程中生成的結(jié)果,無需重復(fù)計(jì)算。實(shí)驗(yàn)結(jié)果表明,R-dedup的SHA-1指紋計(jì)算吞吐率提升至標(biāo)準(zhǔn)CDC方法的165%～422%,系統(tǒng)總體吞吐率提升至標(biāo)準(zhǔn)CDC方法的6%～54%。

1 背景知識(shí)

1.1 基于內(nèi)容的分塊算法

重復(fù)數(shù)據(jù)刪除需要先對(duì)數(shù)據(jù)流進(jìn)行切分,將其劃分為更細(xì)粒度的數(shù)據(jù)塊,以數(shù)據(jù)塊為單位進(jìn)行重復(fù)數(shù)據(jù)檢測(cè)?？勺冮L(zhǎng)度分塊能夠避免因?yàn)樽止?jié)變化造成的數(shù)據(jù)塊漂移問題,檢測(cè)到更多的重復(fù)數(shù)據(jù),因此目前被重復(fù)數(shù)據(jù)刪除系統(tǒng)廣泛使用。

CDC是目前可變長(zhǎng)度分塊的標(biāo)準(zhǔn)算法。CDC的主要原理如圖1所示,通過設(shè)置大小為48 B的滑動(dòng)窗口,從數(shù)據(jù)流的起始處開始滑動(dòng),計(jì)算窗口內(nèi)數(shù)據(jù)的Rabin指紋[15]。之后,通過將Rabin指紋和掩碼進(jìn)行與操作,判斷所得結(jié)果是否等于預(yù)先設(shè)定的魔數(shù)。如果等于預(yù)先設(shè)定的魔數(shù),則將當(dāng)前窗口的最后一個(gè)字節(jié)作為分塊的邊界點(diǎn),當(dāng)窗口在數(shù)據(jù)流中滑動(dòng)結(jié)束后,所形成的邊界點(diǎn)將數(shù)據(jù)流劃分為長(zhǎng)度不同的一系列數(shù)據(jù)塊集合。為了避免出現(xiàn)分塊過大或過小的情況,可設(shè)置分塊大小的最小值與最大值。當(dāng)分塊大小小于最小值時(shí),舍棄當(dāng)前邊界點(diǎn);當(dāng)分塊大小大于最大值時(shí),強(qiáng)制設(shè)置當(dāng)前窗口最后一個(gè)字節(jié)為邊界點(diǎn)。

圖1 CDC原理

1.2 Rabin指紋計(jì)算

Rabin指紋由哈佛大學(xué)的Rabin于1981年提出。對(duì)于任何一個(gè)n位字符串b0,…,bn-1,可將其表示為有限域GF(2)上的n-1次多項(xiàng)式

f(x)=b1xl-1+b2xl-2+…+bl

(1)

隨機(jī)選擇有限域GF(2)上的k次不可約多項(xiàng)式p(x),定義字符串m的Rabin指紋為GF(2)上f(x)除以p(x)后的余數(shù),即k-1次多項(xiàng)式r(x)

r(b1,…,bl)=

(b1xl-1+b2xl-2+…+bl)modp(x)=

r1xk-1+r2xk-2+…+rk

(2)

在CDC算法中,設(shè)置一個(gè)大小為48 B的數(shù)據(jù)窗口,計(jì)算當(dāng)前窗口的Rabin指紋,判斷是否為塊邊界?；瑒?dòng)1 B后,窗口數(shù)據(jù)發(fā)生變化,因此需要重新計(jì)算當(dāng)前窗口的Rabin指紋。如果再次用式(2)計(jì)算Rabin指紋,會(huì)造成不必要的計(jì)算開銷。事實(shí)上,當(dāng)前窗口與滑動(dòng)前窗口的數(shù)據(jù)只有一個(gè)字節(jié)不一樣,因此可以利用上一個(gè)窗口Rabin指紋來計(jì)算當(dāng)前窗口Rabin指紋,公式為

f(b9,…,bl+8)=(b9xl-1+…+bl+8)modp(x)=

(x8(b9xl-9+…+bl)+bl+1x7+…+

bl+8)modp(x)=(x8(b1xl-1+…+

b8xl-8+b9xl-9+…+bl+b1xl-1+…+

b8xl-8)+bl+1x7+…+bl+8)modp(x)=

(x8(r1xk-1+r2xk-2+…+rk+b1xl-1+…+

b8xl-8)modp(x)+bl+1x7+…bl+8)modp(x)=

((x8(f(b1,…,bl)+(b1xl-1+…+

b8xl-8)modp(x))modp(x)+(bl+1x7+…+

bl+8))modp(x)

(3)

通過式(3)可以看出,通過對(duì)多項(xiàng)式做變化,可將f(b9,…,bl+8)表示為f(b1,…,bl)的多項(xiàng)式,從而利用已計(jì)算窗口的Rabin指紋結(jié)果。與式(2)相比,式(3)只需要將f(b1,…,bl)做移位運(yùn)算。

在窗口滑動(dòng)1 B(8 b)后,當(dāng)前窗口從b1,…,bl變?yōu)閎9,…,bl+8,而b9,…,bl+8的Rabin指紋可根據(jù)式(3)利用b1,…,bl已計(jì)算的Rabin指紋f(b1,…,bl)得到。

2 R-dedup設(shè)計(jì)

R-dedup的核心思想是將數(shù)據(jù)塊劃分為更小粒度的48 B等長(zhǎng)小數(shù)據(jù)片,先計(jì)算每個(gè)數(shù)據(jù)片的Rabin指紋,再將數(shù)據(jù)塊包含的所有數(shù)據(jù)片對(duì)應(yīng)的Rabin指紋替代原始數(shù)據(jù),用于計(jì)算數(shù)據(jù)塊對(duì)應(yīng)的SHA-1指紋。R-dedup框架如圖2所示。

圖2 R-dedup框架

2.1 重復(fù)數(shù)據(jù)檢測(cè)

重復(fù)數(shù)據(jù)刪除系統(tǒng)檢測(cè)重復(fù)數(shù)據(jù)的原理是使用一個(gè)函數(shù)h(x),如果兩個(gè)數(shù)據(jù)塊a≠b,則h(a)≠h(b),反之如果a=b,則h(a)=h(b)。SHA-1哈希函數(shù)符合這一要求,目前普遍被重復(fù)數(shù)據(jù)刪除系統(tǒng)作為h(x)函數(shù)使用。R-dedup通過計(jì)算f(g(x))作為數(shù)據(jù)塊的指紋來加速指紋計(jì)算,令g(x)=w(x1)·w(x2)·…·w(xn),其中,·是字符串連接運(yùn)算符,x1,x2,…,xn是數(shù)據(jù)塊x按48 B切分后形成的數(shù)據(jù)片,w(x)為弱哈希函數(shù),例如Rabin哈希函數(shù)。由于Rabin哈希值的長(zhǎng)度通常小于80 b(10 B),小于數(shù)據(jù)片xi的長(zhǎng)度48 B,因此g(x)的長(zhǎng)度小于x的,h(g(x))的計(jì)算量小于h(x)的。CDC分塊過程中需要不斷計(jì)算48 B窗口的Rabin哈希值,因此只需每隔48 B保存一次Rabin哈希值,即可得到w(xi),無需再次計(jì)算。R-dedup算法偽代碼如下。

輸入:數(shù)據(jù)流

輸出:SHA-1指紋

1 獲取數(shù)據(jù)流長(zhǎng)度

2 計(jì)算數(shù)據(jù)片數(shù)量

3 初始化數(shù)據(jù)流指針為0

4 初始化48 B窗口

5 初始化Rabin指紋數(shù)組

6 從數(shù)據(jù)流中讀取48 B數(shù)據(jù)填滿窗口,并將數(shù)據(jù)流指針加48

7 while 數(shù)據(jù)流指針未指向數(shù)據(jù)流末尾do

8 計(jì)算窗口數(shù)據(jù)的Rabin指紋

9 if Rabin指紋形成邊界點(diǎn)then

10 跳出循環(huán)

11 end if

12 if 已滑動(dòng)長(zhǎng)度等于48 B的倍數(shù)then

13 保存當(dāng)前窗口數(shù)據(jù)的Rabin指紋值到數(shù)組

14 end if

15 數(shù)據(jù)流指針加1

16 end while

17 if 窗口數(shù)據(jù)不足48 B then

18 用‘