云存储中快速安全的数据去重方法

第 1 章 绪论

1.1 研究背景

网络信息技术等计算机新兴科技不但促进了国民经济各个领域的蓬勃发展，同时也推进了相应软硬件系统全面步入信息化、智能化时代。随着这些技术逐渐融入到社会生活中的各个角落里，大数据时代在全球数字化浪潮带来的海量信息数据逐渐推动下也越来越清晰地步入全球的视野。据 IDC 研究指出[1]，2006 年个人用户数据已经进入 TB 级的时代，从 2006 年到 2010 年，数据每年以 57%的速度持续增长，2011 年，全球的数据量已经进入以 ZB 为单位的时代，全世界使用的数据总量超过1.8ZB。IDC调查称，2020年全球数据总量甚至将会超过40ZB，大数据时代越来越清晰，同时其数据种类多(Variety)，数据量大(Volume)，价值密度低(Value)，处理速度快(Velocity)的四大特性也逐渐被大家所熟知[2]。

...............

1.2 课题研究内容

当前各企业厂商和研究机构为了能节省磁盘等硬件成本开销同时又能提高存储空间的利用率提出了重复数据删除技术的概念。重复删除技术实质上是一种有效的数据压缩技术，用来删除存储系统中存在的大量冗余数据，以降低磁盘 I/O开销，提高系统资源利用率。目前国内外很多研究组织和企业都在对其进行研究，并且取得了非常明显的成果，LBFS[7]是一种由麻省理工学院开发的网络文件系统，其目标在于降低数据传输对带宽的占用，在传输之前判断数据块是否已经在于目标服务器上，如果已经存在则无需重复发送数据块。此外，LBFS 使用 SHA1 值的前 64 位作数据块指纹索引，是有一定指纹冲突的可能；Venti 系统[8]是美国贝尔实验室设计和研发的用于数据归档的网络存储系统，但它绑定到 Plan9 操作系统上，因此不能用于诸如 Linux，Windows 等系统环境中，Venti 以固定大小的数据块作为存储基本单位，并且计算每个数据块的 SHA1 值作为块数据指纹，最后利用速度比较块的哈希运算检测判断重复数据。

...............

第 2 章 重复数据检测方法

2.1 重复数据去重原理

重复数据删除（DataDeduplication）是一种单一对象存储或智能数据压缩技术，它利用哈希值来判断内容相同的数据，对那些相同内容的数据只存储其唯一一份对象，对这个对象的其他重复数据使用指向唯一副本的指针来代替[8]，通过此种方式消除重复冗余的数据、提高存储空间使用率，图 2.1 具体展示了这一原理。而学术界给出了重复数据删除技术的精确定义，基于数据自身冗余度来检测数据流中存在的相同数据，然后只存储和传输唯一的数据对象，最终使用指向唯一数据对象副本的指针替换其中的重复副本[9]。

...............

2.2 重复数据检测方法

对于重复数据检测技术来讲，按照不同的标准，可以分为不同的处理方式。最为广泛的分类方式是以检测的粒度大小划分，再有是根据去重操作发生的时机来划分用于评价重复数据删除技术优劣的指标有两个，一个是重复数据删除率，另外一个是执行性能。想要取得相对更高的重复数据删除率则需要以牺牲一定执行性能为代价，操作的粒度越精细，检测的重复数据就越多，能节省的存储空间就越大。

...............

第 3 章 数据指纹计算................14

3.1 单向散列函数..................14

3.2 MD5 哈希函数................16

第 4 章 指纹索引策略................27

4.1 数据去重的指纹索引研究................27

4.2 基于局部性的索引技术.................28

第 5 章 基于 SHA3 算法和两级索引的双端去重检测框架.................36

5.1 TLDM 方法原理 .................36

5.2 TLDM 架构 ................36

第 6 章 TLDM 在 Hadoop 平台中的应用

6.1 实验环境和数据集

本文使用三台机器搭建的 Hadoop 集群环境，每个节点的操作系统都是Ubuntu12.04，三个节点中有一个同时运行 NameNode 和 DataNode 进程，其余两个节点只存在 DataNode 进程，每台机器的配置如表 6.1 所示。本文采用 Rabin 指纹算法对每一个待处理的文件进行按内容分块，且设定数据块的平均大小为 4KB。除此之外，设定数据块大小最小为 2K，最大为 64KB，。对于重复的文件无需再次上传，而在对非重复 SSH 文件进行分块之前，先确定文件的大小，对于小于 2K 的小文件不做分块处理，而是将整个文件作为一个块处理，这样可以减少对这些小文件进行数据分块过程的时间开销。而对于文件指纹以及数据块指纹的计算都采用 SHA3 哈希算法。

...............

6.2 实验结果与分析

在比较数据集所需的存储空间时，使用三种方法：无去重措施、在线 EB 检测，本文的客户-服务端双重检测，分别用 No-Dedup、EB-Dedup 和 CS-Dedup 表示。图 6.2 和图 6.3 所示为采用不同方法时，Dataset I 和 Dataset II 所占的存储空间比较。可以看出：采用任意一种去重处理后，数据集所占的存储空间明显减少，尤其在数据量增大时，存储空间利用率大大提高；而且 CS-Dedup 相比EB-Dedup 能够节省更多的存储空间，因为 CS-Dedup 相当于在 EB-Dedup 之上又做了一次服务端的全局查重。不过图 6.3 中 CS-Dedup 相比 EB-Dedup 去重率提高不大，其原因是数据集中大多数重复数据通过 EB 即可得到确认，即能在客户端检测到大部分的重复数据，，只有少数副本需要通过服务端的全局确认。

...............

结论

无论是在个人 PC 机、备份、归档系统还是在分布式文件系统里，都存在一定量的数据是重复存储的，而加之当前信息飞速发展带来数据规模的急剧增大，如何充分利用系统的存储资源，去除这些重复数据愈加显得重要和迫切。本文的目的是通过研究国内外重复数据去重领域研究现状，结合以往相关经典算法并提出一种扩展性强、去重率高的客户-服务端双端去重框架-TLDM。首先，本文分析了当前大数据环境下给数据存储带来的一系列问题，重点讲到了云存储环境重复数据冗余存储的客观现状以及因此给企业和个人带来的各种问题。其中阐述了国内外重复数据删除技术的主要方法，包括基于内容识别的传统去重方法和当代基于块粒度的数据去重方法。并在后续内容中对基于去重粒度的文件级、静态分块和按内容分块方法进行了重点叙述，这其中又对基于文件内容的分块技术进行更加细致的讲解，该讲解中涉及到了两项重要技术，一个是滑动窗口的概念，另一个是 Rabin 指纹分块方法。

参考文献（略）