1引言
文件同步(File Synchronization)技術是一種廣泛應用于集群計算、網絡管理和移動計算領域中的關鍵技術。文件同步的目標是如何將位于兩個邏輯或者物理位置的文件同步到一個統一的狀態。最簡單的文件同步技術是直接文件覆蓋。首先確定一個版本為更新的文件，然后將這個文件覆蓋到舊版本文件上即可。直接文件覆蓋是一種帶寬占用量最大的文件同步手段，在網絡通信流量敏感的環境中，這種技術顯然不可取。較為理想的同步算法是基于差量的更新，同步時傳輸兩個文件版本之間不同的文件數據，而重用相同的部分，從而達到節省同步帶寬的效果。
迄今為止，國內外研究者提出了不少用于文件同步的算法。1996年，Andrew Tridgell和Paul Mackerras在提出了rsync算法[1]。在1999年Andrew Tridgell對rsync經典算法進行了深入討論和研究[2]，比較了rsync中各種數據塊校驗碼算法的優劣，設計了多級簽名層次搜索方法以便加快數據塊校驗碼匹配及搜索過程，并且對rsync算法在實際中可能遇到的問題進行了研究。為了改進rsync算法的性能，Bernd Freisleben等設計實現了一種類似與rsync的多級簽名的分布式文件系統數據塊管理算法[3]，提出了一種在大規模網格或計算集群環境中性能較好的文件同步策略。Christos T. IKaramanolis等提出了一種分布式文件塊管理協議[4]，集中于計算集群節點組的分布式配置和管理。針對網格計算環境，Houda Lamehamedi等設計了一組分布式文件管理的服務和協議[5]，致力于提高數據可用性、降低帶寬消耗、增加容錯性以及提高可擴展性。這些算法為相應的應用環境做了優化，但是可擴展性不好，協議過于復雜，不適合移動計算等領域實現。
針對以上問題，本文提出一種改進的遠程文件同步算法ARsync，提出了多粒度文件分塊、多線程及流水線、緩存及版本樹等多種改進方案，并給出了其在Windows系統及Windows Mobile系統中的實現。
2 差量遠程文件同步算法
記擁有文件的新版本的計算機A為服務器，擁有文件舊版本的計算機B為客戶端。文件同步就是指計算機B上的文件更新到與計算機A上的文件相同的過程，一個有效的文件同步算法可以使得B上的文件b更新到與a相同，且代價為O(diff(a, b))。
需要進行同步的文件f被等分成大小為blocksize字節的n塊P1，P2，…，Pn，其中 。記S(Pi)為文件塊Pi強校驗碼，W(Pi)為文件塊Pi弱校驗碼。
為了避免對文件塊進行整塊的簡單復制和覆蓋操作，文件塊使用一種校驗碼系統來唯一確定。當兩個文件的校驗碼系統中各種校驗碼都相等時，認為這兩個文件塊相同；當兩個文件的校驗碼系統中存在不相同的校驗碼時，認為這兩個文件塊不同。實驗結果表明，在實際同步中，兩個不同的文件塊擁有相同的強弱校驗碼是小概率事件[2]。
W(Pi)的計算可以通過兩種方式完成：（1）通過使用初始函數hash計算得到。（2）通過W(Pi-1)，和diff(Pi-1, Pi)，使用滾動函數g計算得到。當blocksize較大時，通過滾動函數g計算W(Pi)的速度遠遠高于使用初始函數hash直接計算W(Pi)的速度，更遠遠高于S(Pi)的計算速度。
同步主要過程和校驗碼的計算與選擇本文不再贅述，見參考文獻[1][2]。
3算法的優化
3．1多粒度文件分塊
rsync同步算法在同步過程中采用了固定blocksize的方式，使得rsync算法只能局限在小型的文本文件中。rsync同步算法需要對每一個文件塊計算兩個校驗碼，帶寬占用與文件分塊的個數成正比。因此對大文件進行同步時，因為文件塊增多，rsync產生的校驗碼數據也更大，如果對于一種很少變動的大文件來說，rsync的通信代價很高。
為了實現算法執行效率和帶寬占用的平衡，ARsync算法采用了多粒度文件塊大小，blocksize要根據文件的具體情況來選擇，經過調優，使得算法執行效率最大化。blocksize的選取主要考慮兩個因素：文件的大小和文件的類型。對于大型文件來說，應當適當采取較小的blocksize以便減小帶寬占用。但是blocksize不能小于校驗碼的總長度，否則算法不會節省，反而會增加對帶寬的占用。
此外，需要進行同步的文件本身可能包含一些特點，使得blocksize也不能任意取值，而應當根據具體文件的存儲和更新特點進行合理的選擇。例如對于數據庫管理系統，數據存儲文件中的每條記錄的長度都是確定的，建立數據表時根據每個字段的數據類型，確定一定的存儲空間，每增加一條記錄都會增加固定長度的數據段，而更新或者刪除某條記錄時，也是基于固定大小的文件塊進行更新或者刪除。對這類文件進行同步時，應當取blocksize為記錄長度的整數倍，此時的同步算法會最大限度地保存相同的文件塊，有較好的性能優勢。而在對圖像進行同步時，根據圖像文件的類型，以及記錄在圖像文件頭部中的信息，可以獲取到本幅圖像使用了幾個字節來表示一個像素點。此時取blocksize為像素單元大小的整數倍，會取得較好的同步效率。
具體的實現中，多粒度文件分塊采取手動和自動兩種方式進行。對于一些已知結構的數據文件，按照其文件后綴區分文件，在配置文件中針對這種類型的文件設置合適的分塊大小。對于其他文件類型，根據其文件大小選擇較合適的分塊大小，較大的文件要選擇較大的分塊大小，從而使得通信成本控制在可接受的范圍內。自動的文件分塊還可以對具體的文件數據進行一定分析，嘗試尋找其分段重復的結構特征，提升文件塊重用率。
3．2多線程及流水線技術
經典的rsync算法提出的時間較早，使用經典rsync算法實現的同步軟件已經不適合現代計算機的實際情況�，F代計算機普遍使用了超線程（Hyper-Threading，HT）技術以及多核（Multi-Core）處理機架構。使用多線程技術實際上就是開啟多個工作線程進行文件同步操作，從而更好地利用處理機的計算資源。
對文件同步應用來說，流水線技術的工作階段主要分為：讀取文件（磁盤I/O操作）、計算校驗碼（CPU計算）、發送數據（網卡I/O操作）。
圖1 多級流水線多線程技術
在實際實現中采取了多級流水線多線程技術。多級流水線多線程技術實際上可以看做是對流水線技術的多線程擴展，整體工作流程與采用流水線技術相同，但是在每一個工作階段中，針對各種系統資源的特點，加入了多線程技術。
圖1所示為一臺8核心服務器上同步算法運行時的流水線狀態，任務A、任務B、任務C依次執行。同步計算任務分為三個階段，每個任務在每個階段又由多個線程進行執行。
多級流水線多線程技術充分利用了各種系統資源，平滑不同類型的系統資源的差異性，達到了較高的同步吞吐率。
3．3更新數據打包
圖2 更新包緩存及文件版本樹
經過對各種網絡環境的分析后發現，影響遠程文件同步網絡傳輸速度因素由兩部分組成：連接的建立時間和數據傳輸時間。在GPRS網絡等慢速網絡中，連接建立的時間往往是不能忽略的。實際測試中我們發現，一旦連接成功建立，數據的傳輸往往能夠穩定地以額定速度完成，連接建立的時間則不可預料，一般與網絡環境和信號強度有關。因此當文件的個數逐步增多后，對每一個文件都建立一對連接進行同步，其整體性能很低。
在系統實現中采用了更新數據打包的方法解決這個問題。通過將一定數量或者一定大小的文件整體計算校驗碼之后，將每個文件的更新文件校驗碼信息結構體合并在一個TCP數據包中，并使用gzip壓縮后傳輸，獲得了相當可觀的性能提升。
3．4緩存技術及版本樹
遠程文件同步算法的一個典型應用是文件的發布。中心服務器保存最新版本的文件，各個客戶端連接到服務器進行文件版本更新操作。對于這種操作，中心服務器需要在每次收到文件更新請求后都要對新版本文件進行校驗碼計算，嚴重影響更新任務吞吐率。
實際上，客戶端包含的舊版本文件往往是分成有限種版本，服務器只需要針對每一種版本的舊文件計算一次文件更新指令序列并將文件更新指令序列緩存到服務器上，當另一臺包含同樣版本的舊文件客戶端發起文件更新請求時，服務器不需要計算，直接返回緩存好的結果即可。采用緩存技術，實際上在服務器上形成了文件的版本樹，如圖2所示。
4實驗與性能分析
實驗機器CPU為Intel Core 2 Duo E6550 2.33GHz，內存為DDR2 800MHz 2.0GB，磁盤為SATA 160G，操作系統為Windows Server 2003，關閉了大部分系統服務和運行中的程序。實驗采用的測試數據為Linux源代碼，作為舊版本的是Linux 1.1.13，包含598個文件，4997258字節。作為新版本的是Linux 1.1.23，共603個文件，5286496字節。
表1 回環方式完成同步所需時間統計數據（單位：毫秒）
算法 連接建立 文件掃描 校驗碼計算 數據傳輸 更新合并 總計
rsync 10 530 780 80 23601 24991
ARsync 0 536 674 63 20408 21681
表2 互聯網方式完成同步所需時間統計數據（單位：毫秒）
算法 連接建立 文件掃描 校驗碼計算 數據傳輸 更新合并 總計
rsync 1130 610 775 321 23723 26559
ARsync 6 599 681 212 20415 21913
由表1和表2比較發現，ARsync采用了多線程和流水線技術，便于程序利用多核處理機架構優勢，在進行校驗碼計算和更新合并中比rsync都要快。
rsync算法在對每一個文件進行更新時，都會建立一對TCP連接。在真實的網絡環境中，連接建立開銷是可觀的。假定單個連接建立時間是恒定的，則總連接建立時間與文件數量呈線性關系，當文件數量增多時，連接建立階段便成了整個同步過程的瓶頸。在改進算法中，采用更新數據打包技術，在校驗碼計算階段付出了一些代價，但在連接建立階段只需要建立一對TCP連接，節省了整體同步時間。
圖3 完整文件夾更新時間比較
隨著同步的文件的逐步增多，rsync消耗的時間是隨同步任務規模的增大而線性增長的，而ARsync的同步速度相比rsync可以提升15%左右，命中緩存情況下的同步時間則更小。
5結語
本文提出并實現了一種基于rsync文件同步算法改進，引入了多粒度文件分塊技術，使用了現代計算機技術中的緩存機制、流水線及多線程技術，達到了文件同步速度快，計算量適中，帶寬占用小，可擴展性好的效果。
參考文獻 (References)
[1] Andrew Tridgell, Paul Mackerras. The rsync algorithm[R]. Canberra: The Australian National University, 1996: 1-6
[2] Andrew Tridgell. Efficient Algorithms for Sorting and Synchronization[D] Canberra: The Australian National University, 1999: 49-95
[3] Bernd Freisleben, Hans-Henning, Koch Oliver Theel. Replication Management in Large Networks[A]. Local Computer Networks[C], 1991. Proceedings., 16th Conference on 14-17 Oct. 1991: 629-637
[4] Christos T. IKaramanolis, Jeff N. Magee. A Replication Protocol to Support Dynamically Configurable Groups of Servers[A]. Configurable Distributed Systems[C], 1996. Proceedings., Third International Conference on 1996: 161-168
[5] Houda Lamehamedi, Boleslaw Szymanski, Zujun Shentu, Ewa Deelman. Data Replication Strategies in Grid Environments[A]. Algorithms and Architectures for Parallel Processing[C], 2002. Proceedings. Fifth International Conference on 23-25 Oct. 2002: 378-383
作者簡介: 李征(1985-),男,同濟大學計算機軟件與應用專業碩士研究生,主要研究領域分布式系統,并行計算,Web標準化.張棟良(1977-),男,博士研究生,主要研究領域為并行計算,交通仿真.
