Extracting data changes and storing data history to allow for instantaneous access to and reconstruction of any point-in-time data

• US 7,979,404 B2
• Filed: 09/17/2004
• Issued: 07/12/2011
• Est. Priority Date: 09/17/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong
• Primary Examiner(s): HICKS, MICHAEL J
• Application Number:
  US10/943,541
• Publication Number:
  US 20060064416A1
• Time in Patent Office: 2,489 Days
• Field of Search: None
• US Class Current: 707/694
• 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 for capturing and storing a data history of a file to enable instantaneous access to and reconstruction of any version of the file, comprising:

for a first version of the file at a first location;

storing a full copy of the file at a second location;

generating a first byte range index at the second location;

wherein the first byte range index references the entire contents of the full copy of the file;

storing the first byte range index at the second location; and

labeling the contents of the file referenced by the first byte range index as the first version of the file;

for a second version of the file at the first location;

comparing the second version of the file to the first version of the file to generate one or more delta strings associated with the second version of the file;

storing the one or more delta strings associated with the second version of the file at the second location;

generating a second byte range index at the second location that refers to bytes in the full copy of the file and to bytes in the one or more delta strings associated with the second version of the file;

wherein the second byte range index references the entire contents of the second version of the file;

storing the second byte range index at the second location;

wherein storing the second byte range index does not overwrite the first byte range index;

labeling the contents referenced by the second byte range index as the second version of the file; and

using the second byte range index to enable instantaneous access to and reconstruction of the second version of the file without having to apply to the full copy of the file the one or more delta strings associated with the second version of the file.

2. The method as described in claim 1 further including:

for an nth version of the file at the first location;

comparing the nth version of the file to an (n−

1)th version of the file to generate one or more delta strings associated with the nth version of the file;

storing the one or more delta strings associated with the nth version of the file at the second location;

generating a nth byte range index at the second location that refers to bytes in the full copy of the file, to bytes in the one or more delta strings associated with any of the second to (n−

1)th versions of the file, and to bytes in the one or more delta strings associated with the nth version of the file;

wherein the nth byte range index references the entire contents of the nth version of the file;

storing the nth byte range index at the second location;

wherein storing the nth byte range index does not overwrite the first to (n−

1)th byte range indexes;

labeling the contents referenced by the nth byte range index as an nth version of the file.

3. The method as described in claim 2 further including:

using the nth byte range index to enable instantaneous access to and reconstruction of the nth version of the file without having to apply to the full copy of the file the one or more delta strings associated with any of the second to nth versions of the file.

4. The method as described in claim 1 wherein the comparing step utilizes a signature-based algorithm that performs checksum-based delta extraction to generate the one or more delta strings.

5. The method as described in claim 1 wherein the comparing step includes a first stage, and a second stage, wherein the first stage generates a first, coarse data reduction, and the second stage generates a second, more fine-grained data reduction.

6. The method as described in claim 5 wherein the first stage occurs at the first location, and the second stage occurs at the second location remote from the first location.

7. The method as described in claim 5 wherein, as compared to the second location, the first location utilizes less processing capability to perform the comparing step.

8. The method as described in claim 5 wherein, during the first stage, a digital signature of a block of an nth version of the file is compared to a digital signature of a corresponding block of an (n−

1)th version of the file to generate a delta string.

9. The method as described in claim 8 wherein, during the second stage, a digital signature of the block of nth version is compared to a digital signature of a corresponding block of the (n−

1)th version of the file to generate another delta string, where the block that is processed during the second stage is smaller than the block that is processed in the first stage.

10. The method as described in claim 1 wherein each byte range index comprises a set of one or more entries, each entry comprising a start byte-end byte sequence and a reference value that represents contents of the file within the start byte-end byte sequence.

11. The method as described in claim 10 wherein the reference refers to a data range of the full copy or any delta string of any version of the file.

12. The method as described in claim 10 wherein the reference refers to a content file associated with the file, an offset in the content file, and a length or end byte of the content file.

13. The method as described in claim 10 wherein the reference refers to a physical storage location.

14. The method as described in claim 1 wherein a given version of the file represents an application checkpoint, a user file save, or a file close.