之前毕设有用到文件增量同步,于是乎就记录一下。
在A和B两个不同端之间有相似度很高的文件,同时这个文件又比较大。如果通过全量传输来更新,http传输量很大,非常不友好。那么可以通过某些手段,只上传修改的内容,其余内容复用旧文件。
对于A、B文件进行同步为例,首先对A文件进行分块,并且对每一块进行摘要计算(弱摘要&强摘要),并将其摘要数据传输给B端。B从第一字节开始,以相同大小的块滑动下去一一比较。
首先计算当前块的弱摘要,若弱摘要命中,则计算强摘要是否相同;若均相同,则该区域是相同块;两个相同块之间的区域,则是差异块。
(图片来源于网络)
那么以上的内容,其实对于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个同时上传比较好。
作者:江鱼儿呃呃呃
链接:https://juejin.im/post/6865562336158023688
本文源码:https://github.com/cjj281795819/study_rsync