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

• US 9,934,301 B2
• Filed: 10/02/2012
• Issued: 04/03/2018
• Est. Priority Date: 03/28/2003
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Srivastava, Piyush Kumar, Murthy, Madhusudhana Honnuduke Srinivasa
• Primary Examiner(s): Singh, Amresh
• Application Number:
  US13/633,526
• Publication Number:
  US 20130124472A1
• Time in Patent Office: 2,009 Days
• Field of Search: None
• 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 system for performing file store synchronization across multiple servers, comprising:

a processor; and

a memory coupled with and readable by the processor and storing therein a set of instructions which, when executed by the processor, causes the processor to initiate a file store synchronization process by;

receiving a first file from a first computer server, the first file comprising a plurality of physical blocks of data located at various allocated positions on a memory device of the first computer server;

receiving a second file from a second computer server, the second file comprising a second plurality of physical blocks of data located at various allocated positions on the memory device of the second computer server;

performing, in logical order for each particular physical block of the first plurality of the physical blocks of the first file;

(a) determining a first signature parameter for the particular physical block of the first file by retrieving a predetermined number of bits from a predetermined location within the particular physical block of the first file, wherein the first signature parameter for the particular physical block of the first file is determined based upon a subset of the data within the particular physical block that is less than all of the data in the particular physical block;

(b) determining a first signature parameter for a corresponding physical block of the second file by retrieving the same predetermined number of bits from the same predetermined location within the corresponding physical block of the second file, wherein the first signature parameter for the corresponding physical block of the second file is determined based upon a subset of the data within the corresponding physical block that is less than all of the data in the corresponding physical block;

(c) determining whether the retrieved bits comprising the first signature parameter for the particular physical block of the first file match the retrieved bits comprising the first signature parameter for the corresponding physical block of the second file; and

(d) in response to determining that the first signature parameter for the particular physical block of the first file matches the first signature parameter of the corresponding physical block of the second file, performing the following additional steps for the particular physical block of the first file;

(i) determining a second signature parameter for the particular physical block of the first file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the particular physical block of the first file;

(ii) determining a second signature parameter for the corresponding physical block of the second file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the corresponding physical block of the second file;

(iii) determining whether the second signature parameter comprising the output of the one or more algorithms for the particular physical block of the first file matches the second signature parameter comprising the output of the one or more algorithms for the corresponding physical block of the second file; and

(iv) in response to determining that the second signature parameter of the particular physical block of the first file matches the second signature parameter of the corresponding physical block of the second file, creating a delta file using the second signature parameters of the at least one physical block of the second file by generating primitive commands and corresponding logical data parameters for the primitive commands, wherein the logical data parameters comprise logical offset addresses for the base file and logical data lengths for the base file; and

initiating a file store synchronization process between the first computer server and the second computer server, using the delta file as input to the file store synchronization process.

2. The system as recited in claim 1, wherein the second signature parameter for each physical block of the first file comprises an amount of valid data within the associated physical block.

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

4. The system of claim 1, wherein the first signature parameter of the first file and the first signature parameter of the second file comprise coarse signature values.

5. The system of claim 4, wherein the second signature parameter of the first file and the second signature parameter of the second file comprise fine signature values.

6. The system of claim 5, the instructions, when executed by the processor, further causing the processor to perform comparing in logical order of the physical blocks of the first file a first signature parameter for each of these physical blocks of the first file to a first signature parameter of at least one physical block of the second file, by moving a reference frame from a first physical block to a second or subsequent physical block until a match is found between the first signature parameter of at least one physical block of the first file and the first signature parameter of the at least one physical block of the second file.

7. The system of claim 6, the instructions, when executed by the processor, further causing the processor to perform comparing a second signature parameter for each of these physical blocks of the first file to a second signature parameter of at least one physical block of the second file, by moving a reference frame from a first location in a physical block to a second or subsequent location in a physical block until a match is found between the second signature parameter of at least one physical block of the first file and the second signature parameter of the at least one physical block of the second file.

8. A computer-readable memory device comprising a set of instructions stored therein which, when executed by a processor, causes the processor to perform file store synchronization across multiple servers, by:

receiving a first file from a first computer server, the first file comprising a first plurality of physical blocks of data located at various allocated positions on a memory device of the first computer server;

receiving a second file from a second computer server, the second file comprising a plurality of physical blocks of data located at various allocated positions on the memory device of the second computer server;

performing the following steps for each particular physical block of the first plurality of physical blocks in the first file;

(a) determining a first signature parameter for the particular physical block of the first file by retrieving a predetermined number of bits from a predetermined location within the particular physical block of the first file, wherein the first signature parameter for the particular physical block of the first file is determined based upon a subset of the data within the particular physical block that is less than all of the data in the particular physical block;

(b) determining a first signature parameter for a corresponding physical block of the second file by retrieving the same predetermined number of bits from the same predetermined location within the corresponding physical block of the second file, wherein the first signature parameter for the corresponding physical block of the second file is determined based upon a subset of the data within the corresponding physical block that is less than all of the data in the corresponding physical block of the second file;

(c) determining whether the retrieved bits comprising the first signature parameter for the particular physical block of the first file match the retrieved bits comprising the first signature parameter for the corresponding physical block of the second file; and

(d) in response to determining that the first signature parameter for the particular physical block of the first file matches the first signature parameter of the corresponding physical block of the second file, performing the following additional steps for the particular physical block of the first file;

(i) determining a second signature parameter for the particular physical block of the first file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the particular physical block of the first file;

(ii) determining a second signature parameter for the corresponding physical block of the second file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the corresponding physical block of the second file;

(iii) determining whether the second signature parameter comprising the output of the one or more algorithms for the particular physical block of the first file matches the second signature parameter comprising the output of the one or more algorithms for the corresponding physical block of the second file; and

(iv) in response to determining that the second signature parameter of the particular physical block of the first file matches the second signature parameter of the corresponding physical block of the second file, creating a delta file using the second signature parameters of the at least one physical block of the second file by generating primitive commands and corresponding logical data parameters for the primitive commands, wherein the logical data parameters comprise logical offset addresses for the base file and logical data lengths for the base file; and

initiating a file store synchronization process between the first computer server and the second computer server, using the delta file as input to the file store synchronization process.

9. The computer-readable memory device as recited in claim 8, wherein the second signature parameter for each physical block of the first file comprises an amount of valid data within the associated physical block.

10. The computer-readable memory device as recited in claim 8, wherein the second signature parameter for each physical block of the first file comprises a cyclic redundancy check value residing in a signature file.

11. The computer-readable memory device of claim 8, wherein the first signature parameter of the first file and the first signature parameter of the second file comprise coarse signature values.

12. The computer-readable memory device of claim 11, wherein the second signature parameter of the first file and the second signature parameter of the second file comprise fine signature values.

13. The computer-readable memory device of claim 12, wherein the instructions, when executed by the processor, further cause the processor to compare the first signature parameter for each of the particular physical blocks of the first file to the first signature parameter of the corresponding physical block of the second file, by moving a reference frame from a first physical block to a second or subsequent physical block until a match is found between the first signature parameter of the particular physical block of the first file and the first signature parameter of a corresponding physical block of the second file.

14. The computer-readable memory device of claim 13, wherein the instructions, when executed by the processor, further cause the processor to compare the second signature parameter for each of the particular physical blocks of the first file to the second signature parameter of the corresponding physical block of the second file, by moving a reference frame from a first location in a physical block to a second or subsequent location in a physical block until a match is found between the second signature parameter of the particular physical block of the first file and the second signature parameter of a corresponding physical block of the second file.

15. A method of performing file store synchronization across multiple servers, the method comprising:

receiving a first file from a first computer server, the first file comprising a first plurality of physical blocks of data located at various allocated positions on a memory device of the first computer server;

receiving a second file from a second computer server, the second file comprising a second plurality of physical blocks of data located at various allocated positions on a memory device of the second computer server;

for each particular physical block of the first plurality of physical blocks in the first file, performing the following steps;

(a) determining a first signature parameter for the particular physical block of the first file by retrieving a predetermined number of bits from a predetermined location within the particular physical block of the first file, wherein the first signature parameter for the particular physical block of the first file is determined based upon a subset of the data within the particular physical block that is less than all of the data in the particular physical block;

(b) determining a first signature parameter for a corresponding physical block of the second file by retrieving the same predetermined number of bits from the same predetermined location within the corresponding physical block of the second file, wherein the first signature parameter for the corresponding physical block of the second file is determined based upon a subset of the data within the corresponding physical block that is less than all of the data in the corresponding physical block of the second file;

(c) determining whether the retrieved bits comprising the first signature parameter for the particular physical block of the first file match the retrieved bits comprising the first signature parameter for the corresponding physical block of the second file; and

(d) in response to determining that the first signature parameter for the particular physical block of the first file matches the first signature parameter of the corresponding physical block of the second file, performing the following additional steps for the particular physical block of the first file;

(i) determining a second signature parameter for the particular physical block of the first file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the particular physical block of the first file;

(ii) determining a second signature parameter for the corresponding physical block of the second file, by executing at least one of a cyclic redundancy check (CRC) algorithm or an MD5 algorithm, using as input all bits of the corresponding physical block of the second file;

(iii) determining whether the second signature parameter comprising the output of the one or more algorithms for the particular physical block of the first file matches the second signature parameter comprising the output of the one or more algorithms for the corresponding physical block of the second file; and

(iv) in response to determining that the second signature parameter of the particular physical block of the first file matches the second signature parameter of the corresponding physical block of the second file, creating a delta file using the second signature parameters of the at least one physical block of the second file by generating primitive commands and corresponding logical data parameters for the primitive commands, wherein the logical data parameters comprise logical offset addresses for the base file and logical data lengths for the base file; and

initiating a file store synchronization process between the first computer server and the second computer server, using the delta file as input to the file store synchronization process.

16. The method of claim 15, wherein the first signature parameter of the first file and the first signature parameter of the second file comprise coarse signature values.

17. The method of claim 16, wherein the second signature parameter of the first file and the second signature parameter of the second file comprise fine signature values.

18. The method of claim 17, further comprising comparing the first signature parameter for each of the particular physical blocks of the first file to the first signature parameter of the corresponding physical block of the second file, by moving a reference frame from a first physical block to a second or subsequent physical block until a match is found between the first signature parameter of the particular physical block of the first file and the first signature parameter of a corresponding physical block of the second file.

19. The method of claim 18, further comprising comparing the second signature parameter for one or more of the particular physical blocks of the first file to the second signature parameter for the corresponding one or more physical blocks of the second file, by moving a reference frame from a first location in a physical block to a second or subsequent location in a physical block until a match is found between the second signature parameter of the particular physical block of the first file and the second signature parameter of a corresponding physical block of the second file.