Method and apparatus for synchronizing files

• US 5,978,805 A
• Filed: 05/14/1997
• Issued: 11/02/1999
• Est. Priority Date: 05/15/1996
• Status: Expired due to Term

• Current Assignee: Clouding Corporation (Marathon Patent Group, Inc.)
• Original Assignee: Microcom Systems Incorporated
• Inventors: Carson, Dwayne A.
• Primary Examiner(s): Amsbury, Wayne
• Assistant Examiner(s): PARDO, THUY N
• Application Number:
  US08/856,111
• Time in Patent Office: 902 Days
• Field of Search: 707/10, 707/205, 707/202, 707/204, 211/144, 834/4, 395/185.01, 395/184.01, 395/200.76, 395/286, 395/182.16
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1787 Details of non-transparently synchronising file systems
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and apparatus is disclosed for synchronizing files stored in memory of two remotely located systems. The system can generate a copy of a source file at the destination location without transferring all the data of the source file. The destination location includes a reference file that can contain similar data as that contained in the source file. The synchronization is accomplished by sending keys (representing reference blocks of data from the reference file) to the source system. At the source system, a portion of each keys called a Feature is compared with portions of source file. If the Features match, a checksum corresponding to the reference block is compared with a check sum corresponding to the source block. If the checksums match, an short message identifying the key and reference block that matched is transmitted to the destination system in order that the reference block can be copied from the reference file in order to build the synchronized file.

Claims

1. A method of transmitting data from a source file located at a first memory location of a data processing system to a destination memory location, said data processing system including a reference file located at a second memory location of said data processing system so that the transmitted data updates the reference file such that the reference and source files are synchronized, the method comprising the steps of:

(A) dividing said reference file into a plurality of reference data blocks, each data block including a plurality of data units;

(B) for each reference data block, determining a corresponding one or more reference items as a function of the data units of said reference data block, wherein each reference item is comprised of original reference file data;

(C) comparing a first portion containing original reference file data of said reference item to a portion of said source file data;

(D) if said first portion of said reference item matches said portion of said source file, determining a source block checksum as function of a source block of data units from said source file which includes the matching portion of said source file, said source block having the same number of data units as said reference data block corresponding to said reference item; and

(E) if said source block checksum matches a second portion of said reference item, copying said reference block into said destination memory location.

2. The method according to claim 1 wherein

said step of determining said reference item includes determining the reference item as a function of a reference item feature including one or more data units from the corresponding reference block, a reference block length value and a unique reference block checksum value.

3. The method according to claim 2 wherein

said step of determining said reference item includes determining the reference item feature as a function of a reference item feature from a different reference block.

4. The method according to claim 1 wherein

said step of determining said reference item includes determining the reference item as a function of a reference item feature including one or more data units from the corresponding reference block and said reference item feature is different from at least one other reference item feature associated with a different reference data block.

5. The method according to claim 1 further comprising the step of:

(F) if said source block checksum matches a second portion of said reference item, copying a portion of source file located before said source block in said source file into said destination memory location.

6. An apparatus, including at least one system processor and associated memory, for transmitting data from a source file located at a first memory location to a destination memory location, and including a reference file located at a second memory location so that the transfer of data updates the reference file such that the reference and source files are synchronized, said apparatus comprising:

means for dividing said reference file into a plurality of reference data blocks, each data block including a plurality data units;

means for determining a corresponding one or more reference items for each reference data block as a function of the data units of said reference data block, wherein each reference item is comprised of original reference file data;

means for comparing a first portion containing original reference file data of said reference item to a portion of said source file data;

means for determining a source block checksum as function of a source block of data units in said source file which includes the matching portion of said source file, said source block having the same number of data units as said reference data block corresponding to said reference item, if said first portion of said reference item matches said portion of said source file; and

means for copying said reference block into said destination memory location, if said source block checksum matches a second portion of said reference item.

7. The apparatus according to claim 6 further comprising

means for determining said reference item as a function of a reference item feature including one or more data units from the corresponding reference block, a reference block length value and a unique reference block checksum value.

8. The apparatus according to claim 7 further comprising

means for determining the reference item feature as a function of a reference item feature from a reference item feature corresponding to a different reference block.

9. The apparatus according to claim 6 wherein

said means of determining said reference item includes means for determining the reference item as a function of a reference item feature including one or more data units from the corresponding reference block and means for comparing said reference item feature to at least one other reference item feature associated with a different reference data block.

10. The apparatus according to claim 6 further comprising:

means for copying a portion of source file located before said source block in said source file into said destination memory location, if said source block checksum matches a second portion of said reference item.

11. A system, including at least one system processor and associated memory, for transmitting data from a source file located at a first memory location of said system to a destination memory location so that the transfer of data updates the reference file such that the reference and source files are synchronized, said system further including a reference file located at a second memory location, said system comprising:

a processing subsystem adapted for dividing said reference file into a plurality of reference data blocks, each data block including a plurality data units;

a processing subsystem adapted for determining a corresponding one or more reference items for each reference data block as a function of the data units of said reference data block, wherein each reference item is comprised of original reference file data;

a processing subsystem adapted for comparing a first portion containing original reference file data of said reference item to a portion of said source file to determine a matching portion of the source file data;

a processing subsystem adapted for determining a source block checksum as function of a source block of data units in said source file which includes the matching portion of said source file, said source block having the same number of data units as said reference data block corresponding to said reference item, if said first portion of said reference item matches said portion of said source file; and

a processing subsystem adapted for copying said reference block into said destination memory location, if said source block checksum matches a second portion of said reference item.

12. The system according to claim 11 further comprising

a processing subsystem adapted for determining said reference item as a function of a reference item feature including one or more data units from the corresponding reference block, a reference block length value and a unique reference block checksum value.

13. The apparatus according to claim 12 further comprising

a processing subsystem adapted for determining said reference item feature as a function of a reference item feature from a reference item feature corresponding to a different reference block.

14. The apparatus according to claim 11 wherein

said processing subsystem adapted for determining said corresponding reference item includes a processing subsystem adapted for determining the reference item as a function of a reference item feature including one or more data units from the corresponding reference block and a processing subsystem adapted for comparing said reference item feature to at least one other reference item feature associated with a different reference data block.

15. The apparatus according to claim 11 further comprising:

a processing subsystem adapted for copying a portion of source file located before said source block in said source file into said destination memory location, if said source block checksum matches a second portion of said reference item.

16. A system, having a system processor and associated memory, for transmitting data from a source file located at a first memory location of said system to a destination memory location located at a remote system, said remote system further including a reference file located at a memory location at said remote system so that the transfer of data updates the reference file such that the reference and source files are synchronized, said system comprising:

a processing subsystem adapted for receiving at least one reference item corresponding to a reference data block, wherein the reference item contains at least one data unit from said reference file;

a processing subsystem adapted for comparing a first portion containing original reference file data of said reference item to a portion of said source file data to determine a matching portion of the source file;

a processing subsystem adapted for determining a source block checksum as function of a source block of data units in said source file which includes the matching portion of said source file, said source block having the same number of data units as said reference data block corresponding to said reference item, if said first portion of said reference item matches said portion of said source file; and

a processing subsystem adapted for transmitting a signal to said remote system indicating that the reference data block matches said source block, if said source block checksum matches a second portion of said reference item.

17. The system according to claim 16 further comprising:

a processing subsystem adapted for transmitting to said remote system, a portion of said source file located before said source block in said source file into said destination memory location, if said source block checksum matches a second portion of said reference item.

18. A system, having a system processor and associated memory, for receiving data from a source file located at a first memory location at a remote system, said system further including a reference file located at a second memory location so that the transfer of data updates the reference file such that the reference and source files are synchronized, said system comprising:

a processing subsystem adapted for dividing said reference file into a plurality of reference data blocks, each data block including a plurality data units;

a processing subsystem adapted for determining a corresponding one or more reference items for each reference data block as a function of the data units of said reference data block;

a processing subsystem adapted for transmitting at least one reference item corresponding to a reference data block, wherein each reference item is comprised of original reference item data;

a processing subsystem adapted for receiving a signal from said remote system indicating that a first portion containing original reference item data of said reference item matched a portion of said source file data and a second portion of said reference item matched a source block checksum corresponding to a source block of data units in said source file which includes the matched portion of the source file and the same number of data units as the reference data block; and

a processing subsystem adapted for copying said reference block to a destination memory location at said system as a function of said signal.

19. The system according to claim 18 further comprising

a processing subsystem adapted for determining said reference item as a function of a reference item feature including one or more data units from the corresponding reference block, a reference block length value and a unique reference block checksum value.

20. The system according to claim 19 further comprising

a processing subsystem adapted for determining said reference item feature as a function of a reference item feature from a reference item feature corresponding to a different reference block.

21. The system according to claim 18 wherein

said processing subsystem adapted for determining said corresponding reference item includes a processing subsystem adapted for determining the reference item as a function of a reference item feature including one or more data units from the corresponding reference block and a processing subsystem adapted for comparing said reference item feature to at least one other reference item feature associated with a different reference data block.