1、引言

基于LAN或WAN的网络应用之间进行数据传输或者同步非常普遍，比如远程数据镜像、备份、复制、同步，数据下载、上传、共享等等，最为简单的做法自然就是对数据进行完全复制。然而，数据在网络上来回被复制多次后就会存在大量副本，很多情形下这些文件副本之间仅有很小的差异，很可能是从同一个文件版本演化而来。如果对文件进行完全复制，在文件较大的情况下，会占用大量网络带宽，同步时间也会较长。

目前，广域网WAN的带宽与访问延迟仍然是急需解决的问题，完全复制使得很多网络应用无法提供良好的服务质量，比如分布式文件系统(DFS)、云存储(Cloud Storage)。Rsync与RDC(Remote Differential Compression)是两种最为常见的数据同步算法，它们仅传输差异数据，从而节省网络带宽并提高效率。本文基于这两种算法思想并借助重复数据删除(De-duplication)技术，对数据同步算法进行深入研究与分析，并研发了原型系统。首先介绍rsync与RDC算法，然后详细描述算法设计与相应的数据结构，并重点分析文件分块、差异编码、文件同步算法，最后简介推拉两种应用模式。

2、相关工作

Rsync是类Unix环境下的一个高效的远程文件复制(同步)工具，它通过著名的Rsync算法来优化流程，减少了数据通信量并提高文件传输效率。假设现在有两台计算机Alpha和Beta ,计算机Alpha能够访问A文件,计算机Beta能够访问B文件，文件A和B非常相似，计算机Alpha和Beta通过低速网络互联。它的大致流程如下(详细过程请参考Rsync作者Andrew Tridgell的tech_report.ps)：

1、Beta将文件B分割成连续不重叠的固定大小数据块S，最后一个数据块上可能会小于S字节；

2、Beta对于每一个数据块,计算出两个校验值，一个32位的弱滚动校验和一个128位的MD4校验；

3、Beta将校验值发送给Alpha；

4、Alpha通过搜索文件A的所有大小为S的数据块(偏移量可以任意，不一定非要是S的倍数)，来寻找与文件B的某一块有着相同的弱校验码和强校验码的数据块。这主要由滚动校验Rolling checksum快速完成；

5、Alpha给Beta发送重构A文件的指令，每一条指令是一个文件B数据块引用（匹配）或者是文件A数据块（未匹配）。

Rsync是一个非常优秀的工具，但它仍然存在一些不足之处。

1、Rolling checksum虽然可以节省大量checksum校验计算量，也对checksum搜索作了优化，但多出一倍以上的hash查找，这个消耗不小；

2、Rsync算法中，Alpha和Beta计算量是不对等的，Alpha计算量非常大，而Bete计算量非常小。通常Alpha是服务器，因此压力较大；

3、Rsync中数据块大小是固定的，对数据变化的适应能力有限。

RDC算法的典型代表是微软DFS中的DFSR(Distributed File System Replication)，它与Rsync不同之处在于采用一致的分块规则对复制的源文件和目标文件进行切分。因此，RDC对于源端和目标端的计算量是对等的。RDC和RSync算法在设重点上有所不同，Rsync追求更高的重复数据发现而不惜计算量；RDC在两者之间作了一个折衷，目标是以少量的计算快速发现数据差异，当然重复数据发现不及Rsync。另外，Rsync是定长分块策略，而RDC是变长分块策略。

3、重复数据删除技术

De-duplication，即重复数据删除，它是一种非常新的且流行度很高的存储技术，可以大大减少数据的数量。重复数据删除技术，通过数据集中重复的数据，从而消除冗余数据。借助dedup技术，可以提高存储系统的效率，有效节约成本、减少传输过程中的网络带宽。同时它也是一种绿色存储技术，能有效降低能耗。

Dedupe按照消重的粒度可以分为文件级和数据块级。文件级的dedup技术也称为单一实例存储(SIS, Single Instance Store)，数据块级的重复数据删除，其消重粒度更小，可以达到4-24KB之间。显然，数据块级的可以提供更高的数据消重率，因此目前主流的 dedup产品都是数据块级的。将文件都分割成数据块(定长或变长的数据块)，采用MD5或SHA1等Hash算法 (可以同时使用两种或以上hash算法或CRC校验等，以获得非常小概率的数据碰撞发生)为数据块计算指纹(FP, Fingerprint)。具有相同FP指纹的数据块即可认为是相同的数据块，存储系统中仅需要保留一份。这样，一个物理文件在存储系统就对应一个逻辑表示，由一组FP组成的元数据。当进行读取文件时，先读取逻辑文件，然后根据FP序列，从存储系统中取出相应数据块，还原物理文件副本。

出处：CSDN
责任编辑：bluehearts

上一页 下一页 数据同步算法研究 [2]

◎进入论坛网络编程版块参加讨论