數(shù)據(jù)分塊算法在定位差異數(shù)據(jù)時的作用分析

黃文豪,齊德昱,謝 嶸,劉 宇,張皓同

(1.廣東外語外貿(mào)大學(xué)南國商學(xué)院 數(shù)字化技術(shù)研究院,廣東 廣州 510545;2.華南理工大學(xué) 計算機科學(xué)與工程學(xué)院,廣東 廣州 510641)

0 引 言

隨著數(shù)據(jù)量的快速增長,如何定位兩個相似數(shù)據(jù)之間的差異數(shù)據(jù),即差異數(shù)據(jù)定位,也得到了快速的發(fā)展。在現(xiàn)有的研究中,學(xué)者們多采取數(shù)據(jù)分塊的方式來找出兩個相似數(shù)據(jù)間不同的分塊,這些分塊則是差異數(shù)據(jù)。這種方式的工作過程如圖1所示。具體的,首先對Data1和Data2按照相同的數(shù)據(jù)分塊算法進行分塊,然后比較兩組分塊之間不同的分塊,這些不同的分塊所組成的數(shù)據(jù)即為差異數(shù)據(jù)。

圖1 差異數(shù)據(jù)定位的過程

學(xué)術(shù)界關(guān)于差異數(shù)據(jù)分塊的研究重點集中在數(shù)據(jù)分塊算法的設(shè)計上。數(shù)據(jù)分塊算法的不同將直接影響差異數(shù)據(jù)定位的效果,比如能否全部定位出不同的數(shù)據(jù)、定位到的差異數(shù)據(jù)中相同數(shù)據(jù)的多少等。

不過學(xué)術(shù)界提出的數(shù)據(jù)分塊算法都是在實驗上驗證算法在差異數(shù)據(jù)定位中起到的作用,并沒有從理論上給出數(shù)據(jù)分塊算法能否定位出所有不同的數(shù)據(jù),也沒有探討數(shù)據(jù)分塊算法中各參數(shù)在差異定位中所起到的作用。因此,該文對差異數(shù)據(jù)定位的過程進行抽象,推導(dǎo)出了這一過程的正確性。同時,還對數(shù)據(jù)分塊算法中參數(shù)與差異數(shù)據(jù)定位的關(guān)系進行了討論。

1 相關(guān)工作

借助數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)這一方法多用在重復(fù)數(shù)據(jù)刪除、數(shù)據(jù)增量同步等領(lǐng)域。數(shù)據(jù)分塊算法是對數(shù)據(jù)進行分塊,通過對每個塊進行處理,解決數(shù)據(jù)整體不易處理的問題,是一種化整為零的思路。該文探討的數(shù)據(jù)差異定位主要是為了更好地應(yīng)用于數(shù)據(jù)增量同步,因為重復(fù)數(shù)據(jù)刪除對分塊的穩(wěn)定性會有額外的要求,不過該文得到的一些結(jié)論也可以在重復(fù)數(shù)據(jù)刪除中起到借鑒作用。

數(shù)據(jù)分塊算法最早應(yīng)用在差異數(shù)據(jù)定位中是A.Tridgell提出的一種基于多輪通訊的同步算法Rsync[1],該算法中利用數(shù)據(jù)分塊算法對需要同步的文件進行等長分塊,然后通過分塊比較得到兩個文件間的差異數(shù)據(jù)。不過Rsync中使用的數(shù)據(jù)分塊算法是固定長度的數(shù)據(jù)分塊算法,這類算法存在字節(jié)漂移的問題:當(dāng)在文件的起始位置插入一個字節(jié),將會導(dǎo)致文件所有的分塊發(fā)生變化。這種問題在定位差異數(shù)據(jù)時會導(dǎo)致發(fā)現(xiàn)的差異數(shù)據(jù)遠大于實際變化的數(shù)據(jù),雖然Rsync采用了別的方法規(guī)避了字節(jié)漂移,但卻大大增加了算法的計算量。在Rsync的基礎(chǔ)上,為了加快差異定位的速度,Lkhagvasuren Ider等人提出了一種兩級分塊策略[2],數(shù)據(jù)塊大小分別為4 MB和32 KB。在第一級,使用4 MB塊大小的索引表,采用字節(jié)索引分塊的方法快速檢測出大尺寸相同的數(shù)據(jù)塊。在第二級,使用32 KB索引表對通過第一級文件相似性檢測生成的整個非重復(fù)數(shù)據(jù)區(qū)域執(zhí)行字節(jié)索引分塊。

為了避免固定長度分塊算法的字節(jié)漂移問題,學(xué)者們開始探索可變長度分塊算法(Content-Defined Chunking,CDC)在差異數(shù)據(jù)定位中的應(yīng)用。最早的可變長度分塊算法基于Rabin指紋[3]的分塊算法,該算法以匹配指紋為分塊依據(jù),增加了分塊的抗字節(jié)漂移能力。Xia Wen等人為了追求分塊速度,提出了FastCDC算法[4],在指紋匹配過程中使用Gear指紋代替Rabin指紋,并在窗口移動過程中使用一次移動兩個字節(jié)的方式加快文件遍歷速度,同時還使用兩種指紋匹配難度增加了分塊的穩(wěn)定性。文章中,作者對FastCDC在單次匹配過程中成功的概率進行了簡單的介紹,并討論了跨字節(jié)時匹配概率的變化,但沒有推敲算法設(shè)計上的優(yōu)劣。為了減少指紋匹配存在的較大計算量,Bjrner Nikolaj等人提出了基于區(qū)間最大值的分塊算法LMC[5],通過尋找一個固定窗口內(nèi)的最大值是否在窗口的中間位置來判斷是否設(shè)置切點,文中探討了LMC算法在尋找切點時的概率問題,但同樣沒有討論這個概率對差異定位的影響。除此之外,還有一些應(yīng)用在重復(fù)數(shù)據(jù)刪除[6-7]中的數(shù)據(jù)分塊算法[8-11],這些算法的作者在論文中也有提及算法的分塊效率、分塊平均長度等,但都沒有討論數(shù)據(jù)分塊算法各參數(shù)對差異數(shù)據(jù)定位的影響。

已有的研究中,學(xué)者們提出了很多數(shù)據(jù)分塊算法以提升差異數(shù)據(jù)定位的效果,比如速度[12-13]、差異數(shù)據(jù)的大小[14-16]。但是這些研究是以實驗數(shù)據(jù)為支撐,通過與已有算法做比較,得到實驗上的優(yōu)勢,然后證明所提算法的先進性。通過實驗的手段來驗證算法的先進性會因為實驗數(shù)據(jù)或算法參數(shù)的不同而產(chǎn)生偏差,且沒有去探討借助數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)的正確性,比如能否定位到所有的不一樣的數(shù)據(jù)。此外,定位到的差異數(shù)據(jù)大小與數(shù)據(jù)分塊算法存在什么關(guān)系,怎樣設(shè)計數(shù)據(jù)分塊算法才能在包含所有不一樣的數(shù)據(jù)的前提下盡可能地減少定位到的差異數(shù)據(jù),這些問題也是現(xiàn)有研究中的空缺。因此,為了解決這些問題,該文將數(shù)據(jù)分塊算法抽象成一種窗口的模式匹配過程,并在此基礎(chǔ)上證明了借助數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)的正確性,同時給出了定位到差異數(shù)據(jù)大小與數(shù)據(jù)分塊算法的關(guān)系,為后人在設(shè)計數(shù)據(jù)分塊算法時提供參考。

2 準備知識

本節(jié)對差異數(shù)據(jù)定位的詳細過程進行闡述,并將這一過程中涉及到的對象進行符號定義以便后文討論。同時,對數(shù)據(jù)分塊算法進行了抽象,并對其中涉及到的參數(shù)等進行了符號定義,以方便后文的討論。

在定位差異數(shù)據(jù)時,使用數(shù)據(jù)分塊算法對data1和data2進行分塊。數(shù)據(jù)分塊算法的目的是對數(shù)據(jù)進行分塊,分塊的依據(jù)是在數(shù)據(jù)中尋找切點,相鄰兩個切點之間的數(shù)據(jù)就屬于一個分塊。數(shù)據(jù)分塊算法可以分為固定長度分塊和基于內(nèi)容的數(shù)據(jù)分塊。固定長度分塊由于存在字節(jié)漂移的問題,在定位差異數(shù)據(jù)時一般不采用?；趦?nèi)容的數(shù)據(jù)分塊算法(Content-Defined Chunking,CDC)是在待分塊數(shù)據(jù)中尋找符合特定條件的數(shù)據(jù)窗口,首先從數(shù)據(jù)的第一個字節(jié)開始,選取窗口大小的相鄰數(shù)據(jù),如果符合特定條件,則在該數(shù)據(jù)窗口的最后一個字節(jié)處設(shè)置切點,然后從下一個字節(jié)開始選取窗口大小的相鄰數(shù)據(jù),繼續(xù)尋找切點。如果不符合,則將窗口往后移動一個字節(jié),繼續(xù)判斷,直至找到符合特定條件的窗口或者數(shù)據(jù)結(jié)束。

該文將尋找符合特定條件的數(shù)據(jù)窗口的過程抽象為基于固定長度窗口的模式匹配,并記模式匹配成功的概率記為θ1。在對已有數(shù)據(jù)分塊算法的研究中發(fā)現(xiàn),大多數(shù)數(shù)據(jù)分塊算法尋找切點的方式符合該抽象模型。在對以往CDC的分析中得到一個有趣的結(jié)論,即對于一個給定的CDC,在一次隨機匹配的過程中,θ為一個可計算的固定值。此外,相鄰窗口匹配成功的概率是不相互獨立的,這是因為在進行模式匹配的過程中是采取逐字節(jié)移動的方式,因此相鄰窗口間會存在數(shù)據(jù)的重疊,如圖2所示。由于Window1,Window2之間存在重疊的數(shù)據(jù),Window1匹配成功有可能增加Window2匹配成功的概率,反之亦然。但是為了更加客觀地對待匹配的隨機性同時降低推導(dǎo)的難度,該文假定所有窗口進行模式匹配時成功或失敗是相互獨立的。

圖2 重疊窗口的情況

基于固定長度窗口的模式匹配過程如圖3所示。對于窗口(圖3中的Window)內(nèi)的數(shù)據(jù),如果滿足預(yù)先設(shè)計的匹配規(guī)則,則視為匹配成功,反之匹配失敗。需要注意的是,匹配成功并不一定會在窗口處形成分塊的切點,比如圖3中,假設(shè)Window1處形成了一個切點,那么即使Window2可以匹配成功也不會產(chǎn)生切點,這是因為下一次的模式匹配是從字節(jié)A3開始的。

圖3 基于固定長度窗口的模式匹配過程

為了方便后文的討論,對用到的一些對象或者名稱進行符號定義。

data1:定位差異數(shù)據(jù)時的原數(shù)據(jù)。

data2:定位差異數(shù)據(jù)時,在data1的基礎(chǔ)上修改之后得到的數(shù)據(jù)。

n:模式匹配窗口的長度。

θ:一個隨機窗口進行模式匹配時成功的概率。

FW(Fit Window):模式匹配成功且形成切點的數(shù)據(jù)窗口。

3 差異數(shù)據(jù)定位正確性與數(shù)據(jù)分塊算法的關(guān)系

本節(jié)討論借助數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)時的正確性。通過給出一些定義,并借助定義來推導(dǎo)差異數(shù)據(jù)定位的正確性。

定義1:字節(jié)數(shù)據(jù)是一個集合,集合中的元素滿足條件:由1個或多個字節(jié)按照特定順序拼接而成數(shù)據(jù)。字節(jié)數(shù)據(jù)記作B。對于b∈B,b中的每個字節(jié)byte,記作byteb。

在存儲領(lǐng)域,任意一個數(shù)據(jù)均可以視為B的一個元素。如果將完全相同的兩個數(shù)據(jù)視為一個,那么數(shù)據(jù)與B中元素是一一對應(yīng)的關(guān)系。對存儲在磁盤上的數(shù)據(jù)進行處理時,默認不會發(fā)生磁盤故障?；谶@一點,在討論的過程中,對于發(fā)生概率小于磁盤故障概率的事件,視為不會發(fā)生。

定義2:<=>,表示B上的一個二元關(guān)系。對于?b1,b2∈B,當(dāng)滿足b1與b2相同時,記作b1<=>b2,反之記作b1<≠>b2。

引理1:對于?b1,b2∈B,如果b1與b2不同的概率p<θ,其中θ表示磁盤損壞的概率,則b1<≠>b2。

證明:因?qū)Υ鎯υ诖疟P上的數(shù)據(jù)進行討論時,發(fā)生概率小于θ的事件視為不會發(fā)生,因此依然存在b1與b2相同,即b1<=>b2。

定義3:對于?b∈B,如果存在B上的一個映射關(guān)系f,使得唯一存在?b'∈B,且f(b)<=>b',則稱f為B的一個屬性,f(b)為b在該屬性上的值。

定義4:對于?b1,b2∈B,f為B的一個屬性,如果f(b1)<=>f(b2)→b1<=>b2,則稱f為B的可信屬性。

引理2:對于?b1,b2∈B,f為B的一個可信屬性,則f(b1)<≠>f(b2)→b1<≠>b2。

證明:反證法,假設(shè)存在b1<≠>b2∧f(b1)<=>f(b2),這與可信屬性的定義矛盾,引理得證。

引理3:MD5哈希是B的可信屬性。

證明:對于?b∈B,其MD5哈希存在唯一性,即MD5哈希是B的一個屬性。對于MD5相同的兩個數(shù)據(jù),它們不同的概率低于磁盤故障的概率,由引理1及可信屬性的定義可知,MD5哈希為B的可信屬性。引理得證。

由定理1可知,對于存在于data1中的字節(jié),如果不存在于data2中,則一定會被檢測到。不過,在實際應(yīng)用中,單檢測出差異的字節(jié)是不夠的,還需要根據(jù)data1和BD來得到data2。

定理2:對于?data1,data2∈B,設(shè)它們之間的差異數(shù)據(jù)為BD,若data1的分塊集合為B1,data2的分塊集合為B2,則B2=B1+BD。

證明:反證法,假設(shè)?b,s.tb∈B2&b?B1&b?BD。由于b∈B2&b?B1,由差異數(shù)據(jù)的定位過程可知b∈BD,這與假設(shè)相矛盾,定理得證。

由定理2可知,B2中所有分塊均可以從B1或BD的分塊中獲得。因此,借助數(shù)據(jù)分塊算法來實現(xiàn)差異數(shù)據(jù)定位時,只需要記錄B2中分塊在B1或BD中對應(yīng)的分塊,就可以在B1所在的節(jié)點,結(jié)合BD來拼接出B2。這就意味著,當(dāng)B1和B2不在同一節(jié)點上時,B1只需要BD就可以得到B2的內(nèi)容,進而可以實現(xiàn)增量同步等目的。

綜合以上討論,使用數(shù)據(jù)分塊算法來實現(xiàn)差異數(shù)據(jù)定位不僅可以保證差異數(shù)據(jù)中包含了所有的變化數(shù)據(jù),還可以借助data1和差異數(shù)據(jù)來獲得data2。

4 差異數(shù)據(jù)大小與數(shù)據(jù)分塊算法的關(guān)系

在理想的情況下,差異數(shù)據(jù)的大小理論上應(yīng)當(dāng)與實際的修改量相同。當(dāng)使用數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)時,由于最小單位是分塊,而不是字節(jié),因此定位出的差異數(shù)據(jù)往往比實際修改量大。為此,該文將對實際得到的差異數(shù)據(jù)大小進行討論。

如上文所說,data2是在data1的基礎(chǔ)上修改得到的,那么尋找data2和data1之間的差異數(shù)據(jù)實際上就是尋找在對data1的一次修改后受影響的分塊。數(shù)據(jù)的修改一般包括三種:增加、刪除和變動。數(shù)據(jù)的修改量也可以有很多種情況,該文首先以單個字節(jié)的變動為例來討論受影響的分塊。假設(shè)data1的分塊結(jié)果如圖4所示。其中FWi表示匹配成功的窗口。設(shè)模式匹配窗口的長度為n,模式匹配成功的概率為θ,data1為無邊界的一段數(shù)據(jù),其長度為L。

圖4 data1的分塊結(jié)果

當(dāng)單個字節(jié)變動發(fā)生后,會有兩種情況發(fā)生:一種是包含該字節(jié)的某個窗口形成了FW,另一種是包含該字節(jié)的所有窗口都沒有形成FW。如果要data1在字節(jié)變動后受影響的分塊,就必須找到受影響的FWi。如果原來的FWi所在的窗口依然是FW,那么受影響的分塊就是字節(jié)變動所在的分塊。如果原來的FWi所在的窗口不再是FW,那么受影響的分塊就是FWi所在的分塊以及相鄰的下一個分塊,小概率影響更多后續(xù)分塊(FWi之間距離較近的情況)。接下來,在這兩種情況下分別討論對FWi的影響。在討論之前,需要有一個假設(shè):不存在兩個滿足匹配條件的窗口有重疊區(qū)域,否則會產(chǎn)生嚴重的字節(jié)漂移問題。

當(dāng)包含該字節(jié)的某個窗口形成了FW時(只會有一個窗口形成FW),會有兩種情況使得原來的FWi依然是FW:一是原來的FWi在新形成的FW之前或兩者不存在重疊區(qū)域,一種是原來的FWi與新形成的FW完全重疊。當(dāng)原來的FWi在新形成的FW之前時,即使存在重疊區(qū)域,也會將新形成的FW破壞掉。設(shè)包含該字節(jié)的某個窗口形成了FW時,原來的FWi依然是FW的概率為P1,則:

P1=(1-θ)n-1

(1)

設(shè)包含該字節(jié)的某個窗口形成了FW的概率為P2,則:

P2=1-(1-θ)n

(2)

當(dāng)包含該字節(jié)的所有窗口都沒有形成FW時,概率記為P3。會有一種情況使得原來的FWi依然是FW:該字節(jié)不在FWi中。設(shè)包含該字節(jié)的所有窗口都沒有形成FW時,原來的FWi依然是FW的概率為P4。則:

P3=1-P2

(3)

P4=(1-θ)n

(4)

設(shè)一次字節(jié)變動所引起的差異數(shù)據(jù)為,則可以得出公式(5)。

P3P4xi+P3(1-P4)(xi+xi+1+▽))

(5)

N=P2*2E(xi)-P2P1E(xi)+P3*2E(xi)-

P3P4E(xi)+▽

(6)

(1-θ)n-1+▽)

(7)

n-1)(2θ(1-θ)2n-1ln(1-θ)-

(1-θ)n-1ln(1-θ))

(8)

θ-1-θ+1+▽

(9)

在定位差異數(shù)據(jù)時,上文已經(jīng)證明差異數(shù)據(jù)中包含了所有變動數(shù)據(jù),那么為了取得更好的定位效果,只需要降低差異數(shù)據(jù)的大小,即讓N盡可能小。既然N與n是正相關(guān)的,且n為正整數(shù),那么令n=1,代入公式(7)得到公式(9)。

理論上,根據(jù)公式(7)可以推導(dǎo)出N與θ的關(guān)系,但是經(jīng)過較長時間的工作之后始終未能得出一個有效的結(jié)果。在后續(xù)的研究中將繼續(xù)努力,以期可以得出N與θ的具體關(guān)系。

綜上所述,在原數(shù)據(jù)只發(fā)生單個字節(jié)變動時,借助數(shù)據(jù)分塊算法定位得到的差異數(shù)據(jù)的大小與數(shù)據(jù)分塊算法的匹配窗口大小正相關(guān)。當(dāng)匹配窗口大小為1時,差異數(shù)據(jù)的大小與窗口匹配成功的概率負相關(guān)。該結(jié)論可以通過圖5形象地說明,圖中C1和C3是分塊中的非匹配窗口字段,C2和C4是匹配窗口字段,深色背景表示因字節(jié)變動產(chǎn)生的差異數(shù)據(jù)。由上文的分析可知,在θ相同的情況下,C1長度與匹配窗口的長度無關(guān),因此在圖5(b)場景下,差異定位的長度與匹配窗口的長度正相關(guān)。同理,在圖5(c)場景下,差異定位的長度與匹配窗口的長度也是正相關(guān)。

圖5 差異數(shù)據(jù)的大小與算法匹配窗口大小的關(guān)系

當(dāng)原數(shù)據(jù)發(fā)生單個字節(jié)的增加或刪除時,可以理解為雙字節(jié)變成了單字節(jié),或單字節(jié)變成了雙字節(jié),進而也可以得出類似的結(jié)論。對于多個字節(jié)發(fā)生變化的情況,可以理解成發(fā)生了多次單字節(jié)變化,進而也同樣可以得出類似的結(jié)論。

因此可以得出結(jié)論:當(dāng)原數(shù)據(jù)發(fā)生變化時,借助數(shù)據(jù)分塊算法定位得到的差異數(shù)據(jù)的大小與數(shù)據(jù)分塊算法的匹配窗口大小成正比。當(dāng)匹配窗口大小為1時,差異數(shù)據(jù)的大小與窗口匹配成功的概率成反比。另外,當(dāng)匹配窗口大小不為1時,需要從公式(7)中計算此時N與θ的關(guān)系。

需要注意的是,在實際使用中,當(dāng)n固定時,θ的值是無法取到任意值的,因為一個匹配窗口內(nèi)的數(shù)據(jù)的可能性是有一定范圍的。比如,一個長度為1的匹配窗口,那么窗口中數(shù)據(jù)的種類最多只有256種,無法依據(jù)這256種可能來設(shè)計任意的匹配概率。此外,當(dāng)差異數(shù)據(jù)定位用在數(shù)據(jù)增量同步等場景時,對數(shù)據(jù)分塊的數(shù)量有要求,分塊數(shù)量的增多會產(chǎn)生更多的網(wǎng)絡(luò)帶寬。因此在定位差異數(shù)據(jù)時,并不是θ越大越好,應(yīng)該先根據(jù)分塊數(shù)量計算出大致的θ值,然后找出滿足θ的最小n值,然后利用公式(7)來尋找最優(yōu)的θ,進而設(shè)計出一個較優(yōu)的數(shù)據(jù)分塊算法。

5 結(jié)束語

首先對借助數(shù)據(jù)分塊算法來定位差異數(shù)據(jù)的過程進行抽象,利用數(shù)據(jù)集合的相關(guān)理論證明了這一過程的正確性,其中包括定位到的差異數(shù)據(jù)包含了所有的變化數(shù)據(jù),原數(shù)據(jù)借助差異數(shù)據(jù)的幫助可以拼接得到變化后的數(shù)據(jù)。然后,將數(shù)據(jù)分塊算法抽象為一種基于固定長度窗口的模式匹配過程,通過推導(dǎo)的方式得出了數(shù)據(jù)分塊算法中窗口大小和匹配成功概率兩個參數(shù)與定位得到的差異數(shù)據(jù)大小之間的關(guān)系。并得出數(shù)據(jù)分塊算法的窗口大小參數(shù)與定位得到的差異數(shù)據(jù)大小成正比,匹配成功概率參數(shù)在窗口大小為1的情況下與定位得到的差異數(shù)據(jù)大小成反比。這對設(shè)計數(shù)據(jù)分塊算法有一定的參考意義。

不過,該文未能給出一個差異數(shù)據(jù)大小與匹配成功的概率之間具體的關(guān)系,此外N與θ的關(guān)系也未能給出一個準確的結(jié)論,有待進一步研究。