文件副本经常在网络上来回被COPY多次,很多情形下这些文件副本之间仅有很小的差异,很可能是从同一个文件版本演化而来。如果对文件进行完全COPY,在文件较大的情况下,会占用大量网络带宽,同步时间也会较长。Rsync是类Unix环境下的一个高效的远程文件复制(同步)工具,它通过著名的Rsync算法来优化流程,减少了数据通信量并提高文件传输效率。它的大致流程如下:
假设现在有两台计算机Alpha和Beta ,计算机Alpha能够访问A文件,计算机Beta能够访问B文件,文件A和B非常相似,计算机Alpha和Beta通过低速网络互联。
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作者Andrew Tridgell的tech_report.ps。
Rsync是一个非常优秀的工具,但它仍然存在一些不足之处。
1、Rolling checksum虽然可以节省大量checksum校验计算量,也对checksum搜索作了优化,但多出一倍以上的hash查找,这个消耗不小;
2、Rsync算法中,Alpha和Beta计算量是不对等的,Alpha计算量非常大,而Bete计算量非常小。通常Alpha是服务器,因此压力较大;
3、Rsync中数据块大小是固定的,对数据变化的适应能力有限。
为了弥补以上这些不足,我利用dedup技术中的变长块数据切分算法,重新实现了一个远程相似文件同步原型dedup_sync。它的大致流程与Rsync相似,简单描述如下:
1、Beta采用变长块数据切分算法CDC(Content-defined chunking)将文件B分割成大小不等的数据块;
2、Beta对于每一个数据块,计算md5校验值,并记录数据块长度len和在文件B中的偏移量offset;
3、Beta将这将数据块信息发送给Alpha;
4、Alpha采用同样的数据块切分技术将文件A切成大小不等的数据块,并与Beta发过来的数据信息进行md5搜索匹配;
5、Alpha给Beta发送重构文件A的指令,每一条指令是一个文件B数据块引用(匹配)或者是文件A数据块(未匹配)。
明显地,上面这算法与rsync算法相比,去除了rolling checksum计算与hash查找,数据块大小是变化的,alpha与beta计算量也是对等的。
变长块切分CDC算法,我在dedup uitl中有实现,感兴趣读者可以去http://sourceforge.net/projects/deduputil下载源码。
当然,CDC算法也是有缺陷的,数据块大小的确定比较困难,粒度太细则开销太大,粒度过粗则dedup效果不佳。如何在两者之间权衡折衷,这是一个难点。
分享到:
相关推荐
基本用法: dedup <INPUT> [-o ] 运行dedup --help来查看: USAGE: dedup.exe [FLAGS] [OPTIONS] [INPUT] FLAGS: -l, --count-lines If flag is set only print the number of unique entries found. -...
通过在开放式堆栈中使用重复数据删除技术,设计并实现了一种图像管理系统IM-dedup,该系统使用静态分块(SC)将图像文件划分为数据块,并避免使用指纹预传输技术在网络上传输重复数据块,通过在映像存储服务器中...
R-Dedup:基于SSD的RAID系统的内容感知冗余管理
为解决云存储系统中机密数据去重面临的密文重复性检测与拥有性证明、针对数据机密性的攻击等难题,提出了基于Merkle散列树的MHT-Dedup方案和基于同态MAC的hMAC-Dedup方案。两者均通过对密文文件的拥有证明进行跨用户...
##描述文件被切成 512 字节的块唯一的块存储在一个巨大的转储文件中,并组织在一个中央索引日志中去重文件由包含原始块索引的二进制文件表示##依赖GNU/Linux ##用法重复数据删除{主机,GPU} -i <文件名> ...
开源项目-jpillora-dedup.zip,A command-line tool to deduplicate files
重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除 重复数据删除
from text_dedup . dedupers import EditDistanceSimilarityDeduper from text_dedup import group_duplicates df = pd . read_csv (...) df_groups = group_duplicates ( df , deduper = ...
重复的Windows Utility,用于搜索重复文件
spotify-dedup, 从你的Spotify播放列表中删除重复项 一个Spotify播放列表副本你是否想从你的Spotify播放列表中删除重复的音轨? 现在,你可以使用Spotify重复数据删除来检测并删除它们。这个项目使用 Spotify Web ...
installnpm i dedup-arrayUsagelet filteredArr = dedup(array,["key1","key2"])Demolet dedup = require("dedup-array");let array = [ { id: 1, name: '1', prop: { url: "url1", description: "des1" } }, { id: ...
HashBackup是Unix命令行备份程序,可使用以下方式在您自己的存储帐户...并在它们之间进行dedup备份服务器上托管的许多VM映像,从而在它们之间重复数据删除客户端计算机已存储在已安装的备份服务器上的所有备份文件空间
这是一个非常简单的实用程序,用于修复具有来自跨接端口等的重复流量的PCAP文件。 它使用IP ID字段根据该流的最后10个数据包中出现的源/目标来识别任何重复项。
用于对视频文件进行重复数据删除的工具 分支 掌握 该工具包括服务器和客户端模块。 默认情况下,客户端在本地主机上查找服务器。 使用实现通信。 服务器搜索视频文件的副本。 重复项由以下可配置设置确定: 要...
require 'resque/plugins/dedup' class DoSomeHeavyLifting extend Resque::Plugins::Dedup def self.perform(some_id) heavy_lifting end end 任何时候都只会将这个作业的一个实例加入队列。 作业由lock键标识...
里面介绍了一些MapReduce的案例,可以共初学者练习,再也不用不再局限于WordCount案例
随着重复数据删除次数的增加,系统中用于存储指纹索引的清单文件等元数据信息会不断累积,导致不可忽视的存储资源开销。...针对查重元数据中存在大量冗余数据,提出了一种基于压缩近邻的查重元数据去冗算法Dedup
语言:English (United States) 删除重复的标签。 自动关闭重复的标签页。
为了使使用dedup和renameall命令更容易地执行重复性任务,可以将预设存储在配置文件中。 fwt --help和fwt CMD --help将提供CLI和支持的命令的简要用法信息。 使用pip python3 -m pip install git+h
重复数据删除 欢迎 这是我们在 TOS 中介绍的论文中描述的 RevDedup 的源代码。...对输入文件(Segment 和 Chunk)执行分块并输出元数据文件 ./chunking <input file> <output chunking metafi