2023年7月27日发(作者：)

如何实现⽂件增量同步——算法问题：如何增量同步⽂件，例如⼀个⽂本⽂件有10M，分别存放在A，B两个地⽅，现在两个⽂件是完全⼀样的，但是我马上要在A上对这个⽂件进⾏修改，B如何实现⾃动和A上的⽂件保持⼀致，并且⽹络的传输量最少。

应⽤场景：这样的使⽤场景太多，这⾥随便列举⼏个1.A机器为线上运营的机器，现在需要⼀台备份的机器B，当A发⽣宕机的时候，或者硬盘损坏等各种认为⾮⼈为原因导致数据不可⽤时，可以很快从B恢复这样的应⽤场景，不需要每次修改都向服务器发送并替换掉⼀个⽂件，⽽是只发送被修改的部分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 是⼀个⽐较通⽤的解决⽅案

Alder32有两个优点：

1、计算⾮常快，⽐MD5快多了，成本⼩；2、当我们有了从0-k长度的校验和后，计算出1-k或者2-k等其他校验和⾮常⽅便，只要少量运算即可。(k可以理解为上⾯的20Byte)

当然，它的缺点也很明显，就是碰撞率⽐MD5⾼多了，所以，我们客户端需要同时计算出Alder32校验和与MD5值，传给服务器，⽽服务器，为了节省CPU时间，第⼀步只⽣成Alder32进⾏校验，当值相等时，在进⾏MD5校验，这样服务器就节省了很⼤的开⽀。Alder32算法实现：

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 + AC实现版本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;}

三.实现更改因为已经找出来了⽂件不同的地⽅，所以只需要按需上传更改的部分到服务器，然后服务器做更改就可以了。

实例分析：

理论概述完毕，来点⼩例⼦⼦客户端⽂件内容是：

taohuiissoman⽽服务器的⽂件内容是：itaohuiamsoman

⾸先，客户端开始分块并计算出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⽂件结束。

通过这个简单的例⼦，可以设想⼀下其他任何的增删查改功能

参考资料：