De-duplication of files for continuous data protection with remote storage

• US 9,223,793 B1
• Filed: 06/03/2010
• Issued: 12/29/2015
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: AmZetta Technologies, LLC (American Megatrends International, LLC)
• Original Assignee: American Megatrends Incorporated
• Inventors: Mahalingam, Anandh, Ganapathy, Narayanaswami, Ramasamy, Senthilkumar
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Mueller, Kurt
• Application Number:
  US12/793,178
• Time in Patent Office: 2,035 Days
• Field of Search: 707/695
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1756 based on delta files

Abstract

Technologies are described herein for performing data de-duplication of a version of a data file for backup to a remote storage location. A CDP module executing on a computer creates a collection of files corresponding to the version of the data file by de-duplicating the version against a previous version master file stored locally on the computer. The previous version master file contains one or more unique data blocks of a specific block size from a previous version of the data file. Once the de-duplication against the locally maintained previous version master file is complete, the CDP module stores the collection of files corresponding to the version of the data file to the remote storage location. The remote storage location also contains a master file corresponding to the data file that contains all of the unique data blocks in the previous version master file.

Claims

1. A computer-implemented method of backing-up a version of a data file to a remote storage, the method comprising executing instructions on a computer to perform the operations of:

de-duplicating the version of the data file against a previous version master file stored on a local storage device, wherein the previous version master file comprises a single instance of each of one or more unique data blocks of a specific block size from a previous version of the data file, and wherein de-duplicating the version of the data file against the previous version master file comprises determining whether at least one block of data from the version of the data file matches at least one of the one or more unique data blocks of the specific size from the previous version of the data file by;

maintaining a lightweight checksum for each of the one or more unique data blocks in the previous version master file, and

matching a block of data read from the version of the data file to one of the one or more unique data blocks in the previous version master file by calculating a lightweight checksum value for the read block of data and comparing the calculated lightweight checksum value with the lightweight checksums maintained for the one or more unique data blocks in the previous version master file, wherein calculating the lightweight checksum for a subsequently read block of data from the version of the data file comprises subtracting one or more bytes from the lightweight checksum for a previously read block of data and adding one or more bytes from the subsequently read block of data to the lightweight checksum for the previously read block of data;

creating a supplemental file corresponding to the version of the data file and comprising one or more chunks of data from the version of the data file not matching one of the one or more unique data blocks in the previous version master file;

creating a version map file corresponding to the version of the data file and comprising one or more references to unique data blocks in the previous version master file and one or more references to chunks of data in the supplemental file, wherein each of the one or more references to unique data blocks in the previous version master file comprise an index to a unique data block and each of the one or more the references to chunks of data in the supplemental file comprise a length of a chunk of data; and

storing the supplemental file and the version map file corresponding to the version of the data file to the remote storage, wherein the remote storage contains a master file corresponding to the data file and comprising each of the unique data blocks referenced in the version map file.

2. The computer-implemented method of claim 1, further comprising executing instructions on the computer to perform the operations of:

appending a new unique data block to the master file corresponding to the data file, wherein the new unique data block comprises data of the specific block size not matching one of the one or more unique data blocks in the previous version master file.

3. The computer-implemented method of claim 1, further comprising executing instructions on the computer to perform the operations of:

creating a new version master file corresponding to the version of the data file and replacing the previous version master file stored on the local storage device with the new version master file.

4. The computer-implemented method of claim 1, wherein a plurality of version map files and supplemental files are stored in the remote storage along with the master file corresponding to the data file, each of the plurality of version map files and supplemental files corresponding to individual versions of the data file.

5. The computer-implemented method of claim 4, wherein a plurality of version map files corresponding to individual versions of the data file contain a reference to the same unique data block in the master file.

6. The computer-implemented method of claim 1, wherein after a specified number of versions of the data file have been backed-up to the remote storage, a subsequent version of the data file is backed-up to the remote storage without de-duplicating the subsequent version of the data file against the previous version master file stored on the local storage device.

7. The computer-implemented method of claim 1, wherein the remote storage comprises a cloud-based storage service.

8. A non-transitory computer-readable storage medium having computer-executable instructions stored thereon for de-duplicating a current version of a data file that, when executed by a computer, cause the computer to:

read a first block of data of a particular block size from a current offset in the current version of the data file;

determine if the first block of data matches one of a plurality of unique data blocks contained in a previous version master file corresponding to a previous version of the data file, wherein the previous version master file is stored on a local storage device of the computer, wherein the previous version master file comprises a single instance of each of the plurality of unique data blocks from the previous version of the data file, wherein determining if the first block of data matches one of the plurality of unique data blocks contained in the previous version master file comprises calculating a lightweight checksum value for the first block of data and comparing the calculated lightweight checksum value with lightweight checksums maintained for the plurality of unique data blocks in the previous version master file, and wherein calculating the lightweight checksum for a subsequently read block of data from the current version of the data file comprises subtracting one or more bytes from the lightweight checksum for a previously read block of data and adding one or more bytes from the subsequently read block of data to the lightweight checksum for the previously read block of data;

upon determining that the first block of data matches one of the plurality of unique data blocks contained in the previous version master file, appending a reference to the matching unique data block to a version map file corresponding to the current version of the data file;

upon determining that the first block of data does not match one of the plurality of unique data blocks contained in the previous version master file, creating a supplemental file corresponding to the current version of the data file and comprising a chunk of data from the current version of the data file not matching one of the plurality of unique data blocks contained in the previous version master file, appending a reference to the chunk to the version map file and increasing the current offset by a slide size; and

reading a next block of data of the particular block size from the current offset in the current version of the data file, wherein the reference to the matching unique data block comprises an index to the matching unique data block and the reference to the chunk comprises a length of the chunk.

9. The non-transitory computer-readable storage medium of claim 8, wherein the operations are repeated until all the data in the current version of the data file have been processed, and wherein the version map file corresponding to the current version of the data file is then copied to a remote storage containing a master file corresponding to the data file and comprising each of the unique data blocks referenced in the version map file.

10. The non-transitory computer-readable storage medium of claim 9, wherein a plurality of version map files are stored in the remote storage along with the master file corresponding to the data file, each of the plurality of version map files corresponding to individual versions of the data file.

11. The non-transitory computer-readable storage medium of claim 10, wherein a plurality of version map files corresponding to individual versions of the data file contain a reference to the same unique data block in the master file.

12. A system backing-up a version of a data file to a remote storage, the system comprising a continuous data protection (“

CDP”

) module executing on a user computer and configured to;

create a collection of files corresponding to the version of the data file by de-duplicating the version of the data file against a previous version master file stored on a local storage device of the user computer, wherein the previous version master file comprises a single instance of each of one or more unique data blocks of a specific block size from a previous version of the data file, and wherein de-duplicating the version of the data file against the previous version master file comprises determining whether at least one block of data from the version of the data file matches at least one of the one or more unique data blocks of the specific size from the previous version of the data file by;

maintaining a lightweight checksum for each of the one or more unique data blocks in the previous version master file, and

matching a block of data read from the version of the data file to one of the one or more unique data blocks in the previous version master file by calculating a lightweight checksum value for the read block of data and comparing the calculated lightweight checksum value with the lightweight checksums maintained for the one or more unique data blocks in the previous version master file, wherein calculating the lightweight checksum for a subsequently read block of data from the version of the data file comprises subtracting one or more bytes from the lightweight checksum for a previously read block of data and adding one or more bytes from the subsequently read block of data to the lightweight checksum for the previously read block of data; and

store the collection of files corresponding to the version of the data file to the remote storage, wherein the remote storage contains a master file corresponding to the data file and comprising the one or more unique data blocks in the previous version master file, wherein the collection of file comprises;

a supplemental file corresponding to the version of the data file and comprising one or more chunks of data from the version of the data file not matching one of the one or more unique data blocks in the previous version master file; and

a version map file corresponding to the version of the data file and comprising one or more references to unique data blocks in the previous version master file and one or more references to chunks of data in the supplemental file, wherein each of the one or more references to unique data blocks in the previous version master file comprise an index to a unique data block and each of the one or more the references to chunks of data in the supplemental file comprise a length of a chunk of data.

13. The system of claim 12, wherein the CDP module is further configured to:

append a new unique data block to the master file corresponding to the data file, wherein the new unique data block comprises data of the specific block size not matching one of the one or more unique data blocks in the previous version master file.

14. The system of claim 12, wherein the CDP module is further configured to:

create a new version master file corresponding to the version of the data file and replacing the previous version master file stored on the local storage device with the new version master file.

15. The system of claim 12, wherein after a specified number of versions of the data file have been backed-up to the remote storage, a subsequent version of the data file is backed-up to the remote storage without de-duplicating the subsequent version of the data file against the previous version master file stored on the local storage device.