前言

之前毕设有用到文件增量同步，于是乎就记录一下。

场景

在A和B两个不同端之间有相似度很高的文件，同时这个文件又比较大。如果通过全量传输来更新，http传输量很大，非常不友好。那么可以通过某些手段，只上传修改的内容，其余内容复用旧文件。

重复块检测技术固定分块检测技术：固定分块检测的话，如果某一区域发生变化，之后分块将均无法检测命中块，命中率低且局限性大。可变块检测技术：可变块很好解决上面的问题，例如CDC算法。不过好像没有通用的解决方案，我是没找到。滑动块检测技术：采用固定块，滑动检测是否命中，命中率高，但是相似度越低的文件，越耗时，例如：rsync增量传输算法，也是本文的讲解目标rsync增量传输算法

对于A、B文件进行同步为例，首先对A文件进行分块，并且对每一块进行摘要计算（弱摘要&强摘要），并将其摘要数据传输给B端。B从第一字节开始，以相同大小的块滑动下去一一比较。

首先计算当前块的弱摘要，若弱摘要命中，则计算强摘要是否相同；若均相同，则该区域是相同块；两个相同块之间的区域，则是差异块。

弱摘要采用Adler-32，生成速度快，但是可能出现重复。强摘要采用md5，生成慢，但是有保障。

（图片来源于网络）

那么以上的内容，其实对于A、B两端，均有计算量。其实是不友好的，在单A对多B或者单B对多A的场景，则压力过大。

同时滑动块的大小也非常影响结果：若滑动块过小，可以提高命中率，但是计算量增大；若滑动块过大，计算量减少，但是可能降低命中率。

优化

对于实际的应用场景，可以大致分成两种情况：

客户端有新文件，要增量同步给服务端；服务端有新文件，要增量同步给其他端；

无论是第一种情况还是第二种情况，我们都希望将计算量放到客户端，而服务端仅仅做合并操作或者传输数据操作。

那么我们可以在其他端第一次传输给服务端新文件的时候，将摘要在本地计算得到，然后一起发给服务端。在之后更新的时候，同时也把新的摘要发给服务端更新。服务端就可以缓存摘要内容，省去计算过程。

同时，对于某些情况，可以缓存新旧文件的差异内容，通过版本号的差异，查询服务端是否有保存差异内容文件，若保存了，则可以直接传输更新。

那么对于第一种情况：客户端首先向服务端发起获取摘要请求，服务端返回摘要后，客户端本地滑动块检测摘要，然后，将检测结果同差异内容文件发送给服务端，服务端做合并操作。

对于第二种情况：客户端还是向服务端发起获取摘要请求，服务端返回摘要后，客户端滑动块检测摘要。相同块内容，则从本地文件获取，差异块内容文件则通过http range请求。其实也可以直接请求差异文件，若服务端有保存的话。

同时需要设置阙值，在块滑动检测时，若命中率过低，可以省去检测过程，直接采用全量上传文件同步操作。因为，相似度低的文件，滑动检测比较花时间，同时结果也不尽人意。

实际使用

我也写了个demo在github上，在文章末尾已放链接。

以浏览器新文件增量同步给服务端为例。

我们可以建立一个webwork，然后将计算摘要的过程和滑块检测的过程，都放到webwork上。

由于摘要结果需要三个数据，弱摘要，强摘要以及对应序号。一开始想的是数组，对象包括两种摘要，下标作为序号。但是，这样查找效率太低了，每次查找都需要遍历一遍，效率低下。

后来换了个思路，采用以下数据结构：

弱摘要作为key值，强摘要作为value值，对应的原文件内容序号则以@index放到value的末尾。同时，因为弱摘要是可能出现重复的，所以，在计算时，检测弱摘要是否存在，若存在则在末尾加@1，若还存在则，继续@2等等，直到不存在，可以放入对象中。

目的就是为了降低查找复杂度，从O(n)变成O(1)。

同时，对于相似度高的文件，滑动块检测，必然出现连续的相同块。 若连续区域，在原文件上是连续的序号，则可以将其合并，减小传输数据大小：

null是差异块文件，下标作为文件的标识之一。

num是原文件分块结果的第num块区域。

数组是原文件分块结果的第start至end区域。

然后，对于差异块文件，就进行正常上传操作，目前还是以http1.1为主流，还是采用4~5个4~5个同时上传比较好。

作者：江鱼儿呃呃呃

链接：

本文源码: