數據分塊算法在定位差異數據時的作用分析

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

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

0 引 言

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

圖1 差異數據定位的過程

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

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

1 相關工作

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

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

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

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

2 準備知識

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

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

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

圖2 重疊窗口的情況

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

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

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

data1:定位差異數據時的原數據。

data2:定位差異數據時,在data1的基礎上修改之后得到的數據。

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

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

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

3 差異數據定位正確性與數據分塊算法的關系

本節討論借助數據分塊算法來定位差異數據時的正確性。通過給出一些定義,并借助定義來推導差異數據定位的正確性。

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

在存儲領域,任意一個數據均可以視為B的一個元素。如果將完全相同的兩個數據視為一個,那么數據與B中元素是一一對應的關系。對存儲在磁盤上的數據進行處理時,默認不會發生磁盤故障。基于這一點,在討論的過程中,對于發生概率小于磁盤故障概率的事件,視為不會發生。

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

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

證明:因對存儲在磁盤上的數據進行討論時,發生概率小于θ的事件視為不會發生,因此依然存在b1與b2相同,即b1<=>b2。

定義3:對于?b∈B,如果存在B上的一個映射關系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。

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

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

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

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

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

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

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

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

4 差異數據大小與數據分塊算法的關系

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

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

圖4 data1的分塊結果

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

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

P1=(1-θ)n-1

(1)

設包含該字節的某個窗口形成了FW的概率為P2,則:

P2=1-(1-θ)n

(2)

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

P3=1-P2

(3)

P4=(1-θ)n

(4)

設一次字節變動所引起的差異數據為,則可以得出公式(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)

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

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

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

圖5 差異數據的大小與算法匹配窗口大小的關系

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

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

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

5 結束語

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

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