数据重复删除技术的研究与应用
摘 要
随着信息数字化的快速发展与生产力的突飞猛进，当今企业对信息的存储需求 也在飞速增长。尽管存储设备的销售价格在不断地下降，但远远赶不上企业内部产 生和需要保存数据的攀升速度。重复数据删除技术能够删除重复的数据，实现数据 的唯一实例存储，将有望解决该问题。该技术一般应用在备份、归档等集中式数据 存储的系统中，能有效地节省存储空间和网络的传输带宽。
目前，对文件或数据流中重复数据的查找效率始终是重复数据删除技术应用的 瓶颈，为此重点对提高重复数据的查找效率进行了研究，并将重复数据删除技术融 合到数据备份领域实现了高效的、稳定的数据容灾备份系统，它可以为数据提供安 全的存储服务。该系统运用了多项技术来提高数据的备份和恢复性能：元数据的多 级查询机制、数据缓存机制和多线程技术。元数据的多级查询机制通过使用全局 UBRS系统、二级索引缓存和磁盘哈希表来提高对重复数据的查找速度；数据缓 存机制则通过对数据块的内存缓冲，可以避免对磁盘频繁的 I/O 操作；多线程技术 可以提高系统的并发处理能力，从而在整体上提升系统的性能。
测试表明，提出的重复数据删除技术能有效地提高备份和恢复性能，同时，能 极大的减少冗余数据的存储，节省存储空间，提高备份容灾系统的存储效率。
关键词：重复数据删除，哈希算法，备份，元数据组织
1 绪论
1.1 课题背景和意义
全球信息化程度的不断提高正在加速产生海量的高价值数据，而这些指数级增 长的高价值数据给企业的 IT 部门提出了很多挑战。虽然目前存储设备的销售价格在 不断地下降，但是远远赶不上企业内部产生和需要保存的数据的攀升速度。据 IDC
（Internet Data Center）统计，2007 年全球产生了 281EB（1EB＝260Byte）的数据， 并且大约以每年 30%至 50%的速度持续增长，其中有 35%的数据源自于企业和由非结 构化的内容组成,而这些数据中含有大量的重复数据。例如：一个办公文档的流转和 版本的修订比较普遍，一个文档可能拥有多个版本，也可能拷贝给多个人，这样就 会有大量的重复数据；另外，同一文件以附件的方式群发给多个人，这也会导致大 量的重复数据，尤其在文件比较大时，这些重复的数据所占用的存储空间将十分可 观。如果在数据备份和归档时将这些重复的数据删除，数据压缩比通常可达到 20：1 甚至更高[1]。
普通的数据压缩技术是对数据的重新编码来消除单个文件内的重复数据来优化 存储容量；而重复数据删除技术是一种非常高级的数据压缩方式，它是通过算法消 除文件之间的重复数据，与普通的数据压缩技术相比，在节省存储空间方面更加有 效。该技术可以在很大程度上减少备份数据的数量，使得基于磁盘的数据备份和归 档成为可能，目前已被广泛应用到备份和归档存储领域[2]。然而，建立完善的备份和 归档系统必须解决以下几个方面令人棘手的问题[3]：
1．全球数字化、信息化的浪潮以及数据的“爆炸式”增长所导致的直接问题是 存储空间的不足。这样，需要购买更多存储介质的成本、存储介质的使用和维护成 本以及数据信息的管理成本等都会迅速增长。
2．对于文件或数据流的网络备份和归档，更多的数据要求网络具有更高网络带 宽。由于网络带宽的限制，传输时间的延长可能会降低系统的运行效率，甚至无法 即时完成数据的网络传送。
3．数据的大量增长也给系统处理能力（如 CPU、I/O 总线等）带来巨大压力， 而系统的处理能力一般较难扩展，通常只能通过硬件的整体升级来完成。如果不通 过技术手段有效地平抑数据量增长对系统处理能力的压力，系统可靠性将面临频繁
硬件升级的严峻挑战，对系统的投资也不能得到充分的利用。 为了解决上述问题，重复数据删除技术是比较理想的解决方案。一方面重复数
据删除技术能大幅度减少所需存储的数据量（只需要备份经过修改的数据），降低数 据对存储空间的需求，使得在存储容量固定的情况下，可以利用有限的存储空间在 更长的时间内存储更多重要的数据；另一方面重复数据删除技术可以避免重复数据 的多次网络传送，使得通过网络传输的数据量呈几何级别递减，进而降低能量消耗 和网络成本，并为数据的复制节省大量的网络带宽[4]；同时，也能适当缓解系统处理 能力上的压力。
在今天全球数据量急剧增长的大环境下，在企业业务应用需求和法律法规遵从 的要求下，在全球都在提倡绿色节能环保的大背景下，重复数据删除技术已经成为 了越来越多企业的选择；重复数据删除技术通过减少存储的数据量，改变了数据保 护的方式，同时提升了磁盘备份的经济性，已经逐步被业界公认为备份技术的下一 代发展步骤，是数据中心的“必备”技术[5]。正如某些分析家所说，重复数据删除技 术的产生将改写存储行业的经济规则。
因此，使用重复数据删除技术开发一种安全的、稳定的、高效的备份和归档系 统，无论是在节约存储空间方面，还是在节省网络带宽方面，甚至在能耗节省（实 现“绿色”数据中心）方面都有突出的实际意义。
1.2 重复数据删除技术
重复数据删除也称文件间的数据压缩（Inter-file Data Compression）或智能 压缩（Intelligent Compression）或单实例存储（Single-instancing Storage）[6]， 通常用于基于磁盘的存储备份系统，旨在减少存储系统中所使用的存储容量，是存 储备份领域的一项热门技术。ESG（Enterprise Strategy Group）定义重复数据删 除为删除或消除冗余的文件、数据块或字节，确保在存储系统中只有唯一的存储实 例的过程[1]。当遇到重复的数据时，不是进行重复数据的存储，取而代之，增加一个 指向唯一（第一份）数据的指针。重复数据删除通过有效地减少后端存储设备中冗 余的数据，解决了存储容量紧张的问题。
重复数据删除技术是利用文件之间和文件内部的相同或相似性，处理的粒度可 以是文件、数据块、字节甚至位，处理粒度越细，删除冗余数据就越多，存储容量
减少也就越大，但同时系统也越复杂，处理消耗的计算资源也越多。目前，文件之 间和文件内部的重复数据检测都普遍使用 Hash 算法：先对数据进行哈希，从而得到 一个唯一的哈希值，通过哈希值的比对来确定是否有重复的数据。为了很好地完成 对重复数据的检测，哈希函数的选取尤为重要，其中以 MD5[7] （Message Digest Algorithm 5,生成 128 位的哈希值）和 SHA-1[8]（Secure Hash Algorithm,生成 160 位的哈希值）最为流行，两者的抗冲突性都比较好，能很好地满足对重复数据进行 检测的要求。加州大学研究表明，在普通硬件条件下，SHA-1 的计算速度是 83MB/S， 而 MD5 的计算速度是 227MB/S[9]，应根据实际的应用环境选取适当的哈希函数，在数 据的安全可靠性和系统运行性能方面找到一个很好的平衡点。
