在文件存储系统中使用检查点管理去复制的系统和方法

摘要

一种去复制系统以及方法，涉及基于软件的系统和基于硬件的系统之间的交互，其中，基于软件的系统管理整个后台去复制处理，而基于硬件的系统包括基于硬件的文件系统管理器和哈希生成器。文件系统检查点机制被改变，以管理后台去复制处理，并且还降低关于识别用于去复制的候选组块以及处理该组块的处理复杂性。

说明书

技术领域

本发明总体上涉及文件存储系统，尤其涉及文件存储系统中的去复制。

背景技术

去复制(deduplication)是一种用于提高存储利用率的机制。它主要包括 识别数据存储系统中的重复的数据组块(chunk)并消除重复件，同时只保持 该数据的单个拷贝以及该单个拷贝的参考。其中，去复制减少了例如在磁盘上 和/或固态存储器上存储数据所需的空间的量。

发明内容

在第一示例性实施例中，提供了一种去复制文件存储系统中的数据的方法， 所述文件存储系统运行活动的文件系统，所述文件存储系统具有基于软件的系 统以及基于硬件的系统，所述基于软件的系统包括被配置为与去复制检测/索 引引擎接口的基于软件的去复制管理器，所述基于硬件的系统包括基于硬件的 文件系统管理器以及哈希生成器，所述活动的文件系统由一系列检查点进行描 绘。所述方法涉及：由所述基于软件的去复制管理器制作所述文件系统的快照 拷贝；由所述基于软件的去复制管理器确定用于去复制的检查点范围；由所述 基于软件的去复制管理器基于所述检查点范围在所述快照拷贝中识别候选组 块；由所述基于软件的去复制管理器向所述基于硬件的文件系统管理器请求， 使用所述哈希生成器哈希所述候选组块，所述基于硬件的文件系统管理器向所 述基于软件的去复制管理器返回所述候选组块的哈希值以及组块元数据；由所 述基于软件的去复制管理器向所述去复制检测/索引引擎发送所述候选组块的 哈希值，以及当所述候选组块匹配先前索引的组块时，由所述基于软件的去复 制管理器从所述去复制检测/索引引擎接收先前索引的组块的组块元数据；基 于所述先前索引的组块的组块元数据，由所述基于软件的去复制管理器向所述 基于硬件的文件系统管理器请求所述候选组块的去复制；基于所述组块元数据， 由所述基于硬件的文件系统管理器验证是否能够使用先前索引的组块在活动 的文件系统中去复制所述候选组块；并且一旦确定能够使用先前索引的组块在 活动的文件系统中去复制所述候选组块，则使用与先前索引的组块相关联的对 应的指针来替换与所述候选组块相关联的多个指针中的每一个指针。

在第二示例性实施例中，提供了一种文件存储系统，其运行活动的文件系 统，所述活动的文件系统由一系列检查点进行描绘。所述文件存储系统包括： 基于软件的系统，包括被配置为与去复制检测/索引引擎接口的基于软件的去 复制管理器；以及基于硬件的系统，包括基于硬件的文件系统管理器以及哈希 生成器。所述基于软件的去复制管理器被配置为(1)制作所述文件系统的快 照拷贝，(2)确定用于去复制的检查点范围，(3)基于所述检查点范围在所述 快照拷贝中识别候选组块，(4)请求所述基于硬件的文件系统管理器使用所述 哈希生成器哈希所述候选组块，所述基于硬件的文件系统管理器向所述基于软 件的去复制管理器返回所述候选组块的哈希值以及组块元数据，(5)向所述去 复制检测/索引引擎发送所述候选组块的哈希值，并且当所述候选组块匹配先 前索引的组块时，从所述去复制检测/索引引擎接收先前索引的组块的组块元 数据，并且(6)请求所述基于硬件的文件系统管理器基于所述先前索引的组 块的组块元数据，去复制所述候选组块。所述基于硬件的文件系统管理器被配 置为(1)基于所述组块元数据，验证是否能够使用先前索引的组块在活动的 文件系统中去复制所述候选组块；并且(2)一旦确定能够使用先前索引的组 块在活动的文件系统中去复制所述候选组块，则使用与先前索引的组块相关联 的对应的指针来替换与所述候选组块相关联的多个指针中的每一个指针。

在各种可选实施例中，所述候选组块包括来自给定的文件系统对象的单一 文件系统块(block)，或者包括来自给定的文件系统对象的多个文件系统块。

在各种可选实施例中，验证是否能够在活动的文件系统中去复制所述候选 组块至少部分基于与所述候选组块相关联的检查点编号以及与先前索引的组 块相关联的检查点编号，和/或至少部分基于与先前索引的组块的块相关联的 参考计数。

在各种可选实施例中，所述使用与先前索引的组块相关联的对应的指针来 替换与所述候选组块相关联的多个指针中的每一个指针包括：增加与每个对应 的指针相关联的参考计数。

在各种可选实施例中，所述基于所述检查点范围在所述快照拷贝中识别候 选组块包括：检查文件系统对象的根节点中的创建检查点；并且至少部分基于 所述创建检查点来确定所述文件系统对象是否包括任何候选组块。所述确定所 述文件系统对象是否包括任何候选组块包括：当所述创建检查点处于检查点范 围之内并且所述文件系统对象不是克隆的对象时，确定与所述文件系统对象相 关联的所有组块是候选组块；当所述创建检查点处于检查点范围之内并且所述 文件系统对象是克隆的对象时，遍历对象树结构以识别已经脱离从中克隆所述 文件系统对象的原始对象的任何组块；并且当所述创建检查点超出检查点范围 时，遍历对象树结构以识别在检查点范围内具有修改检查点的任何组块。或者， 所述确定所述文件系统对象是否包括任何候选组块包括：当所述创建检查点处 于检查点范围内，所述文件系统对象不是克隆的对象，且所述文件系统对象不 是稀疏的对象时，确定与所述文件系统对象相关联的所有组块是候选组块；当 所述创建检查点处于检查点范围内，所述文件系统对象不是克隆的对象，且所 述文件系统对象是稀疏的对象时，遍历对象树结构以识别不稀疏的任何候选组 块；当所述创建检查点处于检查点范围内，且所述文件系统对象是克隆的对象 时，遍历所述对象树结构以识别已经脱离从中克隆所述文件系统对象的原始对 象的任何候选组块；并且当所述创建检查点超出检查点范围时，遍历对象树结 构以识别在检查点范围内具有修改检查点的任何候选组块。

在各种可选实施例中，当先前索引的组块被确定为不可用于去复制时，基 于与所述候选组块相关联的组块元数据以及哈希值，索引所述候选组块。

在另一示例性实施例中，提供了一种装置，包括具有体现于其中的计算机 程序的有形的、非瞬态计算机可读介质，所述程序用于去复制文件存储系统中 的数据，所述文件存储系统运行活动的文件系统，所述活动的文件系统由一系 列检查点进行描绘，所述计算机程序包括指令，当运行于所述文件存储系统的 计算机处理器上时，该指令使得所述计算机处理器执行包括以下的处理：制作 所述文件系统的快照拷贝；确定用于去复制的检查点范围；基于所述检查点范 围在所述快照拷贝中识别候选组块；向所述基于硬件的文件系统管理器发送请 求，请求哈希所述候选组块；从所述基于硬件的文件系统管理器接收所述候选 组块的组块元数据以及哈希值；基于所述哈希值，确定所述候选组块是否是先 前索引的组块的复制件；并且当所述候选组块被确定为是先前索引的组块的复 制件时，向所述基于硬件的文件系统管理器发送请求去复制所述候选组块，所 述请求包括先前索引的组块的组块元数据。

在又一示例性实施例中，提供了一种用于去复制文件存储系统中的数据的 装置，所述文件存储系统运行活动的文件系统，所述活动的文件系统由一系列 检查点进行描绘，所述装置包括：哈希生成器；以及基于硬件的文件系统管理 器，其被配置为接收来自基于软件的去复制管理器的用于哈希候选组块的请求， 基于与所述候选组块相关联的检查点编号确定是否哈希所述候选组块，一旦确 定哈希所述候选组块，调用所述哈希生成器哈希所述组块，向所述基于软件的 去复制管理器返回所述候选组块的组块元数据以及哈希值，接收来自所述基于 软件的去复制管理器的去复制所述候选组块的请求，基于先前索引的组块验证 在活动的文件系统中是否能够去复制所述候选组块，并且，一旦使用所述先前 索引的组块确定在活动的文件系统中能够去复制所述候选组块，则使用与先前 索引的组块相关联的对应的指针来替换与所述候选组块相关联的多个指针中 的每一个指针。

在另一示例性实施例中，提供了一种用于识别在文件存储系统中去复制的 候选组块的方法，所述文件存储系统具有包括多个文件系统对象的活动的文件 系统，所述活动的文件系统由一系列检查点进行描绘，所述去复制与预先确定 的检查点范围相关。所述方法包括：检查文件系统对象的根节点中的创建检查 点；并且至少部分基于所述创建检查点，确定所述文件系统对象是否包括任何 候选组块，包括：当所述创建检查点处于检查点范围内，所述文件系统对象不 是克隆的对象，且所述文件系统对象不是稀疏的对象时，确定与所述文件系统 对象相关联的所有组块是候选组块；当所述创建检查点处于检查点范围内，所 述文件系统对象不是克隆的对象，且所述文件系统对象是稀疏的对象时，遍历 对象树结构以识别不稀疏的任何候选组块；当所述创建检查点处于检查点范围 内，且所述文件系统对象是克隆的对象时，遍历所述对象树结构以识别已经脱 离从中克隆所述文件系统对象的原始对象的任何候选组块；并且当所述创建检 查点超出检查点范围时，遍历对象树结构以识别在检查点范围内具有修改检查 点的任何候选组块。

可以公开或者要求保护额外的实施例。

附图说明

通过参考下面的具体实施方式并参照附图将更容易地理解实施例的前述 特征，其中：

图1是根据本发明的示例性实施例的文件存储系统的示意框图；

图2是根据该示例性实施例的软件/硬件架构的示意图；

图3是示出了根据本发明的示例性实施例的对象树结构的一般格式的示 意框图；

图4是示出了根据一个示例性实施例的基于软件的去复制管理器的组件 的示意图；

图5是根据本发明的某个示例性实施例的用于去复制的示意性逻辑流程 图；并且

图6是根据一个示例性实施例的用于识别候选组块的逻辑流程图。

应当指出的是，前述附图和其中所示的要素不一定绘制为一致的尺度或任 何比例。除非上下文另有说明，相同的要素用相同的附图标记表示。

具体实施方式

正如在本说明书和所附权利要求中所使用的，下列词汇具有以下所示的含 义，除非上下文另有所指：

“存储设备”是用于存储数据的设备或系统。存储设备可以包括一个或多 个电磁的或磁光的或光盘驱动器、固态存储设备或磁带。为方便起见，存储设 备有时被称为“盘”或“硬盘”。数据存储系统可以包括相同或不同类型的具 有相同或不同的存储容量的存储设备。

“RAID控制器”是这样的设备或系统，其将多个存储设备的存储容量合 并为存储空间的虚拟空间，可选地，该存储空间的虚拟空间可以被称为“系统 驱动器”(system drive，“SD”)、“逻辑单元”(logical unit，“LU”或“LUN”)、 或者是“卷”。通常，SD大于来自多个存储设备的单个存储设备、绘图空间， 并包括冗余信息，以便它能够承受一定数量的磁盘的故障而无数据丢失。在示 例性实施例中，各个SD与一个唯一的标识符相关联，该标识符以下称为“逻 辑单元标识符(logical unit identifier)”或“LUID”，并且每个SD将不超过预 定的最大大小，例如，2TB-64TB或以上。当命令被发送到SD时，RAID控 制器通常在同一时间将命令转发给SD的所有存储设备。RAID控制器有助于 克服典型存储设备的三个主要限制，即，该存储设备通常为存储系统中最慢的 组件，它们通常最有可能遭受灾难性的故障，并且它们通常具有相对较小的存 储容量。

“RAID系统”是这样的设备或系统，其包括一个或多个RAID控制器和 若干存储设备。通常，RAID系统将包含两个RAID控制器(以便如果有一个 发生故障后，另一个可以继续工作，并且当两者都正常工作时，分担负载)和 几十个存储设备。在示例性实施例中，RAID系统通常被配置有2-32个SD。 当文件服务器需要存储或取得数据时，它将命令发送到RAID系统的RAID控 制器，其中，RAID控制器依次地负责向前路由命令至单个存储设备，并且根 据需要存储或取得数据。通过一些RAID系统，在SD之间可以建立镜像关系， 使得被写入到一个SD(称为“主SD”)的数据由RAID系统自动写入到另一 个SD(在本文中称为“从SD”或“镜像SD”)以实现冗余目的。从SD可能 由与主SD相同的RAID系统进行管理，或由不同的本地或远程RAID系统进 行管理。镜像SD有效地提供了跨越SD的RAID 1+0功能性，以便在某些情 况下，从SD甚至可能多个SD的丢失或损坏中提供恢复。

“文件系统”是存储在文件存储系统中的文件和目录(文件夹)的结构。 在文件存储系统内，文件系统通常使用若干虚拟存储构造(construct)来进行 管理，并且在示例性实施例中，文件系统使用被称为域(range)、条带集(stripeset) 以及跨越(span)的虚拟存储构造的分级结构来进行管理。域(range)由主 SD自己或主/从SD对组成，主/从SD对应该包含相同的数据，并且因此作为 单一的SD提供相同的存储容量。条带集(stripeset)是由一个或多个域组成。 跨越(span)是由一个或多个条带集(stripeset)组成。因此，跨越(span)最 终由一个或多个SD(通常4至50个SD)组成。跨越可以分成一个或多个文 件系统，每个文件系统具有单独的名称和标识符并且可能具有不同的特性(例 如，一个文件系统可以用32KB簇(cluster)格式化，而另一个用4KB簇格式 化，一个文件系统可是蠕虫(Worm)和另一个不是，等等)。在跨越上的每个 文件系统被单独地进行格式化、安装和卸载。可以以任何顺序和在任何时间创 建和删除文件系统。文件系统通常可被配置为自动扩展(或可替代地，防止或 限制自动扩展)，或者可以手动进行扩展。

“块(block)”是在文件系统中的存储的单位，其对应于在其中存储用户 数据和/或系统数据的物理存储的部分。(下面讨论的)文件系统对象一般包括 一个或多个块。

“组块(chunk)”是在文件系统中的存储的概念单位，它包括一个或多个 文件系统对象的块。在本文中所描述的示例性实施例中，去复制是在组块基础 上执行的。

值的“集合”可以包括一个或多个值。

为方便起见以下使用标题，但其不应当被解释为以任何方式限制本发明。

参考通常被称为BlueArc Titan^TM和Mercury^TM文件服务器的由Hitachi数据 系统销售的各种文件服务器中使用的类型的示例性文件系统，对本发明的示例 性实施例进行描述，然而应当指出的是，各种概念可应用于其它类型的文件系 统。

示例性文件存储系统

图1是根据本发明的示例性实施例的文件存储系统的示意框图。其中，该 文件存储系统包括若干文件服务器(为简化和方便起见示出了单个文件服务器 102)，其通过诸如因特网协议网络(例如，因特网)的通信网络104与各种客 户端设备106₁-106_M通信，并且还通过诸如光纤通道网络的存储网络110与各 种RAID系统108₁-108_N通信。客户端设备106₁-106_M和文件服务器102使用一 个或多个网络文件协议，例如CIFS和/或NFS，进行通信。文件服务器102和 RAID系统108₁-108_N使用存储协议，例如SCSI，进行通信。应当指出的是， 该文件存储系统可能包括以各种配置互联的多个文件服务器和多个RAID系 统，包括全网配置，其中任何文件服务器都可以通过冗余和交换光纤通道网络 与任何RAID系统进行通信。

文件服务器102包括用于管理一个或多个文件系统的存储处理器。文件服 务器102可以被配置为允许客户端访问部分的文件系统，诸如指定名称下的树 或子树。按CIFS的说法，这种访问可以被称为“共享”，而按NFS中的说法 这样的访问可以被称为“输出(export)”。固有地，文件服务器102可以包括 各种硬件实现的和/或硬件加速的子系统，例如，如美国专利No.6826615 (2337/103)和8180897(2337/108)中所描述的那样，它们的全部内容通过 引入合并于此，文件服务器102还可包括基于硬件的文件系统，其包括多个链 接的子模块，例如，如美国专利No.7457822(2337/104)和8224877(2337/117) 所描述的那样，它们的全部内容通过引入合并于此，

每个RAID系统108通常包括至少一个RAID控制器(通常两个RAID控 制器以用于冗余)以及由(多个)RAID控制器管理的若干物理存储设备(例 如，盘)。RAID系统108将其存储资源聚集至若干个SD。例如，每个RAID 系统108可以配置有2-32个SD。每个SD可以被限制到预定的最大大小(例 如，2TB-64TB或以上)。将多个存储设备合并至一个SD可以提供若干益 处，包括提高的速度(单个存储设备相对缓慢，但数据可以跨越多个存储设备 以拓宽瓶颈)，增加的容量(单个存储设备相对较小，但可以合并多个存储设 备以提供更多的可用空间)，抽象性(abstraction)(使用的空间的量可以大于 或者小于单个存储设备的大小)和可靠性(resilience)(奇偶校验或冗余信息 可以存储在每个存储设备上，以便SD可以承受存储设备的损耗)。

文件服务器102被配置为使用一个或多个SD，其可以来自单一的RAID 系统或来自多个RAID系统。该文件服务器102可以正常询问RAID系统以发 现每个SD是主要的还是从属的。控制哪些SD被文件服务器102所使用的方 法在本文中称为“许可”(licensing)。因此，在实践中，文件服务器102通常 对于一些SD被许可而对另一些则不被许可。

固有地，该文件服务器102能够将多个SD合并成较大的存储池，在本文 中称为“跨越(span)”。跨越基本上是多个SD的RAID 0阵列。将多个SD合 并成跨越可以提供类似于将多个物理磁盘合并成SD所获得的那些若干益处， 包括增加的速度(在多个RAID系统上扩展多个SD之间的I/O可以进一步拓 宽存储瓶颈)，增加的存储容量(跨越可以大于可能被限制为2TB的单个SD) 和允许更灵活的存储空间分配的额外的抽象性。

软件/硬件架构

在某些示例性实施例中，文件服务器通过基于软件的系统和基于硬件的系 统之间的特殊分工来实施去复制。图2是根据该示例性实施例的软件/硬件架 构的示意图。这里，基于软件的系统210包括各种软件组件，其包括在操作系 统211下运行的基于软件的去复制管理器212和去复制检测/索引引擎213，操 作系统211运行在微处理器系统(例如包括微处理器和相关的存储器和外设) 上。提供进程间通信通道214(例如，经由Bossock套接字层(socket layer)) 以允许基于软件的去复制管理器212和去复制检测/索引引擎213之间的通信。 基于硬件的系统220包括各种硬件组件，该组件包括基于硬件的文件系统管理 器221，其与基于硬件的哈希生成器(hash generator)222(将在下面更充分讨 论)以及文件系统223通信，文件系统223被存储在各种存储器和存储设备中， 其中一些可以在文件服务器102内(例如，在内部缓冲存储器中)并且其中一 些可以在文件服务器102外(例如，被存储在各种RAID系统或其他存储系统 中)。提供接口230以允许基于软件的去复制管理器212和基于硬件的文件系 统管理器221之间的通信。

其中，图2中所示的分工允许基于软件的去复制管理器212在后台管理去 复制功能，从而控制去复制对基于硬件的文件系统的性能的影响，并且也减少 基于软件的组件和基于硬件的组件之间的通信量。如下面所讨论的，基于软件 的去复制管理器212和基于硬件的文件系统管理器221都包括减少执行去复制 所需的处理量和通信量的各种优化。

文件系统对象以及树结构

文件服务器102在文件系统中存储各种类型的对象。对象一般可以被分类 为系统对象以及文件对象。文件对象被创建以用于存储用户数据以及关联的属 性，诸如文字(word)处理器或者电子数据表(spread sheet)文件。系统对象 由文件存储系统创建用于管理信息，并且包括如下内容，例如根目录对象，空 闲空间分配对象，修改的检查点对象列表对象，修改的保留的(retained)对 象列表对象，以及软件元数据对象，这里仅举几例。更具体地，目录对象被创 建以用于存储目录信息。空闲空间分配对象被创建以用于存储空闲空间分配信 息。修改的检查点对象列表对象以及修改的保留的对象列表对象(这两者都将 在下文进行更详细地描述)被创建以用于存储分别涉及检查点以及保留的检查 点的信息。软件元数据对象(将在下文进行更详细地描述)是用于保持与文件 或者目录对象关联的额外文件属性的特殊对象(即，不能适合在如下文所描述 的文件或者目录对象之内的预先指定的区域之内的文件属性，诸如CIFS安全 属性等)，并且其是由文件或者目录对象的创建器所创建的，该创建器包括对 于文件或者目录对象之内的软件元数据对象的参考。

在某些实施例中，使用具有根节点的树结构(称为动态超级块或者DSB) 来管理文件系统的实例。文件服务器102可以维持多个DSB以存储表示不同 检查点的文件系统的不同版本(例如，当前“工作”版本以及一个或多个“检 查点”版本)。在一个示例性实施例中，DSB包括指向间接对象的指针，该间 接对象依次地包括指向其它对象的指针。通过间接对象所参考的每个对象与对 象编号相关联。系统对象通常具有固定的、预定义的对象编号，因为它们一般 总是存在于系统当中。文件对象通常从可用的对象编号池中被动态地分配对象 编号，并且在某些情况下这些文件对象编号可以被重新使用(例如，当文件被 删除时，其对象编号可以被释放，以被随后的文件对象重新使用)。可以通过 对象编号索引间接对象以便获得指向对应的对象的指针。

一般而言，在文件系统中的每个对象，包括间接对象、每个系统对象以及 每个文件对象，都是使用独立的树结构来进行实施的，其中，树结构包括独立 的对象根节点(root node，有时被称为root onode)并且可选地包括若干间接 节点(indirect node，有时称为indirect onode)，直接节点(direct node，有时 称为direct onode)，以及存储块。DSB包括指向间接对象的根节点的指针。间 接对象包括指向其它对象的根节点的指针。

图3是示出了根据本发明的示例性实施例的对象树结构的一般格式的示 意框图。根(“R”)节点302可以指向各种间接(“I”)节点304，每个节点304 可以指向若干直接(“D”)节点306，每个节点306可以指向若干存储块(“B”) 308。在实践中，对象树结构可以例如根据对象的大小发生很大的变化。另外， 当信息被增加至对象和从对象删除时，特定对象的树结构可随时间而变化。例 如，当更多的存储空间被用于对象时，节点可以被动态地增加至树结构；并且 可以根据需要使用不同层级的间接(例如，间接节点可以指向直接节点或者其 它间接节点)。

当对象被创建时，为对象创建对象根节点。最初，该“空”对象的根节点 没有指向任一间接节点、直接节点、或者数据块的指针。

当数据被增加至对象时，它首先被放入直接从根节点所指向的数据块。一 旦在根节点中的所有的直接块指针被填满，则创建具有从根节点到直接节点的 指针的直接节点。如果对象中的数据增长以填满了直接节点中的所有的数据指 针，则创建间接节点。

例如在美国专利No.7457822(2337/104)(其通过上面的引用合并于此) 以及美国专利No.8041735(2337/105)(其全部内容通过引用合并于此)所描 述的那样的检查点机制被包括以在各种时间制作文件系统的可选的保留的拷 贝以及临时拷贝。具体地，文件系统请求的处理被一系列检查点所划定，该一 系列检查点被安排为以不低于一些用户指定的间隔，诸如每10秒发生。对于 每个连续的检查点，在盘上存储当前文件结构信息，其取代来自紧接在前面的 检查点的先前存储的文件结构信息。检查点被依次地编号并且被用于临时组合 (group)文件请求的处理。每个文件系统对象均与创建该对象于其中的检查 点相关联，并且创建检查点编号被存储在对象根节点中。

为用于各种目的，在选择的时间点了解文件系统结构可能是有用的。通过 允许存储与当前保存的检查点相关联的文件系统结构数据来提供该能力，为方 便起见，在下文中，当前保存的检查点被称为保留的检查点或者快照(snapshot)。 该保留的检查点基本上是在特定的检查点的文件系统结构的只读版本。可以制 作多个保留的检查点，并且包括机制以用于删除所选择的保留的检查点或者将 文件系统恢复至所选择的保留的检查点(例如，将文件系统返回至灾难之后的 已知状态)。

在本发明的某些实施例中，包括了例如在美国专利申请公开No.US2012/ 0130949(2337/130)(其全部内容通过参考合并于此)所描述的文件克隆机制， 以允许诸如当用户制作文件的拷贝时，在文件系统内快速创建文件的拷贝(克 隆)。在示例性实施例中，源对象的克隆至少最初是由包含源对象的各种要素 (例如，间接节点、直接节点以及数据块)的参考的结构所表示的。只读以及 可变的克隆都可以被创建。源文件和克隆最初共享这些要素并且当对源文件或 者可变的克隆进行改变的时候继续共享未修改的要素。描述与源文件关联的数 据流(即，间接/直接节点)的用户数据块或者元数据块均不需要在克隆被创 建的时候被拷贝。在适当的时间，克隆的文件可以被“去克隆”。

对象根节点包括检查点编号以识别检查点，在该检查点中对象是被最后修 改的(检查点编号最初识别在其中对象被创建的检查点，并且随后每次对象在 新检查点被修改时检查点编号改变)。在示例性实施例中，在其中创建对象的 检查点编号也被存储在对象根节点中。

对于对象根节点所对应的实际的数据，对象根节点包括指向与对应的对象 关联的数据的每个块的独立指针。一般而言，指向多达16个数据块的指针被 存储在对象根节点中。对于超出16块的数据，在对象树中需要一个或多个直 接节点和/或间接节点，其中，在每个节点中根据需要存储的合适的指针链接 各种节点。这些指针存储与对应的数据块或者节点关联的在盘上的块的扇区 (sector)编号。

直接节点包括检查点编号并且被布置为存储与对象有关的块(例如，大约 60或者61个块)的某编号的位置。

当第一直接节点被完全地利用以识别数据块时，则一个或多个间接节点被 用于识别第一直接节点以及额外的直接节点，该额外的直接节点具有对应于对 象的数据块。在这种情况下，对象根节点具有指向间接节点的指针，并且间接 节点具有指向对应的直接节点的指针。当间接节点被完全地利用时，则在必要 时采用额外的中间间接节点(intervening indirect node)。这种结构允许部分文 件的快速识别，而不管文件的分段存储(fragmentation)。

如以上所讨论的，间接节点提供根节点和直接节点之间的间接的层级。下 面的信息被存储在一个示例性实施例的间接节点中:

●检查点编号。

●指向或者间接或者直接节点的指针(例如，多达60个这样的指针)。

●CRC以及各种健全双字(sanity dwords)，以允许检查间接节点的有效 性。

如以上所讨论的，直接节点提供指向盘上的数据块的直接的指针。下面的 信息被存储在一个示例性实施例的直接节点中:

●检查点编号。

●若干数据块描述符(例如，多达60个这样的描述符)。每个数据块描 述符包括指向数据块的指针、检查点编号以及说明块是否被零填充的 比特。

●CRC以及各种健全双字，以允许检查间接节点的有效性。

在每个节点(即，根节点、间接节点、直接节点)内，指向块或者其它节 点的每个指针与检查点编号相关联以表明检查点与由指针参考的块/节点相关 联。在下文描述的某些示例性实施例中，这些检查点编号被用于确定特定的文 件系统是否应当对于对象组块进行调查研究以用于可能的去复制。

尽管上述描述了文件系统对象树结构是如何在写入对象时用分配给占有 的位置(populated)的树节点和数据块来进行管理的，但是某些示例性实施例 支持稀疏的文件系统对象，其中可以写入文件系统对象而无需分配所有的数据 块以及树节点，并且对于对象的一些零填充的部分无需零填充数据块。

例如，如果对于文件的写入具有超过文件的当前末端的起始偏移，则当前 末端和新的写入数据的开始之间的文件的未定义的部分技术上必须用零进行 填充。如果对象的长度被设定为大于当前长度也会发生相同的事情。如果文件 被创建并且然后长度被设定为例如1GB，则这可能是特别地有问题的。为这 样的文件系统对象完全地分配数据块将会需要将被分配至对象的盘块实际地 用零写入。对于1GB的文件，这将花费，比如说，10秒钟的量级。对于1TB 的文件，它将可能花费比如说3小时的量级。

在本发明的某些实施例中，通过具有比特可以避免该问题，其中，所述比 特具有说明该块是否零填充的每个数据块指针。如果设定了该比特，则文件服 务器知道该块应当用零进行填充，即使在盘上它可以包含非零数据。如果该块 被读取，则为该块返回零而非实际的盘上的内容。如果用不填充整个块的写入 来写入该块，则没有被正在写入的块的部分写入零，并且重置比特以表明该块 不是零填充的。值得注意的是，在这种情况下，将为文件的所有的零填充的部 分分配盘块，虽然盘块将不会实际地用零进行填充。

在一些实例中，甚至不为这样的文件系统对象的零填充的部分分配数据块 以及相关的树节点，因为分配数据块以及树节点可能花费过多的大量时间。例 如，对于4K的盘块大小，1TB对象需要大约4百万直接节点以及较少的数量 的间接节点，这将花费40秒钟的量级以写入盘。此外，所需的所有的数据块 的空闲空间分配以及随后的对于空闲空间位图的更新都将显著地增加该时间。 如果在文件创建开始之后立即取得检查点，则对于整个该时间，整个系统一般 将停止(至任意卷)的服务请求。

在某些示例性实施例中，通过双重方法(twofold approach)来解决该问题。 解决方案的第一方面是不为零填充的文件部分实际地分配盘块。这意味着当对 象存储发现对零填充的块的写入时，它将首先不得不为该块分配盘空间，并且 在有关的节点结构(onode structure)中放置指向它的指针。

第二方面建立在第一方面之上，并且，除了不分配数据块之外，还涉及不 创建节点结构。为实施该方面，每个节点指针具有表明它所指向的节点是否被 分配的比特。如果为否，则仅当需要节点有效的操作发生时，为其分配盘空间 并且插入正确的指针。这样，大量的零填充的对象可以仅具有根节点，显然， 该根节点可以被非常快速地创建。

仅仅为了示例，下面示出了包含在根节点以及从根节点参考的下一级节点 中的信息的类型的说明(具有下划线并在括号内的是注释)：

文件的根节点的示例

onode/ccache:onode-o 16392

onode/ccache:Read 1024bytes from sector 0x38b560(Byte Offset 0x716ac000)

onode/ccache:

onode/ccache:ActiveRootNode

onode/ccache:AsciiDescriptor:RONA

onode/ccache:SanityDWord0:WFS1(valid)

onode/ccache:ObjectNumber:0x4008(Type:OBJ_TYPE_FSOBJECT_ FILE)

onode/ccache:Checkpoint:0x123ab(当该对象是最后被修改时的检查点编号)

onode/ccache:ReuseCount:0x123ab

onode/ccache:WriteCount:0x3

onode/ccache:IndirectionCount:2

onode/ccache:ResiliencyMode:None

onode/ccache:DataLength:1MB(1048576B)

onode/ccache:FreeRootOnodePtr:0x0(unused)

onode/ccache:SavedRootOnodePtr:0x0(unused)

onode/ccache:BlockPtr[00]:0x38d0c8(Checkpoint:0x123ab)(指向在检查点0x123ab写入的数据块的指针)

onode/ccache:BlockPtr[01]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[02]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[03]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[04]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[05]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[06]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[07]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[08]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[09]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[10]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[11]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[12]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[13]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[14]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:BlockPtr[15]:(Checkpoint:0x123ab)(ZeroFill)(Sparse)

onode/ccache:LeafOnodePtr:0x38b5c0(Checkpoint:0x123ab)(指向剩余的数据块的额外的节点树)

onode/ccache:Format TimeStamp:0x5034155431d149c3

onode/ccache:WfsEnode

onode/ccache:<Enode contains file's attributes-snipped>

onode/ccache:

onode/ccache:Cloned Checkpoint:0x0(如果该对象是另一个对象的克隆，则克隆的检查点将是非零的。)

onode/ccache:Reserved[1]:0x0

onode/ccache:Reserved[2]:0x0

onode/ccache:BlockCount:0x100(sparse blocks)

onode/ccache:CreationChkpoint:0x123ab(其中该对象被创建的检查点)

onode/ccache:Crc32:0xcbe306ba(valid)

onode/ccache:SanityDWord1:WFS2(valid)

节点树中的下一级的示例：

onode/ccache:onode-s 0x38b5c0

onode/ccache:Read 1024bytes from sector 0x38b5c0(Byte Offset 0x716b8000)

onode/ccache:Leaf Onode:

onode/ccache:IndirectOnode

onode/ccache:AsciiDescriptor:IONA

onode/ccache:SanityDWord0:WFS1(valid)

onode/ccache:ObjectNumber:0x4008(Type:OBJ_TYPE_FSOBJECT_ FILE)

onode/ccache:Checkpoint:0x123ab(当该节点被写入时的检查点，其必须匹配在指向该节点的指针—在本示例中，从上述根节点的叶子节点指针—中的检查点字段(field))

onode/ccache:ReuseCount:0x123ab

onode/ccache:WriteCount:0x3

onode/ccache:ResiliencyMode:None

onode/ccache:ObjectPtr[00]:0x38b5b8(Checkpoint:0x123ab)(指向树的第一下一分支的指针)

onode/ccache:ObjectPtr[01]:0x38b5c8(Checkpoint:0x123ab)(指向树的第二下一分支的指针)

onode/ccache:ObjectPtr[02]:0x38b5d0(Checkpoint:0x123ab)(指向树的第三下一分支的指针)

onode/ccache:ObjectPtr[03]:0x38b5d8(Checkpoint:0x123ab)(指向树的第四下一分支的指针)

onode/ccache:Reserved[0]:0x0

onode/ccache:Reserved[1]:0x0

onode/ccache:Reserved[2]:0x0

onode/ccache:Crc32:0x25972e2f(valid)

onode/ccache:SanityDWord1:WFS2(valid)

去复制检测/索引引擎

虽然本发明的实施例并不限于任意特定的去复制检测/索引引擎，但是在 某些示例性实施例中，去复制检测/索引引擎213是从Permabit Technology  Corporation of Cambridge,MA得到许可的被称为ALBIREO^TM数据优化软件 的商业可用软件产品(下文中称为“该引擎”)，其被提供为预编译的共享的库 以及可执行的以及被整合至基于软件的系统210。

该引擎支持两种类型的索引，即，稀疏索引以及默认索引。索引是基于组 块的SHA-256哈希(hash)。两种索引类型都使用每索引组块的四字节的内存 表项(in-memory entry)以及盘上(on-disk)数据结构，在该数据结构中关于 组块的信息被记录为它们被呈现给该引擎的(并且以呈现的顺序的)样子。该 盘上数据结构用于存储关于每个组块的特定应用信息(在下文中被称为“组块 元数据”(chunk metadata)，并将在下文进行更加详细地讨论)。在某些示例性 实施例中，使用稀疏索引，这是因为稀疏索引对于后台去复制处理可以是更优 选的，在该处理中，不必以暂时的顺序(即，以组块被实际修改的顺序)去复 制来处理组块，即使这样的暂时的方位一般是优选考虑的。优选地(但不是必 须地)，盘上的数据结构被存储在与其相关的文件系统之内，这允许在EVS以 及文件系统迁移期间盘上的数据结构自动地随文件系统移动。

基于检查点的去复制

在非常高的层级，去复制处理涉及识别候选进行去复制的组块，确定特定 的候选组块是否是文件系统内的其它组块的复制件，以及使用对于其它组块的 参考来替换复制件组块，以便候选组块(以及由此复制件数据)不需要被存储。 或者该其它组块的复制件的其它候选组块也可以使用对于该其它组块的参考 来替换，从而进一步减少存储的数据量。

本发明的某些示例性实施例改变了文件系统检查点机制以管理后台去复 制处理，而且还减少了关于识别候选去复制的组块以及处理这样的组块的处理 复杂性。

在某些实施例中，改变(leverage)检查点的一种方式是由基于软件的去 复制管理器执行作为在连续的去复制循环中的后台功能的去复制，其中，去复 制循环运行于各种时间(其可以是被安排的，在某条件下执行的或者手动启动 的，其中所述条件可以包括诸如在预先确定的编号的块已经被修改之后或者在 预先确定的编号的检查点已经取得之后)，并且每个循环都涵盖预先确定的范 围内的检查点编号，该检查点编号不一定是连续的。在一个示例性实施例中， 在每个检查点，自从早前的检查点被追踪且累积而改变的块的编号，以及自从 最后的去复制循环在文件系统中被改变的块的编号，被用于确定何时开始去复 制循环。如果基于软件的去复制管理器确定去复制已经落后活动的文件系统预 先确定的量(例如，自从去复制的最后的检查点范围开始，多于预先确定的编 号的块已经被修改)，则基于软件的去复制管理器可以省略若干检查点范围的 去复制以“追上”活动的文件系统。检查点编号也由基于软件的去复制管理器 使用以减少检测候选组块所需的处理量，并且检查点编号也由基于硬件的文件 系统管理器使用以减少验证匹配去复制所需的处理量并且还执行复制件组块 的实际的去复制。下面将对检查点的使用进行更详细的讨论。

下面的示例性去复制处理的描述假定每个组块包括单一文件系统块，并且 因此，对于该示例性实施例，术语“组块”和“块”基本上是可以互换的。稍 后，将描述对更一般的实施例的一些考虑，其中每个组块可以包括多个文件系 统块。

如图4所示意地示出的，在某些示例性实施例中，基于软件的去复制管理 器212使用被分为3个i层级的“管线(pipeline)”架构。这里，基于软件的 去复制管理器212包括“检测改变的块(Detect Changed Block)”层级402，“获 取去复制意见(Get Deduplication Advice)”层级404，以及“去复制组块 (Deduplicate Chunk)”层级406。在该示例性实施例中，每个层级发布来自单 一线程的异步请求。

图5是根据本发明的某些示例性实施例的去复制的示意性逻辑流程图。

一般而言，作为后台功能，基于软件的去复制管理器212在框502中取得 文件系统的快照，并在框504中确定用于去复制的检查点范围。检查点范围包 括基部(base)检查点编号(称为“检查点-低”)以及上部(upper)检查点编 号(称为“检查点-高”)，其中检查点-高通常是与快照关联的检查点编号，而 检查点-低是预先确定的以前的检查点，其可以与去复制的紧接前一迭代的检 查点-高值相同或不同。任务被发送至“检测改变的块”序列(queue)，其包 含文件系统标识符(其允许如下面所讨论的支持多个文件系统的去复制)、该 去复制循环将开始于此的对象编号、在单一任务中应当被检查的对象的编号、 基部检查点编号(检查点-低)、以及上部检查点编号(检查点-高)。

在框506中，基于软件的去复制管理器212的检测改变的块的线程池/进 程402处理文件系统的“快照”拷贝，以识别在预先确定的检查点范围内修改 的以及因此成为去复制候选的组块。下面讨论识别候选组块的示例性处理。

当发现候选组块时(框508中的是)，检测改变的块层级402将任务发送 至包括关于候选组块的相关信息(例如，块指针以及组块的检查点)的获取去 复制意见层级404。在框510中，获取去复制意见层级404经由接口230将请 求发送到基于硬件的文件系统管理器221，以有条件地(即，受到下面讨论的 某限制)从存储器中读取候选组块并且使用基于硬件的哈希生成器222计算候 选组块的哈希值。

在读取/哈希特定的候选组块之前，基于硬件的文件系统管理器221决定 是否读取并哈希该候选组块，这是因为例如，自从取得了被基于软件的去复制 管理器212所使用的文件系统的快照拷贝，与候选组块关联的文件系统对象可 能已经被删除或者删减了而排除该候选组块，或者自从取得了被基于软件的去 复制管理器212所使用的文件系统的快照拷贝，组块可能已经被修改。在前者 的情况下，不需要为候选组块计算哈希值，从而节省处理资源并且降低基于软 件的去复制管理器以及基于硬件的文件系统管理器之间的通信。在后者的情况 下，如果候选组块与其在“快照”拷贝中处于相同的检查点，则如以上所讨论， 基于硬件的文件系统管理器221为候选组块计算哈希值并且将哈希值以及关 联的组块元数据传递至基于软件的去复制管理器。

假定基于硬件的文件系统管理器221决定读取/哈希候选组块，则基于硬 件的文件系统管理器221调用哈希生成器222以生成哈希，并且然后将关于候 选组块的哈希以及相关的组块元数据(其中包括，对象编号，检查点编号等) 传回至获取去复制意见层级404。相对于由基于软件的去复制管理器212请求 整个候选组块(在一个示例性实施例中，其可以是32千字节(Kbyte))并且 (例如，由基于软件的去复制管理器212或者由去复制检测/索引引擎213)在 基于软件的系统210之内执行哈希，该机制通过传递哈希值以及相关的组块元 数据(在一个示例性实施例中，其处于64字节的信息的量级上–256比特哈 希值加上多达32字节的组块元数据)而非整个候选组块而降低了基于软件的 系统210以及基于硬件的系统220之间的通信，并且还通过在硬件执行哈希功 能降低了基于软件的系统210中的微处理器的负荷。

假定哈希了候选组块(框512中的是)，则在框514，获取去复制意见层 级404经由接口214调用去复制索引/匹配引擎213以确定是否该哈希值匹配 先前索引的组块的哈希值。如果候选组块的哈希不匹配先前索引的组块的哈希 (框516中的否)，则获取去复制意见层级404通常指令去复制检测/索引引擎 213通过为该哈希值存储从基于硬件的文件系统管理器221接收的组块元数据 来索引候选组块(即，候选组块变为先前索引的组块，用于将来的复制件检测)。 而另一方面，如果候选组块的哈希匹配先前索引的组块的哈希(框516中的是)， 则去复制索引/匹配引擎213将先前索引的组块的存储的组块元数据返回至获 取去复制意见层级404，其接着将任务发送至去复制组块线程池/进程406。

去复制组块层级406(基于由去复制检测/索引引擎213返回的组块元数据) 锁定与先前索引的组块相关联的对象，并且在框518将请求发送至基于硬件的 文件系统管理器221以验证该匹配并且基于由去复制检测/索引引擎213返回 的组块元数据有条件地去复制候选组块。

当基于硬件的文件系统管理器221被通知候选组块匹配先前索引的组块 时，基于硬件的文件系统管理器221必须决定是否去复制候选组块，这是因为， 自从取得了被基于软件的去复制管理器212所使用的文件系统的快照拷贝甚 至自从生成哈希时，活动的文件系统中的相关信息可能已经改变，从而使得先 前索引的组块和/或候选组块对于去复制目的已经过时了。例如，至基于软件 的去复制管理器识别出候选组块为复制件的时候，与候选组块关联的对象可能 已经从活动的文件系统中被删除了，与候选组块关联的对象可能已经被删减了 从而使得候选组块不再是对象的一部分，或者候选组块可能已经被修改了。因 此，候选组块的匹配仅仅是暂时性的，并且必须在候选组块可以被去复制之前 处于有效。因此，基于硬件的文件系统管理器221有效先前索引的组块以及使 用检查点编号的候选组块，具体地通过比较先前索引的块指针的当前检查点与 从索引在组块元数据中返回的检查点，以确保两个块没有改变并且仍然处于使 用中，并且因此可用于去复制。

即使先前索引的组块以其他方式可用于去复制候选组块，在某些示例性实 施例中，如果与先前索引的组块相关联的块已经被参考(即，被共享)预先确 定的最大次数，则基于硬件的文件系统管理器221可能还是不能去复制候选组 块。因此，在这样的示例性实施例中，可以参考(即，共享)特定的块的次数 可能被限制了。在该示例性实施例中，基于硬件的文件系统管理器221为该块 检查参考计数(下面讨论)，以确定是否已经达到最大参考计数。如果已经达 到最大参考计数，表明不可以使用来自先前索引的组块的块来去复制该候选组 块，则基于硬件的文件系统管理器221通知去复制组块层级406。

假定基于硬件的文件系统管理器221确定候选组块可以被去复制，则除其 他事项外，基于硬件的文件系统管理器221使用先前索引的组块的参考替换对 于对应的文件系统对象中的候选组块的参考，增加与先前索引的组块相关联的 参考计数，并且将候选组块标记为释放的，从而减少文件系统对象所需的存储 空间的量。

如果候选组块被基于硬件的文件系统管理器221成功地去复制了(框520 中的是)，则如果仍然有要处理的对象(框526中的否)，处理基本上返回至框 506。然而如果候选组块没有被基于硬件的文件系统管理器221成功地去复制 (框520中的否)，并且，正如下面更全面地讨论的那样，这样的去复制候选 组块的失败是由于先前索引的组块已经达到其最大参考计数从而不可用于去 复制候选组块而造成的(框522中的是)，则在框524中，去复制组块线程层 级406通常指令去复制检测/索引引擎213通过为该哈希值存储从基于硬件的 文件系统管理器221接收的组块元数据来索引候选组块(即，候选组块变为用 于将来复制件检测的先前索引的组块)。无论是否去复制了该候选组块，以及 无论索引是否基于候选组块进行了更新，如果仍然有要被处理的对象(框526 中的否)，则处理基本上返回框506。

识别候选组块

正如以上所讨论的，检测改变的块层级402将必须识别文件系统中的改变 以尝试将它们去复制。在某些示例性实施例中，基于软件的去复制管理器212 遍历间接对象，使用检查点编号识别被改变的对象并且然后识别该被改变的对 象之内的被改变的块。图6是根据一个示例性实施例的识别候选组块的逻辑流 程图。这里，在框602中检测改变的块层级402检查文件系统对象的根节点。 如果对象的创建检查点处于检查点范围之内(框604中的是)，则除非对象是 克隆的对象(下面讨论)，否则与文件系统对象相关联的所有的块将在该检查 点范围之内完成改变，并因此文件系统对象的所有块通常将被考虑为候选组块 (可选地具有例外，下面讨论)。

如果文件系统对象是克隆的对象(框606中的是)，则仅仅已经脱离原始 对象(即，从中克隆对象的那个对象)的文件系统对象的块将被认为是候选组 块，从而在框608中，检测改变的块层级402“遍历(walk)”(即，穿越(traverse)) 对象树以识别已经脱离原始对象的任意候选块。这样的脱离的块将具有大于对 象的在其中克隆的检查点编号的检查点编号，其被存储在对象根节点中。

如果文件系统对象不是克隆的对象(框606中的否)但是对象是稀疏的对 象(框610中的是)，则不是将对象的所有的块视为候选组块(其中有一些块 可能是未被分配的)，而是可选地，在框612中，基于软件的去复制管理器212 可以“遍历”对象树以仅发现已经被分配并且被写入的块并且将这些块视为候 选组块。

如果对象的创建检查点处于检查点窗口之内并且对象不是克隆的而且对 象也不是稀疏的(在如上述处理稀疏的对象的一些实施例中)，则在框614中， 检测改变的块层级402将对象的所有的块视为候选组块。

如果对象的创建检查点小于检查点范围的底部(框604中的否)，则在框 616，检测改变的块线程池/进程402“遍历”对象树以识别在检查点范围内已 经改变的任意候选块。

另外或者可选地，在各种可选实施例中，基于硬件的文件系统管理器221 可以保持被改变的对象列表和/或被改变的块列表，并且检测改变的块层级402 可以使用这样的列表以识别在给定的检查点范围之内的文件系统中的改变。

数据打包(PACKING)

在某些示例性实施例中，相对于正如通常所做的在独立的块中存储每个数 据片段，为了节约存储空间，系统可以允许来自相同的文件系统对象或者来自 不同文件系统对象的多个数据片段(segment)(例如，小于整个块的用户数据 片段和/或节点)被打包成单一的块。例如，多达预先确定的数量的节点可以 被存储在单一的块中，或者多个数据片段(甚至是与多于一个文件系统对象相 关联的数据)都可以被存储在单一的块中。

例如，当数据片段请求存储空间时，系统并非为数据片段请求且获取整个 块，而是可以为数据片段请求并获取一个或多个扇区，其中扇区不必须处于块 边界的开始并且可以从现有的部分填充的块中进行分配，并且因此多个数据片 段可以共享单一块。对于某类型的数据片段(例如，叶节点是固定大小的)可 以以固定大小的增量分配扇区，或者对于其它类型的数据片段(例如，可变大 小的用户数据片段)可以以可变大小的增量分配扇区。这样的打包的块基本上 由多个实体共享(并且因此由多个实体参考)，并且类似于由于去复制导致的 可以由多个实体共享(并且因此由多个实体参考)块的方式，不可以删除这样 的打包的块直至已经删除在块中包含的所有的数据片段。因此，类似于由于去 复制导致的块的共享，系统必须能够追踪与该打包的块相关联的参考的编号， 例如，使用下面更详细地描述的与用于去复制的相同的参考计数机制。当将数 据片段增加至块时，参考计数递增，并且当将数据片段从块中移除时，参考计 数递减。

在某些具体示例性实施例中，根节点将被存储在独立的块中并且将不被打 包以避免对处理根节点的某应用(utility)(例如，“fixfs”应用)的修改，虽 然固定大小的叶节点和可变大小的数据块可以被打包。关于数据块的打包，如 果在现有的部分填充的块中没有足够的空间以存储给定的数据片段，则通常数 据片段将被存储在新的块中，而非在现有的部分填充的块中存储部分数据片段 并在新的块中存储数据片段的剩余部分，虽然某些实施例可以允许这样的数据 片段的“分割(splitting)”。

应当指出的是，如本文所讨论的，可以以类似于去复制其它数据块的方式 来去复制打包的块。

块参考计数

如以上所讨论的，对于去复制以及数据打包，块可以被两个或者更多实体 参考(共享)。因此，需要机制以为每个块追踪参考。通常，使用参考计数追 踪参考，并且不可以删除块除非并直至参考计数达到零(即，当删除参考块的 最后的实体的时候)。

虽然本发明不限于任意特定的用于为每个块追踪参考计数的机制，但在某 些实施例中，使用位图来追踪参考计数，其中该位图具有与每个块关联的多个 比特。在某些示例性实施例中，位图是现有的空闲空间位图(FSB)的修改版 本，空闲空间位图(FSB)不仅被用于追踪块的状态(例如，使用的块相对空 闲的块，其在原始FSB中包括每块的两个比特)也用于追踪参考计数。为方 便起见，本文中这样的位图被称为“参考计数位图(Reference Counted Bitmap)” 或者“RCB”。例如，RCB可以包括每个编码的块的四个或者八个比特，从而 体现块的状态(例如，使用的块相对空闲的块)和参考计数。下面仅是一个示 例性编码方案，其使用每块八个比特，其允许去复制以及利用每块多达八个根 节点来打包的根节点:

-值(value)＝0:块没有被分配

-值＝[1，239(0xEF)]:正常块或者快照块的参考计数

-值＝[240(0xF0)，247(0xF7)]:打包的块的参考计数(参考计数1至8)

-值＝248(0xF8)至255(0xFF):未使用的/保留的

可选地，可以使用独立的位图或者其它数据结构以追踪每个块的参考计数。 增强的去复制

在某些示例性实施例中，当先前索引的组块不再与其原始对象关联(例如， 因为与先前索引的组块关联的原始对象已经被删除或者删减)时，去复制的处 理不需要被放弃。取而代之地，可以经由包含索引的组块中的块的链接的列表 的文件系统来维持独立的数据结构。该数据结构可以经文件系统被保存在已知 的对象中。当如以上所讨论的由去复制检测/索引引擎213检测到复制件时， 则该数据结构可以被用于定位与先前索引的组块关联的块，然后其可以被检查 以确定该块是否可以被用于去复制候选组块(例如，块的内容没有改变)。如 果先前索引的组块被用于去复制候选组块，则与每个块相关联的参考计数递增， 并且块随后不可以被释放除非并且直至其不再被参考。

处理多层文件系统中的去复制

在某些示例性实施例中，文件系统可以是多层文件系统(MTFS)，例如， 在美国专利申请No.13/043,837(2337/128)(其全部内容通过引用合并于此) 中所描述的那样。MTFS可以通过将文件系统元数据放置在更快的存储器(元 数据层)上来改善性能。

优选地，去复制将不允许用户对象共享用于在元数据层的文件系统元数据 的块，因为如果允许，则有可能甚至在块已经停止作为部分文件系统的元数据 之后，用户对象可能仍然保持元数据层中的块。

应当指出的是，对于元数据共享在用户数据层中的块一般是可接受的。

处理能复原的对象

某些示例性实施例可以支持所谓的“能复原的(resilient)”对象，其中， 能复原的对象是为其存储对象的两个完整拷贝的文件系统对象。该能复原的对 象可以被去复制，虽然它们不应当以这样的方式被去复制：任意块被两个拷贝 共享(这将基本上去除对象的能复原的特性)。因此，当去复制能复原的对象 时，系统将确保两个拷贝不结束于指向盘上的相同的数据。

NVRAM保留(RESERVATION)

在某些示例性实施例中，在去复制期间执行的修改操作将不被记录至 NVRAM。这意味着在崩溃(crash)的情况下，随后的还原(rollback)将清除 在最后的检查点之后在文件系统中发生的所有的去复制。

多个文件系统的去复制

可以以各种方式处理多个文件系统的去复制，诸如，例如使用用于多个文 件系统的单一索引或者使用用于每个文件系统的独立的索引。某些示例性实施 例将使用后一种方法。

快照恢复文件

在某些示例性实施例中，对象的快照拷贝可以通过在活动的文件系统中分 配新的对象编号并且然后使得对象的节点树以及块指针与快照中的文件共享， 来进行恢复。每个共享的块将需要使其参考计数递增。如果碰到处于其最大参 考计数的块，则将拷贝该块，并将活动的对象更新以指向拷贝的块。该新的对 象将被插入至活动的文件系统目录树，如果有需要，允许原始的以及快照恢复 的对象共同存在。在根节点中可以包括标记(flag)以表明该对象已经被快照 恢复。可以允许活动的对象的修改同时根据需要，递增共享的块的参考计数。 用于去复制的可选组块大小

在上述的示例性实施例中，每个组块包括给定的文件系统对象的单一的块， 从实施的立场来看，其为去复制提供若干简化，这通过可选实施例的下面的讨 论将变得清楚，在该实施例中，每个组块包括多个块(例如，每组块四个或者 八个块)。

由于对于给定量的分配的内存，去复制检测/索引引擎基本上可以索引固 定的数量的组块，因此更大的组块大小允许索引更大量的数据，虽然在一些情 况下更大的组块大小可能减少检测复制件的可能性(例如，匹配4K组块的数 据的可能性一般可能高于匹配256K组块的数据的可能性)。

在某些具有每组块具有多个块的示例性实施例中，根据预先确定的方案将 对象分至组块。例如，对象可以被连续地分至N-块的组块，例如，块1–N， 块(N+1)–2N等。

为了将这样的多个块的组块整合至上述的去复制方案中，每个组块必须被 分配有检查点编号。在某些示例性实施例中，组块检查点编号是具有最高检查 点编号的块的检查点编号。

另外，当去复制多个块的组块时，必须更新与候选组块相关联的对象，以 使用来自先前索引的组块的相应的参考来替换在候选组块中所有的块的参考。 块参考计数通常将按逐块原则(block-by-block basis)(相对于组块原则)进行 处理，以便可以仅仅共享尚未达到最大参考计数的块。

可选的去复制管理

在上述的示例性实施例中，去复制被执行为后台功能，修改的组块的检测 以及复制件组块的去复制都是如此。然而，发明人意识到，其它类型的去复制 管理也是可能的。例如，在一个可选例中，去复制可以当修改组块是在写入路 径中同步发生，从而使得，当写入到来时，由去复制检测/索引引擎哈希并处 理组块，并且如果检测到复制件，则作为写入操作的一部分将其去复制。这样 的同步的去复制会将等待时间(latency)引入写入路径，这可能负面地影响文 件系统的性能。在另一可选例中，可以以“混合(hybrid)”同步/异步方式执 行去复制，以便当写入到来时，由去复制检测/索引引擎(如同在上述的同步 解决方案的那样)哈希并处理组块的同时，组块自己被写入存储器(如同在全 后台去复制处理中的那样)，并且如果检测到复制件，则稍后在后台将其去复 制。

可选的哈希生成器的使用

在本发明的某些实施例中，基于硬件的系统220被配置使得可以由基于软 件的系统和/或由基于硬件的系统调用哈希生成器222以用于附加或者代替去 复制的其它基于哈希的功能，诸如，例如IPsec、SMB2签名(signing)、HCP 外部迁移或者利用SHA-256哈希的其它功能。

其他方面

上面描述了去复制以及数据打包特征。这些机制应当彼此互相排他地进行 考虑，即，某些实施例可能实施去复制而非数据打包，某些其它实施例可能实 施数据打包而非去复制，并且还有其它实施例可能实施去复制以及数据打包两 者。优选地，在示例性实施例中，实施能够被用于去复制以及数据打包两者的 参考计数机制(例如，参考计数位图或者其它机制)，以例如允许将来一个或 者两个特性的增加。

虽然上面参考整合至基于软件的系统210的商业可用的去复制检测/索引 引擎对示例性实施例进行了描述，但是应当指出的是，可以实施各种可选实施 例，其中去复制检测/索引引擎作为基于软件的去复制管理器的一部分或者作 为基于硬件的文件系统管理器的一部分。当去复制检测/索引引擎被实施为基 于硬件的文件系统管理器的一部分时，在为候选组块生成哈希值之后，基于硬 件的文件系统管理器通常将调用去复制检测/索引引擎，而不将哈希值传递至 基于软件的去复制管理器。

应当指出的是，可以在图中使用箭头以表示通信、传递，或者涉及两个或 者更多实体的其它活动。双端箭头一般表示活动可以在双向发生(例如，在一 个方向的命令/请求以及在另一方向的对应的响应，或者由任一实体发起的点 对点的通信)，虽然在一些情况下，活动可以不必在双向发生。单端箭头一般 表示活动专门或者主要在一个方向，虽然应当指出的是，在某些情况下，这样 的方向性的活动实际可能涉及双向的活动(例如，从发送器至接收器的消息以 及从接收器至发送器返回的确认，或者早于传递的连接的建立以及传递之后的 连接的终止)。因此，表示具体的活动的在具体的图中使用的箭头的类型是示 例性的而不应当被视为限制性的。

应当指出的是，为方便起见，上面使用了标题，不应以任意方式将其解释 为限制本发明。

应当指出的是，在本文中可以使用诸如“客户端”以及“服务器”的术语 以描述在本发明的某些实施例中可能使用的设备，不应当将其解释为将本发明 限制至任意特定的设备类型，除非上下文另有需要。因此，设备可以包括而不 限于节点、服务器、计算机、装置或者其它类型的设备。该设备通常包括一个 或多个网络接口，其用于通信网络上的通信以及相应地配置为执行设备功能的 处理器(例如，具有内存以及其它外设和/或特定应用硬件的微处理器)。通信 网络一般可以包括公共和/或私人网络；可以包括局域、广域、城域存储和/或 其它类型的网络；还可以采用通信技术，包括而不限于模拟技术、数字技术、 光学技术、无线技术(例如，蓝牙)、网络技术以及互联网技术。

还应当注意的是，设备可以使用通信协议和消息(例如，由设备创建、发 送、接收、存储和/或处理的消息)，并且这样的消息可以由通信网络或者媒介 传递。除非上下文另有需要，本发明不应当被解释为限于任意特定的通信消息 类型，通信消息格式，或者通信协议。因此，通信消息一般可以包括而不限于， 帧、包、数据报、用户数据报、单元、或者其它类型的通信消息。除非上下文 另有需要，对特定通信协议的参考是示例性的，并且应当理解的是，可选实施 例可以适当地采用该通信协议的变型(例如，随时间进行的协议的修改或者延 伸)或者将来已知的或者开发的其它协议。

还应当注意的是，本文中可能对逻辑流进行了描述以说明本发明的各个方 面，其不应当被解释为将本发明限定至任意特定的逻辑流或者逻辑实施。描述 的逻辑可以被划分成不同的逻辑块(例如，程序、模块、功能或者子程序)而 不改变总体的结果或者脱离本发明的真正保护范围。通常，可以使用不同逻辑 构造(例如，逻辑门、循环元、条件逻辑以及其它逻辑构造)实施，或者以不 同的顺序增加、修改、省略、执行逻辑要素，而不改变总体的结果或者脱离本 发明的真正保护范围。

上述的示例性实施例包括用于处理器(例如，微处理器、微控制器、数字 信号处理器或者通用目的计算机)使用的计算机程序逻辑和基于硬件的逻辑。 基于硬件的逻辑可以包括用于可编程的逻辑设备(例如，现场可编程门阵列 (Field Programmable Gate Array,FPGA)或者其它PLD)、独立组件、集成电 路(例如，特定应用集成电路(Application Specific Integrated Circuit，ASIC))， 或者包括它们的任意组合的任意其它装置来使用的可编程的逻辑。计算机程序 逻辑实施一些或全部的描述的功能，通常是被实施为计算机程序指令的集合， 其中，计算机程序指令被转换为计算机可执行的形式，如此存储在计算机可读 介质中，并且在操作系统的控制下由微处理器执行。基于硬件的逻辑实施一些 或全部的描述的功能，可以使用一个或多个适当配置的FPGA来进行实施。

计算机程序逻辑实施本文中先前的描述的所有或者部分的功能可以体现 为各种形式，包括但不限于源代码形式、计算机可执行形式以及各种中间形式 (例如，由汇编器、编译器、链接器或者定位器生成的形式)。源代码可以包 括用于各种操作系统或者操作环境使用的以任意的各种程序语言(例如，对象 代码、汇编语言或者高级语言，诸如Fortran，C，C++，JAVA，或者HTML) 实施的一系列计算机程序指令。源代码可以定义并且使用各种数据结构以及通 信消息。源代码可以处于计算机可执行形式(例如，经由解释器)，或者源代 码可以(例如，经由翻译器，汇编器，或者编译器)被转换至计算机可执行形 式。

计算机程序逻辑实施所有或者部分的本文先前的描述功能可以在单一处 理器上(例如，并行地)在不同时间进行执行，或者可以在多个处理器上在相 同的或者不同时间进行执行，并且可以在单一操作系统进程/线程或者在不同 操作系统进程/线程下运行。因此，术语“计算机处理”一般是指计算机程序 指令集合的执行，而不管不同的计算机进程是否在相同的或者不同处理器上进 行执行，并且不管不同的计算机进程是否运行在相同的操作系统进程/线程或 者不同操作系统进程/线程下。

可以以任意形式(例如，源代码形式、计算机可执行形式或者中间形式) 或永久地或暂时地在有形的存储介质诸如半导体存储器设备(例如，RAM、 ROM、PROM、EEPROM、或者快闪可编程的(Flash-Programmable)RAM)、 电磁存储器设备(例如，软盘或者固定的盘)、光学存储器设备(例如，CD-ROM)、 PC卡(例如，PCMCIA卡)或者其它存储器设备中固定计算机程序。可以以 任意形式以信号固定计算机程序，其中，所述信号使用任意的各种通信技术可 发送至计算机，所述通信技术包括但不限于模拟技术、数字技术、光学技术、 无线技术(例如，蓝牙)、网络技术、以及互联网技术。计算机程序可以以任 意形式分发为可移动存储介质以及打印的或者电子文档(例如，压缩包装软件)， 用计算机系统预加载(例如，在系统ROM或者固定的盘上)，或者经通信系 统(例如，因特网或者万维网)从服务器或电子公告板分发。

硬件逻辑(包括用于可编程的逻辑设备使用的可编程的逻辑)实施本文中 先前的描述的所有或者部分的功能可以使用传统的手动方法来设计，或者使用 各种工具诸如计算机辅助设计(CAD)、硬件描述语言(例如，VHDL或AHDL) 或PLD编程语言(例如，PALASM，ABEL或CUPL)进行设计、捕获、模拟 或电子地记载。

可以或永久地或暂时地在有形的存储介质诸如半导体存储器设备(例如， RAM、ROM、PROM、EEPROM、或者快闪可编程的(Flash-Programmable) RAM)、电磁存储器设备(例如，软盘或者固定的盘)、光学存储器设备(例 如，CD-ROM)、或者其它存储器设备中固定可编程的逻辑。可以以信号固定 可编程的逻辑，其中，所述信号使用任意的各种通信技术可发送至计算机，所 述通信技术包括但不限于模拟技术、数字技术、光学技术、无线技术(例如， 蓝牙)、网络技术、以及互联网技术。可编程的逻辑可以分发为可移动存储介 质以及打印的或者电子文档(例如，压缩包装软件)，用计算机系统预加载(例 如，在系统ROM或者固定的盘上)，或者经通信系统(例如，因特网或者万 维网)从服务器或电子公告板分发。当然，本发明的一些实施例可以被实施为 软件(例如，计算机程序产品)以及硬件的组合。而本发明的其它实施例被实 施为整体硬件或者整体软件。

本发明可以以其他特定形式来体现而不脱离本发明的真正范围，并且基于 这里的教导对于本领域技术人员许多变化和修改将是清楚的。对“本发明”的 任何引用都意在指本发明的示例性实施例，并且不应被解释为是指本发明的所 有实施例，除非上下文另有要求。在所有方面都应仅是说明性地而不是限制性 地考虑所述实施例。