Chinaunix首页 | 论坛 | 博客
  • 博客访问: 371374
  • 博文数量: 273
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1430
  • 用 户 组: 普通用户
  • 注册时间: 2018-02-02 15:57
文章分类

全部博文(273)

文章存档

2018年(273)

我的朋友

分类: 高性能计算

2018-08-01 16:35:08

问题:

如何增量同步文件,例如一个文本文件有10M,分别存放在A,B两个地方,现在两个文件是完全一样的,但是我马上要在A上对这个文件进行修改,B如何实现自动和A上的文件保持一致,并且网络的传输量最少。

 

应用场景:

这样的使用场景太多,这里随便列举几个

1.A机器为线上运营的机器,现在需要一台备份的机器B,当A发生宕机的时候,或者硬盘损坏等各种认为非人为原因导致数据不可用时,可以很快从B恢复

2.SVN这样的应用场景,不需要每次修改都向服务器发送并替换掉一个文件,而是只发送被修改的部分

3.手机客户端对一个文本修改,如果那个文本有2M,难道我每次更新都需要上传整个文件吗?每次2M,傻子才用! 

等等.... 

 

解决方案:

.分而治之

计算机最重要的基本算法思路就是分而治之,在我们眼里,一个文件不是一个文件,而是一堆存储块,每个存储块可能20Byte大小,至于这个值具体多大,你可以自己设定,这里的20Byte仅提供参考。通过这样的方法,一个文件被分成了很多个块,我们只需要比对块是否相同就可以得出哪个部分做了相应修改。

 

.快速校验

刚上面提到如何比对文件,当然这里肯定不会把文件的每个块上传去比对,那样做就没有意义了。快速比对这不禁让我想起了哈希规则,哈希表可以通过O(1)的复杂度查找某个key,为什么?  因为它通过计算hash值来初步验证key,一个key的hash值是唯一的。但是仅仅验证hash值是不可靠的,因为hash值有可能会冲突,所以在验证完hash值后,我们在进行key的比较来确定要找的值...

通过哈希的思路,我们可以使用类似的方法来实现文件增量同步,把每一个存储块,通过MD5计算其值,然后传递MD5值到服务器,让服务器比对MD5来确定有没有被修改,如若MD5值不相等,则判定这个文件块有被修改过

为什么是MD5?

1)能够将任意长度的字符串转换为128位定长字符串(MD5 16) 

2)MD5能够保证绝大部分情况下不同的值hash之后其hash值不一样,哈希冲突比较少

这样就可以了吗?

No,MD5的生成需要占用比较长的CPU时间,所以我们需要寻找一种更简洁的校验方式,这里选用Alder32 是一个比较通用的解决方案


阅读(1210) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~