一种等级化动态可变的共享重复数据存储和读取机制

摘要

本发明为云备份系统提出一种等级化动态可变的共享重复数据存储和读取机制，适用于云备份系统的等级化和公平化的服务质量需求。该方法与重复数据删除技术有机的契合，针对不同等级的租户，提供不同的服务质量策略，提高了系统的重删率并达到最佳的服务效果。该发明保障了租户在云备份系统环境中享有公平且具有等级化的服务质量。

说明书

技术领域

本发明属于计算机信息存储技术领域，针对多租户重复数据删除的云备份系统的服务质量需求，提出了一种等级化动态可变的共享重复数据存储和读取机制，为租户提供公平的且具有等级保障的服务质量。

背景技术

在云备份系统中，不同租户会根据各自的业务需求，向云备份提供商购买相应的备份资源，租户需要云备份系统提供公平的且具有等级保障的服务质量。而随着重复数据删除技术的应用，共享重复数据加剧了其服务质量维系的难度，仅仅依靠传统单一的，已经无法满足租户的等级化服务的需求。

针对云备份系统存在的以上问题，本发明提出了一种等级化动态可变的共享重复数据存储和读取机制，以保障租户公平且具有等级化的服务质量。与已有方法不同的是，该方法是一种基于重复数据删除的等级化服务质量控制方法，其资源分配和吞吐量监测采用基于数据块的细粒度控制，可以获得比其他方法更加公平的等级化服务质量，并且能提高系统的重删率，吞吐率以及数据恢复速度。

发明内容

本发明提出了一种等级化动态可变的共享重复数据存储和读取机制。该发明充分考虑每个数据块在备份和恢复各个处理阶段的资源分配和吞吐量情况，在系统性能稳定的前提下，从租户等级化、资源公平分配和共享重复数据处理三个方面实现云备份系统的等级化服务质量。

本发明的核心思想之一是资源公平分配。使用资源公平分配方法可以保障租户在数据备份和数据恢复各个处理阶段获得公平服务。资源分配方法是根据租户的服务等级，为租户分配公平的内存空间。步骤为：(1)先向云备份系统申请内存空间；(2)对内存空间量化，用申请到的内存空间容量除以1个数据块对应的元数据大小，得到云备份系统总的内存空间数目；(3)根据租户等级对应的权重，以及各等级租户的总人数，使用公式1为每位租户分配内存空间。

其中Memory_L表示L等级的租户分配的内存空间大小，Memory_total是系统申请的内存空间总量，N表示当前系统的等级个数，P_n、A_n分别表示目前系统第n个等级对应的内存空间权重和租户总人数，表示所有租户的权重之和，P_L代表L等级的租户对应的内存空间权重，是L等级租户所占内存空间总量的比值，表示L等级的租户从总的内存空间中获得的内存空间大小。

本发明的核心思想之二是吞吐量监测，吞吐量监测方法的目的是动态调整租户内存空间和吞吐量阈值，保障租户的等级化服务质量。步骤为：(1)周期性的对数据备份和数据恢复中每位租户吞吐量实时监控；(2)将监测得到的租户吞吐量进行求和，并根据租户等级对应的权重，以及系统中各个等级的租户人数，使用公式2计算各个等级的平均吞吐量。

其中Throughput_L,a代表L等级的租户的平均吞吐量大小，Throughput_total是系统的总吞吐量，N表示当前系统的等级个数，P_n、A_n分别表示目前系统第>表示所有租户的权重之和，P_L分别是L等级对应的吞吐量权重。是L等级租户的吞吐量大小占总吞吐量大小的比值，表示L等级的租户的平均吞吐量大小。

(3)用第一个周期监测的每位租户吞吐量大小，初始化租户吞吐量阈值。每个监测周期结束后，如果租户的实时吞吐量不等于对应等级的平均吞吐量，使用公式3动态调整其内存空间大小和吞吐量阈值，公式3如下所示。

其中Throughput_L,a表示L等级的平均吞吐量大小，Throughput_i是租户i的当前的实时吞吐量大小，ΔMemory、ΔThroughput是租户的当前吞吐量不等于对应等级的平均吞吐量时，内存空间和吞吐量阈值的增加量，Throughput_L,a->i表示租户i损失的吞吐量大小，Memory_i代表租户当前的内存空间大小，是租户i被补偿的内存空间大小。

根据公式3计算得到的内存空间的增量ΔMemory和吞吐量阈值的增量ΔThroughput，将租户的内存空间大小和吞吐量阈值分别增加ΔMemory、ΔThroughput。

本发明的核心思想之三是共享重复数据处理。共享重复数据处理方法包括共享重复数据存储机制和共享数据读取机制。具体为：

(a)共享重复数据存储机制：在单位时间周期内，高优先级租户与低优先级租户备份的新数据块出现重复时，根据吞吐量监控方法得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，表明由高优先级租户完成该数据块备份对其性能没有影响，该数据块的备份任务交给高优先级租户完成，低优先级租户的数据块标记为重复并指向该数据块；否则由低优先级租户完成对该数据块的备份，高优先级租户的数据块标记重复并指向该数据块。

(b)共享数据读取机制：在单位时间周期内，高优先级租户和低优先级租户恢复的数据块出现重复且不在缓存中时，根据吞吐量监控模型得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，表明由高优先级租户完成该数据块缓存对其性能没有影响，该数据块的缓存任务交给高优先级租户完成并恢复，高优先级租户的内存空间增加1个数据块对应的元数据大小，低优先级租户的内存空间减少1个数据块对应的元数据大小；否则由低租户缓存该数据块，并完成该数据块的恢复。

本发明提出一种等级化动态可变的共享重复数据存储和读取机制，主要包括数据备份与数据恢复两个部分。

数据备份的具体步骤为：

(1)客户端对租户需要备份的数据流进行数据分块，然后对分块后的数据块使用哈希算法计算得到对应的指纹，把数据指纹以及租户等级信息发送至服务器。

(2)服务器接收到客户端发送的数据信息后，进行如下步骤：

(2.1)根据租户的服务等级，为租户的备份业务建立相应优先级；资源公平分配模块，按服务等级对应的权重，使用公式(1)为租户分配内存空间和吞吐量阈值。

(2.2)对数据备份中每位租户的吞吐量，周期性的实时监测。将监测得到的租户吞吐量进行求和，并根据租户等级对应的权重，以及系统中各个等级的租户人数，使用公式(2)计算出不同等级的平均吞吐量。每个监测周期结束后，如果租户吞吐量大小不等于对应等级的平均吞吐量大小，使用公式(3)对步骤(2.1)的内存空间和吞吐量阈值进行调整。

(2.3)根据步骤(2.1)中确定业务优先级后，按照租户备份业务优先级，从高优先级到低优先级依次遍历步骤(1)发送来的指纹序列，在指纹索引表中查询，若不存在指纹索引表中，则标记对应的数据块为新数据块；反之则说明对应的数据块已经被存储过，标记该数据块为重复数据块，并记录该数据块的存储地址。

(2.4)对新数据块进行存储，具体步骤为：

(a)如果新数据块是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，采用共享重复数据存储策略，并根据新数据块的存储地址更新指纹索引表。共享重复数据存储策略具体为：

根据步骤(2.2)中得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，由高优先级租户完成对新数据块存储，否则由低优先级租户完成对新数据块的存储。

(b)如果新数据块不是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，由数据块所属租户完成数据块存储，并根据新数据块的存储地址更新指纹索引表。

数据恢复的具体步骤为：

(1)客户端读取租户需要恢复数据的地址，将需要恢复数据的地址和租户等级信息发送至服务器。

(2)服务器接收到客户端发送的恢复数据地址、租户等级信息，进行如下步骤：

(2.1)根据租户的服务等级，为租户的恢复业务建立相应优先级。

(2.2)通过恢复数据的地址，在磁盘上查找保存该数据的元数据信息。

(2.3)按服务等级对应的权重，使用公式(1)为租户分配内存空间和吞吐量阈值。

(2.4)对数据恢复中每位租户的吞吐量，周期性的实时监测。将监测得到的租户吞吐量进行求和，并根据租户等级对应的权重，以及系统中各个等级的租户人数，计算出不同等级的平均吞吐量。每个监测周期结束后，如果租户吞吐量大小不等于对应等级的平均吞吐量大小，使用公式(3)对步骤(2.1)的内存空间和吞吐量阈值进行调整。

(2.5)根据步骤(2.1)中确定业务优先级后，按照租户恢复业务优先级，从高优先级到低优先级扫描步骤(2.2)中所恢复数据的元数据信息，并在服务器缓存中查找，如果元数据信息对应的数据块存在缓存中，直接恢复；如果元数据信息对应的数据块不在缓存中，执行如下步骤：

(a)如果数据块是高优先级租户与低优先级租户在单位时间周期内共同恢复的数据，采用共享数据读取策略处理。该策略具体为：

根据步骤(2.4)中得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值，判断高优先级租户完成对数据块缓存的性能影响。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，由高优先级租户完成对数据块的缓存，高优先级租户的内存空间增加1个数据块对应的元数据大小，低优先级租户的内存空间减少1个数据块对应的元数据大小；否则由低优先级租户完成对数据块的缓存并恢复；

(b)如果数据块不是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，则由数据块所属租户完成对数据块的缓存并恢复。

本发明的特点：本发明一种基于重复数据删除的等级化服务质量控制方法，资源分配和吞吐量监控采用基于数据块的细粒度的控制，精确到数据备份和数据恢复的每个阶段的数据块，解决了重复数据删除带来的服务质量不公平问题，进而使得重复数据删除技术更好与云备份系统契合。

附图说明

图1为模块结构示意图；

图2为重复数据删除机制和共享数据读取机制处理流程图

具体实施方式

图1为本发明的模块结构示意图。本发明涉及到客户端100和服务器200。客户端包含指纹处理模块110，主要对备份数据集进行数据块分块，以及采用哈希函数计算每个数据块的指纹。服务器包含租户等级化管理模块210、资源公平分配模块220、吞吐量监测模块230、共享重复数据处理模块240。租户等级化管理模块210根据每位租户的服务等级，建立相应的优先级，按照租户数据备份或数据恢复的业务优先级，从高优先级到低优先级依次调度。资源公平分配模块220和吞吐量监测模块230用来保障租户的等级化服务质量，其中资源公平分配模块220使用公式(1)，为租户分配公平的内存空间；吞吐量监测模230块对租户数据处理的吞吐量进行实时监测，使用公式(2)和(3)动态调整租户的内存空间和吞吐量阈值。当高优先级租户和低优先级租户，在单位时间周期内出现共同存储或缓存的数据块时，共享重复数据处理模块240查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值，如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，由高优先级租户完成数据块存储或缓存，否则由低优先级租户完成。

图2为本发明的重复数据删除机制和共享数据读取机制处理流程图，包括数据备份和数据恢复两个部分。

数据备份的具体步骤为：

(1)客户端100的指纹处理模块110对租户需要备份的数据流进行数据分块，然后对分块后的数据块使用哈希算法计算得到对应的指纹，把数据指纹以及租户等级信息发送至服务器。

(2)服务器200接收到客户端发送的数据信息后，进行如下步骤：

(2.1)租户等级管理模块210根据租户的服务等级，为租户的备份业务建立相应优先级；资源公平分配模块220，按服务等级对应的权重，使用公式(1) 为租户分配内存空间和吞吐量阈值。

(2.2)吞吐量监测模块230对数据备份中每位租户的吞吐量，周期性的实时监测。将监测得到的租户吞吐量进行求和，并根据租户等级对应的权重，以及系统中各个等级的租户人数，计算出不同等级的平均吞吐量。每个监测周期结束后，如果租户吞吐量大小不等于对应等级的平均吞吐量大小，使用公式(3) 对步骤(2.1)的内存空间和吞吐量阈值进行调整。

(2.3)根据步骤(2.1)中确定业务优先级后，租户等级管理模块210按照租户备份业务优先级，从高优先级到低优先级依次遍历步骤(1)发送来的指纹序列，在指纹索引表中查询，若不存在指纹索引表中，则标记对应的数据块为新数据块；反之则说明对应的数据块已经被存储过，标记该数据块为重复数据块，并记录该数据块的存储地址。

(2.4)对新数据块进行存储，具体步骤为：

(a)如果新数据块是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，共享重复数据处理模块240采用共享重复数据存储策略，并根据新数据块的存储地址更新指纹索引表。共享重复数据存储策略具体为：根据步骤(2.2)中得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，由高优先级租户完成对新数据块存储，否则由低优先级租户完成对新数据块的存储。

(b)如果新数据块不是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，由数据块所属租户完成数据块存储，并根据新数据块的存储地址更新指纹索引表。

数据恢复的具体步骤为：

(1)客户端100读取租户需要恢复数据的地址，将需要恢复数据的地址和租户等级信息发送至服务器。

(2)服务器200接收到客户端发送的恢复数据地址、租户等级信息，进行如下步骤：

(2.1)租户等级管理模块210根据租户的服务等级，为租户的恢复业务建立相应优先级。

(2.2)通过恢复数据的地址，在磁盘上查找保存该数据的元数据信息。

(2.3)资源公平分配模块220，按服务等级对应的权重，使用公式(1) 为租户分配内存空间和吞吐量阈值。

(2.4)吞吐量监测模块230对数据恢复中每位租户的吞吐量，周期性的实时监测。将监测得到的租户吞吐量进行求和，并根据租户等级对应的权重，以及系统中各个等级的租户人数，计算出不同等级的平均吞吐量。每个监测周期结束后，如果租户吞吐量大小不等于对应等级的平均吞吐量大小，使用公式(3) 对步骤(2.1)的内存空间和吞吐量阈值进行调整。(2.5)根据步骤(2.1)中确定业务优先级后，租户等级管理模块210按照租户恢复业务优先级，从高优先级到低优先级扫描步骤(2.2)中所恢复数据的元数据信息，并在服务器缓存中查找，如果元数据信息对应数据块存在缓存中，直接恢复；如果元数据信息对应的数据块不在缓存中，执行如下步骤：

(a)如果数据块是高优先级租户与低优先级租户在单位时间周期内共同恢复的数据，共享重复数据处理模块240采用共享数据读取策略处理。该策略具体为：根据步骤(2.4)中得到的租户吞吐量和各个等级的平均吞吐量，查看高优先级租户和低优先级租户的吞吐量比值是否大于等于对应等级的平均吞吐率比值，判断高优先级租户完成对数据块缓存的性能影响。如果高优先级租户和低优先级租户的吞吐量比值大于等于对应等级的平均吞吐率比值，由高优先级租户完成对数据块的缓存，高优先级租户的内存空间增加1个数据块对应的元数据大小，低优先级租户的内存空间减少1个数据块对应的元数据大小；否则由低优先级租户完成对数据块的缓存并恢复；

(b)如果数据块不是高优先级租户与低优先级租户在单位时间周期内共同备份的数据，则由数据块所属租户完成对数据块的缓存并恢复。