渐进式备份的基于片段的高延展的去复本系统与方法

摘要

本发明涉及一种渐进式备份的基于片段的高延展的去复本系统与方法。在此系统中，一主装置位于一次级存储节点端，可接收至少一渐进式更新、多个指纹、多个映射的个体备份，将去复本功能分散到至少一从属装置，并通过丛集多个在一个数据局部单元的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的每一片段汇总结构，在多个片段上执行数据去复本，其中，稳定片段具有一固定的取样率，而不稳定的片段则指定随时间变化的取样率。

权利要求

1.一种渐进式备份的基于片段的高延展的去复本系统，该系统包含：一主装置，位于一次级存储节点端，该主装置可接收至少一渐进式更新、去复本的多个片段的多个指纹、多个逻辑区块地址至物理区块的映射个体；

其中该主装置还包括至少一分散器，将去复本功能分散到位于一数据节点端的至少一从属装置，并通过丛集多个在数据节点上的数据本地单元的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的每一片段汇总结构，在该多个片段上执行数据去复本，其中该数据本地单元称为子数据筒，其是基于伪物理区块范围与指纹内容且保留指纹局部性的渐进式更新的数据筒。

2.如权利要求1所述的去复本系统，其中该系统还包括该至少一从属装置，并执行并行式去复本，以利用位于该数据节点端的计算能力。

3.如权利要求2所述的去复本系统，其中每一从属装置还包括：一指纹管理器，以维持该指纹缓存存储器，除了指纹的替换之外；以及一数据筒管理器，以维持该数据筒缓存存储器，除了数据筒的替换之外。

4.如权利要求1所述的去复本系统，其中多个指纹数据筒以一种分散方式来存储至与获取于该次级存储节点，并且一指纹缓存存储器与一数据筒缓存存储器也在不同的数据节点上被分散与分割。

5.如权利要求2所述的去复本系统，其中该并行式去复本为片段式去复本，并且是依据一种一致性哈希法，将输入片段的每一指纹映射至该数据节点端上的一数据节点。

6.如权利要求3所述的去复本系统，其中该至少一从属装置的每一从属装置还包括一数据筒更新器，用于在一本地数据节点写入多个子数据筒。

7.一种渐进式备份的基于片段的高延展的去复本系统，该系统包含：一主装置，位于一次级存储节点端，该主装置可接收至少一渐进式更新、去复本的多个片段的多个指纹、多个逻辑区块地址至物理区块的映射个体；

其中该主装置还包括至少一分散器，将去复本功能分散到位于一数据节点端的至少一从属装置，并通过丛集多个在数据节点上的数据本地单元的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的每一片段汇总结构，在该多个片段上执行数据去复本，其中该可变取样率是以一种最近最少使用顺序为基础。

8.如权利要求7所述的去复本系统，其中该数据筒是以多个伪物理区块地址为基础，来保存每一卷宗逻辑区块地址里的局部性，并且区别于其他卷宗的区块地址。

9.如权利要求8所述的去复本系统，其中该每一片段汇总结构由下列来达成：该多个片段中，大于一阈值的每一片段具有一汇总片段指纹；以及该汇总片段指纹被匹配时，表示已完成在该片段中的去复本，并且不需要个别的检查片段内的指纹。

10.一种渐进式备份的基于片段的高延展的去复本系统，该系统包含：一主装置，位于一次级存储节点端，该主装置可接收至少一渐进式更新、去复本的多个片段的多个指纹、多个逻辑区块地址至物理区块的映射个体；

其中该主装置还包括至少一分散器，将去复本功能分散到位于一数据节点端的至少一从属装置，并通过丛集多个在数据节点上的数据本地单元的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的片段汇总结构，在该多个片段上执行数据去复本，其中该数据本地单元称为子数据筒；

其中该至少一分散器还包括：

一指纹分散器，映射每一指纹至一哈希值，来决定一目的地数据节点，并等待该数据节点的一回应；以及一数据筒分散器，使用相同的一致性哈希法以分割一概念上的数据筒，并当作数个子数据筒，如此，一子数据筒、一指纹缓存存储器、以及一数据筒缓存存储器常皆驻于同一个数据节点。

11.如权利要求10所述的去复本系统，其中该概念上的数据筒分割为N个文件，N为该数据节点端的数据节点的数目，N个数据节点的每一节点负责存储该概念上的数据筒的一条纹，并且将该概念上的数据筒的一条纹当作一于数据筒。

12.如权利要求10所述的去复本系统，其中该主装置还包括一替换引擎，来存储一指纹缓存存储器与一数据筒缓存存储器的最近最少使用目录，以替换位于数据节点上子数据筒与指纹。

13.如权利要求10所述的去复本系统，其中该主装置还包括一映射更新器，依据该去复本的输出，将每一逻辑区块地址映射到一个区块的物理位置。

14.如权利要求10所述的去复本系统，其中该主装置还包括一单元检测器，检测运作中的输入指纹所对应的概念数据筒或是根据过往历史确定去复本单元的边界。

15.一种渐进式备份的片段式高延展的去复本方法，通过在一次级存储节点端的一主装置来执行，该方法包含：接收至少一渐进式更新、欲被去复本的多个输入片段的多个指纹、及多个从逻辑区块地址至物理区块的映射的个体；

丛集该多个在一数据本地单元的指纹，其中该数据本地单元称为子数据筒，其是基于伪物理区块范围与指纹内容且保留指纹局部性的渐进式更新的数据筒；

指定片段的可变取样率；以及

重建一个片段汇总结构，以避免在片段上执行数据去复本时不必要的输入与输出。

16.如权利要求15所述的去复本方法，该方法还包括：该主装置的至少一分散器执行并行式去复本，以利用位于一数据节点端的至少一参与节点的计算能力。

17.如权利要求16所述的去复本方法，其中该并行式去复本还包括：利用一加密哈希算法来计算出多个渐进更新区块的指纹；

依相同的一致哈希算法，来分散该多个渐进更新区块的多个指纹，以存储取样指纹索引缓存存储器与多个子数据筒至多个数据节点；

依该一致哈希算法，将每一数据筒片段索引分散到至少一参与数据节点；以及依该一致哈希算法，将该每一片段汇总结构分散到至少一参与数据节点。

18.一种渐进式备份的片段式高延展的去复本方法，通过在一次级存储节点端的一主装置来执行，该方法包含：接收至少一渐进式更新、欲被去复本的多个输入片段的多个指纹、及多个从逻辑区块地址至物理区块的映射的个体；

丛集该多个在一数据本地单元的指纹；

指定片段的可变取样率；以及

重建一个片段汇总结构，以避免在片段上执行数据去复本时不必要的输入与输出，该方法还包括：分割该多个渐进式更新的多个区块，以作为多个输入片段；

查询一内存中的取样的指纹索引，以找出该多个输入片段的每一指纹，并回传一对相对应的数据筒识别码与片段识别码；

当一存储片段与一输入片段是相同时，则以该对相对应的数据筒识别码与该片段识别码来查询一内存中的片段式汇总，以决定是否查询该对相对应的数据筒与片段，否则，查询一内存数据筒存储缓存存储器，来决定是否载入缓存相对应的数据筒至缓存；以及当没有缓存该数据筒时，自一盘片数据筒存储元件，载入该相对应的数据筒，并查询一每一数据筒片段索引，以找出路由至该相对应的数据筒的一特定指纹的一偏移量，以取得该特定指纹的片段信息。

19.一种渐进式备份的片段式高延展的去复本方法，通过在一次级存储节点端的一主装置来执行，该方法包含：接收渐进式更新、欲被去复本的多个输入片段的多个指纹、及多个从逻辑区块地址至物理区块的映射的个体；

丛集该多个在一数据本地单元的指纹；

指定片段的可变取样率；以及

重建一个片段汇总结构，以避免在片段上执行数据去复本时不必要的输入与输出，其中一基本分享单元BSU片段被定义为产生之后就不会变更的一存储片段，并且该多个输入片段的该可变取样率是以下列方式来实现：对于每一BSU片段，只取样一个指纹；以及

对其它非BSU片段，指定不同的取样率。

20.一种渐进式备份的片段式高延展的去复本方法，通过在一次级存储节点端的一主装置来执行，该方法包含：接收渐进式更新、欲被去复本的多个输入片段的多个指纹、及多个从逻辑区块地址至物理区块的映射的个体；

丛集该多个在一数据本地单元的指纹，其中该数据本地单元称为子数据筒；

指定片段的可变取样率；以及

重建一个片段汇总结构，以避免在片段上执行数据去复本时不必要的输入与输出；

其中，所述方法还包括：

该主装置的至少一分散器执行并行式去复本，以利用位于一数据节点端的至少一参与节点的计算能力；

其中该并行式去复本还包括：

利用一加密哈希算法来计算出多个渐进更新区块的指纹；

依相同的一致哈希算法，来分散该多个渐进更新区块的多个指纹，以存储取样指纹索引缓存存储器与多个子数据筒至多个数据节点；

依该一致哈希算法，将每一数据筒片段索引分散到至少一参与数据节点；以及依该一致哈希算法，将该每一片段汇总结构分散到至少一参与数据节点；以及其中，每一片段汇总结构被分散至位于至少一参与数据节点，并且在该至少一参与节点上存储该片段汇总结构。

说明书

渐进式备份的基于片段的高延展的去复本系统与方法

技术领域

[0001] 本公开涉及一种渐进式备份(incremental backkups)的基于片段的(segment-based)高延展的(scalable)去复本(de-duplicated)系统与方法。

背景技术

[0002] 大部分的数据去复本技术着重于完整备份(full backups)，即使所有逻辑区块中仅一小部分已经被变更，一逻辑卷宗的所有逻辑区块会以现存的区块去复本。

[0003] 在一种已知的稀疏索引(sparse indexing)方法中，以取样指纹索引(sampling fingerprint index)来取代完整指纹索引(whole fingerprint index)，将此指纹索引适当地配置于磁盘对磁盘(Disk to Disk，D2D)数据备份系统的内存(Random Access Memory，RAM)中。取样指纹索引的洞察是，被复制的数据区块(duplicated data blocks)会趋向于以明显的长度(non-trivial length)存储在一个连续的范围里。在此范围内的取样指纹值(sampling fingerprint value)的匹配(matching)意味着高机率的完整范围的匹配。在所有候选的取样指纹中，选择冠军者作为去复本的对象。稀疏指纹索引方法是依据一固定取样率来选取样本指纹。在另一种已知的方法中，指纹是依据数据片段(segment)的时域区域性(temporal locality)来取样。如果条件符合的话(一时间周期；一固定计数)，在稀疏区块索引(sparse chuck index)中的数据片段的元素(entries)会被删除或裁剪(pruned)。被取样的指纹的每一元素最多指向R个数据筒(container)。换句话说，此方法利用一最近最少使用的(Least Recently Used，LRU)目录，来降低数据筒的取样率。

[0004] 在另一种已知的方法中，使用布隆过滤器(bloom filter)来决定一指纹是否在指纹索引里。此布隆过滤器不论这些区块的历史为何，盲目地记录所有区块的全部指纹。另一种已知的方法是每一文件有一整个文件哈希值映射(whole-file-hash)，意味着此整份文件哈希映射的一个匹配意指此整份文件是一个副本，此文件中的个别指纹不用被检查。此方法是基于文件来进行去复本。每一文件具有一代表性的(representative)指纹。指纹索引中的元素依据模运算(modular operation)或其他分散式的哈希映射表功能，一个接一个被分散至K个节点(node)。对应于一指纹索引元素的整个数据筒会被分散至与此指纹索元素相同的节点。如果两个指纹索引元素有相同的数据筒，但是被分散在两个不同节点，此相同的数据筒就会被复制在两个节点上。当一个文件被备份，只有代表性的指纹被用来路由(route)此文件至一节点，此文件的其他所有指纹不被用来做路由的目的。

[0005] 一些已知的美国专利提供去复本的技术。例如，在一已知技术中，数据区块的数个指纹记录依据此指纹值(fingerprint value)的一部分来分散至子节点。指纹记录具有执行数据去复本的完整信息。此技术没有揭示指纹数据筒的概念。在另一已知技术中，采用一种固定前置网络(Fixed Prefix Network，FPN)的修正版本，依一预定的数据冗余层次(data redundancy level)来分散数据区块。因为此存储器是一种内容可定址(content-addressable)的存储器，此技术没有揭示指纹索引与数据筒。另一已知技术是依据指纹来分散区块。第一步骤是依据指纹值的k个最低位(Least-Significant-Bit)将区块分割而成数个部分。第二步骤是利用一分散式哈希表(Distributed Hash Table，DHT)，将此数个部分映射到一物理节点(physical node)。每一数据节点备有一个加密钥(encrypted key)的队列(queue)，以及一个用来搜寻此队列以发现复本的一个请求(request)。

发明内容

[0006] 本公开的实施范例可提供一种渐进式备份的基于片段的高延展的去复本系统与方法。

[0007] 在一实施范例中，所公开者涉及一种渐进式备份的片段式高延展的去复本系统。此系统包含一主装置(maste device)位于一次级存储节点端(secondary-storage node side)。此主装置可接收至少一渐进式更新、去复本多个片段的多个指纹、多个逻辑区块地址至物理位置的映射的个体，并将去复本功能分散到位于一数据节点端的至少一从属装置，并通过丛集多个本地数据单元(称为数据筒)的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的每一片段汇总结构(per-segment summary structure)，在多个片段上执行数据去复本。

[0008] 在另一实施范例中，所公开者涉及一种渐进式备份的基于片段的高延展的去复本方法。此方法包含：对于多个欲被去复本的区块的多个渐进式更新，丛集多个在一数据局部单元(称为数据筒)的指纹；分割此多个渐进式更新的多个区块，以作为多个输入片段；查询一内存中(in-memory)取样的指纹索引，以找出此多个输入片段的每一指纹，并回传一对相对应的数据筒与片段；当存在一已存储的片段与此输入片段是相同时，则以此对相对应的数据筒与片段来查询一内存中的片段式汇总(segment-based summary)，以决定是否撷取此对相对应的数据筒与片段，否则，查询一内存中数据筒存储缓存存储器(cache)，来决定是否载入相对应的数据筒；当没有缓存此数据筒时，自一盘片(on-disk)数据筒存储元件，载入此相对应的数据筒，并查询每一数据筒片段索引(per-container segment index)，以找出路由至此相对应的数据筒的一特定指纹的一偏移量(offset)，以取得(retrieve)此特定指纹的片段信息。

[0009] 现在配合下列附图、实施范例的详细说明及权利要求书，将上述及本公开的其他特征与优点详述于后。

附图说明

[0010] 图1是在一渐进式备份的基于片段的高延展的系统里的一个高阶数据流的范例示意图，并与本公开的某些实施范例一致。

[0011] 图2是一范例示意图，说明当K＝2时，如何进行片段存储，并与本公开的某些实施范例一致。

[0012] 图3是一范例示意图，说明一数据筒的内容，并与本公开的某些实施范例一致。

[0013] 图4是一渐进式备份的基于片段的高延展的去复本系统的一个架构范例示意图，并与本公开的某些实施范例一致。

[0014] 图5是片段的高延展的去复本系统的分散式去复本架构的一个范例示意图，并与本公开的某些实施范例一致。

[0015] 图6是一范例示意图，说明如何从两个参与节点去重建一片段，并与本公开的某些实施范例一致。

[0016] 图7是一范例示意图，说明片段的高延展的去复本系统的运作流程，并与本公开的某些实施范例一致。

[0017] 图8是图7的详细运作的一个工作范例，并与本公开的某些实施范例一致。

[0018] 图9是一范例示意图，说明并行式去复本的运作流程，并与本公开的某些实施范例一致。

[0019] 图10是图9的详细运作的一个工作范例，并与本公开的某些实施范例一致。

[0020] 【主要元件符号说明】

[0021] 110内存中的取样指纹索引缓存存储 120内存中的片段式汇总

[0022] 器

[0023] 130内存中的数据筒存储缓存存储器 141磁盘数据筒存储设备

[0024] 143磁盘中的指纹索引

[0025] 300数据筒 310每一数据筒指纹索引

[0026] 320最近最少使用目录 330存储片段

[0027] 340汇总结构 341片段索引

[0028] 342汇总指纹

[0029] 400片段式高延展的去复本系统 410主装置

[0030] 412多个区块的渐进更新 414去复本的多个片段的

[0031] 指纹

[0032] 416多个逻辑区块地址至物理位置的映

[0033] 射的个体

[0034] 501指纹分散器 502数据筒分散器

[0035] 503替换引擎 504单元检测器

[0036] 505映射更新器 511指纹管理器

[0037] 512数据筒管理器 513数据筒更新器

[0038] 601节点 602节点

[0039] 710对于多个欲被去复本的区块的多个渐进式更新，丛集多个在一本地数据单元(称为数据筒)的指纹

[0040] 720分割此多个渐进式更新的多个区块，以作为多个输入片段

[0041] 730查询一内存中的取样的指纹索引，以找出此多个输入片段的每一指纹，并回传一对相对应的数据筒与片段

[0042] 740当存在一已存储的片段与此输入片段是相同时，则以此对相对应的数据筒与片段来查询一内存中的片段式汇总，以决定是否撷取此对相对应的数据筒与片段，否则，查询一内存中的数据筒缓存，来决定是否缓存此数据筒

[0043] 750当没有缓存此数据筒时，自一盘片数据筒存储元件，载入此相对应的数据筒，并查询一每一数据筒片段索引，以找出路由至此相对应的数据筒的一特定指纹的一偏移量，以取得此特定指纹的片段信息

[0044] 910利用一加密的哈希值来计算出多个渐进更新区块的指纹

[0045] 920依一致的哈希值将此多个指纹分散，并存储于一取样指纹索引缓存存储器与子数据筒

[0046] 930依一致的哈希值将每一数据筒片段索引分散到至少一参与节点[0047] 940依一致的哈希值将每一片段汇总结构分散到至少一参与节点具体实施方式

[0048] 当一主要的存储系统渐进地追踪更新的区块，并且只有备份这些渐进更新的区块(incremental changed blocks)时，本公开的实施范例可提供一种渐进式备份的片段式高延展的去复本系统与方法。具体地说，假设此主要的存储系统从最新的快照(渐进式更新追踪)的一快照图像来追踪更新的区块，并且只有更新的区块被当作是此备份存储系统的输入。

[0049] 本公开的实施范例将焦点放在以片段为基础的四个方面，以影响数据去复本比例(data de-duplication ratio，DDR)尽量为最小的方式，来改善去复本的数据传输量(throughput)：(1)丛集多个在一个数据局部单元(称为数据筒)的指纹；(2)多个片段的可变取样率，稳定且泛用的(popular)片段具有一固定的取样率，而去复本的“非泛用的(unpopular)”目标片段则指定较低的取样率；(3)在去复本时，避免不必要的输入与输出的每一片段汇总结构；(4)分散式的去复本，来利用多个参与存储节点的运算能力。

[0050] 就第一个方面来说，数据筒是依去复本的历史记录来建构，而非依纯逻辑地址接近度(pure logical address proximity)来建构。对于输入的渐进式更新，数据局部性的语义是更难以捉摸的，因为很难预测在此渐进式更新流(incremental changes stream)中会出现什么情况。在本实施范例中，互相分享内容的所有渐进式的更新都会被放入同一个数据筒，以捕捉被同组应用而更新的数据的局部性。

[0051] 就第二个方面来说，将指纹设置在一内存中(RAM)，片段的取样率是用下列方式来区分的，亦即稳定片段具有一固定的取样率，而去复本的不稳定的片段则指定随时间变化的取样率。一个稳定片段的定义是去复本历史记录中没有改变的一片段。此稳定片段直觉上是副本之间倾向分享大于一区块的一物件。通过观察数据去复本的历史记录，可指出此稳定片段，并且可使用在此稳定片段中的一个指纹来代表在指纹索引中的片段。而对于非泛用片段，可采用一种最近最少使用的策略来变化在被取样的指纹索引中所有非泛用的片段的取样率。

[0052] 就第三个方面来说，每一片段汇总结构可以避免去复本的不必要输入与输出。对于较大容量且几乎很少改变的片段，不需要一个接一个的比较一片段中的个别指纹，因此可减少从磁盘中撷取个别指纹的磁盘输入/输出(disk I/O)。每一片段汇总结构可依下列原则来形成：(1)大于一阈值(threshold)的片段具有一整体片段指纹，以及(2)整体片段指纹匹配时，表示在此片段中，不需个别得检查区块指纹。相关片段的整体片段指纹可以构成一Merkle树(tree)。

[0053] 就第四个方面来说，本公开的实施范例在分散式存储系统中，可将此去复本功能分散至多个参与存储节点。依据此指纹的一致性哈希(consistent hashing)方法，将指纹索引与数据筒分散及分开至多个参与存储节点(participating storage node)。并且，依据汇总(root summary)的一致性哈希方法，所有汇总结构也被分散及分开至多个参与存储节点。

[0054] 现在，本公开的实施范例的渐进式备份的基于片段的高延展系统可用Hadoop分散式文件系统(Hadoop Distributed File System，HDFS)来实现，作为基本的存储器(underlying storage)。然而，本公开的实施范例是可与任何备有多个数据节点的分散式存储系统来共同运作的。在下列讨论中，假设Hadoop分散式文件系统为基础的存储器阶层(underlying storage layer)。本公开的实施范例可与一次级存储系统共同运作。此渐进式备份的基于片段的高延展系统可包含一元件并位于次级服务器端，来分散此去复本的工作量(workload)；还可包括一第二元件并位于数据节点端，来对传送至特定数据节点的数据区块去执行去复本。

[0055] 在探讨去复本的细节之前，图1是在一渐进式备份的基于片段的高延展的系统里的一个高阶数据流(high-level data flow)的范例示意图，并与本公开的某些实施范例一致。图1省略渐进式备份的基于片段的高延展系统中的并行部分，此部分将在后面陈述。

[0056] 参考图1，首先，将数个渐进更新分割成数个片段。每一片段通过发出(issue)片段内的每一个别指纹的指纹查询(fingerprint query)，来查询一内存中的取样指纹索引(Sampled Fingerprint Index，SFI)缓存存储器110。每一个别指纹的查询则传回一对的<数据筒识别码，片段识别码>。在同一片段内指纹的查询会被聚成一群，以找出是否一已存储的片段相同于一输入片段。是的话，此输入片段以此对<数据筒识别码，片段识别码>来查询一内存中的片段式汇总120，以决定是否需要载入此数据筒。否则，以此数据筒辨识码来查询一内建存储器数据筒存储缓存存储器130，以查看此数据筒是否被缓存，如果没有被缓存的话，则自一磁盘数据筒存储设备141载入此数据筒。

[0057] 载入此数据筒后，每一输入片段在此数据筒中查询一每一数据筒片段索引(per-container segment index)，以找出路由至此数据筒的一指纹的偏移量(offset)。此偏移量可以用来取得此区块的物理位置，因为指纹以一阵列(array)方式存储在此数据筒内。通过此偏移量查询此片段索引可以取得特定指纹的片段信息。磁盘指纹索引143包括从取样指纹索引释出的指纹。磁盘指纹索引143没有包括所有数据筒的全部指纹。

[0058] 如果有去复本的话，数据流的输出是此输入片段里逻辑区块地址(logical block address)的物理位置(physical location)。具体来说，产生的逻辑至物理的一更新目录(L2P-CL)是当做输出。

[0059] 在基于片段的高延展的去复本系统中，片段是一基本单元，并且可由目前输入(current input)与输入的历史记录(input history)来决定。具体来说，如果数个区块在输入中是相邻的话，则这些区块属于相同的输入片段。然后，此输入片段与已存储的片段(stored segment)做比较，以形成存储片段(store segment)。当输入片段与存储片段互相冲突时，每一指纹最多可属于K个片段。如果一指纹超过K个片段时，K≥2，则从此指纹中移除最旧的片段。

[0060] 图2是一范例示意图，说明当K＝2时，如何进行片段存储，并与本公开的某些实施范例一致。参考图2，在输入片段中的号码代表逻辑区块号码，而在存储片段中的号码代表在一数据筒的指纹偏移量。如输入-1，有片段a与片段b共两个输入片段。去复本之后，发现片段a是存储片段1的一个复本，但是发现输入片段b横跨两个存储片段(存储片段2与存储片段3)。存储片段1与输入片段a是相同的，所以存储片段1是没有更新。反之，具有偏移量从52至55的指纹映射至存储片段2与输入片段，共对应至两个片段。输入片段c匹配于指纹51至55。因为K＝2，亦即每一指纹指允许属于两个片段，对于指纹52至
55，则移除存储片段2(即最旧的片段)。替代的是，将指纹52至55映射至两个片段，亦即输入片段b与输入片段c。

[0061] 事实上，本公开的实施范例允许每一区块，最多参与到K个片段中，即保持追踪曾经与一区块相关的最后K个片段。本公开的实施范例中，使用一区间树(interval tree)来保持追踪逻辑区块地址范围映射至此片段。下列叙述中，此区间树称为片段索引(segment index，SI)。

[0062] 一基本分享单元(Basic sharing unit，BSU)被定义为产生之后就不会被变更的一存储片段。在基本分享单元礼的所有指纹一次全部都出现，所以一个指纹就足以代表此相对应的基本分享单元。

[0063] 因为一指纹索引无法配置在(fit into)内存中，本公开的实施范例提出取样指纹(sampling fingerprint)的概念，将指纹索引配置在一指纹索引缓存存储器中。此取样是依个别片段(individual segment)为基础。此指纹索引缓存存储器可被实现为，例如一哈希表(hash table)。指纹索引缓存存储器的每一元素(entry)是以一指纹值(fingerprint value)为键值，并且此元素包括一数据筒辨识码。甚且，如果多个数据筒分享相同一指纹的话，此数据筒辨识码最多可指向至K(如K＝2)个片段辨识码。注意的是，此K是与前述的K相同的。

[0064] 在本公开的实施范例中，有两种改变此片段取样的方式：(1)片段为基本分享单元的话，取出来自于一基本分享单元所有指纹的第一指纹，来代表此基本分享单元。注意的是，此取样不会损害去复本率，因为在一基本分享单元里的指纹总是一次全部都出现。然而，因为节省存储器的空间，所以可以改善此去复本的数据传输流量。(2)当存储器的空间不足时，不需减少所有片段的取样率，而是对这些长时间未被参照的片段，当取样率达到一个最小值时，在被他们被释出前，先减少它们的取样率。一种最近最少使用的目录(LRU list)可用在这个用途。特别是，基本分享单元片段具有以最近最少使用顺序为基础的一个虚拟取样率(virtual sampling)。当基本分享单元到达此最近最少使用目录的尾端时，会减少此虚拟取样率。

[0065] 数据筒的含意是以群聚有数据局部性的指纹，来摊提载入一数据筒的输入/输出的成本。渐进式备份的数据局部性是不同于整体备份。本公开的实施范例的渐进式备份的片段式高延展系统是依据去复本历史记录来关连多个片段。一开始，通过结合逻辑卷宗辨识码与逻辑区块地址，来自不同的逻辑卷宗的逻辑区块地址包含一个统一的伪(unified pseudo)逻辑区块地址。例如，对于在逻辑卷宗1的逻辑区块地址500，此伪逻辑区块地址是(1，500)。每一数据筒起始时可以是半满的(half full)，以容纳此数据筒未来的更新。由在此去复本历史记录随着时间累积，与一存储片段分享至少一单依指纹的那些片段会被放入与此存储片段相同的数据筒。

[0066] 图3是一范例示意图，说明一数据筒的内容，并与本公开的某些实施范例一致。在图3的范例中，数据筒300的内容可包括一每一数据筒指纹索引310、逻辑区块地址的K对物理位置和存储片段330的信息、以及一汇总结构340。每一数据筒指纹索引310将同一数据筒的指纹安排于一哈希表中，来加速寻找此数据筒里的指纹值。每一指纹指向最后的K(例如K＝2)片段。直觉的理解是(1)如果有任何基本分享的话，此最后的K片段在日后最有可能成为此基本分享单元，以及(2)两个片段是极不可能意外地分享一些相互连结的指纹，而非分享一整体片段。注意的是，此K是与前述的K相同的。

[0067] 当一数据筒需要被分割时，保留一个最近最少使用的目录给数据筒300，如此数据筒300会依据存取历史(access history)而被分割。每一最近最少使用目录是以时间戳记(timestamp)为键值，并且包含做为内容的指纹值。

[0068] 如前所述，在一数据筒内片段之间的关系可以分成两种类型。第一类型是在相同伪逻辑区块地址范围内的两片段；第二类型是分享指纹的两个片段。如果没有提供汇总信息的话，此两片段的指纹则依一最近最少使用目录的顺序被置放在此数据筒中。因为会将每一片段汇总结构包括在内，所以，需要区别此两种类型。

[0069] 对于第一种类型的片段，每一片段不会再进一步处理，而是直接留在此数据筒中。对于第二种类型的片段，因为每一指纹最多可以指向K(如K＝2)个片段，片段根据历史可能需要被分割。如果一指纹指向超过K个片段，结果导致片段之间分享指纹，则在加入一新片段之前，会移除最旧的片段。

[0070] 所有的每一片段结构会被输入至汇总结构340。在汇总结构340里的每一元素是以一片段索引341为键值，并且其内容是由相对应片段的汇总指纹(Summary Fingerprint，SF)342所组成的。注意的是，并非所有片段都备有一汇总指纹342，只有较大容量(例如大于1000)的那些片段备有一汇总指纹，如此所有汇总结构得以配置在内存中。

[0071] 一数据筒可以依据一伪物理区块地址，但，既不是逻辑区块地址，也不是真正的物理区块范围。伪物理区块地址保存了在每一卷宗逻辑区块地址里的局部性，并且也可区别于其他卷宗的区块地址。例如，卷宗A与卷宗B分别具有逻辑区块范围(0，32M)与(0，16M)。此伪物理区块范围对卷宗A而言可以是(0，32M)，而伪物理区块范围对卷宗B而言可以是(32M，48M)。一数据筒可以依据两个片段的内容为基础。分享至少一指纹的两个片段可被置放于一数据筒内。并且，一数据筒保存指纹索引元素里的局部性。也就是说，此数据筒是一个基于伪物理区块范围与内容的且保留指纹局部性的数据筒(range and content-based locality-preserved fingerprint)。

[0072] 如上述，一个大于一阈值N的片段有一汇总指纹(summary index)。此汇总指纹可通过以N个指纹为数据内容以及算出此内容的一个指纹来算出。也就是说，汇总指纹是基于片段的。并且，一汇总指纹的特性也是，N个指纹中的一个指纹的改变可以极大地改变此汇总指纹。结果，如果两个片段的汇总指纹相互匹配的话，此两个片段是不同的机率会小到只存在于理论中。换句话说，如果汇总指纹匹配的话，则此两个片段是完全相同的(identical)。

[0073] 片段式汇总索引可通过合适的选择N，而配置在一存储器中，例如随机存取存储器。每一索引元素以一对<数据筒辨识码，片段辨识码>做为键值。内容可包括汇总指纹、片段长度、以及包括此片段的物理区块。此物理区块也同样是被存储的，因为如果汇总指纹匹配的话，则不需要缓存此数据筒，并且这些物理区块作为数据去复本时的目标物理区块。如上述，向指纹索引缓存存储器查询一数据筒之后，取得一数据筒辨识码以及最多K个片段辨识码。查询结果产生的<数据筒辨识码，片段辨识码>对被用来查询片段式汇总索引，以找出相对应的片段，此产生的片段的汇总指纹与一存储片段的汇总指纹做比较。为了减少因片段式汇总索引的存储器消耗量，并非所有在此片段里的物理区块都是个别地被存储。而是存储此物理区块范围来减少此存储器的消耗量。

[0074] 通过组合片段识别、可变的取样率、以及使用片段式汇总结构，图4是一渐进式备份的片段式高延展的去复本系统的一个架构范例示意图，并与本公开的某些实施范例一致。参考图4，片段式高延展的去复本系统400可包含一主装置410，位于一次级存储节点端。主装置410可接收多个输入，例如多个区块的渐进更新412、去复本的多个片段的指纹414、多个逻辑区块地址至物理位置的映射的个体416等，并且还包括至少一分散器(distributor)，来将至少一去复本功能分散给至少一从属装置(slave device)，如从属装置1至从属装置n，并通过丛集多个在一个本地数据单元(称为数据筒)的指纹、多个片段的可变取样率、以及一种避免不必要的输入与输出的每一片段汇总结构，在多个片段上执行数据去复本，其中，稳定片段具有一固定的取样率，而去复本的不稳定的片段则指定随时间变化的取样率。系统400还可包括至少一从属装置420，位于数据节点端，并执行并行式去复本，以利用位在此数据节点端的从属装置的运算能力。

[0075] 图5是片段式高延展的去复本系统的分散式去复本架构的一个范例示意图，并与本公开的某些实施范例一致。参考图5，在次级存储节点端，主装置410可包括一指纹分散器(fingerprint distributor)501与一数据筒分散器(container distributor)502。指纹分散器501可哈希每一个别指纹，来决定一目的地数据节点(destination data node)，并可等待此数据节点的回应。此回应可以是被一逻辑区块地址所指到的一目标物理区块(target physical block)。此回应有三个考虑的情况。

[0076] 第一个情况是，在一指纹索引缓存存储器中找到此指纹，并且此数据筒在一数据筒缓存存储器中已被缓存或是在此片段式汇总索引找到。在此情况下，此回应可包括一目标区块(去复本区块)的信息。对应此目标区块的原始区块可被做回收(disposed)。

[0077] 第二个情况是，在一指纹索引缓存存储器中找到此指纹，但是此数据筒在一数据筒缓存存储器中没有被缓存，并且此片段式汇总索引没有匹配。此数据筒被载入至一次级存储节点端的内存中。使用与数据统分散器502分散指纹时相同的哈希函数(hash function)，将此数据筒中的元素分散至相关的数据节点。位于一特定数据节点的相同数据筒的元素被组成一子数据筒(sub-container)。

[0078] 注意的是，数据筒分散器502没有直接写入数据筒。而是数据筒分散器502给位在此数据节点的每一子数据筒一个公用的文件名称(public file name)，如此，可同时取得属于相同数据筒的子数据筒。例如说，如果一数据筒有一识别码(identifier)0x01234，四个子数据筒分别被命名为0x01234.ip1、0x01234.ip2、0x01234.ip3、以及0x01234.ip4。当数据筒分散器502取得数据筒0x01234时，也向每一个别数据节点要求相对应的子数据筒。每一数据节点轮流读取子数据筒0x01234.ipI，ipI是特定数据节点的IP地址。在数据节点写入子数据筒的优点是在存取时，每一子数据筒备有一本地复本(local copy)，且此数据节点可通过它的本地磁盘，而不是通过网络取自其它数据节点，取得子数据筒。通过查询每一数据筒指纹索引，可以撷取对应此被查询指纹的元素，以取得此目标物理区块。

[0079] 第三个情况是，在一指纹索引缓存存储器中没有找到指纹。此指纹已被更新至一对应的数据筒。此原始物理区块则作为此目标物理区块。

[0080] 数据筒分散器502可使用已知的一致性哈希法加条纹(stripe)于一概念的数据筒，并分割为数个子文件，即数据筒条纹、指纹缓存存储器、以及数据筒缓存存储器可常驻于同一个数据节点。依据汇总指纹的相同且一致的哈希法，数据筒分散器502也负责去分散此片段汇总。

[0081] 主装置410还可包括一替代引擎(replacement engine)503来存储指纹缓存存储器与数据筒缓存存储器的最近最少使用目录，以确定子数据筒与指纹的替换。注意的是，指纹缓存存储器的此最近最少使用目录是依据数据筒，而不是个别的指纹。

[0082] 主装置410还可包括一单元检测器(unit detector)504来检测运作中(on the fly)的输入指纹所属的数据筒或是通过去副本历史辨别的一去复本单元的边界。检测此输入指纹的数据筒可如下进行。对于每一输入片段，起初没有此输入片段相对应的数据筒。如果此去复本的回应指出此输入片段属于一数据筒，则此数据筒是对应此输入片段的数据筒。否则，产生一个新数据筒来容纳此输入片段。一数据筒具有其大小(size)的上限。

[0083] 通过去副本历史辨别的一去复本单元的边界的进行如下说明。起初将每一输入片段视为一去复本单元(de-duplication unit)。此输入片段存储在一数据筒。具体来说，每一子数据筒存储物理区块，也存储与这些物理区块相关的此输入片段。下一次，此片段被查询时，以存储片段来检查此输入片段。如果是同一片段，则此片段可能在将来还是一样的片段。如果一片段经过一预定数目的去复本查询后，仍是维持同一个片段，则此片段被视为稳定，并且在此单元里的第一指纹可被挑出并做为被取样的指纹，如同上述。

[0084] 主装置410还可包括一映射更新器(mapping updater)505，依据此去复本的输出来更新映射到此卷宗的元数据(metadata)。

[0085] 在数据节点端，至少一从属装置的每一从属装置还可包括一指纹管理器(fingerprint manager)511，来维持此指纹缓存存储器，除了替换指纹之外。指纹的替换是由位于主装置410的替换引擎(replacement engine)503来协调。多个指纹被安排成一哈希表。每一指纹元素备有一数据筒辨别码目录(container identifier list)。此目录最多有K个元素、此数据筒内的指纹的偏移量、以及指向此相同数据筒的指纹的一指标(pointer)。以此指标，在相同数据筒中的所有指纹被组织成为一单一连结目录(linked list)。此连结目录的前端是此数据筒的第一个被取样的指纹。

[0086] 在替换引擎503中，指纹索引的最近最少使用目录的每一元素包括相对应的数据筒的第一个被取样的指纹的指纹值，以及此数据筒的辨别码。而此数据筒缓存存储器的最近最少使用目录的每一元素备有此数据筒辨别码。当一数据筒的指纹从指纹索引被释出时，这些元素被写至一磁盘，作为此指纹索引的一永久复本(persistent copy)。

[0087] 每一从属装置也可包括一数据筒管理器(container manager)512来维持此数据筒缓存存储器，除了数据筒的替换之外。数据筒管理器512可具备三个部分，亦即数据筒缓存存储器、数据筒格式、以及数据筒读取。对于此数据筒缓存存储器，其数据筒是以唯一的数据筒识别码作为健值，而组织成一哈希表，此与前述的数据筒缓存存储器相同。此数据筒格式是与前述的数据筒及图3相同的。关于读取数据筒，它以数据筒辨识码加上IP当做文件名称来读取基本文件系统的子数据筒。每一从属装置也可包括一数据筒更新器513，以供在此本地数据节点上写入子数据筒。为了加速写入速度，其更新是序列式地被写入至磁盘。

[0088] 因为数据筒被分散在所有参与节点上，存储片段的信息不是存储在单一的节点。而是将一片段内的偏移量存储在参与节点上。从参与节点上收集一片段的偏移量与片段辨识码后，则可重建此存储片段的信息。图6是一范例示意图，说明如何从两个参与节点去重建一片段，并与本公开的某些实施范例一致。此去复本是与图2相同的。片段1、2、3都是属于同的数据筒。加括号的(parenthesized)对(n，k)代表在第n个片段的第k个物理区块。例如，对(2，3)代表在第2个片段中的第3个物理区块。在本范例中，片段1、2、3平均地被分散至两个存储节点，如节点601与节点602。在查询此每一数据筒指纹索引之后，相对应的从属装置回复偏移量与片段辨识码。在主装置中重建片段1、2、3的被匹配的部分。
例如，来自节点601的对(1，0)与对(1，2)属于片段1，来自节点602的对(1，1)与对(1，
3)也是属于片段1。并且整个片段1也被重建，其中第0个与第2个区块来自节点601，而第1个与第3个区块来自节点602，则可重建整个片段1。然后，图2所述的片段辨识码方案可继续进行。

[0089] 请参考图7，图7是一范例示意图，说明片段式高延展的去复本系统运作流程，并与本公开的某些实施范例一致。在图7中，范例运作流程700可包含：对于多个欲被去复本的区块的多个渐进式更新，丛集多个在一数据局部单元(称为数据筒)的指纹，如步骤710所示。分割此多个渐进式更新的多个区块，以作为多个输入片段，如步骤720所示。查询一内存中的取样的指纹索引，例如内存中的的指纹索引110，以找出此多个输入片段的每一指纹，并回传一对相对应的数据筒与片段，例如<数据筒辨识码，片段辨识码>，如步骤730所示。当存在一存储片段与此输入片段是相同时，则以此对相对应的数据筒与片段来查询一内存中的片段式汇总，例如内存中的片段式汇总120，以决定是否查询此对相对应的数据筒与片段，否则，查询一内存中的数据筒存储缓存存储器，例如内存中的数据筒存储缓存存储器130，来决定是否载入此相对应的数据筒，如步骤740所示。当没有缓存此数据筒时，自一盘片数据筒存储元件，载入此相对应的数据筒，并查询一每一数据筒片段索引，以找出路由至此相对应的数据筒的一特定指纹的一偏移量，以取得此特定指纹的片段信息，如步骤750所示。如果有去复本的话，数据流的输出是此输入片段里逻辑区块地址的物理位置。

[0090] 步骤710还可包括，例如，输入一更新目录、输入此更新目录中多个区块的多个逻辑至物理对应元素、计算出在此更新目录中多个区块的指纹、通过去复本的历史记录为基础来重建数据筒，以撷取起因于同组应用上的改变的数据局部性等。当此输入片段大于一阈值T时，步骤730还可包括，例如，计算出此输入片段的汇总指纹索引、搜寻一指纹索引、找出物理区块的一缓存存储器、取得物理区块附加至此更新目录等。当一被匹配的存储片段是大于此阈值时，步骤740还可包括，例如，计算出此存储片段的汇总指纹、并更新汇总索引、检查此存储片段的一偏移量对(offset pair)、移除此片段索引中最旧的片段(每一指纹元素可包括一数据筒辨识码目录，最多指向K个元素)、对此数据筒更新新指纹、附加逻辑至物理目录至更新目录中，等等。此数据筒被缓存后，片段缓存存储器会被更新。步骤750还可包括，例如，当找到一满的(full)数据筒时，产生一个新数据筒，附加此输入片段至新产生的数据筒，以一序列方是来将数据筒记录至磁盘等。这些详细运作的子步骤在图
8的工作范例中可以找到。图8是图7的详细运作的一个工作范例，并与本公开的某些实施范例一致。此处省略已经提述的其它子步骤的细节。

[0091] 如前述，渐进式备份的片段式高延展的系统400可与一次级存储系统一起运作，片段式高延展的去复本系统400有两种装置。一种是在次级存储装置端上，来分散去复本的工作量；另一种装置是在数据节点端上，以将传送至特定数据节点的数据区块去复本。指纹数据可用一种分散的方式，来存储及取得于次级存储节点端的一次级存储服务器，并且此指纹缓存存储器与数据筒缓存存储器也可分散及分割至不同的数据节点上。通过一致的哈希法来分割数据筒、指纹、缓存存储器、以及数据筒缓存存储器。

[0092] 图9是一范例示意图，说明并行式去复本的运作流程，并与本公开的某些实施范例一致。参考图9，范例运作流程900可包含：利用一加密的哈希值(cryptographic hashing)来计算出多个渐进更新区块的指纹(步骤910)；依一一致的哈希值将此多个指纹分散，并存储于一取样指纹索引缓存存储器与数个子数据筒(步骤920)；依该一致的哈希值，将每一数据筒片段索引分散到至少一参与节点(步骤930)，如此，在每一数据节点(从属装置)上的片段索引可具有较小偏移量对；并且依该一致的哈希值，将每一片段汇总结构分散到至少一参与节点(步骤940)。此至少一参与节点在一数据节点端上可以是不同数据节点。此一致的哈希值为熟知的一致的哈希值。

[0093] 步骤910还可包括，例如，集合多个在更新目录中的渐进更新区块作为一输入片段目录，此至少一参与节点可在此取样指纹索引缓存存储器中查询此指纹等。在并行式去复本的期间，数据筒缓存存储器的载入与释出也需要此至少一参与节点的协助。图10是图9的详细运作的一个工作范例，并与本公开的某些实施范例一致。此处省略已经提述的其它子步骤的细节。

[0094] 综合上述，本公开的实施范例可提供一种渐进式备份的基于片段的高延展的去复本系统与方法，可经由数据筒的渐进更新的每一片段汇总指纹、多变的片段取样率、每一片段汇总结构、以及分散去复本至多各参与节点，并以影响数据去复本比例为尽量最小的方式，来改善去复本的数据传输量。

[0095] 然而，以上所述仅为本公开的实施范例而已，当不能依此限定本公开实施的范围。即大凡一本公开申请专利范围所作的均等变化与修饰，皆应仍属本公开权利要求书涵盖的范围内。