rsync

rsync是如此神奇的同步软件，它用来在不同主机间同步文件系统。它不需要历史同步信息，也不需要依赖时间戳，但它却做真正的增量拷贝，也就是说假如你的文件在主机间只有少量差异，那么rsync会只传送差异，即使是二进制文件也可以增量拷贝。因此rsync给人的感觉就是神奇且速度奇快。

隐藏在rsync背后的就是一个rsync算法，记录在rsync原作者Andrew Tridgel的1999年的博士毕业论文 Efficient
Algorithms for Sorting and Synchronization
中，这篇论文共115页，我没有精力看完它，不过关于这个算法的介绍网上比比皆是。

在看介绍之前，我自己想了一下，大概猜测是用hash之类的算法，将文件分块得到的hash传递给对端主机以作比较，然后就可以做增量拷贝，但我很快就否定自己的想法了，比如一个文件的开头被加了一个字符，那么会导致所有的hash比较都不相等，而这种修改又是非常常见的。

迫不及待的看完rsync算法介绍之后，我明白了，原来我的想法和真正的rsync算法可以说已经接近了，但也可以说有天壤之别，问题就在于如何处理我难以解决的那个问题，rsync设置了两个hash算法，一个强一个弱，强hash就是和我想象的hash一样功能(rsync用的是MD4)，关键之处在于这个弱hash，它叫做rolling
hash，说的再直白一点就是类似于checksum的算法，可以在文件中以一个固定窗口来快速移动计算。这样以弱hash来做快速滑动比较，以寻找"可能"相同的块，强hash来校验之，问题解决。这样的算法可以对付几乎所有的文件类型的增量拷贝，但我想对某些特殊类型文件，比如压缩文件，可能不那么有效。

看似微不足道的设计成就了这个经典的同步软件 --- rsync.
( 微软的Server 2003中包含的分布式文件系统(DFS)中实现了一个"类似"的RDC协议。)