CN105051724B - 一种数据对象处理方法与装置 - Google Patents

Abstract

本发明提供了一种数据对象处理方法和装置，可以把数据对象划分为一个或多个分区；计算每个分区的采样压缩率，把采样压缩率具有共同特征且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；根据每个所述数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。应用本发明提供的技术，可以把数据对象拆分成数据块。

Description

一种数据对象处理方法与装置

技术领域

本发明涉及信息技术领域，特别有关于一种数据对象处理方法与装置。

背景技术

数据去重(Data Deduplication)是在数据集或数据流中发现和消除重复内容以提高数据的存储和/或传输效率的过程，又称重复数据删除(Duplicate DataElimination)，简称去重或重删。去重技术通常把数据集或数据流拆分成一系列数据单元，且对于重复的数据单元只保留一份，从而减少数据存储过程中的空间开销或传输过程中的带宽消耗。

如何把数据对象划分为易发现重复内容的数据单元，是需要解决的一个关键问题。数据对象划分为数据单元以后，可以计算数据块的哈希值h(·)作为指纹，把具有相同指纹的数据单元定义为重复数据。现有技术常用的去重数据单元包括文件、固定长度分块(Block)、基于内容的可变长度分块(Chunk)等。其中，基于内容的分块方法(ContentDefined Chunking，CDC)采用滑动窗口扫描数据并识别符合预设特征的字节串，并将字节串所在位置标记为分块边界，进而将数据集或数据流拆分为可变长度分块序列，该方法基于数据的内容特征选择分块边界，能够更敏感发现相似文件或数据流所共享的数据单元，从而被广泛用于各种数据去重方案。研究表明，在采用基于内容的分块方法拆分数据集或数据流时，分块粒度越小，发现重复数据的概率越高，去重效果也越好；但分块粒度变小，意味着划分给定数据集所获得的分块数量也越多，从而增加了索引开销和查找重复数据的复杂度，进而降低数据去重的时间效率。

期望长度是基于内容的分块(Content Defined Chunking，CDC)方法控制分块粒度的关键参数，一般情况下，CDC分块方法对给定的数据对象输出可变长度的分块序列，各分块的长度在统计上服从正态分布，期望长度用于调整正态分布的均值。通常，所述正态分布的均值表现为平均分块长度，由于正态分布下随机变量取均值的概率最高，平均分块长度也称峰值长度，其在理想情况下可等于期望长度。举例说明，在CDC方法中，实时计算滑动窗口内数据的指纹f(w-bytes)，当f(w-bytes)的某些位匹配预设值时，则选择滑动窗口所在位置为分块边界。由于数据内容的更新会导致哈希指纹的随机变化，若设定f(w-bytes)&0xFFF＝0为匹配条件，其中&为二进制域上的位与运算，0xFFF为4095的十六进制表示，则理论上f(w-bytes)随机变化4096次会出现一次指纹匹配，即滑动窗口每向前滑动4KB(4096字节)能发现一个分块边界，这种在理想条件下的分块长度即为CDC方法的期望分块长度(Expected Chunk Length)，简称期望长度。

为了在保持去重空间效率的同时尽量减少分块数量，现有技术提出一种基于内容的双峰分块方法。其核心思想是采用两种不同期望长度的变长分块模式，在把文件拆分成数据块时，通过查询去重存储系统判断候选分块的重复性，在重复数据与非重复数据之间的过渡区域采用小分块模式，而在非过渡区域采用大分块模式。

然而这种技术无法独立工作，分块计算设备在确定数据对象如何分块时，需要频繁的查询去重存储设备中已存在的数据块的指纹，去重存储设备中存储有数据去重后的数据块，根据候选分块的重复性判断是否遇到重复数据与非重复数据的过渡区域，进而确定最终采用何种分块模式。因此，这种现有技术给去重存储设备造成了查询负载压力。

发明内容

本发明实施例提供一种数据对象处理技术，可以把数据对象拆分成数据块。

第一方面，本发明实施例提供一种数据对象处理方法，该方法包括：把数据对象划分为一个或多个分区；计算每个分区的采样压缩率，把采样压缩率具有共同特征的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；根据每个所述数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。

第二方面，本发明实施例提供一种数据对象处理装置，该装置包括：分区划分模块，用于把数据对象划分为一个或多个分区；数据段生成模块，用于计算每个分区的采样压缩率，把采样压缩率具有共同特征的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；数据块生成模块，根据每个所述数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。

应用本发明实施例，先把数据对象划分为分区，再根据各个分区的压缩率把分区聚合为数据段，接着把拆分成数据块，实现了把数据对象拆分成数据块的效果。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单的介绍，下面描述中的附图仅仅是本发明的一些实施例，还可以根据这些附图获得其他的附图。

图1是一种数据对象处理方法实施例的流程图；

图2是一种数据对象处理方法实施例的流程图；

图3是一种数据对象处理方法实施例的流程图；

图4是一种数据对象处理方法实施例的流程图；

图5是一种数据对象处理方法实施例的流程图；

图6是一种数据对象处理装置实施例的结构图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明的技术方案进行清楚、完整的描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例所获得的所有其他实施例，都属于本发明保护的范围。

降低数据块的期望长度有利于获得更好的去重率，但同时也会增加数据块数量和相应的索引量，进而提高查找重复数据块的复杂度并制约去重性能。

现有技术提出在重复内容与非重复内容的过渡区域采用细粒度分块，在其他区域采用粗粒度分块，从而形成一种双峰的分块方法。但该方法在分块过程中需要频繁查询候选分块的重复性，从而给去重存储系统造成查询负载压力。此外，该方法的分块结果依赖于多版本数据的传输顺序，不具有稳定性。

本发明实施例提出一种基于内容和可压缩性的多峰数据去重分块方法，可以把数据对象拆分成数据块。具体而言，应用本发明实施例，先把数据对象划分为分区，再根据各个分区的采样压缩率把分区聚合为数据段，接着根据数据段的长度和采样压缩率选择期望长度把各数据段分别拆分成数据块，实现了把数据对象拆分成具有多峰长度分布的数据块序列的效果。

本发明实施例中，数据对象是指一段可以被操作的数据，例如文件或数据流。通过分块策略映射表维护压缩率区间、长度区间和期望分块长度之间的映射关系，数据段的压缩率越高、长度越长，则对应的期望分块长度也越大。

本发明实施例方法可以把数据对象拆分成数据块，拆分后的数据块可以作为数据去重的单元，从而可以减少存储空间占用又不丢失数据的前提下对数据对象进行存储或者传输，当然，拆分生成的数据块还可以用于数据去重以外的其他目的。本发明实施例包括：步骤(a)，数据对象(Data Object)输入分块设备，数据对象可以来自于分块设备外也可以来自于分块设备内部的存储器，例如是文件或者数据流，符合去重操作要求即可，本实施例不做限定；步骤(b)，把数据对象分成一个或多个分区(Block)，利用采样的方法估算每个分区的压缩率，查询分块策略映射表，把属于同一个压缩率区间的相邻的连续分区聚合为一个数据段(Segment)，其中，采样压缩率是对数据块可压缩性的衡量，当对整个分区进行采样时，采样压缩率和分区的压缩率相同；步骤(c)，对每个数据段，查询分块策略映射表，根据其对应的压缩率区间和长度区间选择一种期望长度，采用基于内容的分块方法按照选择的期望长度将数据段划分为分块(Chunk)序列；步骤(d)，对位于不同数据段且相邻的分块进行拼接，计算各分块的哈希值用于数据去重，其中拼接步骤属于可选步骤，也可以不拼接直接计算哈希值。步骤(b)利用分区序列的采样压缩率信息将数据对象重新划分为数据段序列，划分方法可以有多种，例如在另外一种实施方式中，步骤(b)也可以不参考压缩率区间，而是把采样压缩率差值小于指定阈值的相邻的连续分区聚合为一个数据段。

实施例一

参照附图1，下面用具体的步骤对本发明实施例的一种数据对象处理方法做更详细的介绍。

步骤11、把待去重的数据对象划分成一个或多个分区，计算各分区的采样压缩率，把具有共同压缩率特征且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率。其中，各分区可以是定长的，也可以是不定长的。在不定长的情况下，可以在一定范围内选择一个随机长度作为分区长度；也可以扫描数据对象并输出多组具有不同期望长度的候选分块边界，使用其中一组候选分块边界，把所述数据对象划分为一个或多个变长分区。

压缩率用于度量数据可以被压缩的程度，其计算方法为：压缩率＝压缩后数据量/原始数据量。一种估算压缩率的方法是：对每个分区，按采样比例S抽取一段样本数据，用数据压缩算法压缩样本数据，例如无损压缩算法LZ算法、RLE编码，计算压缩率，并把样本的压缩率作为被采样分区的压缩率。采样比例越高，样本的压缩率越接近被采样分区的真实压缩率。

对于可压缩的数据段，其压缩率一般小于1；对于不可压缩的数据段，由于增加了描述字段等元数据开销，其进行压缩编码后的长度有可能大于原始数据长度，从而可以出现压缩率大于1的情况。压缩率表项包含一系列的压缩率区间，不同的压缩率区间之间交集为空，且所有压缩率区间的并集构成完整的压缩率取值范围[0，∞)。

压缩率特征是指把压缩率作为聚合分区的参数，压缩率或者对压缩率进行运算获得的值符合预设条件的分区，就是符合压缩率特征的分区。具体而言，压缩率特征可以是压缩率区间，也就是压缩率的范围；也可以是相邻分区的压缩率的差值的阈值。参照表1示例，是以压缩率区间作为压缩率特征。数据对象划分为分区1-分区7共计7个分区。通过对各个分区采样并估算压缩率，获得各个分区的采样压缩率，例如分区1的采样压缩率是0.4，分区2的采样压缩率是0.42；每个采样压缩率属于一个压缩率区间，例如压缩率0.4属于压缩率区间[0，0.5)，压缩率0.61属于压缩率区间[0.5，0.8)，因为每个分区对应有一个采样压缩率，也可以认为每个分区属于一个压缩率区间；属于同一个压缩率区间的分区聚合为一个数据段，因此分区1、分区2可聚合为数据段1，分区3、分区4以及分区5可聚合为数据段2，分区6、分区7可聚合为数据段3。

表1

步骤12，根据每个数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块。其中，所述数据段的长度取值范围划分为至少一个所述长度区间，每个所述数据段的长度唯一属于一个所述长度区间，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间。

不同的压缩率区间不相交，不同的长度区间也不相交，他们的每种组合对应一种期望长度，每个数据段的采样压缩率唯一属于一个压缩率区间，每个数据段的长度唯一属于一个长度区间。数据段的采样压缩率可以通过对数据段进行采样压缩获得；也可以通过对组成数据段的各分区的采样压缩率取平均值获得，取平均值可以是算术平均值；也可以按照各分区的长度，计算各分区采样压缩率的加权平均值，具体方法是以组成所述数据段的各分区的采样压缩率作为标志值，各分区的长度作为权重，计算各分区采样压缩率的加权平均值。

在把数据段拆分成数据块时，需要找到数据块的边界，相邻边界之间就是一个数据块。

如果步骤11中分区划分方法是，计算多组具有不同期望长度的候选分块边界，使用其中一组候选分块边界，把所述数据对象划分为一个或多个变长分区，则本步骤可以按照选择的所述期望长度，从所述候选分块边界中，选择具有相同期望长度的分块边界把数据段拆分成数据块，也就是说从步骤11中扫描获得的多组候选边界中选择相应的边界即可，不用再次扫描数据段。如果步骤11中，分区划分是其他方法，例如定长分区，本步骤可以是选择一种期望长度，然后扫描数据段找到各个分块的边界，从而将数据段拆分成数据块，相较于计算多个具有不同期望长度的候选分块边界的方法，多了一个扫描数据段寻找数据块边界的步骤。

参照表2的示例，压缩率的取值范围被划分成[0，0.5)、[0.5，0.8)、[0.8，∞)三个压缩率区间，压缩率区间之间没有交集，每个数据段的采样压缩率都属于一个压缩率区间，也可以理解为每个数据段对应一个压缩率区间。此外，数据段的长度取值范围划分为至少一个长度区间，长度区间之间没有交集，因此每个数据段对应一个长度区间，长度区间和压缩率区间共同决定一个数据段的期望长度。例如数据段A属于的长度区间是长度[0MB，10MB)，且数据段A的采样压缩率在[0，0.5)内，而长度区间[0MB，10MB)、压缩率区间[0，0.5)共同确定的期望长度是32KB，那么数据段A的期望长度就是32KB；同样的道理，由数据段B的长度所属于的长度区间、以及数据段B的采样压缩率所属于的压缩率范围，可以得出数据段B的期望长度是256KB。获得了期望长度后，就可以把各数据段按照期望长度拆分成数据块。例如，把数据段A按照期望长度32KB拆成数据块，把数据段B按照期望长度256KB拆成数据块。其中，B是字节(Byte)的缩写，1KB＝1024Bytes，1MB＝1024KB。

由于期望长度是一个理论值，各个数据块的实际长度可能不一样，也就是说是不定长的，但数据段A拆分形成的数据块中，平均分块长度接近于期望长度32KB，这些不定长的数据块长度取值为32KB的概率最高，32KB也是一个峰值长度。本发明实施例中，每个期望长度对应一个峰值长度，因此本发明实施例是一种多峰值长度的数据分块与去重方法。

表2

本实施例中，期望长度可以用经验值或者通过分析统计获得。一种可选的期望长度的确定规则，如表2示例所示，对于相同的压缩率区间，则随着长度区间下限的增加，对应的期望长度也递增；另一方面，对于相同的长度区间，随着压缩率区间下限的增加，其在该映射表中对应的期望长度也递增。数据段的期望分块长度与数据段采样压缩率所属的压缩率区间下限值、数据段长度所属的长度区间下限正相关。一些情况下，大数据对象和难以压缩的数据对象的去重率对分块粒度不敏感，采用这种期望长度的分块方式，可以快速减少分块数量而不会导致去重率快速恶化。

按照各个数据块在数据段中的位置，每个数据段拆分形成的数据块具有前后顺序，这些具有前后顺序的数据块形成一个数据块序列，也可以称为分块子序列。本步骤12还可以包括把不同数据块拆分生成的分块子序列拼接起来，形成数据对象的分块序列，分块序列中各个分块的前后顺序，与分块数据在数据对象中的前后顺序相同。

步骤13，把相邻数据段中，前一数据段的末端数据块与后一数据段的首个数据块拼接成1个数据块，拼接形成的数据块可以称为拼接数据块。步骤13是可选步骤，例如，如果步骤11中数据段的边界来自于定长分区的边界，可以选用步骤13，拼接后可以避免固定长度分区的边界被沿用成为分块的边界，可以获得更好的去重效果。

此外，两个数据段之间过渡区域所产生的拼接数据块，其两侧相邻数据块分别对应不同的期望长度，可选的，可以采用两种期望长度的较小值把拼接数据块拆分为更细粒度的数据块，可以更好的发现两个数据段之间过渡区域的重复内容，在数据块总量增加不多的情况下，提高去重效果。在其他实施例中，也可以采用比两种期望长度的较小值更小的期望长度，把拼接数据块拆分为更细粒度的数据块。

当步骤12中包括拼接分块子序列的步骤时，步骤13可以在拼接分块子序列之前执行，也可以在拼接分块子序列之后执行。

步骤14，计算各数据块的指纹，通过指纹判断数据块是否已经在存储设备中存储，把存储设备中未存储的数据块，以及未存储的数据块对应的指纹、采样压缩率发送给存储设备。

指纹用于唯一标识数据块，数据块和数据块对应的指纹有一一对应的关系。一种指纹计算方法是计算数据块的哈希(Hash)值作为指纹。

步骤15，存储设备对收到的数据、数据块的指纹进行存储。在存储时，可以判断收到的数据块的采样压缩率是否符合压缩率阈值，把符合压缩率阈值的数据块压缩后存储，以节约存储空间；不符合压缩率阈值的数据不做压缩直接存储。例如压缩率阈值是小于等于0.7，则可以对采样压缩率小于等于0.7的数据块压缩后存储，采样压缩率大于0.7的数据不压缩直接存储。

需要说明的是，步骤11的分段方式不止一种。例如在另外一种实施方式中，可以把步骤11的分段策略修改为：把采样压缩率的差值小于指定阈值、并且相邻的连续分区聚合为同一个数据段。也就是说采样压缩率的差值小于指定阈值是压缩率的特征。仍以表1举例，假如以采样压缩率差值小于0.1作为阈值。那么0.42-0.4＜0.1，因此分区1与分区2划分到同一个数据段中；而0.53-0.42＞0.1，因此分区3不和分区2划分到同一个数据段中。依次类推，分区1与分区2划分到第一个数据段，分区3与分区4划分到第二个数据段，分区5、分区6、分区7划分到第三个数据段。

实施例二

如图2所示对实施例二进行详细描述，本实施例数据对象处理方法包括以下步骤。

21、加载分块策略映射表，参照表1、表2，分块策略映射表记录了哪些压缩率属于同一个压缩率特征；此外，分块策略映射表中还记录了数据段所属于的长度区间、数据段的压缩率所属于的压缩率区间，以及由二者共同确定的期望长度。期望长度用于把数据段拆分为数据块。本步骤也可以在后续执行，在需要使用分块策略映射表之前加载即可。

22、输入需要处理的数据对象给执行本方法的装置。也就是获取需要处理的数据对象，获取的来源可以是执行本方法的装置，也可以是与执行本方法装置连接的外部装置。

23、用固定长度对数据对象进行分区。在具体实现时，本步骤需要扫描数据对象，获得各个固定长度分区的边界，相邻两个边界之间的数据就是一个分区。

24、对各分区数据进行采样压缩，以采样压缩获得的压缩率作为整个分区数据的采样压缩率。

25、根据分块策略映射表，把具有相同压缩率特征的连续分区聚合为数据段。

26、根据分块策略映射表，把各数据段划分为具有特定期望长度的数据块。在具体实现时，本步骤需要扫描各数据段，找到各个数据块的边界，以边界拆分数据段，形成一系列的数据块。

本实施例，执行到数据26即完成了数据对象的处理，实现了把数据对象拆分成数据块的效果。后续步骤27、28、29是对数据对象处理方法的进一步拓展。

27、拼接各数据段产生的分块子序列。每个数据段拆分形成的数据块具有先后次序，其次序与数据块在数据段中的位置相同，这些具有先后次序的数据块也可以称为分块子序列。本步骤一种拼接方式是，对任意相邻的两个数据段，把前一数据段的末尾数据块和后一数据段的首个数据块拼接成一个数据块，从而消除数据段之间的边界，把多个子序列合并，形成整个数据对象的数据块序列；可选的，还可以对本步骤拼接成的数据块拆分成更小粒度的数据块，提高去重的效果。另外一种拼接方式是，各数据块保持不变，按照数据段在数据对象中的顺序，把各数据段的分块子序列进行排序，下一个数据段首数据块承接前一个数据段的末尾数据块，形成整个数据对象的数据块序列。

28、计算各分块的哈希值作为指纹。

29、输出各分块及分块的指纹，可选的还可以输出分块的采样压缩率。其中，分块的采样压缩率可利用其所属分段的采样压缩率计算获得，一种方式是直接使用分段的采样压缩率作为其所含各分块的采样压缩率。

当数据对象不止一个时，对上述步骤(22)-(29)进行循环，直至所有数据对象处理完成。

上述步骤的一种具体实现方法是：采用w-bytes滑动窗口扫描数据对象，每向前滑动一个字节则采用快速哈希算法重新计算窗口内数据的指纹f(w-bytes)，若当前数据段的期望长度为E，则以表达式Match(f(w-bytes)，E)＝D是否成立判断当前指纹是否符合分块边界筛选条件，其中整数D∈[0，E)为预定义的特征值。函数Match(·)用于将f(w-bytes)映射到区间[0，E)，由于哈希函数f(·)具有随机性，该筛选条件能够输出峰值长度为E的一系列分块。该流程在到达新数据段时，由于新数据段的期望长度E发生了改变，因此输出具有新的峰值长度的分块子序列。在对两个数据段的相邻区域进行分块时，数据块的前一边界由前一个数据段的期望长度确定，后一边界由后一个数据段的期望长度确定，因此这个数据块的前后边界分别位于两个数据段中，相当于自动完成了相邻段之间分块子序列的拼接，因此该流程不会引入段边界作为分块边界。

为了方便理解，实施例二另外提供流程图3，其步骤流程依次是：3a，输入需要执行数据对象处理方法的数据对象，这个数据对象在被执行数据对象处理前，可以暂存在缓存中；3b，对数据对象进行分区、采样并估算压缩率，L、M、H分别代表三种不同的压缩率区间；3c，将具有共同压缩率特征的连续分区聚合为数据段，3d，根据各数据段的压缩率和长度特征选择期望长度并计算分块边界，按照计算出的分块边界把各数据段拆分成数据块，每个数据段拆分成的数据块组成一个分块子序列；3e，拼接各数据段的分块子序列并计算分块指纹。

实施例三

实施例二把待去重的数据对象划分成多个定长的分区。而实施例三中，采用期望长度对待去重的数据对象进行预分块，具体而言是采用基于内容的分块方法扫描数据对象(文件/数据流)并生成多组具有不同期望长度的候选分块边界，其中每组候选分块边界对应数据对象的一种候选分块序列，后续分块序列也可以理解成分块方案。用其中一种预分块方案把数据对象划分为分区，用于进行采样压缩和确定数据段的划分方法，在后续的把数据段拆分成数据块的步骤中，可以根据期望长度，选择相应的候选分块边界用于拆分数据块。

因此，实施例二在把数据对象划分成分区、把数据段拆分成数据块时都需要扫描数据对象。而本实施例只需要扫描一次数据对象，节约了系统资源，提高了数据对象处理效率。此外，由于实施例三中分区边界与数据块边界都是基于候选分块边界，因此由分区聚合而产生的段边界不会对去重造成不良影响，不需要对数据块进行去除段边界的操作，也就是说不需要把相邻数据段中前一数据段的末尾数据块与后一数据段的首个数据块拼接成一个数据块。

期望长度越小则平均分块粒度越细，越有利于感知数据内容局部压缩率的变化，期望长度越大，则平均分块粒度越粗。

如图4所示，本实施例数据对象处理方法，具体可以包括以下步骤。

41、加载分块策略映射表，参照表1、表2，分块策略映射表记录了哪些压缩率属于同一个压缩率特征；此外，分块策略映射表中还记录了数据段所属于的长度区间、数据段的压缩率所属于的压缩率区间，共同确定的期望长度，这个期望长度用于把数据段拆分为数据块。本步骤也可以在后续执行，在需要使用分块策略映射表之前加载即可。

42、输入需要处理的数据对象给执行本方法的装置。也就是获取需要处理的数据对象，获取的来源可以是执行本方法的装置，也可以是与执行本方法装置连接的外部装置。

43、在一次扫描过程中，输出多组候选分块边界，每组候选分块边界与一个期望长度一一对应。这些期望长度包括了后续步骤中各个数据段对应的期望长度。

44、从步骤43的多组候选分块边界中，选择一组候选边界，并对由这组候选边界形成的候选分块序列进行采样压缩。本步骤也就是对数据对象进行分区，分区的期望长度是步骤43中多个期望长度中的一个，在按照这个期望值分区时，不需要再次扫描数据对象，直接按照这个期望长度对应的候选分块边界划分分区即可。然后对各分区数据进行采样压缩，以采样压缩获得的压缩率作为整个分区数据的采样压缩率。

45、根据分块策略映射表，把具有相同压缩率特征的连续分区聚合为数据段。

46、根据分块策略映射表，为各数据段选择相应期望长度对应的候选分块边界，数据块的边界决定了数据块的长度和位置，因此本步骤也就是把数据段拆分成数据块。如前所述，由于本步骤46的候选分块边界来自步骤43，因此在把数据段拆分成数据块时不需要重复扫描数据对象，节约了系统资源。

本实施例，执行到数据46即完成了数据对象的处理，实现了把数据对象拆分成数据块的效果。后续步骤47、48、49是对数据对象处理方法的进一步拓展。

47、拼接相邻数据段的分块子序列。按照数据段在数据对象中的顺序，把各数据段的子序列进行排序，形成数据对象的数据分块序列。数据分块也可以称为数据块。

48、计算各数据块的哈希值作为指纹。

49、输出各分块及分块的指纹，可选的还可以输出分块的采样压缩率。其中，分块的采样压缩率可利用其所属分段的采样压缩率计算获得，一种方式是直接使用分段的采样压缩率作为其所含各分块的采样压缩率。

在存储数据分块时，可以根据分块的采样压缩率判断是否要对数据块进行压缩后再存储。

当数据没有处理完，也就是说数据对象不止一个时，对余下的对象依次执行步骤42-49，直至所有数据对象处理完成。

上述步骤43的一种具体实现方法是：该流程将表2所示分块策略映射表中的所有期望长度E_i及对应的特征值D_i构造成参数列表，对滑动窗口输出的每个指纹f(w-bytes)，依次用不同的参数<E_i，D_i>判断是否符合匹配条件Match(f(w-bytes)，E_i)＝D_i，若是，则选择当前窗口位置为E_i对应的候选分块边界。其中，通过优化参数<E_i，D_i>可以提高指纹匹配效率。例如，定义Match(f(w-bytes)，E_i)＝f(w-bytes)mod E_i，并选择E₀＝2¹²B＝4KB，E₁＝2¹⁵B＝32KB，D₀＝D₁＝0，则当f(w-bytes)mod E₀≠D₀时，必然出现f(w-bytes)mod E₁≠D₁，即一个指纹如果不满足4KB期望长度对应的筛查条件，则不需要继续检查其是否符合32KB期望长度对应的筛查条件。

为了方便理解，实施例三另外提供流程图5。图5中各步骤流程依次是：5a，输入需要执行数据对象处理方法的数据对象，这个数据对象在被执行数据对象处理前，可以暂存在缓存中；5b，用不同的期望长度确定多组候选分块边界；5c，在5b确定出的多组候选分块边界中，选择其中一组候选分块序列划分数据对象，并对划分后得到的分块进行采样并估算压缩率；5d，将具有共同压缩率特征的连续候选分块聚合为数据段；5e，根据各数据段的压缩率和长度特征选择期望长度和相应分块边界，每个数据段按照相应的分块边界拆分成的数据块组成一个分块子序列；5f，拼接各数据段的分块子序列并计算分块指纹。

实施例四

参照图6，本实施例描述一种数据对象处理装置6，可以应用上述实施例一、实施例二、实施例三的方法。数据对象处理装置6包括：分区划分模块61、数据段生成模块62以及数据块生成模块63。

在对象处理装置6中，分区划分模块61，用于把数据对象划分为一个或多个分区；数据段生成模块62，用于计算每个分区的采样压缩率，把采样压缩率具有共同特征的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；数据块生成模块63，根据每个所述数据段的长度所属于的长度区间、每个数据段的压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。

具体而言，分区划分模块61，可以把所述数据对象划分为一个或多个定长分区；也可以用于计算多组具有不同期望长度的候选分块边界，使用其中一组候选分块边界，把所述数据对象划分为一个或多个变长分区。

数据段生成模块62，具体可以用于：计算每个分区的采样压缩率，把采样压缩率属于相同压缩率区间并且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率。

数据段生成模块62，具体还可以用于：计算每个分区的采样压缩率，把采样压缩率的差值小于指定阈值并且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率。

在上述数据对象处理装置6各种可能的实现方案中，数据块生成模块63具有的选择一种期望长度将数据段拆分成数据块的功能，具体可以是：按照选择的所述期望长度，从分区模块计算出的多组具有不同期望长度的候选分块边界中，选择具有相同期望长度的分块边界把数据段拆分成数据块。

数据块生成模块63还可以用于把相邻数据段中，前一数据段的末数据块与后一数据段的首数据块拼接成一个拼接数据块。进一步的，数据块生成模块63还可以用于：把所述拼接数据块拆分成多个数据块，拆分所使用的期望长度小于或等于所述前一数据段对应的期望长度，且拆分所使用的期望长度小于或等于所述后一数据段对应的期望长度。

此外，对象处理装置6中，还可以进一步包括数据块发送模块64。数据块发送模块64用于计算各所述数据块的指纹，通过指纹判断在存储设备中是否已经存储有各所述数据块，把所述存储设备中未存储的数据块，以及未存储的数据块对应的指纹、采样压缩率发送给所述存储设备，存储设备存储接收到的数据块指纹，并判断收到的数据块的采样压缩率是否符合压缩率阈值，把符合压缩率阈值的数据块压缩后存储。

对象处理装置6也可以看做由CPU、内存组成的设备。内存中存储有程序，CPU通过内存中的程序执行实施例一、实施例二或者实施例三种的方法。还可以包括接口，接口用于和存储设备连接。接口的功能例如可以把经过CPU处理后产生的数据块发送给存储设备。

通过以上的实施方式的描述，可以清楚地了解到本发明可借助软件加必需的通用硬件的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品存储在可读取的存储介质中，如计算机的软盘，硬盘或光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述的方法。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了详细说明，但本发明的保护范围并不局限于此，任何人员在本发明揭露的技术范围内，所做的任何修改、等同替换、改进等均应包含在本发明的保护范围之内。因此，本发明的保护范围应以所述权利要求的保护范围为准。

Claims (20)

1.一种数据对象处理方法，其特征在于，该方法包括：

把数据对象划分为一个或多个分区；

计算每个分区的采样压缩率，把采样压缩率具有共同特征的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；

根据每个所述数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。

2.根据权利要求1所述的方法，其特征在于，所述把数据对象划分为一个或多个分区，具体是：

把所述数据对象划分为一个或多个定长分区。

3.根据权利要求1所述的方法，其特征在于，所述方法之后，进一步包括：

把相邻数据段中，前一数据段的末数据块与后一数据段的首数据块拼接成一个拼接数据块。

4.根据权利要求3所述的方法，其特征在于，所述方法进一步包括：

把所述拼接数据块拆分成多个数据块，拆分所使用的期望长度小于或等于所述前一数据段对应的期望长度，且拆分所使用的期望长度小于或等于所述后一数据段对应的期望长度。

5.根据权利要求1所述的方法，其特征在于，所述把数据对象划分为一个或多个分区，具体是：

计算多组具有不同期望长度的候选分块边界，使用其中一组候选分块边界，把所述数据对象划分为一个或多个变长分区。

6.根据权利要求1或权利要求5所述的方法，其特征在于，所述选择一种期望长度将数据段拆分成数据块，具体是：

按照选择的所述期望长度，从多组候选分块边界中，选择具有相同期望长度的分块边界把数据段拆分成数据块。

7.根据权利要求1所述的方法，其特征在于，所述把采样压缩率具有共同特征的连续分区聚合为一个数据段，具体是：

把采样压缩率属于相同压缩率区间并且相邻的连续分区聚合为一个数据段。

8.根据权利要求1所述的方法，其特征在于，所述把采样压缩率具有共同特征的连续分区聚合为一个数据段，具体是：

把采样压缩率的差值小于指定阈值并且相邻的连续分区聚合为一个数据段。

9.根据权利要求1或3所述的方法，其特征在于，所述方法之后，进一步包括：

计算各所述数据块的指纹，通过指纹判断在存储设备中是否已经存储有各所述数据块，把所述存储设备中未存储的数据块，以及未存储的数据块对应的指纹、采样压缩率发送给所述存储设备；

所述存储设备存储接收到的数据块指纹，并判断收到的数据块的采样压缩率是否符合压缩率阈值，把符合压缩率阈值的数据块压缩后存储。

10.根据权利要求9所述的方法，其特征在于，

把所述数据块所来自的分段的采样压缩率，作为所述数据块的采样压缩率。

11.根据权利要求1所述的方法，其特征在于，所述数据段的采样压缩率具体为：

计算组成所述数据段的各分区的采样压缩率的算术平均值获得；或者

以组成所述数据段的各分区的采样压缩率作为标志值，各分区的长度作为权重，计算各分区采样压缩率的加权平均值。

12.一种数据对象处理装置，其特征在于，该装置包括：

分区划分模块，用于把数据对象划分为一个或多个分区；

数据段生成模块，用于计算每个分区的采样压缩率，把采样压缩率具有共同特征的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率；

数据块生成模块，根据每个所述数据段的长度所属于的长度区间、每个数据段的采样压缩率所属于的压缩率区间，选择一种期望长度将数据段拆分成数据块，其中，每个所述数据段的采样压缩率唯一属于一个所述压缩率区间，每个所述数据段的长度唯一属于一个所述长度区间。

13.根据权利要求12所述的装置，其特征在于，所述分区划分模块，具体用于：

把所述数据对象划分为一个或多个定长分区。

14.根据权利要求12所述的装置，其特征在于，数据块生成模块还用于：

把相邻数据段中，前一数据段的末数据块与后一数据段的首数据块拼接成一个拼接数据块。

15.根据权利要求14所述的装置，其特征在于，数据块生成模块还用于：

把所述拼接数据块拆分成多个数据块，拆分所使用的期望长度小于或等于所述前一数据段对应的期望长度，且拆分所使用的期望长度小于或等于所述后一数据段对应的期望长度。

16.根据权利要求12所述的装置，其特征在于，所述分区划分模块，具体还用于：

计算多组具有不同期望长度的候选分块边界，使用其中一组候选分块边界，把所述数据对象划分为一个或多个变长分区。

17.根据权利要求12或16所述的装置，其特征在于，所述选择一种期望长度将数据段拆分成数据块，具体是：

按照选择的所述期望长度，从多组候选分块边界中，选择具有相同期望长度的分块边界把数据段拆分成数据块。

18.根据权利要求12所述的装置，其特征在于，所述数据段生成模块，具体用于：

计算每个分区的采样压缩率，把采样压缩率属于相同压缩率区间并且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率。

19.根据权利要求12所述的装置，其特征在于，所述数据段生成模块，具体用于：

计算每个分区的采样压缩率，把采样压缩率的差值小于指定阈值并且相邻的连续分区聚合为一个数据段，获取各所述数据段的采样压缩率。

20.根据权利要求12所述的装置，其特征在于，所述装置，进一步包括：

数据块发送模块，用于计算各所述数据块的指纹，通过指纹判断在存储设备中是否已经存储有各所述数据块，把所述存储设备中未存储的数据块，以及未存储的数据块对应的指纹、采样压缩率发送给所述存储设备；

所述存储设备存储接收到的数据块指纹，并判断收到的数据块的采样压缩率是否符合压缩率阈值，把符合压缩率阈值的数据块压缩后存储。