对应于ADMAD的两个方面的优点，本节主要从两个方面总结和分析相关工作，包括文件切分和重复数据删除算法，以及数据组织私存储布局。

　　1.文件切分重复数据删除算法

　　传统的无损压缩技术 (如gzip，以下简称压缩技术)由于I/O和内存的开销，运行速度太慢;它把数据从一种形式转换成另一种形式，使用前还要还原 (解压);规模不宜扩充，而且因为压缩算法要维持有限数最的状态信息，这样就不能识别彼此间隔的数据之间的冗余。

　　重复数据删除技术更多关注文件之间的压缩和去重技术。这种技术总的思路是把每一个文件切分成若干不重合 (non-overlapping)的数据片断 (Data Chunk)，然后把数据片断作为基本的逻辑存储和访问单位进行相应的处理和存储操作。重复数据删除算法可以进一步分成两类，即基于切分的方法 (Chunking based)和基于差最的方法 (DelbEncodingbasd)。

　　按照数据片段的长度和数据片段的边界，可以将基于切分的方法进一步细分为以下三种子方法.

　　1)以文件为数据片段粒度的切分

　　文件级粒度把整个文件作为一个数据片段。Farsite[48]首先研究了文件系统内部的数据公共性:Windows2000中的单例存储 (SlS)[49]使用整个文件压缩方法节省磁盘和主存高速缓存空间，链接时使用Windows20OONTFS中相同文件的复制语义。使用用户级服务groveler 自动寻找相同文件，跟踪文件系统的变化，并维护一个与文件索引相对应的数据库。在具有20个不同的WindowsNT映像的服务器上对SlS的测试表明可节省58%的存储空间:用于Web代理的基于复制的高速缓存RAC[50]使用MD5和对象长度而不是URL表示对象，在Web代理的高速缓存中只保留一份对象，减少了缓存占用最并提高了缓存对象命中率。实验结果表明，对不同缓存容量和替换算法，缓存命中率改进13·2一19·8，字节命申率改进7.3%～17.4%;DTD【51】。对Web整个有效载荷 (payload)计算MD5摘要，可以改进Web高速缓存命中率和减少15%的使用带宽。

　　2)定长数据片段切分

　　定长数据片段切分是指将每个待归档文件分割成若干个固定长度的数据片段，并且只存储不同的数据片段。Venti(37)存档系统，使用磁盘块固定长度的数据片段切分来减少存储空间的消耗，能节约存储空间约30%斯坦福大学在虚拟机迁移罔中用于检测重复数据块，减少在低速网络上传送的数据，当软件更新时可有效地压缩用户计算机的内存映像和磁盘映像:CMU的Nath等人(53)在基于虚拟机的企业客户管理系统(ISR)上研究不同长度的定长数据片段对存储空间和网络估送效率的影响，结论是短数据片段比长数据片段压缩效率商，如便用4KB的数据片段，可使存储空间从87GB减少到36GB，而使用5l2KB的数据片段时，存储空间从342GB减少到137GB。另外，数据片段长度越短，元数据开销越大。但元数据的开销随着数据片段长度的减小增加得比较缓慢，而存储空间的压缩效果随数据片段长度的减小越发显著，所以减小数据片段长度收益大。Nath等人提出了最佳数据片段长度:对干末压缩数据使用4K8数据片段，而对于已压缩 (gzip)的数据使用16KB期数据片段。在减少网络传输数据最方面，上传时使用4KB数据片段比l28KB记平均减少一半(不管侍传送的数据是否是压缩的)，而下载(8GB以上)时缩短到 1/31.4(未压缩数据)和1/55(同时使用数据片段压缩和gzip压缩)。使用定长数据片段切分的缺点是，当在数据对象中插入或删除部分数据，从而改变相邻的数据片段边界时，全部数据片段的边界都要改变，大大降低了压缩率。为了解决这个问题，可以先使用容易计算的、可在数据对象上滚动的弱报文摘要发现匹配，再使用强报文摘要避行比较，确定重复(简称滚动定长数据片段)。例如，rsync(54)，(55)在网上把一个目录树复制到另一个包含相似文件的目录树，寻找使用同一名字存储的文件的相似性以节省带宽:Surie等人(56)在虚拟机迁移中使用rsync。有效地同步虚拟机内存映像，使用SHA-I识别和传送不同部分，减少的数据传输量可达80.5。

　　3)变长数据片段切分

　　先在滑动窗口(典型为48个字节)上计算Rabin Fingerprint指纹(57),(58),(59)，当指纹低序位与某个值匹配时，则确定一个数据片段的边界。由于数据片段的边界是基于内容寻址的，所以插入或删除数据只能使包含变化数据的数据片段的长度增长或缩短，而不会影响相邻的数据片段。LBFS(60)系统、Pasta(61)系统和Pastiche(62)系统等，均采用这种变长数据片段切分方法。

　　LBFS系统是将Rabin Fingerprint指纹用于此目的的第一个系统，拟用在低带宽网络上传输数据。LBFS使用算Rabin Fingerprinting指纹识别算法，在文件之间或同一文件的不同版本之间发现相似性，避免在客户高速缓存和数据服务器之间重发相同的数据片段。实验表明，LBFS的数据片段切分算法在354MB的数据集申发现了约20%的重复数据。

　　在实验的P2P文件系统Pasta的数据片段切分方法中，高速缓存和副本的布置是由数据片段的内容所决定的。在滑动窗口上计算文件数据的算Rabin Fingerprint指纹创建这些数据片段。类似的技术也适用于Pastiche系统。

　　VBWC算法(63)在Web高速缓存中使用变长数据片段 (MD5算法)对数据进行检索，在低带宽网络 (如低于80kb/s的电话网或无线网)上的父代理和子代理之间传送非冗余数据。最近一些研究工作对变长数据片段切分方法进行了不同程度的政进。惠普的TTTD框架(64)减小了数据片段长度的变化范围，尽量避免很小的和很大的数据片段，把开销减少到1/1.6(其Hash函数使用MD5函数):Fingerdiff(65)是一种新的文件切分方法，其原理是在数据改变的区域内充分减小包含变化数据的数据片段长度，但保持区域内未受改变数据影响的数据片段长度足够大，动态地重新划分数据，把未改变的数据块聚合成为大数据片段，将含有更新数据的新数据片段最小化，克服了变长数据片段切分方法在数据片段长度较小时管理开销大的困难，从而改进了重复数据删除的能力，同时减少了存储管理开销。实验表明其存储效率平均提高25%，带宽利用率平均提高40%，且可以支持数据片段长度在较大范围内变化。但这种方法在实际应用中开销较大，且不适用于海量存储系统。

　　责任编辑：GOCN