详解rsync算法--如何减少同步文件时的网络传输量

el/2024/3/2 11:36:51
 

详解rsync算法--如何减少同步文件时的网络传输量

分类: 技术分享 算法 C/C++ 13504人阅读 评论(30) 收藏 举报
算法网络服务器server手机android

先看下图中的场景,客户端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
  1. A = 1 + D1 + D2 + ... + Dn (mod 65521)  
  2. B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)  
  3.   = n×D1 + (n−1)×D2 + (n−2)×D3 + ... + Dn + n (mod 65521)  
  4.   
  5. Adler-32(D) = B × 65536 + A  

D1到Dn就是待计算的字符串块,所有位上的ASC字符。它的C代码实现为:

[cpp] view plaincopy
  1. const int MOD_ADLER = 65521;  
  2.    
  3. unsigned long adler32(unsigned char *data, int len) /* where data is the location of the data in physical memory and  
  4.                                                        len is the length of the data in bytes */  
  5. {  
  6.     unsigned long a = 1, b = 0;  
  7.     int index;  
  8.    
  9.     /* Process each byte of the data in order */  
  10.     for (index = 0; index < len; ++index)  
  11.     {  
  12.         a = (a + data[index]) % MOD_ADLER;  
  13.         b = (b + a) % MOD_ADLER;  
  14.     }  
  15.    
  16.     return (b << 16) | a;  
  17. }  

http://www.ngui.cc/el/1380842.html

相关文章

求树的“直径”以及所想到的

分类&#xff1a; c2013-11-05 14:59 249人阅读 评论(0) 收藏 举报算法导论直径算法导论22.2-7题&#xff1a;树T&#xff08;V,E&#xff09;的直径&#xff08;diameter&#xff09;定义为max(u,v)&#xff0c;亦即&#xff0c;树的直径是树中所有最短路径长度中的最大值。试…

Python的动态加载机制

分类&#xff1a; python2013-03-25 23:23 380人阅读 评论(0) 收藏 举报python动态加载延迟导入众所周知import是用来加载Python模块的&#xff0c;其实import是调用内建函数__import__来工作的&#xff0c;这就使我们动态加载模块变成了可能。 [python] view plaincopy import…

HDU 3666 THE MATRIX PROBLEM (差分约束判负环)

分类&#xff1a; ACM_HDU ACM_图论2013-10-27 13:37 226人阅读 评论(0) 收藏 举报差分约束题意: 给你一个N*M的矩阵C&#xff0c;问是否存在一个长度为N的数列a和长度为M的数列b使得所有C(i,j)*a(i)/b(j)在L , U范围内。 解题思路: 有两个式子 C(i,j)*a(i)/b(j) > L , C…

Redis2.2.2源码学习——dict中的hashtable扩容和rehash

[置顶] 分类&#xff1a; Redis2013-10-17 13:35 377人阅读 评论(0) 收藏 举报redishash扩容Redis2.2.2 dict是Redis的hash数据结构&#xff0c;所有类型的元素都可以依据key值计算hashkey&#xff0c;然后将元素插入到dict的某个hash链上&#xff08;采用拉链法解决hash冲突&…

POJ 2187 Beauty Contest 构造凸包 + 旋转卡壳

分类&#xff1a; 计算几何2013-10-23 09:17 240人阅读 评论(0) 收藏 举报目录(?)[] 在刷了一整版的 TLE 和 WA 外加一个CE和几个OLE之后终于拿到了第一个旋转卡壳的AC。。。泪奔 http://blog.csdn.net/ACMaker/archive/2008/10/29/3176910.asp http://cgm.cs.mcgill.ca/~orm/…

poj 2104 K-th number (模板级划分树)

分类&#xff1a; 数据结构2013-07-19 16:36 191人阅读 评论(0) 收藏 举报划分树代码测试通过那一刻&#xff0c;我心都碎了。 昨天晚上开始学习划分树&#xff0c;花了大概一个小时左右弄清楚了划分树的原理&#xff08;自以为弄清楚了&#xff09;。然后在网上找了一份代码对…

[poj 1364]King[差分约束详解(续篇)][超级源点][SPFA][Bellman-Ford]

[poj 1364]King[差分约束详解(续篇)][超级源点][SPFA][Bellman-Ford] 分类&#xff1a; 图论2013-08-24 11:30 187人阅读 评论(0) 收藏 举报目录(?)[] 题意 有n个数的序列, 下标为[1.. N ], 限制条件为: 下标从 si 到 sini 的项求和 < 或 > ki. 一共有m个限制条件. 问是…

数论相关知识

ACM 进阶学习第一课----同余相关之欧几里得算法及其扩展&#xff08;2&#xff09; 分类&#xff1a; C/C学习进阶之路2013-11-03 02:16 747人阅读 评论(0) 收藏 举报目录(?)[] 最大公约数算法分析 欧几里德算法 伪代码while b>0 do r←a%b a←b b←…

高次同余方程式的解数及解法

分类&#xff1a; 数论2013-07-26 18:41 561人阅读 评论(0) 收藏 举报定理一&#xff1a; 若是k个两两互质的正整数&#xff0c;&#xff0c;则同余式 (1) 与同余式组 (i1,2,3,...,k) (2) 等价&#xff0c;并且若用表示对模的解数&#xff0c;T表示(1)式对模m的解数&…

ZOJ 1654 Place the Robots(超牛的建图思路) - from lanshui_Yang

ZOJ 1654 Place the Robots&#xff08;超牛的建图思路&#xff09; - from lanshui_Yang 分类&#xff1a; 图论2013-08-03 09:54 423人阅读 评论(0) 收藏 举报二分图建图最大匹配Place the RobotsTime Limit: 5 Seconds Memory Limit: 32768 KBRobert is a famous engineer. …