File comparison for data backup and file synchronization

• US 6,101,507 A
• Filed: 02/10/1998
• Issued: 08/08/2000
• Est. Priority Date: 02/11/1997
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Connected Corporation (Iron Mountain Incorporated)
• Inventors: Marson, Howard, Cane, David, Vaitzblit, Lev, Speare, Philip, Hirschman, David
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/021,705
• Time in Patent Office: 910 Days
• Field of Search: 707/203, 707/1, 707/204, 707/201, 707/207, 714/6, 711/162
• US Class Current: N/A
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

File comparison employs a single function F to calculate a digital signature from data in a sliding window. The digital signature is both incrementally computable and position sensitive. In particular, F is computable without reprocessing each byte in the array when the window is advanced and facilitates detection of such changes as transposed bytes of data. The function F is defined by two qualities. First, for F(A+B), where A is an array, F(A+B)=F(A)+F(B). Second, given a concatenation operator "!" such that "0!A" indicates an array A with 0 inserted before A, the function F has the property that there is a function G such that F(0!A)=G(F(A'"'"'0)). Both polynomials and cyclic redundancy checks ("CRC") may be used as that class of function.

Claims

1. A system for comparing a first data set on a first storage device with a second data set on a second storage device, comprising:

a transmission medium for transmitting data between the first storage device and the second storage device;

a control program that generates a first digital signature from the first data set and a second digital signature from the second data set, the control program including a function F that incrementally calculates position sensitive first and second digital signatures, wherein said first data set is defined by a sliding indexed window and said incremental calculation comprises data leaving the window, data entering the window, and a previous digital signature; and

a comparator for determining whether the first digital signature matches the second digital signature.

2. The comparing system of claim 1 wherein polynomials are used to implement the function F.

3. The comparing system of claim 2 wherein the function F is a polynomial:

F(A_n)=Sum (a_i+n^* N.sup.(w-1-i)) modulo 2⁶⁴ for i=0 to w-1, for an array A starting at index position n with a window size of w, where a_i is an element of A.

4. The comparing system of claim 3 wherein, if the window is advanced in A, then a new function is computed as:

F(A_n=1)=N^* F(A_n)-a_n^* N^w-1 +a_n+w modulo 2⁶⁴.

5. The comparing system of claim 1 wherein a cyclic redundancy check is used to implement the function F.

6. A method for calculating a position sensitive digital signature from data on a first storage medium for comparison with a digital signature that represents data on a second storage medium, comprising the steps of:

selecting the data in the first system with an indexed sliding window;

applying a function F to the data within the window to generate the incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and

comparing the position sensitive digital signature with at least one digital signature representing data in the second system.

7. The method of claim 6 including the further step of employing a polynomials to implement the function F.

8. The method of claim 7 including the further step of employing the function:

F(A_n)=Sum (a_i+n^* N.sup.(w-1-i)) modulo 2⁶⁴ for i=0 to w-1, for an array A starting at index position n with a window size of w, where a_i is an element of A, to implement the function F.

9. The method of claim 8 including the further step of, if the window is advanced in A, computing a new position sensitive digital signature as:

F(A_n=1)=N^* F(A_n)-a_n^* N^w-1 +a_n+w module 2⁶⁴.

10. The method of claim 6 including the further step of employing a cyclic redundancy check to implement the function F.

11. A method for providing an incremental backup of a first memory in a second memory wherein a set of different files have previously been stored in the second memory, comprising the steps of:

selecting a file from the first memory for examination;

generating a signature from a portion of the file defined by a sliding indexed window;

comparing the generated signature with signatures generated from the set of previously stored files having different filenames;

determining the closest matching previously stored file, relative to the file under examination, where the stored file and the file under examination have different filenames, by identifying at least some portions of the stored file and the file under examination which are different, wherein said determining comprises applying a function F to the data within said sliding indexed window to generate an incremental position sensitive digital signature, wherein said function of F comprises input from data leaving said sliding indexed window, data entering said sliding indexed window, and a previously generated digital signature; and

storing the portions of the file under examination identified as being different from the closest matching file in the second memory.

12. The method of claim 11 including the further step of creating a match count table with a row corresponding to each respective previously stored file.

13. The method of claim 12 including the further step of comparing the generated signature with signatures generated for N blocks of the previously stored files, where N is a predetermined integer.

14. A method for determining a minimum set of data compression units for restoring a file from a base copy and a plurality of revision elements, comprising the steps of:

selecting the base copy and revision elements required to build the file;

sorting the selected base copy and revision elements into a list with the most recently generated revision element at the list head and the base copy at the list tail;

reading information for each selected revision element into an array with five columns;

chunk, operation, data offset, data length, and target offset;

creating an output array indicative of the reconstructed file with five columns;

revision element pointer, chunk, data offset, data length, and target offset;

calling a recursive function for the most recent revision, requesting data offset 0 and the final file length, and passing in target offset 0, the recursive function iterating through the array columns and comparing the requested data offset and length with the target of offset and data length of each item, and in the case of a match, writing an entry into the output array if the array item is a data operation;

optimizing, via a block filter, an optimal set of array elements wherein elements not affecting said output array are ignored; and

sorting the output array by revision element and chunk; and

transmitting the array followed by the transmission blocks for each data block.

15. The method of claim 14 wherein the recursive function operates by iterating through the array items, and comparing the requested data offset and length with the target offset and data length of each item.

16. The method of claim 15 wherein, if a match or partial match is found, either writing an entry into the output array item or calling the recursive function again for the next list element with the offset equal to the item'"'"'s data offset minus the target offset of each item plus the requested data offset, and the length equal to the remaining requested length and the item length.

17. The method of claim 16 wherein, if a partial match was found, incrementing the requested data offset and target offset and decrementing the requested length and continuing to iterate.