燕雪峰，丁 葉

（南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院/人工智能學(xué)院，南京，211106）

引 言

隨著大數(shù)據(jù)、云計算等技術(shù)的不斷發(fā)展，數(shù)據(jù)成為了貫穿整個智能制造過程的關(guān)鍵因素[1]。以數(shù)據(jù)為核心，從智能車間生產(chǎn)過程產(chǎn)生的海量數(shù)據(jù)中挖掘有價值的信息來指導(dǎo)車間運行優(yōu)化，已經(jīng)引起學(xué)術(shù)界和工業(yè)界的極大關(guān)注[2]。在智能制造領(lǐng)域需要進(jìn)行數(shù)據(jù)采集及存儲，數(shù)據(jù)包括裝配數(shù)據(jù)、建模數(shù)據(jù)、產(chǎn)線數(shù)據(jù)等，這些數(shù)據(jù)對于智能制造生產(chǎn)發(fā)揮重要作用，為防止這些重要數(shù)據(jù)的丟失造成損失就需要對生產(chǎn)數(shù)據(jù)進(jìn)行保護(hù)。遠(yuǎn)程文件同步[3?5]作為其中的一個重要的數(shù)據(jù)保護(hù)手段受到了廣泛研究，其主要原理是通過將生產(chǎn)機上的文件數(shù)據(jù)同步備份到異地災(zāi)備機來實現(xiàn)容災(zāi)。遠(yuǎn)程文件同步的核心是數(shù)據(jù)同步，高效的同步方法需要在數(shù)據(jù)正確的情況下，盡可能地降低時間、存儲等資源的消耗，所以研究高效的同步算法十分必要。

在過去幾十年的研究中，研究者提出了遠(yuǎn)程同步（Remote synchronization, RSYNC）方法，它是數(shù)據(jù)同步的常用工具[6?8]，該方法只對差異數(shù)據(jù)進(jìn)行傳輸，提高了同步效率, 是目前通用的文件同步系統(tǒng)[9]，適合低帶寬下的同步[10]。但是該方法需要對所有同步數(shù)據(jù)進(jìn)行分塊，對比校驗值，計算文件差異塊，在文件變化數(shù)量少或新增文件較多時，消耗了大量時間。RSYNC 算法如圖1 所示，服務(wù)器與主機相連，在服務(wù)器端對數(shù)據(jù)進(jìn)行固定分塊，并計算各數(shù)據(jù)塊的強、弱校驗碼，形成以弱校驗碼為關(guān)鍵字的哈希表發(fā)送給主機。主機接受哈希表后，按照同樣的分塊長度對主機數(shù)據(jù)進(jìn)行分塊，并計算強、弱校驗碼，通過比對哈希值找到差異數(shù)據(jù)并將差異數(shù)據(jù)塊發(fā)送給服務(wù)器。

目前的研究主要對RSYNC 進(jìn)行預(yù)處理。張靜等[11]提出的兩輪差異數(shù)據(jù)同步算法，根據(jù)差異數(shù)據(jù)塊的比例，在比例較低，即差異數(shù)據(jù)塊數(shù)量較少時，直接用內(nèi)容可變長度分塊（Content?defined chunk?ing, CDC）[12]算法計算差異數(shù)據(jù)塊內(nèi)容得到差異數(shù)據(jù)，在比例較大時仍采用RSYNC 精確查詢進(jìn)行同步，這種方法只有在數(shù)據(jù)差異不大的情況下效果較好，在數(shù)據(jù)差異較大時還是使用了RSYNC 算法進(jìn)行同步，效果不明顯。針對上述問題，王青松等[13]提出了Winnowing 指紋串匹配的重復(fù)數(shù)據(jù)刪除算法，此方法在數(shù)據(jù)分塊前引入分塊大小預(yù)測模型，解決CDC 中分塊大小難以控制的問題，并使用ASCII/Uni?code 編碼方式作為數(shù)據(jù)塊，減少指紋計算開銷，重刪率提升了10% 左右，在指紋計算和對比開銷方面減少了18% 左右。Ghobadi 等[14]提出指紋預(yù)處理目錄結(jié)構(gòu)方法，對原目錄的層次結(jié)構(gòu)采用層次信息、文件名以及文件大小進(jìn)行編號的方式，快速查找出需要采用RSYNC 進(jìn)行評估的文件，這種方法可以減少評估的文件數(shù)量，但由于編號使用了文件大小作為其中的對比依據(jù)，造成數(shù)據(jù)發(fā)生變化而大小未變情況下的對比錯誤，同時該算法因為編碼函數(shù)的限制只能識別修改文件，無法識別新增文件。李帥等[15]提出了基于目錄哈希樹（Directory hash tree，DHT）的數(shù)據(jù)同步方法，該方法在保持與原磁盤目錄樹拓?fù)浣Y(jié)構(gòu)一致的條件下，通過利用DHT 能夠快速確定文件的異同，并對差異文件使用RSYNC 同步算法，從而實現(xiàn)數(shù)據(jù)同步。但該方法中父節(jié)點的Hash 值采用將所有子節(jié)點Hash 值相加，增大碰撞概率，并且由于DHT 結(jié)構(gòu)復(fù)雜，造成構(gòu)建時間較長，影響同步效率。Hu 等[16]提出使用多因素身份驗證的增強型安全備份方案，來加密同步數(shù)據(jù)，防止某些敏感數(shù)據(jù)被攔截，提高數(shù)據(jù)傳輸?shù)陌踩浴hang 等[17]設(shè)計并實現(xiàn)了一個安全性得到增強的數(shù)據(jù)備份和恢復(fù)系統(tǒng)，此系統(tǒng)在原有備份恢復(fù)系統(tǒng)中加入基于數(shù)字證書的身份驗證，提高安全性能。任燕博等[18]提出借助文件系統(tǒng)監(jiān)控機制同步數(shù)據(jù)的方法，通過Inotify 機制監(jiān)控文件目錄下的文件變動情況，提高同步效率。Yang 等[19]設(shè)計基于文件系統(tǒng)的增量備份，對文件內(nèi)容采用Diff 算法進(jìn)行數(shù)據(jù)庫增量備份，降低數(shù)據(jù)的傳輸量。

本文針對上述問題，采用MD5 信息摘要算法（Message digest algorithm，MDA）[20]作為編號中的識別碼同時使用更為簡單的層次結(jié)構(gòu)來構(gòu)建對比表。通過比較文件編號可以快速識別變化文件，并根據(jù)文件的變化類型，選擇合適的備份策略。對于修改文件采取增量同步備份策略，而對于新增文件采用完全同步策略。

1 基于分層哈希編號算法的數(shù)據(jù)同步模型

基于分層哈希編號算法的數(shù)據(jù)同步模型由2 部分組成：（1）服務(wù)器根據(jù)目錄的層次結(jié)構(gòu)，構(gòu)建分層哈希編號表（Hierarchical hash numbering algorithm, HHNT），并傳輸該文件；（2）客戶端接收服務(wù)器發(fā)送的HHNT，根據(jù)目錄層次結(jié)構(gòu)分層對比差異文件。

1.1 HHNT 的構(gòu)建

根據(jù)目錄層次結(jié)構(gòu)，通過編號函數(shù)構(gòu)建每個文件的唯一編號，編號函數(shù)為

C = FilePath*F*( Identifier ) (1)

式中，F(xiàn)ilePath 表示父文件的路徑，F(xiàn) 為文件或文件夾名稱，Identifier 為文件或文件夾的識別碼。如果是文件夾，則設(shè)為-1，如果是文件，則設(shè)為此文件的MD5 值。由于使用了MD5 值作為文件的識別碼，所以文件編號會隨著文件變化而改變，解決了文件內(nèi)容變化而文件大小不變造成的文件對比錯誤問題。HHNT 構(gòu)建算法如下。

輸入：文件夾路徑

輸出：分層目錄哈希表

Begin

for QueIsNotEmpty() do

獲取隊列頭結(jié)點，Ni

if Niis 文件

計算Ni的MD5 值作為Ni的識別碼

end if

if Niis 文件夾

使用“-1”作為Ni的識別碼

將Ni增加到隊列的隊尾

end if

end for

end

構(gòu)建分層的哈希編號表，其具體步驟如下：

步驟1根據(jù)輸入的目錄，對根節(jié)點進(jìn)行編號并加入到隊列中，隊列用來記錄還未編號節(jié)點；

步驟2檢測隊列是否為空，若為空即沒有需要編號的節(jié)點，返回HHNT，若不為空執(zhí)行步驟3；

步驟3取出隊頭元素，計算此節(jié)點的識別碼，如果此節(jié)點是文件，計算其MD5 值作為其識別碼，若為文件夾，“-1”作為其識別碼，并將其子文件加入隊尾，執(zhí)行步驟2。

1.2 對比同步

當(dāng)目錄發(fā)生改變時，根據(jù)層次結(jié)構(gòu)，對比相應(yīng)層的節(jié)點編號，快速區(qū)分出變化文件，并加入不同的同步隊列中，差異文件對比算法如下。

輸入：改變后的文件夾及上個版本的HHNT

輸出：完全同步隊列以及增量同步隊列

Begin

for ComQueIsNotEmpty() do

獲取隊列頭結(jié)點，Ni

獲取對應(yīng)層的編號集合，N[level]

if Niis 文件

if 在N[level]找到Ni的前綴碼

計算Ni的哈希值, Hashi=MD5(path of Ni)

if Hashi匹配

continue

else

將Ni加入增量備份隊列

end if

else

if 在N[level]未找到Ni的前綴碼

計算Ni的哈希值并修改編號, Hashi=MD5(path of Ni)

將Ni加入完全備份隊列

end if

else if Niis 文件夾

if 在N[level]找到Ni的前綴碼

continue

else

計算Ni以及Ni子文件的目錄編號

將Ni以及Ni子文件加入完全備份隊列

end if

end if

end for

end

對比同步步驟如下。

步驟1將目錄根節(jié)點加入隊列中，隊列用來記錄待對比的節(jié)點。

步驟2若隊列不為空，取出隊頭節(jié)點，根據(jù)層次信息，從HHNT 中取出對應(yīng)層的編號集合，若為空則輸出RSYNC 以及完全同步（Full synchronization，F(xiàn)SYNC）隊列。

步驟3如果節(jié)點是文件夾，執(zhí)行步驟4，節(jié)點是文件執(zhí)行步驟5。

步驟4遍歷集合，根據(jù)節(jié)點的路徑和編號的前綴碼對比結(jié)果，判斷是否為新增文件夾，若為新增文件夾，執(zhí)行步驟6；若不是則將此文件的子文件加入到隊列中，執(zhí)行步驟2。

步驟5遍歷集合，將節(jié)點的路徑和編號的前綴碼對比，若匹配，表示此文件存在，計算節(jié)點MD5值和編號中的識別碼對比，若對比失敗，則表示此文件為修改文件，將此文件加入RSYNC 隊列，若前綴碼對比失敗，將其加入FSYNC 隊列，執(zhí)行步驟2。

步驟6通過編號算法，將此文件夾進(jìn)行編號，添加到HHNT 中，并將此文件夾加入FSYNC隊列。

根據(jù)分層哈希編號算法，可以快速分離出變化文件，如圖2 所示。與DHT 算法相比，在構(gòu)建過程中不需要使用復(fù)雜的樹結(jié)構(gòu)以及計算文件夾節(jié)點的哈希值，減少時間消耗，同時降低了文件夾節(jié)點的碰撞概率。

2 分層哈希編號算法在智能制造中的應(yīng)用

圖3 框架流程圖Fig.3 Framework flow chart

基于分層哈希編號算法應(yīng)用在RSYNC數(shù)據(jù)同步之前，根據(jù)智能制造產(chǎn)線數(shù)據(jù)的層次目錄結(jié)構(gòu)，構(gòu)建HHNT。 當(dāng)產(chǎn)線數(shù)據(jù)發(fā)生變化時，對比上個版本的HHNT 即可完成文件同步。 圖3 展示了整體框架流程圖，服務(wù)器對智能制造產(chǎn)線數(shù)據(jù)構(gòu)建HHNT 并發(fā)送給客戶端，客戶端根據(jù)此表分層對比文件編號，分離出變化文件，并對變化文件使用不同的備份策略進(jìn)行同步。

由上述可知，本文方法根據(jù)比對HHNT判斷結(jié)果進(jìn)行文件同步。若文件是未變化文件，則無需對該文件進(jìn)行分塊、校驗值計算、校驗值查找驗證等操作，解決了RSYNC 在文件未變情況下還需進(jìn)行分塊、校驗值計算對比的資源浪費問題。 當(dāng)文件是改變文件時，根據(jù)HHNT 中的編號信息進(jìn)一步判斷是否是新增文件，如果是新增文件，同樣跳過RSYNC 評估，進(jìn)一步減少RSYNC 評估的文件數(shù)量，降低資源以及時間消耗。該方法作為RSYNC 同步的一個預(yù)處理過程，可以有效減少使用RSYNC 評估的文件夾和文件的數(shù)量。如果不使用預(yù)處理方法，標(biāo)準(zhǔn)的RSYNC 將對整個文件結(jié)構(gòu)進(jìn)行遍歷評估，在有限數(shù)據(jù)發(fā)生改變的情況下，這將是不必要的開銷。

3 仿真與實驗分析

為了驗證上述分層哈希編號算法的有效性，本文對磁盤在不同變化程度情況下的同步時間進(jìn)行對比。同步時間是同步算法最重要的評價標(biāo)準(zhǔn)，本文中的同步時間采用系統(tǒng)時間函數(shù)，計算同步進(jìn)程所用時間。

本文使用1 GB 的智能制造產(chǎn)線數(shù)據(jù)進(jìn)行實驗，該環(huán)境包含19 個層次級別，共10 000 個文件。 分別記錄無差同步、全同步、差異同步3 種情況下的同步時間。實驗結(jié)果如圖4 所示。

圖4 同步時間比較Fig.4 Comparison of synchronization time

圖4 中，在無差同步情況下，本文方法不像標(biāo)準(zhǔn)RSYNC 那樣使用精準(zhǔn)查詢找到差異數(shù)據(jù)塊，只對目錄構(gòu)建HHNT 記錄文件編號便可完成同步，所以在時間消耗上效果明顯，特別是當(dāng)數(shù)據(jù)量越大時，所用時間相差越明顯。在全同步情況下，即包含大量新增文件時，從圖4 中可以看出與無差同步相比，本文方法只增加了很短時間便完成同步，而標(biāo)準(zhǔn)方法卻直線上升，這是由于本文方法不需要對這些新增文件再使用RSYNC 算法，只需花費很短的時間對比分層目錄哈希表并更新即可。在差異同步情況下，本文方法只對修改文件使用了RSYNC 進(jìn)行精確查詢，所以時間消耗變大，但是這與標(biāo)準(zhǔn)RSYNC對全目錄進(jìn)行精確查詢相比，在時間消耗上還是有很大改善的。從整體上來看，標(biāo)準(zhǔn)RSYNC 算法消耗的時間上升趨勢較快，而本文方法只有當(dāng)差異數(shù)據(jù)較多情況下，時間消耗才會有較明顯的上升。

綜上，在智能制造產(chǎn)線數(shù)據(jù)變化有限的情況下，本文的預(yù)處理方法與標(biāo)準(zhǔn)RSYNC 相比可極大降低同步時間；與目錄哈希表方法相比，本文方法可以避免哈希碰撞引起的文件同步錯誤問題，且在同步時間上提高了30% 左右。

4 結(jié)束語

本文提出的分層哈希編號方法，作為RSYNC 的預(yù)處理方法，結(jié)合目錄層次結(jié)構(gòu)進(jìn)行編號，通過比對編號找出修改文件，對修改文件使用RSYNC 進(jìn)行同步，其他變化文件使用完全同步，有效降低評估文件數(shù)量，在時間消耗上獲得較大提升。當(dāng)然本方法還存在一定的不足，由于該方法仍需遍歷對比整個文件夾的編號，所以未來需要設(shè)計一個識別文件層次的算法，快速定位到文件變化的目錄層級，優(yōu)化對比算法，進(jìn)一步提高同步效率。同時，在大量新增文件的情況下，完全同步中的網(wǎng)絡(luò)資源消耗仍是一個需要優(yōu)化的問題，需要尋找合適的壓縮算法解決該問題。