曾暢，蔣文保，郭陽楠

（北京信息科技大學(xué)信息管理學(xué)院，北京 100085）

0 概述

隨著信息時代的到來，分布式系統(tǒng)得到了廣泛的應(yīng)用，包括個人使用多臺主機(jī)保存文件與數(shù)據(jù)，企業(yè)利用總部、分部服務(wù)器來運(yùn)行業(yè)務(wù)數(shù)據(jù)等。個人由于工作場景、工作需求的不同使用多臺主機(jī)工作，導(dǎo)致文件數(shù)據(jù)分散且難以同步更新。企業(yè)要求各分部服務(wù)器與總部服務(wù)器保持實(shí)時更新以及通過遠(yuǎn)程服務(wù)器備份來應(yīng)對異常情況。大型企業(yè)及單位需要同步或備份的文件數(shù)據(jù)量較大且更新頻繁，采用傳統(tǒng)完全拷貝式同步或備份難以滿足其要求。這些需求促使文件數(shù)據(jù)同步方法的發(fā)展［1-2］。目前，國內(nèi)所進(jìn)行的同類工作多為遠(yuǎn)程同步系統(tǒng)或文件備份架構(gòu)的研究，針對文件數(shù)據(jù)同步算法的優(yōu)化研究較少［3］。

基于差異的文件同步算法改進(jìn)了傳統(tǒng)文件同步中將文件庫所有文件重新傳輸一遍的缺點(diǎn)［4］，在一定程度上提高了同步的效率。其中Rsync 同步算法是被廣泛使用的遠(yuǎn)程同步算法［5-6］，其核心方法是計算服務(wù)器端和客戶端文件庫的差異，以及通過差異計算對不同部分進(jìn)行同步更新，保證兩端文件的一致性。目前，國內(nèi)外對于文件數(shù)據(jù)同步的研究主要是基于Rsync 算法［7］。ZHANG 等［8］提出一種新的增量同步方法SimpleSync，根據(jù)服務(wù)器端不主動修改云存儲服務(wù)中備份文件的特點(diǎn)，去掉了Rsync 中的冗余步驟，僅通過一次通信就可以實(shí)現(xiàn)客戶端和服務(wù)器端之間的同步。該方法在計算差異部分時仍存在使用大量哈希算法的問題。IRMAK 等［9］提出一種基于冗余碼的新方法，通過對單輪協(xié)議的文件進(jìn)行同步，以顯著地改進(jìn)Rsync 算法。盡管這些方法都在實(shí)踐中對Rsync 進(jìn)行改進(jìn)以提升同步效率，但是都未從根本上減少同步過程中時間和資源的消耗。

現(xiàn)有的大多數(shù)同步算法需要逐個對文件瀏覽對比并進(jìn)行差異計算，增加了性能消耗，以及缺少一致性承諾，無法快速判斷文件庫是否產(chǎn)生新變動和同步完全。在對文件進(jìn)行查找比對和同步后，現(xiàn)有算法未對操作狀態(tài)和更新結(jié)果進(jìn)行備份［10］，在恢復(fù)文件庫原有版本面臨諸多困難。

本文提出一種基于操作系統(tǒng)的文件同步方法hcsync。通過對文件庫進(jìn)行差異監(jiān)視，利用哈希鏈記錄全部文件操作狀態(tài)。由于有序哈希鏈的節(jié)點(diǎn)包含文件/目錄的變化信息，并記錄了相關(guān)操作的狀態(tài)，因此通過哈希鏈的比較能快速找到變化的文件/目錄，同時跳過沒有變化的文件/目錄，從而提高了同步效率［11-12］。鏈尾哈希值能滿足快速驗(yàn)證文件庫的變動情況和一致性。通過服務(wù)器端鏈尾哈希值判斷文件庫是否產(chǎn)生新的更新，利用客戶端鏈尾哈希值判斷鏈尾和服務(wù)器端的文件庫是否保持一致性。由于哈希鏈會記錄文件庫的相關(guān)操作狀態(tài)，因此使用者可以通過溯源哈希鏈查詢認(rèn)證或撤銷某次操作。

1 相關(guān)工作

1.1 Inotify 特性

Inotify 是一個Linux 內(nèi)核特性，為用戶提供監(jiān)控文件系統(tǒng)的接口，并記錄某些事件，例如讀、寫、刪除等操作，以及跟蹤事件的源頭、目標(biāo)等細(xì)節(jié)［13］。Inotify 在虛擬文件系統(tǒng)（Virtual File System，VFS）層中工作。VFS 又稱虛擬文件系統(tǒng)開關(guān)，采用標(biāo)準(zhǔn)的UNIX 系統(tǒng)調(diào)用讀寫位于不同物理介質(zhì)上的不同文件系統(tǒng)。

本文方法根據(jù)Inotify 構(gòu)建哈希鏈，監(jiān)控文件庫中的文件數(shù)據(jù)變化來獲取新建、修改、移動、刪除等事件的相關(guān)屬性。對于不同系統(tǒng)的服務(wù)器，在哈希鏈構(gòu)造時所監(jiān)控的系統(tǒng)接口存在不同情況，如Linux系統(tǒng)下使用Inotify 接口，windows 系統(tǒng)下使用WinApi 接口等，需要根據(jù)不同的系統(tǒng)做適當(dāng)?shù)恼{(diào)整。

1.2 哈希鏈

哈希鏈的思想最初由美國數(shù)學(xué)家LAMPORT［14］提出，用于一種安全通信的用戶密碼認(rèn)證方法。利用哈希運(yùn)算對密碼進(jìn)行多次迭代，所得的密文序列具有較優(yōu)的抗干擾性、防篡改性，且根據(jù)最后一次加密密文即可驗(yàn)證整條密文序列。

近年來，哈希鏈技術(shù)的研究和應(yīng)用在不斷地拓展和豐富。HUANG 等［15］提出一種基于哈希鏈的災(zāi)后恢復(fù)數(shù)據(jù)可用性監(jiān)控方法，解決分布式系統(tǒng)中數(shù)據(jù)備份及數(shù)據(jù)恢復(fù)問題。MOTOHASHI 等［16］提出一種基于區(qū)塊鏈與客戶端哈希鏈相結(jié)合的mHealth系統(tǒng)，確保醫(yī)療機(jī)構(gòu)數(shù)據(jù)管理的安全性、可擴(kuò)展性和可靠性。YE 等［17］提出一種基于哈希鏈的可信DNP3-BAE 廣播認(rèn)證加密協(xié)議，解決了廣播模式下消息安全認(rèn)證機(jī)制缺失的問題。ZHAO 等［18］提出一種基于哈希鏈的跨境身份認(rèn)證和隱私保護(hù)方案，通過哈希鏈的安全特性來管理網(wǎng)絡(luò)中的數(shù)據(jù)信息。

1.3 Rsync 算法

Rsync 是UNIX/Linux 下文件同步算法［19］。該算法對文件數(shù)據(jù)進(jìn)行對比檢驗(yàn)，在服務(wù)器端和客戶端傳輸兩個文件庫的不同部分，而不是完全拷貝式傳輸，實(shí)現(xiàn)了增量變化同步，提升效率。Rsync 可快速對比在服務(wù)器端和客戶端磁盤中相同目錄下的文件，查出兩端的區(qū)別，并對客戶端上不同的部分進(jìn)行同步更新。

Rsync 算法由檢查模式和同步模式兩部分組成，檢查模式?jīng)Q定哪些文件需要同步，同步模式?jīng)Q定傳輸變化文件數(shù)據(jù)。其中檢查模式分為“quick check”策略和常規(guī)策略?！皅uick check”策略如下：

1）同步端創(chuàng)建文件列表，文件列表中包含文件的一些屬性信息，主要包括文件大小len、修改時間mtime 等。

2）“quick check”策略快速檢查兩端文件列表中相同文件的文件大小len、修改時間mtime 是否一致。如果不一致，則表明該文件為待傳輸文件，對其執(zhí)行常規(guī)策略同步操作；如果一致，“quick check”策略認(rèn)定該文件相同，不需要傳輸。

常規(guī)策略過程如下：1）客戶端將文件f 數(shù)據(jù)分成沒有重疊的m 字節(jié)數(shù)據(jù)塊，如果最后一塊不足m 字節(jié)，則填充為m 字節(jié)；2）每個數(shù)據(jù)塊分別計算強(qiáng)弱校驗(yàn)碼，強(qiáng)校驗(yàn)碼是通過可靠的哈希函數(shù)獲得，并傳輸給服務(wù)器端；3）服務(wù)器端遍歷搜索文件f1，產(chǎn)生強(qiáng)弱校驗(yàn)碼并與客戶端發(fā)送的強(qiáng)弱校驗(yàn)碼進(jìn)行對比，首先匹配弱校驗(yàn)和，如果相同說明是同一個數(shù)據(jù)塊，如果強(qiáng)校驗(yàn)和也相等，則說明兩個數(shù)據(jù)塊相同，繼續(xù)比較下一個數(shù)據(jù)塊，如果不相等跳轉(zhuǎn)到下一個字節(jié)，對數(shù)據(jù)塊進(jìn)行匹配，記錄不匹配數(shù)據(jù)塊索引與偏移量內(nèi)容，直到得出所有偏移量內(nèi)容，則停止比較［20］；4）在客戶端獲取服務(wù)器端的不匹配數(shù)據(jù)塊索引和偏移量內(nèi)容時，通過這些數(shù)據(jù)重組臨時文件，使其內(nèi)容與文件f1 相同，當(dāng)臨時文件重組完成后，修改該臨時文件的屬性信息（權(quán)限、mtime 等），然后將該臨時文件替換客戶端文件f，客戶端文件f 與服務(wù)器端文件f1保持同步。

1.4 基于哈希樹的同步方法

基于哈希樹的同步方法是根據(jù)文件庫的目錄結(jié)構(gòu)構(gòu)建有序哈希樹，并利用此哈希樹來獲取文件庫的變化并快速同步［21］。文獻(xiàn)［22］提出的基于有序哈希樹同步方法中，哈希樹各節(jié)點(diǎn)由四元組＜p，Hash，firstChild，nextSibling＞表示。其中：p表示路徑；Hash表示該節(jié)點(diǎn)存儲的哈希值，在該方法中Hash 值為路徑與時間戳拼接進(jìn)行運(yùn)算的哈希值；firstChild 為該節(jié)點(diǎn)的第一個子節(jié)點(diǎn)；nextSibling 為該節(jié)點(diǎn)的后繼兄弟節(jié)點(diǎn)。因?yàn)楣涞臉?gòu)建過程是遍歷目錄樹，依次計算子節(jié)點(diǎn)的哈希值，之后回溯到父節(jié)點(diǎn)，按順序拼接子節(jié)點(diǎn)哈希值，并將拼接結(jié)果的哈希值作為父節(jié)點(diǎn)的哈希值。一旦文件庫資料發(fā)生變化，其對應(yīng)有序哈希樹的根節(jié)點(diǎn)哈希值必定發(fā)生變化，如果根節(jié)點(diǎn)哈希值未發(fā)生變化，則文件庫未產(chǎn)生新變化。這就是有序哈希樹能快速檢測和定位文件庫變化的原理。

2 總體設(shè)計

2.1 符號定義

基于有序哈希鏈的文件數(shù)據(jù)同步方法所使用的符號、函數(shù)以及對應(yīng)參數(shù)如表1 所示。

表1 本文方法的重要符號說明Table 1 Important symbol description of the proposed method

2.2 整體架構(gòu)

基于有序哈希鏈的同步模型可以用一個三元組表示：

Monitor 表示對文件操作或事務(wù)日志的監(jiān)聽算法，以獲取文件庫的文件數(shù)據(jù)操作狀態(tài)，最終輸出一個文件庫變化內(nèi)容序列。操作狀態(tài)的分類以文件系統(tǒng)接口和事務(wù)日志提供的類型為基準(zhǔn)。

Setup 表示哈希鏈的構(gòu)建算法，輸入為Monitor 算法中變化內(nèi)容序列，將變化內(nèi)容Xi作為哈希鏈上的新節(jié)點(diǎn)，最終輸出一個有序哈希鏈(C1,C2,…,Cn)。該算法將文件庫的操作狀態(tài)以時間順序，通過哈希函數(shù)迭代形成一個能夠記錄文件庫所有操作狀態(tài)的有序哈希鏈。

Sync表示根據(jù)哈希鏈執(zhí)行邏輯同步，根據(jù)哈希鏈上所記錄的操作狀態(tài)o_type=(mov,add,del,mod)，執(zhí)行服務(wù)器端相同的文件數(shù)據(jù)變化操作，以保證兩端文件庫的一致性。

hcsync 方法整體架構(gòu)如圖1 所示。該方法不需要對文件庫中的文件數(shù)據(jù)逐一比較，就可以快速獲取文件變化并保持更新，避免了傳統(tǒng)同步方法中需要全盤檢索文件庫以獲取差異文件而耗費(fèi)的額外資源與時間。

圖1 hcsync 方法整體架構(gòu)Fig.1 Overall architecture of hcsync method

2.3 構(gòu)建與同步流程

有序哈希鏈的構(gòu)建流程如圖2 所示。

圖2 有序哈希鏈的構(gòu)建流程Fig.2 Construction procedure of ordered Hash chain

服務(wù)器端通過系統(tǒng)接口監(jiān)測文件庫，實(shí)時獲取文件庫變化生成的六元組節(jié)點(diǎn)，并構(gòu)成變化內(nèi)容序列(X1,X2,…,Xn)，再由變化內(nèi)容序列計算得到哈希序列，最終迭代哈希函數(shù)得到哈希鏈。

客戶端通過有序哈希鏈對服務(wù)器端文件庫進(jìn)行同步，同步流程如圖3 所示。

圖3 客戶端同步流程Fig.3 Procedure of client synchronization

客戶端首先向服務(wù)器端發(fā)出同步請求，獲取最新哈希鏈并與本地哈希鏈做比較，以快速獲取最新文件變化。在比較過程中獲取新生成的哈希鏈節(jié)點(diǎn)，然后按照順序執(zhí)行節(jié)點(diǎn)操作。具體同步步驟如下：

1）客戶端同步服務(wù)器端文件庫，如果是首次同步，下載完整文件庫與哈希鏈至本地，否則客戶端對比兩端哈希鏈，并進(jìn)行相應(yīng)更新操作。

2）當(dāng)兩端哈希鏈鏈尾的哈希值不相等時，根據(jù)服務(wù)器端哈希鏈新增加的變化節(jié)點(diǎn)更新文件庫。在執(zhí)行當(dāng)前哈希鏈節(jié)點(diǎn)變化操作時，需要對本節(jié)點(diǎn)進(jìn)行哈希值驗(yàn)證，以保證哈希鏈的不可篡改性和完整性。如果o_type=0 為移動事件，客戶端執(zhí)行相同文件/目錄移動操作；o_type=1 為新建事件，客戶端同步該新文件至本地；o_type=2 為刪除事件，刪除客戶端文件庫的該文件/目錄；o_type=3 為修改事件，刪除本地文件并同步最新文件。

3）執(zhí)行完所有新增變化節(jié)點(diǎn)，文件庫同步更新完畢，此時留存最新哈希鏈至本地。當(dāng)服務(wù)器端哈希鏈過長時，同步端可根據(jù)需要留存部分哈希鏈，僅根據(jù)鏈尾哈希值即可判斷是否同步完全。

3 單層哈希鏈

3.1 單層哈希鏈構(gòu)建方法

單層哈希鏈的結(jié)構(gòu)如圖4 所示。

圖4 單層哈希鏈結(jié)構(gòu)Fig.4 Structure of single layer Hash chain

該方法根據(jù)先后次序?qū)⒎?wù)器端文件庫目錄、文件變化看作一個變化序列(X1,X2,…,Xn)。變化序列內(nèi)容可以用六元組表示：

本文通過哈希函數(shù)計算每一個變化內(nèi)容的哈希值，如圖4 中由變化序列計算得到的哈希序列(h1,h2,…,hn)，再通過哈希函數(shù)對哈希序列進(jìn)行迭代，生成哈希鏈。哈希鏈節(jié)點(diǎn)由八元組表示：

節(jié)點(diǎn)哈希值是通過哈希函數(shù)對存在變化內(nèi)容的哈希值與上一節(jié)點(diǎn)的哈希值共同處理獲得，由多次計算得到的節(jié)點(diǎn)Hash 值構(gòu)成一條哈希鏈。單層哈希鏈構(gòu)建方法的步驟如下：

1）系統(tǒng)監(jiān)測到文件庫存在數(shù)據(jù)更新，將每一次變化內(nèi)容按照時間順序生成變化內(nèi)容序列。

2）取出變化內(nèi)容序列頭部一個變化內(nèi)容Xi，為此次內(nèi)容創(chuàng)建有序哈希鏈的節(jié)點(diǎn)：

3）對變化事件Xi進(jìn)行哈希運(yùn)算hi=H(Xi)。

4）獲取哈希鏈末尾節(jié)點(diǎn)的哈希值，previous_Hash=Ci-1[Hash]；如果哈希鏈為空，previous_Hash=null。

5）記Ci[Hash]=H(hi+previous_Hash)，并將其添加至節(jié)點(diǎn)：

6）將哈希鏈節(jié)點(diǎn)Ci添加至哈希鏈尾部，彈出變化內(nèi)容序列頭部Xi。

7）若變化內(nèi)容序列為空，退出；否則進(jìn)入步驟2。

3.2 單層哈希鏈同步方法

算法1單層哈希鏈同步算法

4 雙層哈希鏈

4.1 雙層哈希鏈構(gòu)建方法

本文提出一種基于目錄-文件雙層哈希鏈，其結(jié)構(gòu)如圖5 所示。

圖5 雙層哈希鏈結(jié)構(gòu)Fig.5 Structure of double layer Hash chain

該方法將服務(wù)器端文件庫變化分為目錄哈希鏈和文件哈希鏈。目錄哈希鏈作為主鏈記錄所有目錄的變化，在每個目錄下都存在一個文件哈希鏈記錄該目錄下文件的變化。當(dāng)文件庫存在文件數(shù)據(jù)更新時，主鏈?zhǔn)紫扔涗浽撐募鶎倌夸涀兓?，再到第二級該目錄下的文件哈希鏈記錄文件變化?nèi)容。

該方法根據(jù)先后次序?qū)⒎?wù)器端文件庫變化視作一個變化序列(X1,X2,…,Xn)，首先根據(jù)目錄變化生成目錄哈希鏈節(jié)點(diǎn)：

再到該目錄下文件哈希鏈生成文件哈希鏈節(jié)點(diǎn)：

雙層哈希鏈的基本構(gòu)造方法步驟如下：

1）系統(tǒng)監(jiān)測到文件庫存在數(shù)據(jù)更新，將每一次變化內(nèi)容按照時間順序生成變化內(nèi)容序列。

2）取出變化內(nèi)容序列頭部Xi中的目錄部分，為此次內(nèi)容創(chuàng)建目錄哈希鏈的節(jié)點(diǎn)：

愛是春雷，能驚醒迷途的學(xué)生；愛如夏雨，能沁入學(xué)生的心脾；愛是秋風(fēng)，能拂去學(xué)生心靈的塵垢；愛如冬日，能溫暖學(xué)生的心靈。

3）對變化內(nèi)容Xi目錄的變化部分進(jìn)行哈希運(yùn)算。

4）獲取目錄哈希鏈末尾節(jié)點(diǎn)的哈希值，previous_Hash=Di-1[Hash]。如果哈希鏈為 空，previous_Hash=null。

5）記Di[Hash]=H(hi+previous_Hash)，并將其添加至目錄哈希鏈節(jié)點(diǎn)Di中。

6）將目錄哈希鏈節(jié)點(diǎn)Di添加至目錄哈希鏈尾部。若type=3，進(jìn)入第二層src_path 目錄下的文件哈希鏈；否則彈出變化內(nèi)容序列頭部Xi并轉(zhuǎn)入步驟9。

7）根據(jù)Xi文件變化部分創(chuàng)建src_path 目錄下文件哈希鏈的節(jié)點(diǎn)Fi，構(gòu)建節(jié)點(diǎn)的過程與目錄哈希鏈相同。

8）將文件哈希鏈節(jié)點(diǎn)Fi添加至文件哈希鏈尾部，彈出變化內(nèi)容序列頭部Xi。

9）若變化內(nèi)容序列為空，則退出；否則轉(zhuǎn)入步驟2。

4.2 雙層哈希鏈同步方法

雙層哈希鏈基于雙層結(jié)構(gòu)，將目錄和文件變化分級存儲。在同步過程中只需要對比兩端目錄哈希鏈鏈尾的哈希值，即可判斷是否存在文件庫更新。如果是目錄變化，對目錄執(zhí)行相關(guān)操作；如果是目錄下的文件變化，則比較該目錄下的文件哈希鏈并更新文件，執(zhí)行結(jié)束后返回目錄哈希鏈?？蛻舳藞?zhí)行完所有目錄哈希鏈新增的變化節(jié)點(diǎn)后，留存最新的雙層哈希鏈并作為本地哈希鏈，同步完成。雙層哈希鏈同步如算法2 所示。

算法2 雙層哈希鏈同步算法

5 安全性分析

本文驗(yàn)證所提同步方法的安全性，證明如下：

引理假設(shè)哈希鏈構(gòu)建方法中使用的哈希函數(shù)具有密碼學(xué)安全性。不可篡改性是指在哈希鏈同步時，哈希鏈無法被攻擊者惡意篡改其內(nèi)容。

證明每個哈希序列節(jié)點(diǎn)Xi包含h_id、src_path、dest_path、p_type、o_type、timestamp。由哈希鏈構(gòu)建公式可得：

若哈希鏈內(nèi)容被惡意篡改，即Xi轉(zhuǎn)變?yōu)閄′i，則說明h_id 轉(zhuǎn)變?yōu)閔_id′，或src_path 轉(zhuǎn)變?yōu)閟rc_path′，或dest_path 轉(zhuǎn)變?yōu)閐est_path′，或p_type 轉(zhuǎn)變?yōu)閜_type′，或o_type 轉(zhuǎn)變?yōu)閛_type′，或timestamp 轉(zhuǎn)變?yōu)閠imestamp′，則無法通過哈希值驗(yàn)證，如式（2）所示：

由于節(jié)點(diǎn)內(nèi)容被篡改，因此必然存在Hashi≠Hash′i，則哈希鏈驗(yàn)證不通過。即使篡改節(jié)點(diǎn)Ci的哈希值Hashi為惡意篡改后 的Hash′i，也會導(dǎo)致下一節(jié)點(diǎn)無法通過哈希值驗(yàn)證，如式（3）所示：

因此，本文方法可以實(shí)現(xiàn)不可篡改性，證畢。

除了不可篡改性，本文方法還具有以下安全特性：1）完整性，將文件庫所有更新變化記錄在哈希鏈中，在完成同步后可確保更新內(nèi)容的完整性以及與服務(wù)器端文件庫的一致性；2）不可抵賴性，根據(jù)哈希鏈鏈尾的哈希值即可判斷所有節(jié)點(diǎn)變化內(nèi)容都已被執(zhí)行，哈希鏈上的所有更新已同步；3）可溯源性，作為一條基于時間順序記錄文件庫所有變化的有序哈希鏈，所有更新內(nèi)容在哈希鏈上且可查詢，并且通過逆向操作得到想要恢復(fù)的文件庫版本。

表2 所示為本文同步方法與當(dāng)前其他同步方法的安全性對比。其中“√”表示該方法具有這種特性，“×”表示不具有這種特性。從表2 可以看出，本文同步方法具有一定的優(yōu)勢。

表2 各同步方法的安全性對比Table2 Security comparison of various synchronization methods

6 效率分析

6.1 實(shí)驗(yàn)設(shè)計

本文實(shí)驗(yàn)采用單層哈希鏈進(jìn)行對比，使用的哈希函數(shù)為SHA-3，將客戶端同步服務(wù)器端文件庫的過程分為以下三種實(shí)驗(yàn)：1）當(dāng)文件庫未發(fā)生改變時，hcsync 與Rsync 同步時間效率對比；2）hcsync 與使用“quick check”策略的Rsync 同步時間效率對比；3）hcsync 與使用常規(guī)策略的Rsync 同步時間效率對比。當(dāng)Rsync 使用獨(dú)特的“quick check”策略時，可以實(shí)現(xiàn)快速同步備份數(shù)據(jù)的目的。實(shí)驗(yàn)一在文件庫未變動時進(jìn)行同步效率對比，補(bǔ)充了文件庫同步時含有變動和未變動的情況。實(shí)驗(yàn)二和實(shí)驗(yàn)三分別對比兩種策略下Rsync 的同步效率。

客戶端首次同步服務(wù)器端時需要下載整個文件庫，但在后續(xù)同步或備份過程中都是更新文件變化，初始同步通常只發(fā)生一次，后續(xù)的同步是文件庫的局部更新。在此基礎(chǔ)上，本文設(shè)計文件庫文件數(shù)據(jù)發(fā)生變化和未發(fā)生變化兩種情況，涵蓋了在日常使用中的絕大多數(shù)情況。其中本文實(shí)驗(yàn)的文件庫變化以文件新增為代表。

本文實(shí)驗(yàn)配置為Quad-Core Intel Core i7 2.2 GHz CPU、4 GB RAM、Ubuntu 20.04 LTS操作系統(tǒng)。

本文設(shè)計了三種情況下Rsync 方法與hcsync 方法的對比實(shí)驗(yàn)，以測量兩種方法實(shí)際的文件同步效率，并與htsync 方法進(jìn)行對比。算法參數(shù)為兩端存儲目錄/root/test。實(shí)驗(yàn)結(jié)果中關(guān)于Rsync 和基于有序哈希樹的同步方法htsync 對比數(shù)據(jù)來源于文獻(xiàn)［22］。

6.2 實(shí)驗(yàn)結(jié)果

6.2.1 文件庫未變動的實(shí)驗(yàn)結(jié)果

在文件庫未變動的情況下，本文實(shí)驗(yàn)的文件大小為95 MB、190 MB、285 MB、380 MB、475 MB 和570 MB，未產(chǎn)生相應(yīng)文件的數(shù)據(jù)傳輸。Thcsync、Thtsync分別表示hcsync、htsync 同步時間，TRsync和T′Rsync分別表示與hcsync 和htsync 相同實(shí)驗(yàn)環(huán)境下的同步時間?；诠ｆ溑c哈希樹的同步時間加速比分別如式（4）和式（5）所示：

表3 所示為在不同環(huán)境下hcsync 與Rsync 的同步性能對比和htsync 與Rsync 的同步性能對比。在文件庫未變動的情況下，hcsync、Rsync、htsync 都需要快速判斷客戶端與服務(wù)器端之間文件庫的異同，如果未產(chǎn)生變化時便可結(jié)束更新，且hcsync 和htsync 都能較快地完成同步。從表3 可以看出，hcsync 和htsync 的平均加速比分別為94.85% 和3.63%。hcsync 和htsync 相較于Rsync 都不需要對文件庫進(jìn)行逐個文件對比，但htsync 需要對比哈希樹與節(jié)點(diǎn)哈希值，導(dǎo)致時間延長。hcsync 只需對比鏈尾哈希值即可判斷兩端文件庫的差別。

表3 在文件庫未變動情況下不同方法的同步性能對比Table 3 Synchronization performance comparison among different methods without changing the file library

在文件庫未改動的情況下，hcsync 和Rsync 的同步時間對比如圖6 所示，hcsync 相較于Rsync 的同步時間大幅減少。

圖6 在文件庫未變動情況下不同方法的同步時間對比Fig.6 Synchronization time comparison among different methods without changing the file library

6.2.2 “quick check”策略下的實(shí)驗(yàn)結(jié)果

本文在文件庫初始大小為0 和每次新增95 MB的條件下進(jìn)行實(shí)驗(yàn)，當(dāng)客戶端文件庫同步結(jié)束后，文件庫大小分別對應(yīng)為95 MB、190 MB、285 MB、380 MB、475 MB 和570 MB。Rsync使用“quick check”策略，對比兩端文件大小與時間戳后進(jìn)行同步。hcsync 與使用“quick check”策略Rsync 的同步性能對比如表4 所示。由于htsync 缺少關(guān)于“quick check”策略的同步效率，因此該實(shí)驗(yàn)不與htsync對比。

表4 hcsync 與使用“quick check”策略Rsync 的同步性能對比Table 4 Synchronization performance comparison among hcsync and Rsync using‘quick check’policy

圖7 所示為hcsync 與使用“quick check”策 略Rsync 的同步時間對比。

圖7 hcsync 與使用“quick check”策略Rsync 的同步時間對比Fig.7 Synchronization time comparison of hcsync and Rsync using‘quick check’policy

從圖7 可以看出，Rsync 使用“quick check”策略的同步效率大幅增加，僅需要對大小和時間戳有改動的文件執(zhí)行Rsync 具體同步操作。但是這種模式也有其相應(yīng)的弊端，如果客戶端的文件時間戳和大小與服務(wù)器端完全一致，但內(nèi)容恰巧不一致時，在這種模式下Rsync 是無法發(fā)現(xiàn)文件庫存在更新。因此，Rsync 的“quick check”策略能夠減少同步時對比文件所消耗的資源，提升同步效率，但是卻無法完全保證同步的完整性。在兩端同步文件時，該策略下記錄文件大小與時間戳的文件列表容易被竊取與篡改，存在同步的安全性與穩(wěn)定性等問題。實(shí)驗(yàn)結(jié)果表明，相比使用“quick check”策略的Rsync，hcsync同步方法在效率上仍存在一定優(yōu)勢，平均同步加速比為6.5%。因此，基于有序哈希鏈的同步方法具有較優(yōu)的完整性、穩(wěn)定性且較高的效率。

6.2.3 常規(guī)策略下的實(shí)驗(yàn)結(jié)果

該實(shí)驗(yàn)場景與6.2.2 節(jié)相同，區(qū)別在于Rsync 使用常規(guī)策略檢查模式。hcsync 與使用常規(guī)策略Rsync 的同步性能對比如表5 和圖8 所示。傳統(tǒng)的Rsync 同步算法需要對每個文件數(shù)據(jù)進(jìn)行分塊、校驗(yàn)碼的計算及匹配。

表5 hcsync 與使用常規(guī)策略Rsync 的同步性能對比Table 5 Synchronization performance comparison of hcsync and Rsync using general policy

圖8 hcsync 與使用常規(guī)策略Rsync 的同步時間對比Fig.8 Synchronization time comparison of hcsync and Rsync using general policy

從表5 和圖8 可以看出，在常規(guī)策略下的Rsync同步過程可以確保數(shù)據(jù)的一致性，但是速度需減慢。這種情況下，Rsync 會進(jìn)行大量強(qiáng)弱校驗(yàn)碼的計算以及哈希表的匹配。隨著文件庫中文件數(shù)據(jù)的增加，耗費(fèi)的資源與時間也逐漸增加，此時hcsync 平均加速比為69.99%。

基于哈希樹的同步方法通過判斷根節(jié)點(diǎn)哈希值快速獲取文件庫是否發(fā)生變化，利用構(gòu)建的哈希樹結(jié)構(gòu)捕捉變化節(jié)點(diǎn)且跳過沒有變化的節(jié)點(diǎn)，從而加快同步速度。htsync 平均加速比為38.70%。

hcsync 與htsync 同步效率都要高于Rsync，它們都避免了傳統(tǒng)Rsync 中需要逐個對比文件數(shù)據(jù)的弊端，通過樹形結(jié)構(gòu)快速捕捉文件變化并進(jìn)行同步。但哈希鏈與哈希樹的區(qū)別在于：一個以時間順序迭代哈希函數(shù)并不斷延長鏈?zhǔn)浇Y(jié)構(gòu)，一個以目錄結(jié)構(gòu)創(chuàng)建的需要不斷更新的樹式結(jié)構(gòu)。但哈希樹的缺點(diǎn)是需要不斷地維持和更新一個樹形結(jié)構(gòu)，即使是一個普通的文件更新，也需從葉子節(jié)點(diǎn)溯源到根節(jié)點(diǎn)并更新節(jié)點(diǎn)與哈希值。當(dāng)文件庫更新時，hcsync只需在哈希鏈上增加節(jié)點(diǎn)，對比兩端哈希鏈節(jié)點(diǎn)h_id 即可獲取并執(zhí)行后續(xù)變化節(jié)點(diǎn)；htsync 則需要遍歷比對兩端哈希樹定位到變化節(jié)點(diǎn)，然后從變化節(jié)點(diǎn)溯源到根節(jié)點(diǎn)并對這些節(jié)點(diǎn)進(jìn)行更新。hcsync 在獲取變化節(jié)點(diǎn)的效率與更新鏈?zhǔn)浇Y(jié)構(gòu)的效率上相較于htsync 與Rsync 有較大的提升。因此，hcsync 的同步時間均低于htsync 和Rsync，整體同步效率排序：hcsync＞htsync＞Rsync。

7 結(jié)束語

本文設(shè)計一種基于有序哈希鏈的文件數(shù)據(jù)同步方法hcsync。通過哈希鏈?zhǔn)浇Y(jié)構(gòu)實(shí)時獲取并記錄文件庫數(shù)據(jù)的變化，以更加安全且穩(wěn)定地完成端到端的同步傳輸，在提升同步效率的同時保證了數(shù)據(jù)的一致性、可追溯性和防篡改性。實(shí)驗(yàn)結(jié)果表明，在設(shè)計的三種實(shí)驗(yàn)場景下，hcsync 的同步時間平均加速比分別為94.85%、6.5% 和69.99%，相比htsync 和Rsync，能有效減少同步過程中時間以及資源的消耗，提升了同步效率。下一步將對同步時間和空間上的開銷進(jìn)行探索和改進(jìn)［25］，實(shí)現(xiàn)更高效、更安全的同步技術(shù)。