CN102880663A

CN102880663A - 部分去重复的文件的优化

Info

Publication number: CN102880663A
Application number: CN2012103202010A
Authority: CN
Inventors: R·卡拉赫; K·哈桑; P·A·奥尔泰安; J·R·本顿; C·H·张; A·古普塔
Original assignee: Microsoft Corp
Current assignee: Microsoft Technology Licensing LLC
Priority date: 2011-09-01
Filing date: 2012-08-31
Publication date: 2013-01-16
Anticipated expiration: 2032-08-31
Also published as: US20130060739A1; CN102880663B; JP6045590B2; EP2751693A2; KR20140068919A; WO2013032825A3; US8990171B2; WO2013032825A2; EP2751693A4; JP2014525631A; KR101988683B1; EP2751693B1

Abstract

本发明涉及部分去重复的文件的优化。本公开针对将具有至少一个未去重复的部分的文件变换成完全去重复的文件。针对所述至少一个未去重复部分中的每个，去重复机制在与所述至少一个未去重复部分相关联的文件偏移量之间定义至少一个块。与所述至少一个块相关联的块边界被存储在去重复元数据内。去重复机制使所述至少一个块与所述文件的至少一个去重复部分的块边界对齐。然后，所述至少一个块被提交给块存储。

Description

部分去重复的文件的优化

技术领域

本发明涉及部分去重复的文件的优化。

背景技术

数据去重复（有时也称为数据优化）指的是检测、唯一地标识以及消除存储系统中的冗余数据从而减少需要被存储在盘上或需要通过网络进行传送的数据的物理字节量，而不会损害原始数据的保真性和完整性。通过减少存储和/或传送数据所需的资源，数据去重复因此导致硬件和功率成本（用于存储）以及数据管理成本（例如，降低备份成本）的节约。随着数字存储的数据的数量增长，这些成本节约变得重要。

数据去重复通常使用用于消除持久存储的文件内部及其之间的冗余性的技术的组合。一种这样的技术用于标识一个或多个文件中的相同数据区域，并在物理上只存储一个唯一区域（块），同时为此数据的所有重复出现与文件相关联地维护对该块的引用。另一技术是例如通过存储经压缩的块来将数据去重复与压缩混合。

关于数据去重复可能存在许多困难、折衷和选择，包括在一些环境中，在给定可用时间和资源的条件下在单个操作中存在过多的数据要去重复。具体的挑战存在于被部分地去重复的文件，比如响应于新数据或对现有数据的修改而被部分召回到盘的之前被去重复的文件。对被部分去重复的文件整体进行去重复需要：大量的输入/输出资源以用于读取整个文件并对其进行分块（chunking）并且然后将所述块写入到块存储中；以及CPU资源以用于执行分块和压缩。

发明内容

提供本概述以便以简化形式介绍将在以下的详细描述中进一步描述的一些代表性概念。本概述不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在以限制所要求保护的主题的范围的任何方式来使用。

简言之，在此所描述的主题的各方面所针对的是，通过把具有一个或多个未去重复的部分的文件变换成完全去重复的文件来优化部分去重复的文件。在一个方面，去重复机制通过如下方式对未去重复的部分执行去重复进程：标识出涵盖该未去重复的部分的一个或多个块；以及定义与所述一个或多个块相关联的文件偏移量之间的一个或多个新块。与所述一个或多个新块相关联的块边界与该文件的未召回的去重复的部分的块不重叠。通过维护与未召回的去重复的部分的对齐，所述一个或多个新块可以被提交给块存储而不必修改任何其他块。在另一方面，与该文件相关联的去重复元数据被修改为包括所述块边界以及与所述一个或多个新块相关联的其他信息，并且与所述一个或多个块相关联的任何元数据都可以被替换。

在另一方面，该文件可以被分区成子文件分区以简化去重复进程。去重复机制在每个去重复进程期间一次对单个子文件分区进行分块和提交。然后，去重复机制在对下一子文件分区进行去重复以前从该文件中截去（truncate）该子文件分区。如果去重复进程在完成子文件分区的去重复以前被暂停，则去重复进程可以在已被提交的最后一个块之后的位置处恢复。

附图说明

作为示例而非限制，在附图中示出了本发明，附图中相同的附图标记指示相同或相似的元素，附图中：

图1是示出根据一个示例性实施方式的用于优化被部分去重复的文件的示例系统的框图图示。

图2是表示根据一个示例性实施方式的去重复机制的示例性组件/阶段的框图。

图3A－图4B示出了根据一个示例性实施方式被变换成完全去重复文件的各种示例性部分召回的文件。

图3C示出了根据一个示例性实施方式被变换成完全去重复文件的示例性部分去重复文件。

图4A－图4B示出了根据一个示例性实施方式的去重复元数据。

图5是示出了根据一个示例性实施方式用于将具有至少一个未去重复部分的文件变换成完全去重复的文件的步骤的流程图。

图6是示出了根据一个示例性实施方式用于对被分区成子文件分区的文件进行去重复的步骤的流程图。

图7是表示其中可实现此处描述的各种实施例的示例性非限制联网环境的框图。

图8是表示其中可实现此处所描述的各种实施例的一个或多个方面的示例性非限制计算系统或操作环境的框图。

具体实施方式

在此所描述的技术的各方面总体上所针对的是，通过把具有一个或多个未去重复的部分的文件变换成完全去重复的文件来优化部分去重复的文件。在一个示例性实施方式中，部分去重复的文件可以包括部分召回的文件，该部分召回的文件通过如下方式被优化：对所召回的文件范围而不是整个文件进行去重复；以及把与之前被去重复的部分相关联的去重复元数据同新的被去重复的文件范围相组合。由于之前被去重复的部分未再次被去重复，因此节省了显著的I/O和CPU资源量。类似地，被部分去重复的文件内的一部分可以被去重复，使得该部分内的新块与周围的之前被去重复的部分的块对齐。

在另一示例性实施方式中，去重复机制以如下方式分阶段地优化大文件：将该文件分区成子文件分区；将每个子文件分区内的块提交给块存储；以及从包含该文件的文件流中截去该子文件分区。这样的实施方式在优化整个文件以前释放了存储空间，并且降低了在该文件被完全去重复之前存在崩溃或异常中止的情况下发生存储器泄漏的可能性。

在另一示例性实施方式中，去重复机制支持暂停指令，该暂停指令挂起去重复进程直到随后的恢复指令。去重复机制在第一未去重复的部分处重启去重复进程，其中该第一未去重复的部分是未被分块和提交给块存储的最后一个部分。这允许主系统在另一工作量需要系统资源的情况下暂停去重复进程，而不必对已经去重复的数据重复去重复进程。

在又一示例性实施方式中，通过对块和相应文件范围进行多级分区来实现对大文件的快速输入/输出。由于包括大文件范围集合的去重复元数据变得难以搜索，因此将文件分区成多个连续的较小子文件分区（所述子文件分区再次被分区）允许去重复机制高效地将虚拟文件偏移量（相对于文件的开头）转换成这些子文件分区内的特定块偏移量。文件偏移量转换可以在对文件的输入/输出（I/O）活动（即读取/写入）期间执行。可以在对I/O活动的影响有限的情况下实现该转换的充分性能。

图1是示出根据一个示例性实施方式的用于优化被部分去重复的文件的示例系统的框图图示。该示例性系统可以支持用于将诸如文件102之类的被部分去重复的文件变换成完全去重复文件的各种去重复或优化机制。在一个示例性实施方式中，文件102包括未去重复的数据104和去重复的部分（即块）的组合。未去重复的数据104包括部分召回的数据和/或仍须去重复的数据。例如，应用114可以修改部分召回的数据和/或向文件102添加新数据。

一般而言，当文件被完全去重复时，该文件与元数据106相关联，该元数据106包括将该文件在块存储110中的块（例如，C3、C6和C7）映射回该文件的逻辑表示的去重复（去重）元数据108。如果文件102在去重复进程期间被分区成子文件分区，则文件102还包括分区表118，所述分区为每个子文件区分维护文件偏移量、并且为子文件分区内的任何分区维护文件偏移量。如在此所述，分区表118可以包括与子文件分区相对应的文件范围的分层结构。

块存储元数据112包括散列索引以保证块存储110不存储重复的块。一般而言，当应用114修改现有数据或者向文件写入新数据时，（例如在文件系统过滤器中实现的）去重复机制116访问块存储110中的一个或多个所引用的块，酌情在任何解压缩以后作为所召回的文件数据返回所述一个或多个所引用的块，并且将所召回的文件数据存储在未去重复的数据104中。

存在致使文件102从处于完全去重复状态变为未去重复/部分去重复状态的各种操作。这包括：用户或进程向文件写入，使得位于写入文件偏移量位置处的经修改的文件数据不再与先前包含该数据的块相匹配。完全召回整个文件以支持这样的文件修改常常是低效的（例如对于非常大的文件的小修改而言）。

仅仅召回相关块使文件102处于部分去重复状态，在该状态下，文件102包括某些所召回的文件数据、以及对还未被召回的块的引用。例如，在图1中考虑：应用114仅仅召回块C7并且将其写入到其相应数据。文件102把所召回的块数据包含在被写入操作修改的未去重复的数据104中。去重复元数据108被更新以反映该部分召回状态，以便得知文件102包含了所召回的数据以及不再映射到现在过期的块C7。

在一个示例性实施方式中，去重复元数据108跟踪：文件102的哪个或哪些部分已经被召回、以及哪些部分作为去重复的块保留在块存储110中。文件因此可存在于非去重复状态、部分去重复（部分召回）状态或完全去重复（即，优化）状态中。文件可以在各种场景中处于部分去重复状态。例如，用户可能已经在适当位置处修改了某些文件范围。去重复机制116还可以召回更多数据以使用户写入与块边界、稀疏文件边界（在一个实施方式中是各自为六十四（64）KB的固定块）、或任何其他边界对齐。作为另一示例，去重复机制116优化子文件分区，截去相关联的文件范围并且要么由于暂停指令、要么因为系统崩溃而必须在去重复进程期间停止。在又一示例中，去重复机制116对文件的之前版本进行去重复，然后用户用新数据来扩展该文件。

在一个实施方式中，去重复机制116执行各种跟踪操作，包括在去重复元数据108中维护关于文件的哪些部分已经被召回以及哪些部分被保留在块存储110中的跟踪数据。在一个示例性实施方式中，根据

NTFS配置，跟踪数据被维护在NTFS重解析点中，NTFS重解析点还用于向去重复机制116通知文件被部分去重复。在其它使用场景中，解析点是公知的且不在此处详细描述。注意到，重解析点仅是一个备选；可为跟踪目的替换地使用其它元数据/流。

在一个示例性实施方式中，去重复机制116根据去重复策略120执行去重复进程。这样的策略包括用于确定对文件102何时启动、停止和/或恢复去重复进程的各种标准。例如，去重复机制116可以在对文件102的修改之后流逝了某段时间时或者在主机变为空闲时启动去重复进程。作为另一示例，去重复机制116可以在新块超过某个大小时或者在主机变为非空闲或者需要关闭时停止去重复进程并提交新块。作为又一示例，去重复机制116可以在完成对未去重复的数据104的分块以后或者在完成对子文件分区之一的分块以后将新块提交给块存储112。

图2是表示根据一个示例性实施方式的去重复机制116的示例性组件的框图。在该示例性实施方式中，示例性组件在对文件202执行去重复进程期间作为顺序阶段操作。

如在此所述，去重复进程将部分去重复的文件或未去重复的文件变换成完全去重复的文件。这包括标识阶段204，该阶段扫描文件202并且确定哪些文件被部分去重复。在一个示例性实施方式中，去重复机制116检查各个去重复元数据并且检测处于部分召回状态的文件。去重复元数据可以包括重解析指向一个或多个流图的数据。如果块存储中的块的组合大小小于文件大小或者文件范围位图指示一个或多个未去重复部分，则该文件处于部分去重复状态。然后，去重复机制116检索定义文件范围的流图以获得被去重复的部分以及未去重复的部分。每个部分都可以对应于起始文件偏移量和大小，根据所述起始偏移量和大小，去重复机制116计算出结束文件偏移量。文件范围不重叠，并且从开始到结尾覆盖整个文件。

在一个示例性实施方式中，去重复机制116标识出涵盖未去重复的部分的文件范围的块。例如，应用可能已经召回了这些块并且修改了一个或多个各个部分以将该文件置于部分召回状态。对齐阶段206修改与这些块相关联的块边界以防止这些新块和与被去重复的部分相关联的块边界重叠。如在此所解释的那样，对齐阶段206还引导分块组件在特定文件偏移量处开始分块阶段208并且在另一文件偏移量处终止分块阶段208。

在分块阶段208期间，可以根据试探法来选择诸如ChA₁-ChA_m之类的分块算法，所述试探法可以涉及诸如文件扩展名、头信息等等之类的属性。例如，可为一个文件选择通用分块算法，而另一文件可具有专用于其文件扩展名的分块算法（诸如用于ZIP部分的分块算法）。还可以基于来自标识阶段204的提示或者基于内部反馈220或外部反馈222来选择分块算法。

分块阶段208（其在给定实施方式需要时可以包括或遵循文件解压缩）根据所选择的算法将文件内容分解成块，其中所述算法可以增加每个文件的内容在另一文件中重复的概率，然后这些块可以在之后被压缩。可通过如下方式来执行分块：根据文件的结构、内容驱动的算法（例如将媒体文件划分成媒体头和媒体正文，该媒体正文进而可被分层地拆分成一系列部分）；或者使用基于在滑动窗上重复计算的快速散列化技术（这样的快速散列函数包括CRC和Rabin函数族）来对文件内容分块的算法，其中块是在散列函数和当前块大小/内容满足特定标准时被选择的。

分块阶段208的结果包括（每文件的）块列表232，所述块是使用一组“块记录”来传递的，这些块记录中的每个都包含描述块中的数据类型的相关联元数据。这样的元数据的一个示例是作为分块算法的执行的一部分来计算的任何滚动散列。另一示例是块内的实际数据的压缩级别的指示符（例如ZIP分块模块将指示压缩选择器模块不压缩可能已被压缩的块）。注意：对于所托管的进程执行，块被插入到恰当的“输出队列”以用于处理，并在然后被批量地发送给去重复进程。

可批量处理的块被下一阶段、即去重复检测阶段210消费，该去重复检测阶段210通过散列唯一地标识每个块，然后将该散列用于去重复检测。在分块之后，去重复检测阶段210确定块存储中是否已存在所述块。计算出针对块计算的强散列以在散列索引服务中调用查找操作。散列索引服务对已为去重复系统所知或已被存储在块存储218内的唯一块中的一些或全部的散列进行索引化。

块存储模块218维护实际块的持久数据库。分块阶段208支持：将新块插入到块存储218（如果还不存在这样的块）中；将引用数据添加到块存储中的现有块（在检测到先前持久存储的块以后）；以及提交一组块插入和/或块引用添加。块存储218还可实现各种后台/维护作业，包括垃圾收集、数据/元数据检查等等。

元数据创建阶段212生成去重复元数据和块存储元数据，以考虑到已经被分块阶段208定义的新块。在维护每文件的块存储元数据（比如流图）的示例性实施例中，去重复机制116通过将原始块存储元数据和新块元数据相组合来重构这样的元数据。另外，元数据创建阶段212更新去重复元数据以映射到与新块相关联的块存储元数据。

在一个示例性实施方式中，去重复机制116保留来自旧的流图的未改变的块定义，并且将这些定义添加到新的流图。对于与对齐的未去重复部分相对应的新块，去重复机制116将相应定义添加到新流图并且随后跳过旧的流图的任何过时的定义。基本上，新的流图是通过缝合旧的流图和新块元数据而创建的。去重复机制116将新的流图添加到块存储元数据并且删除旧的流图。或者，去重复机制116用新块元数据更新旧的流图而不是创建新的流图并删除旧的流图。

在另一示例性实施方式中，去重复元数据可以包括分区表，该分区表包括与块和子文件分区相关联的文件范围的分层结构。该分层结构可以直接映射到一组子文件分区。一个示例包括指向一组二级流图的顶级流图。另一示例包括流图的多级组织。另一示例包括使用预定义的、固定大小的子文件分区，这通过将文件偏移量除以固定的子文件分区大小来实现文件偏移量到特定子文件分区的转换，而无需咨询顶级流图。

在另一示例性实施方式中，去重复机制116将引用计数、而不是流图用作元数据的一部分。去重复机制116针对不再被给定文件引用的任何块递减引用计数，并且针对与对齐的未去重复部分相对应的任何新近引用的块递增引用计数。

如在此所述，当在同一去重复进程中从一个阶段转移到另一阶段时，去重复机制116可以将新块定义添加到原始流图，而不是创建新的流图。在一个示例性实施方式中，去重复机制116将新块定义追加到该文件的原始流图。在另一示例性实施方式中，去重复机制116将原始流图分割成一系列部分流图，其中每个部分流图都对应于在提交阶段216期间被处理的子文件分区。

如果去重复进程在优化子文件分区时处理暂停指令，则去重复机制116创建新的流图，所述新的流图包括新块元数据以及与去重复的部分相关联的定义。当分块阶段208恢复对未去重复部分的分块时，新的流图取代原始流图。在提交阶段216期间，重解析数据现在引用新的流图，这允许原始流图被回收。

如果文件处于部分召回状态并且去重复进程被暂停，则在恢复指令以后创建的新的流图不取代原始流图。在一个示例性实施方式中，部分召回的文件引用两个流图。在另一示例性实施方式中，部分召回的文件继续仅仅引用旧的流图。去重复机制116在提交阶段216期间避免文件截去。当最后一个子文件分区被去重复时，新的流图取代原始流图。

在将新块添加到块存储218以前，可以参照压缩阶段214处理这些新块。压缩算法选择器处理文件和块元数据，并且可以尝试确定对于此类型数据，哪个压缩算法CA₁-CA_n （若有的话）工作得最好。在执行任何压缩以后，运行时可以验证是否进行了任何显著的节省。例如，如果经压缩的块大于其未经压缩的形式，则新块以未经压缩的形式存储（或者可以利用不同算法再次尝试压缩）。压缩算法可基于策略、文件类型等等来选择。

提交阶段216用指向块存储218内的已去重复数据的引用来替代每个文件。为此目的，去重复机制116接收其块已被插入到块存储中的文件的列表。在一个实现中，每个块列表都被封装到块ID流（由唯一的流ID来标识）中，其被持久保存到与文件相关联的重解析点。在提交阶段216期间，去重复机制116用诸如重解析点之类的跟踪数据来替代该文件，所述跟踪数据包含该ID和块流ID的定位器，也就是说，包含流图的块，包括用于组装当前文件以及它们的逻辑偏移量的块的列表。

图3A－图3C示出了包括至少一个未去重复的部分的各个示例文件，所述未去重复的部分根据一些示例性实施方式被变换成完全去重复的文件。

图3A示出了具有如下块的部分召回的文件：所述块在文件偏移量302处开始、在文件偏移量304处结束，并且包括在文件偏移量308处开始的未去重复的部分306。每个块都为六十四（64）KB的相同大小，但是其他块大小处于本公开的范围内。在一个示例性实施方式中，去重复机制116在文件偏移量302处开始分块阶段。在另一示例性实施方式中，去重复机制116在文件偏移量308处开始分块阶段，该分块阶段定义了小于六十四（64）KB的新块310。去重复机制116将新块的块边界修改为与同之前去重复的部分相关联的块边界对齐。

图3B示出了具有如下块的部分召回的文件：所述块在文件偏移量312处开始、在文件偏移量312处结束，并且包括在文件偏移量318处结束的未去重复的部分316。在一个示例性实施方式中，去重复机制116在文件偏移量318处终止分块阶段，该分块阶段定义了小于六十四（64）KB的新块316。在另一示例性实施方式中，去重复机制116在文件偏移量314处终止分块阶段，使得新块与同随后的去重复的部分相关联的块边界对齐。根据另一实施方式，去重复机制116可以继续超出文件偏移量314的分块阶段，直到与具有随后的去重复的部分的块对齐。

在另一示例性实施方式中，去重复机制116继续超出文件偏移量314的分块阶段，但是使用阈值来确定何时终止分块阶段。如果在该阈值内未实现与具有随后的去重复部分的块对齐，则去重复机制116定义类似于块320的新块，所述新块小于六十四（64）KB并且导致所需的对齐。在一个示例性实施方式中，去重复机制基于固定的块大小（例如六十四（KB）至一百二十八（128）KB）或者块的总数来计算该阈值。

图3C示出了部分去重复的文件，该文件被分区成子文件分区322、子文件分区324和子文件分区326。去重复元数据为这些子文件分区维护文件偏移量。分阶段地对部分去重复的文件执行去重复，其中每个子文件分区都在单独的阶段被分块并且提交给块存储。然后，去重复机制更新去重复元数据并且截去部分去重复的文件以避免保留特定子文件分区的两个副本。在每个阶段以后，未去重复的部分的大小减小。当最后一个子文件分区被提交时，部分去重复的文件被变换成完全去重复的文件。

在一个示例性实施方式中，去重复机制116在对子文件分区322去重复时处理暂停指令，并且在文件偏移量328处停止去重复进程。当接收到恢复指令时，去重复机制116在文件偏移量328处重启去重复进程。在将形成子文件分区322的块提交给块存储并且更新元数据以后，去重复机制116删除子文件分区322并且继续对子文件分区324去重复。如在此所述那样，一旦子文件分区324被去重复，则去重复进程就终止，因为不再存在剩余的未去重复的部分。

图4A－图4B示出了根据一个示例性实施方式的去重复元数据。在图4A中所表示的一个示例性实施方式中，去重复元数据包括文件402和文件404。文件402包括引用流图408的跟踪数据406。类似地，文件404包括引用流图412的跟踪数据410。两个流图都对应于块存储414内的块。如所示那样，流图408定义形成文件402的块C2－C4和块C6。类似地，流图412定义形成文件404的块C1－C5。

如果诸如块C5之类的特定块被召回并且一部分随后被应用修改（未去重复），从而致使文件404变为部分去重复的文件，则去重复机制116定义涵盖块C5的一个或多个新块。然后，去重复机制116更新流图412或者创建新流图以替换流图412。在两个实施方式任一中，去重复元数据现在映射到一个或多个新块而不是块C5。例如，如果去重复机制116创建与块C6匹配的新块，则更新后的或新的流图包括映射到块存储414中的块C6的新定义。

在图4B中大体上示出的一个实施方式中，NTFS重解析点440包括用于引用流图的指针442、以及用于跟踪具有未去重复部分的块的位图结构444。重解析点440可以是跟踪数据406或跟踪数据410的体现。更具体而言，为了部分召回文件，去重复机制116创建文件的虚拟视图，其中分块阶段在预定边界处（比如在64K边界处）执行。去重复机制116在重解析点440中的位图结构444中维护该视图，其中在一个实施方式中，位图结构444中的经置位的位指示块已经被召回到去重复的文件，而0位指示该块驻留在块存储中。在设置重解析点440时，可添加块的大小。

注意，数据在一个时间被召回，而位图结构444在另一时间更新，这导致可能的与崩溃相关的不一致性。如此处所述的，当将数据提交（例如转储清除）到稳定存储（例如，盘等）时，对操作的排序使得系统为崩溃一致的。更具体而言，位图结构444的改变仅在它所表示的相应数据被转储清除到盘之后才被转储清除到盘上。以此方式，直到数据已知被安全地转储清除到盘上，位图结构444才指示该数据已经被部分召回。注意，如果盘和文件系统支持通写（write-through），则可以替代于转储清除而使用通写。注意，尽管通常使用将文件数据/元数据转储清除到盘作为此处的示例，但这仅是示例。因此，“提交到稳定存储”还包括文件系统和存储介质通写的概念、以及使用文件系统和存储介质转储清除的概念、或者用于保证安全地将数据写入到稳定存储的任何其他手段。

在一个示例性实施方式中，可使用位图结构444来高效地将部分召回的文件转回完全去重复的文件。为此目的，当扫描文件以进行去重复时，可使用跟踪数据，使得向去重复机制116仅仅提供部分召回的文件范围（即未去重复的部分）以用于去重复。当包括这些部分召回的文件范围的新块被添加到块存储时，包括重解析点440的去重复元数据被调整为反映：部分召回的文件范围现在是经优化的块并且不再是部分召回的范围。

图5是示出了根据一个示例性实施方式用于将具有至少一个未去重复部分的文件变换成完全去重复的文件的步骤的流程图。图5所示的步骤始于步骤502，并且前进到步骤504，在该步骤，去重复机制116标识出部分召回的文件，该文件被分区成块。步骤506示出了使用与该文件相关联的元数据（比如去重复元数据和块存储元数据）来标识出一个或多个未去重复的部分。如在此所述，根据一个或多个示例性实施方式，去重复机制116可以检查重解析点内的召回位图，并且确定召回文件范围以及涵盖这些文件范围的块的位置。

步骤508表示关于是否消除任何去重复的部分的块边界的判定。在一个示例性实施方式中，由于未去重复的部分需要与包括去重复部分的块的块边界对齐，因此两个未去重复部分之间的小的去重复部分导致要在分块阶段期间定义小块。如果部分召回的文件包括小的去重复的部分，则图5中所述的方法前进到步骤510。另一方面，如果不存在要消除的去重复部分，则图5中所述的方法前进到步骤512。

步骤510针对将两个或更多未去重复的部分组合成一个未去重复的部分，该未去重复的部分作为召回数据的单个文件范围被去重复，这可能需要从块存储读取块以填充未去重复的部分之间的空隙。在执行步骤510之后，图5中所述的步骤继续到步骤512。

步骤512针对确定检查未去重复的部分。在一个示例性实施方式中，去重复机制116标识出包括或涵盖未去重复的部分的块。在一个示例性实施方式中，去重复机制116标识出该文件内的第一或最早的未去重复部分，并且定义与至少一个去重复部分内的周围块的块边界对齐的新块。步骤514表示至少一个如下的块的定义：所述块在先于或等于与未去重复部分相关联的起始文件偏移量的一文件偏移量处开始，并且在后继于或等于与未去重复部分相关联的结束文件偏移量的一文件偏移量处终止。

步骤516针对关于是否对部分召回文件的下一未去重复部分进行去重复的判定。如果不再存在未去重复的部分，则图5中所述的方法前进到步骤518。另一方面，如果存在附加的未去重复部分，则图5中所述的方法返回到步骤512。步骤518示出了与部分召回文件的至少一个去重复部分的文件偏移量对齐的块边界的确定。在一个示例性实施方式中，所述至少一个块中的最后一个块具有与所述至少一个去重复部分的后继块的块边界不重叠的块边界。类似地，所述至少一个块中的第一块具有与所述至少一个去重复部分的之前块的块边界不重叠的块边界。

步骤520涉及为至少一个块创建元数据并且将所述至少一个块提交给块存储。在一个示例性实施方式中，去重复机制116创建部分召回文件的文件偏移量与所述至少一个块的块边界之间的映射。然后，去重复机制116将这些映射与所述至少一个去重复部分的块边界相组合，并且创建块存储元数据，所述块存储元数据替换该文件的之前的块存储元数据。在替换实施方式中，去重复机制116使用这些映射更新去重复元数据（例如重解析点、流id和/或位图等等）和块存储元数据（例如流图）。在存储所述至少一个块以前，去重复机制116检查与块存储相关联的散列索引以确定所述块中是否有任何块已经存储在该块存储中。

在另一替换的实施方式中，去重复机制116在对下一去重复部分分块之前执行步骤518和步骤520。例如，在执行步骤516以前，去重复机制116中止去重复进程，用块边界更新块存储元数据，将所述至少一个块提交给块存储，并且通过删除未去重复的部分来截去部分召回的文件。去重复机制116可以如图6所示响应于暂停指令而中止去重复进程。

在又一替换的实施方式中，去重复机制116基于去重复策略中止去重复进程。作为示例，去重复机制116在标识出下一未去重复部分以及定义具有这样的部分的至少一个块之前使用各种标准来提交与未去重复部分相关联的至少一个块。

步骤522针对从块存储中删除未被引用的块。例如，这些块不再与包括部分召回文件在内的任何文件的流图相关联。对于采用引用计数的实施方式，去重复机制针对所述至少一个块递减引用计数。如果任何所得到的引用计数等于0，则每个相对应的块都被回收和删除。步骤524终止图5所描述的方法的步骤。

图6是示出了根据一个示例性实施方式用于对被分区成子文件分区的文件进行去重复的步骤的流程图。图6所示的步骤始于步骤602，并且前进到步骤604，在该步骤，去重复机制116处理文件。步骤606针对将该文件分区成子文件分区。在一个示例性实施方式中，一次对文件全部去重复需要大量时间。因此，去重复机制116将该文件划分成大小相等的子文件分区，所述子文件分区一次一个、而不是一起被去重复。

步骤608针对标识出具有第一去重复部分的子文件分区。如果该文件是完全未去重复的，则去重复进程在第一子文件分区处开始。如果该文件是部分去重复的，则去重复进程在与包括未去重复部分的第一子文件分区相关联的起始偏移量处开始。如在此所解释的那样，如果去重复进程在完成子文件分区以前暂停，则去重复进程在与第一未去重复部分相关联的起始偏移量处重启，因为那里是去重复进程曾经停止的地方。此外，在第一未去重复部分之前的块曾是提交给块存储的最后一个块。

步骤610针对定义具有该子文件分区的至少一个块。步骤612涉及确定去重复机制116是否接收到中止第一未去重复部分的分块的暂停指令。根据替换的实施方式，系统崩溃致使去重复进程有效地以类似方式暂停。如果去重复机制116暂停，则图6中所述的方法前进到步骤614。步骤614针对等待直到去重复进程恢复第一未去重复部分的分块。在一个示例性实施方式中，去重复机制116从文件系统接收指令，并且在第一未去重复部分的起始偏移量处重启所述至少一个的定义。另一方面，如果去重复机制116在去重复进程期间不暂停，则图6中所述的方法前进到步骤616。

步骤616针对更新去重复元数据和块存储元数据。在一个示例性实施方式中，去重复机制116用新块定义更新流图中的映射。在另一示例性实施方式中，去重复机制116使用到之前去重复的块的原始映射以及与新块定义相关联的新映射来创建新的流图。

步骤618针对截短文件并且将所述至少一个块提交给块存储。包括第一未去重复部分的子文件分区被从该文件中移除，因为相应文件数据的副本被存储在块存储中。步骤620针对确定是否对下一子文件分区进行去重复。如果该文件中不再存在子文件分区，则图6中所述的方法前进到步骤622。另一方面，如果存在附加的子文件分区，则图6中所述的方法返回到步骤608。步骤622终止图6所描述的方法的步骤。

示例性联网以及分布式环境

本领域技术人员可以理解，此处描述的各实施例和方法可结合任何计算机或其它客户机或服务器设备来实现，其可被部署为计算机网络的部分或在分布式计算环境中，并且可以被连接到任何类型一个或多个数据存储。在这一点上，此处描述的各实施例可在具有任何数量的存储器或存储单元的、并且任何数量的应用和进程跨任何数量的存储单元发生的任何计算机系统或环境中实现。这包括但不限于具有部署在具有远程或本地存储的网络环境或分布式计算环境中的服务器计算机和客户机计算机的环境。

分布式计算通过计算设备和系统之间的通信交换提供了计算机资源和服务的共享。这些资源和服务包括信息的交换、对于诸如文件等对象的高速缓存存储和盘存储。这些资源和服务还包括多个处理单元之间的处理能力共享以便进行负载平衡、资源扩展、处理专门化，等等。分布式计算利用网络连接，从而允许客户机利用它们的集体力量来使整个企业受益。就此，各种设备可具有可如参考本发明的各实施例描述地参与资源管理机制的应用、对象或资源。

图7提供了示例性的联网或分布式计算环境的示意图。该分布式计算环境包括计算对象710、712等以及计算对象或设备720、722、724、726、728等，这些计算对象或设备可包括如由示例应用730、732、734、736、738表示的程序、方法、数据存储、可编程逻辑等。可以理解，计算对象710、712等以及计算对象或设备720、722、724、726、728等可包括不同的设备，诸如个人数字助理（PDA）、音频/视频设备、移动电话、MP3播放器、个人计算机、膝上型计算机等。

每一个计算对象710、712等以及计算对象或设备720、722、724、726、728等可通过通信网络726直接或间接与一个或多个其他计算对象710、712等以及计算对象或设备720、722、724、728、740等进行通信。尽管在图7中被示为单个元件，但通信网络740可包括向图7的系统提供服务的其他计算对象和计算设备和/或可表示未示出的多个互连网络。每个计算对象710、712等或计算对象或设备720、722、724、726、728等还可以包含应用，诸如可以利用API或其他对象、软件、固件和/或硬件的、适于根据本发明的各实施例所提供的应用实现与其进行通信的应用730、732、734、736、738。

存在支持分布式计算环境的各种系统、组件和网络配置。例如，计算系统可由有线或无线系统、本地网络或广泛分布的网络连接在一起。当前，许多网络被耦合至因特网，后者为广泛分布的计算提供了基础结构并包含许多不同的网络，但任何网络基础结构都可用于便于与如各实施例中所描述的系统的示例性通信。

由此，可使用诸如客户机/服务器、对等、或混合体系结构之类的网络拓扑结构和网络基础结构的主机。“客户机”是使用与它无关的另一类或组的服务的一个类或组中的成员。客户机可以是进程，例如，大致上是请求另一程序或进程所提供的服务的一组指令或任务。客户机进程利用所请求的服务，而不必“知道”有关其他程序或服务本身的任何工作细节。

在客户机/服务器体系结构中，尤其在联网系统中，客户机通常是访问另一计算机（例如，服务器）所提供的共享网络资源的计算机。在图7的图示中，作为非限制性示例，计算对象或设备720、722、724、726、728等可被认为是客户机而计算对象710、712等可被认为是服务器，其中计算对象710、712等担当提供数据服务的服务器，诸如从客户机计算对象或设备720、722、724、726、728等接收数据、存储数据、处理数据、向客户机计算对象或设备720、722、724、726、728等发送数据，但任何计算机都可取决于环境而被认为是客户机、服务器、或两者。

服务器通常是可通过诸如因特网或无线网络基础结构之类的远程网络或本地网络访问的远程计算机系统。客户机进程可在第一计算机系统中活动，而服务器进程可在第二计算机系统中活动，它们通过通信介质相互通信，由此提供分布式功能并允许多个客户机利用服务器的信息收集能力。

在其中通信网络740或总线例如是因特网的网络环境中，计算对象710、712等可以是其他计算对象或设备720、722、724、726、728等通过诸如超文本传输协议（HTTP）等多种已知协议中的任一种与其通信的web服务器。担当服务器的计算对象710、712等还可用作客户机，例如计算对象或设备720、722、724、726、728等，这是分布式计算环境的特性。

示例性计算设备

如上所述，有利地，本文所描述的技术可应用于任何设备。因此，应当理解，构想了结合各实施例使用的所有种类的手持式、便携式和其它计算设备和计算对象。因此，以下在图8中所述的通用远程计算机只是计算设备的一个示例。

各实施例可部分地经由操作系统来实现，以供设备或对象的服务开发者使用和/或被包括在用于执行此处所述的各实施例的一个或多个功能方面的应用软件内。软件可以在由诸如客户端工作站、服务器或其它设备等一个或多个计算机执行的诸如程序模块等计算机可执行指令的通用上下文中描述。本领域的技术人员可以理解，计算机系统具有可用于传递数据的各种配置和协议，并且由此没有特定配置或协议应当被认为是限制性的。

图8由此示出了其中可实现本文所述的各实施例的一个或多个方面的合适的计算系统环境800的一个示例，尽管如上所述，计算系统环境800仅为合适的计算环境的一个示例，并非对使用范围或功能提出任何限制。此外，也不应当将计算系统环境800解释为对在示例性计算系统环境800中所示的组件中的任何一个或其组合有任何依赖。

参考图8，用于实现一个或多个实施例的示例性远程设备包括计算机810形式的通用计算设备。计算机810的组件可包括，但不限于，处理单元820、系统存储器830、以及将包括系统存储器的各种系统组件耦合到处理单元822的系统总线820。

计算机810通常包括各种计算机可读介质，并且可以是可由计算机810访问的任何可用介质。系统存储器830可包括诸如只读存储器（ROM）和/或随机存取存储器（RAM）之类的易失性和/或非易失性存储器形式的计算机存储介质。作为示例而非限制，系统存储器830还可包括操作系统、应用程序、其他程序模块、以及程序数据。

用户可通过输入设备840向计算机810输入命令和信息。监视器或其他类型的显示设备也经由诸如输出接口850之类的接口连接到系统总线822。除监视器以外，计算机还可包括诸如扬声器和打印机之类的其他外围输出设备，它们可通过输出接口850连接。

计算机810可使用到一个或多个其他远程计算机（诸如远程计算机870）的逻辑连接在联网或分布式环境中操作。远程计算机870可以是个人计算机、服务器、路由器、网络PC、对等设备或其他常见网络节点、或者任何其他远程媒体消费或传输设备，并且可包括以上关于计算机810所述的任何或全部元件。图8所示的逻辑连接包括诸如局域网（LAN）或广域网（WAN）之类的网络872，但也可包括其他网络/总线。这些联网环境在家庭、办公室、企业范围的计算机网络、内联网和因特网中是常见的。

如上所述，尽管结合各种计算设备和网络体系结构描述了各示例性实施例，但基本概念可被应用于其中期望改进资源使用的效率的任何网络系统和任何计算设备或系统。

而且，存在实现相同或相似功能的多种方法，例如适当的A PI、工具箱、驱动程序代码、操作系统、控件、独立或可下载软件对象等，它们使得应用和服务能够使用此处提供的技术。由此，此处的各实施例从API（或其他软件对象）的观点以及从实现如此处描述的一个或多个实施例的软件或硬件对象构想。由此，此处所述的各实施例可具有完全采用硬件、部分采用硬件并且部分采用软件、以及采用软件的方面。

本文中所使用的词语“示例性”意味着用作示例、实例、或说明。为避免疑惑，本文所公开的主题不限于这些示例。另外，在此所述的被描述为“示例性”的任意方面或设计并不一定要被解释为相比其它方面或设计更优选或有利。此外，在使用术语“包括”、“具有”、“包含”和其他类似词语的程度上，为避免疑惑，这些术语旨在当用于权利要求中时以类似于术语“包括”作为开放的过渡词的方式是包含性的而不排除任何附加或其他元素。

如所述的，此处所述的各种技术可结合硬件或软件或，在适当时，以两者的组合来实现。如此处所使用的，术语“组件”、“模块”、“系统”等同样旨在指计算机相关实体，或者是硬件、硬件和软件的组合、软件或者是执行中的软件。例如，组件可以是，但不限于是，在处理器上运行的进程、处理器、对象、可执行码、执行的线程、程序和/或计算机。作为说明，在计算机上运行的应用和计算机都可以是组件。一个或多个组件可以驻留在进程和/或执行线程中，并且组件可以位于一个计算机内和/或分布在两个或更多计算机之间。

如前所述的系统已经参考若干组件之间的交互来描述。可以理解，这些系统和组件可包括组件或指定的子组件、某些指定的组件或子组件和/或附加的组件，并且根据上述内容的各种置换和组合。子组件还可作为通信地耦合到其他组件的组件来实现，而不是被包括在父组件内（层次性）。另外，应注意到一个或多个组件可被组合成提供聚集功能的单个组件，或被分成若干单独的子组件，且诸如管理层等任何一个或多个中间层可被设置成通信耦合到这样的子组件以便提供集成功能。此处所述的任何组件也可与一个或多个此处未专门描述的但本领域技术人员一般已知的其他组件进行交互。

鉴于本文所述的示例性系统，可根据参考各附图的流程图还可理解根据所述的主题来实现方法。尽管为了说明简洁起见，作为一系列框示出和描述的方法，但是应当理解，各实施例不仅仅限于框的次序，因为一些框可以与此处所描绘和描述的框不同的次序发生和/或与其他框并发地发生。尽管经由流程图示出了非顺序或分支的流程，但可以理解，可实现达到相同或类似结果的各种其他分支、流程路径和框的次序。此外，某些示出的框在实现下文所述的方法中是可选的。

结语

尽管本发明易于作出各种修改和替换构造，但其某些说明性实施例在附图中示出并在上面被详细地描述。然而应当了解，这不旨在将本发明限于所公开的具体形式，而是相反地，旨在覆盖落入本发明的精神和范围之内的所有修改、替换构造和等效方案。

除此处所述的各实施例以外，应当理解，可使用其他类似实施例，或者可对所述实施例作出修改和添加以便执行对应实施例的相同或等效功能而不背离这些实施例。此外，多个处理芯片或多个设备可共享此处所述的一个或多个功能的性能，并且类似地，存储可跨多个设备实现。因此，本发明不应限于任何单个实施例，而是应当根据所附权利要求书的广度、精神和范围来解释。

Claims

1.一种在计算机环境中至少部分在至少一个处理器上执行的方法，包括：将具有至少一个未去重复的部分（104）的文件（102）重新优化成完全去重复的文件（402，404），包括处理（506）所述文件的每个未去重复的部分以确定至少一个块（310，320）；将所述至少一个块提交（520）给块存储（110）；以及将与所述文件相关联的元数据（106）修改（616）为包括对每个块的引用。

2.如权利要求1所述的方法，其特征在于，还包括：将所述文件中被去重复的部分隔开的两个未去重复的部分组合成包括每个未去重复的部分和所述去重复的部分的单个未去重复的部分，然后处理所述单个未去重复的部分。

3.如权利要求1所述的方法，其特征在于，处理至少一个未去重复的部分包括：定义从先于或等于与所述未去重复的部分相关联的起始文件偏移量的一文件偏移量开始的块；以及通过与完全包含在在先的去重复部分中的最后一个块对齐来确定所述文件偏移量。

4.如权利要求1所述的方法，其特征在于，处理至少一个未去重复的部分包括：通过在后继于或等于与所述未去重复的部分相关联的结束文件偏移量的一文件偏移量处结束所述部分的分块来定义块；以及基于所述未去重复的部分的分块与同在先的去重复的部分相关联的一个或多个现有块对齐之处来确定所述结束文件偏移量。

5.如权利要求4所述的方法，其特征在于，分块继续到超出所述未去重复的部分的结尾，并且还包括：确定块对齐是否在基于大小的阈值或基于块数目的阈值内被实现，并且如果块对齐未在所述阈值内实现，则停止分块。

6.如权利要求1所述的方法，其特征在于，还包括：暂停并随后恢复所述暂停以前的对所述文件的重新优化以及所述至少一个块到所述块存储的提交，其中所述暂停基于一个或多个标准进行，所述标准包括文件大小、执行所述重新优化的机器何时变为非空闲、以及所述机器何时将关闭。

7.如权利要求1所述的方法，其特征在于，所述块被提交给块存储，并且还包括：从所述块存储中对由于所述文件的重新优化而不再被引用的至少一个块进行垃圾收集。

8.一种在计算环境中的系统，包括去重复机制（116），所述去重复机制（116）被配置为将具有至少一个未去重复的部分（306，316）的文件（102）重新优化成完全去重复的文件（402，404），所述去重复机制被配置为：将每个未去重复的部分分块（610）成至少一个经重新优化的块（310，320）；在完全重新优化所述文件以前将至少一个经重新优化的块提交（520）到块存储（110）中；以及修改（616）表示被提交的文件的每个块的文件元数据（106）。

9.如权利要求8所述的方法，其特征在于，所述去重复机制将所述文件分区成子文件分区，在开始重新优化下一子分区以前或者当最后一个子文件分区已经被重新优化时提交每个子文件分区的每个经重新优化的块；以及基于哪个子文件分区已经被重新优化来截短所述文件。

10.一个或多个具有计算机可执行指令的计算机可读介质，所述计算机可执行指令在被执行时执行以下步骤，包括：

为文件（102）的未去重复的部分（306，316）定义（514）块（310，320）；

使所述块的块边界与同所述文件的至少一个去重复的部分相关联的文件偏移量（302，308）对齐（518）；

基于所述块边界更新（520）与所述文件相关联的元数据（106）；以及

将所述块提交（520）给块存储（110）。