Reducing data transmitted during backup

• US 10,185,504 B1
• Filed: 11/25/2015
• Issued: 01/22/2019
• Est. Priority Date: 11/26/2014
• Status: Active Grant

• Current Assignee: MidCap Financial Trust
• Original Assignee: Acronis International GmbH (Acronis AG)
• Inventors: Pogosyan, Vitaliy, Yusupov, Ramil, Tsvetkov, Anton, Protasov, Stanislav, Beloussov, Serguei M.
• Primary Examiner(s): Bertram, Ryan
• Assistant Examiner(s): Kwong, Edmund H
• Application Number:
  US14/952,232
• Time in Patent Office: 1,154 Days
• Field of Search: 711162
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for reducing an amount of data transmitted during a backup process is described. The method may include receiving input data to insert into a rating hash table during the backup process. The method may further include selecting, based on a hash function, a bucket of the rating hash table in which the input data will be inserted, the bucket including a plurality of blocks. The method may also include, in response to determining that the input data has already been inserted in one of the plurality of blocks, increasing a rating corresponding to the one of the plurality of blocks by a popularity rating increment. The method may additionally include, in response to determining that the input data has not already been inserted in one of the plurality of blocks, determining a first block with a smallest rating from the plurality of blocks.

Claims

1. A method for reducing an amount of data transmitted during a backup process, the method comprising:

receiving input data to insert into a rating hash table during the backup process;

selecting, based on a hash function, a bucket of the rating hash table in which the input data will be inserted, the bucket including a plurality of blocks;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

increasing a rating corresponding to the one of the plurality of blocks by a popularity rating increment;

in response to determining that the input data has not already been inserted in one of the plurality of blocks;

determining a first block with a smallest rating from the plurality of blocks;

inserting the input data in the first block with the smallest rating;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

decreasing a rating corresponding to the other blocks of the plurality of blocks by an aging rating increment; and

determining data that does not need to be transmitted from a client to a server using the backup process based on hash values having higher assigned ratings from popularity increment increases, wherein hash values from the client are rated and data associated with such hash values is selectively backed up to the server.

2. The method of claim 1, further comprising:

setting a rating corresponding to the first block to an initial rating value.

3. The method of claim 1, further comprising:

for each block of the plurality of blocks besides the first block, decreasing a corresponding rating by an aging rating increment.

4. The method of claim 1, wherein the input data was sent or requested by a cloud computing client being backed up in a virtualization platform.

5. The method of claim 1, wherein the input data was sent or requested by a cloud computing client being backed up in a virtualization platform, the rating hash table resides with the cloud computing client, and a reduced amount of data is transmitted during a compare operation of the backup process based on the rating hash table.

6. A computer program product residing on a computer readable storage medium having a plurality of instructions stored thereon, which, when executed by a processor, causes the processor to perform operations for reducing an amount of data transmitted during a backup process, the operations comprising:

receiving input data to insert into a rating hash table during the backup process;

selecting, based on a hash function, a bucket of the rating hash table in which the input data will be inserted, the bucket including a plurality of blocks;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

increasing a rating corresponding to the one of the plurality of blocks by a popularity rating increment;

in response to determining that the input data has not already been inserted in one of the plurality of blocks;

determining a first block with a smallest rating from the plurality of blocks;

inserting the input data in the first block;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

decreasing a rating corresponding to the other blocks of the plurality of blocks by an aging rating increment; and

determining data that does not need to be transmitted from a client to a server using the backup process based on hash values having higher assigned ratings from popularity increment increases, wherein hash values from the client are rated and data associated with such hash values is selectively backed up to the server.

7. The computer program product of claim 6, wherein the operations further comprise:

setting a rating corresponding to the first block to an initial rating value.

8. The computer program product of claim 6, wherein the operations further comprise:

for each block of the plurality of blocks besides the first block, decreasing a corresponding rating by an aging rating increment.

9. The computer program product of claim 6, wherein the operations further comprise:

in response to determining that the input data has already been inserted in one of the plurality of blocks;

decreasing a rating corresponding to the other blocks of the plurality of blocks by an aging rating increment.

10. The computer program product of claim 6, wherein the input data replaces data already in the first block upon being inserted.

11. The computer program product of claim 6, wherein the input data was sent or requested by a cloud computing client being backed up in a virtualization platform, the rating hash table resides with the cloud computing client, and a reduced amount of data is transmitted during a compare operation of the backup process based on the rating hash table.

12. A computing system for reducing an amount of data transmitted during a backup process, the computing system comprising one or more processors, wherein the one or more processors are configured to:

receive input data to insert into a rating hash table during the backup process;

select, based on a hash function, a bucket of the rating hash table in which the input data will be inserted, the bucket including a plurality of blocks;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

increase a rating corresponding to the one of the plurality of blocks by a popularity rating increment;

in response to determining that the input data has not already been inserted in one of the plurality of blocks;

determine a first block with a smallest rating from the plurality of blocks;

insert the input data in the first block;

in response to determining that the input data has already been inserted in one of the plurality of blocks;

decrease a rating corresponding to the other blocks of the plurality of blocks by an aging rating increment; and

determine data that does not need to be transmitted from a client to a server using the backup process based on hash values having higher assigned ratings from popularity increment increases, wherein hash values from the client are rated and data associated with such hash values is selectively backed up to the server.

13. The computing system of claim 12, wherein the one or more processors are further configured to:

set a rating corresponding to the first block to an initial rating value.

14. The computing system of claim 12, wherein the one or more processors are further configured to:

for each block of the plurality of blocks besides the first block, decrease a corresponding rating by an aging rating increment.

15. The computing system of claim 12, wherein the one or more processors are further configured to:

in response to determining that the input data has already been inserted in one of the plurality of blocks;

decrease a rating corresponding to the other blocks of the plurality of blocks by an aging rating increment.

16. The computing system of claim 12, wherein the input data replaces data already in the first block upon being inserted.

17. The computing system of claim 12, wherein the input data was sent or requested by a cloud computing client being backed up in a virtualization platform, the rating hash table resides with the cloud computing client, and a reduced amount of data is transmitted during a compare operation of the backup process based on the rating hash table.

18. A system for reducing an amount of data transmitted during a backup process, the system comprising:

a rating hash table residing in a cloud computing client;

a plurality of buckets residing in the rating hash table, each bucket including a plurality of blocks, wherein each block includes data and a rating corresponding to the data; and

a processor configured to run an insertion operation on the rating hash table,

the processor configured to increase rating of a first set of hash values of data at a client based on popularity rating of such first set of hash values, and

the processor configured to decrease rating of a second set of hash values of data at the client based on aging rating of such second set of hash values,

wherein the data in each block is rated based on how often the data is sent or requested at the client and a reduced amount of data is transmitted to a backup server during a compare operation of the backup process based on the rating hash table,

wherein the processor is further configured to determine a first block with a smallest rating from the plurality of blocks of a bucket; and

insert the input data in a first block with the smallest rating, wherein hash values from the client are rated to generate first and second hash values, wherein the data associated with such first set of hash values is selectively backed up to the backup server.