CN111045988B

CN111045988B - 文件查找方法、设备和计算机程序产品

Info

Publication number: CN111045988B
Application number: CN201811191427.9A
Authority: CN
Inventors: 王毅; 郑庆霄; 廖兰君
Original assignee: EMC IP Holding Co LLC
Current assignee: EMC Corp
Priority date: 2018-10-12
Filing date: 2018-10-12
Publication date: 2023-06-16
Anticipated expiration: 2038-10-12
Also published as: US11200204B2; CN111045988A; US20200117638A1

Abstract

本公开的实施例涉及一种文件查找方法、设备和计算机程序产品。该文件查找方法，包括：确定与待查找文件的标识相关联的哈希值；从多个候选位置链中确定与哈希值相关联的目标位置链；基于标识从目标位置链中确定目标元素，目标元素指示待查找文件在存储器中的地址；以及基于地址，从存储器中获取文件。

Description

文件查找方法、设备和计算机程序产品

技术领域

本公开的实施例总体上涉及存储系统，并且更具体地涉及在存储系统中使用的文件查找方法、设备和计算机程序产品。

背景技术

在许多备份系统(如Avamar备份系统)中，有一项重要功能称为创建快照视图(snapview)备份。此功能希望使用备份服务器中的现有备份文件来创建新的备份。在例如这种备份系统中，通常连接有一个服务器(例如，DataDomain服务器)，备份文件数据通常存储在该服务器中，而备份元数据通常存储在另一服务器(例如，Avamar服务器)中。备份元数据包含备份总体信息，如备份文件大小、创建时间等。备份文件数据包含备份文件数据的内容。

由于文件数据存储在例如DataDomain服务器中，因此，为了创建快照视图，需要获取文件在该服务器中的位置。获取文件在该服务器中位置后，就可以使用现有文件创建新的快照视图备份。

然而要搜索文件位置，当前解决方案将待搜索文件的文件名与多个现有文件的文件名逐个进行比较，直到找到完全匹配的项目。当前的解决方案虽然可以工作，但这并不是一种高效的方法。这是因为当存在大量文件时，通过逐个比较来进行搜索会需要很长时间，这将影响创建快照视图备份的性能。因此，需要一种更高效的文件搜索方法来缩短搜索过程所需的时间。

发明内容

本公开的各种实施例提供了一种文件查找方法、设备和计算机程序产品。

本公开的第一方面提供了一种文件查找方法，包括：确定与待查找文件的标识相关联的哈希值；从多个候选位置链中确定与哈希值相关联的目标位置链；基于标识从目标位置链中确定目标元素，目标元素指示待查找文件在存储器中的地址；以及基于地址，从存储器中获取文件。

本公开的第二方面提供了一种任务管理设备。该设备包括：处理单元；以及存储器，耦合至处理单元并且存储有指令，指令在由处理单元执行时执行以下动作：确定与待查找文件的标识相关联的哈希值；从多个候选位置链中确定与哈希值相关联的目标位置链；基于标识从目标位置链中确定目标元素，目标元素指示待查找文件在存储器中的地址；以及基于地址，从存储器中获取文件。

本公开的第三方面提供了一种用于任务管理的计算机程序产品，计算机程序产品被有形地存储在非瞬态计算机可读介质上并且包括机器可执行指令，机器可执行指令在被执行时使机器执行根据本公开第一方面所述方法的步骤。

附图说明

在此提供本文所描述的附图，用以进一步解释本公开，并构成本公开的一部分。本公开的示例性实施例及其描述用于解释本公开，而并非不恰当地限制本公开。

图1示出了示例性备份服务器的框图；

图2示出了备份文件位置和ddr_files；

图3示出了一种传统的文件搜索方法；

图4示出了根据本公开实施例的文件搜索方法的流程图；

图5示出了根据本公开实施例的创建地址数组和位置链的过程；

图6示出了根据本公开的一个实施例的文件搜索方法；以及

图7示出了用来实施本公开的实施例的设备的示意性框图。

在附图中，相同或相似的附图标记用于表示相同或相似的元件。

具体实施方式

现在将参照附图中示出的若干示例实施例来描述本公开的原理。尽管本公开的示例实施例在附图中示出，但是应当理解，实施例的描述仅仅是为了便于本领域技术人员更好地理解并由此实现本公开，而不以任何方式限制本公开的范围。

如本文所使用的，术语“包括”及其变体要被解读为意味着“包括但不限于”的开放式术语。术语“基于”要被解读为“至少部分地基于”。术语“一个实施例”和“一种实施例”要被解读为“至少一个实施例”。术语“另一个实施例”要被解读为“至少一个其他实施例”。术语“第一”、“第二”等等可以指代不同的或相同的对象。下文还可能包括其他明确的和隐含的定义。

在许多备份系统(如Avamar备份系统)中，快照视图备份使管理备份更加灵活。例如，在磁盘映像备份方案中，基本磁盘映像文件和更改的块文件是在不同时间创建的，因此分别为它们创建了2个备份。但是当客户想要恢复最新的映像文件时，他们需要恢复映像文件。这对于用户来说是不方便的，因为客户需要找到基本映像文件备份和相应的更改块备份。使用快照视图功能，客户可以为映像文件和更改块文件创建快照视图(snapview)备份，然后可以从一个快照视图备份还原所有内容，而无需分别查找它们。

另一个例子是，客户可能希望延长某个文件的过期时间。过期时间是从备份服务器中删除备份的时间。在此方案中，可以执行快照视图备份并为快照视图备份设置新的过期时间。同时，其他文件可以在原过期时间之后删除。这将节省大量存储空间，因为不需要在到期后时间之后备份任何数据。相反，只有快照视图备份中的指定文件数据才会保留到新的到期时间。

图1示出了示例性备份服务器100的框图。如图1所示，在备份服务器100中存在三个备份110、120和130，其中每个备份中又储有三个文件，即第一备份110中的文件1、文件2和文件3，第二备份120中的文件4、文件5和文件6，以及第三备份130中的文件7、文件8和文件9。在图1所示的示例中，快照视图备份140是基于文件1、文件5、和文件9的快照备份。需要指出，图1中所示的备份服务器100中的备份的数目以及每个备份中的文件数目仅仅是示例性的。本领域技术人员可以理解的是，可以包括与图1所示的备份的数目(即，3个)不同的备份数目，同时，每个备份中也可以包括不同的文件数目。

在上述备份系统(例如，Avamar备份系统)中，通常连接有另一个服务器(例如，DataDomain服务器)，备份文件数据通常存储在该服务器中，而备份元数据通常存储在备份服务器(例如，Avamar服务器)中。备份元数据包含备份总体信息，如备份文件大小、创建时间等。备份文件数据包含备份文件数据的内容。

下面以DataDomain服务器为例进行进一步说明。为了获取文件位置，首先需要了解文件数据是如何存储在DataDomain服务器中的。存在一个特殊格式容器，称为“原始格式容器“(后面也简称为“容器”)。原始格式容器广泛用于映像备份。如果文件数据存储在原始格式容器中，那么DataDomain服务器中将有一个名为“ddr_files”的文件，它描述了DataDomain服务器中的备份文件位置。“ddr_files”文件将描述文件所在的容器和容器中的文件位置偏移。为了在ddr_files中进行搜索，备份服务器将在服务器的内存中加载ddr_files的内容，并在内存中进行搜索。图2示出了备份文件位置以及ddr_files。

在图2所示的示例中，由服务器220表示DataDomain服务器，由210表示Avamar服务器。如图2所示，服务器220中存储有两个备份，即，备份110和备份120，其中备份110中包含3个原始格式容器111、112和113，文件1、文件2、文件3分别包含在相应的原始格式容器中。同样，备份120中也包含3个原始格式容器121、122和123，文件4、文件5、文件6分别包含在相应的原始格式容器中。同样需要指出，虽然在这一示例中，为清楚起见，每个容器中仅包含有一个文件，但是每个容器中也可以包含多个文件。

在本示例中，为了使用现有的文件2和文件6创建新的快照视图备份211，服务器210将在服务器210的内存212中加载ddr_files的内容，其中框“115”和“125”分别表示备份110的ddr_files的内容和备份120的ddr_files的内容。框213示出了在ddr_files的内容115中查找文件2，并且框214示出了在ddr_files的内容215中查找文件6的过程。

然而，要搜索到文件位置，当前解决方案需要将待查找的文件名与ddr_files中的多个文件名逐个进行比较，直到找到完全匹配的项目。图3示意性地示出了这种传统的文件搜索方法。如图3所示，以加载到(如图2所示的)内存212中的一个ddr_files的内容115为例，其中包括三个元素150、160和170，其中每个元素包含相应的文件1的文件名151、文件2的文件名161、和文件3的文件名171。另外，元素中还分别包含这些文件在容器中的存储位置152、162和172。当要搜索文件名300的位置时，需要将文件名300与每个元素所包含相应的文件名151、161和171逐一进行比较，直到找到文件名完全匹配的元素。

可以看出，这种解决方案虽然可以工作，但显然不是一种高效的方法。例如，当ddr_files中有远多于3个元素时，逐个搜索将需要很长时间，这将影响创建快照视图备份的性能。举例来说，当ddr_files内容115有超过1000个元素、且需要对中700个文件进行快照视图备份的情况下，对于快照视图备份中的每个文件，平均需要500次搜索整个1000项的ddr_files，总共需要500x 700次的比较，时间复杂度为O(N)。因此，如图3所示的这种传统的搜索方案会影响创建快照视图备份的性能。

本公开的各种实施例提供了一种更高效地文件查找的方法。通过这种文件查找方法，可以显著节省搜索过程所需的时间。将在下面仍参照ddr_files进行详细描述。

图4示出了根据本公开各种实施例的文件查找方法400的流程图。在410，确定与待查找文件的标识相关联的哈希值。这里，待查找文件的标识例如可以是文件的文件名。在420，从多个候选位置链中确定与哈希值相关联的目标位置链。在430，基于标识从目标位置链中确定目标元素，目标元素指示待查找文件在存储器中的地址。例如，该目标元素可以包括待查找文件的文件名和其在存储器中的地址。在440，基于地址，从存储器中获取文件。

通过本公开所提供的方案，通过使用哈希值来将待查找文件与包含有该文件的目标位置链相关联，使得在随后的查找过程中仅对该相关联的位置链(也即，包含有指示待查找文件在存储器中的地址的目标元素的那个位置链)中的一个或多个元素进行查找。以这种方式，将显著降低查找的次数，因为避免了对大量其他不相关的元素(即，包含在其他位置链中的元素)进行查找。

在某些实施例中，步骤420包括：从多个候选位置链中选择一个候选位置链，所选择的候选位置链与一个候选哈希值相对应，候选哈希值是基于与所选择的候选位置链中的元素相对应的哈希值而确定的。换句话说，在候选位置链中的所有元素可以具有相同的哈希值。这时，当所确定的哈希值与候选哈希值匹配时，将所选择的候选位置链确定为目标位置链。

在某些实施例中，从目标位置链确定目标元素包括：确定目标位置链中的元素所包括的候选标识(例如，候选文件名)；以及响应于标识(例如，待查找文件名)与候选标识之一相匹配，将与匹配的候选标识相对应的元素确定为目标元素。

为了实现上述高效的文件查找方法，在一些实践性的实施例中，通常需要首先创建多个位置链以及与多个位置链相关联的地址数组。例如，通常需要在内存(例如，图2中所示的内存212)中分配最大索引为0xFFF的数组(这里假设该数组为P[0xFFF])，并为数组中的每个元素分配一个空的位置链。随后，针对已经存储在ddr_files中的每个文件确定哈希值，该哈希值确定步骤与上述在文件查找过程中的哈希值确定方式相同。最后，获取ddr_files中每个元素的地址，并将地址添加到位置链中。至此，完成了多个位置链以及与多个位置链相关联的地址数组的建立。

使用哈希值来代替文件名能够实现如下有益技术效果：如果直接使用文件名作为索引，可能不能保证文件名在数组中的均匀分布，而哈希值可以使其分布均匀。

在某些实施例中，哈希值可以是根据该标识直接计算的哈希值，例如通过SHA-1算法计算得到的哈希值。在某些实施例中，哈希值可以是经截取的哈希值。在这种情况，可以根据标识首先计算一个初始哈希值，然后从初始哈希值中选择预定数目的连续位，以获得经截取的哈希值。

在一些示例中，从初始哈希值中选择预定数目的连续位可以包括：从初始哈希值的最低位开始选择预定数目的连续位。例如，以SHA-1哈希算法为例，初始哈希值有160位，从160位的初始哈希值的最低位开始选择12个连续位作为经截取的哈希值。

使用12位哈希值而不是使用完整哈希值是因为，使用完整哈希值作为索引将占用过多内存空间。以SHA-1哈希算法为例，完整哈希值有160位，这时如果使用160位作为数组索引，则数组大小将非常大，因为数组中会有太多元素。已经证明了截断的哈希值是均匀分布的。因此，即使使用12位截断的哈希值，地址数组也会被均匀使用。通常情况下，被用来创建快照视图备份的文件少于4000个文件。因此，12位数组索引可以覆盖大多数快照视图备份情况，并且其足够长以避免过多的哈希冲突。

举例来说，有一个文件A，计算文件名A的哈希值，文件A的截断12位哈希值是0x123。同时在ddr_files中获取元素的地址，然后通过检查数组元素P[0x123]的值找到位置链，并将此ddr_files元素地址添加到位置链。

图5示出了根据本公开实施例的创建地址数组和位置链的过程。如图5所示，一个ddr_files的内容115中包括三个元素150、160和170，其中每个元素分别包含相应的文件1的文件名151、文件2的文件名161、以及文件3的文件名171，以及这些文件在容器中的存储位置152、162和172。

对应于文件1的元素150为例，在框640处，针对文件1的文件名151确定哈希值。随后在框650处，获得截取的哈希值。同时在框660处获取元素150的地址，并将该地址添加到对应的位置链510中。针对另外两个元素160和170执行的操作与针对元素150执行的操作类似。具体来说，对应的确定哈希值操作步骤分别以框640’,640”指示，对应的获得截取的哈希值的操作分别以框650’,650”指示，并且对应的获取元素地址的操作分别以以框660’,660”指示。

继续参考图5，位置链510中进一步包括位置链头部511和一个位置链元素512，该位置链元素中包括文件1的文件名和元素150在ddr_files中的地址。位置链520中进一步包括位置链头部521和两个位置链元素522、523，位置链元素522中包括文件2的文件名和元素160在ddr_files中的地址，位置链元素523中包括文件3的文件名和元素170在ddr_files中的地址。此外，内存212还包括三个地址数组元素，并且每个地址数组中又包含截断的哈希值和位置链的地址。

注意到，在位置链520中包含了两个置链元素522、523。这意味着，文件2和文件3的文件名具有相同的截断的哈希值。因此，在创建位置链的过程中，将文件2和文件3归到同一个位置链中。需要指出，一个位置链中可以包含多于两个位置链元素(例如，4个、6个或更多)，当然，也可以像位置链510一样，仅包含一个位置链元素。这取决于所获得的截断的哈希值。

一旦创建了地址数组和位置链，将可以使用地址数组和位置链来搜索ddr_files中的元素。图6描述了根据本公开的一个实施例的文件查找方法。为了在ddr_files中搜索，在610处获得文件6的文件名，在620处，计算文件名的哈希值，并获得截取的哈希值。随后使用地址数组630来查找到相应的位置链640。在位置链640中，逐个比较每个元素的文件名，直到通过文件名642找到完全匹配的元素641。一旦在位置链中找到匹配元素641，通过元素641中包含的该元素在ddr_files中的地址643，就可以直接在ddr_files中找到该元素在容器中的地址651。由于位置链中元素的数量远小于ddr_files中元素的总数，因此搜索过程比传统的在ddr_files中逐个搜索每个元素的解决方案快得多。

综上所述，本公开所提供的各个实施例能够实现如下诸多有益技术效果。

首先，显着改善了快照视图备份的性能。新的解决方案将复杂度从O(N)降低到O(1)的，这为在ddr_files中搜索项目节省了大量时间。因此性能得到显着改善。

其次，将基于原始文件名的比较算法改为基于截断哈希值的比较算法，保证了新算法的均匀分布。

再次，节省了搜索的内存使用量。在新的解决方案中，不使用整个哈希值作为数组索引，因为可能存在很多数组元素并且将消耗大量内存空间。相反，只使用低12位并创建了一个位置链。这可以节省大量的内存空间。同时，已经证明截断的12位是均匀分布的。

另外，解决了哈希冲突。无论使用完整哈希值还是截断的低12位哈希值，对于相同的哈希仍可能存在哈希冲突。在新的解决方案中，使针对相同的哈希值使用位置链。这可以解决哈希冲突，并使位置链平滑分布。

图7示出了一个可以用来实施本公开的实施例的设备700的示意性框图。如图所示，设备700包括中央处理单元(CPU)701，其可以根据存储在只读存储器(ROM)702中的计算机程序指令或者从存储单元408加载到随机访问存储器(RAM)703中的计算机程序指令，来执行各种适当的动作和处理。在RAM 703中，还可存储设备700操作所需的各种程序和数据。CPU 701、ROM 702以及RAM 703通过总线404彼此相连。输入/输出(I/O)接口405也连接至总线704。

设备700中的多个部件连接至I/O接口705，包括：输入单元706，例如键盘、鼠标等；输出单元707，例如各种类型的显示器、扬声器等；存储单元708，例如磁盘、光盘等；以及通信单元709，例如网卡、调制解调器、无线通信收发机等。通信单元709允许设备700通过诸如因特网的计算机网络和/或各种电信网络与其他设备交换信息/数据。

上文所描述的各个过程和处理，例如方法400，可由处理单元701执行。例如，在一些实施例中，方法400可被实现为计算机软件程序，其被有形地包含于机器可读介质，例如存储单元708。在一些实施例中，计算机程序的部分或者全部可以经由ROM 702和/或通信单元709而被载入和/或安装到设备700上。当计算机程序被加载到RAM 703并由CPU 401执行时，可以执行上文描述的方法400的一个或多个步骤。备选地，在其他实施例中，CPU 701也可以以其他任何适当的方式被配置以实现上述过程/方法。

应当理解，本公开的上述详细实施例仅仅是为了举例说明或解释本公开的原理，而不是限制本公开。因此，不脱离本发明的精神和范围的任何修改、等同替换和改进等均应被包括在本发明的保护范围之内。同时，本公开的所附权利要求旨在覆盖落入权利要求的范围和界限内或范围和界限的等同物内的所有变化和修改。

Claims

1.一种文件查找方法，包括：

通过SHA-1算法确定与待查找文件的标识相关联的哈希值；

生成多个候选位置链以及与所述多个候选位置链相关联的多个地址数组，所述多个地址数组中的每个地址数组存储所述哈希值以及所述多个候选位置链的地址，其中所述待查找文件中的候选元素的地址被添加到所述多个候选位置链中；

从所述多个候选位置链中确定与所述哈希值相关联的目标位置链；

基于所述标识从所述目标位置链中确定目标元素，所述目标元素包括针对所述待查找文件的文件名和针对所述待查找文件的所述目标元素在存储器中的地址，所述目标位置中的所述目标元素的所述地址指向相应目标元素在所述待查找文件的容器中的地址，其中确定所述目标位置链包括：

基于所述多个候选位置链的存储在所述多个地址数组中的所述地址，从所述多个候选位置链中选择候选位置链，所选择的所述候选位置链具有候选哈希值，所述候选哈希值基于与所选择的所述候选位置链中的元素相对应的特定哈希值而被确定，以及

响应于所述特定哈希值与所述候选哈希值匹配，将所选择的所述候选位置链确定为所述目标位置链；以及

基于所述目标元素的所述地址，从所述存储器中获取所述文件。

2.根据权利要求1所述的方法，其中确定所述哈希值包括：

根据所述标识计算初始哈希值；以及

从所述初始哈希值中选择预定数目的连续位，以作为所述哈希值。

3.根据权利要求2所述的方法，其中从所述初始哈希值中选择所述预定数目的连续位包括：

从所述初始哈希值的最低位开始选择所述预定数目的连续位。

4.根据权利要求1所述的方法，其中从所述目标位置链确定所述目标元素包括：

确定所述目标位置链中的元素所包括的候选标识；以及

响应于所述标识与所述候选标识之一相匹配，将与匹配的候选标识相对应的元素确定为所述目标元素。

5.一种文件查找设备，包括：

处理单元；以及

存储器，耦合至所述处理单元并且存储有指令，所述指令在由所述处理单元执行时执行以下动作：

通过SHA-1算法确定与待查找文件的标识相关联的哈希值；

基于所述标识从所述目标位置链中确定目标元素，所述目标元素包括针对所述待查找文件的文件名和针对所述待查找文件的所述目标元素在所述存储器中的地址，所述目标位置中的所述目标元素的所述地址指向相应目标元素在所述待查找文件的容器中的地址，其中确定所述目标位置链包括：

6.根据权利要求5所述的设备，其中确定所述哈希值包括：

根据所述标识计算初始哈希值；以及

7.根据权利要求6所述的设备，其中从所述初始哈希值中选择所述预定数目的连续位包括：

8.根据权利要求5所述的设备，其中从所述目标位置链确定所述目标元素包括：

确定所述目标位置链中的元素所包括的候选标识；以及

9.一种非瞬态计算机可读介质，在其中存储有指令，所述指令在由处理器执行时，使所述处理器执行根据权利要求1-4中任一项所述的方法的步骤。