Methods and systems for file replication utilizing differences between versions of files

• US 20070288533A1
• Filed: 08/14/2007
• Published: 12/13/2007
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Srivastava, Piyush, H.S., Madhusudhana
• Granted Patent: US 7,844,580 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Methods and systems for efficient file replication are provided. In some embodiments, one or more coarse signatures for blocks in a base file are compared with those coarse signatures for blocks of a revised file, until a match is found. A fine signature is then generated for the matching block of the revised file and compared to a fine signature of the base file. Thus, fine signatures are not computed unless a coarse signature match has been found, thereby minimizing unneeded time-consuming fine signature calculations. Methods are also provided for determining whether to initiate a delta file generation algorithm, or whether to utilize a more efficient replication method, based upon system and/or file parameters. In accordance with additional embodiments, the lengths of valid data on physical blocks are obtained from physical block mappings for the files, and these lengths and mappings are utilized for delta file generation, to minimize unnecessary signature computations.

Claims

1. A computerized method for determining whether to create a delta file reflecting differences between a base file and a revised version of the base file, the method comprising:

determining whether the differences between a base file and a revised version exceed a threshold change amount, further including shifting a reference frame of data of a set length of the revised file and counting an amount of said shifting when a comparison of signatures of the base file and the revised file do not match; and

if the threshold change amount is exceeded, avoiding the completion of a delta file and transmitting a copy of the revised version for replication purposes.

2. The computerized method as recited in claim 1, wherein the determining operation further comprises:

comparing the amount of said shifting of the step of counting to a threshold to establish if the threshold change amount has been exceeded.

3. The computerized method as recited in claim 2, wherein the deciding operation comprises:

comparing an identifier for the shifted frame of data with an identifier for a block of data in the base file.

4. The computerized method as recited in claim 3, wherein the identifier for the block of data in the base file comprises a cyclic redundancy check value residing in a base signature file.

5. A system for comparing two versions of a file to determine the differences between the versions, the system comprising:

a first file comprising a plurality of physical blocks of data located at various allocated positions on a memory device;

a second file comprising a plurality of physical blocks of data located at various allocated positions on a memory device; and

a set of executable instructions configured to create a delta file by proceeding in logical order of the physical blocks of the first file and comparing a signature parameter for each of these physical blocks of the first file to a signature parameter of at least one physical block of the second file, wherein the instructions are configured to create the delta file by generating primitive commands and corresponding logical data parameters for the primitive commands, further wherein the logical data parameters comprise logical offset addresses for the base file and logical data lengths for the base file.

6. The system as recited in claim 5, wherein the signature parameter comprises the amount of valid data within the physical blocks.

7. The system as recited in claim 5, wherein the signature parameter for each physical block of the first file comprises a cyclic redundancy check value residing in a signature file.

8. A computer implemented method for comparing data of a first and a revised version of a file to determine differences between the versions, comprising:

segmenting the first and the revised versions into blocks of data of equal size; and

moving a reference frame of a set resolution across adjacent portions of one of the blocks of the revised version to obtain plural coarse signatures of the one of the blocks of the revised version for comparing to a coarse signature of a comparable one of the blocks of the first version.

9. The method of claim 8, further including recursively moving the reference frame until a match of the comparing of the coarse signatures is found.

10. The method of claim 8, wherein the moving the reference frame further includes shifting the reference frame in increments of one byte or one bit.

11. The method of claim 9, upon finding the match, further including comparing a fine signature of the one of the blocks of the revised version to a fine signature of the comparable one of the blocks of the first version.

12. The method of claim 11, further including creating a delta file upon finding a match between the fine signatures of the revised and first versions.

13. The method of claim 8, wherein the moving the reference frame further includes bridging the reference frame over a boundary of at least one of the blocks of data of the revised version.

14. The method of claim 11, wherein the comparing the fine signatures of the revised and first versions further includes calculating the fine signature of the one of the blocks of the revised version.

15. The method of claim 14, wherein the calculating further includes obtaining a number of bits or bytes adjacent a present position of the reference frame, wherein the number is equal to said equal size of the blocks of data of the revised version.

16. The method of claim 15, wherein after the obtaining, performing a cyclic redundancy check based on the number of bits or bytes adjacent said present position.

17. The method of claim 8, wherein the moving the reference frame further includes counting a shift amount of the reference frame between a first and second position.

18. The method of claim 17, further including using the shift amount in creating a delta file.

19. A computer implemented method for comparing data of a first and a revised version of a file to determine differences between the versions, comprising:

segmenting the first and the revised versions into blocks of data of equal size;

moving a reference frame of a set resolution across adjacent portions of one of the blocks of the revised version to obtain plural coarse signatures of the one of the blocks of the revised version for comparing to a coarse signature of a comparable one of the blocks of the first version;

recursively moving the reference frame until a match of the comparing of the coarse signatures is found, if possible; and

upon finding the match, further including calculating a fine signature of some of the data of the revised version.

20. The method of claim 19, further including comparing the fine signature to a fine signature of the comparable one of the blocks of the first version.

21. The method of claim 19, wherein the calculating the fine signature further includes obtaining a number of bits or bytes adjacent a present position of the reference frame.

22. The method of claim 19, wherein the moving the reference frame further includes bridging the reference frame over a boundary of at least one of the blocks of data of the revised version.

24. The method of claim 19, wherein the moving the reference frame further includes counting a shift amount of the reference frame between various positions.

25. The method of claim 24, further including creating a delta file indicative of the differences between the versions, the creating using the shift amount.

23. The method of 22, wherein the bridging the reference frame further includes accessing data in different memory locations.