云存储中基于相似性的数据块级数据去重方法

摘要

本发明公开了一种云存储中基于相似性的数据块级数据去重方法，包括：在云存储系统中添加一个指纹索引节点，指纹索引节点用于得到已存储文件的数据块指纹并根据已存储文件的相似性构建由主索引和从索引组成的二级指纹索引，其中，主索引为文件的文件特征指纹与文件相似性集合地址的映射，从索引为文件的数据块指纹与数据块地址、用户ID之间的映射，文件特征指纹为文件的最小数据块指纹；根据指纹索引节点的二级指纹索引对待存储的文件数据块进行去重。本发明利用文件的相似性构建二级指纹索引，然后根据构建的二级指纹索引进行数据块级的数据去重，检索效率更高；基于文件的相似性进行去重，应用范围更广。本发明可广泛应用于云存储领域。

说明书

技术领域

本发明涉及云存储领域，尤其是一种云存储中基于相似性的数据块级数据去重方法。

背景技术

数据去重是一种数据无损的冗余数据缩减技术，是一种数据处理技术。它使得多个相同的数据块在存储系统中只存储一个数据块副本，减少了存储数据所需的资源，节约了成本，已成为存储系统的一种新趋势。在云存储系统中，数据相对更密集，数据量更多，出现相似度高的数据可能性更高，因而对云存储中的数据进行去重更具实际意义，其在提高数据处理效率的同时还能减少存储设备的开销。

数量去重的分类方法主要包括：（1）从数据去重的粒度大小来分，数据去重可以分为字节级数据去重、数据块级数据去重和文件级数据去重；（2）从去重位置的角度来分，数据去重可以分为数据源端数据去重和数据宿端的数据去重；（3）从数据去重的范围来分，数据去重可以分为局部数据去重和全局数据去重。

传统文件系统中的数据去重过程如下：

1.对需要存储的数据进行分块；

2.利用哈希函数对每个数据块生成一个唯一的数据指纹，用以区分不同的数据块；

3.对每个将要存储数据块的数据指纹在系统的数据指纹库中查找，若找到相同的数据指纹，则表明数据块重复；若未找到，则表明数据块不重复。

从上述数据去重过程可以看出，现有的数据去重方法大多数都需要为已存储文件构建一个索引表，来提高对已存储数据的检索速度。这样的方法适用于存储有少量文件的文件系统，但是在存储着海量数据文件的云存储系统中，普通的文件索引无法保障高效的检索，也无法跨用户对数据进行去重。

发明内容

为了解决上述技术问题，本发明的目的是：提供一种高效和应用范围广的云存储中基于相似性的数据块级数据去重方法。

本发明解决其技术问题所采用的技术方案是：

云存储中基于相似性的数据块级数据去重方法，包括：

A、在云存储系统中添加一个指纹索引节点，所述指纹索引节点用于得到已存储文件的数据块指纹并根据已存储文件的相似性构建由主索引和从索引组成的二级指纹索引，其中，主索引为文件的文件特征指纹与文件相似性集合地址的映射，从索引为文件的数据块指纹与数据块地址、用户ID之间的映射，文件特征指纹为文件的最小数据块指纹；

B、根据指纹索引节点的二级指纹索引对待存储的文件数据块进行去重。

进一步，所述云存储系统为基于HDFS的云存储服务系统。

进一步，所述步骤B，其包括：

B1、计算待存储的文件的文件特征指纹和每个数据块指纹；

B2、根据计算的文件特征指纹检索主索引，并根据检索的结果判断待存储的文件是否为新的文件类型，若是，则在执行步骤B3后执行步骤B5，反之，则在执行步骤B4后执行步骤B5；

B3、将待存储的文件分块存入存储系统中，并更新主索引及构建与待存储的文件类型相同的从索引；

B4、根据计算的数据块指纹检索从索引，并根据检索的结果更新从索引；

B5、更新元数据表，所述元数据表包括文件与数据块间的映射关系表以及数据块与数据节点间的映射关系表。

进一步，所述步骤B2，其具体为：

客户端将计算的文件特征指纹与每个数据块指纹发送给主节点，由主节点根据文件特征指纹去主索引中检索，若未检索到与计算的文件特征指纹相同的记录，则表明待存储的文件为新的文件类型，此时先执行步骤B3然后执行步骤B5；若检索到已存在与计算的文件特征指纹相同的记录，则表明云存储系统中已有同类型的文件数据存在，待存储的文件为旧的文件类型，此时先执行步骤B4然后执行步骤B5。

进一步，所述步骤B3，其包括：

为待存储的文件分配存储地址，并根据分配的地址将待存储的文件数据块存储到存储系统的数据节点上；

对主索引进行更新；

构建与待存储的文件类型相同的从索引。

进一步，所述步骤B4，其包括：

B41、主节点根据客户端发送过来的当前数据块指纹去从索引中检索，检索从索引中是否存在与客户端发送过来的当前数据块指纹相同的数据块指纹，若是，则表明当前数据块需要进行去重操作，此时执行步骤B43，反之，则执行步骤B42；

B42、为待存储的文件分配存储地址，并根据分配的地址将待存储的文件数据块存储到存储系统的数据节点上，然后更新从索引；

B43、更新从索引的用户ID，将当前数据块的用户ID添加到从索引中与当前数据块相同的数据块的用户ID上。

进一步，所述已存储文件的数据块指纹及待存储的文件的数据块指纹均采用SHA-1哈希算法计算得到。

本发明的有益效果是：利用文件的相似性构建由主索引和从索引组成的二级指纹索引，然后根据构建的二级指纹索引进行数据块级的数据去重，与传统基于文件的单个索引表的数据去重方法相比，检索效率更高；基于文件的相似性进行去重，不仅可以在一个用户的同类文件中进行数据去重，而且还可以在多个用户的同类文件之间进行数据去重，实现了跨用户的数据去重，应用范围更广。

附图说明

下面结合附图和实施例对本发明作进一步说明。

图1为本发明云存储中基于相似性的数据块级数据去重方法的整体流程图；

图2为本发明步骤B的流程图；

图3为本发明步骤B3的流程图；

图4为本发明步骤B4的流程图；

图5为本发明实施例二云存储系统数据去重的组成模块结构图；

图6为本发明的二级指纹索引结构示意图；

图7为本发明对待存储的文件数据块进行去重的流程图。

具体实施方式

参照图1，云存储中基于相似性的数据块级数据去重方法，包括：

A、在云存储系统中添加一个指纹索引节点，所述指纹索引节点用于得到已存储文件的数据块指纹并根据已存储文件的相似性构建由主索引和从索引组成的二级指纹索引，其中，主索引为文件的文件特征指纹与文件相似性集合地址的映射，从索引为文件的数据块指纹与数据块地址、用户ID之间的映射，文件特征指纹为文件的最小数据块指纹；

B、根据指纹索引节点的二级指纹索引对待存储的文件数据块进行去重。

进一步作为优选的实施方式，所述云存储系统为基于HDFS的云存储服务系统。

参照图2，进一步作为优选的实施方式，所述步骤B，其包括：

B1、计算待存储的文件的文件特征指纹和每个数据块指纹；

B2、根据计算的文件特征指纹检索主索引，并根据检索的结果判断待存储的文件是否为新的文件类型，若是，则在执行步骤B3后执行步骤B5，反之，则在执行步骤B4后执行步骤B5；

B3、将待存储的文件分块存入存储系统中，并更新主索引及构建与待存储的文件类型相同的从索引；

B4、根据计算的数据块指纹检索从索引，并根据检索的结果更新从索引；

B5、更新元数据表，所述元数据表包括文件与数据块间的映射关系表以及数据块与数据节点间的映射关系表。

进一步作为优选的实施方式，所述步骤B2，其具体为：

客户端将计算的文件特征指纹与每个数据块指纹发送给主节点，由主节点根据文件特征指纹去主索引中检索，若未检索到与计算的文件特征指纹相同的记录，则表明待存储的文件为新的文件类型，此时先执行步骤B3然后执行步骤B5；若检索到已存在与计算的文件特征指纹相同的记录，则表明云存储系统中已有同类型的文件数据存在，待存储的文件为旧的文件类型，此时先执行步骤B4然后执行步骤B5。

参照图3，进一步作为优选的实施方式，所述步骤B3，其包括：

为待存储的文件分配存储地址，并根据分配的地址将待存储的文件数据块存储到存储系统的数据节点上；

对主索引进行更新；

构建与待存储的文件类型相同的从索引。

参照图4，进一步作为优选的实施方式，所述步骤B4，其包括：

B41、主节点根据客户端发送过来的当前数据块指纹去从索引中检索，检索从索引中是否存在与客户端发送过来的当前数据块指纹相同的数据块指纹，若是，则表明当前数据块需要进行去重操作，此时执行步骤B43，反之，则执行步骤B42；

B42、为待存储的文件分配存储地址，并根据分配的地址将待存储的文件数据块存储到存储系统的数据节点上，然后更新从索引；

B43、更新从索引的用户ID，将当前数据块的用户ID添加到从索引中与当前数据块相同的数据块的用户ID上。

进一步作为优选的实施方式，所述已存储文件的数据块指纹及待存储的文件的数据块指纹均采用SHA-1哈希算法计算得到。

下面结合说明书附图和具体实施例对本发明作进一步详细说明。

实施例一

本实施例对本发明所涉及到的相关理论进行介绍。

（1）名词定义及解释

HDFS：Hadoop的核心组件之一，即Hadoop分布式文件系统，可以用来在多台普通的计算机之间搭建分布式文件存储系统。HDFS具有高容错性、高可靠性的特征。

数据指纹：通过哈希函数生长的散列值，能唯一标识生成该数据指纹的数据块，具有全局唯一性。

SHA-1算法：一个使用非常广泛的哈希算法，SHA-1的输入消息的长度小于264，输出160位长度的字符串，即散列值。

最小值理论：两个数据集合S1与S2被随机排列转换后，得到的散列值中最小的两个相等的概率等于集合S1与S2的Jaccard相似度。设H(S)代表集合S中的所有元素的散列值的集合，集合S中的最小元素为min(H(S))，则最小值理论用公式表达为：

Pr[min(H(S1))=min(H(S2))]=

本发明将使用SHA-1算法求得数据块的数据指纹，并使用最小的数据指纹作为文件特征指纹对文件进行分类，构建相似文件集合，从而在相似的文件之间进行数据块去重。

（2）HDFS的基本概念

block：数据块，HDFS的基本存储单位为64M的数据块。

NameNode：主节点，用来管理文件系统的命名空间,其将所有的文件和文件夹的元数据保存在一个文件系统树中。

DataNode：数据节点，是文件系统中真正存储数据的地方。

ClientNode：客户端节点。

客户端节点或者主节点均可以向数据节点请求写入或者读出数据块。

DistributedFileSystem,，用于客户端节点向数据节点读取数据。

FSDataOutputStream，用于客户端节点将数据分成块，写入数据节点。

实施例二

参照图5、6和7，本发明的第二实施例：

本发明从基于HDFS的云存储系统角度出发，设计了一种跨用户的、基于相似性的数据块级文件去重方法，来对云存储中的数据进行去重，具体的实现过程为：

（一）为已存储文件构建二级指纹索引

本发明在云存储系统中添加了一个数据指纹索引节点，该指纹索引节点，用于由已存储文件的数据块生成数据块指纹，并包括一个由主索引和从索引组成的二级指纹索引。其中，主索引为已存储文件的文件特征指纹索引与文件相似性集合地址的映射，从索引为已存储文件的数据块指纹与数据块地址、用户ID之间的映射。加入指纹索引节点的云存储系统组成模块如图5所示，而基于相似性的二级指纹索引如图6所示。

如图6所示，主索引为一个key-value键值对的数据结构，key为文件特征指纹，代表某一类文件；value为该指向类文件的相似性集合的指针，指向某一特定文件的相似性集合，即指向从索引。从索引的数据结构为相似性集合中数据块指纹与数据块地址、数据块拥有者之间的映射。其中，相似性集合与文件的类别相对应，每个相似性集合里面保存着某一特定类型文件的数据块指纹索引。对于某个数据块，其可能对应有多个用户ID，即该数据块被多个用户所共有，若某个用户删除文件时包含被共享的数据块，则其只删除该索引记录中该数据块对应的自身用户ID；只有在该数据块对应的用户ID为空（即所有用户ID均被删去）时，才可以删除该数据块。

（二）对待存储的文件进行数据去重

在NameNode发送DataNode节点地址给客户端之前，要先对待存储的文件数据块进行去重。如图7所示，对待存储的文件进行数据去重的具体实现过程为：

首先，由客户端计算需要存储的文件的文件特征指纹和每个数据块指纹，然后将文件特征指纹与每个数据块指纹发送给NameNode，由NameNode根据该文件特征指纹去主索引中检索。

若主索引中未检索到与该文件特征指纹相同的记录，则表明该文件为一新文件类型，此时即可将该文件分块存入存储系统中。同时，需要更新主索引和file-blocks的映射关系表（即文件与数据块间的映射关系表），并构建与该文件类型相同的从索引，然后将数据块存储到DataNode节点上。

若检索到主索引中已存在与该文件特征指纹相同的记录，则表明云存储系统中已有同类型的文件数据存在。这种情况下，NameNode根据客户端发送过来的每个数据块指纹去文件相似集合即（从索引）中检索。如果在从索引中查询到已存在与客户端发送过来的某个数据块指纹相同的数据块指纹，则表明该数据块是重复的，需要进行去重操作。此时需要更新从索引中的数据块拥有者字段（即用户ID），将当前数据块拥有者的ID添加到数据块拥有者字段中。

与现有技术相比，本发明具有以下优点：

（1）利用文件的相似性构建由主索引和从索引组成的二级指纹索引，然后根据构建的二级指纹索引进行数据块级的数据去重，与传统基于文件的单个索引表的数据去重方法相比，检索效率更高。

（2）基于文件的相似性进行去重，不仅可以在一个用户的同类文件中进行数据去重，而且还可以在多个用户的同类文件之间进行数据去重，实现了跨用户的数据去重，应用范围更广。

以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可做作出种种的等同变形或替换，这些等同的变形或替换均包含在本申请权利要求所限定的范围内。