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算法实现的同步软件已经不适合现代计算机的实际情况。现代计算机普遍使用了超线程（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-),男,博士研究生,主要研究领域为并行计算,交通仿真.