Opportunistic Asynchronous De-Duplication in Block Level Backups

• US 20110213754A1
• Filed: 02/26/2010
• Published: 09/01/2011
• Est. Priority Date: 02/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Deb, Bodhi, Bindal, Anuj, Deshpande, Gaurav, Suriyanarayanan, Guhan
• Granted Patent: US 8,458,131 B2
• Time in Patent Office: Days
• US Class Current: 707/641
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process

Abstract

A block based backup system may store backed up data from multiple clients by maintaining backup databases for each client, where each backup database may include blocks of data. The backup system may perform a de-duplication process by examining the databases to identify common blocks and moving the common blocks to a common database. The common blocks may be removed from the client backup databases and a pointer substituted for the data, thus compacting the client backup databases. The de-duplication operation may be performed at an opportunistic time, such as after the clients have completed any data transfer to the backup system.

Claims

1. A method being performed on a computer processor, said method comprising:

receiving a first set of backup data from a first client, said first set of backup data being block based backup data;

storing said first set of backup data in a first client backup database;

receiving a second set of backup data from a second client, said second set of backup data being block based backup data;

storing said second set of backup data in a second client backup database;

comparing said first backup database and said second backup database to identify a first common block; and

storing said first common block in a common backup database and removing said first common block from both of said first client backup database and said second client backup database.

2. The method of claim 1 further comprising:

receiving a request from said first client, said request being for a first set of identifiers for backup data stored in said first client backup database; and

transmitting said first set of identifiers to said first client.

3. The method of claim 2, said request further being for a second set of identifiers, said second set of identifiers being for backup data stored in said common backup database.

4. The method of claim 3, said method further comprising:

receiving a third set of backup data from said first client, said third set of backup data comprising a subset of said first set of identifiers but no blocks of data associated with said subset and at least one new block of data.

5. The method of claim 4, said third set of backup data representing an incremental backup from said first client.

6. The method of claim 3 further comprising:

determining that said first set of backup data is not to be retained;

removing a reference to said first set of backup data from said first client backup database;

identifying a first unused block within said first client backup database, said first unused block not being referenced by any backup within said first client backup database; and

removing said first unused block from said first client backup database.

7. The method of claim 6 further comprising:

determining that said first common block is no longer referenced from said first client backup database and that said second client backup database does reference said first common block; and

moving said first common block from said common backup database to said second client backup database.

8. The method of claim 1, said first set of backup data comprising identifiers for blocks of data.

9. The method of claim 8, said identifiers being hash values calculated from said blocks of data.

10. The method of claim 1 further comprising:

analyzing said first set of backup data to create identifiers for each block of data within said first set of backup data; and

storing said identifiers in said first client backup database.

11. The method of claim 1 further comprising:

receiving a first request for said first set of backup data;

identifying a plurality of blocks of data representing said first set of backup data, a first subset of said blocks of data being located in said common backup database and a second subset of said blocks of data being located in said first backup database; and

transmitting said plurality of blocks in response to said first request.

12. The method of claim 11 further comprising:

determining an order for said plurality of blocks from said first database and said transmitting said plurality of blocks being performed according to said order.

13. A backup server device comprising:

a processor;

a plurality of client databases, each of said client databases comprising a repository for blocks of data and a backup database comprising backup definitions and references to said blocks of data from said backup definitions;

a communications engine that;

establishes a first communication session with a first client device;

determines that a first client database is associated with said first client device;

receives a first plurality of said blocks of data;

stores said first plurality of said blocks of data in said first client database as a first backup;

establishes a second communication session with a second client device;

determines that a second client database is associated with said second client device;

receives a second plurality of said blocks of data; and

stores said second plurality of said blocks of data in said second client database;

an optimization engine that;

analyzes said first client database and said second client database to identify a first common block;

adds said first common block to a common client database;

adds pointers to said first common block from said first client database and said second client database; and

removes said first common block from said first client database and from said second client database.

14. The backup server device of claim 13, said optimization engine configured to operate when said communications engine is not receiving said blocks of data.

15. The backup server device of claim 13 further comprising:

a hash generator that analyzes blocks of data to calculate a hash value for each of said blocks of data, said hash value being used within said client databases as an identifier for each of said blocks of data.

16. The backup server device of claim 13 further comprising:

a restore engine that;

receives a request for said first backup;

identifies said first plurality of blocks of data; and

transmits said first plurality of blocks of data in response to said request, said first plurality of blocks comprising blocks of data from said first client database and said common client database.

17. A backup client device comprising:

a storage device comprising a first file system to backup;

a backup engine that;

establishes a communication session with a backup server;

generates a first set of block identifiers representing each block of data in said first file system;

determines that an incremental backup is to be performed; and

transmits said first set of block identifiers and a subset of said blocks of data in said file system to said backup server.

18. The backup client device of claim 17, said incremental backup being determined by a method comprising:

requesting a second set of block identifiers from said backup server;

receiving said second set of block identifiers from said backup server; and

comparing said first set of block identifiers to said second set of block identifiers to identify a third set of block identifiers, said third set of block identifiers corresponding to said subset of said block of data.

19. The backup client device of claim 18, said second set of block identifiers comprising block identifiers from a common client backup database and from a first client backup database.

20. The backup client device of claim 17, said incremental backup being determined by comparing said first file system to a snapshot of said file system, said snapshot representing a previous state of said first file system during a previous backup operation.