一种基于Hadoop平台的分布式重复数据删除系统和方法

摘要

本发明公开了一种基于Hadoop平台的分布式重复数据删除系统和方法。该系统包括客户端、主节点和工作节点，通过Hadoop平台的MapReduce并行编程框架实现分布式并行重复数据删除处理，实现方法包括客户端向主节点发送文件，主节点完成文件分片、数据分配以及构建文件元数据表，各个工作节点对数据分片按细粒度进行分块，计算细粒度数据块的指纹值，并在数据库Hbase的索引中进行查询比对，将新数据块存储在分布式文件系统HDFS中，再将索引信息反馈给主节点。该系统和方法能在保证高重删率的同时，具有高吞吐率和良好的可扩展性。

说明书

技术领域

本发明涉及计算机数据存储管理领域，特别是涉及一种基于 Hadoop平台的分布式重复数据删除系统和方法。

背景技术

随着信息技术高速发展，云计算、物联网、信息栅格以及各种社 交平台等新兴技术不断涌现，数据类型逐渐多样化，数据量急剧增长。 面对持续膨胀的海量数据，存储系统容量以及存储数据管理逐步成为 富有挑战性的问题。一方面，数据中心需要增加大量的存储设备以满 足海量数据存储需求，另一方面，存储设备的增加会带来企业采购、 管理、电力等成本投入。然而，数据中心的数据存储普遍具有高冗余 特点，尤其是备份存储系统和基于虚拟机的主存储系统。如何缩减冗 余数据，提升存储空间的有效利用率，进而减少企业维护管理开销， 成为目前热门研究领域。

在现有技术中，通过重复数据删除(简称重删)技术可以检测并 消除内容重复的数据，极大缩减数据存储容量，优化存储空间利用率， 并可减少数据传输的网络开销，节省网络带宽。与传统数据压缩技术 相比，重复数据删除技术不仅可以消除文件内的数据冗余，还能消除 共享数据集内文件之间的数据冗余，在数据备份、容灾以及归档存储 等方面应用广泛。

当采用单服务器进行重复数据删除时，存在处理能力有限，速率 较低，不能满足大规模备份数据管理的需求。为此，现有技术中开始 采用分布式重复数据删除方法，主要是通过建立分布式重复数据删除 系统实现分布式并行数据消重，能够有效提升重复数据删除效率，但 同时增加了系统复杂性，带来数据分块、路由策略选择、系统扩展性、 负载均衡等问题。

具体而言，现有技术中的分布式重复数据删除方法主要存在以下 问题：一是重复数据删除的效率问题，例如当使用分布式的服务器并 行处理一个文件中的重复数据时，需要根据服务器的数量及文件大小 合理确定对该文件的分割大小，这是因为对文件分割的数据片的大小 与重删率密切相关，若被分割的数据片的粒度越细，检测出的重复数 据块越多，但对重复数据块的处理时间也会相应增加，因此，需要在 重删率和处理时间上进行权衡，提高重复数据删除的并行处理效率； 二是重复数据删除的整体性问题，这是因为各服务器并行处理一个文 件的数据片时，具有独立性，分别独立处理数据片中的重复数据块， 若这些服务器之间没有协调机制，则会存在重删效果不充分的问题， 例如在两个服务器上存在相同的重复数据块，若分别处理后不再协 调，则该重复数据块在两个服务器上均有处理记录信息并分别存储在 这两个服务器上，但对于整体而言，只需存储一次该重复数据块即可， 造成了数据重删在服务器之间仍留有冗余的问题；三是重复数据删除 的可靠性问题，为达到整体性的重删效果，通过多服务器并行重删处 理后，各服务器之间增加了依赖关系，若仅有对处理记录和经过重删 处理后数据的一次性存储，而没有进行必要的副本备份，则任何数据 损失都会造成多个文件损坏，在可靠性方面，系统面临着很大的潜在 风险。

发明内容

本发明主要解决的技术问题是提供一种基于Hadoop平台的分布 式重复数据删除系统和方法，解决现有技术中分布式重复数据删除方 法效率不高、各服务器之间因缺乏整体性协调而导致重删效果不充 分、以及可靠性不强等问题。

为解决上述技术问题，本发明采用的一个技术方案是：提供一种 基于Hadoop平台的分布式重复数据删除方法，包括基于Hadoop平 台构建的重删集群，该重删集群包括客户端、主节点和至少两个工作 节点，包括如下步骤：第一步，文件分片，由该客户端指定需要进行 重复数据删除处理的文件提交给该主节点，该主节点将接收的该文件 分成大小均等的粗粒度数据片；第二步，数据片分配，由该主节点通 过Hadoop平台将该粗粒度数据片分配到该各个工作节点；第三步， 数据片分块，各工作节点并行运行Map函数，对所分配的粗粒度数 据片通过定长分块方法或者变长分块方法进一步划分为细粒度数据 块；第四步，计算指纹值，各个工作节点对划分后的细粒度数据块根 据哈希函数计算出该细粒度数据块的指纹值；第五步，块索引查询， 该各个工作节点在已建立的块索引中，查询该细粒度数据块的指纹值 是否存在，若该细粒度数据块的指纹值在该索引中已存在，则不再存 储该细粒度数据块，若该细粒度数据块的指纹值在该索引中不存在， 则将该细粒度数据块存储到HDFS文件系统中，并根据该细粒度数据 块的存储信息在该块索引中添加相应的块索引信息；第六步，文件元 数据表更新，各个该工作节点将所属的该细粒度数据块对应的块索引 信息反馈给该主节点，该主节点将该块索引信息存储到已建立的文件 元数据表中，建立文件全路径到细粒度数据块的映射关系，以支持后 续的文件读操作。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该Hadoop平台以HDFS为底层文件系统，通过MapReduce 并行编程范式在该主节点与各个工作节点之间实现对该重复数据删 除分布式并行处理。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该块索引是通过HBase数据库构建的一个全局块索引，该 全局块索引被各个工作节点所共享。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该文件元数据表存储在该HBase数据库中。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该块索引包括块指纹值、块存储地址、偏移、块大小和重 复次数。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该文件元数据表包括文件全路径和块索引信息。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该粗粒度数据块大小为1Mbyte～256Mbyte，该细粒度数据 块大小为1kbyte～128kbyte。

在本发明基于Hadoop平台的分布式重复数据删除方法的另一个 实施例中，该细粒度数据块的指纹值是通过MD系列或SHA系列的 加密哈希函数计算得到。

本发明还提供了一种基于Hadoop平台的分布式重复数据删除系 统，该分布式重复数据删除系统包括客户端、主节点和至少两个工作 节点构成的集群，该客户端将需要进行重复数据删除处理的文件提交 给该主节点；该主节点将接收到的来自该客户端的文件分成均等的粗 粒度数据片，然后，将该粗粒度数据片分配到各个该工作节点；各个 该工作节点并行运行Map函数，对所分配的粗粒度数据片通过定长 分块方法或者变长分块方法进一步划分为细粒度数据块，再根据哈希 函数计算出该细粒度数据块的指纹值，然后，在已建立的块索引中， 查询该细粒度数据块的指纹值是否存在，若该细粒度数据块的指纹值 在该索引中已存在，则不再存储该细粒度数据块，若该细粒度数据块 的指纹值在该索引中不存在，则将该细粒度数据块存储到HDFS文件 系统中，并根据该细粒度数据块的存储信息在该块索引中添加相应的 块索引信息；各个该工作节点将所属的该细粒度数据块对应的块索引 信息反馈给该主节点，该主节点将该块索引信息存储到已建立的文件 元数据表中，建立文件全路径到细粒度数据块的映射关系，以支持后 续的文件读操作。

在本发明基于Hadoop平台的分布式重复数据删除系统的另一个 实施例中，该Hadoop平台以HDFS为底层文件系统，通过MapReduce 并行编程范式在该主节点与各个工作节点之间实现对该重复数据删 除及存储的分布式并行处理；该块索引是通过HBase数据库构建的一 个全局块索引，该全局块索引被各个工作节点所共享。

本发明的有益效果是：通过本发明提供了一种基于Hadoop平台 的分布式重复数据删除系统和方法，利用MapReduce并行编程框架 进行数据分块与指纹值计算，实现了分布式并行重删处理，提高了并 行重删的效率。通过将块索引存放在非关系型数据库HBase中，有效 解决了块索引的可扩展性问题。重删后的数据使用分布式文件系统 HDFS存储，充分保证了数据的可靠性。本系统具有良好的重删能力 和扩展能力，同时能够自动实现负载均衡和故障恢复。

附图说明

图1是根据本发明基于Hadoop平台的分布式重复数据删除方法 一个实施例的分布式重复数据删除系统架构图；

图2是根据本发明基于Hadoop平台的分布式重复数据删除方法 一个实施例的流程图；

图3是根据本发明基于Hadoop平台的分布式重复数据删除方法 一个实施例的块索引组成图；

图4是根据本发明基于Hadoop平台的分布式重复数据删除方法 一个实施例的文件元数据表组成图。

具体实施方式

为了便于理解本发明，下面结合附图和具体实施例，对本发明进 行更详细的说明。附图中给出了本发明的较佳的实施例。但是，本发 明可以以许多不同的形式来实现，并不限于本说明书所描述的实施 例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解 更加透彻全面。

需要说明的是，除非另有定义，本说明书所使用的所有的技术和 科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。 在本发明的说明书中所使用的术语只是为了描述具体的实施例的目 的，不是用于限制本发明。本说明书所使用的术语“和/或”包括一个或 多个相关的所列项目的任意的和所有的组合。

图1显示了本发明基于Hadoop平台的分布式重复数据删除系统 和方法一个实施例的分布式重复数据删除系统架构图。该系统架构包 括若干客户端11、一个主节点12和至少两个工作节点构成的集群， 图1中所示为工作节点1、工作节点2、…、工作节点N，表示有N 个工作节点，N≥2，还包括HDFS文件系统13和HBase数据库14。

该分布式重复数据删除系统的软件平台是Hadoop平台，以下对 Hadoop平台以及HDFS文件系统13和HBase数据库14做一说明。

Hadoop平台是一个由Apache基金会所开发的分布式系统基础架 构，用于海量数据分布式存储和高效并行处理，是当前最流行的分布 式计算平台之一。

其中，HDFS(HadoopDistributedFileSystem)和MapReduce是 Hadoop最主要的两大组件。HDFS作为Hadoop底层文件系统，管理 数据分块、副本存储等，对存储数据进行合理组织。由于Hadoop使 用专门为分布式计算设计的文件系统HDFS，计算的时候只需要将计 算代码推送到各工作节点上，即可在工作节点上完成数据本地化计 算，Hadoop中的集群工作节点也是计算节点。

MapReduce是一个高度抽象的并行编程模型，它将分布式并行编 程抽象为两个原语操作，即map操作和reduce操作，开发人员只需 要简单地实现相应的接口即可，完全不用考虑底层数据流、容错、程 序的并行执行等细节，这种设计无疑大大降低了开发分布式并行程序 的难度。

HBase(HadoopDatabase)是Hadoop平台中应用最广泛的非关 系型数据库，可实现高可靠性、高性能、面向列、可伸缩的分布式存 储系统，利用HBase技术可在廉价PCServer上搭建起大规模结构化 存储集群。HBase在Hadoop平台中运行，需要底层HDFS支持，但 HDFS不支持随机读写，HBase弥补了这一缺陷，这也是HBase比 HDFS效率高的原因之一。HBase具有良好的可扩展性，在系统伸缩 过程中，HBase可以透明地进行数据重分区和迁移，实现负载均衡。

基于以上说明，图1所示的分布式重复数据删除系统是基于 Hadoop平台，利用Hadoop大数据处理平台下的分布式文件系统 HDFS和非关系型数据库HBase两种数据管理模式，实现一种可扩展 分布式重复数据删除存储系统。采用Hadoop平台是由于该平台将自 动并行化、负载均衡和故障管理等很多繁琐的技术细节隐藏起来，极 大地简化了程序员的开发工作。其中，利用Hadoop平台中的 MapReduce并行编程框架实现分布式并行重删处理，工作节点1、工 作节点2、…、工作节点N的文件管理和HBase数据库14均是以HDFS 文件系统13作为底层块管理机制来支持的，在这种Hadoop平台架 构中，由主节点12对各工作节点进行管控，协调各工作节点的任务 处理进度。当需要扩展集群规模时，只需要在主节点12配置文件中 进行注册，便可在线增加工作节点，之后系统自动完成数据平衡。进 一步的，当系统处理数据量超出当前处理能力时，也可以通过增加工 作节点的数量获取更优处理性能。

图1中的HBase数据库14中又进一步包括块索引141和文件元 数据表142，以下将结合具体实施例对块索引141和文件元数据表142 做进一步说明。

图2是根据本发明基于Hadoop平台的分布式重复数据删除方法 一个实施例的流程图，以下结合图1所示重删集群对图2所示各步骤 进行详细说明。

第一步S101，文件分片，由图1中的客户端11指定需要进行重 复数据删除处理的文件，提交给主节点12，主节点12对接收的文件 分成大小均等的粗粒度数据片，如图1中所示的数据片1、数据片 2、…、数据片N。粗粒度数据片一般以1Mbyte～256Mbyte为单位， 优选为64Mbyte。

第二步S102，数据片分配，主节点12通过Hadoop平台将这些 粗粒度数据片分配给集群中的所有各个工作节点，以实现并行重复数 据删除处理。各个工作节点得到的粗粒度数据片数量由客户端11提 供的文件大小和各个工作节点的数量共同决定。Hadoop平台可以很 好地自动平衡各个节点分配的工作负载。优选的，Hadoop平台以 HDFS为底层文件系统，通过MapReduce并行编程范式在所述主节点 与各个工作节点之间实现对所述重复数据删除的分布式并行处理。

第三步S103，数据片分块，各工作节点并行运行Map函数，对 所分配的粗粒度数据片通过定长分块方法或者变长分块方法进一步 划分为细粒度数据块。

定长分块方法是以固定大小的数据内容作为数据块单元来划分 文件，这种方法简单有效，适用于更新操作较少的静态数据集，但对 文件数据的增删高度敏感。

变长分块方法是应用滑动窗口技术基于文件的内容来确定数据 块的分割点，往往通过计算窗口的弱哈希指纹来确定边界。变长分块 方法适合应用于更新频繁的数据集，在减少存储空间的使用上较定长 分块方法更具有优势，但由于其分块过程中需要进行大量的哈希指纹 计算，需要消耗更多的计算资源。

细粒度数据块的一般按照1kbyte～128kbyte大小期望分块，优选 将粗粒度数据片分为期望大小4kbyte的细粒度数据块。选择合适的 分块大小可以有效地平衡重复数据删除处理的存储空间节省量和系 统资源开销。

进一步地，本发明基于Hadoop平台的分布式重复数据删除方法 是基于Hadoop平台通过MapReduce机制实现了重删的并行化处理。 通常情况下，Map函数负责数据的读取和预处理，Reduce函数负责 对Map产生的中间结果进行合并。本发明并未严格按照MapReduce 框架编写，而是省略了Reduce步骤，只通过Map函数完成并行重删 功能，进一步提升了重删速度。除了在主节点完成对文件的粗颗粒数 据分片外，细颗粒数据分块、指纹值计算、块索引查找、细颗粒数据 块存储以及文件元数据表写入等都是在Map函数中并行完成的，Map 函数实现的一个优选实施例如下：

第四步S104，计算指纹值，各个工作节点对划分后的细粒度数 据块根据哈希函数并行计算出所述细粒度数据块的指纹值。

这里，细粒度数据块的指纹值是用来表示该数据块独特性的“数 字指纹”，该指纹值可以通过一定的算法进行计算，无论该数据块的 类型如何、体积多大，都有且只有一个独一无二的指纹值，目的在于 获取该数据块的指纹值后，在重复数据检测时直接通过比较指纹值就 可以验证是否为相同的数据块，而无需再对数据块整体组成逐一比对 来验证是否为重复数据块。

优选的，在本重删集群系统中，通过MD系列或SHA系列两类 方法计算细粒度数据块的指纹值，即实现了MD系列或SHA系列两 类计算指纹的哈希函数。

第五步S105，块索引查询，各个工作节点在已建立的块索引中 查询细粒度数据块的指纹值是否存在，若该细粒度数据块的指纹值在 该索引中已存在，则表明该细粒度数据块为重复数据块，不再存储， 若该细粒度数据块的指纹值在该索引中不存在，则该细粒度数据块是 唯一的，存储到该HDFS文件系统13中，并根据该唯一的细粒度数 据块的存储信息在该块索引中添加相应的块索引信息。

通过图1可以看出，块索引141在HBase数据库14中，表示采 用HBase数据库14存储块索引141，实现块索引的并行查询，并且， 通过HBase数据库14来维护一张全局的块索引141，能够被多个工 作节点共享，达到了并行查询的效果。因此，块索引141是通过HBase 数据库14构建的一个全局块索引，该全局块索引被各个工作节点所 共享。

另外，为避免块索引成为系统扩展瓶颈，通过将块索引141存放 在分布式非关系型HBase数据库14中，同样支持在线添加节点，以 实现线性扩展。

图3是块索引一个优选实施例的组成图。可以看出该块索引包括 四个部分，即：块指纹值、块存储地址、偏移、块大小和重复次数。 其中，块指纹值表示的就是细粒度数据块的指纹值；块存储地址则表 示细粒度数据块的具体存储位置，是采用HDFS文件系统进行打包成 粗粒度容器进行存储管理的；偏移值为该细粒度数据块起始地址离容 器开始地址的偏移量；块大小为该细粒度数据块的大小值；重复次数 表示该细粒度数据块作为重复数据块在一个文件或多个文件中出现 的次数。

第六步S106，文件元数据表更新，各个工作节点将所属的各细 粒度数据块对应的块索引信息反馈给主节点，主节点将各块索引信息 存储到已建立的文件元数据表中，建立文件全路径到细粒度数据块的 映射关系，以支持后续的文件读操作。

通过图1可以看出，文件元数据表142也在HBase数据库14中， 表示采用HBase数据库14存储和维护一张统一的文件元数据表142， 在该表中，一个文件作为一条记录存储。

图4是文件元数据表一个优选实施例的组成图。可以看出该文件 元数据表包括：文件全路径，以及由1号数据块索引信息、2号数据 块索引信息、……、N号数据块索引信息所组成的块索引信息。其中， 文件全路径包含该文件在文件系统中的绝对路径和文件名，各数据块 索引信息则包括该文件的每一个细粒度数据块的指纹值、块存储地 址、偏移、块大小和重复次数等信息。通过建立文件元数据表是为便 于重删后还能够对原文件快速恢复。

基于同一构思，本发明还提供了一种基于Hadoop平台的分布式 重复数据删除系统。

在本发明基于Hadoop平台的分布式重复数据删除系统的一个优 选实施例中，该分布式重复数据删除系统包括客户端、主节点和至少 两个工作节点构成的集群。该客户端将需要进行重复数据删除处理的 文件提交给该主节点；该主节点将接收到的来自该客户端的文件分成 均等的粗粒度数据片，然后，将该粗粒度数据片分配到各个该工作节 点；各个该工作节点并行运行Map函数，对所分配的粗粒度数据片 通过定长分块方法或者变长分块方法进一步划分为细粒度数据块，再 根据哈希函数计算出该细粒度数据块的指纹值，然后，在已建立的块 索引中，查询该细粒度数据块的指纹值是否存在，若该细粒度数据块 的指纹值在该索引中已存在，则不再存储该细粒度数据块，若该细粒 度数据块的指纹值在该索引中不存在，则将该细粒度数据块存储到 HDFS文件系统中，并根据该细粒度数据块的存储信息在该块索引中 添加相应的块索引信息；各个该工作节点将所属的该细粒度数据块对 应的块索引信息反馈给该主节点，该主节点将该块索引信息存储到已 建立的文件元数据表中，建立文件全路径到细粒度数据块的映射关 系，以支持后续的文件读操作。

进一步的，在本发明基于Hadoop平台的分布式重复数据删除系 统的优选实施例中，该Hadoop平台以HDFS为底层文件系统，通过 MapReduce并行编程范式在该主节点与各个工作节点之间实现对该 重复数据删除及存储的分布式并行处理；该块索引是通过HBase数据 库构建的一个全局块索引，该全局块索引被各个工作节点所共享。

通过本发明提供了一种基于Hadoop平台的分布式重复数据删除 系统和方法，利用其中的MapReduce并行编程框架可以进行数据分 片、分块和指纹值计算，实现了分布式并行重删处理，提高了并行重 删的效率。通过将块索引存放在非关系型数据库HBase中，有效解决 了块索引的可扩展性问题。重删后的数据使用分布式文件系统HDFS 进行存储，充分保证了数据的可靠性。本系统具有良好的重删能力和 扩展能力，同时能够自动实现负载均衡和故障恢复。

以上所述仅为本发明的实施例，并非因此限制本发明的专利范 围，凡是利用本发明说明书及附图内容所作的等效结构变换，或直接 或间接运用在其他相关的技术领域，均包括在本发明的专利保护范围 内。