Data compression and storage techniques

• US 8,832,045 B2
• Filed: 05/02/2012
• Issued: 09/09/2014
• Est. Priority Date: 04/07/2006
• Status: Active Grant

• Current Assignee: Data Storage Group, Inc.
• Original Assignee: Data Storage Group, Inc.
• Inventors: Dodd, Brian, Moore, Michael
• Primary Examiner(s): HASAN, SYED HAROON
• Application Number:
  US13/462,664
• Publication Number:
  US 20120310890A1
• Time in Patent Office: 860 Days
• US Class Current: 707/693
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 16/113 Details of archiving lifecycle management in storage systems G06F3/0649; backup systems G06F11/1446

Abstract

Provided are systems and methods for use in data archiving. In one arrangement, compression techniques are provided wherein an earlier version of a data set (e.g., file folder, etc) is utilized as a dictionary of a compression engine to compress a subsequent version of the data set. This compression identifies changes between data sets and allows for storing these differences without duplicating many common portions of the data sets. For a given version of a data set, new information is stored along with metadata used to reconstruct the version from each individual segment saved at different points in time. In this regard, the earlier data set and one or more references to stored segments of a subsequent data set may be utilized to reconstruct the subsequent data set.

Claims

1. A method for use in computerized data storage, wherein a computerized system is operative to utilize computer readable media to back-up a data set, comprising:

generating hash signatures including an identifier hash associated with identifying data and a content hash associated with content of individual portions of an initial data set;

transferring the initial data set to a storage location via a network interface;

at a time subsequent to transferring the initial data set, performing a back-up of a subsequent data set associated with the initial data set, wherein performing the back-up comprises;

generating hash signatures including an identifier hash associated with identifying data and a content hash associated with content of individual portions of the subsequent data;

comparing the identifier hashes of corresponding portions of the initial data set and the subsequent data set and, upon failing to match identifier hashes, comparing content hashes of said corresponding portions to determine if a corresponding content hash exists for the initial data set and to identify changed portions of the subsequent data set;

obtaining corresponding portions of the initial dataset that correspond to the changed portions of the subsequent data set;

preloading a dictionary-based compression engine with one of the corresponding portions of the initial data set, wherein the one corresponding portion of the initial data set is loaded in the dictionary-based compression engine and defines an individual dictionary block;

compressing a corresponding one of the changed portions of the subsequent data set using the dictionary-based compression engine as loaded with the corresponding portion of the initial data set as a dictionary, wherein a compressed data portion is generated; and

storing the compressed data portion to the storage location via the network interface to define a back-up version of the subsequent data set.

2. The method of claim 1, further comprising:

repeating the preloading and compressing steps for each of the changed portions of the individual data portions of the subsequent data set and corresponding individual portions of the initial data set, to generate a set of compressed data portions defining changes between the initial data set and the subsequent data set.

3. The method of claim 1, wherein preloading the dictionary-based compression engine further comprises:

buffering content of the one corresponding portion of the initial data set into a first series of data segments;

buffering the content of the changed portion of the subsequent data set into a second series of like-sized data segments.

4. The method of claim 3, wherein preloading and compressing comprises:

preloading the dictionary-based compression engine with one data segment of the first series of data segments; and

compressing a corresponding one of the second series of data segments using the dictionary-based compression engine as loaded with the one data segment of the first series of data segments.

5. The method of claim 1, wherein the compressed data portion references the individual dictionary block utilized to generate the compressed data portion.

6. The method of claim 1, wherein obtaining the corresponding portions of the initial dataset comprises receiving the corresponding portions via the network interface from the storage location.

7. The method of claim 1, wherein the hash signature of the initial data set is stored at an origination location of the subsequent data set.

8. The method of claim 1, further comprising:

upon identifying a corresponding content hash for the initial data set, obtaining the portion of the initial data set from the storage location.

9. The method of claim 1, wherein the portions of the initial data set and the subsequent data set are defined by files in the data sets.

10. The method of claim 1, wherein the portions of the initial data set and the subsequent data set are defined by predefined byte lengths.

11. The method of claim 10, wherein the predetermined byte lengths are between 1 Megabyte and 1 Gigabyte.

12. The method of claim 1, wherein changed portions of the subsequent data set are stored at an origination location of the subsequent data set, wherein the changed portions are available for use as dictionary blocks in a further second back-up of a second subsequent data set.

13. The method of claim 1, further comprising, transferring the hash signatures associated with the initial data set from the storage location to an origination location of the subsequent data set, wherein the comparing step is performed at the origination location.

14. A method for use in computerized data storage, wherein a computerized system is operative to utilize computer readable media to back-up a data set, comprising:

delineating an initial data set into a first set of data portions having a predetermined size;

generating a hash signature including an identifier hash and a content hash associated with each data portion of the initial data set;

storing the data portions of the initial data set;

at a time subsequent to storing the initial data set, performing a back-up of a subsequent data set associated with the initial data set, wherein performing the back-up comprises;

delineating the subsequent data set into a second set of data portions having the same predetermined size as the data portions of the first data set;

generating a hash signature including an identifier hash and a content hash associated with each data portion of the subsequent data set;

comparing identifier hashes of the initial data set and the subsequent data set and, upon failing to match identifier hashes, comparing content hashes to determine if a corresponding content hash exists for the initial data set and to identify data portions of the subsequent data set that are different from corresponding data portions of the first data set;

preloading a dictionary-based compression engine with one of the corresponding data portions of the initial data set;

compressing a corresponding one of the changed data portions of the subsequent data set using the dictionary-based compression engine as loaded with the one corresponding portion of the initial data set as a dictionary, wherein a compressed data portion is generated; and

storing the compressed data portion to at least partially define a back-up version of the subsequent data set.

15. The method of claim 14, further comprising

repeating the preloading and compressing steps for each of the changed data portions and corresponding data portions, respectively, to generate a series of compressed data portions;

and

storing the serried of compressed data portions to at least partially define the back-up version of the subsequent data set.

16. The method of claim 14, wherein storing the data portions of the initial data set further comprises;

transferring the data portions across a data network to a data storage location.

17. The method of claim 16, further comprising;

retrieving the corresponding data portions from the data storage location.

18. The method of claim 17, wherein the each compressed data portion references the corresponding data portion as an individual dictionary block.

19. The method of claim 14, wherein the steps of comparing, preloading and compressing are performed on multiple processors for individual data portions.

20. The method of claim 14, wherein delineating comprises:

delineating the data sets into virtual pages having a predetermined byte size.