您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

文件增量同步之rsync算法

时间:2020-08-28 13:42:34  来源:  作者:

前言

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

场景

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

重复块检测技术

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

rsync增量传输算法

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

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

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

 

文件增量同步之rsync算法

 

(图片来源于网络)

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

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

优化

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

  • 客户端有新文件,要增量同步给服务端;
  • 服务端有新文件,要增量同步给其他端;

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

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

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

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

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

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

实际使用

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

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

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

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

后来换了个思路,采用以下数据结构:

文件增量同步之rsync算法

 

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

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

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

文件增量同步之rsync算法

 

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

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

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

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


作者:江鱼儿呃呃呃
链接:https://juejin.im/post/6865562336158023688

本文源码:https://github.com/cjj281795819/study_rsync



Tags:rsync算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言之前毕设有用到文件增量同步,于是乎就记录一下。场景在A和B两个不同端之间有相似度很高的文件,同时这个文件又比较大。如果通过全量传输来更新,http传输量很大,非常不友好。...【详细内容】
2020-08-28  Tags: rsync算法  点击:(155)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条