重复数据删除(De-duplication)技术研究
- 格式：pdf
- 大小：235.79 KB
- 文档页数：14
文档推荐
-
SQL删除重复数据页数:4
-
SQL中重复数据的查询与删除页数:16
-
如何消除重复数据删除的四大误区页数:2
-
重复数据删除技术简介页数:4
-
excel电子表格如何删除重复记录页数:2
-
如何删除Excel表里的重复数据页数:5
下载文档原格式
合集下载
数据处理中的数据去重方法
数据处理中的数据去重方法数据去重是指在数据处理过程中，从一个数据集中删除重复的数据行或数据记录。
在实际数据处理操作中，数据可能存在重复记录的情况，这可能是由于多种原因引起的，比如数据采集的问题、数据输入错误、数据合并等。
数据去重是数据处理的一个常见任务，可以提高数据的质量和准确性，提高后续数据分析和应用的效果。
下面是一些常见的数据去重方法：1.基于字段的去重：根据一些或几个字段的唯一性来进行去重。
比如，对于一个包含学生信息的数据集，可以根据学生的学号字段来进行去重，保留每个学号对应的唯一一条记录。
2.整行去重：将整行数据作为一个唯一标识，去除重复的行。
这种方法适用于数据集中每一行的数据都是完全一样的情况。
3.字段组合去重：将多个字段的组合作为唯一标识，去除重复的组合。
比如，对于一个包含商品信息的数据集，可以根据商品的名称、价格和品牌组合来进行去重，保留每个组合的唯一一条记录。
4.抽样去重：通过抽样的方式来判断数据的重复性。
对于大规模的数据集，可以通过抽取一定比例的数据样本，然后对样本进行去重，再根据样本的去重结果对原始数据集进行去重。
5.哈希算法去重：使用哈希算法将数据转换成唯一的哈希值，然后根据哈希值来判断数据的重复性。
比较常用的哈希算法有MD5、SHA-1等。
通过将数据进行哈希转换后，可以快速地判断数据是否重复，从而进行去重操作。
6.基于相似度的去重：对于一些非精确匹配的场景，可以使用相似度算法来进行去重。
比如，对于一个包含文本信息的数据集，可以使用文本相似度算法来计算文本之间的相似度，然后根据相似度来判断文本的重复性。
7.基于规则的去重：根据一定的规则来进行数据去重。
比如，对于一个包含日期信息的数据集，可以根据日期的范围来进行去重操作，保留每个日期范围内的唯一一条记录。
8.基于机器学习的去重：利用机器学习的方法来进行数据去重。
可以通过训练一个二元分类模型，将数据分为重复和非重复两类，然后根据模型的预测结果来进行去重操作。
重复数据删除(De-duplication)技术研究
重复数据删除(De-duplication)技术研究1、Dedupe概述De-duplication，即重复数据删除，它是一种目前主流且非常热门的存储技术，可对存储容量进行有效优化。
它通过删除数据集中重复的数据，只保留其中一份，从而消除冗余数据。
如下图所示。
这种技术可以很大程度上减少对物理存储空间的需求，从而满足日益增长的数据存储需求。
Dedupe技术可以带许多实际的利益，主要包括以下诸多方面：(1) 满足ROI(投资回报率，Return On Investment)/TCO(总持有成本，Total Cost of Ownership)需求；(2) 可以有效控制数据的急剧增长；(3) 增加有效存储空间，提高存储效率；(4) 节省存储总成本和管理成本；(5) 节省数据传输的网络带宽；(6) 节省空间、电力供应、冷却等运维成本。
Dedupe技术目前大量应用于数据备份与归档系统，因为对数据进行多次备份后，存在大量重复数据，非常适合这种技术。
事实上，dedupe技术可以用于很多场合，包括在线数据、近线数据、离线数据存储系统，可以在文件系统、卷管理器、NAS、SAN中实施。
Dedupe也可以用于数据容灾、数据传输与同步，作为一种数据压缩技术可用于数据打包。
Dedupe技术可以帮助众多应用降低数据存储量，节省网络带宽，提高存储效率、减小备份窗口，节省成本。
Dedupe的衡量维度主要有两个，即重复数据删除率(deduplocation ratios)和性能。
Dedupe性能取决于具体实现技术，而重复数据删除率则由数据自身的特征和应用模式所决定，影响因素如下表[2]所示。
目前各存储厂商公布的重复数据删除率从20:1到500:1不等。
2、Dedupe实现要点研发或应用Dedupe技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。
(1) What：对何种数据进行消重？对时间数据还是空间数据进行消重，对全局数据还是局部数据进行消重？这是首先需要考虑的因素，这直接决定着Dedupe实现技术和数据消重率。
重复数据处理的技巧
重复数据处理的技巧在处理数据时，常常会遇到重复数据的情况。
重复数据可能会导致分析结果的偏差，因此在进行数据分析之前，需要对重复数据进行处理。
下面是一些处理重复数据的常用技巧：1. 查找重复数据：首先，需要找出数据集中的重复数据。
可以通过使用Excel的“条件格式”功能或者编程语言中的函数（如Python的pandas库的.duplicated(函数）来查找数据集中的重复项。
2. 删除重复数据：一旦找到了重复数据，可以选择直接删除这些重复项。
在Excel中，可以使用“删除重复项”功能来删除数据集中的重复数据。
在编程语言中，也可以使用相应的函数（如Python的pandas库的.drop_duplicates(函数）来删除重复项。
3. 标记重复数据：有时候，需要保留数据集中的重复项，并对其进行标记。
可以在数据集中添加一个新的列，并给重复项进行标记。
例如，在Excel中，可以使用函数如IF和COUNTIF来对重复项进行标记。
在编程语言中，可以使用条件语句来对重复项进行标记。
4. 合并重复数据：在一些情况下，需要将数据集中的重复项进行合并。
例如，对于销售订单数据，如果存在相同的订单号，可以将这些订单合并为一个订单并计算总销售金额。
可以使用Excel的透视表功能或者编程语言中的函数（如Python的pandas库的.groupby(函数）来合并重复数据。
5. 替换重复数据：有时候，需要将重复数据替换为其他值。
例如，可以将每个重复项替换为其在数据集中的平均值。
在Excel中，可以使用函数如AVERAGEIF和COUNTIF来计算重复项的平均值，并使用函数如VLOOKUP来将重复项替换为平均值。
在编程语言中，可以使用相应的函数（如Python的pandas库的.groupby(和.transform(函数）来计算重复项的平均值，并将其替换为重复项。
6. 拆分重复数据：有时候，需要将含有重复数据的单元格拆分成多个单元格。
企业数据备份与容灾问题的探讨
企业数据备份与容灾问题的探讨作者：赵妍来源：《电子世界》2013年第10期【摘要】随着企业信息化建设工作的不断深入，企业的数据量在日益扩大，数据资料已经成为企业的重要资源，其安全性也倍受关注。
怎样保证数据的安全可靠，保证企业业务系统的连续运营是IT运维管理工作中首要考虑的问题。
企业要保持业务连续性，最大的威胁并不是来自于火灾、地震等小概率、大影响的灾难，更多地是受到诸如于硬件故障、软件崩溃、人员错误、流程缺陷等事件的威胁，这些威胁造成的企业业务系统的中断会对企业造成致命的打击，因此数据备份工作显得尤为重要。
本文就企业数据备份的必要性，方法以及灾难恢复的手段等方面加以阐述、探讨，介绍了重复数据删除技术（Data De-duplication）及持续数据保护技术（Continuous Data Protection）的应用。
【关键词】企业数据；数据安全；连续数据保护；异地容灾一、数据备份的重要性1.系统风险分析近几年来，许多大中型企业十分重视信息技术的应用和开发，建设“数字化企业”已成为很多企业的目标，越来越多的生产经营活动建立在信息化的基础上。
一个大中型企业的信息化应用环境可能包含了OA、采购管理、财务、图档管理，人力资源、CRM等多种应用系统，以及数台基于Windows或Linux操作系统的文件服务器，数据库服务器、WEB服务器、邮件服务器、打印服务器、域管理服务器等多种功能服务器。
怎样保护好这些业务系统的数据，是信息管理工作的重中之重。
尽管系统本身已经有了一些容错机制和备份措施，比如集群或者采用RAID0+1或RAID5的保护方式，但是，仍然存在单点故障的风险。
如果不进行统筹的规划，数据分散存储，存在安全风险，IT运维人员维护负担较重，需要确保所有独立数据的安全，才能保证整体安全，数据恢复演练也比较困难。
2.数据备份需求针对以上这些可能存在的风险，如何对业务数据以及业务系统进行系统的备份，从而有效地进行管理，企业的需求是：（1）对现有的各种应用系统以及办公文档、设计图档等重要的文件数据进行基于策略的集中保护。
数据库容灾基础知识
2.2 快照技术
SNIA（存储网络行业协会）对快照 SNIA（存储网络行业协会）对快照 （Snapshot）的定义是：关于特定数据集合的 Snapshot）的定义是：关于特定数据集合的 一个完全可用拷贝，该数据集包含源数据在拷 贝点的静态映像，是数据再现的一个副本或者 复制。快照实际上是建立了数据的目录表，保 存了源数据在存储设备上的数据指针，作用是 提供在线备份和恢复服务，用户可以访问快照 数据而不影响应用系统对元数据的正常操作， 灾难发生时可以将数据恢复到快照产生的时间 点。
数据库容灾基础知识
王煜
摘要
一.容灾相关概念 二.容灾系统关键技术
一.容灾相关概念
1.1 容灾定义 1.2 容灾分类 1.3 容灾等级 1.4 容灾技术指标
1.1 容灾定义
容灾（Disaster Tolerance），就是在灾难发 容灾（Disaster Tolerance），就是在灾难发 生时，在保证应用系统的数据尽量少丢失的情 况下，维持系统业务的连续运行。
二 容灾关键技术
容灾备份系统常用的技术包括镜像技术、快照 技术、连续数据保护技术和重复数据删除技术 等。
2.1 镜像技术
镜像（Mirroring）是数据冗余的一种形式，是 镜像（Mirroring）是数据冗余的一种形式，是 将一个磁盘上的数据在另一个或多个磁盘系统 上生成完全相同的数据副本的过程。它分为主 镜像系统和从镜像系统。根据两系统所处地理 位置的不同分为本地镜像和远程镜像。本地镜 像的主从镜像系统处于一个局域网中，远程镜 像的主从镜像系统通过城域网或广域网相连。
1.2 容灾分类
容灾可以区分为离线式容灾（冷容灾）和在线 容灾（热容灾）两种类型。
1.3 容灾等级
level 0 Βιβλιοθήκη 2 3 4 5 6 sub本地数据容灾 本地应用容灾 异地数据冷备份 异地异步数据容灾 异地同步数据容灾 异地异步应用容灾 异地同步应用容灾
数据容灾系统及相关技术 RTO和RPO
1.容灾相关概念2.1容灾定义容灾（Disaster Tolerance），就是在灾难发生时，在保证应用系统的数据尽量少丢失的情况下，维持系统业务的连续运行。
和容灾比较容易混淆的概念有容错和灾难恢复。
容错是指在计算机系统软硬件发生故障时，保证系统能继续运行的能力，主要通过硬件冗余和错误检查等技术来实现；容灾是通过系统冗余、灾难检测和系统迁移等技术来实现。
灾难恢复是指灾难发生后，系统恢复正常运行的能力；而容灾指灾难发生时保持系统不间断运行的能力。
1.2容灾分类容灾可以区分为离线式容灾（冷容灾）和在线容灾（热容灾）两种类型。
离线式容灾主要依靠备份技术来实现。
首先通过备份软件将数据备份到磁带上，然后将磁带异地保存、管理。
数据的备份过程可以实现自动化管理，整个方案的部署和管理比较简单，投资较少。
缺点在于：系统的数据恢复较慢，备份窗口内的数据丢失严重，实时性差。
对RTO（Recovery Time Objective）和RPO（Recovery Point Objective）要求较低的用户可以选择这种方式。
在线式容灾中，源数据中心和灾备中心同时工作。
数据在写入源数据中心的同时，实时地被复制传送到灾备中心。
在此基础上，可以在应用层进行集群管理，当生产中心遭受灾难、出现故障时，可由灾备中心自动接管并继续提供服务。
应用层的管理一般由专门的软件来实现，可以代替管理员实现自动管理。
在线容灾可以实现数据的实时复制，因此，数据恢复的RTO和RPO都可以满足用户的高要求。
因此，数据重要性很高的用户都应选择这种方式，比如金融行业的用户等。
实现这种方式的容灾需要很高的投入。
容灾备份系统按照灾难防御程度的不同，可分为数据容灾和应用容灾。
数据容灾是对应用系统数据按照一定的策略进行异地容灾备份，当灾难发生时，应用系统暂时无法正常运行，必须花费一定时间从灾备中心恢复应用关键数据至本地系统以保证业务的连续性和数据的完整性，因为异地容灾备份系统只保存了灾难发生前应用系统的备份数据，因此数据容灾可能会产生部分数据丢失。
关于“重复数据删除”技术，你还需要知道这些
关于“重复数据删除”技术，你还需要知道这些展开全文重复数据删除(De-duplication)，简称“去重”，是主流的存储技术之一，通过对比校验技术删除存储设备上重复的数据，只保留其中一份，从而消除冗余数据，优化存储设备的物理空间，从而满足日益增长的数据存储需求。
经过近些年的发展，重复数据删除技术已经很成熟，本文整理了部分知识，有助于大家进一步了解重复数据删除。
一、重复数据删除技术的价值虽然存储介质的价格已经非常廉价，但若能在有限的存储介质上实现更高的存储效率，何乐而不为呢？此外，重复数据删除技术最大的一个收益点是能降低备份大数据量时对各资源的消耗和依赖。
巨量数据的备份不论对生产系统还是备份系统都是一个不小的冲击，况且随着系统的发展，备份系统越来越大，备份的数据越来越多，备份的计划与安排越来越受制于备份数据量的规模。
重复数据删除技术提供了一个物美价廉的解决方案，更提高了整个系统的效率。
也许在很多不太关注重复数据删除技术的工程师心中，重复数据还是那个效率低、成本高的空壳子，但实际上重复数据删除技术早已发展到了一个新的高度。
借个人实施经历中一个真实的案例，看看现如今的重复数据删除技术的性能：一台Windows虚拟机存储着490 GB（有效数据）非结构化文件（文件主要为word/Excel/PPT/PDF 等），日变化量大约15 GB/DAY,虚拟机的配置为2 * 2.8 GHz CPU，8 GB内存，千兆网卡。
部署了一套源端、在线、基于CPU-内存的重复数据删除备份（重复数据删除设备并非物理机而是虚拟机），所有配置均采用默认配置、不作定制优化。
首次备份耗时35 min，消重效率87%，消重时CPU消耗上涨5%，内存占用小于200MB，网络负载约3 MB/S左右。
第二次备份耗时19min，消重效率98%，CPU、内存消耗与首次备份差不多，但网络负载明显下降，偶尔占用1~2MB/S。
（@Li Fei 某保险公司系统架构师）二、主流的几种重复数据删除技术重复数据删除已经不是一个新的话题了，如今各个厂商的存储或备份产品都有这项功能。
自动精简配置(Thin Provisioning)
HDS：自动精简配置不是“万能药”发表时间：2008-4-11 IT168存储频道来源：IT168关键字：自动精简配置存储HDS信息化应用调查在线投稿加入收藏发表评论好文推荐打印文本自动精简配置（Thin Provisioning）是一项对存储资源的自动分配和利用，以避免磁盘空间被无限制索取的技术。
可以根据该应用或者该用户的容量需求现状，动态并且实时地改变存储容量资源的划分，因此能更加充分的利用磁盘阵列的有效存储空间，降低用户购买存储阵列的容量需求，大量降低用户在购置存储空间方面的成本。
自动精简配置（Thin Provisioning）和重复数据删除核心技术解读2009-3-3 来源：至顶网我要评论分享到：博客引用投稿打印大 | 中 | 小导读：在当前严峻的金融危机逐渐影响实体经济的情况下，企业面临存储扩容需求时不得不精打细算，为了降低最终拥有成本(TCO)，众企业将目光集聚到重复数据删除技术（De-duplication）与自动精简配置(Thin Provisioning)。
关键词：自动精简配置重复数据删除Thin Provisioning在当前日益汹涌的金融危机逐渐影响实体经济的情况下，企业面临存储扩容需求时不得不精打细算，为了降低最终拥有成本(TCO)，除了减少初次采购成本，也希望尽可能减少企业今后的运营维护成本。
重复数据删除（De-duplication）技术作为时下最热门的存储优化技术，能显著降低存储设备物理介质消耗，并减少数据中心对空调，空间，和灾备的消耗，还可以与本文涉及的自动精简技术无缝配合，极大降低存储系统的维护管理成本，显著提高企业存储系统的利用率，实为抵御当前经济危机的又一利器。
首先介绍存储系统的自动精简配置(Thin Provisioning)技术。
自动精简配置技术扩展了存储管理功能，虽然实际分配的物理容量小，但可以为操作系统提供超大容量的虚拟存储空间。
随着应用写入的数据越来越多，实际存储空间也可以及时扩展，而无须手动扩展。
基于声学指纹的海量MP3文件近似去重方法
基于声学指纹的海量MP3文件近似去重方法赵晓永;杨扬;王宁【摘要】Song re-uploading had been shared wastes network bandwidth and storage,which needs to use data de-duplicationtechnology.However,the current approach to de-duplication based file bit-feature does not recognize the same song after signal processing or compression.Aiming at this problem,this paper proposes a near de-duplication method of massive MP3 files based on acoustic fingerprint.It combines the certainty of message digest with the robustness of the acoustic fingerprint,after Bloom Filter(BF) de-duplicate data based on the message digest,then reduces acoustic fingerprint for the secondary near de-duplication based on the dimensionality.It ensures efficient at the same time,greatly improves the de-duplication ratio.Experimental results show that this method can improve the de-duplication rate by one time than Content-defined Chunking(CDC) method,and has good extensibility.%在互联网中重复上传他人已经分享的歌曲会消耗网络带宽,浪费存储空间,但目前的重复数据删除方法主要基于文件的二进制特征,无法识别经过信号处理或压缩后的歌曲.针对该问题,提出一种基于声学指纹的海量MP3文件近似去重方法.结合文件消息摘要的确定性与声学指纹的鲁棒性,在采用布隆过滤器对文件消息摘要一次去重的基础上,根据降维后的声学指纹值进行二次近似去重,保证高效的同时提高去重率.实验结果表明,与可变分块检测方法相比,该方法的去重率可提高1倍以上,扩展性较好.【期刊名称】《计算机工程》【年(卷),期】2013(039)007【总页数】4页(P73-75,82)【关键词】声学指纹;重复数据删除;近似去重;布隆过滤器;海量数据【作者】赵晓永;杨扬;王宁【作者单位】北京科技大学计算机与通信工程学院,北京100083;北京科技大学计算机与通信工程学院,北京100083;北京科技大学计算机与通信工程学院,北京100083【正文语种】中文【中图分类】TP3111 概述随着Web2.0和社交网络服务(Social Network Service,SNS)的快速发展，提供用户音乐分享服务的音乐SNS社区已成为当前热门的领域之一。
数据重删算法
数据重删算法
数据重删算法主要用于消除重复数据，以节省存储空间和网络带宽。
这种算法主要分为两种：源端去重和宿端去重。
1. 源端去重：在客户端计算待传输数据的指纹，并通过与服务端进行指纹比对来发现和消除重复内容，然后仅向服务端发送非重复数据内容。
这种方式可以节约网络带宽和存储资源，但需要消耗客户端的计算资源。
2. 宿端去重：将客户端的数据直接传输到服务端，并在服务端内部检测和消除重复内容。
这种方式不消耗客户端的计算资源，但可能会牺牲数据备份的准确性。
此外，数据重删算法还可以分为Post-Processing和In-line两种技术。
1. Post-Processing技术：先备份所有数据，然后再在第二时间做重复数据删除工作。
这种技术可能更加安全、可靠、准确，但会牺牲备份时间和备份效率。
2. In-line技术：在备份的过程中就开始做重复数据删除工作。
这种方式可以大大提高备份效率、缩短备份时间，但可能会牺牲数据备份的准确性，同时对重复数据删除算法的准确性、备份系统的高性能都有着很高的要求。
以上内容仅供参考，建议查阅专业书籍或咨询专业人士以获取更全面准确的信息。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
重复数据删除(De-duplication)技术研究文章地直址：/liuaigui/article/details/58290831、Dedupe概述De-duplication，即重复数据删除，它是一种目前主流且非常热门的存储技术，可对存储容量进行有效优化。
它通过删除数据集中重复的数据，只保留其中一份，从而消除冗余数据。
如下图所示。
这种技术可以很大程度上减少对物理存储空间的需求，从而满足日益增长的数据存储需求。
Dedupe技术可以带许多实际的利益，主要包括以下诸多方面：(1) 满足ROI(投资回报率，Return On Investment)/TCO(总持有成本，Total Cost of Ownership)需求；(2) 可以有效控制数据的急剧增长；(3) 增加有效存储空间，提高存储效率；(4) 节省存储总成本和管理成本；(5) 节省数据传输的网络带宽；(6) 节省空间、电力供应、冷却等运维成本。
Dedupe技术目前大量应用于数据备份与归档系统，因为对数据进行多次备份后，存在大量重复数据，非常适合这种技术。
事实上，dedupe技术可以用于很多场合，包括在线数据、近线数据、离线数据存储系统，可以在文件系统、卷管理器、NAS、SAN中实施。
Dedupe也可以用于数据容灾、数据传输与同步，作为一种数据压缩技术可用于数据打包。
Dedupe技术可以帮助众多应用降低数据存储量，节省网络带宽，提高存储效率、减小备份窗口，节省成本。
Dedupe的衡量维度主要有两个，即重复数据删除率(deduplocation ratios)和性能。
Dedupe性能取决于具体实现技术，而重复数据删除率则由数据自身的特征和应用模式所决定，影响因素如下表[2]所示。
目前各存储厂商公布的重复数据删除率从20:1到500:1不等。
2、Dedupe实现要点研发或应用Dedupe技术时应该考虑各种因素，因为这些因素会直接影响其性能和效果。
(1) What：对何种数据进行消重？对时间数据还是空间数据进行消重，对全局数据还是局部数据进行消重？这是首先需要考虑的因素，这直接决定着Dedupe实现技术和数据消重率。
随时间变化的数据，如周期性的备份、归档数据，比空间数据具有更高的消重率，Dedupe 技术在备份归档领域中被广泛应用。
不难想象，全局范围内的数据重复率比局部范围数据要高，会获得更高的数据消重率。
(2) When：何时进行消重？数据消重时机分为两种情形：在线消重和离线消重。
采用在线消重模式，数据写入存储系统同时执行消重，因此实际传输或写入的数据量较少，适合通过LAN或WAN进行数据处理的存储系统，如网络备份归档和异地容灾系统。
由于它需要实时进行文件切分、数据指纹计算、Hash查找，对系统资料消耗大。
离线消重模式，先将数据写入存储系统，然后利用适当的时间再进行消重处理。
这种模式与前面一种刚好相反，它对系统资料消耗少，但写入了包含重复的数据，需要更多的额外存储空间来预先存储消重前数据。
这种模式适合直连存储DAS和存储区域网络SAN存储架构，数据传输不占用网络带宽。
另外，离线消重模式需要保证有足够的时间窗口来进行数据去重操作。
总之，在何时进行消重，要根据实际存储应用场景来确定。
(3) Where：在何处进行消重？数据消重可以在源端(Source)或者目标端 (Target)进行。
源端消重在数据源进行，传输的是已经消重后的数据，能够节省网络带宽，但会占用大量源端系统资源。
目标端消重发生在目标端，数据在传输到目标端再进行消重，它不会占用源端系统资源，但占用大量网络带宽。
目标端消重的优势在于它对应用程序透明，并具有良好的互操作性，不需要使用专门的 API，现有应用软件不用作任何修改即可直接应用。
(4) How：如何进行消重？重复数据删除技术包含许多技术实现细节，包括文件如何进行切分？数据块指纹如何计算？如何进行数据块检索？采用相同数据检测还是采用相似数据检测和差异编码技术？数据内容是否可以感知，是否需要对内容进行解析？这些都是 Dedupe具体实现息息相关。
本文主要研究相同数据检测技术，基于二进制文件进行消重处理，具有更广泛的适用性。
3、Dedupe关键技术存储系统的重复数据删除过程一般是这样的：首先将数据文件分割成一组数据块，为每个数据块计算指纹，然后以指纹为关键字进行Hash查找，匹配则表示该数据块为重复数据块，仅存储数据块索引号，否则则表示该数据块是一个新的唯一块，对数据块进行存储并创建相关元信息。
这样，一个物理文件在存储系统就对应一个逻辑表示，由一组FP组成的元数据。
当进行读取文件时，先读取逻辑文件，然后根据FP序列，从存储系统中取出相应数据块，还原物理文件副本。
从如上过程中可以看出，Dedupe的关键技术主要包括文件数据块切分、数据块指纹计算和数据块检索。
(1) 文件数据块切分Dedupe按照消重的粒度可以分为文件级和数据块级。
文件级的dedupe技术也称为单一实例存储(SIS, Single Instance Store)，数据块级的重复数据删除其消重粒度更小，可以达到4-24KB之间。
显然，数据块级的可以提供更高的数据消重率，因此目前主流的 dedupe产品都是数据块级的。
数据分块算法主要有三种，即定长切分(fixed-size partition)、CDC切分(content-defined chunking)和滑动块(sliding block)切分。
定长分块算法采用预先义好的块大小对文件进行切分，并进行弱校验值和md5强校验值。
弱校验值主要是为了提升差异编码的性能，先计算弱校验值并进行hash查找，如果发现则计算md5强校验值并作进一步hash查找。
由于弱校验值计算量要比md5小很多，因此可以有效提高编码性能。
定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。
Deduputil中FSP分块算法代码如下。
1./*2.* fixed-sized file chunking3.*/4.static int file_chunk_fsp(int fd, int fd_ldata, int fd_bdata, unsigned int *pos, unsigned int *block_num,5.block_id_t **metadata, hashtable *htable, char *last_block_buf, unsigned int *last_block_len)6.{7.int ret = 0;8.unsigned int rwsize;9.unsigned char md5_checksum[16 + 1] = {0};10. char *buf = NULL;11.12. buf = (char *)malloc(g_block_size);13. if (buf == NULL)14. {15. perror("malloc in file_chunk_fsp");16. return errno;17. }18.19. while (rwsize = read(fd, buf, g_block_size))20. {21. /* if the last block */22. if (rwsize != g_block_size)23. break;24.25. /* calculate md5 */26. md5(buf, rwsize, md5_checksum);27. if (0 != (ret = dedup_regfile_block_process(buf, rwsize, md5_checksum, fd_ldata,28. fd_bdata, pos, block_num, metadata,htable)))29. {30. perror("dedup_regfile_block_process infile_chunk_fsp");31. goto _FILE_CHUNK_FSP_EXIT;32. }33. }34. *last_block_len = (rwsize > 0) ? rwsize : 0;35. if ((*last_block_len)) memcpy(last_block_buf, buf,*last_block_len);36.37._FILE_CHUNK_FSP_EXIT:38. if (buf) free(buf);39. return ret;40.}CDC(content-defined chunking)算法是一种变长分块算法，它应用数据指纹(如Rabin指纹)将文件分割成长度大小不等的分块策略。
与定长分块算法不同，它是基于文件内容进行数据块切分的，因此数据块大小是可变化的。
算法执行过程中，CDC使用一个固定大小(如48字节)的滑动窗口对文件数据计算数据指纹。
如果指纹满足某个条件，如当它的值模特定的整数等于预先设定的数时，则把窗口位置作为块的边界。
CDC算法可能会出现病态现象，即指纹条件不能满足，块边界不能确定，导致数据块过大。
实现中可以对数据块的大小进行限定，设定上下限，解决这种问题。
CDC算法对文件内容变化不敏感，插入或删除数据只会影响到检少的数据块，其余数据块不受影响。
CDC算法也是有缺陷的，数据块大小的确定比较困难，粒度太细则开销太大，粒度过粗则dedup效果不佳。
如何两者之间权衡折衷，这是一个难点。
Deduputil中CDC分块算法代码如下。
1./*2.* content-defined chunking:3.* 1. BLOCK_MIN_SIZE <= block_size <= BLOCK_MAX_SIZE4.* 2. hash(block) % d == r5.*/6.static int file_chunk_cdc(int fd, int fd_ldata, int fd_bdata, unsigned int *pos, unsigned int *block_num,7.block_id_t **metadata, hashtable *htable, char *last_block_buf, unsigned int *last_block_len)8.{9.char buf[BUF_MAX_SIZE] = {0};10. char block_buf[BLOCK_MAX_SIZE] = {0};11. char win_buf[BLOCK_WIN_SIZE + 1] = {0};12. char adler_pre_char;13. unsigned char md5_checksum[16 + 1] = {0};14. unsigned int bpos = 0;15. unsigned int rwsize = 0;16. unsigned int exp_rwsize = BUF_MAX_SIZE;17. unsigned int head, tail;18. unsigned int block_sz = 0, old_block_sz = 0;19. unsigned int hkey = 0;20. int ret = 0;21.22. while(rwsize = read(fd, buf + bpos, exp_rwsize))23. {24. /* last chunk */25. if ((rwsize + bpos + block_sz) < BLOCK_MIN_SIZE)26. break;27.28. head = 0;29. tail = bpos + rwsize;30. /* avoid unnecessary computation and comparsion */31. if (block_sz < (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE))32. {33. old_block_sz = block_sz;34. block_sz = ((block_sz + tail - head) > (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE)) ?35. BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : block_sz + tail -head;36. memcpy(block_buf + old_block_sz, buf+ head, block_sz - old_block_sz);37. head += (block_sz - old_block_sz);38. }39.40. while ((head + BLOCK_WIN_SIZE) <= tail)41. {42. memcpy(win_buf, buf + head, BLOCK_WIN_SIZE);43. /*44. * Firstly, i think rabinhash isthe best. However, it's performance is very bad.45. * After some testing, i found ELF_hash is better both on performance and dedup rate.46. * So, EFL_hash is default. Now,adler_hash as default.47. */48. if (g_rolling_hash)49. {50. hkey = (block_sz == (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE)) ? adler32_checksum(win_buf, BL OCK_WIN_SIZE) :51. adler32_rolling_checksum(hkey, BLOCK_WIN_SIZE, adler_pre_char, buf[head+BLOCK_WIN_S IZE-1]);52. }53. else54. hkey = g_cdc_chunk_hashfunc(win_buf);55.56. /* get a normal chunk */57. if ((hkey % g_block_size) == CHUNK_CDC_R)58. {59. memcpy(block_buf + block_sz,buf + head, BLOCK_WIN_SIZE);60. head += BLOCK_WIN_SIZE;61. block_sz += BLOCK_WIN_SIZE;62. if (block_sz >= BLOCK_MIN_SIZE)63. {64. md5(block_buf, block_sz, md5_checksum);65. if (0 != (ret = dedup_regfile_block_process(block_buf, block_sz,66. md5_checksum,fd_ldata, fd_bdata, pos, block_num, metadata, htable)))67. {68. perror("dedup_reggile_block_process in file_chunk_cdc");69. goto _FILE_CHUNK_CDC_EXIT;70. }71. block_sz = 0;72. }73. }74. else75. {76. block_buf[block_sz++] = buf[head++];77. /* get an abnormal chunk */78. if (block_sz >= BLOCK_MAX_SIZE)79. {80. md5(block_buf, block_sz, md5_checksum);81. if (0 != (ret = dedup_regfile_block_process(block_buf, block_sz,82. md5_checksum,fd_ldata, fd_bdata, pos, block_num, metadata, htable)))83. {84. perror("dedup_reggile_block_process in file_chunk_cdc");85. goto _FILE_CHUNK_CDC_EXIT;86. }87. block_sz = 0;88. }89. }90.91. /* avoid unnecessary computation and comparsion */92. if (block_sz == 0)93. {94. block_sz = ((tail - head)> (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE)) ?95. BLOCK_MIN_SIZE - BLOCK_WIN_SIZE : tail - head;96. memcpy(block_buf, buf + head, block_sz);97. head = ((tail - head) > (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE)) ?98. head + (BLOCK_MIN_SIZE - BLOCK_WIN_SIZE) : tail;99. }100.101.adler_pre_char = buf[head -1];102.}103.104./* read expected data from file to full up buf */105.bpos = tail - head;106.exp_rwsize = BUF_MAX_SIZE - bpos; 107.adler_pre_char = buf[head -1];108.memmove(buf, buf + head, bpos); 109.}110./* last chunk */111.*last_block_len = ((rwsize + bpos + block_sz ) >= 0) ? rwsize + bpos + block_sz : 0;112.if (*last_block_len > 0)113.{114.memcpy(last_block_buf, block_buf, block_ sz);115.memcpy(last_block_buf + block_sz, buf, rwsize + bpos);116.}117.118._FILE_CHUNK_CDC_EXIT:119.return ret;120.}滑动块(sliding block)算法结合了定长切分和CDC切分的优点，块大小固定。