Granted Patent B2

US 7,979,404 · App. 10/943,541 · Granted Jul 12, 2011

Abstract

Claims (38)

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.

Assignments (28)