周 平，劉曉潔

（四川大學 計算機學院，四川 成都610065）

0 引 言

文件同步是指對客戶端和服務器上同一文件的不同版本進行同步，使這兩個不同主機上文件的版本一致。文件同步廣泛用于文件的備份與恢復、web網站鏡像等場景中。目前，較常用的文件同步算法有RDC（remote differential compression）［1］和Rsync［2，3］。文件同步主要包括文件分塊、hash值比較以及網絡傳輸3個步驟。其中，文件分塊是其中最重要的一個步驟。文件分塊算法是指按照一定的策略將文件分割成較小的數據塊，以用于對比文件之間的細微差異。通常文件的版本之間的差異較小，通過分塊能夠更加準確地檢測兩個版本－中的差異數據塊。

文件分塊算法主要分為固定長度分塊（fixed－sized partitioning，F(xiàn)SP）算 法［4］和 基 于 內 容 的 分 塊（contented－defined chunking，CDC）算法［5］。FSP算法的特點是易于實現(xiàn)，且分塊速度較快，但是對于插入和刪除的位置較敏感，不能根據文件自身內容的變化進行調整與優(yōu)化。而CDC 分塊算法能將文件按內容分成大小不等的塊，能夠較好地檢測到差異。目前最常用的CDC 分塊 算法 有BSW［6，7］（basic sliding window）分塊算法和Winnowing［8］分塊算法。BSW 分塊算法采用的分塊規(guī)則是預先設定兩個正整數D 和r（r＜D），若滑動窗口W 的Rabin［9］指紋值F（ ）W modD＝r，則將窗口W 的右邊界作為分塊的邊界點。由于分塊受窗口寬度及兩個設定值的影響較大，導致分塊長度變化范圍較大，因此分塊效率不穩(wěn)定。Winnowing算法在一個固定大小的窗口內，計算滑動塊的Rabin指紋值，取極值點作為分塊的邊界點。此算法能夠實現(xiàn)按文件內容進行分塊，同時又能將分塊大小限制在一定的范圍內，克服了BSW 算法分塊長度變化范圍較大的問題，但Winnowing算法存在Rabin值的重復計算，因此分塊算法比較耗時。

本文提出了基于兩級分塊的文件同步方法（DFRSYNC）。該方法首先使用循環(huán)隊列對Winnowing分塊算法進行改進，以提高分塊效率；基于該改進的Winnowing分塊算法，本文采用兩級分塊策略，首先設定較大的窗口值和滑塊值，分別對客戶端和服務器上的文件進行快速分塊，初步定位差異塊，然后設定較小的窗口值和滑塊值進行第二次分塊，從而準確定位差異塊。

1 DF－RSYNC方法

DF－RSYNC 方法在傳統(tǒng)Winnowing 分塊算法的基礎上，采用循環(huán)隊列存儲hash值以減少部分hash值的重復計算，同時為了更細粒度地檢測到差異數據，采用了兩級分塊策略，因此需要兩輪往返來傳輸兩次分塊的hash值及最終的差異數據。

1.1 Winnowing分塊算法及其改進

1.1.1 傳統(tǒng)Winnowing數據分塊算法

傳統(tǒng)的Winnowing算法原理如圖1所示，其中W 代表固定窗口。B1，B2，…，BN－1，BN代表窗口W 內從左邊界到右邊界滑動塊。設Lw為固定窗口大小，LB為滑動塊大小，且Lw＞LB。

圖1 Winnowing數據分塊算法

（1）設P為窗口當前的左邊界點，滑動塊以窗口的左邊界為起始點。

（2）若滑塊的右邊界沒有到達窗口的右邊界點，則每次向前移動一個字節(jié)，得到滑動塊B1，B2，…，BN－1，BN，且塊數N＝Lw－LB。

（3）計算各塊B1，B2，…，BN－1，BN的Rabin 指紋值，并保存到hash表H 中。若有Bk（k∈ ［1，N］） 滿足H（Bk）＝min （H （B1），H （B2），…，H （BN）），則劃分長度L＝k的塊，令P＝P＋k＋1為窗口的下一個左邊界點，返回（1）。

由上述算法描述可知，Winnowing雖能夠實現(xiàn)對文件按內容分塊，并將分塊長度L限制在LW－LB，但在窗口的移動過程中，部分塊的Rabin值存在重復計算的問題。如（3），窗體在分塊的前后只滑動了塊長L＝k個字節(jié)的距離，當K 值比較靠近窗口的起始點P 時，就有一部分滑塊的Rabin值要重復計算，重復計算的滑動塊數是LB－L，這極大地增加了分塊的時間。

1.1.2 改進的Winnowing分塊算法

為提高分塊效率，避免Rabin值的重復計算，本文對上述算法做了改進。本文使用了一個容量為N＝Lw－LB＋1的循環(huán)隊列Q，初始時，隊列Q 的頭指針front與尾指針rear都為0，使滑塊的起始位置P初值也為0。

（1）滑塊以P為起點，依次向前滑動一個字節(jié)，并計算每個塊的Rabin 指紋值，依次插入到隊列Q 的隊尾，rear＝rear＋1，直到隊列Q 滿，即（re ar＋1 ）modN＝front。

（2）比較隊列Q 中的各滑塊的Rabin指紋值，若有Qk（k∈［front，rear］）滿足Qk＝min（Qfront，Qfront＋1，…，Qrear），則劃分長度為 L＝ （k－front＋1＋N ）modN新塊，且P＝P＋L。

（3）刪除隊列中從front 到K 的元素，即front＝（k－front＋1 ）modN。轉到（1）。

算法原理如圖2所示。

圖2 改進的Winnowing數據分塊算法

改進的Winnowing分塊算法實現(xiàn)如下：

1.2 兩級分塊方法

為了實現(xiàn)高效準確的差異檢測，本文采用了文獻［10］提出的兩級分塊的文件同步思想，其采用的分塊方法是首先使用CDC算法粗粒度地定位差異塊，再對不匹配的塊使用Rsync定長滑動塊技術在細粒度上查找差異塊。本文中分塊算法采用的是改進的Winnowing分塊方法。算法流程如圖3所示。

圖3 兩級分塊

首先將固定窗口和滑動塊大小設置為較大值，使用改進的Winnowing分塊算法，分別對存在于客戶端和服務器端的相同文件的不同版本進行分塊，其中，客戶端為新版本，服務器端為舊版本，分別將新舊版本文件分成C1，C2…，CM塊和C′1，C′2，…，C′N塊。計算每塊的hash值，再將兩個版本文件分塊的hash值進行比較，分別找出兩組分塊hash值中不相同的塊，如新版本進行比較后的差異塊是Ck…CH，舊版本中差異塊是C′k，…，C′L。將固定窗口和滑動塊的大小設置為較小值，分別對這兩組差異塊再使用改進的Winnowing分塊算法進行再分塊，分成Ck1，…，CLM塊和C′k1…C′LN塊。再將這兩組再分塊的hash值進行比較，找出有差異的小塊Ckd…即為最終的差異數據。

1.3 兩輪往返方法

由于本文采用了兩級分塊策略，因此需要兩輪往返來傳輸兩次分塊的hash值及最終的差異數據。兩輪往返協(xié)議如圖4所示。首先服務器發(fā)送分塊請求到客戶端，客戶端將第一次分塊后的Hash值返回給服務器，服務器將對應文件的舊版本進行分塊，并將這兩個版本的分塊Hash值進行對比，并將對比結果以Bitmap存儲后發(fā)送到客戶端，客戶端根據收到的Bitmap，對差異塊重新進行分塊，并將二次分塊的Hash值傳送到服務器。服務器將其二次分塊Hash值與收到的Hash值進行對比后，將二次分塊的Bitmap發(fā)送到客戶端，客戶端根據該Bitmap計算出差異數據后，將差異數據發(fā)送到服務器。服務器根據兩輪收到的bitmap值和差異數據對文件進行重構。

圖4 服務器與客戶端的兩輪往返

在兩輪往返過程中，文件塊信息存放在各自的主機上。每個信息塊是一個數據結構，第一次分塊的塊信息Block－Info1的格式為＜BlockNumber1，BlcokBegin1，BlockLength1＞，其中，BlockNumber1為第一次分塊塊號，BlockBegin1為分塊起始位置，BlockLength1 為第一次分塊的塊長，第二次分塊的塊信息BlockInfo2 的格式為＜BlockNumber1，BlockNumber2，BlockBegin2，BlockLength2 ＞， 其 中，BlockNumber1為第一次分塊的塊號，BlockNumber2 為對BlcokNumber1塊的第二次分塊的塊號，BlockBegin2 為第二次分塊相對于第一次分塊的起始位置，BlockLength2 為第二次分塊的塊長。

2 實驗分析

本實驗首先對傳統(tǒng)Winnowing分塊算法和本文提出改進的Winnowing分塊算法在分塊的時間上進行了對比。然后基于改進的Winnowing 分塊算法，對比了一級分塊與DF－RSYNC方法的兩級分塊方法在差異數據檢測的粒度以及同步過程中所產生網絡傳輸量。實驗使用SHA1計算分塊的hash值，采用socket進行網絡數據傳輸，并用gzip壓縮算法對待傳輸的數據進行壓縮。

實驗環(huán)境如下：服務器與客戶端為兩臺配置相同的主機。具體配置為CPU：雙核Intel（R）Pentium （R）Dual CPU 2.20GHz，內存：2GB，硬盤：ST3250310AS 250GB，操作系統(tǒng)：Windows32，網絡環(huán)境是百兆局域網。文中算法均在Visual Studio 2010下使用C＋＋編程實現(xiàn)。

2.1 分塊時間對比

本實驗就1.1.1與1.1.2 分別提到的兩種分塊算法對不同大小文件的分塊時間進行對比，如圖5所示，分塊時間以毫秒為單位?？梢钥闯觯捎诒苊饬瞬糠諶abin指紋值的重復計算，改進的分塊算法可顯著地減少了分塊時間。并且隨著文件的增大，改進的分塊算法的分塊時間增長幅度較小。

圖5 分塊時間對比

2.2 差異數據粒度對比

本實驗對不同大小的文件采用改進的Winnowing分塊算法進行一級分塊和二級分塊后，分別統(tǒng)計分塊后獲得的差異數據的大小，并與實際的差異數據大小進行對比，結果如圖6所示。實驗2.2和2.3采用的一級分塊的窗口大小為2048B，滑動塊大小為2048B，二級分塊的窗口大小是512B，滑動塊大小為512B?？梢钥闯觯壏謮K較一級分塊能夠更細粒度地檢測到差異數據。

2.3 網絡流量對比

圖6 分塊粒度對比

該組實驗針對使用改進分塊算法的文件單輪往返同步方法與DF－RSYNC方法在網絡上的數據傳輸量進行對比。表1記錄了一輪往返和兩輪往返同步中需要傳輸的差異數據量、額外數據量和總的數據量，表中除文件大小以KB為單位外，其余數據都以Byte為單位。圖7每兩個柱形代表在相同的文件大小下，兩種同步方法的流量消耗。左邊的柱形代表單輪往返的網絡流量消耗，右邊的柱形代表DF－RSYNC方法的網絡流量消耗。每個柱的下部分代表傳輸中的差異數據量，而上部分代表額外數據的傳輸量。該組實驗結果表明兩輪往返同步較一輪往返同步傳輸的差異數據量要小，但增加了第二次分塊的hash值、第二次分塊的bitmap值等額外數據的傳輸。總體上來說，兩輪往返同步方法DF－RSYNC 能在一定程度上地減少網絡流量的消耗。

表1 一輪往返和兩輪往返網絡流量對比

實驗結果表明，采用了循環(huán)隊列的Winnowing分塊算法可顯著減少分塊的時間，大大地提高了分塊效率。兩級分塊相對于一級分塊能夠更精確地定位差異數據，減少差異數據的傳輸。雖然兩級分塊的兩輪往返相比于一級分塊的一輪往返來說，增加了額外的數據量，但由于兩級分塊檢測到的差異數據量較一級分塊小，因此兩輪往返中差異數據的傳輸量較一輪往返小?？傮w上來說，兩級分塊，兩輪往返的網絡流量較一級分塊一輪往返在一定程度上減少。

3 結束語

圖7 網絡流量對比

本文針對Winnowing算法的分塊效率不高，單級分塊的粒度較粗，以及網絡中差異數據傳輸量較大等問題，提出了基于改進的Winnowing分塊算法對文件兩級分塊，兩輪往返同步的方法DF－RSYNC。實驗結果表明，采用的改進的Winnowing分塊算法極大地減少了分塊時間，其兩級分塊策略能更細粒度地定位差異數據，減少了網絡上差異數據的傳輸量。但由于本文的方法DF－RSYNC 增加了第二次分塊的hash值等額外信息的傳輸，因此怎樣在細粒度的檢測到差異的同時，盡可能地減少額外信息的傳輸量是今后我們要研究的工作。

［1］Teodosiu D，Bjorner N，Gurevich Y，et al.Optimizing file replication over limited bandwidth networks using remote differential compression ［R］.Microsoft Research，2006.

［2］Tangwongsan K，Pucha H，Andersen D G，et al.Efficient similarity estimation for systems exploiting data redundancy［C］／／INFOCOM，Proceedings IEEE，2010：1－9.

［3］TANG Xiaodi，MA Xiaoxu.Design and implementation of remote file synchronization system based on difference［J］.Computer Engineering and Design，2010，31 （20）：4389－4392（in Chinese）. ［湯曉迪，馬曉旭.遠程文件差異同步系統(tǒng)的設計與實現(xiàn) ［J］.計算機工程與設計，2010，31 （20）：4389－4392.］

［4］Gharaibeh A，Constantinescu C，Lu M，et al.CloudDT：Efficient tape resource management using deduplication in cloud backup and archival services ［C］／／8th International Conference on Network and Service Management.IEEE，2012：169－173.

［5］Bjrner N，Blass A，Gurevich Y.Content－dependent chunking for differential compression，the local maximum approach ［J］.Journal of Computer and System Sciences，2010，76 （3）：154－203.

［6］AO Li，SHU Jiwu.Data reduplication techniques ［J］.Journal of Software，2010，21 （5）：916－929 （in Chinese）. ［敖莉，舒繼武.重復數據刪除技術 ［J］.軟件學報，2010，21（5）：916－929.］

［7］Chang Bingchun.A running time improvement for two thresholds two divisors algorithms［D］.San Jose：San Jose State University，2009.

［8］Murugesan M，Jiang W，Clifton C，et al.Efficient privacypreserving similar document detection ［J］.The VLDB Journal—The International Journal on Very Large Data Bases，2010，19 （4）：457－475.

［9］Jarrous A，Pinkas B.Secure computation of functionalities based on hamming distance and its application to computing document similarity ［J］.International Journal of Applied Cryptography，2013，3 （1）：21－46.

［10］XU Dan，SHENG Yonghong.High effective two－round remote file fast synchronization algorithm ［J］.Journal of Frontiers of Computer Science and Technology，2011，5 （1）：38－49 （in Chinese）.［徐旦，生擁宏.高效的兩輪遠程文件快速同步算法 ［J］.計算機科學與探索，2011，5 （1）：38－49.］