Method and system for data reduction
View Patent ↗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. 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. 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.
1. A method for capturing and storing a data history of a file to enable reconstruction of versions of the file, comprising:
storing a copy of a first version of a file at a remote location;
comparing with one or more computer processors, a second version of the file to the first version of the file, or the copy of 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 remote location;
generating a byte range index at the remote location that refers to bytes in the copy of the first version of the file and to bytes in the one or more delta strings associated with the second version of the file;
wherein the byte range index references entire contents of the second version of the file;
storing the byte range index at the remote location; and
using the byte range index to enable reconstruction of the second version of the file without having to apply to the copy of the first version 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 comprising:
comparing an nth version of the file to an (n−1)th version of the file, or a copy of the (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 remote location;
generating an nth byte range index at the remote location that refers to bytes in the copy of the first version 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 entire contents of the nth version of the file; and
storing the nth byte range index at the remote location.
3. The method of claim 2 further comprising:
using the nth byte range index to enable reconstruction of the nth version of the file without having to apply to the copy of the first version of the file the one or more delta strings associated with any of the second to nth versions of the file.
4. The method of claim 1 wherein comparing utilizes a signature-based algorithm that performs checksum-based delta extraction to generate the one or more delta strings.
5. The method of claim 1 wherein comparing comprises 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 of 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.
7. The method of claim 6 wherein, during the second stage, a digital signature of the block of the nth version is compared to a digital signature of the corresponding block of the (n−1)th version of the file to generate another delta string, where the block of the nth version that is processed during the second stage is smaller than the block of the nth version that is processed in the first stage.
8. The method of claim 1 wherein the 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.
9. The method of claim 8 wherein the reference refers to a data range of the copy of the first version of the file or any delta string of any version of the file.
10. The method of claim 8 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.
11. The method of claim 8 wherein the reference refers to a physical storage location.
12. The method of claim 1 wherein a given version of the file represents an application checkpoint, a user file save, or a file close.