rsync原理

rsync的核心原理可以概括为一种在不直接传输整个文件的前提下高效找出文件差异并进行同步的算法。它的精髓在于它不需要两个文件在同一台机器上就能完成“差异化”操作因此非常适合远程文件同步。这个过程主要由下面三个步骤构成巧妙地结合了“校验和”与“滑动窗口”技术 第一步目标端生成文件“指纹”同步目标端假设为B拥有旧文件不会直接发送整个文件而是先为它制作一份精简的“指纹”清单也就是sign文件并发送给源端A。制作过程如下分块将旧文件按固定大小例如512字节或2KB最后一块可能较小切分成多个数据块。生成“指纹”对每一个数据块都计算两种校验和弱校验和 (Rolling Checksum)例如32位的adler-32算法计算速度非常快主要用于快速筛选。强校验和 (Strong Checksum)例如128位的MD5算法几乎可以保证100%准确用于最终确认数据块相同。发送清单B机器将这个包含“数据块编号、弱校验和、强校验和”的清单发送给A机器。 第二步源端进行差异检测源端A拥有新文件收到这个“指纹”清单后会在本地的新文件中以滑动窗口的方式寻找与清单里指纹匹配的数据块。这个过程就像用一把固定长度的“尺子”窗口从文件开头滑到结尾每到一个新位置就测量一下初始窗口从新文件的第1个字节开始取一块同样大小例如512字节的数据。计算并查找计算这个窗口数据的弱校验和然后去B发来的清单中快速查找通常用哈希表实现O(1)的查找速度。如果找不到说明这块数据大概率有变化。滑动窗口如果找不到匹配窗口就向后滑动1个字节然后对新位置的数据块再次计算和查找。双重确认如果弱校验和找到了匹配为了防止碰撞还会进一步计算并比对强校验和MD5。只有两个校验和都匹配才最终认定这个数据块在两端是相同的。通过这个高效的滚动查找过程源端A就能定位出所有与目标端相同的数据块。 第三步构建并传输差异文件最后A端会根据检测结果生成一个delta文件传给B端。这个delta文件包含了重建新文件所需的全部指令匹配到的块只需记录下这个块在B端旧文件中的编号例如“参考第5号块”这部分数据无需传输。未匹配到的块对于无法匹配上的“差异”数据会将其原始字节内容直接打包进delta文件。目标端B收到delta文件后根据指令从自己的旧文件中提取匹配的数据块并插入收到的新的数据块最终就能完整地重建出和源端A一模一样的新文件。 总结一下rsync的原理可以类比为**“用拼图来同步”**目标端先把自己手里的拼图块旧文件编上号、拍下照片生成指纹发给源端。源端拿到照片后在自己的新拼图里寻找一模一样的块找到的就不用再寄了只需要把找不到的新块和一份“用几号旧块拼在哪里”的说明书delta文件寄回去。目标端按照说明书就能用旧块和新寄来的块完整地拼出新图案新文件。Adler-32如何通过0-1024计算1-1025这个问题问得很到位触及了rsync高效运作的核心秘密。简单来说Adler-32之所以能从0~1024的校验值快速计算出1~1025的校验值靠的不是重新计算而是一个极其简单的数学更新公式。它让校验和的计算复杂度从O(n)和窗口大小成正比骤降为O(1)常数时间。 Adler-32算法回顾Adler-32的校验和由两部分组成都是32位整数A窗口中所有字节的累加和模65521。B窗口中所有字节的加权累加和每个字节乘以其从窗口起始位置算起的权重再累加最后模65521。最终的校验和就是A (B 16)。 如何滑动从0~1024到1~1025假设窗口大小为1024字节我们用x0表示第0个字节x1024表示第1024个字节。旧窗口0~1024的校验和是A_old x0 x1 ... x1023B_old 1*x0 2*x1 ... 1024*x1023新窗口1~1025的校验和是A_new x1 x2 ... x1024B_new 1*x1 2*x2 ... 1024*x1024关键步骤来了我们来看如何由旧值得到新值更新 A 值新窗口比旧窗口移出了第一个字节x0移入了新字节x1024。公式是A_new A_old - x0 x1024更新 B 值移出x0后窗口内所有剩余字节的权重都减1。公式是B_new B_old - (x0 x1 ... x1023) 1024*x1024看括号里的x0 x1 ... x1023不正是A_old吗所以公式可以化简为B_new B_old - A_old 1024 * x1024⚡️ 为什么这很重要如果没有这个特性每次窗口滑动1个字节都需要重新计算1024个字节的校验和那rsync的“滚动”扫描将慢得无法接受。而有了这个O(1)的更新公式rsync就能以极快的速度一边滑动窗口一边实时更新校验和然后去哈希表中查找匹配。这使得它在处理大文件时依然能有惊人的效率。 一个重要的修正最后想悄悄修正一个小细节这其实并不影响你刚才问的“滑动”原理但能让我们对rsync的理解更精确在rsync的实际实现中用于快速查找的“弱校验和”并非标准的Adler-32而是一个经过简化的、专门为滚动计算优化的变体。不过它的核心数学思想——利用滑动窗口实现校验和的增量更新——与Adler-32完全一致你刚才理解的滑动更新逻辑依然是完全正确的。希望这个“数学小魔术”能帮你更清晰地看到rsync高效背后的原理。如果对其中某个计算步骤还想深入聊聊我们可以继续探讨rsync同步一个目录时是如何同步的– 一个文件一个文件同步的。所以文件很多时就会比较慢。