Iterative integer programming with load balance for cyclic workloads

Patent metadata

Field	Value
Publication number	US-11403183-B2
Application number	US-202016862561-A
Country	US
Kind code	B2
Filing date	Apr 29, 2020
Priority date	Apr 29, 2020
Publication date	Aug 2, 2022
Grant date	Aug 2, 2022

Abstract

A backup orchestrator for providing backup services to entities includes storage for storing recovery point objectives for the entities and a backup manager. The backup manager selects an optimization periodicity based a number of backups to be generated to meet a portion of the recovery point objectives; makes a determination that at least one of the portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the optimization periodicity; in response to the determination: load balances the number of backups across multiple optimization periods, based on the optimization periodicity, of a balanced backup schedule; selects a backup generation time for each of the to be generated backups in each of the optimization periods of the balanced backup schedule; and generates the number of backups using the balanced backup schedule.

First claim

What is claimed is:

1. A backup orchestrator for providing backup services to entities, comprising:
storage for storing recovery point objectives for the entities;
a processor; and
a backup manager implemented using computing code executed by the processor, the backup manager is programmed to:
select an optimization periodicity based on a number of backups to be generated to meet a portion of the recovery point objectives;
make a determination that at least one of the portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the optimization periodicity;
in response to the determination:
load balance the number of backups across multiple optimization periods, based on the optimization periodicity, of a balanced backup schedule, wherein load balancing the number of backups across multiple optimization periods comprises:
constraining the number of backups to placement across the multiple optimization periods based on, in part, a limit on a total duration for backup generation during each of the multiple optimization periods to obtain a backup periodization of the number of backups; and
adding backups of the number of backups to the respective periods of the balanced backup schedule based on the backup periodization;

select a backup generation time for each of the to be generated backups in each of the optimization periods of the balanced backup schedule; and
generate the number of backups using the balanced backup schedule.

2. The backup orchestrator of claim 1 , wherein the backup manager is further programmed to:
select a second optimization periodicity based on a second number of backups to be generated to meet a second portion of the recovery point objectives;
make a determination that none of the second portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the second optimization periodicity;
in response to the determination:
add each backup to each optimization period of an unbalanced backup schedule;
select a backup generation time for each of the second number of backups in each of the optimization periods of the unbalanced backup schedule; and
generate the second number of backups using the unbalanced backup schedule.

3. The backup orchestrator of claim 1 , wherein the placements of the number of backups are further constrained based, in part, on a second limit on which backup storages, used to store the number of backups, can store the number of backups.

4. The backup orchestrator of claim 3 , wherein the second limit is adapted to aggregate a portion of the number of backups that are likely to include data that is duplicative of existing data stored in a backup storage of the backup storages.

5. The backup orchestrator of claim 1 , wherein the placements of the number of backups are further constrained based, in part, on times required to generate the number of backups.

6. The backup orchestrator of claim 1 , wherein the placements of the number of backups are further constrained based, in part, on maximum allowable unbacked up periods of time for the number of backups.

7. A method for providing backup services to entities, comprising:
selecting an optimization periodicity based on a number of backups to be generated to meet a portion of recovery point objectives associated with the number of backups;
making a determination that at least one of the portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the optimization periodicity;
in response to the determination:
load balancing the number of backups across multiple optimization periods of a balanced backup schedule demarcated by the optimization periodicity, wherein the load balancing comprises:
constraining the number of backups to placement across the multiple optimization periods based on, in part, a limit on a total duration for backup generation during each of the multiple optimization periods to obtain a backup periodization of the number of backups; and
adding backups of the number of backups to the respective periods of the balanced backup schedule based on the backup periodization;

selecting a backup generation time for each of the to be generated backups in each of the optimization periods of the balanced backup schedule; and
generating the number of backups using the balanced backup schedule.

8. The method of claim 7 , further comprising:
selecting a second optimization periodicity based on a second number of backups to be generated to meet a second portion of the recovery point objectives;
making a determination that none of the second portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the second optimization periodicity;
in response to the determination:
adding each backup to each optimization period of an unbalanced backup schedule;
selecting a backup generation time for each of the second number of backups in each of the optimization periods of the unbalanced backup schedule; and
generating the second number of backups using the unbalanced backup schedule.

9. The method of claim 7 , wherein the placements of the number of backups are further constrained based, in part, on a second limit on which backup storages, used to store the number of backups, can store the number of backups.

10. The method of claim 9 , wherein the second limit is adapted to aggregate a portion of the number of backups that are likely to include data that is duplicative of existing data stored in a backup storage of the backup storages.

11. The method of claim 7 , wherein the placements of the number of backups are further constrained based, in part, on times required to generate the number of backups.

12. The method of claim 7 , wherein the placements of the number of backups are further constrained based, in part, on maximum allowable unbacked up periods of time for the number of backups.

13. A non-transitory computer readable medium comprising computer readable program code, which when executed by a computer processor enables the computer processor to perform a method for providing backup services to entities, the method comprising:
selecting an optimization periodicity based on a number of backups to be generated to meet a portion of recovery point objectives associated with the number of backups;
making a determination that at least one of the portion of the recovery point objectives has a maximum allowable unbacked up period of time that is greater than the optimization periodicity;
in response to the determination:
load balancing the number of backups across multiple optimization periods of a balanced backup schedule demarcated by the optimization periodicity, wherein the load balancing comprises:
constraining the number of backups to placement across the multiple optimization periods based on, in part, a limit on a total duration for backup generation during each of the multiple optimization periods to obtain a backup periodization of the number of backups; and
adding backups of the number of backups to the respective periods of the balanced backup schedule based on the backup periodization;

selecting a backup generation time for each of the to be generated backups in each of the optimization periods of the balanced backup schedule; and
generating the number of backups using the balanced backup schedule.

14. The non-transitory computer readable medium of claim 13 , wherein the method further comprises:
selecting a second optimization periodicity based on a second number of backups to be genera

Assignees

• Emc Ip Holding Co Llc

Inventors

• Barbalho Hugo De Oliveira
• Calmon Tiago Salviano
• Vera Sousa Eduardo

Classifications

• G06F9/505

  considering the load · CPC title

• G06F11/1461 Primary

  Backup scheduling policy · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F11/1466

  to make the backup process non-disruptive · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title