基于文件路径的信息集群中重复数据消除研究

杨美艳，徐庆增

(天津科技大学人工智能学院，天津 300457)

1 引言

随着信息化时代的高速发展，各类数据信息的数量均呈现出指数级增加趋势，导致存放于计算机存储系统中的数据信息规模日益扩大[1]。其中越来越多的冗余数据既占据了存储空间、降低存储系统的性能，也提高了数据的管理成本。因此，利用数据缩减方法来减少冗余数据、加强储存系统性能具有重要的现实意义与理论意义[2]。作为数据缩减技术之一的重复数据消除方法，不仅能够实现对冗余数据的大规模删除，而且可以令存储的空间利用率得以提升。因此，重复数据消除方法逐渐成为计算机存储领域的一个热点课题。

文献[3]针对重复数据吞吐量不可控、相似判断完成时间过长等问题，利用关联规则提出一种海量重复数据消除系统，将硬件部分分解为重复数据检测模块，增加其吞吐总量与消除可靠性，采用融合TCP/IP、netBEUI以及IPX/SPX协议方案，通过基础数据序列的关联规则对重复数据检测编码进行改进，从而使消除高效性与稳定性得到保证；文献[4]为了更好地控制重复数据消除算法中的可变长度分块大小，降低指纹计算比较开销，设计一种基于winnowing指纹串匹配的重复数据删除算法，通过建立分块大小的预测模型，依据运用场景对分块大小进行精准计算，然后利用ASCⅡ/UNICODE编码形式，完成数据块指纹生成，采用指纹串匹配分块算法，降低指纹计算与对比开销；文献[5]针对异构型物联网中的重复数据，设计了一种多维数据聚类的重复数据清除方法，对所有感知数据属性的连续值作离散化处理，提取全部数据文本特征向量并量化，再利用傅里叶转换方法联立字符关系矩阵，并形成数据与各字符之间的映射形式，根据各数据的傅里叶系数矢量获取数据相似度判断阈值，从而达成重复数据清除的目的。

上述消除方法存在的共性问题是重复数据消除比率与消除速度偏低，难以提升数据存储空间的利用率。为此，本文利用文件路径设计了一种信息集群中重复数据消除方法。

2 重复数据消除原理分析

利用数据压缩技术的信息集群重复数据消除方法通过对比数据内容的哈希值，完成对相同数据的识别，对于重复副本，利用保留下来的唯一指向单一副本指针实施替换，从而实现冗余数据消除、降低存储容量。

与数据压缩过程不同的是，对信息集群中重复数据的消除是在存储数据的过程中，对数据进行分块筛选，从而实现对当前存在数据的检查与对比。若数据相一致，则将该部分数据备份去除，并将其替换为指向唯一的实例指针。重复数据消除一般步骤如图1所示。

图1 重复数据消除一般步骤示意图

在分块筛选阶段中，重复数据消除方法的三种分块理念分别为内容分块理念、整文件分块理念以及固定规格分块理念，其数据副本保存形式均通过单实例策略得以完成。

假设数据消除前与消除后的文件集合分别为F与F′，经过消除的块数据集合为C′，文件或者块数据及其储存空间索引的集合表示为I，则集合I与输入项文件集合F的表达式分别如下

F={f1，f2，…，fn}

(1)

I={fk→index|fk∈F′}

(2)

输出项文件集合F′符合F′⊆F，各集合的初始状态分别是F′=∅、I=∅以及fk→index∈I、∀fk∈F。

在此基础上，通过在同一节点上存储近似数据或文件提升信息集群重复数据消除的效率。文件路径也叫文件系统路径，是一种文件系统语义，构成部分为文件系统中从根目录到文件位置目录的所有目录名称。一般情况下，数据连续备份版本的目录结构具有一定的稳定性，也就是说，目录名称相同的副本极有可能与同一个初始目录相对应，即目录名称一样的文件集合极有可能含有一样的数据[6]。

由于父目录的更改不会影响到该目录的子目录。因此，当不同副本的子目录被修改或者移动时，其父目录也会保持不变，因此，在对信息集群的重复数据进行消除的过程中，无需运用整个文件目录，只利用与文件最为趋近的部分父目录数据即可。

假设文件的整个路径为directory name，目录深度是directory depth，表示文件位置目录以上的目录层次，get sub directory函数可依据文件目录名称知晓特定目录深度子目录名称功能的是，则针对某一文件目录为“/a/b/c/d.txt”的文件d.txt，“/b/c”为其目录深度是2的子目录名称，同理可知，“/a/b/c”为其目录深度是3的子目录名称。

文件路径重复数据消除原理如图2所示。

图2 文件路径重复数据消除原理图

将文件目录作为粒度，完成重复数据的查找与消除识别不同目录下的相同文件，避免重复存储相同文件[7]。然后依据整个文件的数据目录名称，对比存储过的文件目录名称，若存在相同名称，则文件为重复数据，利用指针对其进行替换，并存储新的文件数据。

3 信息集群中重复数据消除的实现

尉氏县重复数据消除、系统性能提升以及扩展，完成文件路径下信息集群的重复数据消除方法的构建。

基于文件路径的信息集群中重复数据消除方法主要由客户端、元数据服务器以及存储节点集群等模块架构而成。对文件模块与数据块模块的重复数据同时进行消除，以获取更加理想的消除效果。通过架构多个存储节点的文件路径信息集群，并在各节点上实施重复数据检测，更好地发挥消除方法的性能[8]；利用各节点间的整体重复数据消除，令消除方法适用于扩展的存储节点个数，从而取得较好的消除结果。

3.1 元数据信息界定

由于重复数据消除是基于文件路径上的数据目录名称或者数据块的数据标签得以完成的，因此，文件、数据块与容器元数据信息的维护具有很明显的重要性。

文件元数据信息的构成分别有文件目录名称、文件规格以及建立时间等，具体内容如表1所示。

表1 文件元数据信息统计表

数据块元数据信息主要由数据块标签、数据块规格以及数据块存储容器等构成，具体内容如表2所示。

表2 数据块元数据信息统计表

表2中的容器是存储节点磁盘系统内的一种文件，其功能是依据数据块的逻辑顺序存储消除过的数据块与元数据信息，其中元数据信息如表3所示。

表3 容器元数据信息统计表

3.2 信息集群重复数据消除流程

3.2.1 文件部分重复数据消除

在数据备份的过程中，按照以下步骤来完成对文件模块的重复数据消除：

1)客户端依据各文件的哈希值生成目录名称，并将其传输至元数据服务器；

2)元数据服务器根据存储的文件元数据信息检测重复数据，把非重复的新文件目录名称与存储节点信息同步发送给客户端，随后客户端将数据块传输至每个存储节点内，从而实现文件模块的重复数据消除。

文件模块重复数据消除过程如图3所示。

图3 文件模块重复数据消除示意图

3.2.2 数据块模块重复数据消除

基于文件模块的重复数据消除结果，对信息集群中的多个重复文件进行消除，数据块模块重复数据消除则是实现文件内部的重复数据消除，其步骤如下：

1)客户端分块新文件后，对潜在冗余数据进行消除，以防止固定长度数据块发生偏移，所以，当文件规格小于2kB时，不用实施分块操作，可直接当做一个数据块进行处理；

2)经过文件分块，客户端将各文件数据块的哈希值作为数据块标签，把文件元数据信息与所含数据块标签列表同步传输至元数据服务器，从而达成数据存储，为数据恢复阶段的所有数据块获取奠定基础，客户端把所有数据块标签与不同存储节点一一对应后，实施重复数据消除；

3)当存储节点收到数据块标签，通过bloom filter法比较本地节点存储的数据块标签[9]，进而完成全局范围的重复数据消除，随后存储节点会发送给客户端全部的非重复数据块标签；

4)客户端通过把非重复数据块以及相应的元数据信息传输至对应存储节点，对其实施打包存储，此时数据块重复数据消除操作终止。

数据块模块重复数据消除过程如图4所示。

图4 数据块模块重复数据消除示意图

3.3.3 数据恢复阶段

为了使数据的可靠性得到保证，确保数据在出现损坏或者丢失的情况下，也可以随时恢复、随时可用，数据的可恢复性由文件路径下信息集群重复数据消除方法存储的元数据信息实现，其流程如下：

1)客户端发送待恢复的文件目录名称给元数据服务器；

2)元数据服务器接收之后，对文件元数据信息表进行查询，并将取得的数据块标签列表，返回客户端；

3)依据文件名录名称对存储节点个数的取模结果，客户端对文件数据块及其元数据信息的存储节点进行存储，且发送数据块标签列表给对应节点；

4)在接收到全部数据块之后，客户端开始重建操作，数据恢复阶段结束。

数据恢复过程如图5所示。

图5 数据恢复示意图

4 仿真与分析

为验证上述设计的基于文件路径的信息集群中重复数据消除方法的实际应用性能，设计如下仿真。

4.1 仿真环境设置

仿真的硬件环境为：英特尔至强E5502四核处理器、浪潮AS300N服务器，mellanox connectX 4X QDR单向40GBPS的infiniband网卡，LSI logic/symbios logic mega SAS RAID卡；软件环境为：Red Hat Enterprise Linux(RHEL)操作系统，2.6.18-164.11.1.el5＿lustre.1.8.2内核。

信息集群分别选自企业系统的trace集合与Linux系统源代码集合，表4为集群的相应参数。

表4 参数统计表

为突出本文方法的应用优势，将传统的基于winnowing指纹串匹配的重复数据删除方法和基于关联规则的海量重复数据消除方法作为对比，共同完成性能验证。

为了评估不同的重复数据消除方法的性能，将评估指标设定为分块大小的标准方差，表达式如下

(3)

其中，分块大小的标准方差为σ，分块个数为N，实际分块大小为xi，期望分块大小为μ。

4.2 消除效果对比分析

如图6所示为不同方法的重复数据消除比率对比结果。重复数据消除比率越高，说明消除方法对重复数据的检索、删除能力越强。

图6 重复数据消除比率对比图

通过图6可以看出，基于winnowing指纹串匹配方法的消除比率呈不断上升趋势，且消除比率始终在92%以上；基于关联规则方法的消除比率先上升后下降，最大比率接近92%；本文方法的消除比率不断下降，但整体来讲，本文方法的消除比率在三种方法中为最高。由此可知，本文方法对重复数据的消除能力更强。

4.3 消除时长对比分析

进一步验证不同方法对重复数据的消除时长，从而判断不同方法的时效性。结果如图7所示。

图7 重复数据消除时长对比图

根据图7中的曲线走势可以看出，随着数据量的增加，不同方法对重复数据的消除时长也在不断增加。相比之下，基于winnowing指纹串匹配方法的消除时长最多，始终保持在12s以上，基于关联规则方法其次，本文方法的消除时长最少，始终保持在8s以下。由此可知，本文方法消除重复数据的时效性最高。

5 结束语

数字信息技术既改善了人们的生活方式，也推动了经济社会的发展。在数据量呈爆炸式增长的环境下，数据存储容量正面临着一项巨大的挑战。因此，为了使该领域问题得到有效解决，本研究提出一种基于文件路径的信息集群中重复数据消除方法。将信息集群重复数据消除的基本流程与分块思想引入文件系统中，根据根目录到文件位置目录的所有目录名称以及父目录与子目录关系，分析文件路径的消除方法原理，通过同时消除文件模块与数据块模块中的重复数据实现方法设计。该方法具有良好的发展前景，也为信息集群的后续处理奠定了基础。