Methods and systems for file replication utilizing differences between versions of files
View Patent ↗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.
1. 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 digital data of equal size;
moving a reference frame of a set resolution across adjacent portions of one of the blocks of the revised version the set resolution of the reference frame being a number of bits less than a number of bits defining the equal size of the blocks of digital data;
obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving the reference frame across adjacent portions of the one of the blocks of the revised version, the set resolution of the reference frame defining the coarse signatures;
comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version;
determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing; and
in response to determining none of the plural coarse signatures of the one of the blocks of the revised version match the coarse signature of the comparable one of the blocks of the first version, repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to the coarse signature of the comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing.
2. The method of claim 1 , wherein repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing is performed until a match is found between one of the plural coarse signatures of the one of the blocks of the revised version and the coarse signature of the comparable one of the blocks of the first version.
3. The method of claim 2 , 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.
4. The method of claim 3 , further including creating a delta file upon finding a match between the fine signatures of the revised and first versions.
5. The method of claim 3 , 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.
6. The method of claim 5 , 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.
7. The method of claim 6 , wherein after the obtaining, performing a cyclic redundancy check based on the number of bits or bytes adjacent said present position.
8. The method of claim 1 , wherein the moving the reference frame further includes shifting the reference frame in increments of one byte or one bit.
9. The method of claim 1 , 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.
10. The method of claim 1 , wherein the moving the reference frame further includes counting a shift amount of the reference frame between a first and second position.
11. The method of claim 10 , further including using the shift amount in creating a delta file.
12. A system comprising:
a processor; and
a memory coupled with and readable by the processor and having stored therein a sequence of instructions which, when executed by the processor, causes the processor to compare data of a first and a revised version of a file to determine differences between the versions by:
segmenting the first and the revised versions into blocks of digital data of equal size,
moving a reference frame of a set resolution across adjacent portions of one of the blocks of the revised version the set resolution of the reference frame being a number of bits less than a number of bits defining the equal size of the blocks of digital data,
obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving the reference frame across adjacent portions of the one of the blocks of the revised version, the set resolution of the reference frame defining the coarse signatures,
comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version,
determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing, and
in response to determining none of the plural coarse signatures of the one of the blocks of the revised version match the coarse signature of the comparable one of the blocks of the first version, repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to the coarse signature of the comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing.
13. The system of claim 12 , wherein repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing is performed until a match is found between one of the plural coarse signatures of the one of the blocks of the revised version and the coarse signature of the comparable one of the blocks of the first version.
14. The system of claim 13 , 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.
15. The system of claim 14 , further including creating a delta file upon finding a match between the fine signatures of the revised and first versions.
16. The system of claim 14 , 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.
17. The system of claim 16 , 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.
18. The system of claim 17 , wherein after the obtaining, performing a cyclic redundancy check based on the number of bits or bytes adjacent said present position.
19. The system of claim 12 , wherein the moving the reference frame further includes shifting the reference frame in increments of one byte or one bit.
20. The system of claim 12 , 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.
21. The system of claim 12 , wherein the moving the reference frame further includes counting a shift amount of the reference frame between a first and second position.
22. The system of claim 21 , further including using the shift amount in creating a delta file.
23. A computer-readable memory having stored therein a sequence of instructions which, when executed by a processor, causes the processor to compare data of a first and a revised version of a file to determine differences between the versions by:
segmenting the first and the revised versions into blocks of digital data of equal size,
moving a reference frame of a set resolution across adjacent portions of one of the blocks of the revised version the set resolution of the reference frame being a number of bits less than a number of bits defining the equal size of the blocks of digital data,
obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving the reference frame across adjacent portions of the one of the blocks of the revised version, the set resolution of the reference frame defining the coarse signatures,
comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version,
determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing, and
in response to determining none of the plural coarse signatures of the one of the blocks of the revised version match the coarse signature of the comparable one of the blocks of the first version, repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to the coarse signature of the comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing.
24. The computer-readable memory of claim 23 , wherein repeating said moving the reference frame across adjacent portions of one of the blocks of the revised version, obtaining plural coarse signatures of the one of the blocks of the revised version based on said moving, comparing each of the plural coarse signatures of the one of the blocks of the revised version to a coarse signature of a comparable one of the blocks of the first version, and determining whether any of the plural coarse signatures of the one of the blocks of the revised version matches the coarse signature of the comparable one of the blocks of the first version based on said comparing is performed until a match is found between one of the plural coarse signatures of the one of the blocks of the revised version and the coarse signature of the comparable one of the blocks of the first version.
25. The computer-readable memory of claim 24 , 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.
26. The computer-readable memory of claim 25 , further including creating a delta file upon finding a match between the fine signatures of the revised and first versions.
27. The computer-readable memory of claim 25 , 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.
28. The computer-readable memory of claim 27 , 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.
29. The computer-readable memory of claim 28 , wherein after the obtaining, performing a cyclic redundancy check based on the number of bits or bytes adjacent said present position.
30. The computer-readable memory of claim 23 , wherein the moving the reference frame further includes shifting the reference frame in increments of one byte or one bit.
31. The computer-readable memory of claim 23 , 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.
32. The computer-readable memory of claim 23 , wherein the moving the reference frame further includes counting a shift amount of the reference frame between a first and second position.
33. The computer-readable memory of claim 32 , further including using the shift amount in creating a delta file.