基于应用感知的重复数据删除存储系统中的数据重构方法

摘要

基于应用感知的重复数据删除存储系统中的数据重构方法，涉及计算机存储领域。充分利用所备份文件的文件类型信息，对所有文件按文件类型进行分类，再按文件类型对文件进行备份，以提高数据读取时的数据重构速度。由并行的数据写入阶段和数据读取阶段组成，所述备份文件的数据写入阶段由文件分类步骤、文件分块步骤、哈希指纹计算步骤、重复数据删除步骤和数据写入步骤顺序组成；所述备份文件的数据读取阶段由文件分类信息获取步骤、文件指纹信息获取步骤、文件数据块获取步骤、数据重构完成步骤顺序组成。通过改变传统重复数据删除过程中的数据写入方法以提高数据读取时的数据重构速度。

说明书

技术领域

本发明涉及计算机存储领域，尤其是涉及一种基于应用感知的重复数据删除存储系统中 的数据重构方法。

背景技术

随着网络的发展，各种数据呈爆炸性的生长，对存储容量的需求也不断增大，所以存储 容量的要求也不断增加。在考虑存储成本的情况下，人们开始思考如何在有限的空间内存储 更多的数据，于是重复数据删除技术开始问世。

重复数据删除是一种目前主流且热门的存储技术，通过检测数据集的相同数据部分，删 除重复的数据内容，只保留唯一的数据对象副本，从而达到消除冗余的目标。重复数据删除 技术能够有效减少数据的存储容量和数据在网络中的传输量，进而降低存储成本和能耗需求 或提高网络带宽。

存储系统的重复数据删除过程一般如下：系统首先将文件分成一组数据块，计算每个数 据的哈希指纹，然后以该哈希指纹为关键字查找哈希表，判断该数据块是否与已存储的数据 重复。若重复，则丢弃该数据块，只保留该数据块的索引号；若不重复，即该数据块是全新 的，则保存该数据块并给其分配唯一的索引号，同时将该数据块的哈希指纹保存到哈希表。 一个文件经过重复数据删除后在存储系统中就表现为一系列的数据块索引号。因此，一个物 理文件在存储系统中对应一个逻辑表示，由一组指纹组成的元数据组成。当进行文件读取时， 先读取该逻辑文件，然后根据指纹信息从存储系统中读取出相应的数据块，还原物理文件。

数据的分块方式主要有两种，一种是固定大小分块，即将数据分割成大小固定的数据块； 另一种是基于内容的分块，为避免数据更新时带来的分块边界迁移问题而根据数据内容将数 据分割成不同大小的数据块。通过对多个数据集的观察可以知道，对于静态应用文件即数据 不会被更新的文件，例如虚拟机镜像文件，固定大小分块方法优于基于内容的分块方法。这 两种分块方法都需要计算每个数据块的哈希指纹值，而计算哈希指纹是一个非常占用中央处 理器资源的过程，所以评估哈希指纹的计算花销也是很重要的。

Vasily Tarasow,Deepak Jain,Geoff Kuenning,Sonam Mandal,Karthikeyani  Palanisami,Philip Shilane,Sagar Trehan,and Erez Zadol.Dmdedup:Device Mapper  Target for Data Deduplication.In Proceeding of the 2014Ottawa Linux Symposium.Pages 1-2.

发明内容

本发明的目的在于针对重复数据删除存储系统中数据的写入过程会直接影响数据的读取 过程，因此改进数据的写入模式可以提升数据读取时的数据重构速度，提供一种用于提升数 据读取时数据重构速度的基于应用感知的重复数据删除存储系统中的数据重构方法。

本发明包括并行的备份文件的数据写入阶段和备份文件的数据读取阶段；

所述备份文件的数据写入阶段，包括以下步骤：

(1)文件分类步骤，进行下列过程：

递归遍历备份路径下的所有文件，统计所有出现的文件类型和每个类型的所有文件及其 路径，以生成分类树和备份版本号；转步骤(2)；

(2)文件分块步骤，对同一类型的文件进行下列过程：

(2.1)遍历此类型下的全部文件，依次打开步骤(1)提供的对同一类型的所有文件路 径；转过程(2.2)；

(2.2)对每个文件路径，创建一个块结构体并标记文件开始；转过程(2.3)；

(2.3)读取过程(2.2)中文件路径里的数据内容，创建一个块结构体并在此块结构体 中存储文件数据内容，直至文件结束；除最后一个块结构体外，文件结构体中的数据大小固 定的；转过程(2.4)；

(2.4)创建一个块结构体并标记文件结束，并把所有创建的块结构体保存到一个块结构 体队列中；判断同类型文件是否都已完成分块，若是，则转步骤(3)，否则转步骤(2)；

(3)哈希指纹计算步骤，进行下列过程：

根据过程(2.4)得到的块结构体队列，依次调用哈希函数计算每个块结构体数据部分的 哈希值，然后创建一个相应的块结构体以保存其哈希值，把本过程创建的块结构体保存到一 个哈希指纹队列中，并将标记文件开始和结束的块结构体也保存到哈希指纹队列中；转步骤 (4)；

(4)重复数据删除步骤，进行下列过程：

(4.1)将步骤(3)中的哈希指纹队列的一个块结构体包含的哈希指纹在键值表中进行 查找，键值表是存储所有哈希指纹及对应存储地址的索引表，若键值表中找到一致的哈希指 纹，则将此块结构标记为重复，否则将此哈希指纹及其对应存储地址写入键值表中；

(4.2)判断所有数据块是否都已经完成哈希指纹查找步骤即步骤(3)中创建的哈希指 纹队列中所有块结构体中的哈希指纹都已在键值表中完成查找，若是，则转步骤(5)，否则 转过程(4.1)；

(5)数据写入步骤，进行下列过程：

(5.1)判断过程(4.1)中的块结构体标记的数据块是否是重复的，若是，则记录该数 据块在磁盘上的位置，否则将该数据块添加到存储缓存中；转过程(5.2)；

(5.2)将存储缓存中的块结构体、元数据文件、键值表和哈希指纹队列写入到磁相应位 置；转过程(5.3)；

(5.3)判断所有文件类型是否都已完成写入操作，若是，则备份文件的数据写入阶段结 束，否则转步骤(2)；

所述备份文件的数据读取阶段，包括以下步骤：

(6)文件分类信息获取步骤，进行下列过程：

根据需要读取的备份文件的版本号获取相应的备份文件的分类树，统计此备份版本中出 现的所有文件类型，对同一类型的文件进行步骤(7)；

(7)文件指纹信息获取步骤，进行下列过程：

读取元数据文件，查找此备份版本中的全部哈希值队列；转步骤(8)；

(8)文件数据块获取步骤，进行下列过程：

根据哈希指纹队列中的指纹信息查询键值表，读取对应的数据块；转步骤(9)；

(9)数据重构完成步骤，进行下列过程：

递归创建备份文件目录，根据元数据文件将读取到的数据块重构到指定路径下，判断所 有类型的数据是否都已经读取完毕，若是，则备份文件的数据读取阶段结束，否则转步骤(7)。

在重复数据删除存储系统中，数据的写入过程会直接影响数据的读取过程，因此改进数 据的写入模式可以提升数据读取时的数据重构速度。针对这个问题，本发明提出的基于应用 感知的数据重构方法，通过改变传统重复数据删除过程中的数据写入方法以提高数据读取时 的数据重构速度。

本发明由并行的备份文件的数据写入阶段和备份文件的数据读取阶段组成。所述备份文 件的数据写入阶段由文件分类步骤、文件分块步骤、哈希指纹计算步骤、重复数据删除步骤 和数据写入步骤顺序组成；所述备份文件的数据读取阶段由文件分类信息获取步骤、文件指 纹信息获取步骤、文件数据块获取步骤、数据重构完成步骤顺序组成。

所述重复数据删除系统关键在于基于应用感知的数据布局和指纹存储，每种类型的应用 文件都对应四个磁盘文件，即数据块文件、索引文件、指纹序列文件和元数据文件。数据块 文件保存此次备份的数据内容；索引文件保存数据分块后的键值对，即每个哈希指纹及其对 应数据块所在的地址；指纹序列文件保存此次备份中所有数据块对应的指纹序列值；元数据 文件保存此次备份的备份版本、文件数量、文件大小、分块数量、重复删除率和指纹序列文 件地址。读取备份文件时根据需要读取的文件类型按类型重构。

附图说明

图1为本发明的示意图；

图2为本发明备份文件的数据写入过程的示意图；

图3为本发明文件分类过程结果的示意图；

图4为本发明文件数据布局的示意图；

图5为本发明数据读取过程的示意图。

具体实施方式

下面以三个文件a.txt、b.doc和c.pdf为例，结合附图对本发明作进一步说明。

本发明包括并行的备份文件的数据写入阶段和备份文件的数据读取阶段；

所述备份文件的数据写入阶段，包括以下步骤：

(1)文件分类步骤，进行下列过程：

递归遍历备份路径下的所有文件，统计所有出现的文件类型和每个类型的所有文件及其 路径，以生成分类树和备份版本号；转步骤(2)；

(2)文件分块步骤，对同一类型的文件进行下列过程：

(2.1)遍历此类型下的全部文件，依次打开步骤(1)提供的对同一类型的所有文件路 径；转过程(2.2)；

(2.2)对每个文件路径，创建一个块结构体并标记文件开始；转过程(2.3)；

(2.3)读取过程(2.2)中文件路径里的数据内容，创建一个块结构体并在此块结构体 中存储文件数据内容，直至文件结束；除最后一个块结构体外，文件结构体中的数据大小固 定的；转过程(2.4)；

(2.4)创建一个块结构体并标记文件结束，并把所有创建的块结构体保存到一个块结构 体队列中；判断同类型文件是否都已完成分块，若是，则转步骤(3)，否则转步骤(2)；

(3)哈希指纹计算步骤，进行下列过程：

根据过程(2.4)得到的块结构体队列，依次调用哈希函数计算每个块结构体数据部分的 哈希值，然后创建一个相应的块结构体以保存其哈希值，把本过程创建的块结构体保存到一 个哈希指纹队列中，并将标记文件开始和结束的块结构体也保存到哈希指纹队列中；转步骤 (4)；

(4)重复数据删除步骤，进行下列过程：

(4.1)将步骤(3)中的哈希指纹队列的一个块结构体包含的哈希指纹在键值表中进行 查找，键值表是存储所有哈希指纹及对应存储地址的索引表，若键值表中找到一致的哈希指 纹，则将此块结构标记为重复，否则将此哈希指纹及其对应存储地址写入键值表中；

(4.2)判断所有数据块是否都已经完成哈希指纹查找步骤即步骤(3)中创建的哈希指 纹队列中所有块结构体中的哈希指纹都已在键值表中完成查找，若是，则转步骤(5)，否则 转过程(4.1)；

(5)数据写入步骤，进行下列过程：

(5.1)判断过程(4.1)中的块结构体标记的数据块是否是重复的，若是，则记录该数 据块在磁盘上的位置，否则将该数据块添加到存储缓存中；转过程(5.2)；

(5.2)将存储缓存中的块结构体、元数据文件、键值表和哈希指纹队列写入到磁相应位 置；转过程(5.3)；

(5.3)判断所有文件类型是否都已完成写入操作，若是，则备份文件的数据写入阶段结 束，否则转步骤(2)；

所述备份文件的数据读取阶段，包括以下步骤：

(6)文件分类信息获取步骤，进行下列过程：

根据需要读取的备份文件的版本号获取相应的备份文件的分类树，统计此备份版本中出 现的所有文件类型，对同一类型的文件进行步骤(7)；

(7)文件指纹信息获取步骤，进行下列过程：

读取元数据文件，查找此备份版本中的全部哈希值队列；转步骤(8)；

(8)文件数据块获取步骤，进行下列过程：

根据哈希指纹队列中的指纹信息查询键值表，读取对应的数据块；转步骤(9)；

(9)数据重构完成步骤，进行下列过程：

递归创建备份文件目录，根据元数据文件将读取到的数据块重构到指定路径下，判断所 有类型的数据是否都已经读取完毕，若是，则备份文件的数据读取阶段结束，否则转步骤(7)。

图1为本发明的示意图：初始化步骤完成后进入并行的备份文件的数据写入阶段和备份 文件的数据读取阶段，当用户操作完成发出关闭指令时，进入结束步骤。

图2为本发明备份文件的数据写入过程的示意图：初始化完成后首先是备份文件的文件 分类步骤，对用户提供的备份目录进行递归遍历，得到文件分类信息，即备份目录下文件类 型和每个文件类型下的所有文件的路径，在此例子中，有三种文件类型：txt、doc和pdf， 每种文件类型包括一个文件；文件分类完成后，文件分块步骤按照文件类型依次对文件数据 进行分块，生成文件块队列并标记文件的开头和结束；哈希计算步骤将依次调用哈希函数计 算每个文件块结构体数据的哈希指纹值，然后创建一个相应的块结构体以保存其哈希指纹值， 并把本过程创建的块结构体保持到一个哈希指纹队列中。对标记文件开始和结束的块结构体 复制也保存在哈希指纹队列中；然后对哈希指纹队列中的每个块结构中的哈希指纹在键值表 中进行查找，键值表是存储所有哈希指纹及对应存储地址的索引表，如果在键值表中找到一 致的哈希指纹则将此块结构标记为重复，否则将此哈希指纹及其对应存储地址写入键值表中； 标记结束后将非重复数据块和与此文件有关的元数据和键值表分类写入磁盘；判断在三种文 件类型的文件数据是否都写入完成，是则结束，否则继续进行数据写入。

图3为本发明文件分类过程结果的示意图：主队列每个节点保存一个文件类型，每个文 件类型节点下面的子队列中的每个节点保存属于这个文件类型的一个文件路径。

图4为本发明文件数据布局的示意图：每种文件类型的应用文件都对应四个磁盘文件， 即数据块文件、键值表、指纹序列文件和元数据文件。

图5为本发明数据读取过程的示意图：根据用户提供的备份文件的版本号查询备份数据 所在的位置，并通过元数据文件获取该备份文件的文件分类信息，重新生成如图2所示的文 件分类结果，再按照用户的数据读取要求读取所要读取的文件的哈希指纹序列，根据键值表 得到指纹序列对应的文件块地址，最后将用户需要的文件数据读取到用户指定的目录下，直 至所有的文件类型都恢复完毕时数据读取结束。