Data file synchronization

• US 6,636,872 B1
• Filed: 02/22/2000
• Issued: 10/21/2003
• Est. Priority Date: 03/02/1999
• Status: Expired due to Term

• Current Assignee: Flexera Software LLC
• Original Assignee: ManageSoft Corporation (Flexera Software LLC)
• Inventors: Hughes, Paul, Heath, Clifford Z
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Veillard, Jacques
• Application Number:
  US09/507,792
• Time in Patent Office: 1,337 Days
• Field of Search: 707/2, 707/3, 707/4, 707/10, 707/101, 707/102, 707/200, 709/203, 709/201, 709/217, 709/219, 709/246, 709/248, 717/1, 717/4, 717/5, 717/7, 717/9
• US Class Current: 1/1
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

A method for synchronising data between a receiving computer and a sending computer by way of a computer network or the like, wherein the sending computer has a source file and the receiving computer has a reference file. The source file is arranged at the sending computer into a sequence of data blocks, each block comprising a predetermined number of data units (e.g. bytes), and a source key value is computed for each block in the source file, and the source key values are transmitted to the receiving computer. At the receiving computer, the source key values are compared with reference key values computed for each predetermined number of contiguous data units in the reference file to determine matches between source key values and reference key values. Then, based on indications of which source keys do not have matching reference keys, specific data blocks are transmitted from the source file corresponding to the unmatched source keys. Then, the receiving computer constructs a target file from the contiguous data units in the reference file determined to have. reference key values matching respective source key values and the data blocks from the source file received from the sending computer. In the context of the Internet, the provision of the source key values and data blocks to the receiving computer can conveniently be carried out in appropriate circumstances by a proxy server or the like, using standard caching techniques.

Claims

1. A method for synchronizing data between a receiving computer and a sending computer, wherein the sending computer has a source file and the receiving computer has a reference file and the receiving and sending computers are coupled for communication therebetween by way of a communications link or network, the method comprising:

i) arranging the source file at the sending computer into a sequence of data blocks, each block comprising a predetermined number of contiguous data units, and computing a source key value for each block in the source file;

ii) transmitting the source key values from the sending computer to the receiving computer;

iii) at the receiving computer, comparing the source key values with reference key values computed for respective blocks comprising a predetermined number of contiguous data units in the reference file to determine matches between source key values and reference key values;

iv) communicating from the receiving computer to the sending computer an indication of which source keys do not have matching reference keys, and transmitting data blocks from the source file corresponding to the unmatched source keys from the sending computer to the receiving computer; and

v) constructing at the receiving computer a target file from the contiguous data units in the reference file determined to have reference key values matching respective source key values and the data blocks from the source file received from the sending computer wherein the constructed target file at the receiving computer is synchronized with the source file at the sending computer.

2. A method as in claim 1, wherein the source key values for the sequence of source file data blocks are pre-computed and stored for subsequent use.

3. A method as in claim 2, wherein:

the sending computer and receiving computer are coupled to communicate by way of an intervening computer containing a cache memory, and

a copy of the source key values are stored in the intervening computer cache memory and provided therefrom to the receiving computer.

4. A method for constructing a target data file at a first computer from a reference file stored at the first computer and a source file at a remote second computer, the first computer acting as a receiving computer and the remote second computer acting as a sending computer, such that the constructed target file is synchronized with the source file, said method comprising:

i) requesting and receiving from the remote second computer a source file summary comprising a sequence of source key values being codes derived from data blocks of predetermined length making up the source file;

ii) generating reference key values for respective contiguous portions of the reference file of predetermined length and, at the first computer, comparing the reference key values with the received source key values, to determine matches therebetween;

iii) requesting and receiving from the remote second computer those data blocks from the source file for which no match was found between the corresponding source key value and the reference key values at the first computer; and

iv) constructing at the first computer a target data file from the received source file data blocks and those contiguous portions of the reference file for which the corresponding reference key value was found to match a source key value, wherein the constructed target file is synchronized with the source file.

5. A method as in claim 4, wherein:

the first and second computers are coupled to communicate over a computer network including a proxy computer which is closer or more conveniently located to communicate with the first computer than is the second computer, and

requesting and receiving the source file summary includes providing the source file summary to the first computer from a copy of the source file summary generated at the second computer and previously received and stored by the proxy computer.

6. A method as in claim 5, wherein requesting and receiving data blocks for which no match was found includes providing those data blocks to the first computer from the proxy computer from a copy of the source file data blocks previously provided from the second computer and stored in a cache memory at the proxy computer.

7. In a computer network having a sending computer, a receiving computer and at least one proxy computer, wherein the sending computer has a source file and the receiving computer has a reference file and the receiving, sending and a proxy computer are coupled for communication therebetween by way of said network, a method for synchronizing data between the receiving computer and the sending computer, the method comprising:

i) arranging the source file at the sending computer into a sequence of data blocks, each block comprising a predetermined number of data units, and computing a source key value for each block in the source file;

ii) transmitting the source key values from the sending computer to the receiving computer;

iii) at the receiving computer, comparing the source key values with reference key values computed for respective blocks comprising a predetermined number of contiguous data units in the reference file to determine matches between source key values and reference key values;

iv) communicating from the receiving computer to the sending computer or proxy computer an indication of which source keys do not have matching reference keys, and transmitting data blocks from the source file corresponding to the unmatched source keys from the sending computer or proxy computer to the receiving computer; and

v) constructing at the receiving computer a target file from the contiguous data units in the reference file determined to have reference key values matching respective source key values and the data blocks from the source file received from the sending computer wherein the constructed target file at the receiving computer is synchronized with the source file at the sending computer.

8. A method as in claim 7, wherein transmitting the source key values from the sending computer to the receiving computer includes storing a copy of the source key values in a cache at the proxy computer and transmitting the source key values from the proxy computer to the receiving computer on request.

9. A method as in claim 7 wherein:

a copy of at least some of the source file data blocks are transmitted from the sending computer and stored in a cache at the proxy computer; and

transmitting data blocks from the source file includes transmitting said data blocks form the proxy computer cache copy to the receiving computer.

10. A method for synchronizing data between a receiving computer and a sending computer, wherein the sending computer has a source file and the receiving computer has a reference file and the receiving and sending computers are coupled for communication therebetween by way of a communications link or network, the method comprising:

(i) computing source key values for sequential non-overlapping source blocks in the source file, each of said source blocks comprising a predetermined number of contiguous data units;

(ii) transmitting the source key values from the sending computer to the receiving computer;

(iii) at the receiving computer, comparing the source key values with reference key values computed for reference data blocks comprising a predetermined number of contiguous data units in the reference file to determine matches between source key values and reference key values;

(iv) communicating from the receiving computer to the sending computer an indication of which source keys do not have matching reference keys, and transmitting source data blocks corresponding to the unmatched source keys from the sending computer to the receiving computer; and

(v) constructing at the receiving computer a target file from (a) the reference data blocks having reference key values matching respective source key values, and (b) the source data blocks received from the sending computer, wherein the constructed target file at the receiving computer is synchronized with the source file at the sending computer.

11. A method as claimed in claim 10 wherein said reference key values are computed for overlapping reference data blocks comprising a predetermined number of contiguous data units in the reference file.

12. A method as claimed in claim 10 wherein said reference key values are computed for overlapping and non-overlapping reference data blocks comprising a predetermined number of contiguous data units in the reference file.

13. A method for synchronizing data between a receiving computer and a sending computer, wherein the sending computer has a source file and the receiving computer has a reference file and the receiving and sending computers are coupled for communication therebetween by way of a communications link or network, the method comprising:

(i) computing source key values for sequential non-overlapping source blocks in the source file, each of said source blocks comprising a predetermined number of contiguous data units;

(ii) transmitting the source key values from the sending computer to the receiving computer;

(iii) at the receiving computer, computing a reference key value for a reference data block in the reference file, said reference block comprising a predetermined number of contiguous data units;

(iv) comparing the reference key value with said source key values to determine a matching source key value;

(v) if a matching source key value is determined, selecting the corresponding reference data block and recomputing the reference key value for a new non-overlapping reference data block in the reference file;

otherwise, recomputing the reference key value for a new overlapping reference data block in the reference file;

(vi) returning to step (iv) if a new reference data block was determined in step (v);

(vii) communicating from the receiving computer to the sending computer an indication of which source key values do not have matching reference key values, and transmitting source data blocks corresponding to the unmatched source keys from the sending computer to the receiving computer; and

(viii) constructing at the receiving computer a target file from (a) the selected reference data blocks whose corresponding reference key values match source key values, and (b) the source data blocks received from the sending computer, wherein the constructed target file at the receiving computer is synchronized with the source file at the sending computer.

14. A method as claimed in claim 13, wherein selecting the reference data block includes storing location data identifying the location of the reference data block in the reference file.

15. A method as claimed in claim 13, wherein the new overlapping reference data block is offset by one byte from the previous reference data block.