设为首页收藏本站

LinuxTone | 运维专家网论坛 - 最棒的Linux运维与开源架构技术交流社区!

 找回密码
 注册

QQ登录

只需一步,快速开始

#公告#抱歉,网站将关闭,不再开放。由于PC时代已远逝 。在这个后移动互联网时代,我们继续携手前行,保持对技术的热情。共同构建linuxtone知识星球欢迎加入,一起讨论技术、招聘人才、分享资源。请新老linuxtone人 扫码移步到 知识星球:linuxtone

学习是一种信仰!分享是一种快乐!能力= 心态 * 沟通 * 知识 (你的每一天需要正能量!)

 网站的发展需要你贡献一份力量!希望你能每天坚持看贴1小时,并回答网友的问题!祝你在浏览论坛的过程中取得进步!谢谢!linuxtone加油!大家加油! 友情提示: 你今天学习了吗?你今天进步了吗?少一点抱怨!多一点进步!Life is short ! Why not linuxtone ?  

网站的发展、感谢每位坛友的努力!

查看: 6967|回复: 3

[others] 详解rsync算法--如何减少同步文件时的网络传输量 [复制链接]

Rank: 4

签到
17
注册时间
2012-7-11
最后登录
2015-4-7
在线时间
7 小时
阅读权限
50
积分
1906
帖子
27
主题
26
精华
0
UID
32645
发表于 2015-3-27 14:58:27 |显示全部楼层
先看下图中的场景,客户端A和B,以及服务器server都保存了同一个文件,最初,A、B和server上的文件内容都是相同的(记为File.1)。某一时刻,B修改了文件内容,上传到SERVER上(记为File.2)。客户端A这时试图向服务器SERVER更新文件到最新内容,也就是File.1更新为File.2。


上面这个场景很常见,例如现在流行的网盘。假设我有一个文件a.txt在网盘上,上班时在公司的单位PC上更新了文件a.txt,下班后回到家里,家里PC硬盘上的a.txt就不是最新的内容,这时网盘就试图从服务器上去拿最新的a.txt了。

那么问题来了,如果在公司电脑上我只是更新了a.txt里很少的一部分内容,例如a.txt共有20M,我只更新了10个字节,难道家里的电脑上,网盘要从服务器上下载20M大小的文件?这明显很浪费带宽。
更有用的场景,假设我的手机android上也用了这个网盘(手机上网费贵得多),只改了几十字节的内容,就要下载20M的文件,得不偿失。或者我把这个文件共享给其他朋友,也有同样的问题:修改少量的内容,却同步完整的文件!

rsync算法就是用来解决上述问题的。client A发送它所保存的旧文件File.1少量的rsync摘要,server拿到后对比本地的File.2内容,得到File.2相对于File.1的变化,然后通过仅发送这个变化来代替发送完整的File.2内容,这样大大减少了网络传输数据。client A收到这个变化后,更新本地的File.1到最新的File.2。就是这么简单。下面详述rsync算法的步骤。

rsync首先需要客户端与服务器之间约定一个块大小,例如1K。然后把File.1等分成多个1K大小的字符串块,每块各计算出MD5摘要和Alder32校验和,如下图。


这里简单介绍下MD5和校验和。MD5是种哈希算法,用于把任意长度的字符串转化为固定为128位的定长字符串,这里可以保证,相同的字符串不可能计算出不同的MD5值。MD5的碰撞率是有的,就是说,两个不同的字符串有可能计算出相同的MD5值,但是这个机率非常小,这里我们忽略不计。例如,在rsync算法里,同一个文件按1K切分成多块,每块都有一个MD5值,如果两块字符串的MD5值相同,则我们认为这两块数据完全相同。
校验和是把上述1K块数据映射为32位大小整型数字上,我们采用Alder32算法,这里同样可以保证,相同的字符串不可能计算出不同的Alder32值。Alder32有两个优点:1、计算非常快,比MD5快多了,成本小;2、当我们有了从0-1024长度的校验和后,计算出1-1025或者2-1026等其他校验和非常方便,只要少量运算即可。当然,它的缺点也很明显,就是碰撞率比MD5高多了,所以,我们要把每个rynsc块同时计算出Alder32校验和与MD5值。Alder32算法我会在本文最后解释。

客户端按1K大小划分File.1文件为许多块,并对每块计算出MD5、Alder32校验和。最后不满1K的数据不做计算。之后,客户端把这些MD5、Alder32校验和依序通过网络传输给服务器,最后不满1K的数据直接发给服务器。那么,服务器收到数据后怎么处理呢?看下图。

首先重申,计算Alder32校验和非常快!
所以,服务器先把最新文件File.2从0字节开始,按1K切分成许多块,每块计算出Alder32校验和,然后与客户端发来的File.1切分出来的Alder32校验和相比,如果alder32值都不一样,毫无疑问,文件内容是不相同的。接着,把File.2从1字节开始,按1K切分成许多块,每块计算出Alder32校验和,再与客户端的校验和比。如此循环下去,直到某个校验和相同了,那么把这段字符串再计算出MD5值,再与客户端过来的对应的MD5值相比(还记得吧?客户端对每个块既计算出Alder32又计算出MD5值),如果不同,则继续往后移1字节,继续比Alder32、MD5值。如果相同,则认为这1K数据,服务器与客户端保存的一致,忽略这块数据(例如1K字节),继续向下看。

全部处理完后,按File.2的文件顺序,向客户端发送以下数据:对于不能够在客户端File.1数据块中找到相同块的字符串,直接列上发出;如果可以找到,则写上MD5和Alder32值,代替原来1024字节的数据块。同样,最后不足1K大小的部分直接列上发出。

纯理论读起来会有些吃力,我再把它简化了举个例子吧。假设客户端与服务器间约定的字符块大小不是1K,而是4个字节。客户端的文件内容是:
taohuiissoman
而服务器的文件内容是:
itaohuiamsoman
现在我们来看看,rsync算法是怎么运作的。

首先,客户端开始分块并计算出MD5和Alder32值。

如上图,像taoh是一块,对taoh分别计算出MD5和alder32值。以此类推,最后一个n字母不足4位保留。于是,客户端把计算出的MD5和alder32按顺序发出,最后发出字符n。

服务器收到后,先把自己保存的File.2的内容按4字节划分。

划分出itao、huia、msom、an,当然,这些串的Alder32值肯定无法从File.1里划分出的:taoh、uiis、soma、n找出相同的。于是向后移一个字节,从t开始继续按4字节划分。

从taoh上找到了alder32相同的块,接着再比较MD5值,也相同!于是记下来,跳过taoh这4个字符,看uiam,又找不到File.1上相同的块了。继续向后跳1个字节从i开始看。还是没有找到Alder32相同,继续向后移,以此类推。

到了soma,又找到相同的块了。

重复上面的步骤,直到File.2文件结束。

那么,最终客户端与服务器间传输的数据如下图所示。

上面这个例子很简单,可由此推导出复杂的情况,包括File.2对File.1在任意位置上做了增、改、删,都能够完成。
如果这是个大文本文件,应用rsync算法就非常有意义,例如20M的文件,实际可能只传输1M的数据量!这样用户体验会好很多,特别是网速慢的场景。
同时增加的消耗,就是在PC上计算的MD5值和Alder32校验和,这只消耗少量的CPU和内存而已。

最后列下Alder32的算法:
[cpp] view plaincopy
A = 1 + D1 + D2 + ... + Dn (mod 65521)  
B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)  
  = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)  
  
Adler-32(D) = B × 65536 + A  

D1到Dn就是待计算的字符串块,所有位上的ASC字符。它的C代码实现为:
[cpp] view plaincopy
const int MOD_ADLER = 65521;  
   
unsigned long adler32(unsigned char *data, int len) /* where data is the location of the data in physical memory and  
                                                       len is the length of the data in bytes */  
{  
    unsigned long a = 1, b = 0;  
    int index;  
   
    /* Process each byte of the data in order */  
    for (index = 0; index < len; ++index)  
    {  
        a = (a + data[index]) % MOD_ADLER;  
        b = (b + a) % MOD_ADLER;  
    }  
   
    return (b << 16) | a;  
}  

Rank: 8Rank: 8

注册时间
2011-9-16
最后登录
2020-5-27
在线时间
975 小时
阅读权限
90
积分
274705
帖子
2158
主题
2
精华
0
UID
15647
发表于 2015-3-28 09:28:42 |显示全部楼层
感谢楼主分享!

使用道具 举报

论坛元老

社区清洁工

Rank: 8Rank: 8

注册时间
2010-2-8
最后登录
2019-2-21
在线时间
304 小时
阅读权限
90
积分
46778
帖子
773
主题
29
精华
0
UID
7902
发表于 2015-3-30 11:13:01 |显示全部楼层
精华啊!
每天抽空上论坛学习,一步一步把基础打牢,做个技术专才。

使用道具 举报

Rank: 8Rank: 8

注册时间
2012-1-4
最后登录
2020-5-23
在线时间
426 小时
阅读权限
90
积分
235799
帖子
9
主题
0
精华
0
UID
17114
发表于 2015-3-30 21:03:09 |显示全部楼层
好思路,不过感觉好麻烦啊

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

IT运维专家网感谢您的支持

合作联系: QQ:67888954/MSN:cnseek@msn.com/mail:netseek@linuxtone.org

Archiver|手机版|感谢所有关心和支持过LinuxTone的朋友们 转载本站内容请注明原作者名及出处 ( 京ICP备08103151 )   |

GMT+8, 2020-5-27 04:09 , Processed in 0.025148 second(s), 16 queries , Apc On.

Powered by Discuz! X2 Licensed

© 2001-2011 Comsenz Inc.

回顶部