R-dedup:一種重復(fù)數(shù)據(jù)刪除指紋計算的優(yōu)化方法

2021-02-01 01:36:56王龍翔董凱王鵬博董小社張興軍朱正東張利平

西安交通大學(xué)學(xué)報 2021年1期

關(guān)鍵詞：方法

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

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

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

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

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

為了解決上述問題,本文在弱哈希方法思想基礎(chǔ)上,提出了面向基于內(nèi)容分塊算法(CDC)的重復(fù)數(shù)據(jù)刪除指紋計算的優(yōu)化方法R-dedup。CDC能夠?qū)崿F(xiàn)可變長度分塊,是目前應(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等長數(shù)據(jù)片,利用CDC滑動窗口過程中已計算的數(shù)據(jù)片Rabin指紋,替代原始數(shù)據(jù)作為SHA-1函數(shù)的輸入,計算數(shù)據(jù)塊對應(yīng)的SHA-1指紋。因為Rabin指紋長度通常為10 B,遠(yuǎn)小于48 B,因此R-dedup減少了SHA-1函數(shù)的輸入數(shù)據(jù)量。Rabin指紋可以直接利用CDC算法滑動窗口過程中生成的結(jié)果,無需重復(fù)計算。實驗結(jié)果表明,R-dedup的SHA-1指紋計算吞吐率提升至標(biāo)準(zhǔn)CDC方法的165%～422%,系統(tǒng)總體吞吐率提升至標(biāo)準(zhǔn)CDC方法的6%～54%。

1 背景知識

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

重復(fù)數(shù)據(jù)刪除需要先對數(shù)據(jù)流進(jìn)行切分,將其劃分為更細(xì)粒度的數(shù)據(jù)塊,以數(shù)據(jù)塊為單位進(jìn)行重復(fù)數(shù)據(jù)檢測。可變長度分塊能夠避免因為字節(jié)變化造成的數(shù)據(jù)塊漂移問題,檢測到更多的重復(fù)數(shù)據(jù),因此目前被重復(fù)數(shù)據(jù)刪除系統(tǒng)廣泛使用。

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

圖1 CDC原理

1.2 Rabin指紋計算

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

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

(1)

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

r(b1,…,bl)=

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

r1xk-1+r2xk-2+…+rk

(2)

在CDC算法中,設(shè)置一個大小為48 B的數(shù)據(jù)窗口,計算當(dāng)前窗口的Rabin指紋,判斷是否為塊邊界。滑動1 B后,窗口數(shù)據(jù)發(fā)生變化,因此需要重新計算當(dāng)前窗口的Rabin指紋。如果再次用式(2)計算Rabin指紋,會造成不必要的計算開銷。事實上,當(dāng)前窗口與滑動前窗口的數(shù)據(jù)只有一個字節(jié)不一樣,因此可以利用上一個窗口Rabin指紋來計算當(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)可以看出,通過對多項式做變化,可將f(b9,…,bl+8)表示為f(b1,…,bl)的多項式,從而利用已計算窗口的Rabin指紋結(jié)果。與式(2)相比,式(3)只需要將f(b1,…,bl)做移位運算。

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

2 R-dedup設(shè)計

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

圖2 R-dedup框架

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

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

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

輸出:SHA-1指紋

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

2 計算數(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 計算窗口數(shù)據(jù)的Rabin指紋

9 if Rabin指紋形成邊界點then

10 跳出循環(huán)

11 end if

12 if 已滑動長度等于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 用‘