System and method for scheduling data storage replication over a network

• US 8,898,108 B2
• Filed: 01/14/2009
• Issued: 11/25/2014
• Est. Priority Date: 01/14/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Berinde, Radu, Amdur, Matthew B., Karamanolis, Christos
• Primary Examiner(s): Beausoliel, Jr., Robert
• Assistant Examiner(s): Arjomandi, Noosha
• Application Number:
  US12/353,394
• Publication Number:
  US 20100185583A1
• Time in Patent Office: 2,141 Days
• Field of Search: 707/610
• US Class Current: 707/610
• CPC Class Codes: G06F 11/1461 Backup scheduling policy
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis

Abstract

The replication of a group of data sets is coordinated into a single schedule based on the recovery point objective (RPO) of each data set. The resulting generated schedule satisfies each data set'"'"'s RPO requirements and minimizes bandwidth use. If necessary bandwidth exceeds available bandwidth, the resulting generated schedule attempts to best satisfy each data set'"'"'s RPO requirements given the available bandwidth.

Claims

1. A method for replicating a group of data sets, the method comprising:

generating a plurality of schedules from which one schedule is to be selected for replication, wherein each schedule contains a list of replication times for each data set in the group and each data set has a recovery point objective (RPO) requirement and a utilization estimation of computational resources for said data set'"'"'s replication;

calculating a fitness value for each of the schedules, wherein the fitness value is a function of first and second values, the first value being a computed combination of an interval of time for each data set that the RPO requirement of the data set is not satisfied, and the second value being a computed combination of the estimated utilization of computational resources at points in time during a timeframe for replicating the group of data sets;

selecting from the plurality of schedules, a schedule with a best fitness value among the fitness values of the schedules determined according to said calculating; and

replicating the group in accordance with the selected schedule.

2. The method of claim 1,

wherein the first value is a norm of a multi-component vector, each vector component corresponding to a data set in the group and having a value equal to an interval of time when the RPO requirement is not satisfied by the data set;

wherein the second value is a norm of a multi-component vector, each vector component corresponding to a point in time during a timeframe for the replication of the group and having a value equal to the utilization of computation resources in an interval ending at the point in time; and

wherein said utilization estimation of computation resources is a utilization estimation of a network bandwidth.

3. The method of claim 1, wherein the fitness value is further a function of a scaling parameter that weighs a relative importance between the first value and the second value.

4. The method of claim 3, further comprising the steps of:

performing the generating, calculating and selecting steps for a plurality of scaling parameters; and

identifying a best schedule by selecting a schedule generated using a smallest scaling factor from those selected schedules that do not exceed a predetermined bandwidth requirement, wherein the replicating step utilizes the identified best schedule to replicate the group.

5. The method of claim 4, wherein the plurality of scaling parameters is generated by running an exponential binary search across a set of possible scaling parameters.

6. The method of claim 1, wherein the generating step involves performing random perturbations on a current set of schedules.

7. The method of claim 6, wherein the random perturbations are selected from a group consisting of mutation operations and crossover operations.

8. The method of claim 1, wherein the generating step continues until fitness values corresponding to generated schedules do not increase by more than a predetermined percentage value.

9. The method of claim 1, wherein said fitness value is further a function of a weighting factor assigned to each data set in said schedule.

10. The method of claim 1, wherein the plurality of schedules from which one is to be selected as the schedule for replication are generated prior to said calculating, said selecting, and said replicating.

11. A computer system for replicating a group of data sets, the computer system comprising a processor programmed to:

generate a plurality of schedules from which one schedule is to be selected for replication, wherein each schedule contains a list of replication times for each data set in the group and each data set has a recovery point objective (RPO) requirement and a utilization estimation of computational resources said data set'"'"'s replication;

calculate a fitness value for each of the schedules, wherein the fitness value is a function of first and second values, the first value being a computed combination of an interval of time for each data set that the RPO requirement of the data set is not satisfied, and the second value being a computed combination of the estimated utilization of computational resources at points in time during a timeframe for replicating the group of data sets; and

select from the plurality of schedules, a schedule with a best fitness value among the calculated fitness values of the schedules.

12. The computer system of claim 11, further comprising a data store for replicating the data sets in accordance with the selected schedule.

13. The computer system of claim 11, wherein each data set includes at least one virtual machine image.

14. The computer system of claim 13, wherein the processor is further programmed to communicate with a plurality of computer systems, wherein each of the computer systems hosts a virtual machine platform and hosts at least one of the virtual machine images from at least one of the data sets.

15. The computer system of claim 11, wherein the processor is further programmed to communicate with a data store for replicating the data sets in accordance with the schedule.

16. The computer system of claim 11,

wherein the first value is a norm of a multi-component vector, each vector component corresponding to a data set in the group and having a value equal to an interval of time when the RPO requirement is not satisfied by the data set;

wherein the second value is a norm of a multi-component vector, each vector component corresponding to a point in time during a timeframe for the replication of the group and having a value equal to the utilization of computation resources in an interval ending at the point in time; and

wherein said utilization estimation of computation resources is a utilization estimation of a network bandwidth.

17. A non-transitory computer readable storage medium having stored therein a computer program for scheduling a group of data sets for replication, wherein a computer system executing the computer program carries out the steps of:

generating a plurality of schedules from which one schedule is to be selected for replication, wherein each schedule contains a list of replication times for each data set in the group and each data set has a recovery point objective (RPO) requirement and a utilization estimation of computational resources for said data set'"'"'s replication;

calculating a fitness value for each of the schedules, wherein the fitness value is a function of first and second values, the first value being a computed combination of an interval of time for each data set that the RPO requirement of the data set is not satisfied, and the second value being a computed combination of the estimated utilization of computational resources at points in time during a timeframe for replicating the group of data sets; and

selecting from the plurality of schedules, a schedule with a best fitness value among the fitness values of the schedules determined according to said calculating.

18. The computer readable storage medium of claim 17, wherein the computer system executing the computer program further carries out the step of communicating with a data store to replicate the data sets in accordance to the selected schedule.

19. The computer readable storage medium of claim 17, wherein the fitness value is further a function of a scaling parameter that weighs a relative importance between the first value and the second value.

20. The computer readable storage medium of claim 17, wherein the generating step involves performing random perturbations on a current set of schedules.