Method and system for data reduction

• US 20060064416A1
• Filed: 09/17/2004
• Published: 03/23/2006
• Est. Priority Date: 09/17/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong
• Granted Patent: US 7,979,404 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14

Abstract

A “forward” delta data management technique uses a “sparse” index associated with a delta file to achieve both delta management efficiency and to eliminate read latency while accessing history data. The invention may be implemented advantageously in a data management system that provides real-time data services to data sources associated with a set of application host servers. To facilitate a given data service, a host driver embedded in an application server connects an application and its data to a cluster. The host driver captures real-time data transactions, preferably in the form of an event journal that is provided to the data management system. In particular, the driver functions to translate traditional file/database/block I/O into a continuous, application-aware, output data stream. In an illustrative embodiment, a given application aware data stream is processed through a multi-stage data reduction process to produce a compact data representation from which an “any point-in-time” reconstruction of the original data can be made.

Claims

1. A method of data management, comprising:

(a) generating a first data string by comparing contents of a first modified data file against contents of an original data file and characterizing an output of such comparison using a given syntax that defines given data insertions, deletions and replacements;

(b) generating a second data string by comparing the first data string against the contents of the original data file and characterizing an output of such comparison using the given syntax; and

(c) generating a byte range index, the byte range index for use in reconstructing the contents of the first modified data file by referencing the contents of the original data file and the second data string.

2. The method as described in claim 1 further including the step of storing the original data file, the byte range index, and the second data string.

3. The method as described claim 2 wherein the original data file, the byte range index and the second data string are stored in a location remote from a location at which the first data string is generated.

4. The method as described in claim 1 wherein the contents of the modified data file are compared against the original data file using a given signature algorithm.

5. The method as described in claim 4 wherein the given signature algorithm performs a checksum-based delta extraction to generate the output.

6. The method as described in claim 1 further including the steps of:

(d) generating a first data string by comparing the contents of a second modified data file against the contents of the first modified data file and characterizing an output of such comparison using the given syntax;

(e) generating a second data string by comparing the first data string generated in step (d) against the contents of the first modified data file and characterizing an output of such comparison using the given syntax; and

(f) generating a byte range index, the byte range index for use in reconstructing the contents of the second modified data file by referencing the contents of the original data file, the second data string generated in step (b) and the second data string generated in step (e).

7. The method as described in claim 6 wherein the byte range index for use in reconstructing the contents of the second modified data file is created at least in part from the byte range index for use in reconstructing the contents of the first modified data file.

8. A data store in a distributed data management system, comprising:

a first file storing baseline data;

a second file storing data generated at least in part by applying a given differencing function to a given version of the baseline data; and

a set of one or more metadata objects, each metadata object being associated with a given version of the baseline data and including an index that references the first file and, optionally, the second file.

9. The data store as described in claim 8 wherein the given version of the baseline data can be reconstructed from the index irrespective of whether all the contents of the given version are stored in the data store.

10. The data store as described in claim 8 wherein the metadata objects for at least two given versions of the baseline data are laid out in the data store in a reverse order.

11. The data store as described in claim 8 wherein the data comprises a data stream, the data stream having a sequence of one or more delta strings that are generated by applying the given differencing function.

12. The data store as described in claim 8 wherein the set of one or more metadata objects also includes a metadata block that includes fixed metadata associated with the baseline data.

13. The data store as described in claim 8 wherein the set of one or more metadata objects includes a metadata block that is associated with a given version of the baseline data for a given temporary time period.

14. The data store as described in claim 8 wherein the data store is a disk located at a location in the distributed data management system remote from a location at which the baseline data and updates to the baseline data are generated.

15. A method of managing baseline data in a distributed management system, comprising:

(a) storing a given data object, the given data object comprising;

(i) a first file storing baseline data;

(ii) a second file storing data generated at least in part by applying a given differencing function to a given version of the baseline data; and

(iii) a set of one or more metadata objects, each metadata object being associated with a given version of the baseline data and including an index that references the first file and, optionally, the second file; and

(b) in response to a given request, using the index associated with the given version to reconstruct the given version.

16. The method as described in claim 15 wherein the set of one or more metadata objects for at least two given versions of the baseline data are laid out in the given data object in a given order.

17. The method as described in claim 15 wherein the data comprises a data stream that includes a sequence of one or more delta strings that are generated by applying the given differencing function.

18. The method as described in claim 15 wherein updates to the baseline data that create a given version of the baseline data occur at a first location remote from a location at which the given data object is stored.

19. The method as described in claim 15 wherein the given request is a file read.

20. A method of data management, comprising:

(a) generating a data string by comparing contents of a first modified data file against contents of an original data file and characterizing an output of such comparison using a given syntax that defines given data insertions, deletions and replacements; and

(b) generating a byte range index, the byte range index for use in reconstructing the contents of the first modified data file by referencing the contents of the original data file and the data string.

21. The method as described in claim 20 wherein step (a) is carried out at a location at which the first modified data file is generated.

22. The method as described in claim 20 wherein step (a) is carried out at a location remote from a location at which the first modified data file is generated.